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

1、遗传算法求解TSP问题MATLAB现摘要：旅行商问题(TSP)是一个经典的优化组合问题，本文采用遗传算法来求解TSP问题，深入讨论了遗传算法解决TSP问题的求解过程，并通过MATLA8寸算法进行了实现，最后对实验结果进行分析， 并与粒 子群算法进行对比和分析。关键字：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,v3 -vn的一个访问顺序为 t=(t1,t2,t3 - ,tn)，其中 ti C v(i=1,2,.n), 且记tn+1=t1,则旅行上问题的数学模型为式1 :min I =8d(t(i),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 = zeros (574 2):a, y=t ext read (7 iq574. tspn .'强i演fKf');(:, l)=x;2)=y; figure (1)10 C 10) grid on scatter (Clist Clift j 2)> f

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

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

8、:inn=size(pj1)；济从种群中选择两个个体for 1=1:2rand; %产生一个随机数prand=p-r;户1；while prandtjXOj=j+l；end哭比(i)uj；贤选中个体的序号endend3.4交叉操作许多生物的繁衍是通过染色体的交叉完成的，在遗传算法中使用这一概念，并把交叉作为遗传算法的一个操作算子，其实现过程是对选中用于繁殖下一代的个体，随机地选择两个个体的相同位置，按交叉概率Pc,在选择的位置实行交换，目的在于产生新的基因组合，即新的个体(这里由于源代码太多不列出)3.5变异操作是按一定概率随机改变某个个体的基因值，以变异概率Pm对某个个体的某些位执行变异，在

9、变异时，对执行变异的串的对应位求反，如代码：funct i on(snew, pm);snnew=anew;a (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);endend最后根据具体条件判断是否返回或是继续，最后当满足条件是输出适应度最优群体。4实验分析实验硬件环境为普通笔记本电脑，内存 2GB CP堀率2.0GHz。软件环境

10、为 Windows XP Professional SP3 操作系统，Matlab7.1。实验对象是574个城市的旅行商问题。读入574个城市的坐标，如图 1:图1 : 574个城市坐标的两种显示4.1.改变种群数量的对比当参数设置为种群大小为100,最大迭代次数2000,交叉概率0.85,变异概率为0.05的时候对574个城市求解，如图2。当参数设置为种群大小为50,最大迭代次数 2000,交叉概率0.85,变异概率为 0.05的时候对574个城市求解，如图3。当参数设置为种群 50,最大迭代次数为 5000,交叉概率0.85,变异概率为0.05的时候对574个城市求解，如图 4.图2:种群

11、为100最大迭代次数为2000的TSP问题求解结果图3:种群为50最大迭代次数为2000的TSP问题求解结果图4:种群为50最大迭代次数为5000的TSP问题求解结果通过上述种群大小可知迭代越大求解的结果越优化，但是确花费了大量时间，种群越大求解的结果更优化， 所以在时间和求解优化解要权衡，而且改变交叉概率和变异概率也同样影响着收敛速度和优化解的得到。另外从图可以看出， 算法迭代并没有稳定， 那是因为迭代的次数不够，造成解的搜索没有稳定和优化，迭代次数一般可以上万次4.2粒子群算法求解当参数为50个粒子迭代10次，局部优化使用 2-Opt算法，如图4。位子群算法（PS。】图5: 50个粒子10

12、次迭代的粒子群TSP问题求解结果当参数为50个粒子迭代30次，局部优化使用 2-Opt算法，如图5。杭子群算法零。）图6: 50个粒子30次迭代的粒子群TSP问题求解结果当参数为30个粒子迭代30次，局部优化使用 2-Opt算法，如图6。成于群算注诉$。）图7: 30个粒子30次迭代的粒子群TSP问题求解结果根据实验结果50粒子10迭代时最短路径为 42176, 50个粒子30次迭代是最短路径为41619, 30个粒子30次迭代时最短路径为 40809, 30个粒子30次迭代时解最优，可以看出 最优解的得出并不是只受迭代次数或是粒子数影响，在其它条件不变的情况下，两种都对解的求解有影响，如果考

13、虑其它因素的话，求解更加复杂。4.3遗传算法同粒子群算法对比取两个实验的最优解结果，即50粒子群30次迭代的粒子群算法同种群大小为1200的遗传算法的对比，如图 8,图9. 应子群算注PS。）图8: 30个粒子30次迭代的粒子群TSP问题求解结果图9:种群大小为100迭代2000次的TSP问题求解结果采用两种算法对同一 TSP问题进行求解，从实验明显可见粒子群算法比遗传算法得到 的解更加优化，而且所花费的时间也比遗传算法少得多。造成这种实验结果的原因可能是算法本身的适应问题，可能是粒子群算法更适合解此 类问题；另一方面，可能是遗传算法的参数设置不能达到最优解，因为遗传算法的种群大小，最大迭代次数，交叉概率和变异概率的设定对算法的收敛和最优解的得到有很大影响，可能是我们设定的这些参数不够准确，如在遗传算法中我们只设置了2000次的最大迭代次数，明显不能满足要求， 要得到更好的优化解， 就必须设置好算法的参数，目前有许多研究都在改进算法，以达到满意的效果。5总结本文采用MATLAB实现遗传算法求解 TSP问题，并根据实验结果进行了分析， 遗传算 法是一种智能优化算法，它的实现有些关键点，一是串的编码方式，本质就是问题编码，串长