微正則退火的雙向蟻群優化算法*

周浩理， 李太君， 肖　沙， 徐寧敏

(1.海南大學 信息科學技術學院，海南 海口 570228；2.海南省公安廳 科技通信處，海南 海口 570228)

微正則退火的雙向蟻群優化算法*

周浩理1， 李太君1， 肖沙1， 徐寧敏2

(1.海南大學 信息科學技術學院，海南 海口 570228；2.海南省公安廳 科技通信處，海南 海口 570228)

摘要:雙向蟻群搜索算法可以提高算法的搜索速度，并可以選擇搜索的空間；微正則退火算法具有準確度高、速度快等優點，可以實現全局路徑優化搜索。結合兩種算法的優點，提出了雙向蟻群微正則退火算法，用來求解海量數據網絡下的旅行商問題。通過實驗表明：雙向蟻群微正則退火算法不容易陷入局部最優解，且在尋找全局最優解和運行效率上都比其他算法更有優勢。

關鍵詞：雙向蟻群算法； 微正則退火算法； 大規模； 全局最優解

0引言

蟻群算法作為群集智能算法的一種，在求解組合優化問題中有重要的應用，但其容易陷入局部最優而使算法停滯，收斂速度較慢使算法執行時間過長。學者們提出了多種改進策略以改進蟻群算法，王沛棟在改進蟻群算法的基礎上，解決了智能體路徑規劃、車輛路由、多智能體的編隊控制、旅行售貨員等問題[1]；HeYueshun等人基于移動代理和蟻群算法，對無線傳感器網絡的路由算法進行了改進，具有良好的實際應用效果[2]；段海濱等人提出了一種改進的蟻群算法用于求解連續空間優化問題[3]；WangJ等人從涵蓋人、車、物等影響因子在內的實際情況出發，定義路網分割算法，改進了蟻群算法解決實際問題的能力[4]；另外，考慮蟻群算法和其他算法的結合，也提出了多種算法，申利民等人提出一種基于遺傳蟻群融合算法的測試用例最小化方法，降低了回歸測試成本和縮減了測試用例規模[5]，王憲等人提出了一種基于蟻群粒子群融合算法，解決了復雜環境下移動機器人路徑規劃問題[6]，李敬花提出基于遺傳蟻群融合算法，提高了多項目資源能力平衡優化的效率[7]。

本文考慮到雙向蟻群快速求解局部最優和微正則退火高效全局尋優的特性，提出了求解大規模旅行商問題的雙向蟻群微正則退火優化算法。

1旅行商問題求解模型

旅行商問題是近代組合優化領域的一個典型難題，現實生活中的網絡通信問題、交通調度問題、電路板鉆孔問題和郵路問題等都可以轉化為旅行商問題，這些問題本身就是旅行商問題或者可以直接轉化為旅行商問題的原型。旅行商問題一直是測試組合優化新算法的標準問題。

旅行商問題就是指一個商人從自己所在的城市出發，希望找到一條最短路徑，能夠經過給定的城市集合中的所有城市，最后返回家鄉，并且每個城市都被訪問有且僅有一次。旅行商問題用數學語言可描述如下：設G=(V,E)為一個城市圖，V={V1,V2,…,Vn}為n個城市的集合，E={eij|Vi,Vj∈V}為V中元素兩兩連線的集合，旅行商問題的目的是從中找出長度最短的回路，即哈密頓回路，也就是找出對V中n個城市訪問有且僅有一次的最短封閉曲線。

2蟻群算法

2.1蟻群算法思想

