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

1、基于信息素更新和揮發(fā)因子調(diào)整改進(jìn)蟻群算法張永強(qiáng) 王曉東（西安工程大學(xué) 理學(xué)院，陜西 西安 710048）摘要：基本蟻群算法存在易陷入局部最優(yōu)解、收斂速度慢等缺點(diǎn)，本文運(yùn)用正負(fù)反饋調(diào)節(jié)信息素增量大小，并將信息素?fù)]發(fā)因子隨機(jī)化，使得蟻群算法自動(dòng)調(diào)整路徑上的信息素量.改進(jìn)后的蟻群算法運(yùn)用到31個(gè)城市的TSP線路優(yōu)化中，改進(jìn)蟻群算法比基本蟻群算法(15602)得到更優(yōu)路徑長度為15483.關(guān)鍵詞：蟻群算法；信息素；TSP中圖分類號：TP312 文獻(xiàn)標(biāo)志碼：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)解，搜索時(shí)間長等缺點(diǎn)，近年來學(xué)者們做了大量工作.為了克服算法停滯現(xiàn)象，限制了殘留信息量，德國學(xué)者Thomas sttzle與Jolger Hoos提出了最大最小蟻群系統(tǒng)算法1，將各條路徑上的信息素濃度限制在一定的范圍內(nèi)，避免某條路徑的信息量遠(yuǎn)大于其他路徑，使螞蟻過于集中.針對蟻群算法存在的搜索時(shí)間長、易限于局部最優(yōu)解等缺陷

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

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

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

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

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

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

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

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

13、種算法均運(yùn)行10次，運(yùn)行結(jié)果見表1，其中基本蟻群算法運(yùn)行最優(yōu)結(jié)果見圖1，改進(jìn)蟻群算法運(yùn)行最優(yōu)結(jié)果見圖2，最優(yōu)結(jié)果迭代圖見圖3.表1 兩種算法運(yùn)行10次結(jié)果對比（路徑總長度）Table 1 Both algorithms run 10 times results contrast (total path length)序號 基本蟻群算法 改進(jìn)蟻群算法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；改進(jìn)蟻群算法最優(yōu)路徑長度為15483，平均路徑長度為15618.改進(jìn)蟻群算法比基本蟻群算法能夠找到更短的路徑.100015002000250030003500400045005001000150020002500300035004000 14121311231656724891031817192425202122262827303129115圖1 基本蟻群算法運(yùn)行圖Fig.1 Basic ant colony algorithm diagram在圖1中，用基本蟻群算法求

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

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

17、路徑長度，但它找到的最優(yōu)路徑長度比基本蟻群算法找到的最優(yōu)路徑長度更優(yōu).4 結(jié)論路徑優(yōu)化問題是人們外出旅游線路考慮的現(xiàn)實(shí)問題，本文通過利用正負(fù)反饋機(jī)制改進(jìn)信息素增量和揮發(fā)因子隨機(jī)化改進(jìn)基本蟻群算法，并用改進(jìn)的蟻群算法對31個(gè)節(jié)點(diǎn)的TSP路線進(jìn)行路徑優(yōu)化，實(shí)驗(yàn)結(jié)果表明，改進(jìn)的蟻群算法比基本蟻群算法得到了較優(yōu)路徑.本文改進(jìn)的蟻群算法對求解路徑優(yōu)化問題具有一定的參考價(jià)值.參考文獻(xiàn)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劉瑞杰，胡小兵.基于動(dòng)態(tài)調(diào)節(jié)信息素增量的蟻群算法J. 計(jì)算機(jī)應(yīng)用研究，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孟祥萍，片兆宇，沈中玉等.基于方向信息素協(xié)調(diào)的蟻群算法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張家善，王志宏.基于信息素的改進(jìn)蟻群算法及其在TSP中的應(yīng)用J.數(shù)學(xué)的實(shí)踐與認(rèn)識，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)國，田其沖，張磊.基于信息素強(qiáng)度的改進(jìn)蟻群算法J.計(jì)算機(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ìn)蟻群算法J.計(jì)算機(jī)應(yīng)用研究，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柳長安，鄢小虎，劉春陽等，基于改進(jìn)蟻群算法的移動(dòng)機(jī)器人動(dòng)態(tài)路徑規(guī)劃方法J.電子學(xué)報(bào)，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.吉林大學(xué)學(xué)報(bào)，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張 毅，賀興時(shí)，楊新社. 基于模擬退火與高斯擾動(dòng)的布谷鳥算法J.紡織高?；A(chǔ)科學(xué)學(xué)報(bào)，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īng)混沌差分進(jìn)化的粒子群優(yōu)化算法J.紡織高?；A(chǔ)科學(xué)學(xué)報(bào)，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ìn)J.計(jì)算機(jī)應(yīng)用，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張志協(xié)，曹陽.基于改進(jìn)型蟻群算法的最優(yōu)路徑問題求解J.計(jì)算機(jī)系統(tǒng)應(yī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ìn)研究J.電子設(shè)計(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