《基于遗传算法的TSP路径规划算法设计(15页).doc》由会员分享，可在线阅读，更多相关《基于遗传算法的TSP路径规划算法设计(15页).doc（15页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、-基于遗传算法的TSP路径规划算法设计-第 15 页基于遗传算法的TSP路径规划算法设计摘要TSP问题是一个经典的NP难度的组合优化问题,遗传算法是求解TSP问题的有效方法之一。针对这一问题,首先给出了基于遗传算法求解TSP问题的一般性流程，设计了基于遗传算法的求解算法,包括编码设计、适应度函数选择、终止条件设定、选择算子设定、交叉算子设定以及变异算子设定等,然后设计并实现了基于遗传算法的TSP问题求解系统, 并编制了完整的Matlab程序予以仿真实现。1. 引言旅行商问题(Traveling Saleman Problem,TSP) , 又叫货郎担问题, 是最基本的路线问题, 该问题是在寻求
2、单一旅行者由起点出发, 通过所有给定的城市之后, 最后再回到原点的最小路径成本。该问题具有广泛的应用性, 如物流中的配送车辆调度问题就可看成一个约束性多路旅行商问题. 因此, 对TSP问题求解具有一定的现实意义。TSP问题属于组合优化问题, 随着问题规模增大, 其可行解空间也急剧扩大, 有时在当前的计算机上用枚举法很难甚至不能求出最优解, 而用启发式算法求解这类问题的满意解是一个很好的方式, 遗传算法就是寻求这种满意解的最佳工具之一。遗传算法模拟自然进化过程来搜索最优解1 , 其本质是一种高效、并行、全局搜索的方法。本文采用遗传算法求解TSP问题并编制Matlab程序进行仿真试验。2. TSP
3、问题的数学模型TSP 问题即寻找一条最短的遍历n个城市的最短路径, 使得:取最小值, di,i+1表示两城市i和i + 1之间的距离。3. 遗传算法的运行过程遗传算法是一种 生成+ 检测 的迭代搜索算法。其运算流程可用图1来表示。图1 遗传算法的程序4. TSP问题的遗传算法实现4.1 编码并生成初始种群编码是应用遗传算法时要解决的首要问题, 也是设计遗传算法时的一个关键环节。求解TSP问题时, 采用所遍历城市的顺序排列来表示各个个体的编码是最自然的编码方法2 , 而且这种表示方法无需解码过程, 占用的内存空间较小。4.2 适应度评估适应度用来度量群体中各个体在优化过程中达到或接近于或有助于找
4、到最优解的优良程度。适应度较高的个体被选中遗传到下一代的概率较大；而适应度较低的个体被选中遗传到下一代的概率相对较小一些。本文用个体所表示的循环路线的倒数来作为适应度评估值, 路线越短,个体适应度值越大。4.3 选择、交叉、变异选择操作。是从群体中选择生命力强的个体产生新种群的过程. 选择操作以个体的适应度评估为基础。其主要目的是避免有用遗传信息的丢失。从而提高算法的全局收敛性和计算效率。常用的选择算子有赌轮选择、联赛选择、最佳保留等。其中，最佳个体保存策略可保证迄今为止所得到的最优个体不会被交叉、变异等遗传操作所破坏。它是遗传算法收敛性的一个重要保证条件。但它也容易使得某个局部最优个体不易被
5、淘汰反而快速扩散。从而使得算法的全局搜索能力不强。因此，最佳个体保存一般要与其他选择方法配合使用方可取得良好的效果 3 。交叉运算产生子代, 子代继承父代的基本特征。交叉算子一般包括两个内容: 一是对种群中的个体随机配对并按预先设定的交叉概率来确定需要进行交叉操作的个体对; 二是设定个体的交叉点, 并对的部分结构进行相互交换。交叉算子的设计与编码方式有关。在TSP问题中几种有代表性的交叉算子如顺序交叉、类OX交叉等, 这些交叉算子在产生新个体的过程中没有目的性, 对于自然数编码的TSP问题, 这些交叉可能破坏亲代的较优基因, 从而使交叉算子的搜索能力大大降低。变异操作是对个体的某些基因值做变动
6、。变异操作的目的有两个, 一是使遗传算法具有局部的随机搜索能力, 当经过交叉操作群体已接近最优解领域时, 利用变异算子可以加速向最优解收敛; 二是使遗传算法可维持群体的多样性, 以防止早熟现象。变异算子的设计也与编码方法有关, 对于自然数编码的TSP问题, 可采用逆转变异、对换变异和插入变异等。逆转变异, 也称倒位变异, 是指在个体编码中,随机选择两点( 两点间称为逆转区域) , 再将这两点内的字串按反序插入到原位置中. 倒位变异考虑了原有边的邻接关系, 能将巡回路线上的优良基因性能较好地遗传到下一代, 提高寻优速度。5. 仿真结果ans = 1.0e+003 * Columns 1 thro
7、ugh 10 0 2.5389 2.8738 2.5753 2.3181 2.1587 2.2166 3.1740 3.3711 3.5402 2.5389 0 1.0735 0.1113 0.2668 0.3950 0.4101 0.6379 0.8536 1.0550 2.8738 1.0735 0 0.9645 0.9886 1.0943 1.3827 1.2401 1.4603 1.6870 2.5753 0.1113 0.9645 0 0.2621 0.4167 0.5036 0.6247 0.8549 1.0684 2.3181 0.2668 0.9886 0.2621 0 0.1
8、634 0.3951 0.8850 1.1109 1.3182 2.1587 0.3950 1.0943 0.4167 0.1634 0 0.3386 1.0303 1.2486 1.4477 2.2166 0.4101 1.3827 0.5036 0.3951 0.3386 0 0.9841 1.1603 1.3237 3.1740 0.6379 1.2401 0.6247 0.8850 1.0303 0.9841 0 0.2434 0.4738 3.3711 0.8536 1.4603 0.8549 1.1109 1.2486 1.1603 0.2434 0 0.2321 3.5402 1
9、.0550 1.6870 1.0684 1.3182 1.4477 1.3237 0.4738 0.2321 0 1.7370 0.9102 1.2017 0.9072 0.6485 0.5226 0.7762 1.5320 1.7594 1.9651 1.3754 1.1638 1.6871 1.2041 0.9520 0.7897 0.8571 1.7987 1.9989 2.1757 1.6960 0.8690 1.5800 0.9286 0.7014 0.5419 0.5207 1.4898 1.6775 1.8444 1.2508 1.3088 1.8837 1.3595 1.115
10、9 0.9526 0.9666 1.9354 2.1246 2.2898 1.6172 2.3889 3.2394 2.4819 2.3139 2.1719 1.9794 2.8806 2.9815 3.0566 2.4930 0.3709 0.7306 0.2790 0.2683 0.4077 0.6551 0.8280 1.0700 1.2953 2.6174 0.9079 0.2670 0.8067 0.7744 0.8594 1.1683 1.2074 1.4438 1.6757 2.7576 1.1363 0.1713 1.0318 1.0127 1.0967 1.4068 1.37
11、27 1.5998 1.8291 2.4780 0.9080 0.3983 0.8158 0.7373 0.7978 1.1225 1.2776 1.5183 1.7503 2.3869 1.2635 0.6021 1.1795 1.0598 1.0803 1.4183 1.6577 1.8977 2.1298 2.7753 1.5721 0.6122 1.4735 1.4108 1.4621 1.7929 1.8416 2.0675 2.2959 3.0231 1.7323 0.6924 1.6281 1.5967 1.6639 1.9868 1.9282 2.1416 2.3642 2.1
12、631 0.6291 0.8200 0.5824 0.3776 0.3668 0.7054 1.1855 1.4246 1.6450 2.2037 1.0602 0.6812 0.9895 0.8322 0.8310 1.1694 1.5272 1.7706 2.0005 2.1160 1.3504 0.8788 1.2840 1.1120 1.0891 1.4226 1.8247 2.0679 2.2981 2.3127 1.8966 1.2085 1.8226 1.6667 1.6489 1.9822 2.3238 2.5642 2.7962 1.8765 2.0497 1.5920 1.
13、9983 1.7924 1.7288 2.0337 2.5671 2.8104 3.0388 2.2144 2.2900 1.6676 2.2258 2.0448 2.0027 2.3231 2.7563 2.9985 3.2300 1.2418 1.5108 1.6359 1.5099 1.2510 1.1187 1.3239 2.1346 2.3617 2.5657 1.5610 1.7391 1.5152 1.7055 1.4734 1.3832 1.6619 2.3088 2.5492 2.7704 1.2554 2.0895 1.9493 2.0700 1.8231 1.7110 1
14、.9499 2.6868 2.9233 3.1382 Columns 11 through 20 1.7370 1.3754 1.6960 1.2508 1.6172 2.4930 2.6174 2.7576 2.4780 2.3869 0.9102 1.1638 0.8690 1.3088 2.3889 0.3709 0.9079 1.1363 0.9080 1.2635 1.2017 1.6871 1.5800 1.8837 3.2394 0.7306 0.2670 0.1713 0.3983 0.6021 0.9072 1.2041 0.9286 1.3595 2.4819 0.2790
15、 0.8067 1.0318 0.8158 1.1795 0.6485 0.9520 0.7014 1.1159 2.3139 0.2683 0.7744 1.0127 0.7373 1.0598 0.5226 0.7897 0.5419 0.9526 2.1719 0.4077 0.8594 1.0967 0.7978 1.0803 0.7762 0.8571 0.5207 0.9666 1.9794 0.6551 1.1683 1.4068 1.1225 1.4183 1.5320 1.7987 1.4898 1.9354 2.8806 0.8280 1.2074 1.3727 1.277
16、6 1.6577 1.7594 1.9989 1.6775 2.1246 2.9815 1.0700 1.4438 1.5998 1.5183 1.8977 1.9651 2.1757 1.8444 2.2898 3.0566 1.2953 1.6757 1.8291 1.7503 2.1298 0 0.4938 0.5267 0.6916 2.1051 0.7659 0.9347 1.1273 0.8100 0.9040 0.4938 0 0.3483 0.1979 1.6244 1.1556 1.4204 1.6199 1.3006 1.3844 0.5267 0.3483 0 0.447
17、1 1.6594 0.9457 1.3230 1.5470 1.2263 1.4036 0.6916 0.1979 0.4471 0 1.4362 1.3340 1.6172 1.8177 1.4982 1.5782 2.1051 1.6244 1.6594 1.4362 0 2.5778 2.9816 3.2020 2.8799 3.0067 0.7659 1.1556 0.9457 1.3340 2.5778 0 0.5406 0.7737 0.5379 0.9008 0.9347 1.4204 1.3230 1.6172 2.9816 0.5406 0 0.2386 0.1419 0.4
18、667 1.1273 1.6199 1.5470 1.8177 3.2020 0.7737 0.2386 0 0.3224 0.4376 0.8100 1.3006 1.2263 1.4982 2.8799 0.5379 0.1419 0.3224 0 0.3805 0.9040 1.3844 1.4036 1.5782 3.0067 0.9008 0.4667 0.4376 0.3805 0 1.3409 1.8229 1.8315 2.0165 3.4447 1.2017 0.6683 0.4691 0.6737 0.4384 1.5815 2.0674 2.0614 2.2621 3.6
19、865 1.3676 0.8274 0.5963 0.8662 0.6850 0.4265 0.8802 0.7647 1.0734 2.4226 0.3670 0.5591 0.7829 0.4643 0.7141 0.6384 1.1253 1.1333 1.3211 2.7434 0.7197 0.4520 0.5540 0.3139 0.2703 0.7763 1.2161 1.3017 1.4004 2.8366 1.0170 0.6999 0.7207 0.5786 0.2894 1.3046 1.6903 1.8297 1.8561 3.2741 1.5478 1.1287 1.
20、0380 1.0461 0.6666 1.2720 1.5302 1.7552 1.6592 3.0078 1.7459 1.4464 1.4229 1.3307 0.9936 1.5856 1.8848 2.0889 2.0219 3.3793 1.9583 1.5764 1.4969 1.4832 1.1100 0.6027 0.6012 0.8994 0.7005 2.0576 1.3528 1.3845 1.5161 1.2435 1.1524 0.8861 1.0916 1.3350 1.2166 2.5753 1.4818 1.3108 1.3616 1.1752 0.9316 1
21、.1899 1.2340 1.5417 1.2990 2.5052 1.8685 1.7407 1.7960 1.6032 1.3650 Columns 21 through 30 2.7753 3.0231 2.1631 2.2037 2.1160 2.3127 1.8765 2.2144 1.2418 1.5610 1.5721 1.7323 0.6291 1.0602 1.3504 1.8966 2.0497 2.2900 1.5108 1.7391 0.6122 0.6924 0.8200 0.6812 0.8788 1.2085 1.5920 1.6676 1.6359 1.5152
22、 1.4735 1.6281 0.5824 0.9895 1.2840 1.8226 1.9983 2.2258 1.5099 1.7055 1.4108 1.5967 0.3776 0.8322 1.1120 1.6667 1.7924 2.0448 1.2510 1.4734 1.4621 1.6639 0.3668 0.8310 1.0891 1.6489 1.7288 2.0027 1.1187 1.3832 1.7929 1.9868 0.7054 1.1694 1.4226 1.9822 2.0337 2.3231 1.3239 1.6619 1.8416 1.9282 1.185
23、5 1.5272 1.8247 2.3238 2.5671 2.7563 2.1346 2.3088 2.0675 2.1416 1.4246 1.7706 2.0679 2.5642 2.8104 2.9985 2.3617 2.5492 2.2959 2.3642 1.6450 2.0005 2.2981 2.7962 3.0388 3.2300 2.5657 2.7704 1.3409 1.5815 0.4265 0.6384 0.7763 1.3046 1.2720 1.5856 0.6027 0.8861 1.8229 2.0674 0.8802 1.1253 1.2161 1.69
24、03 1.5302 1.8848 0.6012 1.0916 1.8315 2.0614 0.7647 1.1333 1.3017 1.8297 1.7552 2.0889 0.8994 1.3350 2.0165 2.2621 1.0734 1.3211 1.4004 1.8561 1.6592 2.0219 0.7005 1.2166 3.4447 3.6865 2.4226 2.7434 2.8366 3.2741 3.0078 3.3793 2.0576 2.5753 1.2017 1.3676 0.3670 0.7197 1.0170 1.5478 1.7459 1.9583 1.3
25、528 1.4818 0.6683 0.8274 0.5591 0.4520 0.6999 1.1287 1.4464 1.5764 1.3845 1.3108 0.4691 0.5963 0.7829 0.5540 0.7207 1.0380 1.4229 1.4969 1.5161 1.3616 0.6737 0.8662 0.4643 0.3139 0.5786 1.0461 1.3307 1.4832 1.2435 1.1752 0.4384 0.6850 0.7141 0.2703 0.2894 0.6666 0.9936 1.1100 1.1524 0.9316 0 0.2518
26、1.1068 0.7031 0.6643 0.6927 1.1655 1.1390 1.5600 1.2511 0.2518 0 1.3199 0.9432 0.9155 0.8671 1.3635 1.2823 1.8114 1.4887 1.1068 1.3199 0 0.4656 0.7358 1.2930 1.4207 1.6672 0.9915 1.1254 0.7031 0.9432 0.4656 0 0.2982 0.8368 1.0437 1.2386 0.9621 0.8615 0.6643 0.9155 0.7358 0.2982 0 0.5598 0.7531 0.941
27、9 0.8959 0.6426 0.6927 0.8671 1.2930 0.8368 0.5598 0 0.5055 0.4596 1.2295 0.7600 1.1655 1.3635 1.4207 1.0437 0.7531 0.5055 0 0.3717 0.9653 0.4428 1.1390 1.2823 1.6672 1.2386 0.9419 0.4596 0.3717 0 1.3331 0.8095 1.5600 1.8114 0.9915 0.9621 0.8959 1.2295 0.9653 1.3331 0 0.5237 1.2511 1.4887 1.1254 0.8
28、615 0.6426 0.7600 0.4428 0.8095 0.5237 0 1.6646 1.8935 1.5033 1.2894 1.0765 1.0926 0.6241 0.9610 0.6423 0.4344 Column 31 1.2554 2.0895 1.9493 2.0700 1.8231 1.7110 1.9499 2.6868 2.9233 3.1382 1.1899 1.2340 1.5417 1.2990 2.5052 1.8685 1.7407 1.7960 1.6032 1.3650 1.6646 1.8935 1.5033 1.2894 1.0765 1.09
29、26 0.6241 0.9610 0.6423 0.4344 0BestShortcut = Columns 1 through 17 29 31 30 27 28 26 25 20 21 22 18 3 17 19 24 16 8 Columns 18 through 31 9 10 2 4 5 7 6 23 11 13 12 14 15 1theMinDistance = 1.5727e+004图2 31城市搜索图图3 搜索过程6. 总结本文针对TSP问题,首先给出了基于遗传算法求解TSP问题的一般性流程，设计了基于遗传算法的求解算法,包括编码设计、适应度函数选择、终止条件设定、选择算子设
30、定、交叉算子设定以及变异算子设定等, 然后设计并实现了基于遗传算法的TSP问题求解系统, 并编制了完整的Matlab程序予以仿真实现。根据仿真结果可知，遗传算法是寻求这种满意解的最佳工具之一，是一种高效、并行、全局搜索的方法。7. 参考文献1 雷英杰,等.2009 MATLAB 遗传算法工具箱及应用M.西安: 西安电子科技大学出版社, 8-9.2 储理才. 2001 基于MATLAB 的遗传算法程序设计及TSP问题求解J . 集美大学学报( 自然科学版) , 6(1) : 14-19.3 郎茂祥. 2009 配送车辆优化调度模型与算法M . 北京: 电子工业出版社,75.程序清单：31城市坐标
31、图(x)程序：load(x.txt,-ascii);load(y.txt,-ascii);plot(x,y,x)xlabel(X坐标),ylabel(Y坐标);grid onCalDist程序：function F=CalDist(dislist,s)DistanV=0;n=size(s,2);for i=1:(n-1) DistanV=DistanV+dislist(s(i),s(i+1);endDistanV=DistanV+dislist(s(n),s(1);F=DistanV;drawTSP程序：function m=drawTSP(Clist,BSF,bsf,p,f)CityNum=
32、size(Clist,1);for i=1:CityNum-1plot(Clist(BSF(i),1),Clist(BSF(i+1),1),Clist(BSF(i),2),Clist(BSF(i+1),2),ms-,LineWidth,2,MarkerEdgeColor,k,MarkerFaceColor,g); hold on;endplot(Clist(BSF(CityNum),1),Clist(BSF(1),1),Clist(BSF(CityNum),2),Clist(BSF(1),2),ms-,LineWidth,2,MarkerEdgeColor,k,MarkerFaceColor,
33、g);title(num2str(CityNum),城市TSP);if f=0 text(500,230,第 ,int2str(p), 步, 最短距离为 ,num2str(bsf);else text(500,230,最终搜索结果：最短距离 ,num2str(bsf);endhold off;pause(0.05);genetic_algorithm程序：function gaTSPCityNum=31;dislist,Clist=tsp(CityNum);inn=100; %初始种群大小gnmax=200; %最大代数pc=0.8; %交叉概率pm=0.8; %变异概率%产生初始种群for
34、i=1:inn s(i,:)=randperm(CityNum);endf,p=objf(s,dislist);gn=1;while gngnmax+1 for j=1:2:inn seln=sel(s,p); %选择操作 scro=cro(s,seln,pc); %交叉操作 scnew(j,:)=scro(1,:); scnew(j+1,:)=scro(2,:); smnew(j,:)=mut(scnew(j,:),pm); %变异操作 smnew(j+1,:)=mut(scnew(j+1,:),pm); end s=smnew; %产生了新的种群 f,p=objf(s,dislist);
35、%计算新种群的适应度 %记录当前代最好和平均的适应度 fmax,nmax=max(f); ymean(gn)=1000/mean(f); ymax(gn)=1000/fmax; %记录当前代的最佳个体 x=s(nmax,:); drawTSP(Clist,x,ymax(gn),gn,0); gn=gn+1; pause;endgn=gn-1;figure(2);plot(ymax,r); hold on;plot(ymean,b);grid;title(搜索过程);legend(最优解,平均解);end%计算适应度函数function f,p=objf(s,dislist);inn=size(
36、s,1); %读取种群大小for i=1:inn f(i)=CalDist(dislist,s(i,:); %计算函数值，即适应度endf=1000./f;%计算选择概率fsum=0;for i=1:inn fsum=fsum+f(i)15;endfor i=1:inn ps(i)=f(i)15/fsum;end%计算累积概率p(1)=ps(1);for i=2:inn p(i)=p(i-1)+ps(i);endp=p;endfunction pcc=pro(pc);test(1:100)=0;l=round(100*pc);test(1:l)=1;n=round(rand*99)+1;pcc=test(n); end%“选择”操作function seln=sel(s,p);inn=size(p,1);%从种群中选择两个个体for i=1:2 r=rand; %产生一个随机数 prand=p-r; j=1; while prand(j)0 j=j+1; end seln(i)=j; %选中个体的序号endend%“交叉”操作