蟻群遺傳混合算法在求解旅行商問題上的應用

卓雪雪 苑紅星 朱蒼璐 錢鵬

摘要：針對在求解旅行商問題時，蟻群算法易陷入局部最優，而遺傳算法收斂速度慢等問題，將蟻群與遺傳算法相結合：把蟻群算法每次迭代的結果作為遺傳算法的初始種群，并且用遺傳算法尋優結果更新蟻群算法的信息素。在用遺傳算法處理問題的階段，引入了兩種新的交叉算子，并且提出混合交叉算子的新思想，算法的后期使用貪心搜索和2-opt局部優化算法，成功的避免了算法過早陷入局部最優解的問題，加快了算法的收斂速度。通過仿真，本算法與其他算法進行對比，尋優路徑長度明顯降低，在求解效率和求解質量上都有更好的效果。

Abstract： In solving the traveling salesman problem， ant colony algorithm is easy to fall into local optimum， and? genetic algorithm converges slowly. To overcome the problem， the Ant Colony Algorithm and the Genetic Algorithm were combined which uses the results of each iteration of the ant colony algorithm as the initial population of the genetic algorithms， and the pheromone of ant colony algorithm is updated by the optimization result of genetic algorithm. In the process of genetic algorithm， two new crossover operators were introduced and a new hybrid crossover operator scheme was proposed. To avoid the proposed algorithm falling into the local optimal solution and accelerate the convergence speed， the greedy search algorithm and the 2-opt local optimization algorithm are adopted in proposed hybrid algorithm. The simulation results show that the route path length is significantly reduced， and the proposed algorithm is more effective， compared with others algorithms.

關鍵詞：蟻群算法;遺傳算法;混合算法;TSP問題

Key words： ant colony algorithm;genetic algorithm;hybrid algorithm;TSP problem

中圖分類號：TP301.6? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?文獻標識碼：A? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 文章編號：1006-4311（2020）02-0188-06

0? 引言

最近幾年，各類啟發式智能優化算法在生產過程、車輛管理、數據挖掘乃至路徑尋優等領域得到深入的研究與廣泛的應用。蟻群算法[1-2]和遺傳算法作為各類智能優化算法中的佼佼者，各具特色。蟻群算法（Ant Colony Algorithm，ACO）是模擬大自然中真實螞蟻在尋找食物時群體間的相互協作行為，通過群體行為尋求最優結果。遺傳算法（Genetic Algorithm，GA）是模擬生物進化論的自然選擇和遺傳學的生物進化過程，通過自然選擇、優勝劣汰、適者生存的遺傳機制來尋求最優結果。使用智能優化算法可以解決路徑尋優領域中的一個經典問題——旅行商問題。

1? 旅行商問題

旅行商問題（Traveling Saleman Problem，TSP）是一個典型的NP完全問題。求一條使得旅行商的行程最短的路徑，可用以下數學模型表示：

若路徑，滿足函數f（L）的值最小，則路徑L就是所求的最優路徑。函數f（L）如下：

其中，ci為城市號，i=（1，2，…，n-1），c（i，j），j=（1，2，3，…，n），表示城市ci到城市cj的距離。若d（ci，cj）=d（cj，ci），則稱為對稱TSP問題[3]。

“旅行商問題”的應用非常廣泛，如：在互聯網環境中，如何更好地設置節點，以讓信息更好地流動;在道路交通中，如何更合理更高效的規劃道路，以減少擁堵;在物流運輸中，如何更好地規劃物流，以減少運營成本等。

