基于信息素更新和揮發(fā)因子調整改進蟻群算法

1、基于信息素更新和揮發(fā)因子調整改進蟻群算法張永強 王曉東（西安工程大學 理學院，陜西 西安 710048）摘要：基本蟻群算法存在易陷入局部最優(yōu)解、收斂速度慢等缺點，本文運用正負反饋調節(jié)信息素增量大小，并將信息素揮發(fā)因子隨機化，使得蟻群算法自動調整路徑上的信息素量.改進后的蟻群算法運用到31個城市的TSP線路優(yōu)化中，改進蟻群算法比基本蟻群算法(15602)得到更優(yōu)路徑長度為15483.關鍵詞：蟻群算法；信息素；TSP中圖分類號：TP312 文獻標志碼：AImproved ant colony optimization algorithm based onpheromone updating and

2、 evaporationfactor adjusting ZHANG Yong-qiang , WANG Xiao-dong(School of Science, Xian Polytechnic University, Xian 710048, China) Abstract: The basic ant colony algorithm converges slowly, is prone to plunge into partial optimum and results in search stagnation. In this paper, an improved ant colon

3、y algorithm is proposed. New algorithm introduces positive and negative feedback regulation of pheromone increment size, and the pheromone evaporation factor randomized to adjust the amount of pheromone on the path. The simulation results of traveling salesman problem show that improved algorithm ha

4、s been better path length is 15438 than the basic ant colony algorithm(15602).Key words: ant colony algorithm; pheromone; TSP針對蟻群算法易陷于局部最優(yōu)解，搜索時間長等缺點，近年來學者們做了大量工作.為了克服算法停滯現象，限制了殘留信息量，德國學者Thomas sttzle與Jolger Hoos提出了最大最小蟻群系統(tǒng)算法1，將各條路徑上的信息素濃度限制在一定的范圍內，避免某條路徑的信息量遠大于其他路徑，使螞蟻過于集中.針對蟻群算法存在的搜索時間長、易限于局部最優(yōu)解等缺陷

5、，劉瑞杰，胡小兵2提出基于動態(tài)調節(jié)信息素增量的蟻群算法；孟祥萍，片兆宇，沈中玉等3提出了基于方向信息素協調的蟻群算法；張家善，王志宏4引入信息素調節(jié)系數，提出了基于信息素的改進蟻群算法及其在TSP中的應用；鄭衛(wèi)國，田其沖，張磊5對螞蟻進行區(qū)分，控制信息素濃度，提出了基于信息素強度的改進蟻群算法；侯文靜，馬永杰等6提出了一種改進的蟻群算法，通過在初始化信息素矩陣中采用候選節(jié)點列表減少劣質解，在局部搜索中采用聚類進行二次搜索，縮小了算法的搜索范圍、改善了解空間的質量，提基金項目：陜西省教育廳專項科研計劃項目， 14JK1299作者簡介： 張永強(1989-)，男，陜西省寶雞市人，碩士，研究方向：智

6、能算法，E-mail:akuzyq. 王曉東(1974-)，女，陜西省咸陽市人，副教授，碩士生導師，E-mail:wangxiaodong1225.高了搜索速度；柳長安，鄢小虎等7提出了根據目標點自適應調整啟發(fā)函數，提高算法的收斂速度，借鑒狼群分配原則對信息素進行更新，避免搜索陷入局部最優(yōu)；申銥京，劉陽陽等8提出了一種改進的蟻群算法，改進算法采用信息素揮發(fā)因子自適應調整機制，調節(jié)算法收斂速度，保證算法的全局搜索能力等.算法改進工作主要是從全局搜索能力9、收斂速度以及精度10等方面進行改進；蟻群算法的改進，大量是從蟻群算法的路徑選擇11-12、信息素更新準則13、局部搜索與全局搜索14-16等方

