改進(jìn)遺傳算法在tsp問題中的應(yīng)用

《改進(jìn)遺傳算法在tsp問題中的應(yīng)用》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在學(xué)術(shù)論文-天天文庫。

1、改進(jìn)遺傳算法在TSP問題中的應(yīng)用　　摘要：旅行商問題是典型的NP組合優(yōu)化問題。提出一種旅行商問題求解應(yīng)用上的改進(jìn)遺傳算法。引入貪心算法優(yōu)化初始種群，在輪盤賭選擇基礎(chǔ)上，融入最優(yōu)保存策略和摻雜算子進(jìn)行選擇操作，以保證群體的多樣性；基于兩點(diǎn)三段隨機(jī)交叉算子優(yōu)化交叉結(jié)果，基于啟發(fā)式倒位變異算子提高算法的收斂速度；給出了求解旅行商問題系統(tǒng)的體系結(jié)構(gòu)。實(shí)驗(yàn)結(jié)果表明，改進(jìn)的遺傳算法具有更好的尋優(yōu)能力?！　￡P(guān)鍵詞：旅行商問題；遺傳算法；貪心算法；組合優(yōu)化；體系結(jié)構(gòu)　　DOIDOI：10.11907/rjdk.162168　　中圖分類號(hào)：TP319　　

2、文獻(xiàn)標(biāo)識(shí)碼：A文章編號(hào)：1672-7800（2016）012-0127-03　　0引言　　旅行商問題（TravelingSalesman9Problem，TSP）是典型的NP組合優(yōu)化問題，具有重要的理論價(jià)值和良好的應(yīng)用背景，諸如半導(dǎo)體電路設(shè)計(jì)、公路網(wǎng)絡(luò)建設(shè)、飛機(jī)航線安排、連鎖店貨物配送路線等，通過TSP建模均可解決。求解TSP問題方法包括精確算法、近似算法和智能算法。文獻(xiàn)[1]采用遺傳算法基礎(chǔ)上派生出來的分布估計(jì)算法求解TSP問題，并將種群進(jìn)行分級(jí)處理，根據(jù)種群級(jí)別高低分別采用不同的策略進(jìn)行交叉和變異操作；文獻(xiàn)[2]在基本遺傳算法基礎(chǔ)上

3、引入外部最優(yōu)個(gè)體集，以增加群體多樣性，改善局部搜索能力，采用遞歸分治策略將遺傳算法并行化；文獻(xiàn)[3]采用改進(jìn)的遺傳算法，按種群中個(gè)體適應(yīng)度高低采用不同的交叉和變異算子；文獻(xiàn)[4]提出一種改進(jìn)的遺傳算法，動(dòng)態(tài)調(diào)整交叉和變異概率，以降低染色體近親繁殖可能，有效控制了進(jìn)化過程；文獻(xiàn)[5]結(jié)合遺傳算法和模擬退火算法，提出了一種改進(jìn)的模擬退火遺傳算法；文獻(xiàn)[6]將蟻群算法和遺傳算法融合，經(jīng)過蟻群算法迭代獲得初始種群解集，再采用改進(jìn)的遺傳算法尋優(yōu)；文獻(xiàn)[7]在基本遺傳算法基礎(chǔ)上，提出改進(jìn)型多宇宙量子交叉算子，利用不同宇宙間的信息交流提高算法的搜索效

4、率?！　∩鲜銮蠼釺SP問題的研究效果很好，但都沒有提到有關(guān)求解系統(tǒng)的設(shè)計(jì)問題。本文不但對(duì)基本遺傳算法求解TSP問題進(jìn)行分析并加以改進(jìn)，還給出了求解TSP問題系統(tǒng)的體系結(jié)構(gòu)。實(shí)驗(yàn)結(jié)果表明，改進(jìn)的遺傳算法具有更可靠的尋優(yōu)能力，求解系統(tǒng)實(shí)用性較好?！　?基本問題描述　　1.1TSP問題　　TSP問題可描述為：一個(gè)旅行商要到n個(gè)城市推銷商品，從一個(gè)城市出發(fā)，走一遍余下的n-1個(gè)城市再回到起點(diǎn)，要求所走的路程最短，即尋找一條巡回路徑C=（c1，c2，...，cn），使得下列目標(biāo)函數(shù)最小[8]：　　1.2遺傳算法原理及應(yīng)用9　　遺傳算法是一種隨機(jī)并

