改進的遺傳混合蟻群算法在TSP問題中的應用

徐德明

摘要： 為了提高基本蟻群算法的收斂性能和全局求解能力，對基本蟻群算法進行了改進，提出了一種改進的遺傳混合蟻群算法。在每代進化中保留最優解和次優解的公共解集后引入遺傳操作中的交叉算子進行運算，并采用自適應改變信息素揮發系數的方法，加快了算法收斂速度，提高了解的全局性。通過對 TSP 問題的仿真運算表明，改進的遺傳混合蟻群算法在收斂速度和解的全局性上都有較大的改善。

關鍵詞： 蟻群算法； 遺傳算法； 交叉算子； 自適應； TSP

中圖分類號：TP391文獻標志碼：B 文章編號：1006-8228（2012）11-31-02

Application of improved genetic hybrid ant colony algorithm in TSP

Xu Deming

（Huizhou University， Huizhou， Guangdong 516007， China）

Abstract： To improve the efficiency of convergence and the global ability of basic ACA， a novel hybrid algorithm is proposed， which is an improved combination of GA and ACA. Cross operator is calculated after reserving the intersection of the best solution and the second best solution in every evolution， and the adaptive change pheromone volatile coefficient is affected. Convergence speed is accelerated and the global ability of the algorithm is improved. The simulations for TSP problem show that the improved algorithm has better convergence efficiency and global ability.

Key words： ant colony algorithm（ACA）； genetic algorithm（GA）； cross operator； the adaptive change； TSP

0 引言

旅行商問題（Traveling Salesman Problem，TSP）又稱貨郎擔問題，是一個著名的組合優化問題，也是一個典型的、易于描述卻難于處理的NP完全問題[1]。由于該問題的實際模型在路徑、網絡、分配、基因測序和機器人控制等方面有著廣泛的應用[2]，故長期以來一直吸引著許多領域的研究人員對其算法改進的關注。

蟻群算法是一種求解組合最優化問題的新型通用啟發式方法，該方法具有正反饋、分布式計算和貪婪啟發式搜索的特點。由于蟻群算法容易出現停滯現象，即搜索進行到一定程度后，所有個體所發現的解完全一致，不能對解空間進一步搜索，不利于發現更好的解，而且蟻群中多個個體的運動是隨機的，當群體規模較大或網絡結構較為復雜時，要找出一條較好的路徑需要較長的搜索時間。

遺傳算法因其具有良好的魯棒性、可并行性與全局優化性而在求解組合最優化問題時獲得了廣泛的應用。但是，在實際應用中，遺傳算法早熟收斂等缺陷沒有從根本上消除，因此，通常存在計算量大的問題，從而導致定位速度慢。

遺傳算法和蟻群算法都是受生物進化論的啟發而提出來的仿生算法，兩種算法都應用于求解組合優化問題上，并取得了一定的成果。本文在基本蟻群算法的基礎上，給出一種改進的遺傳混合蟻群算法，這種改進后的混合算法利用遺傳算法中交叉與變異的優點，通過引入交叉算子增強蟻群算法尋找全局最優解的能力和加快算法的收斂速度，并采用自適應改變ρ值的方法提高了算法的全局搜索能力。仿真實驗表明，改進后的新算法能在保證一定的收斂速度的基礎上改進算法的全局收斂性。

1 基本蟻群算法原理（基本ACA）

螞蟻從某一地點出發，按照狀態轉移規則選擇下一路徑，該規則也被稱為“隨機比率規則”。螞蟻選擇路徑的轉移概率為：

⑴

式⑴中τij（t）為t時刻路徑（i，j）上的信息量；螞蟻在運動過程中用禁忌表tabuk來記錄螞蟻k走過的城市；allowedk={c-tabuk}表示螞蟻k下一步允許選擇的城市；α為信息啟發式因子，反映了螞蟻在運動過程中所積累的信息在螞蟻運動時所起的作用；β為期望啟發式因子，反映了螞蟻在運動過程中啟發信息在螞蟻選擇路徑中的受重視程度。ηij（t）為啟發函數，其表達式如下：

