智能螞蟻算法應(yīng)用的最新進(jìn)展

王培博

摘要：螞蟻算法是一種新型的集群智能算法，它的主要特點(diǎn)有智能搜索、全局優(yōu)化、魯棒性強(qiáng)、正反饋機(jī)制、分布式計(jì)算，可以解決一些復(fù)雜問(wèn)題，比如二次任務(wù)指派、組合優(yōu)化、車(chē)輛路由、有序排列和車(chē)間任務(wù)調(diào)度等。本文介紹了螞蟻算法在國(guó)內(nèi)的工業(yè)生產(chǎn)、國(guó)防安全、交通運(yùn)輸、旅游、能源、農(nóng)業(yè)科技、信息軟件等各個(gè)領(lǐng)域的最新應(yīng)用進(jìn)展。

關(guān)鍵詞：智能算法； 集群智能； 螞蟻算法； 螞蟻網(wǎng)絡(luò)算法

中圖分類(lèi)號(hào)：TP18 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2017）04-0183-03

Latest Progress of Smart Ant Colony Algorithm Application

WANG Pei-bo

（Yangcun High School of Wuqing District， Tianjin 301700， China）

Abstract： The ant colony algorithm as one of most promising swarm intelligence algorithms， has attracting characters， such as intelligent search， global optimization， strong robustness， positive feedback mechanism， and distributed computing. It provides a resolution to complicated problems， Quadratic Assignment Problem （QAP）， Combinatorial Optimization Problem （COP）， Vehicle Routing Problem （VRP）， Sequential Ordering Problem （SOP）， Job-shop Scheduling Problem （JSP）， etc. The latest progress of smart ant colony algorithm application is introduced， including industrial production， national security， traffic and transportation， tourism， energy， agriculture and information technology field.

Key words：intelligent algorithm； swarm Intelligence； ant colony algorithm； ant net algorithm；

1 概述

螞蟻算法是20世紀(jì)90年代初提出的模擬螞蟻覓食行為的內(nèi)在機(jī)制來(lái)求解復(fù)雜問(wèn)題的方法。螞蟻覓食行過(guò)程中，通過(guò)整體協(xié)作總能發(fā)現(xiàn)從蟻巢到食物源的最短路徑。研究發(fā)現(xiàn)：螞蟻能夠通過(guò)一種稱(chēng)為揮發(fā)的“信息素”的機(jī)制來(lái)傳遞信息。螞蟻在尋找食物源的路徑上會(huì)釋放一定量的信息素，后續(xù)其它螞蟻可以感知信息素濃度，優(yōu)先選擇信息素濃度高的路徑。螞蟻到達(dá)終點(diǎn)以后會(huì)馬上返回，螞蟻來(lái)單程往返的時(shí)間越短，重復(fù)頻率越高，灑下的信息素也會(huì)越多，在單位時(shí)間會(huì)則有更多的螞蟻選擇這條路徑。螞蟻以信息素作為媒介實(shí)現(xiàn)了群體內(nèi)部的間接通信，依賴(lài)自身催化與正向反饋的機(jī)制可以最終發(fā)現(xiàn)覓食的最短路徑。

2 螞蟻算法的數(shù)學(xué)本質(zhì)

如圖1所示，螞蟻算法運(yùn)行機(jī)制的精髓有三點(diǎn)：1）信息素的更新機(jī)制，包括信息素的累積量、信息素的揮發(fā)量、信息素更新的時(shí)間切入點(diǎn)等；2）路徑的選擇機(jī)制，包括螞蟻選路的前提、依據(jù)等；3）信息的傳遞機(jī)制，采用一種外激勵(lì)方式類(lèi)似“黑板系統(tǒng)”，可以保證螞蟻間的溝通、協(xié)作。這些機(jī)制的共同作用使得螞蟻算法有很強(qiáng)的求解能力。

圖 1 螞蟻覓食過(guò)程