5、行搜索算法，其基本思想是：首先對(duì)個(gè)體編碼，生成初始種群，然后開始進(jìn)化，用適應(yīng)度函數(shù)來判斷個(gè)體優(yōu)劣，優(yōu)秀的個(gè)體將獲得更多的選擇、交叉和變異機(jī)會(huì)，一直進(jìn)化到滿足迭代的終止條件，從而得到最優(yōu)解。該算法具有全局尋優(yōu)能力強(qiáng)、計(jì)算過程簡(jiǎn)單、處理并行性、魯棒性等優(yōu)點(diǎn)，在組合優(yōu)化問題、模式識(shí)別、圖像處理、調(diào)度問題等領(lǐng)域得到了廣泛應(yīng)用[9]?！　?應(yīng)用遺傳算法求解TSP問題　　遺傳算法已經(jīng)廣泛應(yīng)用于求解組合化問題的近似最優(yōu)解方面，TSP問題是典型的組合優(yōu)化問題。應(yīng)用遺傳算法求解TSP問題基本方法如下：（1）確定編碼方式。用遺傳算法求解TSP問題常用的編碼

6、方式有二進(jìn)制表示、順序表示、路徑表示、邊表示等，其中路徑表示因自然、直觀且易于加入啟發(fā)式信息，是應(yīng)用最多的一種表示策略。（2）初始化種群。隨機(jī)產(chǎn)生初始個(gè)體，構(gòu)成指定規(guī)模的初始種群，是應(yīng)用遺傳算法求解TSP問題的常用方法。（3）計(jì)算種群中每個(gè)個(gè)體的適應(yīng)度值。在TSP問題中，目標(biāo)函數(shù)f（C）=∑n-1i=1d（ci，ci+1）+d（cn，c1）是路徑總長(zhǎng)度，適應(yīng)度函數(shù)通常取目標(biāo)函數(shù)的倒數(shù)，即F（C）=1/f（C）。（4）選擇算子。目前常用的選擇算子有比例選擇、最優(yōu)保存策略、基于聯(lián)賽的選擇等。（5）交叉算子。按照某一交叉概率pc選擇若干父體并

7、進(jìn)行配對(duì)。針對(duì)路徑表示的TSP遺傳算法，常用的交叉算子有部分匹配交叉、貪婪交叉、次序交叉和循環(huán)交叉等。（6）變異算子。按照某一變異概率pm隨機(jī)確定變異個(gè)體，常用的變異算子包括倒位變異、插入變異、移位變異和2-opt變異等。（7）迭代終止條件。若算法滿足迭代的終止條件，則停止迭代；否則轉(zhuǎn)至第（3）步，利用適應(yīng)度函數(shù)重新計(jì)算每個(gè)個(gè)體的適應(yīng)度值?；具z傳算法存在易陷入局部最優(yōu)、收斂速度慢和優(yōu)化精度低等缺點(diǎn)。改進(jìn)遺傳算法的目標(biāo)是在提高算法收斂速度的同時(shí)確保種群多樣性，從而使尋優(yōu)結(jié)果接近最優(yōu)解[10]?！　?求解TSP問題的改進(jìn)遺傳算法9　　3.

8、1個(gè)體路徑編碼表示　　路徑表示法是TSP問題最直接的表示方法，本文算法采用此方法進(jìn)行個(gè)體編碼，每個(gè)個(gè)體就是一次訪問城市的順序排列。編碼串（x1，x2，...，xn）表示從城市x1出發(fā)，依次經(jīng)過城市x2，x3