蟻群算法在交通尋路中的應用

師揚松 成都市實驗外國語學校西區2019屆

1 引言

蟻群優化（Ant colony optimization，ACO）是一種模仿螞蟻覓食行為的智能仿生算法[1]。蟻群釋放特殊的化學物質信息素來傳達信息，并通過感知信息素濃度來選擇前進道路。通過研究這種行為，結合實際場景，可以解決很多難題并大大提高效率。蟻群算法是一種用來尋找優化路徑的概率型算法[2-7]。這種算法具有分布計算、信息正反饋和啟發式搜索的特征，本質上是一種啟發式全局優化算法。蟻群算法已經在組合優化、函數優化、網絡路由、機器人路徑規劃、數據挖掘以及大規模集成電路的綜合布線設計等領域獲得了廣泛的應用，并取得了較好的效果[8]。例如，在[9]中將蟻群算法的正反饋思想與分布式計算應用到概率路由中，收集機會網絡的節點和拓撲信息，并結合這些信息，設計基于蟻群算法的概率路由，可以提高機會網絡的消息傳輸性能。[10]中提出的改進的蟻群聚類算法應用在了學生成績評價中，基于實驗數據，得到了聚類結果，并對聚類分析的結果做出相應解釋，提出了針對性的策略和建議，證明了改進的蟻群聚類算法的有效性。蟻群算法可以高效的向用戶提供最優路徑，但是現有研究中蟻群算法收斂速度較慢而且容易發生停滯，一些文章中通過改進蟻群算法，來彌補這些缺陷從而達到很好的效果[11-14]。例如，根據A*算法的啟發式信息改進蟻群算法的路徑選擇策略，加快算法收斂速度[15]。

本文基于蟻群算法的優點，將其應用于一個簡易交通尋路模型中，為此模型提供一種快速尋路解決方法。該模型為一個點對點三條通路的模型，通過設置不同的站點人員數目和不同的節點之間的時間開銷來實現不同的交通路況。從該模型中抽象出一個站點人員數矩陣和一個節點間的時間開銷矩陣，輸出這兩個矩陣來觀察算法的運算情況。通過設置相同的矩陣數據，對比常規方法與應用螞蟻算法后的時間開銷，最終證明應用算法后可以大大提高交通效率。該算法優點在于可以根據模型不同變量生成一種尋路花費時間最短的方案算法。在本文中第三部分通過與常規算法相比，證明了其可以大大減少時間開銷提高效率。在小區、游樂園或者大學校園的觀光車或通勤車有很大的應用空間。

2 算法原理

首先，本文中提出了一個簡易的通勤車模型。模型中從起點Q到終點S有三條互不相通的路。三條路上設置不同的站點數目、每個站點等待人員數目和站與站之間的間距。將模型抽象成兩個矩陣，一個站點人員數目矩陣和一個時間開銷矩陣。通過觀察兩個矩陣的數據變化可以驗證算法的優劣。三條路上規定必有三輛車分別通過，接送人員。在每輛車通過本車路段到達終點后會釋放信息素。通過不同的信息素起點安排合適數目的車輛進入相應路段。

圖1 算法流程圖

當每輛車到達站點后根據車上的空余座位和站點人數作對比，可得出離開站點所剩人員和空車位數目。到終點后發出信息素，依據濃度判斷派出車輛數目，直到每個站點人員接送完畢。算法的流程圖如圖1所示。

每個站點之間都有不同的時間開銷，在一個設定好的模型里，即間距和人員分布一樣，在應用本文提出的算法和普通情況下做出對比。本文算法可以大大提高效率。此模型雖然簡單，但是有很多應用，除了在小區校區通勤車的尋路中應用外，還可以在游戲中使用。是一個非常實用的算法模型。

3 仿真實現

按上述流程圖，用Dev-C++實現算法，創建一個簡易交通模型如圖2所示。通過常規方案可以得出初始的總時間開銷。然后在同樣的模型下應用螞蟻算法后得出的時間開銷會小很多。通過數據對比，可以證明應用了提出的算法后可以大大提高尋路的效率。

圖2 簡易交通模型圖。

在仿真中輸出了常規算法下設置的站點數、站點間開銷站點人員數目和每個時間點通過站點后的人員分布結果與總時間開銷如圖3所示。此處使用矩陣形式展示。并且在每個時間單位都會輸出站點人

圖3 常規算法下的仿真結果

