TSP问题的遗传算法求解优化设计小论文

1、TSP 问题的遗传算法求解摘要：遗传算法是模拟生物进化过程的一种新的全局优化搜索算法，本文简 单介绍了遗传算法，并应用标准遗传算法对旅行包问题进行求解。关键词 ：遗传算法、旅行包问题一、旅行包问题描述：旅行商问题，即TSP问题(Traveling Saleman Problem)是数学领域的一 个著名问题，也称作货郎担问题，简单描述为：一个旅行商需要拜访n个城市(1, 2,，n),他必须选择所走的路径，每个城市只能拜访一次，最后回 到原来出发的城市，使得所走的路径最短。其最早的描述是1759年欧拉研究的骑士周游问题，对于国际象棋棋盘中的 64个方格，走访 64个方格一次且最 终返回起始点。用图

2、论解释为有一个图G= (V,E)，其中V是顶点集，E是边集，设D=(dj)是有顶点i和顶点j之间的距离所组成的距离矩阵，旅行商问题就是求出 一条通过所有顶点且每个顶点只能通过一次的具有最短距离的回路。若对于 城市V=v1，v2，v3，vn的一个访问顺序为T=(t1，t2，t3，ti， tn)，其中ti V(i=1，2，3，n)，且记tn+1= t1，则旅行商问题的数学模型 为：min L=2 d(i),t(i+1)(i=1，n)旅行商问题是一个典型组合优化的问题，是一个NP难问题，其可能的路径数为(n-1)!,随着城市数目的增加，路径数急剧增加，对与小规模的旅 行商问题，可以采取穷举法得到最优

3、路径，但对于大型旅行商问题，则很难 采用穷举法进行计算。在生活中 TSP 有着广泛的应用，在交通方面，如何规划合理高效的道路 交通，以减少拥堵；在物流方面，更好的规划物流，减少运营成本；在互联 网中，如何设置节点，更好的让信息流动。许多实际工程问题属于大规模 TSP， Korte于1988年提出的VLSI芯片加工问题可以对应于 1.2e6的城市TSP， Bland于1989年提出X-ray衍射问题对应于14000城市TSP，Litke于1984 年提出电路板设计中钻孔问题对应于17000城市TSP，以及Grotschel1991年提出的对应于442城市TSP的PCB442问题。二、遗传算法简介

4、遗传算法(Genetic Algorithm, GA)是借鉴生物界自然选择和自然遗传 机制“适者生存”的一种高度并行、随机化和自适应的全局优化算法，其首 先由 Holland 与 1975 年提出。其将问题的求解表示成“染色体”的适者生存 过程，通过“染色体“群的一代代不断进化，包括复制、交叉和变异等操作， 最终收敛到”最适应环境“的个体，从而得到问体的最优解。标准的遗传算法的只要步骤可描述为为：1、随机产生一组初始个体构成初始种群，并评价每一个体的适配值；2、判断算法的收敛准则是否满足。若满足则输出搜索结果，否则执行 下面步骤；3、根据适配值大小以一定的方式执行复制操作；4、按交叉概率 pc

5、 执行交叉操作；5、按变异概率 pm 执行变异操作。6、返回 2执行新一轮的复制、交叉、变异。在算法中，适配值是对染色体进行评价的一种指标，是遗传算法进行优 化所用的主要信息，与个体的目标值存在一种对应关系；复制操作通常采用 比例复制，即复制概率正比于个体适配值，适配值高的个体在下一代中复制 自身的概率大，从而提高种群的平均适配值；交叉操作通过交换两父代个体 的部分信息构成后代个体，使得后代继承父代的有效模式，从而有助于产生 优良个体；变异操作通过随机改变个体的某些基因而产生新个体，有助于增 加种群的多样性，避免早熟收敛。遗传算法利用生物进化和遗传的思想实现优化过程，区别与传统优化算 法1、算