螞蟻算法本質(zhì)上是一種仿生學(xué)的集群智能算法，若干低智能的個(gè)體通過(guò)相互之間的簡(jiǎn)單合作，能達(dá)到集體的、系統(tǒng)性的智能行為。它的典型技術(shù)特點(diǎn)有：1）分布式控制，沒(méi)有中心控制，個(gè)體間通過(guò)非直接通信的方式進(jìn)行信息傳遞，從而達(dá)到合作的目的；2）個(gè)體簡(jiǎn)單智能，遵循的行為規(guī)則也非常簡(jiǎn)單，不需要整體復(fù)雜運(yùn)算，體現(xiàn)的系統(tǒng)集群智能；3）擴(kuò)充性好，個(gè)體數(shù)目可以增加，通過(guò)增加小幅的通信開(kāi)銷(xiāo)實(shí)現(xiàn)搜索范圍的加大；4）每個(gè)個(gè)體都能夠改變環(huán)境，通過(guò)局部最優(yōu)達(dá)到全局最優(yōu)，最終呈現(xiàn)系統(tǒng)的自組織性；5）系統(tǒng)魯棒性強(qiáng)，不會(huì)由于某個(gè)個(gè)體的故障而影響集群的最終整體表現(xiàn)。螞蟻算法的這些特點(diǎn)，有助于解決一些復(fù)雜的問(wèn)題，比如二次任務(wù)指派、組合優(yōu)化、車(chē)輛路由、有序排列和車(chē)間任務(wù)調(diào)度問(wèn)題等。

3 螞蟻算法的最新應(yīng)用

3.1在工業(yè)生產(chǎn)領(lǐng)域

有人將螞蟻算法理論應(yīng)用在在優(yōu)化打孔機(jī)作業(yè)路徑的應(yīng)用中，為該工業(yè)的優(yōu)化生產(chǎn)效能提供了參考與建議[1]；有人將螞蟻算法應(yīng)用在車(chē)身底板焊接路徑規(guī)劃中，找出了車(chē)身底板焊接路徑的最優(yōu)解，可以縮短焊槍的行走路程，提高了焊接的生產(chǎn)效率[2]。

有人利用模擬退火混合螞蟻算法嘗試解決OEM 協(xié)作生產(chǎn)環(huán)境生產(chǎn)管理問(wèn)題，建立了一個(gè)帶能力約束的、以總訂單利潤(rùn)與準(zhǔn)時(shí)交貨為目標(biāo)的多目標(biāo)的OEM訂單分配模型，可以讓品牌制造商將不同生產(chǎn)任務(wù)合理分配給眾多協(xié)作供應(yīng)商[3]。有人將螞蟻算法應(yīng)用在選煤廠(chǎng)產(chǎn)品結(jié)構(gòu)優(yōu)化中，結(jié)合生產(chǎn)流程建立了產(chǎn)品結(jié)構(gòu)優(yōu)化數(shù)學(xué)模型，得到了滿(mǎn)足各種約束條件下的各產(chǎn)品的最佳產(chǎn)量，提高了產(chǎn)品的生產(chǎn)率[4]。

有人采用改進(jìn)螞蟻算法對(duì)低速直線(xiàn)電機(jī)的結(jié)構(gòu)進(jìn)行了優(yōu)化，提高了電機(jī)的電磁性能[5]。有人將螞蟻算法應(yīng)用在變風(fēng)量空調(diào)控制系統(tǒng)中，提高了系統(tǒng)的穩(wěn)定性以及自適應(yīng)性，提升了動(dòng)態(tài)響應(yīng)速度，獲得了更小的超調(diào)量[6]。有人提出了一種基于蟻群聚類(lèi)算法神經(jīng)網(wǎng)絡(luò)溫度補(bǔ)償方法，解決了對(duì)壓力傳感器的溫度漂移的補(bǔ)償問(wèn)題[7]。

3.2在國(guó)防系統(tǒng)領(lǐng)域

有人提出了基于“輪盤(pán)式選擇策略、精英策略以及路徑優(yōu)化策略”的改進(jìn)螞蟻算法，并引入反艦導(dǎo)彈航路規(guī)劃中，縮小了航路規(guī)劃的最大搜索范圍，縮短了最優(yōu)航路長(zhǎng)度，提高了航路搜索的收斂速度[8]。

有人將螞蟻算法應(yīng)用在戰(zhàn)損裝備搶修任務(wù)指派中，結(jié)合戰(zhàn)時(shí)裝備保障情況和戰(zhàn)損裝備搶修任務(wù)特點(diǎn)，建立了不同緊急度下的裝備搶修任務(wù)指派模型，可以有效實(shí)施戰(zhàn)損裝備應(yīng)急搶修任務(wù)的指派，提升了智能決策[9]。

3.3在交通運(yùn)輸領(lǐng)域

