基于局部搜索機制快速求解TSP問題的自適應遺傳算法

夏 凱，戴文戰

（1.浙江理工大學機械與自動控制學院，杭州310018；2.浙江工商大學信息與電子工程學院，杭州310018）

基于局部搜索機制快速求解TSP問題的自適應遺傳算法

夏 凱1，戴文戰2

（1.浙江理工大學機械與自動控制學院，杭州310018；2.浙江工商大學信息與電子工程學院，杭州310018）

提出了一種基于局部搜索機制快速求解TSP的遺傳算法?；诰植克阉鳈C制，自適應地將標準遺傳算法與局部啟發式算法結合，使得局部啟發式算法只在有效改善種群個體質量的情況下才允許執行，有效地避免了因局部搜索次數過多而引起的陷入局部最優和計算負擔過重現象的發生。仿真結果表明，該算法具有較強的全局優化能力及較快的收斂速度，在求解TSP問題時有較高效率。

局部搜索機制；自適應；遺傳算法；旅行商問題

0 引 言

旅行商問題（traveling salesman problem，TSP）一直具有重要理論研究價值和廣泛工程應用價值。精確算法如分支定界法、動態規劃法等，在問題規模較小時能到得到最優解，但算法的時間復雜度和空間復雜度都會隨著問題規模的增加而成指數增長。由于近似算法能夠在合理的時間和存儲空間范圍內求出問題的最優解或近似最優解，因而眾多學者對其進行了大量的研究。遺傳算法（genetic algorithm，GA）因其具有較強的全局搜索能力、高效的群體搜索策略以及與目標梯度信息無關等優點，是求解TSP問題的一種理想方法。

GA中一個較難解決的問題是如何較快地找到最優解并防止“早熟”收斂問題。許多研究者提出了各種改進方法來提高GA的搜索性能。彭丹平等［1］從相似性的思想出發，按適應值相似性將群體分級，在不同的級內采用不同的操作，產生數目不等的新解并利用加速算子使其更接近局部極小值，較好地解決了群體多樣性與收斂性的矛盾。姜昌華［2］等結合遺傳算法和2-opt領域搜索優化技術，提出了K近鄰點集以縮減搜索空間從而加快求解速度。楊輝［3］等提出了構建基因庫與遺傳算法相結合的算法，利用基因庫實現初始種群的優生和指導種群的進化方向，并用全局搜索算子和局部搜索算子增強GA的“探測”和“開發”能力，加快了算法的收斂速度和尋優能力。Ren等［4］構建了混沌搜索算法，并結合單親遺傳算法和貪婪局部搜索算法求解旅行商問題，能較好逃離局部最優，獲得全局最優或近似最優解。Yang等［5］引入了遷移機制，當進化中的種群多樣性缺失時，通過遷移機制，將種群中的一部分個體用優良的個體替代。Hua等［6］提出了一種自適應調整控制參數的遺傳算法，自適應的調整交叉和變異概率，并與2-opt算法相結合。許多研究結果表明將遺傳算法與局部啟發式算法結合起來可以有效地提高求解大型TSP問題的質量，利用遺傳算法自適應的隨機搜索性能“勘探”潛在的最優空間，而局部啟發式搜索則在這些子空間進行深入“開發”。這類算法在提高收斂速度和尋求全局最優之間找到一個平衡點［7］。文獻［1-6］雖然將局部搜索算法加入到遺傳算中，但往往導致過多的局部搜索而陷入局部最優和造成計算時間上的不必要浪費。

針對這個問題，提出了一種基于局部搜索機制的自適應遺傳算法（adaptive genetic algorithm，AGA）。在算法中，局部搜索是根據種群個體適應度值標準偏差和種群個體的平均巡回路徑長度的變化情況自適應地與全局搜索相結合，局部搜索只在能有效改善種群個體質量的情況下才允許執行，因而能有效避免陷入局部最優，減輕了計算負擔。

1 TSP問題模型

TSP模型可簡單描述如下：

假設一名旅行商需要訪問n個城市且每個城市的坐標為（xi，yi），（i∈［1，n］），城市i與城市j之間的歐拉距離是：

旅行商需要找到一條哈密頓回路，即從任意一城市出發，路途中經過每個城市當且僅當一次然后回到原出發點，使其路徑長度最短。即：

此外，TSP問題模型也可以從圖論的角度來描述。給出有向圖G=（V，E），圖中每條邊e∈E，有一個非負的權值ω（e），目的是在有向圖G上發現一個具有最小權值和的哈密頓回路［8］。如下：

2 局部搜索策略

