王培博

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

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

中圖分類號：TP18 文獻標識碼：A 文章編號：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世紀90年代初提出的模擬螞蟻覓食行為的內(nèi)在機制來求解復雜問題的方法。螞蟻覓食行過程中，通過整體協(xié)作總能發(fā)現(xiàn)從蟻巢到食物源的最短路徑。研究發(fā)現(xiàn)：螞蟻能夠通過一種稱為揮發(fā)的“信息素”的機制來傳遞信息。螞蟻在尋找食物源的路徑上會釋放一定量的信息素，后續(xù)其它螞蟻可以感知信息素濃度，優(yōu)先選擇信息素濃度高的路徑。螞蟻到達終點以后會馬上返回，螞蟻來單程往返的時間越短，重復頻率越高，灑下的信息素也會越多，在單位時間會則有更多的螞蟻選擇這條路徑。螞蟻以信息素作為媒介實現(xiàn)了群體內(nèi)部的間接通信，依賴自身催化與正向反饋的機制可以最終發(fā)現(xiàn)覓食的最短路徑。

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

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

圖 1 螞蟻覓食過程

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

3 螞蟻算法的最新應用

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

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

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

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

3.2在國防系統(tǒng)領域

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

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

3.3在交通運輸領域

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

3.4 在旅游與公共安全領域

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

3.5在能源領域

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

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

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

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

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

3.7 在信息應用領域

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

4 總結(jié)

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

參考文獻：

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

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

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

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

[5] 魏華生，程志平，焦留成，等.改進的蟻群算法在低速永磁直線電機設計中的應用[J].微電機，2013，46（1）：9-12.

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

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

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

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

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

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

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

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

[14] 譚寶成，宋潔.蟻群算法在無人駕駛智能車中的應用及改進[J].國外電子測量技術(shù)，2012，31（9）：15-17.

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

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

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

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

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

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

[21] 魏星，李志遠，李燕.改進型蟻群算法在煤炭運輸中的應用研究[J].煤礦機械，2013，33（07）：208-209.

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

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

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

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

[26] 朱俚治.蟻群算法在檢測病毒上的應用[J].計算機安全，2014（9）：17-20.

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