有人提出了混合粒子群的螞蟻算法，可以誘導(dǎo)車(chē)輛在城市交通路網(wǎng)中規(guī)劃較優(yōu)出行路線(xiàn)，提高了出行質(zhì)量，并建立出城市道路權(quán)值模型[10]；有人改進(jìn)了現(xiàn)有螞蟻算法的參數(shù)設(shè)置及信息更新機(jī)制，應(yīng)用到飛行路徑模型中，確保了飛機(jī)周期性返回檢修機(jī)場(chǎng)，實(shí)現(xiàn)周期性檢修[11]；有人在GIS 中應(yīng)用螞蟻算法，可以有效解決路徑尋優(yōu)和正射影像鑲嵌線(xiàn)自動(dòng)選擇問(wèn)題[12]。

3.4 在旅游與公共安全領(lǐng)域

有人采用螞蟻算法較好地解決了旅游景區(qū)車(chē)輛路徑問(wèn)題，降低了運(yùn)輸成本[13]；有人將螞蟻算法用于無(wú)人駕駛智能車(chē)的路徑尋優(yōu)，采用虛擬路徑應(yīng)用于動(dòng)態(tài)路徑規(guī)劃，滿(mǎn)足了車(chē)載系統(tǒng)的一些實(shí)時(shí)性和可行性要求[14]；有人將螞蟻算法應(yīng)用在道路應(yīng)急疏散策略選擇中，基于疏散車(chē)輛交通流和非疏散交通流的不確定性，建立帶有區(qū)間參數(shù)的機(jī)會(huì)約束規(guī)劃模型，可以有效縮短突發(fā)事件后車(chē)輛的應(yīng)急疏散時(shí)間[15]。

3.5在能源領(lǐng)域

在超高壓輸電線(xiàn)路故障測(cè)距引入螞蟻算法，可以來(lái)求解故障測(cè)距方程，算法測(cè)距精度高，不需要選擇故障類(lèi)型，有很強(qiáng)的實(shí)用價(jià)值[16]。有人將加權(quán)改進(jìn)的螞蟻算法應(yīng)用在電網(wǎng)系統(tǒng)優(yōu)化中，避免了提早陷入局部極優(yōu)值，提高了收斂速度和計(jì)算準(zhǔn)確度，并可以進(jìn)一步降低網(wǎng)絡(luò)損耗[17]。

基于螞蟻算法正反饋性、并行性等優(yōu)勢(shì)，有人提出了混沌螞蟻算法，優(yōu)化了水庫(kù)發(fā)電調(diào)度模型[18]。有人將螞蟻算法應(yīng)用在泵站優(yōu)化調(diào)度運(yùn)行問(wèn)題，在保證運(yùn)行可靠性的前提下，提高了能源的利用率[19]。

有人將改進(jìn)螞蟻算法應(yīng)用在地下礦山運(yùn)輸路徑優(yōu)化中，提出以電機(jī)車(chē)總運(yùn)輸距離為目標(biāo)函數(shù)，礦石接收點(diǎn)和溜井?dāng)?shù)目為變量的運(yùn)輸路徑優(yōu)化模型，得到最佳的運(yùn)輸路徑[20]。有人提出了一種動(dòng)態(tài)自適應(yīng)的螞蟻算法，并把算法應(yīng)用于煤炭運(yùn)輸優(yōu)化中，可以有效地節(jié)省運(yùn)輸費(fèi)用，提高運(yùn)輸效率[21]。

3.6 在農(nóng)業(yè)生產(chǎn)領(lǐng)域

有人將蟻群灰色神經(jīng)網(wǎng)絡(luò)模型預(yù)測(cè)水稻稻瘟病[22]；有人將螞蟻算法應(yīng)用在蘋(píng)果糖度近紅外光譜分析波長(zhǎng)選擇中，針對(duì)蘋(píng)果近紅外光譜數(shù)據(jù)的特點(diǎn)，建立了一種基于串聯(lián)雙通路構(gòu)建圖的波長(zhǎng)變量選擇模型，提高了蘋(píng)果糖度定量分析模型的準(zhǔn)確性和可靠性[23]。

3.7 在信息應(yīng)用領(lǐng)域

