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

楊娜+馬惠鋮+薛靈芝

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

關(guān)鍵詞：蟻群算法；智能算法；路徑優(yōu)化；應(yīng)用

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

1 蟻群算法

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

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

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

2 蟻群算法在路徑優(yōu)化問(wèn)題的應(yīng)用

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

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

在居民出行方面，文獻(xiàn)[3]研究了一種基于蟻群優(yōu)化的居民公交出行路徑選擇算法，根據(jù)城市公交系統(tǒng)，設(shè)計(jì)基于蟻群算法的居民出行的公交最優(yōu)路徑選擇模型，當(dāng)乘客設(shè)定起點(diǎn)終點(diǎn)后，自動(dòng)為乘客配置出最優(yōu)的公交路徑方案，并驗(yàn)證了該算法的準(zhǔn)確性和有效性。

在避災(zāi)逃生方面，學(xué)者將蟻群算法應(yīng)用到了大型公共建筑火災(zāi)的智能逃生路徑規(guī)劃研究中，在此加入螞蟻體力值，使螞蟻尋找最優(yōu)路徑同時(shí)也考慮到火災(zāi)發(fā)生時(shí)各種復(fù)雜的風(fēng)險(xiǎn)因素，以降低人員傷亡率，仿真表明改進(jìn)后的蟻群算法不僅可以適應(yīng)危險(xiǎn)環(huán)境，而且滿足實(shí)時(shí)計(jì)算的收斂性需求。

在農(nóng)業(yè)應(yīng)用方面，一種節(jié)水灌溉路徑優(yōu)化方案提出了采用信息素優(yōu)化的改進(jìn)蟻群算法進(jìn)行灌溉路徑優(yōu)化設(shè)計(jì)，該方案以田間地塊坐標(biāo)作為數(shù)據(jù)源，采用改進(jìn)的蟻群算法對(duì)田間地塊布線路徑進(jìn)行設(shè)計(jì)，最終可以在相同的迭代次數(shù)內(nèi)找到路徑更短、代價(jià)更小的節(jié)水灌溉管線路徑[4]。

在智能機(jī)器人方面，一種動(dòng)態(tài)搜索策略的蟻群算法應(yīng)用在了機(jī)器人路徑規(guī)劃中，其通過(guò)新的動(dòng)態(tài)搜索誘導(dǎo)算子來(lái)改進(jìn)蟻群算法性能，為增加種群的多樣性，在初期設(shè)定較大閾值；進(jìn)化過(guò)程中為加快收斂速度，動(dòng)態(tài)調(diào)整較小閾值，實(shí)驗(yàn)結(jié)果表明該改進(jìn)蟻群算法的收斂速度高，且解的質(zhì)量得到優(yōu)化，將其應(yīng)用在復(fù)雜環(huán)境下的機(jī)器人路徑規(guī)劃問(wèn)題，驗(yàn)證出較好的實(shí)際應(yīng)用效果。

3 結(jié)束語(yǔ)

蟻群算法是一種集群智能算法，模擬蟻群覓食原理，某路徑上人工螞蟻釋放的信息素越多，被螞蟻選擇的概率會(huì)越大，由此不斷接近并找到最優(yōu)路徑。本文總結(jié)了蟻群算法針對(duì)路徑優(yōu)化問(wèn)題在社會(huì)各個(gè)領(lǐng)域中已有的應(yīng)用研究，該算法可以結(jié)合其它智能算法與技術(shù)，實(shí)現(xiàn)更加復(fù)雜的多因素路徑優(yōu)化問(wèn)題。

參考文獻(xiàn)

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

[2]費(fèi)騰，張立毅，韓應(yīng)征，張錦.免疫蟻群算法在常規(guī)醫(yī)療器械配送路徑優(yōu)化中的應(yīng)用[J].天津商業(yè)大學(xué)學(xué)報(bào)，2010（03）.

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

[4]鄧?yán)倮伲诤淆?，于亞洲，張獻(xiàn)，基于蟻群算法的農(nóng)業(yè)節(jié)水灌溉路徑優(yōu)化部署[J].吉林農(nóng)業(yè)大學(xué)學(xué)報(bào)，2012（04）.