遗传算法讲义523

1TechnicalReportTSP问题的遗传算法求解马广才，大连大学数学建模工作室一、序言本材料简单介绍了遗传算法的概念和算法的流程，结合2010年东北三省数学建模联赛B题：周游全中国，给出了用遗传算法求解TSP问题的matlab程序。二、遗传算法的概念遗传算法（GeneticAlgorithm）是一类借鉴生物界的进化规律（适者生存，优胜劣汰遗传机制）演化而来的随机化搜索方法。它是由美国的J.Holland教授1975年首先提出。它将问题域中的可能解看作是群体的个体,并将个体编码成符号串形式(即染色体),模拟生物进化过程,对群体反复进行杂交等操作,根据预定的适应度函数对每个个体进行评价,依据优胜劣汰的进化规则,不断得到更优的群体,同时搜索优化群体中的最优个体,求得满足要求的最优解。三、遗传算法的基本流程a)初始化:设置进化代数计数器t=0，设置最大进化代数T，随机生成M个个体作为初始群体P(0)。b)个体评价:计算群体P(t)中各个个体的适应度。c)选择运算:将选择算子作用于群体。选择的目的是把优化的个体直接遗传到下一代或通过配对交叉产生新的个体再遗传到下一代。选择操作是建立在群体中个体的适应度评估基础上的。d)交叉运算；将交叉算子作用于群体。所谓交叉是指把两个父代个体的部分结构加以替换重组而生成新个体的操作。遗传算法中起核心作用的就是交叉算子。e)变异运算:将变异算子作用于群体。即是对群体中的个体串的某些基因座上的基因值作变动。群体P(t)经过选择、交叉、变异运算之后得到下一代群体P(t1)。f)终止条件判断:若tT,则以进化过程中所得到的具有最大适应度个体作为最优解输出，终止计算。四、问题描述TSP问题，又称旅行商问题,旅行推销员问题,是指对于给定的n个城市,旅行商从某一城市出发不重复的访问其余城市后回到出发的城市,要求找出一条旅行路线,使总的旅行路程最短。2010年东北三省数学建模联赛B题：周游全中国，即为一个典型的TSP问题，图论中，将地图视为一个附权图，该问题就是求该图的一个最短哈密尔顿圈。到目前为止，哈密尔顿图的非平凡的充分必要条件尚不知道，因此TSP问题还没有有效的方法，现在的解决方法都是寻找一个近似最优的哈密尔顿圈。同时，TSP问题属于组合优化为范畴，目前流行的求解算法有模拟退火算法、蚁群算法、遗传算法等启发式算法。下面我们将给出用遗传算法求解该问题的MATLAB程序。2遗传算法的一般算法流程五、求解程序1、种群规模、最大繁殖代数等基本参数的设定我们设定种群的规模为50，即种群中有50个个体，一个个体对应问题的一个解。基因长度为34，即问题中我们要走访34个城市。最大的繁殖后代为第1000代。个体发生杂交的概率为0.9，发生变异的概率为0.15。读入距离矩阵distance，距离矩阵是一个34*34，主对角线为0的对称矩阵。-----------------------------------------------------------------PopSize=50;City=34;k=20;Max_gen=1000;PcX=0.9;Pm=0.15;distance=xlsread('distance.xls');-----------------------------------------------------------------2、种群的初始化这里我定义了一个函数Initialize.m用来初始化种群。-----------------------------------------------------------------functionPop=Initialize(PopSize,City)Pop=zeros(PopSize,City);fori=1:PopSizePop(i,:)=randperm(City);endPop=[Pop,zeros(PopSize,1)];-----------------------------------------------------------------Pop先设为PopSize行，City列的全0矩阵。之后，Pop的每一行为1—City的随机序列。最后在Pop矩阵加一列0，该列用以存放对应个体的适应值。3行列PopSize02514180232170302381City3、初始种群适应值的计算为计算种群的适应值，我定义了一个Caculate.m函数。对种群中的每个个体，对应Pop矩阵中的每一行，分别计算按照该行的路径走的总路程，并存于该行的最后一个位置。-----------------------------------------------------------------fori=1:sdd=0;forj=1:t-2dd=dd+distance(Pop(i,j),Pop(i,j+1));enddd=dd+distance(Pop(i,1),Pop(i,t-1));Pop(i,t)=dd;End-----------------------------------------------------------------)(251418223217130238idddddd4、适者生存，优胜劣汰4.1、杂交算子杂交算子在遗传算法中起核心作用，它是指将个体进行两两配对，并以交叉概率Pc把配对的父代个体加以替换重组而生成新个体的操作。这里采用的是有序交叉法。步骤1.随机选取两个交叉点pointa和pointb；步骤2.两后代先分别按对应位置复制双亲x1和x2匹配段中的两个子串Al和B1；步骤3.在对应位置交换双亲匹配段以外的城市。如果交换后，后代x1_new中的某一城市a与子串A1中的城市重复，则将该城市取代子串B1与4Al中的城市a具有相同位置的新城市，直到与子串A1中的城市均不重复为止。对后代x2_new亦然，如下图所示（以10个城市为例）。核心代码：-----------------------------------------------------------------[s,t]=size(Pop);Pop1=Pop;……point=randperm(t-3)+1;point=point(1:2);pointa=min(point);pointb=max(point);-------------------------------------------------------------x1=Pop1(i,:);x2=Pop1(i+1,:);x1_new=zeros(size(x1));x2_new=zeros(size(x2));x1_new(pointa:pointb)=x1(pointa:pointb);x2_new(pointa:pointb)=x2(pointa:pointb);-------------------------------------------------------------forj=1:pointa-1x1_new(j)=x2(j);x2_new(j)=x1(j);fork=pointa:pointbifx1_new(j)==x1_new(k)x1_new(j)=x2(k);endifx2_new(j)==x2_new(k)x2_new(j)=x1(k);endendendforj=pointb+1:t-1fork=pointa:pointbifx1_new(j)==x1_new(k)x1_new(j)=x2(k);X1:98|45671|3210X2:87|141032|965x1_new:83|45671|9102x2_new:98|141032|7565endifx2_new(j)==x2_new(k)x2_new(j)=x1(k);endendend-----------------------------------------------------------------为表示遗传中的杂交过程，我定义了一个函数Cross.m来模拟这一过程。4.2、变异算子变异操作是以变异概率Pm对群体中个体串某些基因位上的基因值作变动，若变异后子代的适应度值更加优异，则保留子代染色体，否则，仍保留父代染色体。这里采用的方法是倒置变异法。仍以10个城市为例，假设当前个体x为(13748105962)。如果randPm，那么随机选择来自同一个体的两个点a和b，比如说3和7，倒置a和b之间的部分，产生下面的子体x_new为(13510847962)。核心代码：-------------------------------------------------------------fori=1:sp=rand;ifpPm;qujian=randperm(t-1);b=max(qujian(1:2));a=min(qujian(1:2));Pop1(i,a:b)=Pop1(i,b:-1:a);endend-----------------------------------------------------------------4.3、选择算子选择就是从群体中选择优胜个体、淘汰劣质个体的操作，它是建立在群体中个体适应度评估基础上。这里采用方法是最优保存方法。算法就是首先将群体中适应度最大的k个个体直接替换适应度最小的k个个体。核心代码：-----------------------------------------------------------------m11=Pop(:,t);num=1;whilenumk+1xuhao=find(m11==max(m11));mmax(num)=xuhao(1);m11(mmax(num))=0;num=num+1;endnum=1;m11=Pop(:,t);6whilenumk+1xuhao=find(m11==min(m11));mmin(num)=xuhao(1);m11(mmin(num))=max(m11)+1;num=num+1;end-----------------------------------------------------------------5、实验结果周游先生的行踪周游先生的行踪繁殖10代结果，总路程36702360繁殖50代结果，总路程27136820周游先生的行踪周游先生的行踪繁殖100代结果，总路程22436281繁殖500代结果，总路程17551441周游先生的行踪周游先生的行踪繁殖1000代结果，总路程16708951繁殖2000代结果，总路程17154371当经过1000代的迭代后，结果已经接近最优解，可以接受了。