鑒于TSP問題如此廣泛的應用，近幾年，很多學者進行了深入的研究。其中Abdulah Fajar在2009年使用聚類策略（Clustering Strategy）[4];M. A. H. Akhand在2013年使用速度試探粒子群算法（Velocity Tentative Particle Swarm Optimization）[5];Yingying Yu在2011年使用改進的遺傳算法（Genetic Algorithm）[6];M. D. Arango and C. A. Serna 在2015年使用文化基因算法（Memetic Algorithm）[7];Yongsheng Pan在2014年使用分解交叉路徑（Dismantling Cross Paths）[8]的方法;Haisheng Qin于2015年采用基于動態局部搜索（Dynamic Local Search）的蟻群算法[9];Vaisakh Shaj于2016年采用基于重組運算符（Recombination Operator）的邊緣粒子群優化算法[10]來求解TSP問題。這些算法在收斂速度或全局搜索能力等方面仍有許多值得完善的地方。

針對其他學者研究中的不足，本文提出了一種新的蟻群遺傳混合算法來求解旅行商問題。通過與其他算法的對比分析，本文提出的改進型蟻群遺傳混合算法具有收斂速度快，搜索全局最優解能力強的優點。

2? 蟻群遺傳混合算法求解TSP

蟻群遺傳混合算法（Ant Colony Genetic Hybrid Algorithm，ACGHA）將蟻群算法求得的結果作為遺傳算法的初始種群，用遺傳算法尋優結果更新蟻群算法的信息素。與單一的遺傳算法和蟻群算法相比，該算法減少了遺傳算法的尋優次數，加快了遺傳算法的收斂速度，提高了蟻群算法的正反饋性和全局搜索能力，從整體上提高了算法的執行效率。改進的蟻群遺傳混合算法求解TSP問題的流程圖如圖1所示。

具體步驟如下：

2.1 初始化

初始化信息素啟發式因子α，期望值啟發式因子β，信息素揮發系數ρ，信息素強度Q，每兩個城市之間的距離d、信息素τ、啟發式信息η，交叉率pc，變異率pm。

2.2 循環迭代

step1初始化禁忌表為空

step2將m只螞蟻隨機地分配在n個城市中

step3 確定狀態轉移方向

在每次迭代中，采用禁忌表來記錄每只螞蟻k（k=1，2，…，m）當前走過的城市。螞蟻k根據各路徑上的信息量和路徑啟發信息來計算狀態轉移概率，再根據狀態轉移概率和禁忌表來確定狀態轉移方向。依次執行m次，最終可求出m只螞蟻一次遍歷后的m條完整路徑。

螞蟻k在t時刻由城市i轉移到城市j的狀態轉移概率p（t）為：

公式中，allowedk用以表示螞蟻k在下一時刻允許選擇的下一個城市。τij（t）表示t時刻，路徑（i，j）上的信息素強度，并且路徑上的信息素濃度越大，此路徑被螞蟻選擇的概率也越大。ηij（t）表示啟發式信息，反映螞蟻對下一個城市的能見度，通常取值為1/dij，dij表示路徑（i，j）之間的距離。α為信息素啟發式因子，β為期望值啟發式因子，這兩個因子皆是預先設置的參數，用來控制啟發式信息與信息素濃度作用的權重關系。

step4編碼生成遺傳算法的初始種群

在遺傳算法的設計中，編碼影響著整個算法的執行效率，因此它成為遺傳算法要解決的首要問題。在TSP中，將城市按照被拜訪的順序組成編碼。確定編碼方式后，把蟻群算法中每只螞蟻一次遍歷后的完整路徑作為遺傳算法的初始種群（population）。

step5計算適應度

適應度（fitness）由適應度函數計算而來。適應度函數（fitness function）是問題中的全體對象與其適應度之間的一種對應關系。在TSP中，要尋找使目標函數f （L）取最小值時的個體。因此適應度函數選取目標函數的倒數，即f （k）=1/f （Lk）。可見，路徑越短適應度越大。

step6執行選擇算子

首先按照適應度由大到小的順序對種群中的個體進行排序，然后通過選擇算子對種群中的個體進行選擇，最后得到遺傳的父體。

