動態(tài)蟻群算法用于洪災搜救問題

摘 要： 蟻群算法是一種求解最優(yōu)路徑的常用算法，其利用自然界中蟻群的活動規(guī)律和正反饋原理。動態(tài)的蟻群算法針對基本蟻群算法存在的問題和缺點進行改進，采用動態(tài)參數因子，可以有效避免搜索的局部最優(yōu)和進化停滯現象，并且能夠提高搜索效率。通過實驗結果對比，該算法在求解最短路徑方面具有更高的精確度，為今后的搜救問題提供了一種高效實用的參考方法。

關鍵字： 洪災搜救； 蟻群算法； 動態(tài)參數因子； 信息素

中圖分類號： TN911?34； TP18 文獻標識碼： A 文章編號： 1004?373X（2013）23?0113?02

Application of dynamic ant colony algorithm in flood rescue

ZHANG Cong， QU Wei?ping

（School of Computer Science and Engineering， Anhui University of Science and Technology， Huainan 232001， China）

Abstract： Ant colony algorithm， using the positive feedback principle and the activity rhythm of ant colony in nature， is one of commonly used algorithms for finding the optimal path. Dynamic ant colony algorithm has improved the problems and disadvantages existing in basic ant colony algorithm， the local optimal search and evolutionary stagnation phenomenon can be effectively avoided by using dynamic parameter factors， and the search efficiency can be improved. By comparison with the experimental results， the algorithm has higher accuracy in finding the shortest path， which provides an efficient and practical reference method for the future search problems.

Keywords： flood rescue； ant colony algorithm； dynamic parameter factors； sociohormone

0 引 言

洪災是威脅人民生命和財產安全的重大自然災害之一，因此，如何快速有效地搜救洪水中被困群眾成為一個重要課題[1]。

在洪災搜救問題中，需要根據被困人員的地理位置、救援站點位置等信息，制定救援路線，即最短搜索路徑[2]。

1 洪災搜救問題

在洪水暴發(fā)之前，當地群眾接到有關部門的預警信息，并撤離到某地勢較高的安全地帶，但仍有少量群眾被困。考慮到救援船只數量和油料有限并且救援時間緊迫，因此，救援人員采用最短搜索回路。蟻群算法就是一種求解最短路徑的常用算法，但基本蟻群算法存在一些問題，比如，搜索時間過長，搜索停滯現象，本文提出使用一種動態(tài)信息素濃度的蟻群算法，并討論了其在求解最短路徑問題中的優(yōu)越性。

2 蟻群算法（AS）

2.1 算法思想

以[n]城市TSP問題為例來說明蟻群系統(tǒng)模型。設[m]為蟻群中螞蟻的數量；[ηij（i，j=1，2，…，n）]表示城市節(jié)點[i]與城市節(jié)點[j]之間的距離的倒數，[τij（t）]表示[t]時刻在[ij]連線上殘留的信息量。初始時刻，設[τij（0）=C][（C]為常數）。螞蟻[k（k=1，2，…，m）]在運動過程中，根據[pkij（t）]決定轉移到下一城市節(jié)點[3]。

[pkij（t）=ταijηβij（t）ταijηβij（t），j∈allowed0，其他] （1）

式中：allowed={0，1，…，n-1}表示螞蟻k下一步允許選擇的城市。經過n個時刻完成一次循環(huán)，各路徑上信息量要根據下式進行調整：

[τij（t+n）=ρ?τij（t）+ΔτijΔτij=k=1mΔτkij] （2）

[Δτkij=QLk，若第k只螞蟻經過ij0，其他]

式中：[Q]是常數；[Lk]表示第[k]只螞蟻在一次循環(huán)中走過的路徑長度。參數[Q，α，β，ρ]可以用實驗方法確定最優(yōu)組合[4]。

人工蟻群系統(tǒng)使用tabu（k）記錄螞蟻k走過的節(jié)點，停止條件使用固定循環(huán)次數或當進化趨勢不再明顯時停止運算。

2.2 算法流程

蟻群算法分為ant?cycle system， ant?quantity system以及 ant?density system三種算法，以ant?cycle system 算法效果最好。圖1給出了ant?cycle system 算法框圖[5]。

圖1 Ant?cycle system算法框圖

3 動態(tài)蟻群算法

3.1 信息及啟發(fā)因子

