用遺傳算法解決tsp問(wèn)題

《用遺傳算法解決tsp問(wèn)題》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫(kù)。

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

2、徑。3.計(jì)算適應(yīng)度采用的適應(yīng)度函數(shù)為個(gè)體巡回路徑的總長(zhǎng)度的函數(shù)。具體為adapt(1,i)=(5*maxdis-dis)(1)在式（1）中，adapt(1,i)表示第i個(gè)個(gè)體的適應(yīng)度函數(shù)，maxdis為城市間的最大距離，為4077km,dis為個(gè)體巡回路徑的總長(zhǎng)度，這樣定義的適應(yīng)度，當(dāng)路經(jīng)越短時(shí)適應(yīng)度值越大。在適應(yīng)度值的基礎(chǔ)上，給出的計(jì)算個(gè)體期望復(fù)制數(shù)的表達(dá)式為adaptnum(1,i)=(N*adapt(1,i)/sumadapt)(2)其中，sumadapt為種群適應(yīng)度之和。4.復(fù)制采用優(yōu)秀個(gè)體的大比例保護(hù)

3、基礎(chǔ)上的隨機(jī)數(shù)復(fù)制法。具體做法為在生成下一代個(gè)體時(shí)，先將最大適應(yīng)度對(duì)應(yīng)的路徑個(gè)體以較大的比例復(fù)制到下一代，然后再用隨機(jī)數(shù)復(fù)制法生成下一代的其他個(gè)體。其中，有一個(gè)問(wèn)題必須考慮，即若某一次生成的隨機(jī)數(shù)過(guò)大，結(jié)果能復(fù)制一個(gè)或極少個(gè)樣本。為了避免這一情況，采用了限制措施，即壓低了隨機(jī)數(shù)的上限。5.交叉采用的方法為按步長(zhǎng)的單點(diǎn)交叉，為隨機(jī)選擇一對(duì)樣本，再隨機(jī)選擇一個(gè)交叉點(diǎn)位置，按一定的步長(zhǎng)進(jìn)行交叉點(diǎn)的選擇。選擇一個(gè)步長(zhǎng)而不是將其設(shè)為1，是因?yàn)槿裟骋晃恢锰幍某鞘写a因?yàn)檫M(jìn)行了交叉而發(fā)生了改變，則其經(jīng)過(guò)該處的兩個(gè)距離都會(huì)改變

4、。這種交叉兼有遺傳和變異兩方面的作用，因?yàn)槿艚徊纥c(diǎn)處的城市編號(hào)都相同，則對(duì)兩個(gè)個(gè)體而言交叉后樣本無(wú)變化，否則樣本有變化。6.變異方法為隨機(jī)兩點(diǎn)I，J的交互位置法。對(duì)于A=[12345678910]，若I=3,J=8，則變異后B=[12845673910]雖然是簡(jiǎn)單的隨機(jī)兩點(diǎn)交互，但實(shí)際上已經(jīng)有40%的距離發(fā)生了改變。若用dij表示城市i與j之間的距離，則變異后與變異前樣本路徑的距離差為B23十B34+B78十B89一A23十A34+A78+A89可見(jiàn)，隨機(jī)兩點(diǎn)交互足以產(chǎn)生新的模式樣本。較大地提高變異率就會(huì)產(chǎn)生大

5、量的新樣本，全局最優(yōu)樣本出現(xiàn)的概率隨之提高。為了收斂到最優(yōu)解，借鑒模擬退火算法的思想，采取了變異率由很大逐漸衰減到較小的數(shù)量，這樣做也利于找到全局最優(yōu)解。7.將復(fù)制，交叉，變異后得到的種群group1重新賦給group,然后重復(fù)3，4，5，6步操作。直至滿足循環(huán)停止條件，即找到最優(yōu)路徑。程序?qū)崿F(xiàn)：clcclearallcity=[0145315720873768;14530132625234077;1571326023003900;20872523230003358;37684077390033580]%初始化

6、城市距離maxdis=4077;%城市間最大距離N=50;%每一代種群中的個(gè)體數(shù)maxlun=100;%迭代次數(shù)設(shè)為100fori=1:Nttemp=randperm(5);%初始化種群，即隨機(jī)產(chǎn)生50種路徑，放在5行，N列的矩陣group中forj=1:5group(j,i)=ttemp(j);endendforlun=1:maxlun%迭代循環(huán)maxlun次sumadapt=0;%適度值之和maxadapt(1,lun)=0;%最大適度值初值minadapt(1,lun)=100;%最小適度值初值vipra

7、te=0.1;%最優(yōu)個(gè)體復(fù)制率copyrate=0.02;%復(fù)制率參數(shù)maxadaptloc=0;%最大適應(yīng)值對(duì)應(yīng)的個(gè)體號(hào)碼初值mindisiii(1,lun)=100000;%每一代的最憂路徑對(duì)應(yīng)的旅行距離總和初值fori=1:Ndis(1,i)=0;forj=1:4dis(1,i)=dis(1,i)+city(group(j,i),group(j+1,i));enddis(1,i)=dis(1,i)+city(group(1,i),group(5,i));%求一次旅行個(gè)體的總長(zhǎng)度adapt(1,i)=5*m

8、axdis-dis(1,i);%第i個(gè)個(gè)體的適應(yīng)度函數(shù)sumadapt=sumadapt+adapt(1,i);%適應(yīng)度函數(shù)總和ifdis(1,i)