7、面做了改進.本文針對基本蟻群算法存在易陷入局部最優(yōu)解、收斂速度慢等缺點，通過比較當前路徑長度與平均路徑長度大小，若當前路徑長度小于平均路徑長度，則運用正反饋調節(jié)信息素增量；若當前路徑長度大于平均路徑長度，則運用負反饋調節(jié)信息素增量；并用(0,1)上的一個隨機變量代替信息素揮發(fā)因子，使得蟻群算法自動調整路徑上的信息素量，進而改進蟻群算法，并將改進后的蟻群算法運用到TSP路徑優(yōu)化中，得到了比基本蟻群算法更優(yōu)的路徑.1 蟻群算法蟻群算法是由意大利學者Dorigo M等在20世紀90年代初提出的一種新型的模擬進化算法17-18.每只螞蟻開始搜索時是從任意一個節(jié)點出發(fā)，在時刻以概率選擇下一個節(jié)點，此概率

8、計算公式如(1)式所示： (1)其中表示的是信息素的重要程度，表示的是啟發(fā)因子的重要程度，表示的是指沒有訪問過的節(jié)點，表示在時刻第只螞蟻在節(jié)點選擇節(jié)點的概率，表示路徑上的啟發(fā)因子；表示在路徑上留下的信息素大小，在節(jié)點每被訪問一次，都會以一定的方式更新，信息素的表達式為： (2)其中表示信息素的揮發(fā)因子，初始時刻，隨后按(8)式變化： = (3)其中表示一次旅游結束后螞蟻目前訪問的總路徑長度，是常量.2 蟻群算法的改進2.1 對選擇信息素增量的改進信息素增量直接影響路徑上信息素量的大小，而路徑上的信息素量直接影響蟻群算法的收斂速度.為了使后來螞蟻在搜索過程中避免重復走以前螞蟻所走過較長距離的路徑

9、從而提高蟻群算法的收斂速度，本文通過正負反饋對信息素增量進行改進：若當前螞蟻搜索路徑長度小于以前所有螞蟻搜索路徑長度的平均值，則加強當前路徑上信息素的增量(即正反饋)，使后來螞蟻進行搜索時要在該路徑基礎上找到比其更優(yōu)的路徑；若當前螞蟻搜索路徑長度大于以前所有螞蟻搜索路徑長度的平均值，則減弱當前路徑上信息素的增量(即負反饋)，使后來螞蟻進行搜索時撇棄該路徑.故對信息素增量改進如下： (4)其中表示信息素增量，為第次搜索經過路徑的總長度，表示在第次搜索之前搜索過的所有路徑的平均長度，表示信息素的揮發(fā)因子，是常量.2.2 對揮發(fā)因子的改進揮發(fā)因子的大小也是影響路徑上的信息素量大小的重要因素，從而影響

10、蟻群算法的全局搜索能力和收斂速度.在傳統(tǒng)蟻群算法中，揮發(fā)因子是(0, 1)上的一個常數，如果給定的過大，則路徑上的信息素量減少，導致算法收斂速度降低，但可以使螞蟻遍歷所有路徑，有助于螞蟻找到全局最優(yōu)路徑；若給定的偏小，路徑上的信息素量將增大，使算法急劇收斂，雖節(jié)約了算法的搜索時間，但可能導致算法陷入局部搜索.這種在“探索”和“利用”之間很難找到一種理想的平衡，使得蟻群算法在搜索過程中既避免出現停滯又能具有較強的全局搜索能力.所以為了達到此種平衡去尋找合適的信息素揮發(fā)因子，取是(0, 1)上的一個隨機變量，即0與1之間任意的一個數.若取大了有助于全局搜索；若取小了有利于加快收斂速度；這樣隨機改變

11、著路徑上的信息素量，經過一定的迭代，可以找到全局最優(yōu)解.對揮發(fā)因子改進如下： (5)2.3 算法實現按照以上的改進來確定搜索步驟，每次搜索開始時，在路徑節(jié)點處隨機放置只螞蟻.搜索開始后，每只螞蟻遍歷所有節(jié)點；在每次迭代過程中找到最優(yōu)解，迭代完成時，每次迭代得到的最優(yōu)解組成優(yōu)解池，在優(yōu)解池中找到全局最優(yōu)解.算法步驟如下：Step 1：初始化蟻群算法中的參數，設置迭代計數器初始值；Step 2：隨機選擇每只螞蟻的初始位置，初始化禁忌表；Step 3：只螞蟻按概率函數(1)式選擇下一個節(jié)點，將所選節(jié)點添加到中； Step 4：若禁忌表未滿轉至Step 3，若已滿，得出螞蟻此次的最優(yōu)路徑長度，并且更新