本研究采用了2-opt鄰域搜索優化技術作為與GA結合的局部搜索算法。利用GA自適應性的隨機搜索性能勘探潛在的最優解空間，2-opt在這些子空間內進行深入搜索。按照特定的適應性機制，將GA與2-opt局部搜索算法自適應地結合，能較好地解決提高收斂速度和尋求全局最優之間的矛盾，使它們達到平衡。其基本思想為：局部搜索算法只在需要的時候才允許執行。提出了以下適應性機制，確保只在局部搜索算法能有效地改善種群個體解的質量的前提下才允許執行。

2.1 局部搜索機制

局部搜索只在能提供給種群進化有用的信息時才被執行。一開始種群個體適應度值標準偏差σ和種群個體的平均巡回路徑距離ρ都比較大，但是隨著種群的不斷進化，最后種群中的個體非常相似或趨于一致，此時σ很小或趨于0，ρ也變得很小。

偏差σ的計算公式如下：

其中n為種群中個體的總數，xi為種群中第i個個體的適應度為種群中所有個體適應度的平均值。為了跟蹤σ的變化，本文定義V來表示兩個連續代之間σ的變化率。V的計算公式如下：

其中σ（i）表示第i代種群個體適應度值的標準偏差。如果V＞1，則說明種群中第i代種群中個體適應度值偏離種群平均適應度值的程度比第i-1代大，即種群中的個體適應度分布比較分散。

同時，為了跟蹤ρ的變化，本文定義W來表示連續兩代之間ρ的變化率。W的計算公式如下：

其中ρ（i）表示第i代種群個體所代表的巡回路徑距離平均值。如果W＞1，則說明第i代種群中個體的平均距離比第i-1代大，即種群中個體的平均個體解質量比前代差。

如果同時滿足V＞1且W＞1，則表明第i代種群個體解的質量比第i-1代差，說明算法正在探索新的解空間，這些解子空間可能是通過遺傳算法的交叉或變異算子產生，由于新產生的個體的適應度值與種群中剩余個體相比相差較大，這樣會導致種群的標準偏差值增加和個體平均適應度值減少，此時需要進一步對新的解子空間進行開發，則啟用局部搜索。

當種群中最優個體適應度值fbest與個體平均適應度值fave的偏差率φ很小時，此時，局部搜索不但不能有效的改善解的質量，而且會額外的增加計算時間，則結束局部搜索。偏差率的參考值為1%。

φ的計算公式如下：

3 算法流程

算法流程描述如下：

Step1 遺傳代數計數器初始化：t←0。

Step2 基于基因庫初始化群體P（t），對P（t）進行預處理并計算個體適應度。

Step3 采用賭輪轉方式選擇個體，同時采用精英保留策略，即保存當前群體中的最優個體。

Step4 對種群個體進行雜交、變異操作，即進行標準遺傳算法操作，并計算種群個體適應值。

Step5 判斷是否應該執行局部搜索。如果滿足V＞1，W＞1且φ＞1%，轉到Step6執行，否則轉到Step3。

Step6 局部搜索優化。隨機從種群中選擇一定比例的個體，對這些個體進行局部搜索優化，將優化后的個體替代原先的個體。

Step7 終止條件判斷。若t總設定的進化迭代次數，則t=t+1，轉向Step3。否則，輸出最優結果，算法結束。

4 仿真研究

本文針對城市規模分別為31［1］和50［4］的典型TSP問題，用本算法在matlab7.0軟件上進行仿真研究。初始化控制參數：種群個體數均設為30，最大迭代次數分別設為100和500，交叉概率均設為0.9，變異概率均設為0.01。每組實驗均分別進行10次，得出的城市規模為31的最優路徑如圖1所示。最短路徑長度為15 378，最短迭代次數為18，如圖2所示。

城市規模為50的最優路徑如圖3所示。最短路徑長度為549.96，最短迭代次數為16，如圖4所示。仿真結果表明，AGA算法具有較強的全局搜索能力和較快的收斂速度，能在較短的時間內獲得滿意的解，確實能夠有效地提高TSP問題的求解質量和求解速度。

圖1 城市規模為N=31時的最優路徑

圖2 城市規模為N=31時的優化過程

圖3 城市規模為N=50時的最優路徑

圖4 城市規模為N=50時的優化過程

為了更好的檢驗本算法的性能，將AGA算法所得的最優解分別與文獻［1］和［4］給出的最優解進行比較，結果見表1。

表1 城市規模N=31，50的仿真結果

其中，城市規模指代的是具有不同城市個數的TSP問題；本文結果指代的是采用本文算法求解對應TSP問題獲得的最短路徑長度；已公布最優解指代的是現有已公布的算法求解對應TSP問題所獲得的最短路徑長度；偏差=本研究算法獲得的結果-已知公布結果；改進率=（本研究算法獲得的最短路徑長度-已知公布結果）/已知公布結果。從表1中可以看出，通過本文提出的算法求解規模分別為31和50的TSP問題，所得的最優解明顯優于文獻［1］和［4］給出的最優解，證明了本算法的有效性。

