基于細菌覓食蟻群算法的無人車路徑規(guī)劃

盧泓宇 肖銀寶

摘?要：隨著目前人工智能的日漸普及，無線通信、網絡傳輸和傳感器技術等得到了長足的發(fā)展，人們對機器的自動化智能化要求越來越高。與此同時人們對無人駕駛技術需求越來越高，針對路況及各種可能會出現(xiàn)的異常問題缺少合理高效的路徑優(yōu)化，這使得對路徑規(guī)劃的研究有著重要的意義。對此，本文主要對現(xiàn)有的傳統(tǒng)蟻群算法進行研究，同時考慮到當前傳統(tǒng)蟻群算法的一些缺點，引用細菌覓食算法進行嘗試改進，加深對這兩個算法的認識，并進行歸納總結。

關鍵詞：人工智能；路徑規(guī)劃；無人駕駛；蟻群算法；細菌覓食算法

Path?Planning?of?Unmanned?Vehicle

Based?on?Bacteria?Forageant?Colony?Algorithm

Lu?Hongyu1?Xiao?Yinbao2

1.School?of?Mechanical?and?Electrical?Engineering?and?Automation，?Foshan?University?of?Science?and?Technology

GuangdongFoshan?528225;

2.Songming?County?Bureau?of?Science，Technology?and?Industrial?Information?Technology?YunnanKunming?650000

Abstract：With?the?increasing?popularity?of?artificial?intelligence，wireless?communication，network?transmission?and?sensor?technology?have?been?greatly?developed，and?people?have?higher?and?higher?requirements?for?automation?and?intelligence?of?machines.At?the?same?time，the?demand?for?unmanned?driving?technology?is?getting?higher?and?higher，and?there?is?a?lack?of?reasonable?and?efficient?route?optimization?for?road?conditions?and?various?possible?abnormal?problems，which?makes?the?research?on?route?planning?of?great?significance.In?this?regard，this?paper?mainly?studies?the?existing?traditional?ant?colony?algorithm，and?at?the?same?time，considering?some?shortcomings?of?the?current?traditional?ant?colony?algorithm，references?the?bacterial?foraging?algorithm?to?try?to?improve，deepen?the?understanding?of?the?two?algorithms，and?make?a?summary.

Keywords：artificial?intelligence；path?planning；unmanned?driving；ant?colony?algorithm；bacterial?foraging?algorithm

1?概述

由于人工智能的迅猛發(fā)展，使得無人驅動技術在近幾年得到科研工作者的重視。得力于網絡傳輸、傳感器技術的發(fā)展，路徑規(guī)劃的方案因此更加多樣化，因此本文主要通過細菌覓食算法對蟻群算法的改進來提高路徑規(guī)劃的效率。

2?研究方案

蟻群算法是來源于模擬螞蟻為了生存去尋找所需的補給的行為從中提煉出的一種用來尋求所有路徑中最短路徑的隨機找尋算法。螞蟻通過某種信息機制在尋找食物的路徑上留取信息素，通過不斷迭代，獲得最短路徑。但是隨著對蟻群算法的不斷研究深入，逐漸發(fā)現(xiàn)它的缺陷在不斷擴大，由此需要對其進行優(yōu)化，例如，收斂速度過慢的原因是由于搜索范圍的擴大導致陷入了局部環(huán)境下的最優(yōu)路徑，此時便需要細菌覓食算法的介入進行改進。細菌覓食算法是通過實現(xiàn)人類腸道中大腸桿菌的吞噬食物的行為的一種仿生類優(yōu)化算法。由于蟻群算法有較強的魯棒性，而且相比其他算法，對初始路線要求不高，參數(shù)少設置簡單，便于用于組合性的優(yōu)化問題的求解。而細菌覓食算法中的復制操作與趨向操作適合對蟻群算法進行優(yōu)化，可以提高算法效率，跳出局部最優(yōu)解，獲取全局的搜索能力，使得算法更加精確。

3?傳統(tǒng)蟻群算法實現(xiàn)及其缺點