20世紀90年代初，意大利學者DorigoM等人受到大自然中螞蟻覓食行為的啟發，提出了蟻群算法，仿生螞蟻在沒有事先告訴食物在什么地方的前提下開始尋找食物。當一只螞蟻找到食物以后，它會向周圍釋放信息素(pheromone)，信息素會隨著時間的推移而逐漸消失，路徑的遠近由信息素濃度的大小來表征，其他螞蟻會被信息素吸引過來，從而會有更多螞蟻找到食物。在這個過程中，會有特殊的螞蟻不會像其他螞蟻總是重復同一條路，而會另外開辟一條道路，如果這條路比其他路更短，那么，隨著時間的推移會慢慢地吸引更多的螞蟻走這條更短的路。最后，隨著時間的推移，可能會有一條最短的路徑被大部分螞蟻重復著[8]。

2.2螞蟻系統

螞蟻系統(AS)是由LiuBo,QingZheng和WangRui最先提出的蟻群優化(ACO)算法形式[9]。按照信息素軌跡更新方式不同，給出了三種AS算法，分別稱為螞蟻圈(ant-cycle)、螞蟻數量(ant-quantity)、螞蟻密度(ant-density)。

3雙向蟻群微正則退火算法

3.1小生境雙向蟻群搜索策略

從旅行商的小生境性質出發，可以限定螞蟻在每個城市可以“看到”的下一個城市的數目，或者可以對螞蟻的每次移動的范圍進行限定，能夠縮小搜索范圍、提出劣質解，從而可以對蟻群的搜索效率進行提高。在算法中為每個城市建一個數組 ，保存window個距離最近的城市，window值隨迭代次數動態調整。

旅行商問題的解是哈密頓回路，采用雙向蟻群策略高效搜索：將螞蟻(分泌相同的信息素)成對分配在各個城市，成對的螞蟻共用一個禁忌表，分頭搜索直至訪問完所有城市而相遇。雙向蟻群搜索策略，使得算法搜索空間約減小50 %左右，進一步提高了搜索效率。

(1)

在自然環境中，可揮發物質的濃度越大，揮發系數也越大，因此,可以根據路徑上信息素的多少來調整揮發系數的大小，使其符合自然規律，可以避免信息素堆積的現象，增強后期算法的啟發性，所有最短路徑的信息素更新方式

(2)

式中E(i,j)包含在最短路徑中，Lbest為最短路徑長度。

3.2微正則退火算法

1983年，CreutzM基于微正則蒙特卡羅仿真方法提出了微正則退火概念。在此概念中，令一種能量載體“妖”在系統中不斷移動，實現能量的交換[10]。在一定的時段內，系統表現為能量守恒狀態，但是能量載體在算法模型中不斷移動會使系統的能量出現波動，并使熱系統的能量發生變化，從而脫離亞穩態模式。應用于旅行商問題的微正則退火算法，初始解空間為雙向蟻群搜索的結果S，能量E為目標函數值，巡游路徑長度L。

3.3算法的實現過程

在得到最優路徑的過程中，蟻群算法有時會陷入局部最優解，表現為陷入停滯狀態。因此，關鍵問題就是如何避免算法陷入局部最優，得到全局最優解。許智宏等人提出對蟻群算法和模擬退火算法的優點進行結合，用該算法求解旅行商問題，首先使用蟻群算法得到較優的局部解，而后利用模擬退火算法跳出局部最優的情況，從而可以得到最優解[11]。但是模擬退火算法有一個缺點，其需要生成隨機數，再按照Metropolis準則拒絕或者接受新狀態，而微正則退火算法擺脫了這一限制，其采用了確定性的狀態轉移機制，不需要用隨機數來進行判斷拒絕或接受新狀態，故在大規模問題上要比模擬退火算法更有時間效率[12]。因此，本文提出將微正則退火算法與蟻群算法結合，繼而解決旅行商的局部最優問題。

雙向蟻群微正則退火算法的具體步驟如下：

1)為n個城市分別建立數組cityWin[window]，置迭代次數N=0，初始參數Nmax。

2)將m對螞蟻隨機置于n個城市中，所在城市編號加入相應禁忌表tabu[k]。

3)將m對螞蟻循環直至所有螞蟻對完成巡游。

①最短路徑長度Lmin=0，tabu[k]=0。

