改進的單親遺傳算法在TSP問題中的應用

摘 要:本文提出了求解旅行商問題(TSP)的一個改進的單親遺傳算法。首先，定義了距離系數的概念，并據此設計了一種新的貪心基因段交換算子;同時結合一個模擬退火和2OPT局部搜索技術來改進該算子;然后，在此基礎上提出了一個求解旅行商問題的一個新的單親遺傳算法。計算機仿真結果表明，該算法是有效的。

關鍵詞:單親遺傳算法TSP貪心基因段交換算子

中圖分類號:N1文獻標識碼:A文章編號:1674-098X(2011)07(a)-0231-01

旅行商問題(Traveling Salesman Problem，簡記為TSP)是一個典型的，易于描述卻難以處理的ＮＰ完全問題[1～2]。有效的解決TSP問題在可計算理論上有著重要的價值;同時TSP問題又是諸多領域內出現的多種復雜問題的集中概括和簡化形式;因此快速、有效地解決TSP問題有著極高的實際應用價值。目前，TSP問題因其典型性已成為各種啟發式的搜索、優化算法的間接比較標準。

遺傳算法是一種自適應全局優化概率搜索算法。該算法利用生物進化和遺傳思想實現優化過程，能夠有效地解決組合優化問題。但遺傳算法在這類問題的應用上，都是在一定發生概率的條件下，隨機地、沒有指導地迭代搜索;因此它們在為群體中的個體提供了進化機會的同時，也無可避免地產生了退化的可能。在某些情況下， 這種退化現象還相當明顯。由于不能確保群體的多樣性，容易出現早熟現象。

針對序號編碼GA的上述不足，單親遺傳算法(PGA)[3～4]采用序號編碼，不使用交叉算子，而代之以隱含序號編碼GA交叉算子功能的基因換位等遺傳算子，簡化了遺傳操作。實驗證明，單親遺傳算法(PGA)采用序號編碼，僅在一條染色體上進行遺傳操作，簡化了遺傳操作過程，提高了計算效率，一定程度上避免了早熟收斂。本文在單親遺傳算法的基礎上設計的貪心基因段交換算子充分利用了連接城市之間距離的信息，結合局部搜索技術，大大地提高了收斂速度，減少了信息損失。

1 單親遺傳算法

通過對多個TSP問題解的特征研究，我們發現每一個可行解中都存在著一些的局部較優路徑。而最優解是由多個局部較優路徑組合而成的。簡單的說，它們之間存在著相互沖突。最優解正是它們相互競爭又相互妥協的結果，也就是說，它們最大限度的依存產生了最優特性。因此，本文提出了貪心基因段交換算子，從父代個體中構造子代個體，但是盡量保留那些較好的基因片斷。

1.1 新的貪心基因段交換算子

PGA的基因換位算子是指按一定的概率P交換一條染色體中的某兩個(些)位置基因的過程。PGA的貪心基因段交換算子是指按一定的概率P把一條染色體中的某個(些)串中的基因在貪心思想的指導下重新首尾倒置連接的過程。被交換的子串及其長度是隨機選取的。

1.2 局部搜索算子

在旅行商問題中比較有名的用于局部搜索的算法就是2OPT(二段優化)[5～6]。它是通過路徑的每條邊和反轉子路徑來實現較優解的搜索的。2OPT不僅僅是一個變異操作。使用2OPT的思想基于它既能夠通過交換兩邊來進行變異，又能夠作為局部搜索算法，從而一定程度上解決基本遺傳算法的局部搜索能力差的缺陷。在本文中我們采取的是以模擬退火[5～6]控制降溫的速度進行2OPT操作。

1.3 算法步驟

算法1

(1)TSP問題初始化，確定迭代代數、種群規模和設置退出條件。

(2)設置初始迭代次數，判斷當前迭代次數是否小于設定的迭代次數。

(3)依次選取一個染色體進行如下操作:

1)對選擇染色體采用貪心基因段交換算子進行操作

2)以模擬退火控制降溫的速度對新構造的染色體的進行2OPT操作

3)返回3

4)是否達到設定的退出條件，沒達到返回2

2 實驗結果和討論

本文選取文獻http://www.iwr.uniheidelhergde/groups/vomopt/software/TSPL1B95的標準問題進行測試。本文中對這些問題連續進行了30次計算。計算機仿真結果見表1。

從表1可以看出本文算法在求解TSP問題上是有效的。在小規模TSP問題中本文算法在較小的種群規模和迭代次數就已經達到了問題的最優解，由于Att48問題的復雜性本文算法在100次迭代中獲得了26次最優解。

3 結語

本文在分析TSP問題的基礎上對傳統的遺傳算法和單親遺傳算法進行了比較，定義了好基因段和距離系數的概念，并據此設計了一種新的貪心基因段交換算子;同時結合一個模擬退火和2OPT局部搜索技術來改進該算子;然后，在此基礎上提出了一個求解旅行商問題的一個新的單親遺傳算法。計算機仿真結果表明，該算法是有效的。但對于用遺傳算法求解TSP，還存在許多問題有待于進一步地深入研究。比如如何更好的對大規模TSP問題進行求解。另外，本文算法也可以給其它優化問題的求解提供參考。

參考文獻

[1] D Applexgate，RBixby，V Chvatal，et al.Implementing the Dantzig- Fulkerman-Johnson Algorithm for Large Traveling Salesman Problems[J].MathematicalProgramming，2003，97(122):91～153.

[2]SJung，BRMoon.To ward Minimal Restriction of Genetic Codingand Crossovers for the 2-D Eunclidean TSP[J].IEEE Transon Evolutionary Computation，2002，6(6):557～565.

[3]李茂軍，童調生，羅隆誦.單親遺傳算法及其應用研究[J].湖南大學學報(自然科學版)，1998，25(6):56～59.

[4]陳俊紅，黃麗華.基于配電網絡規劃的優化算法的研究[J].微計算機信息，2006，4(3):293～295.

[5]Gunter Dueck，Tobias Scheuer.Threshold Accepting:A General Purpose Optimization Algorithm Appearing Superior to Simulated Annealing[J].Journal of Computation Physics，1990，90(1):161～175.