首先是對初始路徑的選擇。在算法最開始的階段，將一定數(shù)量的螞蟻隨機地放到一些固定數(shù)量的城市，與此同時，將各只螞蟻的記錄表tabu的第一個錨點設定為它目前處于的城市。此時便可以得知各路徑上的信息素量是相等的，接下來將各只螞蟻在路徑上尋找所殘留的信息素量和遺留式信息（就是兩城市之間的距離）不存在干擾的情況下選擇下一座需要尋覓的城市，直到將所有的城市遍歷完成。

pkij=τij（t）α·ηij（t）β∑s∈Jkτis（t）α·ηis（t）β（指數(shù)為兩個經驗系數(shù)）

P=兩城市信息素濃度α·兩城市距離的倒數(shù)β總和（去某一個城市的概率）

其次，便是信息素的增量與蒸發(fā)：

Tau=（1－r）Tau+Q/L

其中Tau是信息素量，r是蒸發(fā)系數(shù)，Q是信息素增量，L是兩城市之間的距離。

在采用傳統(tǒng)蟻群算法解決路徑規(guī)劃問題會有兩個缺點：（1）早期由于各個節(jié)點之間信息濃度較低，蟻群算法又是一個大空間搜索算法，盲目地搜索必然會導致蟻群在初始階段產生大量的無效路徑，問題規(guī)模越大，早期搜索性能越差。（2）傳統(tǒng)蟻群算法的后期開發(fā)能力有限，非常容易陷入局部最優(yōu)的情況。

4?對細菌覓食算法的復制操作的引入

4.1?復制操作的引入

蟻群算法求解旅行商問題的方法如下，開始時有m只螞蟻隨機分布，并且保證沒有螞蟻在同一個位置，蟻群需要經歷n個城市，然后讓螞蟻開始啟動，記錄下每個城市之間的距離，通過公式計算出當時城市之間的信息素濃度。然后在此之后再獨立選取下一座城市，同時記錄下信息素的濃度，在尋求路徑期間記錄下信息素揮發(fā)的狀態(tài)，在經過所有城市后實時更新直至遍歷所有的城市。

在蟻群算法生成解的時間段引入復制操作，而復制操作是指當細菌的生命周期即將結束時，即達到分裂上限，細菌則開始進行繁殖，遵循自然界中優(yōu)勝劣汰的規(guī)則，對那些適應不了環(huán)境的細菌進行淘汰，對那些尋找食物能力比較強的細菌進行復制繁衍。而蟻群算法在蟻群尋訪完所有城市后的時間點，即第一次尋訪完畢后，各只螞蟻都尋求到了專屬自己的對應的路線即無人車行駛的路線。同時各只螞蟻留下的路線則一一對應當前每個細菌的位置，同時記錄下螞蟻所行進的路徑長度，然后我們對所有螞蟻留下的路徑長度進行從長到短的排列，而其中最短的路徑即為我們本次所需要的。而細菌覓食中的復制操作此時開始優(yōu)化，選出其中優(yōu)良適宜的細菌個體（即路線長度相對短的螞蟻）對這些進行復制發(fā)育，同時對那些劣質的細菌進行淘汰（即路線長度過長的螞蟻）。通過上述操作我們優(yōu)化了蟻群算法的收斂速度，以及全局的收斂性。

4.2?復制操作的具體實現(xiàn)

