用遺傳算法解決tsp問題

1、用遺傳算法解決用遺傳算法解決TSP問題問題設計思路：1.初始化城市距離采用以城市編號（ij=1代表北京，=2代表上海，=3代表天津，=4代表重慶，=5代表烏魯木齊）為矩陣行列標的方法，輸入任意兩個城市之間的距離，用矩陣city表示，矩陣中的元素city(ij)代表第i個城市與第j個城市間的距離。2.初始化種群通過rperm函數(shù)，生成一個一維隨機向量（是整數(shù)1，2，3，4，5的任意排列），然后將其賦給二維數(shù)組group的第一列，作為一個個

2、體。如此循環(huán)N次（本例生成了50個個體），生成了第一代種群，種群的每個個體代表一條路徑。3.計算適應度采用的適應度函數(shù)為個體巡回路徑的總長度的函數(shù)。具體為adapt(1i)=(5maxdisdis)(1)在式（1）中，adapt(1i)表示第i個個體的適應度函數(shù)，maxdis為城市間的最大距離，為4077kmdis為個體巡回路徑的總長度，這樣定義的適應度，當路經(jīng)越短時適應度值越大。在適應度值的基礎上，給出的計算個體期望復制數(shù)的表達式為a

3、daptnum(1i)=(Nadapt(1i)sumadapt)(2)其中，sumadapt為種群適應度之和。4.復制采用優(yōu)秀個體的大比例保護基礎上的隨機數(shù)復制法。具體做法為在生成下一代個體時，先將最大適應度對應的路徑個體以較大的比例復制到下一代，然后再用隨機數(shù)復制法生成下一代的其他個體。其中，有一個問題必須考慮，即若某一次生成的隨機數(shù)過大，結果能復制一個或極少個樣本。為了避免這一情況，采用了限制措施，即壓低了隨機數(shù)的上限。5.交叉采用

4、的方法為按步長的單點交叉，為隨機選擇一對樣本，再隨機選擇一個交叉點位置，按一定的步長進行交叉點的選擇。選擇一個步長而不是將其設為1，是因為若某一位置處的城市代碼因為進行了交叉而發(fā)生了改變，則其經(jīng)過該處的兩個距離都會改變。這種交叉兼有遺傳和變異兩方面的作用，因為若交叉點處的城市編號都相同，則對兩個個體而言交叉后樣本無變化，否則樣本有變化。6.變異方法為隨機兩點I，J的交互位置法。對于A=[12345678910]，若I=3J=8，則變異后

5、B=[12845673910]雖然是簡單的隨機兩點交互，但實際上已經(jīng)有40%的距離發(fā)生了改變。若用dij表示城市i與j之間的距離，則變異后與變異前樣本路徑的距離差為B23十B34B78十B89一A23十A34A78A89可見，隨機兩點交互足以產(chǎn)生新的模式樣本。較大地提高變異率就會產(chǎn)生大量的新樣本，全局最優(yōu)樣本出現(xiàn)的概率隨之提高。為了收斂到最優(yōu)解，借鑒模擬退火算法的思想，采取了變異率由很大逐漸衰減到較小的數(shù)量，這樣做也利于找到全局最優(yōu)解。

6、7.將復制，交叉，變異后得到的種群group1重新賦給group然后重復3，4，5，6步操作。直至滿足循環(huán)停止條件，即找到最優(yōu)路徑。maxadapt(1lun)=adaptnum(1i)%求本代最大適應值maxadaptloc=i%求最大適應值對應的個體號碼endifadaptnum(1i)numfk=1:5%由于針對5個城市，故每個個體有五個元素group1(ktcopy50)=group(ki)endendendend%%%%%%%