基于malab的遺傳算法求解旅行商問題

基于malab的遺傳算法求解旅行商問題

“旅行商問題”可以簡單地描述為：n個(gè)城市中的一個(gè)從遠(yuǎn)處出發(fā)，n個(gè)城市中的另一個(gè)離開，回到原起點(diǎn)。每個(gè)可能路徑都可能最長的路徑長度的確定點(diǎn)是c={c1、b2、s=}。這兩個(gè)城市之間的距離為d（ci，j）z=，其中ci、jc（1）i，jn）。城市序列（ci（1），ci（2），其中i（1），i（2），i（n）是1、2和它是n的完整排列。該問題是一個(gè)相當(dāng)古老的優(yōu)化問題,早在1759年Euler就研究過,同時(shí)TSP問題已被證實(shí)是一個(gè)NP難解問題.在過去的10年中,出現(xiàn)了一些逼近最優(yōu)解的算法:最近鄰居、貪婪算法、最近插入、最遠(yuǎn)插入、雙最小生成樹、帶解法、空間充填曲線及由Karp,Litke,Christofides等開發(fā)的算法.但因這些方法的局限性,故需要尋找一些啟發(fā)式算法.20世紀(jì)70年代初期由美國密執(zhí)根大學(xué)的Holland教授發(fā)展起來的遺傳算法,是一種求解問題的高效并行全局搜索方法,能夠解決復(fù)雜的全局優(yōu)化問題.解決TSP問題也成為遺傳算法界的一個(gè)目標(biāo).1采用遺傳算法求解tsp1.1基于遺傳算法的群體分析遺傳算法是通過借鑒生物界自然選擇和自然遺傳機(jī)制而產(chǎn)生的一種計(jì)算方法,與其他的優(yōu)化算法一樣,遺傳算法也是一種迭代算法.從選定的初始解出發(fā),通過不斷地迭代,逐步改進(jìn)當(dāng)前解,直到最后搜索到最優(yōu)解或滿意解.其迭代過程是從一組初始解(群體)出發(fā),采用類似于自然選擇和有性繁殖的方法,在繼承原有優(yōu)良基因的基礎(chǔ)上生成具有更好性能的下一代解的群體.遺傳算法的運(yùn)算過程為:對給定問題,給出變量的編碼方法,定義適應(yīng)度函數(shù).①初始化.令t=0,給出正整數(shù)T(最大迭代次數(shù)),交叉概率pc及變異概率pm,隨機(jī)生成M個(gè)個(gè)體作為初始群體p(0);②個(gè)體評價(jià).計(jì)算p(t)中各個(gè)體的適應(yīng)度;③選擇.對群體p(t)進(jìn)行選擇操作,得到中間群體;④交叉.把交叉操作作用于中間群體;⑤變異.把變異操作作用于交叉之后所得到的群體,則得到第(t+1)代群體p(t+1);⑥若t<T,則令t=t+1,轉(zhuǎn)②;若t≤T,則以進(jìn)化過程中所得到的具有最大適應(yīng)度的個(gè)體作為最優(yōu)解,運(yùn)算停止.算法流程圖如圖1所示.1.2matlab的編碼對于需要解決的TSP問題來說,其n個(gè)城市之間的距離實(shí)質(zhì)上構(gòu)成了一個(gè)n×n的矩陣,同時(shí)遺傳算法的諸多算子(如選擇、交叉、變異),都是針對所謂染色體進(jìn)行的,而染色體實(shí)質(zhì)上是一個(gè)向量,可將其看成一個(gè)1×n的矩陣,因此這些算子實(shí)質(zhì)上是一些矩陣運(yùn)算,而MATLAB的基本數(shù)據(jù)單元就是一個(gè)維數(shù)不加限制的矩陣,故用它編寫程序,比用其它高級語言更簡單、靈活、快捷.1在初始組中，需要確定變量的編碼方法和適應(yīng)性函數(shù)。在遺傳計(jì)算法領(lǐng)域，有一個(gè)共同的共識：旅行的二進(jìn)制表達(dá)不適用于斯普。在這里，作為算法編碼的首字段序列，i1，i2，…，i是{1，2，…，n}的完整排列。由于所期望的是優(yōu)化目標(biāo)函數(shù)的最小值，因此使用哈密頓圈長度的平均值作為適應(yīng)性函數(shù)。此外，有必要分配變量，如規(guī)模大小、最大迭代數(shù)、交叉概率和變異概率，以便隨機(jī)生成規(guī)模大小m。染色長度城市號中的dap方案如下2計(jì)算個(gè)體的適應(yīng)性，即哈密頓r組的哈密頓r長度的平均值，對應(yīng)于組的哈密頓r組31選擇排列中所有個(gè)體的適應(yīng)性總和；2計(jì)算每個(gè)個(gè)體的相對適應(yīng)性，即每個(gè)個(gè)體在選擇和操作中選擇的概率。3模擬賭博游戲的操作確定每個(gè)單元的選擇頻率，并利用中間群體41對于選擇操作中的中間群體，1使用交叉概率pc從中間群體中隨機(jī)選擇需要交叉的個(gè)體，并隨機(jī)匹配這些個(gè)體。21num-1之間生成兩個(gè)隨機(jī)數(shù)k，l，表示交叉點(diǎn)的位置。3對于k-l所對應(yīng)的兩個(gè)個(gè)體，它們相互對應(yīng)地交換k-l所對應(yīng)的l位數(shù)字51可執(zhí)行交叉操作后的群體操作的操作方法是：首先，在1到num之間生成兩個(gè)隨機(jī)數(shù)g和h，這兩個(gè)數(shù)代表了變異點(diǎn)的位置。最后，將隨機(jī)概率g和h對應(yīng)的個(gè)體隨機(jī)替換2與用遺傳算法求解tsp的結(jié)果比較為檢驗(yàn)該算法的實(shí)際應(yīng)用效果,文中以16,22,24,48,70,101個(gè)城市為例(這6個(gè)TSP實(shí)例,彈性網(wǎng)絡(luò)算法的計(jì)算結(jié)果及最優(yōu)解見參考文獻(xiàn)),將該算法得到的結(jié)果與用彈性網(wǎng)絡(luò)算法得到的結(jié)果進(jìn)行了比較,如表1所示.為了更好地說明遺傳算法在求解TSP問題中良好的全局搜索能力,文中以求解101個(gè)城市為例進(jìn)行運(yùn)算.通過運(yùn)算可以發(fā)現(xiàn),隨著迭代次數(shù)的增加,最佳個(gè)體的適應(yīng)度函數(shù)值逐步增加,最后收斂于一個(gè)相對穩(wěn)定值.用遺傳算法求解得到的101個(gè)城市的遍歷圖,如圖2所示.從表1,圖2中可以看出,遺傳算法有較好的全局最優(yōu)解的求解能力.3交叉概率pc/pc間關(guān)系在算法實(shí)施過程中,M,T,pc,pm等參數(shù)值的設(shè)定對于問題能否找到滿意解起著非常重要的作用.如果M,T值太小,則不容易找到最優(yōu)解;反之,則計(jì)算時(shí)間長.對于交叉概率pc來說,如果取值過大,則會破壞以前遺傳的結(jié)果,因而pc不能取得太大.