復制操作根據細菌當時得出的適應程度的函數(shù)值，從中選出那些較劣等的細菌去繼承那些優(yōu)秀的細菌的位置及步長。同時為了保持菌群的穩(wěn)定，要讓復制后的細菌數(shù)量和原始的細菌數(shù)量保持一致，同時要記錄當前細菌的成長度，建立一個成長度函數(shù)來記錄。與此同時，我們記錄細菌進行的趨向操作次數(shù)，還有其中具體的趨向操作、復制操作、遷徙操作后的適應程度的函數(shù)數(shù)值，而其中得出數(shù)值越高的細菌則表明這個細菌的尋找食物的能力更加強大。與此同時將細菌的種群按照成長度進行排序，對其中成長度不錯的細菌進行復制和保留，在此期間要保證總體的細菌數(shù)量和初始的一致。當螞蟻尋訪完自己所需要的城市后，螞蟻們都擁有了專屬于自己的一條行駛軌跡，這時我們將各只螞蟻的軌跡逐一對應我們之前留下的優(yōu)秀細菌。與此同時算出上次更迭的過程中螞蟻走過的軌跡長度總值即細菌的成長度，在此時通過細菌覓食算法的復制剛進行的操作，對成長度的細菌（即總軌跡相對小的螞蟻）對其進行復制，同時刪除那些成長度小的細菌（即所有軌跡長度比較長的螞蟻），此時便可以改良蟻群算法的收斂速率，以及對于全局的收斂性。因為細菌覓食算法最初沒有對離散性問題有過多的設計，所以在針對此類問題時需要我們對其中的趨向操作進行一些有效的改進優(yōu)化，對其中翻轉的操作進行保留，就是對細菌的位置開始逆轉，在經過這個操作后使得總路線長度變小的細菌來替換之前的細菌位置，這樣算法就不會陷入局部最優(yōu)的情況，這樣就解決了算法的全局搜索能力了。

5?對細菌覓食算法的趨向的操作的引入

由于蟻群算法是在不斷尋求最佳軌跡的進程之中，而算法是依靠螞蟻留下信息素進行運行的關鍵，但是如果我們設置下來的一些路線螞蟻們幾乎不會經過，那么那條軌跡上之前的信息素就會逐漸消失，這時我們設置的螞蟻去往這些路徑的概率就會變小，那么這時算法就陷入了局部最優(yōu)的尷尬情況。而我們?yōu)榱藘?yōu)化提升這一狀況，盡可能去改善這個算法對全局掌控的搜索能力，在此時將細菌覓食算法中的一個操作導入即趨向操作。趨向操作指的是細菌覓食算法模擬腸道中細菌尋找食物的過程中的兩個運動翻轉和前進。細菌由于覓食的原因它們便往那些營養(yǎng)程度高的地方前進，同時翻轉遠離那些環(huán)境差沒有食物的地方。為了更好地優(yōu)化上面提到的不連續(xù)的概率問題，需要對算法中的趨向操作進行一些必要的優(yōu)化，同時保留其中重要的翻轉運動。我們通過概率性地改變細菌的移動的方向就是對細菌目前所處的地點進行反向趨向，在這個操作后那些總路線長度變小的細菌便可以保留，然后去替換原來不夠優(yōu)秀的細菌，這樣算法便可以沖出局部最優(yōu)這個難堪的處境，與此同時全局的搜索能力得到大幅度的提升。

5.1?趨向操作的一些具體細節(jié)

趨向操作是指細菌覓食算法在模擬腸道中細菌尋找食物的過程中的所要進行翻轉和前進兩個基本的動作。因為細菌往往會尋找那些食物多的位置進行前進這個運動，同時在這個時候用翻轉運動去遠離那些沒有食物以及環(huán)境差的地方。我們記錄細菌在某次趨向操作以及當時的復制操作，還有第一次遷徙操作后的位置，通過公式記錄。

5.2?算法的具體過程

第一步：對整個細菌覓食算法的參數(shù)進行初始化，將每只螞蟻當前的地點和細菌一一對應，同時計算城市間的距離矩陣。

第二步：構建解的空間，將一定數(shù)量的螞蟻隨機放在固定數(shù)量的城市上，根據公式計算出每只螞蟻去往下一個城市的概率，選擇下一個城市，加入軌跡路線記錄庫中，不間斷地重復操作上述過程，直到所有的螞蟻都回到了自己最開始的位置上再結束。

第三步：計算各只螞蟻途經的軌跡長度，通過這步找到之前細菌剛開始所處在的位置，記錄這些位置點，生成新的表。

第四步：引入細菌覓食算法的復制操作，將所有細菌留下的軌跡長度從長到短地進行排列，同時淘汰那些路線較長的細菌，同時留下路線較短的細菌，對這些細節(jié)進行復制，變成兩個完全相同的細菌。