6、法进行全空间并行搜索，并将搜索重点集中于性能高的部分， 从而能够提高效率并且不易陷入局部最小。2、算法具有固有并行性， 通过对种群的遗传处理可以处理大量的模 式，并且容易并行实现；其主要设计如下：1、确定问题的编码方案。2、确定适配值函数。3、遗传算子的设计。4、算法参数(种群数目、交叉与变异概率和进化代数等)的选取。5、确定函数终止条件。三、对TSP问题的遗传算法实现设计思路：1、初始化城市距离采用一个 city_xy 函数获取 n 个城市的 TSP 问题的坐标，保存在 city 矩 阵中，并且用 city_dis 矩阵表示任意两个城市之间的距离，矩阵中的元素 city_dis( i，j)

7、代表第 i 个城市与第 j 个城市间的距离。2、初始化种群通过 randperm 函数，生成一个一维随机向量(是整数 1，2，3，4，5 的 任意排列)，然后将其赋给二维数组 group 的第一列，作为一个个体。如此循 环 N 次，生成了第一代种群，种群的每个个体代表一条路径。3、计算适应度 采用的适应度函数为个体巡回路径的总长度的函数。具体为adapt(1,i)=(n*maxdis-dis) (1)在式(1)中，adapt(1,i)表示第i个个体的适应度函数，maxdis为城市间 的最大距离， dis 为个体巡回路径的总长度，这样定义的适应度，当路经越 短时适应度值越大。 在适应度值的基础上

8、， 给出的计算个体期望复制数的表 达式为adaptnum(1,i)=(N*adapt(1,i)/ sumadapt)(2)其中，sumadapt为种群适应度之和。4、复制采用优秀个体的大比例保护基础上的随机数复制法。 具体做法为在生成 下一代个体时，先将最大适应度对应的路径个体以较大的比例复制到下一 代，然后再用随机数复制法生成下一代的其他个体。 其中，有一个问题必须 考虑，即若某一次生成的随机数过大， 结果能复制一个或极少个样本。 为了 避免这一情况，采用了限制措施，即压低了随机数的上限。5、交叉采用的方法为按步长的单点交叉， 为随机选择一对样本， 再随机选择一 个交叉点位置， 按一定的步长

9、进行交叉点的选择。 选择一个步长而不是将其 设为 1，是因为若某一位置处的城市代码因为进行了交叉而发生了改变，则 其经过该处的两个距离都会改变。这种交叉兼有遗传和变异两方面的作用， 因为若交叉点处的城市编号都相同，则对两个个体而言交叉后样本无变化， 否则样本有变化。6、变异方法为随机两点I ,J的交互位置法。对于A= 1 2 3 4 5 6 7 8 9 10,若匸 3, J=8,则变异后B= 1 2 8 4 5 6 7 3 9 10虽然是简单的随机两点交互，但实际 上已经有40%的距离发生了改变。若用dij表示城市i与j之间的距离，则变 异后与变异前样本路径的距离差为 B23 十 B34 +

10、B78 十 B89 一 A23 十 A34 + A78 + A89 可见,随机两点交互足以产生新的模式样本。较大地提高变异率 就会产生大量的新样本,全局最优样本出现的概率随之提高。为了收敛到最 优解,借鉴模拟退火算法的思想,采取了变异率由很大逐渐衰减到较小的数 量,这样做也利于找到全局最优解。7、将复制，交叉，变异后得到的种群 group1重新赋给group然后重复3, 4, 5, 6 步操作。直至满足循环停止条件,即找到最优路径。仿真实验：TSP实验数据点取为：10城市TSP (自己随机选取10个点)：0，0；12，32；5，25;8,45;33,17;25,7;15,15;15,25;25

11、,15;41,1230 城市 TSP 问题(d=423.741 by D.B.Fogel):41,94;37,84;54,67;25,62;7,64;2,99;68,58;71,44;54,62;83,6 9;64,60;18,54;22,60;83,46;91,38;25,38;24,42;58,69;71,71; 74,78;87,76;18,40;13,40;82,7;62,32;58,35;45,21;41,26;44, 35;4,5050 城市 TSP 问题(d=427.855 by D.B.Fogel):31， 32；32， 39；40， 30；37， 69；27， 68；37，

