遗传算法解决TSP问题的matlab程序

1. 遗传算法解决 TSP 问题（附matlab源程序） 2. 知n个城市之间的相互距离，现有一个推销员必须遍访这n个城市，并且每个城市 3. 只能访问一次，最后又必须返回出发城市。如何安排他对这些城市的访问次序，可使其 4. 旅行路线的总长度最短？ 5. 用图论的术语来说，假设有一个图g=(v,e)，其中v是顶点集，e是边集，设d=(dij) 6. 是由顶点i和顶点j之间的距离所组成的距离矩阵，旅行商问题就是求出一条通过所有顶 7. 点且每个顶点只通过一次的具有最短距离的回路。 8. 这个问题可分为对称旅行商问题(dij=dji,,任意i,j=1,2,3，…,n)和非对称旅行商 9. 问题(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代 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 所选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; 132. end 133. if cprobilities(i) <0.9 134. removenumbers=removenumbers+1; 135. end 136. end 137. copygpool=min(copynumbers,removenumbers); 138. for i=1:copygpool 139. for j=ngpool:-1:2*i+2 gpool(j,:)=gpool(j-1,:); 140. end 141. gpool(2*i+1,:)=gpool(i,:); 142. end 143. if copygpool==0 144. gpool(ngpool,:)=gpool(1,:); 145. end 146. %========= 147. %when genaration is more than 50,or the patterns in a couple are too close,do mutation 148. for i=1:ngpool/2 149. % 150. sameidx=[gpool(2*i-1,:)==gpool(2*i,:)]; 151. diffidx=find(sameidx==0); 152. if length(diffidx)<=2 153. gpool(2*i,:)=[1 randomize([2:12]')' 1]; 154. end 155. end 156. %=========== 157. %cross gens in couples 158. for i=1:ngpool/2 159. [gpool(2*i-1,:),gpool(2*i,:)]=crossgens(gpool(2*i-1,:),gpool(2*i,:)); 160. end 161. 162. for i=1:ngpool, 163. cost(i)=sum(diag(distance(gpool(i,:)',rshift(gpool(i,:))'))); 164. end 165. % record current best solution 166. [costmin,idx]=min(cost); 167. tourmin=gpool(idx,:); 168. disp([num2str(increase) 'minmum trip length = ' num2str(costmin)]) 169. end 170. 171. disp(['cost function evaluation: ' int2str(increase) ' times!']) 172. disp(['n:' int2str(resultincrease)]) 173. disp(['minmum trip length = ' num2str(resultcost)]) 174. disp('optimum tour = ') 175. disp(num2str(resulttour)) 176. %==================================================== 177. function B=randomize(A,rowcol) 178. % Usage: B=randomize(A,rowcol) 179. % randomize row orders or column orders of A matrix 180. % rowcol: if =0 or omitted, row order (default) 181. % if = 1, column order 182. 183. rand('state',sum(100*clock)) 184. if nargin == 1, 185. rowcol=0; 186. end 187. if rowcol==0, 188. [m,n]=size(A); 189. p=rand(m,1); 190. [p1,I]=sort(p); 191. B=A(I,:); 192. elseif rowcol==1, 193. Ap=A'; 194. [m,n]=size(Ap); 195. p=rand(m,1); 196. [p1,I]=sort(p); 197. B=Ap(I,:)'; 198. end 199. %===================================================== 200. function y=rshift(x,dir) 201. % Usage: y=rshift(x,dir) 202. % rotate x vector to right (down) by 1 if dir = 0 (default) 203. % or rotate x to left (up) by 1 if dir = 1 204. if nargin ;2, dir=0; end 205. [m,n]=size(x); 206. if m>1, 207. if n == 1, 208. col=1; 209. elseif n>1, 210. error('x must be a vector! break'); 211. end % x is a column vectorelseif m == 1, 212. if n == 1, y=x; 213. return 214. elseif n>1, 215. col=0; % x is a row vector endend 216. if dir==1, % rotate left or up 217. if col==0, % row vector, rotate left 218. y = [x(2:n) x(1)]; 219. elseif col==1, 220. y = [x(2:n); x(1)]; % rotate up 221. end 222. elseif dir==0, % default rotate right or down 223. if col==0, 224. y = [x(n) x(1:n-1)]; 225. elseif col==1 % column vector 226. y = [x(n); x(1:n-1)]; 227. end 228. end 229. %================================================== 230. function [L1,L2]=crossgens(X1,X2) 231. % Usage:[L1,L2]=crossgens(X1,X2) 232. s=randomize([2:12]')'; 233. n1=min(s(1),s(11));n2=max(s(1),s(11)); 234. X3=X1;X4=X2; 235. for i=n1:n2, 236. for j=1:13, 237. if X2(i)==X3(j), 238. X3(j)=0; 239. end 240. if X1(i)==X4(j), X4(j)=0; 241. end 242. end 243. end 244. j=13;k=13; 245. for i=12:-1:2, 246. if X3(i)~=0, 247. j=j-1; 248. t=X3(j);X3(j)=X3(i);X3(i)=t; 249. end 250. if X4(i)~=0, 251. k=k-1; 252. t=X4(k);X4(k)=X4(i);X4(i)=t; 253. end 254. end 255. for i=n1:n2 256. X3(2+i-n1)=X2(i); 257. X4(2+i-n1)=X1(i); 258. end 259. L1=X3;L2=X4; 遗传算法程序 matlab 1. 遗传算法程序: 2. 说明: fga.m 为遗传算法的主程序; 采用二进制Gray编码,采用基于轮盘赌法的非线性排名选择, 均匀交叉,变异操作,而且还引入了倒位操作! 3. 4. function [BestPop,Trace]=fga(FUN,LB,UB,eranum,popsize,pCross,pMutation,pInversion,options) 5. % [BestPop,Trace]=fmaxga(FUN,LB,UB,eranum,popsize,pcross,pmutation) 6. % Finds a maximum of a function of several variables. 7. % fmaxga solves problems of the form: 8. % max F(X) subject to: LB <= X <= UB 9. % BestPop - 最优的群体即为最优的染色体群 10. % Trace - 最佳染色体所对应的目标函数值 11. % FUN - 目标函数 12. % LB - 自变量下限 13. % UB - 自变量上限 14. % eranum - 种群的代数,取100--1000(默认200) 15. % popsize - 每一代种群的规模；此可取50--200(默认100) 16. % pcross - 交叉概率,一般取0.5--0.85之间较好(默认0.8) 17. % pmutation - 初始变异概率,一般取0.05-0.2之间较好(默认0.1) 18. % pInversion - 倒位概率,一般取0.05－0.3之间较好(默认0.2) 19. % options - 1*2矩阵,options(1)=0二进制编码(默认0),option(1)~=0十进制编 20. %码,option(2)设定求解精度(默认1e-4) 21. % 22. % ------------------------------------------------------------------------ 23. 24. T1=clock; 25. if nargin<3, error('FMAXGA requires at least three input arguments'); end 26. if nargin==3, eranum=200;popsize=100;pCross=0.8;pMutation=0.1;pInversion=0.15;options=[0 1e-4];end 27. if nargin==4, popsize=100;pCross=0.8;pMutation=0.1;pInversion=0.15;options=[0 1e-4];end 28. if nargin==5, pCross=0.8;pMutation=0.1;pInversion=0.15;options=[0 1e-4];end 29. if nargin==6, pMutation=0.1;pInversion=0.15;options=[0 1e-4];end 30. if nargin==7, pInversion=0.15;options=[0 1e-4];end 31. if find((LB-UB)>0) 32. error('数据输入错误,请重新输入(LB1时,b(i)=mod(a(i-1)+a(i),2) 104. %其中原二进制串:a(1)a(2)...a(n),Gray串:b(1)b(2)...b(n) 105. initpop(i,:)=pop(1:end-1); 106. end 107. initpop(popsize,:)=ones(1,len);%The whole one encoding individual 108. 109. 110. 111. 112. %解码 113. 114. function [fval] = b2f(bval,bounds,bits) 115. % fval - 表征各变量的十进制数 116. % bval - 表征各变量的二进制编码串 117. % bounds - 各变量的取值范围 118. % bits - 各变量的二进制编码长度 119. scale=(bounds(:,2)-bounds(:,1))'./(2.^bits-1); %The range of the variables 120. numV=size(bounds,1); 121. cs=[0 cumsum(bits)]; 122. for i=1:numV 123. a=bval((cs(i)+1):cs(i+1)); 124. fval(i)=sum(2.^(size(a,2)-1:-1:0).*a)*scale(i)+bounds(i,1); 125. end 126. 127. 128. 129. 130. %选择操作 131. %采用基于轮盘赌法的非线性排名选择 132. %各个体成员按适应值从大到小分配选择概率： 133. %P(i)=(q/1-(1-q)^n)*(1-q)^i, 其中 P(0)>P(1)>...>P(n), sum(P(i))=1 134. 135. function [selectpop]=NonlinearRankSelect(FUN,pop,bounds,bits) 136. global m n 137. selectpop=zeros(m,n); 138. fit=zeros(m,1); 139. for i=1:m 140. fit(i)=feval(FUN(1,:),(b2f(pop(i,:),bounds,bits)));%以函数值为适应值做排名依据 141. end 142. selectprob=fit/sum(fit);%计算各个体相对适应度(0,1) 143. q=max(selectprob);%选择最优的概率 144. x=zeros(m,2); 145. x(:,1)=[m:-1:1]'; 146. [y x(:,2)]=sort(selectprob); 147. r=q/(1-(1-q)^m);% 标准 excel标准偏差excel标准偏差函数exl标准差函数国标检验抽样标准表免费下载红头文件格式标准下载 分布基值 148. newfit(x(:,2))=r*(1-q).^(x(:,1)-1);%生成选择概率 149. newfit=cumsum(newfit);%计算各选择概率之和 150. rNums=sort(rand(m,1)); 151. fitIn=1;newIn=1; 152. while newIn<=m 153. if rNums(newIn)=pCross); 171. len=length(y1); 172. if len>2&mod(len,2)==1%如果用来进行交叉的染色体的条数为奇数，将其调整为偶数 173. y2(length(y2)+1)=y1(len); 174. y1(len)=[]; 175. end 176. if length(y1)>=2 177. for i=0:2:length(y1)-2 178. if opts==0 179. [NewPop(y1(i+1),:),NewPop(y1(i+2),:)]=EqualCrossOver(OldPop(y1(i+1),:),OldPop(y1(i+2),:)); 180. else 181. [NewPop(y1(i+1),:),NewPop(y1(i+2),:)]=MultiPointCross(OldPop(y1(i+1),:),OldPop(y1(i+2),:)); 182. end 183. end 184. end 185. NewPop(y2,:)=OldPop(y2,:); 186. 187. %采用均匀交叉 188. function [children1,children2]=EqualCrossOver(parent1,parent2) 189. 190. global n children1 children2 191. hidecode=round(rand(1,n));%随机生成掩码 192. crossposition=find(hidecode==1); 193. holdposition=find(hidecode==0); 194. children1(crossposition)=parent1(crossposition);%掩码为1，父1为子1提供基因 195. children1(holdposition)=parent2(holdposition);%掩码为0，父2为子1提供基因 196. children2(crossposition)=parent2(crossposition);%掩码为1，父2为子2提供基因 197. children2(holdposition)=parent1(holdposition);%掩码为0，父1为子2提供基因 198. 199. %采用多点交叉，交叉点数由变量数决定 200. 201. function [Children1,Children2]=MultiPointCross(Parent1,Parent2) 202. 203. global n Children1 Children2 VarNum 204. Children1=Parent1; 205. Children2=Parent2; 206. Points=sort(unidrnd(n,1,2*VarNum)); 207. for i=1:VarNum 208. Children1(Points(2*i-1):Points(2*i))=Parent2(Points(2*i-1):Points(2*i)); 209. Children2(Points(2*i-1):Points(2*i))=Parent1(Points(2*i-1):Points(2*i)); 210. end 211. 212. 213. 214. 215. %变异操作 216. function [NewPop]=Mutation(OldPop,pMutation,VarNum) 217. 218. global m n NewPop 219. r=rand(1,m); 220. position=find(r<=pMutation); 221. len=length(position); 222. if len>=1 223. for i=1:len 224. k=unidrnd(n,1,VarNum); %设置变异点数，一般设置1点 225. for j=1:length(k) 226. if OldPop(position(i),k(j))==1 227. OldPop(position(i),k(j))=0; 228. else 229. OldPop(position(i),k(j))=1; 230. end 231. end 232. end 233. end 234. NewPop=OldPop; 235. 236. 237. 238. 239. %倒位操作 240. 241. function [NewPop]=Inversion(OldPop,pInversion) 242. 243. global m n NewPop 244. NewPop=OldPop; 245. r=rand(1,m); 246. PopIn=find(r<=pInversion); 247. len=length(PopIn); 248. if len>=1 249. for i=1:len 250. d=sort(unidrnd(n,1,2)); 251. if d(1)~=1&d(2)~=n 252. NewPop(PopIn(i),1:d(1)-1)=OldPop(PopIn(i),1:d(1)-1); 253. NewPop(PopIn(i),d(1):d(2))=OldPop(PopIn(i),d(2):-1:d(1)); 254. NewPop(PopIn(i),d(2)+1:n)=OldPop(PopIn(i),d(2)+1:n); 255. end 256. end 257. end   TSP问题（又名：旅行商问题，货郎担问题）遗传算法通用matlab程序 %D是距离矩阵，n为种群个数,建议取为城市个数的1~2倍， %C为停止代数，遗传到第 C代时程序停止,C的具体取值视问题的规模和耗费的时间而定 %m为适应值归一化淘汰加速指数 ,最好取为1,2,3,4 ,不宜太大 %alpha为淘汰保护指数,可取为0~1之间任意小数,取1时关闭保护功能,最好取为0.8~1.0 %R为最短路径,Rlength为路径长度 function [R,Rlength]=geneticTSP(D,n,C,m,alpha) [N,NN]=size(D); farm=zeros(n,N);%用于存储种群 for i=1:n farm(i,:)=randperm(N);%随机生成初始种群 end R=farm(1,:);%存储最优种群 len=zeros(n,1);%存储路径长度 fitness=zeros(n,1);%存储归一化适应值 counter=0; while counter=alpha*rand nn=nn+1; FARM(nn,:)=farm(i,:); end end FARM=FARM(1:nn,:); [aa,bb]=size(FARM);%交叉和变异 while aan FARM=FARM(1:n,:);%保持种群规模为n end farm=FARM; clear FARM counter=counter+1 end Rlength=myLength(D,R); function [a,b]=intercross(a,b) L=length(a); if L<=10%确定交叉宽度 W=1; elseif ((L/10)-floor(L/10))>=rand&&L>10 W=ceil(L/10); else W=floor(L/10); end p=unidrnd(L-W+1);%随机选择交叉范围，从p到p+W for i=1:W%交叉 x=find(a==b(1,p+i-1)); y=find(b==a(1,p+i-1)); [a(1,p+i-1),b(1,p+i-1)]=exchange(a(1,p+i-1),b(1,p+i-1)); [a(1,x),b(1,y)]=exchange(a(1,x),b(1,y)); end function [x,y]=exchange(x,y) temp=x; x=y; y=temp; % 计算路径的子程序 function len=myLength(D,p) [N,NN]=size(D); len=D(p(1,N),p(1,1)); for i=1:(N-1) len=len+D(p(1,i),p(1,i+1)); end %计算归一化适应值子程序 function fitness=fit(len,m,maxlen,minlen) fitness=len; for i=1:length(len) fitness(i,1)=(1-((len(i,1)-minlen)/(maxlen-minlen+0.000001))).^m; end 已知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)。 若对于城市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是成指数型增长的，所以一般很难精确地求出其最优解，本文采用遗传算法 求其近似解。 遗传算法： 初始化过程：用v1,v2,v3,…,vn代表所选n个城市。定义整数pop-size作为染色体的个数 ，并且随机产生pop-size个初始染色体，每个染色体为1到18的整数组成的随机序列。 适应度f的计算：对种群中的每个染色体vi，计算其适应度，f=σd(t(i),t(i+1)). 评价函数eval(vi)：用来对种群中的每个染色体vi设定一个概率，以使该染色体被选中 的可能性与其种群中其它染色体的适应性成比例，既通过轮盘赌，适应性强的染色体被 选择产生后台的机会要大，设alpha∈(0,1)，本文定义基于序的评价函数为eval(vi)=al pha*(1-alpha).^(i-1) 。[随机规划与模糊规划] 选择过程：选择过程是以旋转赌轮pop-size次为基础，每次旋转都为新的种群选择一个 染色体。赌轮是按每个染色体的适应度进行选择染色体的。 step1 、对每个染色体vi,计算累计概率qi，q0=0;qi=σeval(vj)   j=1,…,i;i=1, …pop-size. step2、从区间(0,pop-size)中产生一个随机数r； step3、若qi-1   step4、重复step2和step3共pop-size次，这样可以得到pop-size个复制的染色体。 grefenstette编码：由于常规的交叉运算和变异运算会使种群中产生一些无实际意义的 染色体，本文采用grefenstette编码《遗传算法原理及应用》可以避免这种情况的出现 。所谓的grefenstette编码就是用所选队员在未选（不含淘汰）队员中的位置，如： 8 15 2 16 10 7 4 3 11 14 6 12 9 5 18 13 17 1 对应： 8 14 2 13 8 6 3 2 5 7 3 4 3 2 4 2 2 1。 交叉过程：本文采用常规单点交叉。为确定交叉操作的父代，从 到pop-size重复以下过 程：从[0，1]中产生一个随机数r，如果r           将所选的父代两两组队，随机产生一个位置进行交叉，如： 8 14 2 13 8 6 3 2 5 7 3 4 3 2 4 2 2 1 6 12 3 5 6 8 5 6 3 1 8 5 6 3 3 2 1 1 交叉后为： 8 14 2 13 8 6 3 2 5 1 8 5 6 3 3 2 1 1 6 12 3 5 6 8 5 6 3 7 3 4 3 2 4 2 2 1 变异过程：本文采用均匀多点变异。类似交叉操作中选择父代的过程，在r选择多个染色体vi作为父代。对每一个选择的父代，随机选择多个位置，使其在每位置 按均匀变异（该变异点xk的取值范围为[ukmin,ukmax],产生一个[0，1]中随机数r，该点 变异为x'k=ukmin+r(ukmax-ukmin)）操作。如： 8 14 2 13 8 6 3 2 5 7 3 4 3 2 4 2 2 1 变异后： 8 14 2 13 10 6 3 2 2 7 3 4 5 2 4 1 2 1 反grefenstette编码：交叉和变异都是在grefenstette编码之后进行的，为了循环操作 和返回最终结果，必须逆grefenstette编码过程，将编码恢复到自然编码。 循环操作：判断是否满足设定的带数xzome，否，则跳入适应度f的计算；是，结束遗传 操作，跳出。 matlab 代码 distTSP.txt 0 6 18 4 8 7 0 17 3 7 4 4 0 4 5 20 19 24 0 22 8 8 16 6 0 %GATSP.m function gatsp1() clear; load distTSP.txt; distance=distTSP; N=5; ngen=100; ngpool=10; %ngen=input('# of generations to evolve = '); %ngpool=input('# of chromosoms in the gene pool = '); % size of genepool gpool=zeros(ngpool,N+1); % gene pool for i=1:ngpool, % intialize gene pool gpool(i,:)=[1 randomize([2:N]')' 1]; for j=1:i-1 while gpool(i,:)==gpool(j,:) gpool(i,:)=[1 randomize([2:N]')' 1]; end end end costmin=100000; tourmin=zeros(1,N); cost=zeros(1,ngpool); increase=1;resultincrease=1; for i=1:ngpool, cost(i)=sum(diag(distance(gpool(i,:)',rshift(gpool(i,:))'))); end % record current best solution [costmin,idx]=min(cost); tourmin=gpool(idx,:); disp([num2str(increase) 'minmum trip length = ' num2str(costmin)]) costminold2=200000;costminold1=150000;resultcost=100000; tourminold2=zeros(1,N); tourminold1=zeros(1,N); resulttour=zeros(1,N); while (abs(costminold2-costminold1) ;100)&(abs(costminold1-costmin) ;100)&(increase ;500) costminold2=costminold1; tourminold2=tourminold1; costminold1=costmin;tourminold1=tourmin; increase=increase+1; if resultcost>costmin resultcost=costmin; resulttour=tourmin; resultincrease=increase-1; end for i=1:ngpool, cost(i)=sum(diag(distance(gpool(i,:)',rshift(gpool(i,:))'))); end % record current best solution [costmin,idx]=min(cost); tourmin=gpool(idx,:); %============== % copy gens in th gpool according to the probility ratio % >1.1 copy twice % >=0.9 copy once % ;0.9 remove [csort,ridx]=sort(cost); % sort from small to big. csum=sum(csort); caverage=csum/ngpool; cprobilities=caverage./csort; copynumbers=0;removenumbers=0; for i=1:ngpool, if cprobilities(i) >1.1 copynumbers=copynumbers+1; end if cprobilities(i) <0.9 removenumbers=removenumbers+1; end end copygpool=min(copynumbers,removenumbers); for i=1:copygpool for j=ngpool:-1:2*i+2 gpool(j,:)=gpool(j-1,:); end gpool(2*i+1,:)=gpool(i,:); end if copygpool==0 gpool(ngpool,:)=gpool(1,:); end %========= %when genaration is more than 50,or the patterns in a couple are too close,do mutation for i=1:ngpool/2 % sameidx=[gpool(2*i-1,:)==gpool(2*i,:)]; diffidx=find(sameidx==0); if length(diffidx)<=2 gpool(2*i,:)=[1 randomize([2:12]')' 1]; end end %=========== %cross gens in couples for i=1:ngpool/2 [gpool(2*i-1,:),gpool(2*i,:)]=crossgens(gpool(2*i-1,:),gpool(2*i,:)); end for i=1:ngpool, cost(i)=sum(diag(distance(gpool(i,:)',rshift(gpool(i,:))'))); end % record current best solution [costmin,idx]=min(cost); tourmin=gpool(idx,:); disp([num2str(increase) 'minmum trip length = ' num2str(costmin)]) end   disp(['cost function evaluation: ' int2str(increase) ' times!']) disp(['n:' int2str(resultincrease)]) disp(['minmum trip length = ' num2str(resultcost)]) disp('optimum tour = ') disp(num2str(resulttour)) %==================================================== function B=randomize(A,rowcol) % Usage: B=randomize(A,rowcol) % randomize row orders or column orders of A matrix % rowcol: if =0 or omitted, row order (default) % if = 1, column order rand('state',sum(100*clock)) if nargin == 1, rowcol=0; end if rowcol==0, [m,n]=size(A); p=rand(m,1); [p1,I]=sort(p); B=A(I,:); elseif rowcol==1, Ap=A'; [m,n]=size(Ap); p=rand(m,1); [p1,I]=sort(p); B=Ap(I,:)'; end %===================================================== function y=rshift(x,dir) % Usage: y=rshift(x,dir) % rotate x vector to right (down) by 1 if dir = 0 (default) % or rotate x to left (up) by 1 if dir = 1 if nargin ;2, dir=0; end [m,n]=size(x); if m>1, if n == 1, col=1; elseif n>1, error('x must be a vector! break'); end % x is a column vectorelseif m == 1, if n == 1, y=x; return elseif n>1, col=0; % x is a row vector endend if dir==1, % rotate left or up if col==0, % row vector, rotate left y = [x(2:n) x(1)]; elseif col==1, y = [x(2:n); x(1)]; % rotate up end elseif dir==0, % default rotate right or down if col==0, y = [x(n) x(1:n-1)]; elseif col==1 % column vector y = [x(n); x(1:n-1)]; end end %================================================== function [L1,L2]=crossgens(X1,X2) % Usage:[L1,L2]=crossgens(X1,X2) s=randomize([2:12]')'; n1=min(s(1),s(11));n2=max(s(1),s(11)); X3=X1;X4=X2; for i=n1:n2, for j=1:13, if X2(i)==X3(j), X3(j)=0; end if X1(i)==X4(j),                          X4(j)=0; end end end j=13;k=13; for i=12:-1:2, if X3(i)~=0, j=j-1; t=X3(j);X3(j)=X3(i);X3(i)=t; end if X4(i)~=0, k=k-1; t=X4(k);X4(k)=X4(i);X4(i)=t; end end for i=n1:n2 X3(2+i-n1)=X2(i); X4(2+i-n1)=X1(i); end L1=X3;L2=X4;