一種求解旅行商問題的演化算法研究

許 沖,鐘 瑋,劉欣欣

（閩南師范大學計算機學院,福建漳州363000）

1948 年由美國蘭德公司推動的TSP（Traveling Salesman Problem）是一個較古老的巡回旅行商問題[1]，成為近代組合優化領域的一個典型難題，已被證明為NP 難題.TSP 描述為在一個加權無向圖中，尋找一個邊的權值之和最小的Hamilton圈.

隨著TSP的研究和利用的不斷擴展，圖的復雜程度不斷加大，導致TSP求解的搜索空間不斷加大.諸多學者也提出了多種不同的求解TSP 問題的算法.其中，湖水能量算法[2]就是一種高效的求解算法，但其缺點在于找到最優解的概率較低.郭濤算法[3]（GT）是一種改進遺傳演化算法，被證明是一種效率很高的算法.但是，隨著圖的規模和復雜度增大，GT算法找到最優解的概率不斷下降.蔡之華[4]，謝大同[5]等給出了一種對郭濤算法或其Inver-over算子[3]進行改進的求解TSP問題的演化算法，經過實驗證明其找到最優解的能力雖有改善，但仍不夠理想，其在實例CHN144上找到最優解的概率僅為0.7.本文采用粒子群[6]的基因片段插入[7-8]與Inver-over算子結合，隨機的在粒子中插入其他粒子的片段，以達到擴大粒子搜索范圍的作用，從而防止算法解的早熟.

1 新的演化算法

為方便算法描述，先對算法中使用的參數、符號和數據作以下說明.

給定n 個城市{1,2,…,n}以及對應的坐標值，記兩個城市i 和j 之間的距離d(i,j).用c1c2…cn來表示TSP的一個解的路徑（其中1 ≤ci≤n,且c1c2…cn互不相同），并稱c1c2…cn為一個個體p，一組個體的集合稱為P ，第i 個個體稱為Pi. c1c2…cn個體的長度定義為d(c1,c2)+ d(c2,c3)+ …+ d(cn-1,cn)+ d(cn,c1). 設1 ≤t ≤n - 1,長度為l 的路徑cici+1…ci+t稱為個體c1c2…cn的一個起始位……