用遺傳算法解決TSP問題

1、.用遺傳算法解決TSP問題設(shè)計思路：1. 初始化城市距離采用以城市編號（i,j=1代表北京，=2代表上海，=3代表天津，=4代表重慶，=5代表烏魯木齊）為矩陣行列標的方法，輸入任意兩個城市之間的距離，用矩陣city表示，矩陣中的元素city(i,j)代表第i個城市與第j個城市間的距離。2. 初始化種群通過randperm函數(shù)，生成一個一維隨機向量（是整數(shù)1，2，3，4，5的任意排列），然后將其賦給二維數(shù)組group的第一列，作為一個個體。如此循環(huán)N次（本例生成了50個個體），生成了第一代種群，種群的每個個體代表一條路徑。3. 計算適應(yīng)度采用的適應(yīng)度函數(shù)為個體巡回路徑的總長度的函數(shù)。具體為ada

2、pt(1,i)=(5*maxdis-dis) (1)在式（1）中，adapt(1,i)表示第i個個體的適應(yīng)度函數(shù)，maxdis為城市間的最大距離，為4077km,dis為個體巡回路徑的總長度，這樣定義的適應(yīng)度，當(dāng)路經(jīng)越短時適應(yīng)度值越大。在適應(yīng)度值的基礎(chǔ)上，給出的計算個體期望復(fù)制數(shù)的表達式為 adaptnum(1,i)=(N* adapt(1,i)/ sumadapt) (2)其中，sumadapt為種群適應(yīng)度之和。4. 復(fù)制采用優(yōu)秀個體的大比例保護基礎(chǔ)上的隨機數(shù)復(fù)制法。具體做法為在生成下一代個體時，先將最大適應(yīng)度對應(yīng)的路徑個體以較大的比例復(fù)制到下一代，然后再用隨機數(shù)復(fù)制法生成下一代的其他個體。

3、其中，有一個問題必須考慮，即若某一次生成的隨機數(shù)過大，結(jié)果能復(fù)制一個或極少個樣本。為了避免這一情況，采用了限制措施，即壓低了隨機數(shù)的上限。5. 交叉 采用的方法為按步長的單點交叉，為隨機選擇一對樣本，再隨機選擇一個交叉點位置，按一定的步長進行交叉點的選擇。選擇一個步長而不是將其設(shè)為1，是因為若某一位置處的城市代碼因為進行了交叉而發(fā)生了改變，則其經(jīng)過該處的兩個距離都會改變。這種交叉兼有遺傳和變異兩方面的作用，因為若交叉點處的城市編號都相同，則對兩個個體而言交叉后樣本無變化，否則樣本有變化。6. 變異 方法為隨機兩點I，J的交互位置法。對于A= 1 2 3 4 5 6 7 8 9 10，若I= 3

4、, J=8，則變異后B= 1 2 8 4 5 6 7 3 9 10雖然是簡單的隨機兩點交互，但實際上已經(jīng)有40%的距離發(fā)生了改變。若用dij表示城市i與j之間的距離，則變異后與變異前樣本路徑的距離差為B23十B34 + B78十B89一A23十A34 + A78 + A89可見，隨機兩點交互足以產(chǎn)生新的模式樣本。較大地提高變異率就會產(chǎn)生大量的新樣本，全局最優(yōu)樣本出現(xiàn)的概率隨之提高。為了收斂到最優(yōu)解，借鑒模擬退火算法的思想，采取了變異率由很大逐漸衰減到較小的數(shù)量，這樣做也利于找到全局最優(yōu)解。7. 將復(fù)制，交叉，變異后得到的種群group1重新賦給group,然后重復(fù)3，4，5，6步操作。直至滿足

5、循環(huán)停止條件，即找到最優(yōu)路徑。程序?qū)崿F(xiàn)：clcclear allcity=0 1453 157 2087 3768; 1453 0 1326 2523 4077; 157 1326 0 2300 3900; 2087 2523 2300 0 3358; 3768 4077 3900 3358 0 %初始化城市距離maxdis=4077; %城市間最大距離N=50; %每一代種群中的個體數(shù)maxlun=100; %迭代次數(shù)設(shè)為100for i=1:N ttemp=randperm(5); %初始化種群，即隨機產(chǎn)生50種路徑，放在5行，N列的矩陣group中 for j=1:5group(j,i)

