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代表所选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)=al23.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 134.对应：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 139. 6 12 3 5 6 8 5 6 3 1 8 5 6 3 3 2 1 140.交叉后为：41.8 14 2 13 8 6 3 2 5 1 8 5 6 3 3 2 1 142. 6 12 3 5 6 8 5 6 3 7 3 4 3 2 4 2 2 143.变异过程：本文采用均匀多点变异。

类似交叉操作中选择父代的过程，在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 147.变异后：48.8 14 2 13 10 6 3 2 2 7 3 4 5 2 4 1 2 149.反grefenstette编码：交叉和变异都是在grefenstette编码之后进行的，为了循环操作50.和返回最终结果，必须逆grefenstette编码过程，将编码恢复到自然编码。

51.循环操作：判断是否满足设定的带数xzome，否，则跳入适应度f的计算；是，结束遗传52.操作，跳出。

53.54.55.56.matlab 代码57.58.59.60.distTSP.txt61.0 6 18 4 862.7 0 17 3 763. 4 4 0 4 564.20 19 24 0 2265.8 8 16 6 066.%GATSP.m67.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 genepool76.gpool=zeros(ngpool,N+1); % gene pool77.for i=1:ngpool, % intialize gene pool78.gpool(i,:)=[1 randomize([2:N]')' 1];79.for j=1:i-180.while gpool(i,:)==gpool(j,:)81.gpool(i,:)=[1 randomize([2:N]')' 1];82.end83.end84.end85.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.end93.% record current best solution94.[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>costmin108.resultcost=costmin;109.resulttour=tourmin;110.resultincrease=increase-1;111.end112.for i=1:ngpool,113.cost(i)=sum(diag(distance(gpool(i,:)',rshift(gpool(i,:))')));114.end115.% record current best solution116.[costmin,idx]=min(cost);117.tourmin=gpool(idx,:);118.%==============119.% copy gens in th gpool according to the probility ratio120.% >1.1 copy twice121.% >=0.9 copy once122.% ;0.9 remove123.[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.1131.copynumbers=copynumbers+1;132.end133.if cprobilities(i) <0.9134.removenumbers=removenumbers+1;135.end136.end137.copygpool=min(copynumbers,removenumbers);138.for i=1:copygpool139.for j=ngpool:-1:2*i+2 gpool(j,:)=gpool(j-1,:);140.end141.gpool(2*i+1,:)=gpool(i,:);142.end143.if copygpool==0144.gpool(ngpool,:)=gpool(1,:);145.end146.%=========147.%when genaration is more than 50,or the patterns in a couple are too close,do mutation 148.for i=1:ngpool/2149.%150.sameidx=[gpool(2*i-1,:)==gpool(2*i,:)];151.diffidx=find(sameidx==0);152.if length(diffidx)<=2153.gpool(2*i,:)=[1 randomize([2:12]')' 1];154.end155.end156.%===========157.%cross gens in couples158.for i=1:ngpool/2159.[gpool(2*i-1,:),gpool(2*i,:)]=crossgens(gpool(2*i-1,:),gpool(2*i,:));160.end161.162.for i=1:ngpool,163.cost(i)=sum(diag(distance(gpool(i,:)',rshift(gpool(i,:))')));164.end165.% record current best solution166.[costmin,idx]=min(cost);167.tourmin=gpool(idx,:);168.disp([num2str(increase) 'minmum trip length = ' num2str(costmin)])169.end170.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 matrix180.% rowcol: if =0 or omitted, row order (default)181.% if = 1, column order182.183.rand('state',sum(100*clock))184.if nargin == 1,185.rowcol=0;186.end187.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.end199.%===================================================== 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 = 1204.if nargin ;2, dir=0; end205.[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.return214.elseif n>1,215.col=0; % x is a row vector endend216.if dir==1, % rotate left or up217.if col==0, % row vector, rotate left218.y = [x(2:n) x(1)];219.elseif col==1,。