有人提出了基于信息素?cái)U(kuò)散模型的螞蟻算法，并用應(yīng)用在虛擬現(xiàn)實(shí)系統(tǒng)中的碰撞檢測(cè)中，通過(guò)手術(shù)中手術(shù)器械與人體的碰撞反映的仿真，驗(yàn)證了算法的效率和精確度[24]。有人將改良螞蟻算法用于圖像檢測(cè)中，可以有效提取含一定噪聲的低對(duì)比度圖像邊緣[25]。有人將螞蟻算法應(yīng)用在計(jì)算機(jī)病毒檢測(cè)方面，可以降低漏警率和虛警率的發(fā)生，提高病毒檢測(cè)軟件對(duì)病毒檢測(cè)的效能[26]。有人將蟻群聚類(lèi)算法應(yīng)用在教學(xué)評(píng)價(jià)系統(tǒng)中，從原始教學(xué)評(píng)價(jià)的數(shù)據(jù)中提取出有用信息，分析同類(lèi)課程的特點(diǎn)，為這類(lèi)課程評(píng)價(jià)、提高教學(xué)效果提供支持[27]。

4 總結(jié)

螞蟻算法是一種新型的基于仿生學(xué)原理的集群智能算法，本質(zhì)上也是一種模擬進(jìn)化算法。螞蟻間信息的傳遞沒(méi)有采用直接方式，而是通過(guò)駐留在路徑上的信息素得到指示，這種間接信息交流的方式稱(chēng)為外激勵(lì)，外激勵(lì)類(lèi)似黑板指示系統(tǒng)。螞蟻本身的智能較小，比較適合網(wǎng)絡(luò)云化后的移動(dòng)計(jì)算。螞蟻算法的主要特點(diǎn)：智能搜索、全局優(yōu)化、魯棒性強(qiáng)、正反饋機(jī)制、分布式計(jì)算，而且易與其他算法相結(jié)合，可以采用模擬蟻群的協(xié)作行為解決一些復(fù)雜的問(wèn)題，比如二次任務(wù)指派、組合優(yōu)化、圖著色、車(chē)輛路由、有序排列和車(chē)間任務(wù)調(diào)度問(wèn)題等，僅在我國(guó)國(guó)內(nèi)就廣泛應(yīng)用在工業(yè)生產(chǎn)、國(guó)防安全、交通運(yùn)輸、旅游、信息、能源、農(nóng)業(yè)科技、信息軟件等各個(gè)領(lǐng)域，結(jié)合未來(lái)的大數(shù)據(jù)分析，將有更為廣闊的應(yīng)用前景。

參考文獻(xiàn)：

[1] 李韻，李婧騫，林晨光，等.蟻群算法理論及其在優(yōu)化打孔機(jī)作業(yè)路徑的應(yīng)用[J].科技創(chuàng)新導(dǎo)報(bào)2012，（36）： 221-222

[2] 林巨廣，陳甦欣，戴淮初，黃文進(jìn).蟻群算法在白車(chē)身底板焊接路徑規(guī)劃中的應(yīng)用[J].焊接學(xué)報(bào)，2015，35（01）： 5-9

[3] 韓錦東，李英俊，陳志祥.帶能力約束的多目標(biāo)OEM協(xié)作生產(chǎn)訂單分配決策與混合蟻群算法應(yīng)用研究[J].中國(guó)機(jī)械工程，2012，23（22）： 2714-2719.

[4] 孫偉，王宜雷，王慧，等.蟻群算法在選煤廠(chǎng)產(chǎn)品結(jié)構(gòu)優(yōu)化中的應(yīng)用[J].工礦自動(dòng)化，2012，（7）： 52-54.

[5] 魏華生，程志平，焦留成，等.改進(jìn)的蟻群算法在低速永磁直線(xiàn)電機(jī)設(shè)計(jì)中的應(yīng)用[J].微電機(jī)，2013，46（1）：9-12.

[6] 姚瑤，李曼珍.蟻群算法在變風(fēng)量空調(diào)控制系統(tǒng)中的應(yīng)用研究及仿真[J].工業(yè)控制計(jì)算機(jī)，2014，27（8）：70 -71.

[7] 孫艷梅，都文和，馮昌浩，等.基于蟻群聚類(lèi)算法的RBF神經(jīng)網(wǎng)絡(luò)在壓力傳感器中的應(yīng)用[J].傳感技術(shù)學(xué)報(bào)，2013，26（6）： 806-809.

[8] 高曼，劉以安，張強(qiáng).優(yōu)化蟻群算法在反艦導(dǎo)彈航路規(guī)劃中的應(yīng)用[J].計(jì)算機(jī)應(yīng)用，2012，32（9）：2530-2533.

