1. 2. 3. 4. 5. 6. 7. 8. 9.
遗传算法解决 TSP 问题（附matlab源程序）
知n个城市之间的相互距离，现有一个推销员必须遍访这n个城市，并且每个城市 只能访问一次，最后又必须返回出发城市。如何安排他对这些城市的访问次序，可使其 旅行路线的总长度最短？
用图论的术语来说，假设有一个图g=(v,e)，其中v是顶点集，e是边集，设d=(dij) 是由顶点i和顶点j之间的距离所组成的距离矩阵，旅行商问题就是求出一条通过所有顶 点且每个顶点只通过一次的具有最短距离的回路。
这个问题可分为对称旅行商问题(dij=dji,,任意i,j=1,2,3，…,n)和非对称旅行商 问题(dij≠dji,,任意i,j=1,2,3，…,n)。
10. 若对于城市v={v1,v2,v3,…,vn}的一个访问顺序为t=(t1,t2,t3,…,ti,…,tn),其中 11. ti∈v(i=1,2,3,…,n)，且记tn+1= t1，则旅行商问题的数学模型为： 12. min l=σd(t(i),t(i+1)) （i=1,…,n）
13. 旅行商问题是一个典型的组合优化问题，并且是一个np难问题，其可能的路径数目 14. 与城市数目n是成指数型增长的，所以一般很难精确地求出其最优解，本文采用遗传算法 15. 求其近似解。 16. 遗传算法：
17. 初始化过程：用v1,v2,v3,…,vn代表所选n个城市。定义整数pop-size作为染色体的个数 18. ，并且随机产生pop-size个初始染色体，每个染色体为1到18的整数组成的随机序列。 19. 适应度f的计算：对种群中的每个染色体vi，计算其适应度，f=σd(t(i),t(i+1)). 20. 评价函数eval(vi)：用来对种群中的每个染色体vi设定一个概率，以使该染色体被选中 21. 的可能性与其种群中其它染色体的适应性成比例，既通过轮盘赌，适应性强的染色体被 22. 选择产生后台的机会要大，设alpha∈(0,1)，本文定义基于序的评价函数为eval(vi)=al 23. pha*(1-alpha).^(i-1) 。[随机规划与模糊规划]
24. 选择过程：选择过程是以旋转赌轮pop-size次为基础，每次旋转都为新的种群选择一个 25. 染色体。赌轮是按每个染色体的适应度进行选择染色体的。
26. step1 、对每个染色体vi,计算累计概率qi，q0=0;qi=σeval(vj) j=1,…,i;i=1, 27. …pop-size.
28. step2、从区间(0,pop-size)中产生一个随机数r；
29. step3、若qi-1 step4、重复step2和step3共pop-size次，这样可以得到pop-size个复制的染色体。 30. grefenstette编码：由于常规的交叉运算和变异运算会使种群中产生一些无实际意义的 31. 染色体，本文采用grefenstette编码《遗传算法原理及应用》可以避免这种情况的出现 32. 。所谓的grefenstette编码就是用所选队员在未选（不含淘汰）队员中的位置，如： 33. 8 15 2 16 10 7 4 3 11 14 6 12 9 5 18 13 17 1 34. 对应：
35. 8 14 2 13 8 6 3 2 5 7 3 4 3 2 4 2 2 1。
36. 交叉过程：本文采用常规单点交叉。为确定交叉操作的父代，从 到pop-size重复以下过
37. 程：从[0，1]中产生一个随机数r，如果r 将所选的父代两两组队，随机产生一个位置进行交叉，如： 38. 8 14 2 13 8 6 3 2 5 7 3 4 3 2 4 2 2 1 39. 6 12 3 5 6 8 5 6 3 1 8 5 6 3 3 2 1 1 40. 交叉后为：
41. 8 14 2 13 8 6 3 2 5 1 8 5 6 3 3 2 1 1 42. 6 12 3 5 6 8 5 6 3 7 3 4 3 2 4 2 2 1
43. 变异过程：本文采用均匀多点变异。类似交叉操作中选择父代的过程，在r 选择多个染色体vi作为父代。对每一个
选择的父代，随机选择多个位置，使其在每位置
44. 按均匀变异（该变异点xk的取值范围为[ukmin,ukmax],产生一个[0，1]中随机数r，该点 45. 变异为x'k=ukmin+r(ukmax-ukmin)）操作。如： 46. 8 14 2 13 8 6 3 2 5 7 3 4 3 2 4 2 2 1 47. 变异后：
48. 8 14 2 13 10 6 3 2 2 7 3 4 5 2 4 1 2 1
49. 反grefenstette编码：交叉和变异都是在grefenstette编码之后进行的，为了循环操作 50. 和返回最终结果，必须逆grefenstette编码过程，将编码恢复到自然编码。
51. 循环操作：判断是否满足设定的带数xzome，否，则跳入适应度f的计算；是，结束遗传 52. 操作，跳出。 53. 54. 55.
56. matlab 代码 57. 58. 59.
60. distTSP.txt 61. 0 6 18 4 8 62. 7 0 17 3 7 63. 4 4 0 4 5 64. 20 19 24 0 22 65. 8 8 16 6 0 66. %GATSP.m
67. function gatsp1() 68. clear;
69. load distTSP.txt; 70. distance=distTSP; 71. N=5; 72. ngen=100; 73. ngpool=10;
74. %ngen=input('# of generations to evolve = ');
75. %ngpool=input('# of chromosoms in the gene pool = '); % size of genepool 76. gpool=zeros(ngpool,N+1); % gene pool 77. for i=1:ngpool, % intialize gene pool 78. gpool(i,:)=[1 randomize([2:N]')' 1]; 79. for j=1:i-1
80. while gpool(i,:)==gpool(j,:)
81. gpool(i,:)=[1 randomize([2:N]')' 1]; 82. end 83. end 84. end 85.
86. costmin=100000; 87. tourmin=zeros(1,N);
88. cost=zeros(1,ngpool); 89. increase=1;resultincrease=1; 90. for i=1:ngpool,
91. cost(i)=sum(diag(distance(gpool(i,:)',rshift(gpool(i,:))'))); 92. end
93. % record current best solution 94. [costmin,idx]=min(cost); 95. tourmin=gpool(idx,:);
96. disp([num2str(increase) 'minmum trip length = ' num2str(costmin)]) 97.
98. costminold2=200000;costminold1=150000;resultcost=100000; 99. tourminold2=zeros(1,N); 100. tourminold1=zeros(1,N); 101. resulttour=zeros(1,N);
102. while (abs(costminold2-costminold1) ;100)&(abs(costminold1-costmin) ;100)&(increase ;500) 103.
104. costminold2=costminold1; tourminold2=tourminold1; 105. costminold1=costmin;tourminold1=tourmin; 106. increase=increase+1; 107. if resultcost>costmin 108. resultcost=costmin; 109. resulttour=tourmin; 110. resultincrease=increase-1; 111. end
112. for i=1:ngpool,
113. cost(i)=sum(diag(distance(gpool(i,:)',rshift(gpool(i,:))'))); 114. end
115. % record current best solution 116. [costmin,idx]=min(cost); 117. tourmin=gpool(idx,:); 118. %==============
119. % copy gens in th gpool according to the probility ratio 120. % >1.1 copy twice 121. % >=0.9 copy once 122. % ;0.9 remove
123. [csort,ridx]=sort(cost); 124. % sort from small to big. 125. csum=sum(csort); 126. caverage=csum/ngpool;
127. cprobilities=caverage./csort; 128. copynumbers=0;removenumbers=0; 129. for i=1:ngpool,
130. if cprobilities(i) >1.1 131. copynumbers=copynumbers+1;