微正則退火的雙向蟻群優(yōu)化算法*

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

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

微正則退火的雙向蟻群優(yōu)化算法*

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

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

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

關(guān)鍵詞：雙向蟻群算法； 微正則退火算法； 大規(guī)模； 全局最優(yōu)解

0引言

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

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

1旅行商問題求解模型

旅行商問題是近代組合優(yōu)化領(lǐng)域的一個典型難題，現(xiàn)實生活中的網(wǎng)絡(luò)通信問題、交通調(diào)度問題、電路板鉆孔問題和郵路問題等都可以轉(zhuǎn)化為旅行商問題，這些問題本身就是旅行商問題或者可以直接轉(zhuǎn)化為旅行商問題的原型。旅行商問題一直是測試組合優(yōu)化新算法的標(biāo)準(zhǔn)問題。

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

2蟻群算法

2.1蟻群算法思想

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

2.2螞蟻系統(tǒng)

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

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

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

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

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

(1)

在自然環(huán)境中，可揮發(fā)物質(zhì)的濃度越大，揮發(fā)系數(shù)也越大，因此,可以根據(jù)路徑上信息素的多少來調(diào)整揮發(fā)系數(shù)的大小，使其符合自然規(guī)律，可以避免信息素堆積的現(xiàn)象，增強(qiáng)后期算法的啟發(fā)性，所有最短路徑的信息素更新方式

(2)

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

3.2微正則退火算法

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

3.3算法的實現(xiàn)過程

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

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

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

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

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

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

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

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

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

③若L

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

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

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

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

8)循環(huán)，直到i>N即遍歷完S中的所有結(jié)果。

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

②重復(fù)如下步驟，直到j(luò)>jmax,即執(zhí)行完2-opt的所有可能變換。

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

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

c.如果連續(xù)若干次拒絕新解，將狀態(tài)回溯，重新移動。

9)輸出最優(yōu)結(jié)果。

4算法仿真

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

首先利用Matlab仿真隨機(jī)生成30個點代表目的旅行城市，然后計算各座城市的小生境窗口并利用雙向蟻群算法尋找最優(yōu)路徑，如果尋優(yōu)過程出現(xiàn)停滯，就以蟻群算法的結(jié)果作為微正則退火算法的初始解空間，繼而退火尋找最優(yōu)結(jié)果路徑，避免系統(tǒng)陷入局部最優(yōu)。圖1為使用雙向蟻群微正則退火算法得到的30座城市的旅行商問題優(yōu)化的結(jié)果圖，圖示的結(jié)果最短路徑：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。由圖可知，該算法得到的是最優(yōu)的路線圖。

圖1　30座城市旅行商問題優(yōu)化結(jié)果Fig 1　Optimization results of traveling salesman problem of 30 cities

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

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

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

5結(jié)束語

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

參考文獻(xiàn):

[1]王沛棟.改進(jìn)蟻群算法及在路徑規(guī)劃問題的應(yīng)用研究[D].青島：中國海洋大學(xué)，2012.

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

[3]段海濱，馬冠軍，王道波,等.一種求解連續(xù)空間優(yōu)化問題的改進(jìn)蟻群算法[J].系統(tǒng)仿真學(xué)報，2007，19(5)：974-977.

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

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

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

[7]李敬花.遺傳蟻群融合算法求解多項目資源能力平衡問題[J].計算機(jī)集成制造系統(tǒng)，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].河北工業(yè)大學(xué)學(xué)報，2010，39(2)：48-51.

[12] 徐暢.大規(guī)模路網(wǎng)下基于蟻群微正則退火算法的路徑優(yōu)化方法研究[D].長春：吉林大學(xué)，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

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

中圖分類號：TP 301.6

文獻(xiàn)標(biāo)識碼：A

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

作者簡介:

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