⑵

式⑵中dij表示相鄰兩個城市之間的距離。對螞蟻k而言，dij越小，則ηij（t）越大，也就越大。每只螞蟻走完一步或者完成一次循環，要對殘留的信息進行更新處理，每次迭代完成后，各路徑上的信息素都需要進行更新，其公式如下：

⑶

⑷

式⑶中ρ表示信息素揮發系數，1-ρ表示信息素的殘留因子；式⑷中表示第k只螞蟻在本次循環中留在路徑（i，j）上的信息量，其計算方法按照Ant-Cycle模型如下：

⑸

Q表示信息素強度，它在一定程度上影響算法的收斂速度；Lk表示第k只螞蟻在本次循環中所走過的路徑的總長度。

當所有螞蟻遍歷完一次后，要對殘留信息進行全局更新處理，其表達式同式⑶、式⑷，只是的表達式有所不同，在全局更新中只更新本次循環最小路徑L上的信息量，如下：

⑹

2 遺傳算法與蟻群算法融合（GAAA）

根據遺傳算法和蟻群算法兩者在某個集成算法中所處的地位和優勢不同，大體可以劃分為兩個大類算法：一類是以蟻群算法為主體的混合蟻群算法，如文獻[3]利用遺傳算法GA尋找ACS中ρ、α、β的最優組合；另一類是以遺傳算法為主體的混合遺傳算法如參考文獻[4-7]。本文基本思路是：算法前過程采用遺傳算法，充分利用遺傳算法的快速性、隨機性、全局收斂性，其結果是產生有關問題的初始信息素分布；算法后過程采用蟻群算法，在有一定初始信息素分布的情況下，充分利用螞蟻算法并行性、正反饋性、求精解效率高等特點。其總體框架如圖1所示。

[初始化參數，根據優化解生成信息素初始分布，將m只螞蟻置于n個結點][計算每只螞蟻移動到下一結點的概率，根據選擇概率移動每只螞蟻到下一結點][根據式⑶～式⑸局部更新每條路徑上的信息量][問題][定義目標函數和適應值函數][隨機生成一組實數編碼][遞歸迭代][根據適應函數選擇X，Y][對X，Y進行交叉計算][根據適應值函數進行逆轉變異][生成若干組優化解][根據式⑶⑷⑹全局更新每條路徑上的信息量][輸出最優解][遞歸迭代]

圖1遺傳混合蟻群算法流程圖

3 混合算法的改進

在基本遺傳混合蟻群算法的基礎上，本文給出了一種改進的遺傳混合蟻群算法，這種改進后的混合算法通過改進遺傳算法中交叉算子和采用自適應ρ值的方法增強算法尋找全局最優解的能力和加快算法的收斂速度。

3.1 交叉計算的改進[8]

Davis提出的順序交叉方法是先進行普通的雙點交叉，再進行維持原有相對訪問順序的巡回路線修改。這種算法和蟻群算法融合后可以提高算法的搜索空間，有助于提高算法的全局性，但是這種交叉具有隨機性，算法整體收斂速度不快。本文算法采用保留每代進化中最優的兩個解的公共解，采用單點交叉后再維持原有相對訪問順序的巡回路線修改，具體做法是：

設在n個城市的TSP問題中，TSP的一個解可表示為一個循環排列C=（C1，C2，…，Cn，Cl），定義任意兩個解Ci，Cj的交集Aij=Ci∩Cj，其中Aij表示Ci，Cj中排列相同的且子集中元素數目大于2的子集。對于第t代進化中選取最優解Ct1=（…，Ca，…，Cb，…，Cc，…，Cd，…）和次優解Ct2=（…，Cc…，Cd…，Ca，…，Cb），則（Ca，…，Cb）和（Cc，…，Cd）就是Ct1∩Ct2的兩個子集At1t2。在做交叉組合前保留交集，記=Ct1-At1t2，=Ct2-At1t2對，的元素進行中心單點交叉重組，將父體交叉點前元素不變的復制到后代New2中，同時把Ct2加到New2中，同樣也將父體交叉點前元素不變地復制到后代New1中，同時把Ct1加到New1中；在New1、New2中刪除與交叉段相同的元素得到新一代的New1、New2。

