遗传算法求解TSP问题MATLAB实现

1、遗传算法求解TSP问题MATLA或现摘要：旅行商问题(TSP)是一个经典的优化组合问题，本文采用遗传算法来求解TSP问题，深入讨论了遗传算法解决TSP问题的求解过程，并通过MATLAB寸算法进行了实现，最后对实验结果进行分析， 并与粒 子群算法进行对比和分析。关键字：TSR遗传算法；粒子群算法0.引言旅行商问题是一个经典的优化组合问题，它可以扩展到很多问题，如电路布线、输油管路铺设等，但是，由于TSP问题的可行解数目与城市数目N是成指数型增长的，是一个NP难问题，因而一般只能近似求解，遗传算法( GA)是求解该问题的较有效的方法之一，当 然还有如粒子群算法，蚁群算法，神经网络算法等优化算法也可

2、以进行求解。遗传算法是美国学者Holland根据自然界“物竞天择，适者生存”现象而提出的一种随机搜索算法，本文 采用MATLAB来实现遗传算法解决 TSP问题。1 .旅行商问题旅行商问题可以具体描述为：已知n个城市之间的相互距离，现有一个推销员从某一个 城市出发，必须遍访这n个城市，并且每个城市只能访问一次，最后又必须返回到出发城市，如何安排他对这些城市的访问次序，可使其旅行路线的总长度最短。用图论术语来表示， 就是有一个图g=(v,e),其中v是定点5, e是边集，设d=(dij)是有顶点i和顶点j之间的距离所 组成的距离矩阵，旅行商问题就是求出一条通过所有顶点且每个顶点只通过一次的最短距离

