蟻群算法在路徑優(yōu)化問題的應用研究

1、    蟻群算法在路徑優(yōu)化問題的應用研究    楊娜+馬惠鋮+薛靈芝摘 要：蟻群算法是根據(jù)自然界中蟻群覓食行為而提出的一種智能優(yōu)化算法，是一種可以尋找最優(yōu)路徑的概率型算法，具有自組織、正反饋、魯棒性強等特點，具備全局搜索能力，被廣泛應用于各種路徑優(yōu)化問題。本文介紹蟻群算法的來源、核心思想以及基本最優(yōu)路徑的搜索過程，并分析蟻群算法在各個領域中路徑優(yōu)化問題的應用技術(shù)。關(guān)鍵詞：蟻群算法；智能算法；路徑優(yōu)化；應用doi：10.16640/ki.37-1222/t.2017.08.2091 蟻群算法螞蟻是一種生物個體，覓食過程中可以在其經(jīng)過的路徑上留下一種物質(zhì)，稱

2、為信息素，并在覓食過程中能夠感知信息素的強度，以此指導自己的行動方向。蟻群總是朝著信息素濃度高的方向移動，以較高的概率搜索出一條信息素濃度較高的路徑，從而得到一條最佳的路徑。根據(jù)螞蟻“尋找食物”的群體行為，意大利學者dorigo m等最早提出蟻群算法的基本模型，并闡述了蟻群算法的核心思想。該算法中螞蟻需要具備三種智能行為，分別是螞蟻互相通信是通過信息素，螞蟻會在經(jīng)過的路徑上釋放信息素，其他螞蟻根據(jù)信息素濃度選擇路徑；螞蟻具有一定記憶能力，其選擇過一次的路徑不會被再次選擇，可由禁忌表模擬；蟻群活動，在某一路徑上行走的螞蟻越多，留下的信息素濃度越大，該路徑被選擇的概率也就越大，越利于選擇出最優(yōu)路徑

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

4、直到螞蟻的周游次數(shù)滿足停止準則，得到最優(yōu)路徑。2 蟻群算法在路徑優(yōu)化問題的應用蟻群算法是一種自組織、正反饋、魯棒性較強的算法，通過人工螞蟻釋放信息素相互通信，信息素越多的路徑被選擇的概率越大，從而使得蟻群自發(fā)地不斷接近于最優(yōu)解，從而尋找到最優(yōu)路徑，具有全局搜索能力，因此被廣泛應用在各種路徑優(yōu)化問題。從大量文獻看出，學者將蟻群算法不斷改進，使蟻群算法在路徑優(yōu)化問題上的應用涉及社會各個方面，包括物流配送、居民出行、避災逃生、農(nóng)業(yè)應用、智能機器人等領域。在物流配送方面，涉及到應急物流、醫(yī)療器械運送、快遞配送、糧食輸送、礦山運輸?shù)取Ｆ渲?，文獻1提出了基于主次種群蟻群算法的物流配送車輛的路徑優(yōu)化方法，針

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

6、，文獻3研究了一種基于蟻群優(yōu)化的居民公交出行路徑選擇算法，根據(jù)城市公交系統(tǒng)，設計基于蟻群算法的居民出行的公交最優(yōu)路徑選擇模型，當乘客設定起點終點后，自動為乘客配置出最優(yōu)的公交路徑方案，并驗證了該算法的準確性和有效性。在避災逃生方面，學者將蟻群算法應用到了大型公共建筑火災的智能逃生路徑規(guī)劃研究中，在此加入螞蟻體力值，使螞蟻尋找最優(yōu)路徑同時也考慮到火災發(fā)生時各種復雜的風險因素，以降低人員傷亡率，仿真表明改進后的蟻群算法不僅可以適應危險環(huán)境，而且滿足實時計算的收斂性需求。在農(nóng)業(yè)應用方面，一種節(jié)水灌溉路徑優(yōu)化方案提出了采用信息素優(yōu)化的改進蟻群算法進行灌溉路徑優(yōu)化設計，該方案以田間地塊坐標作為數(shù)據(jù)源，采

7、用改進的蟻群算法對田間地塊布線路徑進行設計，最終可以在相同的迭代次數(shù)內(nèi)找到路徑更短、代價更小的節(jié)水灌溉管線路徑4。在智能機器人方面，一種動態(tài)搜索策略的蟻群算法應用在了機器人路徑規(guī)劃中，其通過新的動態(tài)搜索誘導算子來改進蟻群算法性能，為增加種群的多樣性，在初期設定較大閾值；進化過程中為加快收斂速度，動態(tài)調(diào)整較小閾值，實驗結(jié)果表明該改進蟻群算法的收斂速度高，且解的質(zhì)量得到優(yōu)化，將其應用在復雜環(huán)境下的機器人路徑規(guī)劃問題，驗證出較好的實際應用效果。3 結(jié)束語蟻群算法是一種集群智能算法，模擬蟻群覓食原理，某路徑上人工螞蟻釋放的信息素越多，被螞蟻選擇的概率會越大，由此不斷接近并找到最優(yōu)路徑。本文總結(jié)了蟻群算法針對路徑優(yōu)化問題在社會各個領域中已有的應用研究，該算法可以結(jié)合其它智能算法與技術(shù)，實現(xiàn)更加復雜的多因素路徑優(yōu)化問題。參考文獻1康燕妮.基于主次種群蟻群算法的物流配送車輛路徑優(yōu)化研究d.西安建筑科技大學，2015（06）.2費騰，張立毅，韓應征，張錦.免疫蟻群算法在常規(guī)醫(yī)療器械配送路徑優(yōu)化中的應用j.天津商業(yè)大學學報，2010