員矩陣，實時觀察矩陣變化，直到人員接送完畢為止。最后算法出總時間開銷。在輸入設置過程中，因為矩陣定義的是三行四列矩陣，可以在某個點設置為0，同樣對應的時間開銷設置成0，這樣可以表示此處沒有站點，并不消耗空余座位和時間開銷。在關于路程或之間開銷上，每條路上的車通過所有站點到達終點后就會將人員送下車。此時車上全部是空余座位，如果沒有結束運送，則車會從終點返回起始點，同起始點按照算法安排的車一起進入尋路中。從終點到起點的返回車輛所花費的開銷會根據設置的站點間距不同而不同，相當于是原路返回。如此可以較為完善的模擬實際過程中的交通情況。

圖4所示為應用螞蟻算法后的仿真結果。同樣的模型下最后總的時間開銷應用算法后比應用常規方法要少很多。這證明了應用螞蟻算法后可以大大提高效率。

圖4 改進算法后的仿真結果

4 總結

本文基于蟻群算法的優點，通過在一個簡易通勤車尋路模型中實際使用并仿真驗證，應用蟻群算法后可以提高效率。為此模型提供一種快速尋路解決方法。該模型雖然簡單，但是在很多實際應用中都會存在。而該算法優點在于可以根據模型不同變量生成一種尋路花費時間最短的方案算法。在小區、游樂園或者大學校園的觀光車或通勤車有很大的應用空間。

而為了檢驗本文提出的算法，本文所做模型是從實際生活中抽象出的簡易模型。模型可以做出更進一步的改進，使路況復雜化。在路與路之間做聯通路徑結合成網狀，這樣產生的路就會變得多樣化、復雜化，從起始點到終點的路不再單一。而且車輛的分配也不會按照單線路運行。通過判斷信息素的濃度和當前路線的狀況，排列每種路線的優先級，使就近的車輛跨線到另外一條路線，先完成優先級高的路線。以上都是點對點的情況，這種模型不僅適合于交通或者游戲模型，同時也可以模擬點對點通信。假如將終點設置為多個，則會變成一對多的情況，假如應用蟻群算法在樹形結構中收索，同時每個節點設置不同權重，每個節點之間設置不同開銷，就是該模型該進程一對多的情況。更進一步可以設置為多對多模型、三維立體模型，不同模型可以用于不同實際情況，可以分析或實用在生活生產中。

[1]王藝睿.蟻群算法在動態優化問題上的應用研究[D].東華大學，2017.

[2]游戲引擎最短路徑搜索優化遺傳算法設計[J].黎忠文，覃志東，王全宇，倪仲余.計算機應用研究.2014(01).

[3]Dijkstra算法中的多鄰接點與多條最短路徑問題[J].王樹西，李安渝.計算機科學.2014(06).

[4]喻環.改進蟻群算法在機器人路徑規劃上的應用研究[D].安徽大學，2017.

[5]劉建華，楊建國，劉華平，耿鵬，高蒙.基于勢場蟻群算法的移動機器人全局路徑規劃方法[J].農業機械學報，2015，46(09)：18-27.

[6]基于Laguerre圖的自優化A-Star無人機航路規劃算法[J].魏瑞軒，許卓凡，王樹磊，呂明海.系統工程與電子技術.2015(03).

[7]遺傳算法改進策略研究[J].夏季.信息與電腦(理論版).2012(11).

[8]楊劍峰.蟻群算法及其應用研究[D].浙江大學，2007.

[9]賈磊磊.機會網絡中基于蟻群算法的概率路由的設計與實現[D].內蒙古大學，2017.

[10]周穎.基于蟻群算法的聚類分析在學生成績中的研究[D].南昌大學，2015.

[11]張家善.基于改進蟻群算法的物流配送車輛路徑優化研究[D].遼寧工程技術大學，2014.

[12]曹潔，耿振節.一種改進蟻群算法在撿球機器人多目標路徑規劃中的應用[J].小型微型計算機系統，2015，36(10)：2384-2389.

[13]左敏，許華榮.基于改進蟻群算法的智能小車路徑規劃[J].心智與計算，2011，5(02)：60-68

[14]裴振兵，陳雪波.改進蟻群算法及其在機器人避障中的應用[J].智能系統學報，2015，10(01)：90-96.

[15]張志協，曹陽.基于改進型蟻群算法的最優路徑問題求解[J].計算機系統應用，2012，21(10)：76-80.