12、52；38， 46；31， 62；30， 48；21， 47；25， 55；16， 57；17， 63；42， 41；17， 33；25， 32；5， 64；8, 52; 12, 42; 7, 38; 5,56, 37; 52, 41; 49, 49;21; 48, 28; 52, 33; 58,21, 10; 30, 15; 36, 16;25; 10, 17; 45, 35;58, 48; 57, 58; 39,27; 61, 33; 62, 63;62, 42; 63, 69; 52,42, 57; 32, 22; 27, 23;10; 46, 10; 59, 15; 51,20, 26

13、; 5, 6; 13, 13;64; 43, 67对与10点TSP问题，城市数比较少，每一代个体数目为 200,进化代数取为1000代，算法执行结果为：最优路径为：95106713428每一代的最小距离收敛图为:每一代种群最短距离的收敛过程175170离距短最群种代一每16516015515014501002003004005006007008009001000遗传代数最后得到的最优路径为:45闭合曲线即为最优路径40353025y20151050 =!0510152025303540x对于30城市TSP问题，每一代个体数目为200,将其遗传代数取为 算法执行结果为：4510000，最优路径为

14、：62 1 202110151839117814192425262728291617222330121345其每一代的最小距离的收敛图为:每一代种群最短距离的收敛过程11001000900离距短最群种代一每700600500X:1e+004Y: 425.34000 1000 2000trr700080009000100003000400050006000遗传代数得到的最优路径为:闭合曲线即为最优路径100LLL19080*70-604 -3-y 50L *r +*40*4+30-20-10-0rtrr r0102030405060708090100x对于50城市TSP问题，每一代的个体数目选取

15、为 200,遗传代数为20000, 则算法执行结果为：离距短最群种代一每最后得到的优化路径为:X: 2e+004丫： 474.1最优路径为:3516131479118513171812101920212242434426244504948403130292823363839472737153433324645252641每一代最小距离收敛图如下:闭合曲线即为最优路径7060厂11L1c-*缶-* *寺卡50r*JL*40J-y/ 士*4-.*30卡nJrsfcr20-卡7二二 g二-*/严10一-01rrrrr010203040506070x在30城市TSP问题中，得到的最终的优化距离为 42

16、5.3,与实际的最小 值423.471相差很少，在50城市TSP问题中，得到的最终优化解为 474.1, 与实际的最优路线的最小距离427.855相差较大。这是由于标准遗传算法的 缺点所确定的，标准遗传算法在前期搜索的效果比较良好，算法后期搜索比 较缓慢，从收敛图中可以验证这一点。在50城市TSP问题中，遗传代数范围内一个优化解的最小距离开始出现之后经过5000代才继续下降寻找更好的解。此外，遗传算法实现的效果很大程度上取决与问题的多种参数，如交 叉率，变异率，每一代的个体数目，如果这些参数设置不好，遗传算法将类 似随机搜索方法，出现“早熟收敛”。在50城市TSP中，如果增加每一代个 体数目、

17、遗传总代数、优化变异率和交叉率，会更靠近最优化解。鉴于标准遗传算法的缺点，现阶段出现了许多遗传算法的改进。在交叉 操作方面，有部分匹配交叉算子、增强边缘重组算子、序号交叉算子、均匀 排序交叉算子、循环交叉算子以及单点交叉算子等。在变异方面还有自适应 变异、多级变异等。此外，一些高级的基因操作如双倍体、显性遗传、倒位 操作、静态繁殖等被应用于遗传算法之中，以改进和优化遗传算法。参考文献:1、王凌，智能优化算法及其应用D，清华大学出版社2、曾宪钊，军事最优化新方法D，军事科学出版社3、蒋腾旭，智能优化算法概述J，人工智能及识别技术4、郑伟、孙文生，遗传算法及其在求解 TSP问题中的应用，中国科技论