②螞蟻對K(假設第K對螞蟻在城市i)，巡游路徑長度L=0，循環直至禁忌表滿；

a.第一只螞蟻從cityWin[window]和allowedk={C-tabu[k]}的交集中按式(1)選擇j為下一個旅行城市。若交集為空，則只在allowedk={C-tabu[k]}中選擇。更新路徑長度L+=L(i,j)，若L大于Lmin，停止搜索；否則，更新路徑序列，并將城市j加入禁忌表tabu[k]繼續搜索。

b.第二只螞蟻從cityWin[window]和allowedk={C-tabu[k]-j}的交集中按公式(1)選擇jj為下一個旅行城市。若交集為空，則只在allowedk={C-tabu[k]}中選擇。更新路徑長度L+=L(i,jj)，若L大于Lmin，停止搜索；否則，更新路徑序列，并將城市jj加入禁忌表tabu[k]繼續搜索。

③若L

4)更新最短路徑上的信息素，并用min—max準則限定信息素含量。

5)N=N+1，若N=Nmax或者出現Nmax×5次最短路徑結果相同(算法停滯)，停止迭代；否則,繼續。

6)將小生境雙向蟻群搜索的結果S作為退火的解空間。初始化循環變量i=1，j=1。

7)初始化系統能量E0，并釋放一個在狀態空間中行走的“妖”，令其能量初值為ED=0。

8)循環，直到i>N即遍歷完S中的所有結果。

①設定“妖”的能量上界Emax，即Emax=Emax·p(p為能量下降參數)，設定三個初始最優狀態t1，t2，t3。

②重復如下步驟，直到j>jmax,即執行完2-opt的所有可能變換。

a.“妖”在狀態空間中移動一步(產生新解)，計算系統相鄰狀態的差值ΔE。

b.當ED過大，實行能量縮減ED=ED×(1-p)。如果ED>ΔE，則接受新的系統狀態，更新最優狀態數組，并檢查妖的能量是否已越界；否則拒絕新解，當ED過小，實行獎勵ED=ED(1+q)。

c.如果連續若干次拒絕新解，將狀態回溯，重新移動。

9)輸出最優結果。

4算法仿真

本文采用Matlab仿真上述求解旅行商問題的雙向蟻群微正則退火算法，實驗結果與分析如下：

首先利用Matlab仿真隨機生成30個點代表目的旅行城市，然后計算各座城市的小生境窗口并利用雙向蟻群算法尋找最優路徑，如果尋優過程出現停滯，就以蟻群算法的結果作為微正則退火算法的初始解空間，繼而退火尋找最優結果路徑，避免系統陷入局部最優。圖1為使用雙向蟻群微正則退火算法得到的30座城市的旅行商問題優化的結果圖，圖示的結果最短路徑：Shortest_Route=(1，3，5，7，10，13，14，15，17，23，28，21，25，27，22，24，30，29，26，12，11，16，19，20，18，8，6，9，4，2)，最短路徑長度Shortest_Length=457.729 1。由圖可知，該算法得到的是最優的路線圖。

圖1　30座城市旅行商問題優化結果Fig 1　Optimization results of traveling salesman problem of 30 cities

圖2表示使用雙向蟻群微正則退火算法的200次迭代求解旅行商問題的平均距離和最短距離變化圖。由圖可知,本算法的效率很高，可以快速得到最短距離解，并且其平均距離一直是在變化的，表明本算法一直沒有陷入局部最優解的情況。

算法收斂時間比較如圖3所示。本文對算法的執行效率與基本蟻群算法、基于模擬退火的蟻群算法進行了比較。本文采用執行時間(CPU時間)來對算法的執行效率進行評測，圖3顯示各算法執行時間的比較結果。由圖可知，基本蟻群算法的執行時間最長，其次是基于模擬退火的蟻群算法，而本文提出的算法執行時間明顯低于這兩種算法，由此說明本算法能快速有效地從局部優化解中擺脫，從而獲得全局優化解，收斂性高。

