案例4：基于遗传算法的TSP算法.doc

【注】原帖网址:/thread-9220-1-2.htmlMy Email：案例4：基于遗传算法的TSP算法*论坛申明：1 案例为原创案例，论坛拥有帖子的版权，转载请注明出处（MATLABSKY论坛，MATLAB智能算法30个案例分析2 案例内容为书籍原创内容，内容为案例的提纲和主要内容。3 作者长期驻扎在板块，对读者和会员问题有问必答。4 案例配套有教学视频和完整的MATLAB程序，MATLAB程序在购买书籍后可以自由下载，教学视频需要另外购买。MATLAB书籍预定方法和优惠服务：/thread-9258-1-1.html点击这里，预览该案例程序：/znsf/view/s1/GA_TSP.html已经预定的朋友点此下载程序源代码：/thread-9391-1-1.html*1、案例背景 TSP (旅行商问题Traveling Salesman Problem)，是典型的NP完全问题，即其最坏情况下的时间复杂性随着问题规模的增大按指数方式增长，到目前为止不能找到一个多项式时间的有效算法。遗传算法是一种进化算法，其基本原理是仿效生物界中的“物竞天择、适者生存”的演化法则。遗传算法的做法是把问题参数编码为染色体，再利用迭代的方式进行选择、交叉以及变异等运算来交换种群中染色体的信息，最终生成符合优化目标的染色体。实践证明，遗传算法对于解决TSP问题等组合优化问题具有较好的寻优性能。2、案例目录：第4章基于遗传算法的TSP算法4.1 理论基础4.1.1遗传算法概述4.1.2TSP问题介绍4.2 案例背景4.2.1问题描述4.2.2解决思路及步骤 算法流程 遗传算法实现1. 编码2. 种群初始化3. 适应度函数4. 选择操作5. 交叉操作6. 变异操作7. 进化逆转操作4.3 MATLAB程序实现4.3.1种群初始化4.3.2 适应度函数4.3.3选择操作4.3.4交叉操作4.3.5变异操作4.3.6进化逆转操作4.3.7画路线轨迹图4.3.8遗传算法主函数4.3.9结果分析4.4 延伸阅读4.4.1应用扩展4.4.2遗传算法的改进4.4.3算法的局限性4.5 参考文献3、案例实例及结果：本案例以14个城市为例，假定14个城市的位置坐标为： 表4.114个城市的位置坐标城市编号X坐标Y坐标116.4796.1216.4794.44320.0992.54422.3993.37525.2397.2462296.05720.4797.02817.296.29916.397.381014.0598.121116.5397.381221.5295.591319.4197.131420.0992.55从某个城市出发访问每个城市一次且仅一次， 最后回到出发城市，如何安排才使其所走路线最短。结果：优化前的一个随机路线轨迹图2010-8-9 00:37 上传下载附件 (27.73 KB) 优化前的一个随机路线轨迹图 图4.1随机路线图随机路线为：117104129148135236111总距离：71.1144优化后的路线图：2010-8-9 00:37 上传下载附件 (22.93 KB) 最优解路线图 图4.2最优解路线图最优解路线:54314211091181371265总距离：29.3405优化迭代过程：2010-8-9 00:37 上传下载附件 (17.17 KB) 遗传算法进化过程图 图4.3 遗传算法进化过程图4、主程序：1. clear2. clc3. close all4. load CityPosition1;%个城市坐标位置5. NIND=100; %种群大小6. MAXGEN=200;7. Pc=0.9; %交叉概率8. Pm=0.05; %变异概率9. GGAP=0.9; %代沟(Generation gap)10. D=Distanse(X);%生成距离矩阵11. N=size(D,1); %(34*34)12. % 初始化种群13. Chrom=InitPop(NIND,N);14. % 在二维图上画出所有坐标点15. % figure16. % plot(X(:,1),X(:,2),o);17. % 画出随机解的路线图18. DrawPath(Chrom(1,:),X)19. pause(0.0001)20. % 输出随机解的路线和总距离21. disp(初始种群中的一个随机值:)22. OutputPath(Chrom(1,:);23. Rlength=PathLength(D,Chrom(1,:);24. disp(总距离：,num2str(Rlength);25. disp()26. % 优化27. gen=0;28. figure;29. hold on;box on30. xlim(0,MAXGEN)31. title(优化过程)32. xlabel(代数)33. ylabel(最优值)34. ObjV=PathLength(D,Chrom);%计算路线长度35. preObjV=min(ObjV);36. while genMAXGEN37. % 计算适应度38. ObjV=PathLength(D,Chrom);%计算路线长度39. % fprintf(%d %1.10fn,gen,min(ObjV)40. line(gen-1,gen,preObjV,min(ObjV);pause(0.0001)41. preObjV=min(ObjV);42. FitnV=Fitness(ObjV);43. % 选择44. SelCh=Select(Chrom,FitnV,GGAP);45. % 交叉操作46. SelCh=Recombin(SelCh,Pc);47. % 变异48. SelCh=Mutate(SelCh,Pm);49. % 逆转操作50. SelCh=Reverse(SelCh,D);51. % 重插入子代的新种群52. Chrom=Reins(Chrom,SelCh,ObjV);53. % 更新迭代次数54. gen=gen+1 ;55. end56. % 画出最优解的路线图57. ObjV=PathLength(D,Chrom);%计算路线长度58. minObjV,minInd=min(ObjV);59. DrawPa