現實世界中蟻群的活動會隨著時間推移而對環(huán)境不再敏感，這樣信息素的影響就會減小，同時，啟發(fā)函數的影響相對加大[6?7]。在算法中就體現為參數[α，β]成為與時間相關的函數。本文根據參數的最優(yōu)組合[4]，在這里令[α=1，β]隨著迭代過程而變化：在迭代的前[N3]次內[β=5；][N3]～[N2]次內[β=4；][N2]～[2N3]次內[β=3；][2N3]～[N]次內[β=2。]其中，[N=m*n]表示總迭代次數。

3.2 揮發(fā)因子

動態(tài)蟻群算法中，信息素濃度高的節(jié)點，揮發(fā)速度快，反之，揮發(fā)速度慢，這樣就可以有效防止信息素的無限積累或減少為零。揮發(fā)因子[ρ]就成了信息素濃度[τ]的函數[8]。本文所用揮發(fā)函數如圖2所示。

3.3 多路徑信息素更新

AS僅對最短路徑上的信息素進行更新，只有一只螞蟻對全局信息素的更新有影響。如果同時有多只螞蟻對不同路徑的全局信息素的更新產生影響，就可以加快搜索進程[9?10]。

本文對兩只螞蟻所爬過的路徑上的信息素進行更新，對最優(yōu)和最差路徑上的信息素進行全局更新，更新規(guī)則如下：

[Δτ（i，j）=Lgb-1，if（i，j）∈global_best_tourLgw-1，if（i，j）∈global_worst_tour] （3）

圖2 揮發(fā)函數

3.4 實驗結果

實驗使用一組30個村莊的模擬坐標數據，搜救隊員從救援點出發(fā)，遍歷30個村莊，搜索并營救被困群眾，最后回到救援點，坐標為（1 336，695）。

實驗中選擇的參數初始值如下：[m=]30，[α=1，][β=]0.5，[ρ=]0.1，最大迭代次數為1 000次。計算結果與AS算法進行比較，搜索路徑如圖3所示，采用AS算法的最短路徑長度為16.853 km，而動態(tài)蟻群算法的最短路徑長度為16.106 km。

圖3 動態(tài)蟻群算法與AS搜索路徑的比較

4 結 語

本文根據洪災搜救中的時間緊、設備有限等因素，提出使用改進的動態(tài)蟻群算法計算最短搜救回路，確保使用最短路程和在最短時間內將被困人員救往安全地帶。針對基本蟻群算法中存在的過早收斂和局部最優(yōu)問題，動態(tài)蟻群算法采用動態(tài)確定的目標城市標準和揮發(fā)函數。實驗數據表明，動態(tài)修改啟發(fā)因子和揮發(fā)系數對提高算法性能十分關鍵，下一步的研究工作就是動態(tài)因子的組合優(yōu)化，提高算法效率。

參考文獻

[1] 毛德華，何梓霖，賀新光，等.洪災風險分析的國內外研究現狀與展望[J].自然災害學報，2009，18（1）：139?149.

[2] 李守英，馬祖軍，鄭斌，等.洪災被困人員搜救問題的集成優(yōu)化研究[J].系統(tǒng)工程學報，2012，27（3）：287?294.

[3] 郝晉，石立寶，周家啟.求解復雜TSP問題的隨機擾動蟻群算法[J].系統(tǒng)工程理論與實踐，2002（9）：88?91.

[4] 葉志偉，鄭肇葆.蟻群算法中參數[α、][β、][ρ]設置的研究[J].武漢大學學報，2004，29（7）：597?601.

[5] 蔡自興，徐光祐.人工智能及其應用[M].4版.北京：清華大學出版社，2010.

[6] 楊劍鋒.蟻群算法及其應用研究[D].杭州：浙江大學，2007.

[7] 倪應劍，邢漢承，張志政.蟻群算法及其應用研究進展[J].計算機應用與軟件，2008，25（8）：12?16.

[8] 劉好斌，胡小兵，趙吉東.動態(tài)調整路徑選擇的蟻群優(yōu)化算法[J].計算機工程，2010，36（17）：201?203.

[9] DORIGO M， STITZLE T. Ant colony optimization [M]. MA： MIT Press， 2004.

[10] STUTZLE T， HOOS H. MAX?MIN ant system and local search for the traveling salesman problem [C]// Proceedings of the 14th IEEE International Conference on Evolutionary Computation. Washington D C， USA： IEEE， 1997： 309?314.

作者簡介：張 聰 男，1988年出生，碩士研究生。主要研究方向為人工智能應用。

曲衛(wèi)平 男，1954年出生，理學博士，碩士生導師，副教授。主要研究方向為衛(wèi)星探測器光譜分析、地球環(huán)境監(jiān)測等。