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

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

（i=1，…，n）旅行商问题是一个典型组合优化的问题，是一个NP难问题，其可能的路径数为（n-1）！，随着城市数目的增加，路径数急剧增加，对与小规模的旅行商问题，可以采取穷举法得到最优路径，但对于大型旅行商问题，则很难采用穷举法进行计算。在生活中TSP有着广泛的应用，在交通方面，如何规划合理高效的道路交通，以减少拥堵；在物流方面，更好的规划物流，减少运营成本；在互联网中，如何设置节点，更好的让信息流动。许多实际工程问题属于大规模TSP，Korte于1988年提出的VLSI芯片加工问题可以对应于1.2e6的城市TSP，Bland于1989年提出X-ray衍射问题对应于14000城市TSP，Litke于1984年提出电路板设计中钻孔问题对应于17000城市TSP，以及Grotschel1991年提出的对应于442城市TSP的PCB442问题。遗传算法简介遗传算法（GeneticAlgorithm，GA）是借鉴生物界自然选择和自然遗传机制“适者生存”的一种高度并行、随机化和自适应的全局优化算法，其首先由Holland与1975年提出。其将问题的求解表示成“染色体”的适者生存过程，通过“染色体“群的一代代不断进化，包括复制、交叉和变异等操作，最终收敛到”最适应环境“的个体，从而得到问体的最优解。标准的遗传算法的只要步骤可描述为为：随机产生一组初始个体构成初始种群，并评价每一个体的适配值；判断算法的收敛准则是否满足。若满足则输出搜索结果，否则执行下面步骤；根据适配值大小以一定的方式执行复制操作；按交叉概率pc执行交叉操作；按变异概率pm执行变异操作。返回2执行新一轮的复制、交叉、变异。在算法中，适配值是对染色体进行评价的一种指标，是遗传算法进行优化所用的主要信息，与个体的目标值存在一种对应关系；复制操作通常采用比例复制，即复制概率正比于个体适配值，适配值高的个体在下一代中复制自身的概率大，从而提高种群的平均适配值；交叉操作通过交换两父代个体的部分信息构成后代个体，使得后代继承父代的有效模式，从而有助于产生优良个体；变异操作通过随机改变个体的某些基因而产生新个体，有助于增加种群的多样性，避免早熟收敛。遗传算法利用生物进化和遗传的思想实现优化过程，区别与传统优化算法算法进行全空间并行搜索，并将搜索重点集中于性能高的部分，从而能够提高效率并且不易陷入局部最小。算法具有固有并行性，通过对种群的遗传处理可以处理大量的模式，并且容易并行实现；其主要设计如下：1、确定问题的编码方案。2、确定适配值函数。3、遗传算子的设计。4、算法参数（种群数目、交叉与变异概率和进化代数等）的选取。5、确定函数终止条件。对TSP问题的遗传算法实现设计思路：1、初始化城市距离采用一个city_xy函数获取n个城市的TSP问题的坐标，保存在city矩阵中，并且用city_dis矩阵表示任意两个城市之间的距离，矩阵中的元素city_dis（i，j)代表第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为个体巡回路径的总长度，这样定义的适应度，当路经越短时适应度值越大。在适应度值的基础上，给出的计算个体期望复制数的表达式为adaptnum(1,i)=(N*adapt(1,i)/sumadapt)(2)其中，sumadapt为种群适应度之和。4、复制采用优秀个体的大比例保护基础上的随机数复制法。具体做法为在生成下一代个体时，先将最大适应度对应的路径个体以较大的比例复制到下一代，然后再用随机数复制法生成下一代的其他个体。其中，有一个问题必须考虑，即若某一次生成的随机数过大，结果能复制一个或极少个样本。为了避免这一情况，采用了限制措施，即压低了随机数的上限。5、交叉采用的方法为按步长的单点交叉，为随机选择一对样本，再随机选择一个交叉点位置，按一定的步长进行交叉点的选择。选择一个步长而不是将其设为1，是因为若某一位置处的城市代码因为进行了交叉而发生了改变，则其经过该处的两个距离都会改变。这种交叉兼有遗传和变异两方面的作用，因为若交叉点处的城市编号都相同，则对两个个体而言交叉后样本无变化，否则样本有变化。6、变异方法为随机两点I，J的交互位置法。对于A=[12345678910]，若I=3,J=8，则变异后B=[12845673910]虽然是简单的随机两点交互，但实际上已经有40%的距离发生了改变。若用dij表示城市i与j之间的距离，则变异后与变异前样本路径的距离差为B23十B34+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,15;41,1230城市TSP问题（d=423.741byD.B.Fogel）：41,94;37,84;54,67;25,62;7,64;2,99;68,58;71,44;54,62;83,69;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.855byD.B.Fogel）：31，32；32，39；40，30；37，69；27，68；37，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，25；10，17；45，35；42，57；32，22；27，23；56，37；52，41；49，49；58，48；57，58；39，10；46，10；59，15；51，21；48，28；52，33；58，27；61，33；62，63；20，26；5，6；13，13；21，10；30，15；36，16；62，42；63，69；52，64；43，67对与10点TSP问题，城市数比较少，每一代个体数目为200，进化代数取为1000代，算法执行结果为：最优路径为：95106713428每一代的最小距离收敛图为：最后得到的最优路径为：对于30城市TSP问题，每一代个体数目为200，将其遗传代数取为10000，算法执行结果为：最优路径为：621202110151839117814192425262728291617222330121345其每一代的最小距离的收敛图为：得到的最优路径为：对于50城市TSP问题，每一代的个体数目选取为200，遗传代数为20000，则算法执行结果为：最优路径为：3516131479118513171812101920212242434426244504948403130292823363839472737153433324645252641每一代最小距离收敛图如下：最后得到的优化路径为：在30城市TSP问题中，得到的最终的优化距离为425.3，与实际的最小值423.471相差很少，在50城市TSP问题中，得到的最终优化解为474.1，与实际的最优路线的最小距离427.855相差较大。这是由于标准遗传算法的缺点所确定的，标准遗传算法在前期搜索的效果比较良好，算法后期搜索比较缓慢，从收敛图中可以验证这一点。在50城市TSP问题中，遗传代数范围内一个优化解的最小距离开始出现之后经过5000代才继续下降寻找更好的解。此外，遗传算法实现的效果很大程度上取决与问题的多种参数，如交叉率，变异率，每一代的个体数目，如果这些参数设置不好，遗传算法将类似随机搜索方法，出现“早熟收敛”。在50城市TSP中，如果增加每一代个体数目、遗传总代数、优化变异率和交叉率，会更靠近最优化解。鉴于标准遗传算法的缺点，现阶段出现了许多遗传算法的改进。在交叉操作方面，有部分匹配交叉算子、增强边缘重组算子、序号交叉算子、均匀排序交叉算子、循环交叉算子以及单点交叉算子等。在变异方面还有自适应变异、多级变异等。此外，一些高级的基因操作如双倍体、显性遗传、倒位操作、静态繁殖等被应用于遗传算法之中，以改进和优化遗传算法。参考文献：王凌，智能优化算法及其应用[D]，清华大学出版社曾宪钊，军事最优化新方法[D]，军事科学出版社蒋腾旭，智能优化算法概述[J]，人工智能及识别技术郑伟、孙文生，遗传算法及其在求解TSP问题中的应用，中国科技论文在线符一平、陈光喜，一种求解TSP问题的改进遗传算法，桂林电子科技大学学报/downloads76/sourcecode/math/288006/travelsale.doc/math/shumo/news.asp?id=212/view/46e9db2e453610661ed9f4c9.html附：MATLAB程序functionyichaung_TSP2clc,closeallclearalln=50;city=city_xy(n);%获取城市坐标信息city_dis=zeros(n,n);fori=1:nforj=1:ncity_dis(i,j)=sqrt((city(i,1)-city(j,1)).^2+(city(i,2)-city(j,2)).^2);endend%初始化城市距离maxdis=max(max(city_dis));%城市间最大距离N=200;%每一代种群中的个体数maxlun=20000;%迭代次数fori=1:Nttemp=randperm(n);%初始化种群，即随机产生N种路径，放在n行，N列的矩阵group中forj=1:ngroup(j,i)=ttemp(j);endendforlun=1:maxlun%迭代循环maxlun次sumadapt=0;%适度值之和maxadapt(1,lun)=0;%最大适度值初值minadapt(1,lun)=100;%最小适度值初值viprate=0.1;%最优个体复制率copyrate=0.02;%复制率参数maxadaptloc=0;%最大适应值对应的个体号码初值mindisiii(1,lun)=100000;%每一代的最忧路径对应的旅行距离总和初值fori=1:Ndis(1,i)=0;forj=1:n-1dis(1,i)=dis(1,i)+city_dis(group(j,i),group(j+1,i));enddis(1,i)=dis(1,i)+city_dis(group(1,i),group(n,i));%求一次旅行个体的总长度adapt(1,i)=n*maxdis-dis(1,i);%第i个个体的适应度函数sumadapt=sumadapt+adapt(1,i);%适应度函数总和ifdis(1,i)<mindisiii(1,lun)mindisiii(1,lun)=dis(1,i);endendfori=1:Nadaptnum(1,i)=(N*adapt(1,i)/sumadapt);%第i个个体的期望复制数ifadaptnum(1,i)>maxadapt(1,lun)maxadapt(1,lun)=adaptnum(1,i);%求本代最大适应值maxadaptloc=i;%求最大适应值对应的个体号码endifadaptnum(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;%确定最优个体复制个数fortcopyN=1:vipnum%先复制vipnum个最优个体至中间矩阵group1fori=1:ngroup1(i,tcopyN)=group(i,maxadaptloc);endendwhiletcopyN<N%再复制其余N-vipnum个fori=1:Nifadaptnum(1,i)>num&&tcopyN<NtcopyN=tcopyN+1;fork=1:n%由于针对n个城市，故每个个体有n个元素group1(k,tcopyN)=group(k,i);endendendend%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%交叉操作pc=0.5-(0.5-0.4)*(lun-1)/(maxlun-1);%交叉率pair=pc*N/2;%最多交叉对数step=2;%交叉步长取为2pairno=0;%当前交叉过的个体数whilepairno<paira=floor(N*rand(1)+1);%随机产生两个交叉个体，floor为向负无穷取整函数b=floor(N*rand(1)+1);marri(1,a)=2;%参与交叉的个体标记初值marri(1,b)=3;ifmarri(1,a)~=1&&marri(1,b)~=1&&a~=bmarri(1,a)~=1;marri(1,b)~=1;%参与交叉的个体标记为1pairno=pairno+1;location=floor(n*rand(1)+1);%用随机数确定个体中单交叉点位置l1=0;l2=0;fori=location:step:n%以下按步长step进行交叉forj=1:n%用for确定交叉位置ifgroup1(i,a)==group1(j,b)l1=j;endendforj=1:nifgroup1(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;%变异个体数fori=1:bnum%逐个取个体，随机选择位置进行变异a1=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%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%fori=1:Nforj=1:ngroup(j,i)=group1(j,i);%构造经过复制，交叉，变异后的矩阵，group,准备下次循环endendenddisp('最优路径为：');fori=1:nfprintf('%.d',group(i,1));ifrem(i,10)==0fprintf('\n');endendfigure(1);lun=1:1:maxlun;mindis=mindisiii(1,lun);plot(lun,mindis);title('每一代种群最短距离的收敛过程');xlabel('遗传代数');ylabel('每一代种群最短距离');x=zeros(1,n+1);y=zeros(1,n+1);fori=1:nk=group(i,1);x(1,i)=city(k,1);y(1,i)=city(k,2);endx(1,n+1)=x(1,1);y(1,n+1)=y(1,1);figure,plot(x,y,'-*g');title('闭合曲线即为最优路径');xlabel('x')ylabel('y');functionC=city_xy(n)ifn==10C=[0,0;12,32;5,25;8,45;33,17;25,7;15,15;15,25;25,15;41,12];elseifn==30C=[41,94;37,84;54,67;25,62;7,64;2,99;68,58;71,44;54,62;83,69;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,50];elseifn==50C=[31,32;32,39;40,30;37,69;27,68;37,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,25;10,17;...45,35;42,57;32,22;27,23;56,37;52,41;49,49;58,48;57,58;39,10;...46,10;59,15;51,21;48,28;52,33;58,27;61,33;62,63;20,26;5,6;13,13;...21,10;30,15;36,16;62,42;63,69;52,64;43,67];end基于单片机和DSP的卷绕控制器数据采集和通讯设计基于MSP430单片机的柴油发电机监控器的设计基于CPLD/FPGA和单片机的爆速仪设计基于单片机控制的晶闸管中频感应电源的研制基于十六位单片机的电力设备故障在线监测装置的设计与算法研究基于SPCE061A单片机的语音识别系统的研究基于PIC单片机的生物机能实验装置的研究基于MotorolaMC68HC08系列单片机演示系统的设计与实现基于TCP/IP协议的单片机与INTERNET互连的设计与实现基于嵌入式实时操作系统和TCP/IP协议的单片机测控系统AVR8位嵌入式单片机在车载全球定位系统显示终端中的应用基于AVR单片机的250WHID灯电子镇流器的研究基于单片机的TCP/IP技术研究及应用基于P87C591单片机的CAN总线应用层协议的研究基于单片机实现对二级倒立摆的控制C8051FXXX系列单片机仿真器的研制基于80C196MC单片机控制的变频调速及配料控制系统的应用研究基于单片机的胶印机控制系统开发研究基于凌阳单片机的二次压降全自动测量仪的研制基于单片机的超声测距系统基于MOTOROLA单片机的专用电池组智能充电仪全站仪动态测量的研究以及其与单片机在轨道式龙门吊实时检测中的应用一种基于80C196KC单片机的新型电子负载的设计基于单片机的对讲系统的研究开发基于单片机的微波加热沥青路面再生修复机温度控制器的开发与研究基于单片机ATmega128的嵌入式工业控制器设计基于单片机的压电闭环微位移控制系统的研究基于单片机的高压静电除尘整流设备的自动监控系统设计采用W78E58单片机的酸碱浓度检测技术基于单片机的粮库温度监控系统设计基于单片机控制的微型轴流式血泵外磁驱动系统研究基于AVR单片机的电动自行车控制系统研究基于PIC单片机的配电网综