改進(jìn)的遺傳混合蟻群算法在TSP問題中的應(yīng)用

徐德明

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

關(guān)鍵詞： 蟻群算法； 遺傳算法； 交叉算子； 自適應(yīng)； TSP

中圖分類號(hào)：TP391文獻(xiàn)標(biāo)志碼：B 文章編號(hào)：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）又稱貨郎擔(dān)問題，是一個(gè)著名的組合優(yōu)化問題，也是一個(gè)典型的、易于描述卻難于處理的NP完全問題[1]。由于該問題的實(shí)際模型在路徑、網(wǎng)絡(luò)、分配、基因測序和機(jī)器人控制等方面有著廣泛的應(yīng)用[2]，故長期以來一直吸引著許多領(lǐng)域的研究人員對其算法改進(jìn)的關(guān)注。

蟻群算法是一種求解組合最優(yōu)化問題的新型通用啟發(fā)式方法，該方法具有正反饋、分布式計(jì)算和貪婪啟發(fā)式搜索的特點(diǎn)。由于蟻群算法容易出現(xiàn)停滯現(xiàn)象，即搜索進(jìn)行到一定程度后，所有個(gè)體所發(fā)現(xiàn)的解完全一致，不能對解空間進(jìn)一步搜索，不利于發(fā)現(xiàn)更好的解，而且蟻群中多個(gè)個(gè)體的運(yùn)動(dòng)是隨機(jī)的，當(dāng)群體規(guī)模較大或網(wǎng)絡(luò)結(jié)構(gòu)較為復(fù)雜時(shí)，要找出一條較好的路徑需要較長的搜索時(shí)間。

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

遺傳算法和蟻群算法都是受生物進(jìn)化論的啟發(fā)而提出來的仿生算法，兩種算法都應(yīng)用于求解組合優(yōu)化問題上，并取得了一定的成果。本文在基本蟻群算法的基礎(chǔ)上，給出一種改進(jìn)的遺傳混合蟻群算法，這種改進(jìn)后的混合算法利用遺傳算法中交叉與變異的優(yōu)點(diǎn)，通過引入交叉算子增強(qiáng)蟻群算法尋找全局最優(yōu)解的能力和加快算法的收斂速度，并采用自適應(yīng)改變?chǔ)阎档姆椒ㄌ岣吡怂惴ǖ娜炙阉髂芰?。仿真?shí)驗(yàn)表明，改進(jìn)后的新算法能在保證一定的收斂速度的基礎(chǔ)上改進(jìn)算法的全局收斂性。

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

螞蟻從某一地點(diǎn)出發(fā)，按照狀態(tài)轉(zhuǎn)移規(guī)則選擇下一路徑，該規(guī)則也被稱為“隨機(jī)比率規(guī)則”。螞蟻選擇路徑的轉(zhuǎn)移概率為：

⑴

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

⑵

式⑵中dij表示相鄰兩個(gè)城市之間的距離。對螞蟻k而言，dij越小，則ηij（t）越大，也就越大。每只螞蟻?zhàn)咄暌徊交蛘咄瓿梢淮窝h(huán)，要對殘留的信息進(jìn)行更新處理，每次迭代完成后，各路徑上的信息素都需要進(jìn)行更新，其公式如下：

⑶

⑷

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

⑸

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

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

⑹

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

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

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

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

3 混合算法的改進(jìn)

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

3.1 交叉計(jì)算的改進(jìn)[8]

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

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

3.2 ρ取值的改進(jìn)

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

其中ρmin為ρ的最小值，這樣可以防止ρ過小而降低算法的收斂速度；rand（）為是隨機(jī)函數(shù)。這種自適應(yīng)改變?chǔ)阎档姆椒ūＷC了在一定的搜索速度下有效地提高混合算法的全局搜索能力。

4 實(shí)驗(yàn)結(jié)果與分析

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

表1三種算法最優(yōu)解、平均解和進(jìn)化代數(shù)

[[問題＼&算法＼&平均值＼&最優(yōu)值＼&平均進(jìn)化代數(shù)＼&Oliver30＼&基本ACA＼&437.09＼&423.73＼&121＼&GAAA＼&433.54＼&423.73＼&101＼&改進(jìn)的GAAA＼&430.95＼&423.73＼&54＼&]]

從表1中的實(shí)驗(yàn)數(shù)據(jù)可以看出，本文算法的全局性和收斂性相對有所提高。本文通過融入遺傳算法，引入交叉算子擴(kuò)大算法的搜索空間，同時(shí)在交叉運(yùn)算中保留解中公共最優(yōu)路徑加快了算法的收斂速度，并采用自適應(yīng)改變?chǔ)阎档姆椒ㄌ岣吡怂惴ǖ娜炙阉髂芰ΑＭㄟ^對TSP問題的仿真表明本文算法是一種有效的改進(jìn)算法。

參考文獻(xiàn)：

[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].計(jì)算機(jī)工程與設(shè)計(jì)，

2008.29（5）：1248-1252

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

研究[J].制造業(yè)自動(dòng)化，2011.33（1）：91-93