12、的值，并記錄本次迭代最佳路線；Step 5：按(2)式更新信息素，其中信息素增量按(4)式更新，揮發(fā)因子按(5)式確定，禁忌表清零；Step6：判斷迭代次數是否滿足條件，若滿足，則迭代次數，并轉至Step 2，開始新一輪的迭代，若不滿足，轉至Step 7；Step 7：算法結束，輸出最優(yōu)路徑長度.3 用改進蟻群算法求解TSP為了測試改進后的蟻群算法的可行性，選取網絡公布的Benchmark31作為測試數據，對TSP路線優(yōu)化和仿真，用基本蟻群算法和改進后的蟻群算法對其求解.在Windows7環(huán)境下，運用Matlab7.0語言編程，算法參數選擇如下：，取迭代次數250為終止條件，螞蟻個數為31，兩

13、種算法均運行10次，運行結果見表1，其中基本蟻群算法運行最優(yōu)結果見圖1，改進蟻群算法運行最優(yōu)結果見圖2，最優(yōu)結果迭代圖見圖3.表1 兩種算法運行10次結果對比（路徑總長度）Table 1 Both algorithms run 10 times results contrast (total path length)序號 基本蟻群算法 改進蟻群算法1 15602 155502 15829 156023 15973 155904 15602 156025 15948 155746 15818 155907 15884 154838 15948 155929 15772 1596010 15602

14、 15632平均路徑長度 15798 15618由表1可以看出基本蟻群算法最優(yōu)路徑長度為15602，平均路徑長度為15798；改進蟻群算法最優(yōu)路徑長度為15483，平均路徑長度為15618.改進蟻群算法比基本蟻群算法能夠找到更短的路徑.100015002000250030003500400045005001000150020002500300035004000 14121311231656724891031817192425202122262827303129115圖1 基本蟻群算法運行圖Fig.1 Basic ant colony algorithm diagram在圖1中，用基本蟻群算法求

15、得該TSP線路優(yōu)化問題的最短距離為15602，最優(yōu)解路徑為14121311231656724891031817192425202122262827303129115.10001500200025003000350040004500500100015002000250030003500400031293027282625242021221831719231165164289107131214151圖2 改進的蟻群算法運行圖Fig.2 Improved ant colony algorithm Graph在圖2中，用改進后的蟻群算法求得該TSP線路優(yōu)化問題的最短距離為15483，最優(yōu)解路徑為312

16、93027282625242021221831719231165164289107131214151.0501001502002501.51.551.61.651.71.751.81.85x 104基本蟻群算法改進蟻群算法迭代次數路徑長度圖3算法迭代圖Fig.3 Iterative Algorithm Figure圖3為基本蟻群算法與改進蟻群算法的迭代圖，圖中虛線表示基本蟻群算法最優(yōu)路徑長度與迭代次數之間的關系，實線表示改進蟻群算法最優(yōu)路徑長度與迭代次數之間的關系.從圖3中可以看出改進蟻群算法迭代曲線最低點在基本蟻群算法迭代曲線最低點的下方，雖然改進蟻群算法在迭代次數較大的情況下找到了全局最優(yōu)

17、路徑長度，但它找到的最優(yōu)路徑長度比基本蟻群算法找到的最優(yōu)路徑長度更優(yōu).4 結論路徑優(yōu)化問題是人們外出旅游線路考慮的現實問題，本文通過利用正負反饋機制改進信息素增量和揮發(fā)因子隨機化改進基本蟻群算法，并用改進的蟻群算法對31個節(jié)點的TSP路線進行路徑優(yōu)化，實驗結果表明，改進的蟻群算法比基本蟻群算法得到了較優(yōu)路徑.本文改進的蟻群算法對求解路徑優(yōu)化問題具有一定的參考價值.參考文獻1 Stutzle T, Hoos H. MAX-Min ant system and local search for the traveling salesman problem C/ Proceedings of the

18、 1997 IEEE International Conference on Evolutionary Computation, Indianapolis. USA: IEEE, 1997: 309-314.2劉瑞杰，胡小兵.基于動態(tài)調節(jié)信息素增量的蟻群算法J. 計算機應用研究，2012,29(1):135-151.LIU Ruijie,HU Xiaobing. Ant colony algorithm based on dynamic adjustment of incremental of pheromoneJ. Application Research of Computers, 201

