1、實驗二 基于遺傳算法的T S P求解一、實驗目的掌握遺傳算法求解TSP問題的實現過程。二、實驗內容用遺傳算法求解TSR由于其任一可能解一一 一個合法的城市序列，即 n個城市的一個排列，都可以事先構 造出來。于是，我們就可以直接在解空間(所有合法的城市序列)中搜索最佳解。這正適合 用遺傳算法求解。三、實驗步驟(1)編碼路徑表示是表示旅程對應的基因編碼的最自然、最簡單的表示方法。例如，旅程(5 1 7894 623)可以直接表不'為(517894623),基于路徑表不'的編碼方法，要求個個體(即一條旅程)的染色體編碼中不允許有重復的基因碼，也就是說要滿足任一個城市必須而且只能訪問一

2、次的約束。(2)定義適應度函數我們將一個合法的城市序列s= (c1, c2,，cn)作為一個個體。這個序列中相鄰兩城市之間的距離之和的倒數就可作為相應個體s的適應度，從而適應度函數就是：1f (s) = Tj' d(G,Ci 1) i工例如，對于9個城市的TSP,我們用符號1、2、3、4、5、6、7、8、9代表相應的城市， 用這9個符號的序列表示可能解即染色體。然后進行遺傳操作用部分匹配交叉PMRT法：匹配操作要求隨機選取兩個交叉點，確定一個匹配段，根據兩個父個體中兩個交叉點之間的中間段給出的映射關系生成兩個子個體.例如，對下面兩個父個體的表示，隨機選擇兩個交義點P1: 1 2 3 4

3、 5 6 7 8 9o1:4 2 3 1 8 7 6 5 9P2: 4 5 2 1 8 7 6 9 302:1 8 2 4 5 6 7 9 3交叉方法：隨機選取染色體上兩個元，然后交換 它們的位置.例如：4 5 2 1 8 7 6 9 3交換后：4 5 6 1 8 7 2 9 3(3 )求解的Tsp問題的城市坐標如下：38.24 20.4239.57 26.1540.56 25.3236.26 23.1233.48 10.5437.5612.1938.4213.1137.5220.4441.239.1041.1713.0536.08-5.2138.4715.1338.1515.3537.511

4、5.1735.4914.3239.3619.5638.0924.3636.0923.0040.4413.5740.3314.1540.3714.2337.5722.56四、程序實現%基于遺傳算法的TSP問題求解%D是距離矩陣，n為種群個數，建議取為城市個數的12倍，%C為停止代數，遺傳到第C代時程序停止，C的具體取值視問題的規模和耗費的時間而定%m為適應值歸一化淘汰加速指數，最好取為1,2,3,4 ,不宜太大%alpha為淘汰保護指數，可取為01之間任意小數，取1時關閉保護功能，最好取為0.81.0%R為最短路徑，Rlength為路徑長度close all;clc;clear;%城市坐標cit

5、y=38.2420.42;39.57 26.15;40.56 25.32;36.26 23.12;33.48 10.54;37.56 12.19;38.42 13.11;37.52 20.44;41.23 9.10;41.17 13.05;36.08 -5.21;38.47 15.13;38.15 15.35;37.5115.17;35.49 14.32;39.36 19.56;38.09 24.36;36.09 23.00;40.44 13.57;40.33 14.15;40.37 14.23;37.57 22.56;'D=dist(city,city);%城市間距離矩陣n=100;

6、C=100;m=2;alpha=0.9;N,NN=size(D);farm=zeros(n,N);%用于存儲種群for i=1:nfarm(i,:)=randperm(N);%隨機生成初始種群endR=farm(1,:);%存儲最優種群len=zeros(n,1);%存儲路徑長度fitness=zeros(n,1);%存儲歸一化適應值counter=0;%記錄迭代次數while counter<Cfor i=1:nlen(i,1)=myLength(D,farm(i,:);% 計算路徑長度 end maxlen=max(len);minlen=min(len);fitness=fit(l

7、en,m,maxlen,minlen);% 計算歸一化適應值 rr=find(len=minlen);R=farm(rr(1,1),1);%更新最短路徑FARM=farm;%優勝劣汰，nn記錄了復制的個數 nn=0; for i=1:nnn=nn+1;FARM(nn,:)=farm(i,:);if fitness(i,1)>=alpha*randendaa,bb=size(FARM);% 交叉和變異 while aa<nif nn<=2nnper=randperm(2);elsennper=randperm(nn);endA=FARM(nnper(1),:);B=FARM(n

8、nper(2),:);A,B=intercross(A,B);FARM=FARM;A;B;aa,bb=size(FARM);endif aa>nFARM=FARM(1:n,:);%保持種群規模為 n endfarm=FARM;clear FARMcounter=counter+1;endRlength=len(16)% 最優路徑farm(16,:)%城市訪問次序newcood=city(:,farm(16,:);newcood=newcood newcood(:,1);%路徑是封閉連續的分段曲線plot(newcood(1,:),newcood(2,:),'o-');ti

9、tle('最優路徑圖')%計算歸一化適應值子程序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).Am; end%計算路徑的子程序 function len=myLength(D,p) N,NN=size(D);len=D(p(1,N),p(1,1);for j=1:N-1len=len+D(p(1,j),p(1,j+1);function x,y=exchange(x

10、,y)temp=x;x=y;y=temp;function a,b=intercross(a,b)L=length(a);if L<=10%確定交叉寬度W=1;elseif (L/10)-floor(L/10)>=rand&&L>10W=ceil(L/10);elseW=floor(L/10);endp=unidrnd(L-W+1);%隨機選擇交叉范圍，從 p到p+Wfor 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運行結果：counter =%迭代100次100Rlength =%最優路徑程度124.4678ans =%最優路徑次序Columns 1 through 10141731841195610Columns 11 through 2020222816121921713Columns 21 through 22115五、問題思考比較用Hopfield求解TSP問題和遺傳算法求解TS