圖3　算法收斂時間比較Fig 3　Comparison of algorithm convergence time

5結束語

本文采用雙向蟻群微正則退火算法求解旅行商問題，基于小生境的雙向蟻群大大縮減了搜索時間，微正則退火算法具有強大的全局尋優能力。本文在Matlab平臺下進行仿真，得到本文提出的算法相比于其他求解旅行商問題的方法，在運行效率和尋找全局最優解等方面都具有較大的優勢，具有良好的實用性。

參考文獻:

[1]王沛棟.改進蟻群算法及在路徑規劃問題的應用研究[D].青島：中國海洋大學，2012.

[2]HeYueshun,DuPing.Mobileagentroutingalgorithmbasedonimprovedantcolonyalgorithm[J].InternationalFrequencySensorAssociation,2013,22(11)：15-21.

[3]段海濱，馬冠軍，王道波,等.一種求解連續空間優化問題的改進蟻群算法[J].系統仿真學報，2007，19(5)：974-977.

[4]WangJian,WangYanyan,LiHongyun.Improvedantcolonyalgorithmforlogisticsvehicleroutingproblemwithtimewindow[M].Berlin,Heidelberg:Springer,2012:41-48.

[5]申利民，高潔.基于遺傳蟻群融合算法的測試用例最小化研究[J].計算機工程，2012，38(16)：57-64.

[6]王憲，王偉，宋書林,等.基于蟻群粒子群融合的機器人路徑規劃算法[J].計算機系統應用，2011，20(9)：98-102.

[7]李敬花.遺傳蟻群融合算法求解多項目資源能力平衡問題[J].計算機集成制造系統，2010，16(3)：643-649.

[8]MarcoDorigo，LucaMariaGambardella．Antcoloniesforthetra-velingsalesmanproblem[J]．BioSystems，1996，43：73-81．

[9]LiuBo，QingZheng，WangRui，etal.Ahybridheuristicantcolonysystemforcoordinatedmulti-targetassignment[J].InformationTechnologyJournal，2009,8(2)：156-164.

[10]CreutzM.MicrocanonicalMonteCarlosimulation[J].PhysicalReviewLetters,1983,50(19):1411-1414.

[11] 許智宏，宋勃，郭艷艷.模擬退火與蟻群混合并行算法解旅行商問題[J].河北工業大學學報，2010，39(2)：48-51.

[12] 徐暢.大規模路網下基于蟻群微正則退火算法的路徑優化方法研究[D].長春：吉林大學，2013.

Optimizationforbidirectionalantcolonyalgorithmbasedonmicrocanonicalannealing*

ZHOUHao-li1，LITai-jun1，XIAOSha1，XUNing-min2

(1.SchoolofInformationScienceandTechnology,Hai’nanUniversity,Haikou570228,China;2.ScienceandTechnologyCommunicationSection,Hai’nanPublicSecurityDepartment,Haikou570228,China)

Abstract:Bidirectional ant colony search algorithm can improve search speed and select search space;microcanonical annealing algorithm can realize global path optimization search with high speed and accuracy.Combine advantages of the two algorithms and propose bi-ACO microcanonical annealing algorithm for solving traveling salesman problem in massive data network.Experiments show that bi-ACO microcanonical annealing algorithm is not easy to fall into local optimal solution,and it has more advantages in searching for globally optimal solution and operating efficiency than other algorithms.

Key words:bidirectional ant colony algorithm; microcanonical annealing algorithm; large-scale; globally optimal solution

DOI:10.13873/J.1000—9787(2016)04—0127—03

收稿日期：2015—07—09

*基金項目：海南省社會發展科技專項項目(SF201455)； 海南大學2015年研究生實踐創新項目

中圖分類號：TP 301.6

文獻標識碼：A

文章編號：1000—9787(2016)04—0127—03

作者簡介:

周浩理(1989-),男,湖南湘鄉人,碩士研究生，主要研究方向為圖像信息處理與檢索。