旅行商問題的基因片段插入算法研究.pdf

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

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

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