在TSP中，按照1：1的比例，采用最優個體保存策略[11]和輪盤賭方法對種群中的個體進行選擇。即首先適應度排序在前50%的個體一定被保存，然后對剩下50%的個體，計算每個個體適應度在整個種群適應度中被選擇的概率和累計概率，最后通過隨機數random （0

step7執行交叉算子

遺傳算法中起核心作用的是交叉算子（crossover）。在TSP中，對種群中的個體，按照交叉概率pc進行交叉操作，產生下一代種群。本文引入兩種新的交叉算子，并提出混合交叉算子的思想，分別敘述如下：

a）交叉算子1[6]

生成子路徑L1的過程：

首先，從種群population中隨機確定兩個個體p、q作為子代路徑的父體，隨機確定一個交叉城市randcity作為子代路徑的起點城市。

其次，計算父體p、q路徑中城市randcity與下一個城市cp1、cq1的距離，記作dp1和dq1，接著分別計算城市cp1、cq1與城市cp1、cq1之后的城市cp2、cq2之間的距離，記作dp2和dq2，若dp1+r*dp2？燮dq2+r*dq2（0

最后，重復上面的步驟，直到父體中僅剩一個城市為止，直接加入路徑L1。

生成子路徑L2的過程與生成子路徑L1的過程大致相同，不同之處是分別計算父體p、q路徑中城市randcity與上一個城市和上上一個城市之間的距離之和在做比較，這里不再贅述。

按照上述方法選擇不同的父體得出更多的子路徑，然后把這些子路徑組合在一起形成新種群newpopulation。在生成新種群的過程中需要注意的是：按照不同的方向分別生成兩個子路徑之后，在生成下一個路徑的過程中所選擇的父體不允許重復。

相比于其他交叉算子，該交叉算子使算法的收斂速度明顯加快，且易于求出問題空間的最優解;但是，該交叉算子的時間復雜度稍微偏高，而且不利于開拓新路徑，因此本文引入了交叉算子2[11]。

b）交叉算子2

首先，根據TSP中城市的數量，定義4個互不相同的隨機數字作為交叉城市的城市編號。

其次，從種群population中隨機確定兩個個體p、q作為子代路徑的父體。

最后，分別確定4個交叉城市所在父體染色體上的基因位置。保持父體染色體交叉點上的基因不變，其他基因按順序兌換位置。這樣就產生子代種群中的兩個個體。

例如，兩個父體分別如下（標有下劃線加粗的數字代表交叉城市的城市編號）：

05 07 04 11 02 10 03 09 06 01 08

10 03 05 09 04 06 08 02 11 01 07

父體染色體交叉點上的基因不變，其他基因按順序兌換位置后，產生的子代種群中的兩個個體如下：

03 05 04 06 08 10 02 09 11 01 07

10 05 07 09 04 11 02 03 06 01 08

按照上面的三個步驟可以確定構成子代新種群newpopulation所需要的m個個體。同樣地，在生成子代種群的過程中所選擇的父體不允許重復。

相比于交叉算子1，該交叉算子有利于開拓新路徑和搜索全局最優解，且該算子的時間復雜度較低，但算法的收斂速度相對較慢。

鑒于交叉算子1和交叉算子2的優缺點，根據實際問題的需要，本文提出混合交叉算子的新思想，使交叉算子1和2按比例進行交叉運算，使其優劣互補，有效的提高了整個算法的收斂速度和求解全局最優解的能力。

step8執行變異算子

變異（mutation）亦稱為突變，就是改變染色體某個（些）位上的基因。主要的變異技術有逆轉變異、位點變異、插入變異、對換變異等。本文在求解TSP中采用的變異方式為對換變異，即將隨機選取的若干基因按照變異概率pm互換。

step9執行貪心搜索

