旅行商問(wèn)題的基因片段插入算法研究.pdf

1、旅行商問(wèn)題（Traveling Salesman Problem，TSP）又稱為推銷員問(wèn)題、貨郎擔(dān)問(wèn)題，簡(jiǎn)稱為TSP問(wèn)題。該問(wèn)題是在尋求單一旅行者由起點(diǎn)出發(fā)，通過(guò)所有給定的需求點(diǎn)之后，再回到原點(diǎn)的最小路徑成本。如何找到在拜訪每個(gè)地方一次后再回到起點(diǎn)的最短路徑，規(guī)則雖然簡(jiǎn)單，但在地點(diǎn)數(shù)目增多后求解的時(shí)間迅速的增加。多年來(lái)全球數(shù)學(xué)家絞盡腦汁，試圖找到一個(gè)高效的算法--能快速找到最優(yōu)或近似最優(yōu)的解。
　　近幾年，研究人員試圖運(yùn)用各種方法

2、對(duì)TSP進(jìn)行求解，但是，由于對(duì)TSP特性的認(rèn)識(shí)的加深，試圖使用精確算法求解TSP的研究基本銷聲匿跡，取而代之的是各種近似方法；試圖使用單一方法求解TSP問(wèn)題的研究在減少，而使用多種方法結(jié)合的研究逐漸占據(jù)研究的主流。
　　針對(duì)該問(wèn)題，本文研究不同的算法求解旅行商問(wèn)題的優(yōu)缺點(diǎn)，根據(jù)此引入了一種新的運(yùn)算方式：基因片段插入。同時(shí)借鑒于粒子群優(yōu)化算法的思想和郭濤算法，將分別考慮三種方法求解旅行商問(wèn)題的新算法。
　　首先是將基因片段插入

3、方法和類粒子群優(yōu)化算法相結(jié)合，通過(guò)若干次的迭代,可得到最優(yōu)解或近似最優(yōu)解。
　　其次是基于基因片段插入的旅行商問(wèn)題的演化算法研究，隨機(jī)從其它個(gè)體選取一個(gè)基因片段，插入到當(dāng)前進(jìn)化的個(gè)體。通過(guò)若干次的迭代,可得到最優(yōu)解或近似最優(yōu)解。實(shí)驗(yàn)表明，此方法優(yōu)于前面的算法。
　　最后是將基因片段插入方法和郭濤算法相結(jié)合，對(duì)某個(gè)個(gè)體進(jìn)行進(jìn)化時(shí)，先利用郭濤算法對(duì)此個(gè)體中的基因片段進(jìn)行翻轉(zhuǎn)，后隨機(jī)從其它個(gè)體選取一個(gè)基因片段，正向或反向插入到當(dāng)前