本研究運行了來自TSPLIB的多個實例。將計算結果與標準遺傳算法（SGA）、混合遺傳算法（HGA）（將SGA與2opt結合的混合算法）進行比較。其中HGA和AGA算法的最大迭代次數設為500，SGA的最大迭代次數設為2000。仿真結果具體見表2。表中的每個實例都是在連續運行10次后得到的統計結果。實例表示的是帶有不同城市數的TSP具體問題；最優表示的是目前所獲得的求解所對應具體TSP實例的最優路徑長度；算法表示的是求解所對應具體實例問題所使用的不同求解方法，最好表示的是不同算法求解對應的TSP實例問題時得到的最短的路徑長度；平均表示的是指每種算法針對某一實例在10次試驗中所得的在規定的迭代次數內收斂到某一值后不在發生變化的最短路徑長度的平均值。從實驗結果可以看出，AGA算法求得的最好解與TSPLIB提供的最優解非常接近，而且求解的平均代數與其它算法相比要少，均優于文獻［1］和［4］所求得結果。AGA算法確實能夠有效的提高TSP的求解質量和求解速度。

表2 SGA、HGA、AGA算法實驗結果的比較

5 結 論

針對TSP問題，提出了一種基于局部搜索機制的自適應遺傳算法。設計了局部搜索機制，在該機制的指導下，把全局搜索與局部搜索方法自適應地結合，有效減小了算法陷入局部最優解的可能，增強了算法的尋優能力和速度。實驗結果表明，該算法是有效的。對生產調度、路徑規劃等排列組合優化問題具有現實指導意義。

由于提出的算法在求解小規模TSP問題時比較有效，而在求解大規模TSP問題時存在搜索質量差和速度慢等缺點，仍需進一步改進算法的性能加以解決。

［1］彭丹平，林志毅，王江晴.求解TSP的一種改進遺傳算法［J］.計算機工程與應用，2006，42（13）：91-93.

［2］姜昌華，胡幼華.一種求解旅行商問題的高效混合遺傳算法［J］.計算機工程與應用，2004，40（22）：67-70.

［3］楊 輝，康立山，陳毓屏.一種基于構建基因庫求解TSP問題的遺傳算法［J］.計算機學報，2003，26（12）：1753-1758.

［4］Ren S，Wang J，Zhang X J.Research on chaos partheno-genetic algorithm for TSP［C］//Computer Application and System Modeling（ICCASM），2010 International Conference on.IEEE，2010，1：290-293.

［5］Yang W，Hu Y，G K.Parallel search strategies for TSPs using a greedy genetic algorithm［C］//Natural Computation，2007.ICNC 2007.Third International Conference on.IEEE，2007，3：786-790.

［6］Hua F D，Xiao L L，Xue L.An improved genetic algorithm for combinatorial optimization［C］//Computer Science and Automation Engineering（CSAE），2011 IEEE International Conference on.IEEE，2011，1：58-61.

［7］高海昌，馮博琴，朱 利.智能優化算法求解TSP問題［J］.控制與決策，2006，21（3）：241-247.

［8］王宇平，李英華.求解TSP的量子遺傳算法［J］.計算機學報，2007，30（5）：748-755.

Adaptive Genetic Algorithm Based on Local Search Mechanism Quickly Solving TSP

XIA Kai1，DAI Wen-zhan2
（1.School of Mechanical Engineering and Automation，Zhejiang Sci-Tech University，Hangzhou，310018，China；2.School of Information and Electronic Engineering，Zhejiang Gongshang University，Hangzhou 310018，China）

This paper proposes a genetic algorithm based on local search mechanism quickly solving TSP.Based on local search mechanism，this paper adaptively combines standard genetic algorithm with local heuristic algorithm，so that local heuristic algorithm is allowed to execute only when individual quality is effectively improved，and thus avoid effectively phenomena of local optimum or computational overburden due to excessive number of local search.Simulation results show that this algorithm has a strong global optimization ability，fast convergence speed，and high efficiency in solving TSP.

local search mechanism；adaptive；genetic algorithm；traveling salesman problem

U461；TP308

A

（責任編輯：康 鋒）

1673-3851（2014）03-0287-05

2013-11-07

國家自然科學基金（61374022）；國家高新技術研究發展項目（2009AA04Z139）

夏 凱（1988-），男，浙江富陽人，碩士研究生，主要從事智能優化與模式識別等方面的研究。