18、文 在线5、符一平、陈光喜，一种求解TSP问题的改进遗传算法，桂林电子科技大 学学报6、http:/read.pud n. com/dow nloads76/sourcecode/math/288006/travelsale.doc7、& http:/we 附：MATLAB程序function yichaung_TSP2 clc,close all clear all n=50;city=city_xy(n); city_dis=zeros(n,n); for i=1:n%获取城市坐标信息for j=1:ncity_dis(i,j)=sqrt(city(i,1)-city(j,1).A2+(c

19、ity(i,2)-city(j,2).A2); endend maxdis=max(max(city_dis); N=200;-maxlun=20000;for i=1:Nttemp=randperm(n);for j=1:n group(j,i)=ttemp(j); end end%初始化城市距离%城市间最大距离%每一代种群中的个体数%迭代次数%初始化种群，即随机产生 N种路径，放在n行，N列的矩阵group中for lun=1:maxlun sumadapt=0; maxadapt(1,lun)=0; minadapt(1,lun)=100; viprate=0.1; copyrate=0

20、.02; maxadaptloc=0; mindisiii(1,lun)=100000;for i=1:Ndis(1,i)=0;for j=1:n-1%迭代循环maxlun次%适度值之和%最大适度值初值%最小适度值初值%最优个体复制率9复制率参数%最大适应值对应的个体号码初值%每一代的最忧路径对应的旅行距离总和初值dis(1,i)=dis(1,i)+city_dis(group(j,i),group(j+1,i); end dis(1,i)=dis(1,i)+city_dis(group(1,i),group(n,i); adapt(1,i)=n*maxdis-dis(1,i); sumada

21、pt=sumadapt+adapt(1,i);if dis(1,i)maxadapt(1,lun)maxadapt(1,lun)=adaptnum(1,i); maxadaptloc=i;endif adaptnum(1,i)minadapt(1,lun) minadapt(1,lun)=adaptnum(1,i);endend%. %复制操作tcopyN=0;%复制个数初值num=(maxadapt(1,lun)-copyrate-minadapt(1,lun)*rand(1)+minadapt(1,lun);%生成随机数 vipnum=viprate*N ;for tcopyN=1:vip

22、numfor i=1:ngroup1(i,tcopyN)=group(i,maxadaptloc);endendwhile tcopyNnum&tcopyNN tcopyN=tcopyN+1;for k=1:ngroup1(k,tcopyN)=group(k,i);endendendend%确定最优个体复制个数%先复制vipnum个最优个体至中间矩阵 groupl%再复制其余 N-vipnum 个%由于针对n个城市，故每个个体有n个元素%交叉操作pc=0.5-(0.5-0.4)*(lun-1)/(maxlun-1);pair=pc*N/2;step=2;pairno=0;while pairn

23、opaira=floor(N*rand(1)+1);b=floor(N*rand(1)+1);marri(1,a)=2;%交叉率%最多交叉对数%交叉步长取为 2%当前交叉过的个体数%随机产生两个交叉个体，floor 为向负无穷取整函数%参与交叉的个体标记初值marri(1,b)=3;if marri(1,a)=1&marri(1,b)=1&a=bmarri(1,a)=1;%参与交叉的个体标记为1%用随机数确定个体中单交叉点位置%以下按步长 step 进行交叉%用 for 确定交叉位置marri(1,b)=1;pairno=pairno+1; location=floor(n*rand(1)+1

24、); l1=0;l2=0;for i=location:step:ngroup1(i,a)=group1(j,b)for j=1:n if l1=j;endendfor j=1:nif group1(i,b)=group1(j,a)l2=j;endendtemp=group1(i,a); group1(i,a)=group1(l2,a);group1(l2,a)=temp;temp=group1(i,b); group1(i,b)=group1(l1,b);group1(l1,b)=temp;endendend% %变异操作pb=0.1; bnum=pb*N;for i=1:bnum%逐个取个

25、体，随机选择位置进行变异enda1=floor(n*rand(1)+1);a2=floor(n*rand(1)+1); b=floor(N*rand(1)+1);temp=group1(a1,b);group1(a1,b)=group1(a2,b);group1(a2,b)=temp;end% for i=1:Nfor j=1:ngroup(j,i)=group1(j,i);end变异后的矩阵， group, 准备下次循环endend disp( 最优路径为： );for i=1:nfprintf( %.d ,group(i,1); if rem(i,10)=0 fprintf( n ); end end figure(1); lun=1:1:maxlun;mindis=mindisiii(1,lun); plot(lun,mindis); ti