19、2,29(1):135-151.3孟祥萍，片兆宇，沈中玉等.基于方向信息素協調的蟻群算法J.控制與決策，2013,28(5):782-786.MENG Xiangping, PIAN Zhaoyu, SHEN Zhong-yu,etal .Ant algorithm based on direction-coordinatingJ. Control and Decision, 2013,28(5):782-786.4張家善，王志宏.基于信息素的改進蟻群算法及其在TSP中的應用J.數學的實踐與認識，2013,43(22):157-160.ZHANG Jiashan, WANG Zhihong.I

20、mproved Ant Colony Algorithm Based on Pheromone and Application in the TSPJ. Mathematics in Practice and Theory, 2013,43(22):157-160.5鄭衛(wèi)國，田其沖，張磊.基于信息素強度的改進蟻群算法J.計算機仿真，2010,27(7):191-193.ZHENG Weiguo，TIAN Qithong, ZHANG Lei. An Improved Ant Colony Algorithm Based on PheromoneJ.Computer Simulation, 20

21、10,27(7):191-193.6侯文靜，馬永杰，張燕等，求解TSP的改進蟻群算法J.計算機應用研究，2010,27(6):2087-2089.HOU Wenjing,MA Yongjie,ZHANG Yan,etal.Improved ant colony algorithm for solving TSPJ. Application Research of Computers, 2010,27(6):2087-2089.7柳長安，鄢小虎，劉春陽等，基于改進蟻群算法的移動機器人動態(tài)路徑規(guī)劃方法J.電子學報，2011,39(5):1220-1224.LIU Chang,YAN Xiaohu,

22、 LIU Chunyang,etal. Dynamic Path Planning for Mobile Robot Based on Improved Ant Colony Optimization AlgorithmJ. Acta Electronica Sinica, 2011,39(5):1220-1224.8申銥京，劉陽陽，黃永平等，求解TSP問題的快速蟻群算法J.吉林大學學報，2013,43(1):147-151.SHEN Xuanjing,LIU Yangyang, HUANU Yongping,etal.Fast ant colony algorithm for solving

23、 traveling salesman problemJ. Journal of Jilin University, 2013,43(1):147-151.9張 毅，賀興時，楊新社. 基于模擬退火與高斯擾動的布谷鳥算法J.紡織高?；A科學學報，2015，28(04)：515-521.ZHANG Yi，HE Xingshi，YANG Xinshe. A Cuckoo Search Algorithm based on Simulated Annealing and gaussian disturbanceJ. Basic Sciences Journal of Textile Universit

24、ies，2015，28(4)：515-521.10劉召軍，高興寶. 融合自適應混沌差分進化的粒子群優(yōu)化算法J.紡織高?；A科學學報，2015，(1)：116-123.LIU Zhaojun， GAO Xingbao.  Particle Swarm Optimization Algorithm by integrating adaptive chaos differential evolutionJ. Basic Sciences Journal of Textile Universities，2015，(1)：116-123.11姜坤霖，李美安，張宏偉.面向旅行商問題的蟻

25、群算法改進J.計算機應用，2015,35(S2):114-117.JIANG Kunlin，LI Mei'an，ZHANG Hongwei.Improved ant colony algorithm for travelling salesman problemJ. Journal of Computer Applications, 2015,35(S2):114-117.12張志協，曹陽.基于改進型蟻群算法的最優(yōu)路徑問題求解J.計算機系統(tǒng)應用，2012,21(10):76-80.ZHANG Zhixie, CAO Yang.Solving Optimal Path Problem B

26、ased on Improved Ant Colony AlgorithmJ. Computer Systems & Applications, 2012,21(10):76-80.13王寶生，屈寶存.蟻群算法在求解TSP問題中的改進研究J.電子設計工程，2014,22(22):14-18.WANG Baosheng,QU Baocun.The improvement of ant colony algorithm in solving TSPJ. Electronic Design Engineering ,2014,22(22):14-18.14Akihiro Uchida,  Yasuaki Ito,  Koji Nakano. Accelerating ant colony optimisation for the travelling s