蟻群算法在路徑優化問題的應用研究

楊娜+馬惠鋮+薛靈芝

摘 要：蟻群算法是根據自然界中蟻群覓食行為而提出的一種智能優化算法，是一種可以尋找最優路徑的概率型算法，具有自組織、正反饋、魯棒性強等特點，具備全局搜索能力，被廣泛應用于各種路徑優化問題。本文介紹蟻群算法的來源、核心思想以及基本最優路徑的搜索過程，并分析蟻群算法在各個領域中路徑優化問題的應用技術。

關鍵詞：蟻群算法；智能算法；路徑優化；應用

DOI：10.16640/j.cnki.37-1222/t.2017.08.209

1 蟻群算法

螞蟻是一種生物個體，覓食過程中可以在其經過的路徑上留下一種物質，稱為信息素，并在覓食過程中能夠感知信息素的強度，以此指導自己的行動方向。蟻群總是朝著信息素濃度高的方向移動，以較高的概率搜索出一條信息素濃度較高的路徑，從而得到一條最佳的路徑。

根據螞蟻“尋找食物”的群體行為，意大利學者Dorigo M等最早提出蟻群算法的基本模型，并闡述了蟻群算法的核心思想。該算法中螞蟻需要具備三種智能行為，分別是螞蟻互相通信是通過信息素，螞蟻會在經過的路徑上釋放信息素，其他螞蟻根據信息素濃度選擇路徑；螞蟻具有一定記憶能力，其選擇過一次的路徑不會被再次選擇，可由禁忌表模擬；蟻群活動，在某一路徑上行走的螞蟻越多，留下的信息素濃度越大，該路徑被選擇的概率也就越大，越利于選擇出最優路徑。

蟻群算法的最優路徑搜索過程是：初始化，將若干只螞蟻隨機放置到若干個地點，并為每條路徑設定相等的信息素初始值；更新禁忌表，每當螞蟻走過一個地點，將該地點編號添加至禁忌表中，以防止螞蟻走重復的路徑；確定行走方向，根據轉移概率公式，計算轉移概率，從而選擇出螞蟻下一個要訪問的地點；計算信息素增量，每只螞蟻完成一次周游之后，計算每只螞蟻走過的路徑長度，保存最短路徑，并且根據每只螞蟻在經過邊的信息素釋放量，更新每條邊上的信息素，則路徑長度最短的路徑各邊信息素濃度更大，從而該路徑在之后迭代中被選擇的概率也就越大；判斷終止準則，螞蟻完成一次循環后，會將禁忌表清空，重新回到初始地點，進行下一次周游，以此循環，直到螞蟻的周游次數滿足停止準則，得到最優路徑。

2 蟻群算法在路徑優化問題的應用

蟻群算法是一種自組織、正反饋、魯棒性較強的算法，通過人工螞蟻釋放信息素相互通信，信息素越多的路徑被選擇的概率越大，從而使得蟻群自發地不斷接近于最優解，從而尋找到最優路徑，具有全局搜索能力，因此被廣泛應用在各種路徑優化問題。從大量文獻看出，學者將蟻群算法不斷改進，使蟻群算法在路徑優化問題上的應用涉及社會各個方面，包括物流配送、居民出行、避災逃生、農業應用、智能機器人等領域。

在物流配送方面，涉及到應急物流、醫療器械運送、快遞配送、糧食輸送、礦山運輸等。其中，文獻[1]提出了基于主次種群蟻群算法的物流配送車輛的路徑優化方法，針對主次種群蟻群算法前期信息素積累較慢的缺點，分別使用路徑去交叉算法和節約策略進行改進，以陜西省西安市某快遞公司物流配送為例，仿真證明改進的主次種群蟻群算法在解決該快遞物流問題上有明顯優勢。文獻[2]采用了一種改進的蟻群算法進行醫療器械物流配送的路徑優化，將免疫算法與傳統蟻群算法相結合，具有更快的收斂速度、更短的搜索時間，實驗仿真證明免疫蟻群算法的路徑優化結果優于傳統蟻群算法。在應急運輸車輛路徑優化問題中，一種改進的蟻群算法針對地震、泥石流、洪水等應急條件下的路況不穩定，加入動態路況因子，仿真使用21個真實城市作為應急情況下的貨物供應點和需求點，證明了該算法可有效解決應急物流分配問題。

在居民出行方面，文獻[3]研究了一種基于蟻群優化的居民公交出行路徑選擇算法，根據城市公交系統，設計基于蟻群算法的居民出行的公交最優路徑選擇模型，當乘客設定起點終點后，自動為乘客配置出最優的公交路徑方案，并驗證了該算法的準確性和有效性。

在避災逃生方面，學者將蟻群算法應用到了大型公共建筑火災的智能逃生路徑規劃研究中，在此加入螞蟻體力值，使螞蟻尋找最優路徑同時也考慮到火災發生時各種復雜的風險因素，以降低人員傷亡率，仿真表明改進后的蟻群算法不僅可以適應危險環境，而且滿足實時計算的收斂性需求。

在農業應用方面，一種節水灌溉路徑優化方案提出了采用信息素優化的改進蟻群算法進行灌溉路徑優化設計，該方案以田間地塊坐標作為數據源，采用改進的蟻群算法對田間地塊布線路徑進行設計，最終可以在相同的迭代次數內找到路徑更短、代價更小的節水灌溉管線路徑[4]。

在智能機器人方面，一種動態搜索策略的蟻群算法應用在了機器人路徑規劃中，其通過新的動態搜索誘導算子來改進蟻群算法性能，為增加種群的多樣性，在初期設定較大閾值；進化過程中為加快收斂速度，動態調整較小閾值，實驗結果表明該改進蟻群算法的收斂速度高，且解的質量得到優化，將其應用在復雜環境下的機器人路徑規劃問題，驗證出較好的實際應用效果。

3 結束語

蟻群算法是一種集群智能算法，模擬蟻群覓食原理，某路徑上人工螞蟻釋放的信息素越多，被螞蟻選擇的概率會越大，由此不斷接近并找到最優路徑。本文總結了蟻群算法針對路徑優化問題在社會各個領域中已有的應用研究，該算法可以結合其它智能算法與技術，實現更加復雜的多因素路徑優化問題。

參考文獻

[1]康燕妮.基于主次種群蟻群算法的物流配送車輛路徑優化研究[D].西安建筑科技大學，2015（06）.

[2]費騰，張立毅，韓應征，張錦.免疫蟻群算法在常規醫療器械配送路徑優化中的應用[J].天津商業大學學報，2010（03）.

[3]林泉，基于蟻群優化的居民公交出行路徑選擇算法及仿真研究[D].華南理工大學，2010（06）.

[4]鄧蕾蕾，于合龍，于亞洲，張獻，基于蟻群算法的農業節水灌溉路徑優化部署[J].吉林農業大學學報，2012（04）.