3.2 ρ取值的改進

當問題規模比較大時，一方面由于在信息量更新公式中采用了信息素揮發系數1-ρ，使得那些從未被搜索到路徑上的信息量會逐漸減少到0——該路徑將不被搜索，這就降低了算法的全局搜索能力；另一方面，當信息素含量ρ值過大時，隨著解的信息量增大，以前搜索過的解被選擇的可能性過大，也會影響到算法的全局搜索能力，為此應減小ρ值，從而提高全局搜索能力，但這樣又會降低算法的收斂速度。針對上述問題，本文采用自適應地改變ρ值[9]的方法，具體做法是：初始時刻取ρ=0.999；當算法在一定的循環次數內取得的最優值沒有明顯改變時，ρ值減為：

其中ρmin為ρ的最小值，這樣可以防止ρ過小而降低算法的收斂速度；rand（）為是隨機函數。這種自適應改變ρ值的方法保證了在一定的搜索速度下有效地提高混合算法的全局搜索能力。

4 實驗結果與分析

為了驗證混合算法的有效性，通過對TSPLIB中Oliver30問題進行仿真研究，平均運行20次作為仿真結果。實驗中采用的各項參數是：α=1，β=5，Q=150，螞蟻數目m=10，設置最大循環次數250次。實驗結果數據如表1所示。

表1三種算法最優解、平均解和進化代數

[[問題＼&算法＼&平均值＼&最優值＼&平均進化代數＼&Oliver30＼&基本ACA＼&437.09＼&423.73＼&121＼&GAAA＼&433.54＼&423.73＼&101＼&改進的GAAA＼&430.95＼&423.73＼&54＼&]]

從表1中的實驗數據可以看出，本文算法的全局性和收斂性相對有所提高。本文通過融入遺傳算法，引入交叉算子擴大算法的搜索空間，同時在交叉運算中保留解中公共最優路徑加快了算法的收斂速度，并采用自適應改變ρ值的方法提高了算法的全局搜索能力。通過對TSP問題的仿真表明本文算法是一種有效的改進算法。

參考文獻：

[1] Lin S，Kernighan B W.An effective heuristic algorithm for the

traveling salesman problem[J]. Operational Research，1971.19：486-515

[2] Michalewicz Z. How to solve it—modern heuristics[M].Berlin

Heidelberg：Springer-Verlag，2000.

[3] Zhan Shi- chang， Xu Jie， Wu Jun. The optimal selection on the

parameters of the ant colony algorithm[J].Bulletin of Science and Technology，2003.19（5）：381-386

[4] Chen H， Flann N S.Parallel simulated annealing and genetic

algo-rithms： a space of hybrid methods[M]//Parallel Problem Solving from Nature 3.[S.l.]：Springer-Verlag，1994：428-438

[5] Lee S， oLson D.A gradient algorithms for chance constrained

non-linear programming[J].European Journal of Operational Research，1977.11（1）：343-369

[6] Mahfoud S W， Goldgerg D E.A genetic algorithm for parallel

sim-ulated annealing[M]//Parallel Problem Solving from Nature 2， North Holland，1992：301-310

[7] Bilchev G， Parmee I C.Adaptive searching strategies for heavily

constrained design spaces[C]//Proceedings of 22nd International Conference on Computer Aided Design'95， Yelta： Ukraine，1995：230-235

[8] 劉立東，蔡淮.融入遺傳算法的混合蟻群算法[J].計算機工程與設計，

2008.29（5）：1248-1252

[9] 曹文梁，康嵐蘭.基于遺傳算法的混合蟻群算法及其在TSP中的應用

研究[J].制造業自動化，2011.33（1）：91-93