3、 的回路。若对与城市v=v1,v2,v3vn的一个访问顺序为 t=(t1,t2,t3,tn),其中ti C v(i=1,2,.n), 且记tn+1=t1,则旅行上问题的数学模型为式1 :min I = Ed(t,t(i +1) (i =1,.,n)(1)2 .遗传算法与粒子群算法2.1 遗传算法遗传算法的基本原理是通过作用于染色体上的基因寻找好的染色体来求解问题，它需要对算法所产生的每个染色体进行评价，并基于适应度值来选择染色体，使适应性好的染色体有更多的繁殖机会，在遗传算法中，通过随机方式产生若干个所求解问题的数字编码，即染色体，形成初始种群；通过适应度函数给每个个体一个数值评价，淘汰低适应

4、度的个体，选择高适应度的个体参加遗传操作，经过遗产操作后的个体集合形成下一代新的种群，对这个新的种群进行下一轮的进化。2.2 遗传算法的过程遗传算法的基本过程是：1 .初始化群体。2 .计算群体上每个个体的适应度值3 .由个体适应度值所决定的某个规则选择将进入下一代个体。4 .按概率Pc进行交叉操作。5 .按概率Pm进行变异操作。6 .没有满足某种停止条件，则转第2步，否则进入第7步。7 .输出种群中适应度值最优的染色体作为问题的满意解或最优界。停止条件有两种：一是完成了预先给定的进化代数则停止；二是种群中的最优个体在连续若干代没有改进或平均适应度在连续若干代基本没有改进时停止。遗传算法过程图

5、如图1:3结束图1:遗传算法过程框图3.遗传算法MATLAB代码实现遗传算法中控制参数如下：Clist城市的坐标，dislist城市距离矩阵，inn初始种群的大小，gnmax最大代数，pc交叉概率，pm变异概率。3.1 开始准备先读入文件，读入 574个城市坐标读入矩阵，并计算城市距离。如代码：Clist =工”。军(57明幻；a, x, y=t ext read (7 iq574. tspn .,将nSfKF');Clit (:, l)=x;3 2)=y;figure (1) axis<0 10 C 10) grid onscatter (Clist Clist (ij 2)&

6、gt; 7)Igrid onCit jrNum=size (Clisl, 1);for i=l:nCity蚯十算城市间距离，假设距离为欧几里德范数for 1:nCityj) ( (xyCity(i, D-yCitytj, 1) *21-(aryCity(i, 2)-xyCity(jJ 2) )T2) *0. E ; end end遗传算法对求解问题本身是一无所知的，这里采用随机生成初始化种群，如下： for i=l：inns (ij :) =raridperni(CityNujn);end计算适应度值，适应度值是根据适应度函数来计算的，如适应度函数代码如下：furict ion f,p=obj

7、f(5j dislist).;inn=size(sj 1), 将读取种群大小for i=1;irmf (i)=CalDist (dislist j s (i, : ?) ; %计算函数值,即适应度endfiono./f* h用计算选择概率fsum=0 ；for i=1:innf sum=f suiv+f (i) * 15 ;endfor i=1iinnps ti)=f(i)15/fsun,end%计算累积概率P (l)=ps(l), for i=2:innp(i)=p(i-l)+ps(i);endP=PT ；end3.3选择操作选择的目的是为了从当前群体中选出优良的个体，使它们有机会作为父代产

8、生后代个 体，如代码：function seln=sel(s,p):inn=size(pj1)；瑞从种群中选择两个个体for i=l:2r=r皿d; *产生一个随机数prand=p-r;产1 ；while prandtjXOj=i+l ；endseln(i>j;需选中个体的序号endend许多生物的繁衍是通过染色体的交叉完成的，在遗传算法中使用这一概念，并把交叉作为遗传算法的一个操作算子，其实现过程是对选中用于繁殖下一代的个体，随机地选择两个个体的相同位置，按交叉概率 Pc,在选择的位置实行交换，目的在于产生新的基因组合， 即新的个体(这里由于源代码太多不列出)3.5变异操作是按一定概率

9、随机改变某个个体的基因值，以变异概率Pm对某个个体的某些位执行变异，在变异时，对执行变异的串的对应位求反，如代码：funct i on叫X (snew, pm);2),snnew=anew;pnjh=pt q (pit)；if pnm=1cl= round (rand* (bn-2) +1;c2= round (rand* (bn-2) + l;chbl=inin(clJ c2);chb2uK (clj c2);x=sriew(chbl+l: chb25 ;snnewtchb 1+1: chb2)=f liplr (x);end end最后根据具体条件判断是否返回或是继续，最后当满足条件是输出

10、适应度最优群体。4实验分析实验硬件环境为普通笔记本电脑，内存 2GB CPU率2.0GHz。软件环境为 Windows XP Professional SP3 操作系统，Matlab7.1 。实验对象是574个城市的旅行商问题。读入574个城市的坐标，如图 1:Ewni'图1 : 574个城市坐标的两种显示4.1 .改变种群数量的对比当参数设置为种群大小为100,最大迭代次数2000,交叉概率0.85,变异概率为0.05的时候对574个城市求解，如图 2。当参数设置为种群大小为50,最大迭代次数 2000,交叉概率0.85,变异概率为 0.05的时候对574个城市求解，如图 3。当参数

11、设置为种群 50,最大迭代次数为 5000,交叉概率0.85,变异概率为0.05的时候对574个城市求解，如图 4.接素过程图2:种群为100最大迭代次数为2000的TSP问题求解结果图3:种群为50最大迭代次数为2000的TSP问题求解结果图4:种群为50最大迭代次数为5000的TSP问题求解结果通过上述种群大小可知迭代越大求解的结果越优化，但是确花费了大量时间，种群越大求解的结果更优化， 所以在时间和求解优化解要权衡，而且改变交叉概率和变异概率也同样影响着收敛速度和优化解的得到。另外从图可以看出， 算法迭代并没有稳定， 那是因为迭代的次数不够，造成解的搜索没有稳定和优化，迭代次数一般可以上

12、万次4.2 粒子群算法求解当参数为50个粒子迭代10次,局部优化使用 2-Opt算法，如图4。拉子群算法PS5图5: 50个粒子10次迭代的粒子群TSP问题求解结果当参数为50个粒子迭代30次，局部优化使用 2-Opt算法，如图5。粒子群算法华号图6: 50个粒子30次迭代的粒子群TSP问题求解结果当参数为30个粒子迭代30次，局部优化使用 2-Opt算法，如图6。位于群算法(PSD)图7: 30个粒子30次迭代的粒子群TSP问题求解结果根据实验结果50粒子10迭代时最短路径为 42176, 50个粒子30次迭代是最短路径为41619, 30个粒子30次迭代时最短路径为 40809, 30个粒

13、子30次迭代时解最优，可以看出 最优解的得出并不是只受迭代次数或是粒子数影响，在其它条件不变的情况下，两种都对解的求解有影响，如果考虑其它因素的话，求解更加复杂。4.3 遗传算法同粒子群算法对比取两个实验的最优解结果，即50粒子群30次迭代的粒子群算法同种群大小为1200的遗传算法的对比，如图 8,图9. 位子群算法（PS。）图8: 30个粒子30次迭代的粒子群TSP问题求解结果2400160014UU1200ax600图9:种群大小为100迭代2000次的TSP问题求解结果采用两种算法对同一 TSP问题进行求解，从实验明显可见粒子群算法比遗传算法得到 的解更加优化，而且所花费的时间也比遗传算

14、法少得多。造成这种实验结果的原因可能是算法本身的适应问题，可能是粒子群算法更适合解此类问题；另一方面，可能是遗传算法的参数设置不能达到最优解，因为遗传算法的种群大小，最大迭代次数，交叉概率和变异概率的设定对算法的收敛和最优解的得到有很大影响，可能是我们设定的这些参数不够准确，如在遗传算法中我们只设置了2000次的最大迭代次数，明显不能满足要求， 要得到更好的优化解， 就必须设置好算法的参数，目前有许多研究都在改进算法，以达到满意的效果。5总结本文采用MATLAB 实现遗传算法求解TSP 问题， 并根据实验结果进行了分析，遗传算法是一种智能优化算法，它的实现有些关键点，一是串的编码方式，本质就是问