第五步：引入細菌覓食算法的趨向操作，即翻轉操作，對各個細菌當前所處的方位即螞蟻所前進的路線進行固定方向的翻轉操作。如果在這個翻轉操作結束后，我們所需的軌跡長度變短即得到應有的優(yōu)化，那么這時將目前細菌所處的位置更新改變，同時定點標出為最佳的。

第六步：不停重復第二步到第五步，更新所有的信息素，直到被清空然后再進行新的迭代。

第七步：當算法達到最大的迭代次數(shù)時，此時將其停止，并將最優(yōu)路線以及其長度記錄輸出。

6?分析總結

本文主要是應用細菌覓食算法對蟻群算法的改進以便更好地適應目前在路徑規(guī)劃方面的需求，同時加入對離散型問題的求解，使得算法能夠應付多種情況。

6.1?主要創(chuàng)新點

（1）通過對傳統(tǒng)蟻群算法的改進，提高其搜索性能，跳出局部最優(yōu)，避免搜尋時間過長導致出現(xiàn)其他問題。

（2）優(yōu)化參數(shù)的選擇，使得在多種情況下都可以獲得最佳的路徑，可以更好地適應復雜情況。

（3）結合兩種算法，對算法的局限性的補足，提高算法的精確度與效率。

（4）對蟻群算法中的弊端進行了較大的改進，使其更適應目前路徑規(guī)劃問題。

6.2?后續(xù)研究方向

雖然對蟻群算法的一些缺陷進行了一定量的優(yōu)化，但是對于大規(guī)模的問題仍然需要更多的實驗去進行改進。后面會加大模型的多樣性，去提高算法的精確程度。

參考文獻：

［1］毛壽祺，楊平，高迪駒，等.基于細菌覓食蟻群算法的無人船路徑規(guī)劃［J］.控制工程，2023：19.

［2］龍洋，蘇義鑫，廉城，等.混合細菌覓食算法求解無人艇路徑規(guī)劃問題［J］.華中科技大學學報（自然科學版），2022，50（03）：6873.

［3］胡章芳，馮淳一，羅元.改進粒子群優(yōu)化算法的移動機器人路徑規(guī)劃［J］.計算機應用研究，2021，38（10）：30893092.

［4］羅丹.機器人路徑規(guī)劃方法分析［J］.電腦編程技巧與維護，2020（10）：125126+147.

［5］賈翠玲，徐明娜，王利利，等.基于混合細菌覓食和蟻群算法的機器人路徑規(guī)劃研究［J］.制造業(yè)自動化，2013，35（08）：6569.

［6］李梓遠，黃衛(wèi)華，章政，等.基于層次地圖模型的改進蟻群路徑規(guī)劃［J］.組合機床與自動化加工技術，2023（02）：1417.

［7］邱曉磊.基于蟻群算法的網球機器人路徑規(guī)劃算法研究［J］.太原學院學報（自然科學版），2022，40（04）：7278.

［8］楊雷博，周俊.改進蟻群算法下的車間物料配送路徑規(guī)劃研究［J］.制造業(yè)自動化，2022，44（11）：128131.

［9］宋宇，張浩，程超.基于改進蟻群算法的物流機器人路徑規(guī)劃［J］.現(xiàn)代制造工程，2022（11）：3540+47.

［10］趙倩楠，李志錕，黃宜慶.優(yōu)化復式蟻群算法的機器人路徑規(guī)劃研究［J］.安徽工程大學學報，2022，37（05）：5158.

項目：本文受到廣東高校重點領域專項新一代信息技術重點領域專項項目（2021ZDZX1019）的技術及經費支持

作者簡介：盧泓宇（1996—?），男，漢族，江蘇連云港人，碩士研究生在讀，專業(yè)：人工智能，研究方向：大數(shù)據應用；肖銀寶（1973—?），男，漢族，云南昆明人，碩士，助理研究員，研究方向：科技管理及信息化。