為防止遺傳算法過早陷入局部最優解，本文提出一種貪心搜索算法[12]，并按照一定的概率進行貪心搜索。首先，從種群中隨機地選取一個個體p中的城市c作為旅行商當前所在的城市，并加入到新個體中;其次，搜索個體p中所有未加入到新個體中的城市，找到距離當前城市c最近的城市d，將d添加至新個體中并作為旅行商當前所在的城市;最后，按照這種方法，繼續搜索個體p中所有未加入到新個體中的下一個城市，直到所有城市都加入到新個體中，這樣便得到優化后的個體。

step10使用2-opt局部優化

2-opt局部優化[7]是防止遺傳算法過早陷入局部最優的另一有效方法。本文按照一定的概率進行2-opt局部優化。該算法的思想是以邊為基礎，首先，從解當中任意拿出兩條邊，此時會將解拆成兩個部分，如圖2（a）中去掉邊s23和s45，將其中一部分的路徑反接回另一路徑，如圖2（b）所示;

其次，比較新路徑與原路徑的長度，把路徑相對較短的解保留下來;最后，針對不同的邊重復進行以上的步驟，便可得到局部優化的解。

step11更新信息素

隨著時間的推移，信息素不僅會慢慢的積累，也會漸漸的揮發。為了避免一條路徑被螞蟻反復走過之后信息素無限的積累，導致殘留信息素淹沒啟發信息，因此在遍歷完n個城市一次之后，需要對信息素進行更新。t+1時刻路徑（i，j）上的信息素按以下公式進行更新：

公式中，m是螞蟻個數，ρ是信息素的揮發率（0<ρ<1），1-ρ代表信息素殘留因子，Δτ（t）代表第k只螞蟻在本次迭代中（t時刻）經過路徑（i，j）后，對路徑（i，j）上的信息素產生的增量。Lk代表第k只螞蟻在本次迭代中所走過的路徑長度，Q表示螞蟻循環一周所釋放的總信息量。

step12算法終止條件判斷

若nc？燮maxNc且gene？燮maxGene，轉到step5，若nc？燮maxNc且gene>maxGene，轉到step1，若nc>maxNc或遺傳算法得出的結果滿足本文要求的最優解，轉到2.3。

2.3 輸出結果

根據上述步驟得出的結果，輸出最優路徑。

3? 仿真實驗

基于上文提到的算法，采用C++語言編寫程序進行仿真對比實驗。實驗環境為： Windows7系統，2G內存，Intel（R） Core（TM）2 Quad 2.50GHz CPU，Microsoft Visual Studio 2010平臺。實驗參數設置如下：種群規模m=20，α=2，β=3，ρ=0.7，Q=100，pc=0.7，pm=0.095，遺傳算法最大進化代數maxGene=20，程序最大迭代次數maxNc=200。

①為說明本文算法在尋優結果上取得的良好效果，分別選用國際標準TSPLIB測試庫[13]中的eil76、st70、eil51、c50、att48等實例進行模擬。算法連續運行10次，得到的實驗數據對比如表1所示。

對比其他學者在TSP問題上的研究成果，可以得出，本文算法在尋優結果上有了很大的提升。其中，各實例尋優結果最短路徑分別如圖3至圖11所示。

②本文提出的算法具有較快的收斂速度，以eil51實例為例。圖12表示初始種群中的路徑，Route Length=1493.44;圖13表示第1次迭代后的最優路徑，Route Length=492.993;圖14表示最后1次迭代后的最優路徑，Route Length=428.982。圖15是eil51實例中，算法收斂過程迭代圖。

由圖12至圖15可知，經過第1次迭代后便可從初始種群的Route Length=1493.44搜索到Route Length=492.993的良好路徑;迭代不足200次即可搜索出Route Length=428.982的最好路徑。結合算法收斂過程迭代圖，可知本文算法不僅在尋優結果上有了很大的提升，而且具有較好的全局搜索能力和較快的收斂速度。

4? 結論