[9] 蔡紀(jì)偉，賈云獻(xiàn)，孫曉，等.蟻群算法在戰(zhàn)損裝備搶修任務(wù)指派中的應(yīng)用研究[J].數(shù)學(xué)的實(shí)踐與認(rèn)識(shí)，2012，42（19）：160-165.

[10] 陳家琪，劉躍.混合蟻群算法在城市交通路徑規(guī)劃中的應(yīng)用[J].計(jì)算機(jī)系統(tǒng)應(yīng)用，2012，21（1）：122-126.

[11] 牟德一，劉金鳳.改進(jìn)的蟻群算法在飛行路徑模型中的應(yīng)用[J].計(jì)算機(jī)工程與科學(xué)，2012，34（6）：137-139.

[12] 歐春江.蟻群算法在GIS中的應(yīng)用探討[J].測(cè)繪與空間地理信息，2013，36（8）：187-193.

[13] 劉倩，衛(wèi)文學(xué)，張魯.改進(jìn)蟻群算法在景區(qū)路徑規(guī)劃中的應(yīng)用研究[J].信息技術(shù)與信息化，2012（6）：56-59.

[14] 譚寶成，宋潔.蟻群算法在無(wú)人駕駛智能車(chē)中的應(yīng)用及改進(jìn)[J].國(guó)外電子測(cè)量技術(shù)，2012，31（9）：15-17.

[15] 毛新華，王建偉，趙京，等.蟻群算法在道路應(yīng)急疏散策略選擇中的應(yīng)用[J].中國(guó)安全科學(xué)學(xué)報(bào)，2014，24（10）：170-176.

[16] 劉迅，黃純.蟻群算法在超高壓輸電線(xiàn)路故障測(cè)距的應(yīng)用[J].電力系統(tǒng)及其自動(dòng)化學(xué)報(bào)，2012，24（05）：132-137.

[17] 姚建紅，張玲玉，孫大興.改進(jìn)多智能體蟻群算法在電力系統(tǒng)無(wú)功優(yōu)化中的應(yīng)用[J].化工自動(dòng)化及儀表，2014，41（5）：520-523.

[18] 原文林，曲曉寧.混沌蟻群優(yōu)化算法在梯級(jí)水庫(kù)發(fā)電優(yōu)化調(diào)度中的應(yīng)用研究[J].水力發(fā)電學(xué)報(bào)，2013，32（3）：47–53.

[19] 袁堯，劉超.蟻群算法在泵站單機(jī)組優(yōu)化運(yùn)行中的應(yīng)用[J].水力發(fā)電學(xué)報(bào)，2013，32（1）：263-268.

[20] 周科平，翟建波.改進(jìn)蟻群算法在地下礦山運(yùn)輸路徑優(yōu)化的應(yīng)用[J].中南大學(xué)學(xué)報(bào)：自然科學(xué)版，2014，45（1）：257-261.

[21] 魏星，李志遠(yuǎn)，李燕.改進(jìn)型蟻群算法在煤炭運(yùn)輸中的應(yīng)用研究[J].煤礦機(jī)械，2013，33（07）：208-209.

[22] 劉坤，錢(qián)永德，張福軍.蟻群灰色神經(jīng)網(wǎng)絡(luò)模型在稻瘟病預(yù)測(cè)中的應(yīng)用[J].自動(dòng)化儀表，2013，34（2）： 30-33.

[23] 陳鑫，劉飛.蟻群算法在蘋(píng)果糖度近紅外光譜分析波長(zhǎng)選擇中的應(yīng)用[J].分析試驗(yàn)室，2013，32（10）：50-53.

[24] 陳莉芝.基于優(yōu)化的蟻群算法在碰撞檢測(cè)中的應(yīng)用研究[J].電腦知識(shí)與技術(shù)，2012，8（28）： 6758-6760.

[25] 殷小莉，黃曉彤，鄭曉霞，等.蟻群算法在低對(duì)比度圖像邊緣檢測(cè)中的應(yīng)用[J].計(jì)算機(jī)技術(shù)與發(fā)展，2013，23（5）：180-183.

[26] 朱俚治.蟻群算法在檢測(cè)病毒上的應(yīng)用[J].計(jì)算機(jī)安全，2014（9）：17-20.

[27] 朱福珍，薛景.蟻群聚類(lèi)算法在高職院校教學(xué)評(píng)價(jià)系統(tǒng)中的應(yīng)用研究[J].江蘇第二師范學(xué)院學(xué)報(bào)，2014，30（8）：93-96.