数学建模之求解TSP问题的遗传算法

求解TSP问题的遗传算法实现邱文（湖北工业大学机械学院，湖北，武汉，120131055）摘要：本文应用遗传算法（GA）解决TSP（travelsalesmanproblem）问题，在此采用基于对各个城市访问顺序的编码方案，同时在探讨影响GA性能的遗传算子的基础上，介绍了可以改善解的质量的倒位算子。最后通过在VC++6.0上运行该算法的程序得到问题的最优解。关键词：遗传算法（GA）TSP问题倒位算子最优解GeneticAlgorithmforSolvingTSPProblemsQiuWen(SchoolofScience,HubeiUniversityofTechnology,Hubei,Wuhan,120131055）Abstract:ThispaperapplygeneticalgorithmtosolveTSP(travelsalesmanproblems)problem.Theencodingschemebasedonsequenceofeachcity.Duringthesametime,onthestudyingoftheperformanceofgeneticalgorithmwhichbasedonthegeneticoperators,weintroduceaninversionoperatortoimprovethequalityofsolution.Keywords:geneticalgorithm(GA);TSPproblem;inversionoptimalsolution1引言TSP问题（TravelingSalesmanProblems可描述为：已知n个城市之间的相互距离，现有一推销员必须遍历这n个城市，并且每个城市只能访问一次，最后又必须返回出发城市。如何安排他对这些城市的访问次序，可使其旅行路线的总长度最短。用图论的术语来说，假设有一个图G=（V,E）,其中V是顶点集，E是边集，设D=（dij）是由顶点i和顶点j之间的距离所组成的距离矩阵，旅行商问题就是求出一条通过所有顶点且每个顶点只能通过一次的具有最短距离的回路。若对于城市V={v1,V2,V3,…,vn}的一个访问顺序为T=（t1,t2,t3,…,ti,,…,tn），且记tn+1=t1，则TSP问题的数学模型为：MinL=∑ni=1dti,ti+1TSP问题是一个典型的组合优化问题，并且是一个NP难题，其可能的路径数与城市数目n是成指数型增长的，所以一般很难精确的求出自由解因而寻找出其他有效的近似求解算法就具有重要的理论意义，另一方面，很多实际应用问题，比如印制电路板的钻孔路线方案、连锁店的货物配送路线等，经过简化处理后，均可以建模为TSP问题，因而对TSP问题的求解具有重要的应用价值，同时研究TSP问题对促进遗传算法也有重大意义。遗传算法（GA）是模拟生物在自然环境中的遗传和进化过程而形成的一种自适应全局优化概率搜索算法。它包括对表示可行解的个体编码，再对这些编码进行选择、交叉和变异等遗传操作。与传统的优化算法相比，遗传算法的优越性主要表现在：（1）它在搜索过程中不易陷入局部最优，即使在所定义的适应函数是不连续的、非规则的或有噪声的情况下，它也能以最大的概率找到群体最优解；（2）由于它固有的并行性，遗传算法非常适合大规模并行计算机。2初始群体设定由于遗传操作是对众多个体同时进行的，这众多的个体组成了群体，在遗传算法中考虑到初始群体的多样性，群体中的个体是随机产生的，先随机生成一定数目的个体，然后从中挑出最好的个体加到初始群体中。这种过程不断迭代，直到初始群体中个体数达到了预先确定的规模。/*群体初始化*/voidinitpop(){unsignedcharj1;unsignedintj,k,j2,j3,j4,p5[maxstring];j=0;for(k=0;klchrom;k++)oldpop[j].chrom[k]=k;for(k=0;klchrom;k++)p5[k]=oldpop[j].chrom[k];srand((unsigned)time(NULL));for(j=0;jpopsize;j++){j2=rand()%(lchrom);for(k=0;kj2+20;k++){j3=rand()%(lchrom);j4=rand()%(lchrom);j1=p5[j3];p5[j3]=p5[j4];p5[j4]=j1;}for(k=0;klchrom;k++)oldpop[j].chrom[k]=p5[k];}for(k=0;klchrom;k++)for(j=0;jlchrom;j++)dd[k*lchrom+j]=_hypot(x[k]-x[j],y[k]-y[j]);for(j=0;jpopsize;j++){oldpop[j].x=(double)decode(oldpop[j].chrom);oldpop[j].fitness=objfunc(oldpop[j].x);oldpop[j].parent1=0;oldpop[j].parent2=0;oldpop[j].xsite=0;}}3目标函数和适应度函数的设计遗传算法的一个特点是它仅适用所求问题的目标函数值就可以得到下一步的有关搜索信息，对目标函数值的使用是通过评价个体的适应度来体现的。评价个体适应度的一般过程是：（1）对个体编码串进行解码处理后，可得到个体的表现型。（2）由个体的表现型可计算出对应个体的目标函数值。（3）由目标函数值按一定的转换规则求出个体的适应度。在TSP的求解中，将求取距离总和L的最小值MinL作为目标函数，适应度函数常取路径长度L的倒数，即f=1/L。/*个体适应度计算*/doubleobjfunc(doublex1){doubley;y=100.0*ff/x1;returny;}/*群体适应度统计*/voidstatistics(pp*pop){unsignedintj;sumfitness=pop[0].fitness;min=pop[0].fitness;max=pop[0].fitness;maxpp=0;minpp=0;for(j=1;jpopsize;j++){sumfitness=sumfitness+pop[j].fitness;if(pop[j].fitnessmax){max=pop[j].fitness;maxpp=j;}if(pop[j].fitnessmin){min=pop[j].fitness;minpp=j;}}avg=sumfitness/(double)popsize;}4遗传算法4.1编码设计在遗传算法的运行过程中，它不对所求解的问题的实际决策直接进行操作，而是对表示可行解的个体编码施加遗传运算，通过这种遗传操作来达到优化的目的，在遗传算法中把一个问题的解空间转换到遗传算法所能处理的搜索空间的转换方法就叫做编码。在TSP问题的求解方法中，本文描述旅行路线的方法为巡回旅行路线所经过的各个城市的顺序排列。它是采用所遍历的城市的排序来表示各个个体的编码串，由于一般的个体编码方法进行的交叉运算、变异运算会使群体中产生一些不满足问题约束条件或无实际意义的巡回路线。因此本文采用Grefenstetee等提出的一种新的巡回路线编码方法，该方法能够使得任意的基因型个体都能够对应于一条具有实际意义的巡回路线。即对于TSP问题的N个城市列表W，对各个城市的一个访问顺序为T：T=（t1,t2,t3,…,tn）,规定每访问完一个城市，就从城市列表W中将其去掉，则用第i（i=1,2,3,…n）个所访问的城市ti在所有未访问的城市列表W={t1,t2,t3,…,ti-1}中的对应位置序号gi（igi=N-i+1）就可具体访问哪个城市，如此这样直接处理完W中的所有城市。如对十个城市作如下排列：W=（ABCDEFGHIJ）现有如下所述的两条巡回路线：TX=（ADBHFIJGEC）TY=（BCADEJHIFG）按照Grefenstetee所提出的编码方法，这两条巡回路线可编码为：GX=（1315344321）GY=（2211153311）4.2遗传算子标准遗传算法的操作算子一般都包括选择（selection），交叉(crossover)，变异(mutation)三种基本形式。它们构成了遗传算法具备强大搜索能力的核心，是模拟自然选择以及遗传过程中发生的繁殖，杂交和突变现象的主要载体。遗传算法利用遗传算子产生新一代群体来实现群体进化，算子的设计是遗传策略的主要组成部分，也是调整和控制进化过程的基本工具。4.2.1选择算子选择操作是建立在对个体适应度进行评价的基础之上，是从群体中选择优胜个体即适应度较高的个体，淘汰劣质个体的操作，其操作的主要目的是为了避免基因缺失，提高全局收敛性和计算效率。TSP问题采用的是基本遗传操作中的比例选择方法，其代码实现如下：/*选择*/intselect(){doublerand1,partsum;unsignedintj;partsum=0.0;j=0;srand((unsigned)time(NULL));rand1=rand()/32767.0*sumfitness;do{partsum=partsum+oldpop[j].fitness;j=j+1;}while((partsumrand1)&&(jT));returnj-1;}4.2.2交叉算子交叉算子在遗传算法中起着核心作用，它是指将个体进行两两配对，并以交叉概率Pc把配对的父代个体加以替换重组而生成新个体的操作。杂交操作一般分为以下几个步骤：（1）从交配池中随机选取出要配对的一对个体；（2）根据位串长度L，对要配对的一对个体，随机选取[1，L-1]中一个或者对个的整数k作为交叉位置；（3）根据交叉概率Pc（0Pc1）实施交叉操作，配对个体在交叉位置，相互交换各自的部分内容，从而形成新的一对个体。本文采用的交叉方法是常规单点交叉法，即随机选取两条巡回路线上随机设定一个交叉点i（i=1,2,3,…,n），互换两条巡回路线上基因座i上的基因。从而得到两条新巡回路线。配对个体：Gx=(131534|4321)（131534|3321）新个体Gx1Gy=(221115|3311)（221115|4311）新个体Gy1交叉点4.2.3变异算子变异操作是以变异概率Pm对群体中个体串某些基因位上的基因值做变动，若变异后子代的适应度值更加优异，则保留子代染色体，否则，仍保留父代染色体。这里采用的方法是倒位变异法。倒位操作（InverseOperation）是指颠倒个体编码串中随机指定的二个基因座之间的基因排列顺序，从而形成一个新的染色体，即产生一条新的巡回路线。假设当前个体X的编码串为（1315344321）。如果产生的随机数rand()Pm,那么随机选择来自同一个体的两点，比如说3和7，倒置3和7之间的部份，产生下面的子代X1为（131435321）。4.3关键参数确定在遗传算法的运行过程中，存在着对其性能产生极大影响的一组参数。这组参数在初始阶段或群体进化过程中需要合理的选择和控制，以使遗传算法以最佳的搜索轨迹达到最优解。主要参数包括：个体编码串长度L、群体规模M、交叉概率Pc、变异概率Pm、进化代数T等。这些参数对遗传算法的运行性能影响很大，需要谨慎选取。（1）编码串长度L：编码串长度的选取与求取精度有关，本文采用符号编码来表示个体，编码串长度为50。（2）群体大小M：群体大小M表示群体中所含个体数量，当M取值较小时，可提高遗传算法的运算速度，但是却会降低群体的多样性，可能引起早熟现象，而当M取值较大时，又会使得遗传算法的运行效率较低，所以本文群体规模取值100。（3）交叉概率：交叉概率一般取大值，但是取值太大，会破坏群体中的优良模式，取值太小，产生新个体的速度较慢，本文采用的取值为0.8。（4）变异概率若取值较大，可能破坏掉很多较好的模式，是的遗传算法接近于随机算法，若取值太小，操作产生新个体的能力就会变差