本文提出的蟻群遺傳混合算法將蟻群算法求得的結果作為遺傳算法的初始種群，使人工智能蟻群的搜索代替傳統遺傳算法中隨機的編碼。用遺傳算法尋優結果更新蟻群算法的信息素，使蟻群算法信息素的更新更具高效性，提高了算法的正反饋性。引入啟發式混合交叉算子有效地提高了算法的收斂速度，算法的后期使用貪心搜索策略和2-opt局部優化算法有效的防止了解集陷入局部最優，從而提高了算法的全局搜索能力。仿真結果表明，改進的算法在解決TSP問題上具有較好的尋優能力。

參考文獻：

[1]Maniezzo D， Dorigo M， Maniezzo V， et al. Ant System： An Autocatalytic Optimizing Process[J]. Clustering， 1991， 3（12）：340.

[2]Dorigo M， Maniezzo V， Colorni A. The Ant System： Optimization by a colony of cooperating agents[C]// IEEE Transactions on Systems， Man， and Cybernetics. 1996：29-41.

[3]Niendorf M， Kabamba P T， Girard A R. Stability of Solutions to Classes of Traveling Salesman Problems.[J]. Cybernetics IEEE Transactions on， 2015：1.

[4]Fajar A， Abu N A， Herman N S. Initial Result of Clustering Strategy to Euclidean TSP[C]// Soft Computing and Pattern Recognition， 2009. SOCPAR '09. International Conference of. 2009：13-18.

[5]Akhand M A H， Akter S， Rashid M A. Velocity Tentative Particle Swarm Optimization to solve TSP[C]// International Conference on Electrical Information and Communication Technology. 2014：1-6.

[6]Yu Y， Chen Y， Li T. A New Design of Genetic Algorithm for Solving TSP[C]// International Joint Conference on Computational Sciences & Optimization. IEEE Computer Society， 2011：309-313.

[7]Arango Serna M D， Serna Uran C A. A Memetic Algorithm for the Traveling Salesman Problem[J]. IEEE Latin America Transactions， 2015， 13（8）：2674-2679.

[8]Pan Y， Xia Y. Solving TSP by dismantling cross paths[C]// IEEE International Conference on Orange Technologies. IEEE， 2014.

[9]Qin H， Zhou S， Huo L， et al. A New Ant Colony Algorithm Based on Dynamic Local Search for TSP[C]// Fifth International Conference on Communication Systems and Network Technologies. IEEE， 2015：913-917.

[10]Vaisakh Shaj， P M Akhil， S. Asharaf. Edge-PSO：A Recombination Operator Based PSO Algorithm for Solving TSP[C]// 2016 International Conference on Advances in Computing， Communications and Informatics （ICACCI）. IEEE， 2016：35-41.

[11]Huang S C， Jiau M K， Lin C H. Optimization of the Carpool Service Problem via a Fuzzy-Controlled Genetic Algorithm[J]. IEEE Transactions on Fuzzy Systems， 2015， 23（5）：1698-1712.

[12]Lin S， Rong Y， Sun X， et al. Learning capability of relaxed greedy algorithms.[J]. IEEE Transactions on Neural Networks & Learning Systems， 2013， 24（10）：1598-1608.

[13]TSPLIB.http：//www.iwr.uni-heidelberg.de/groups/comopt/software/ TSPLIB95/. April， 2006.

[14]Hua Z， Chen J， Xie Y. Brain Storm Optimization with Discrete Particle Swarm Optimization for TSP[C]// International Conference on Computational Intelligence and Security. IEEE Computer Society， 2016：190-193.

[15]Pan Y， Xia Y. Solving TSP by dismantling cross paths[C]// IEEE International Conference on Orange Technologies. IEEE， 2014：121-124.

[16]Safae Bouzbita， Abdellatif El Afia， Rdouan Faizi， Mustapha Zbakh. Dynamic adaptation of the ACS-TSP local pheromone decay parameter based on the Hidden Markov Model[C]//2016 2nd International Conference on Cloud Computing Technologies and Applications （CloudTech）.IEEE， 2016：344-349.