6、=ttemp(j); end endfor lun=1:maxlun %迭代循環(huán)maxlun次sumadapt=0; %適度值之和maxadapt(1,lun)=0; %最大適度值初值minadapt(1,lun)=100; %最小適度值初值viprate=0.1; %最優(yōu)個體復(fù)制率copyrate=0.02; %復(fù)制率參數(shù)maxadaptloc=0; %最大適應(yīng)值對應(yīng)的個體號碼初值 mindisiii(1,lun)=100000; %每一代的最憂路徑對應(yīng)的旅行距離總和初值for i=1:N dis(1,i)=0; for j=1:4dis(1,i)=dis(1,i)+city(group(j

7、,i),group(j+1,i); end dis(1,i)=dis(1,i)+city(group(1,i),group(5,i); %求一次旅行個體的總長度 adapt(1,i)=5*maxdis-dis(1,i); %第i個個體的適應(yīng)度函數(shù) sumadapt=sumadapt+adapt(1,i); %適應(yīng)度函數(shù)總和 if dis(1,i)maxadapt(1,lun) maxadapt(1,lun)=adaptnum(1,i); %求本代最大適應(yīng)值 maxadaptloc=i; %求最大適應(yīng)值對應(yīng)的個體號碼 end if adaptnum(1,i)minadapt(1,lun) min

8、adapt(1,lun)=adaptnum(1,i); %求本代最小適應(yīng)值 endend %.%復(fù)制操作tcopy50=0; %復(fù)制個數(shù)初值num=(maxadapt(1,lun)-copyrate-minadapt(1,lun)*rand(1)+minadapt(1,lun); %生成隨機數(shù)vipnum=viprate*N ; %N=50，確定最優(yōu)個體復(fù)制個數(shù)for tcopy50=1:vipnum %先復(fù)制vipnum個最優(yōu)個體至中間矩陣group1 for i=1:5 group1(i,tcopy50)=group(i,maxadaptloc); endendwhile tcopy50n

9、um&tcopy50N tcopy50=tcopy50+1; for k=1:5 %由于針對5個城市，故每個個體有五個元素 group1(k,tcopy50)=group(k,i); end endendend%交叉操作pc=0.5-(0.5-0.1)*(lun-1)/(maxlun-1); %交叉率pair=pc*N/2; %最多交叉對數(shù)step=2; %交叉步長取為2pairno=0; %當(dāng)前交叉過的個體數(shù)while pairnopair a=floor(N*rand(1)+1); %隨機產(chǎn)生兩個交叉?zhèn)€體，floor為向負無窮取整函數(shù) b=floor(N*rand(1)+1); marri

10、(1,a)=2; %參與交叉的個體標記初值 marri(1,b)=3; if marri(1,a)=1&marri(1,b)=1&a=b marri(1,a)=1; marri(1,b)=1; %參與交叉的個體標記為1 pairno=pairno+1; location=floor(5*rand(1)+1); %用隨機數(shù)確定個體中單交叉點位置 l1=0; l2=0; for i=location:step:5 %以下按步長step進行交叉 for j=1:5 %用for確定交叉位置 if group1(i,a)=group1(j,b) l1=j; end end for j=1:5 if gr

11、oup1(i,b)=group1(j,a) l2=j; end end temp=group1(i,a); group1(i,a)=group1(l2,a); group1(l2,a)=temp; temp=group1(i,b); group1(i,b)=group1(l1,b); group1(l1,b)=temp; end endend%變異操作 pb=0.02; %個體變異率 bnum=pb*N; %變異個體數(shù) for i=1:bnum %逐個取個體，隨機選擇位置進行變異 a1=floor(5*rand(1)+1); a2=floor(5*rand(1)+1); b=floor(N*r

12、and(1)+1); temp=group1(a1,b); group1(a1,b)=group1(a2,b); group1(a2,b)=temp; end %for i=1:N for j=1:5 group(j,i)=group1(j,i); %構(gòu)造經(jīng)過復(fù)制，交叉，變異后的矩陣，group,準備下次循環(huán) endendendgroupdisp(最優(yōu)路徑為：)for i=1:5 switch group(i,1) case 1,disp(北京) case 2,disp(上海) case 3,disp(天津) case 4,disp(重慶) otherwise,disp(烏魯木齊) %用文字列

13、出最優(yōu)路徑 endenddisp(更多精彩，即將出現(xiàn)，請稍等.)figure(1);lun=1:1:50;mindis=mindisiii(1,lun);plot(lun,mindis);grid on;figure(2);worldmap(china,patch);for i=1:5 switch group(i,1) case 1,x(1,i)=0.12;y(1,i)=0.72; case 2,x(1,i)=0.23;y(1,i)=0.54; %在地圖中定出五個城市的坐標 case 3,x(1,i)=0.15;y(1,i)=0.7; case 4,x(1,i)=0;y(1,i)=0.53; otherwise,x(1,i)=-0.2;y(1,i)=0.73; endendfor i=1:4 u(1,i+1)=x(1,i); v(1,i+1)=y(1,i);endu(1,1)=x(1,5);v(1,1)=y(1,5);for i=1:5 u(1,i)=