盧泓宇 肖銀寶

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

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

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ā)展，使得無(wú)人驅(qū)動(dòng)技術(shù)在近幾年得到科研工作者的重視。得力于網(wǎng)絡(luò)傳輸、傳感器技術(shù)的發(fā)展，路徑規(guī)劃的方案因此更加多樣化，因此本文主要通過(guò)細(xì)菌覓食算法對(duì)蟻群算法的改進(jìn)來(lái)提高路徑規(guī)劃的效率。

2?研究方案

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

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

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

pkij=τij（t）α·ηij（t）β∑s∈Jkτis（t）α·ηis（t）β（指數(shù)為兩個(gè)經(jīng)驗(yàn)系數(shù)）

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

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

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

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

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

4?對(duì)細(xì)菌覓食算法的復(fù)制操作的引入

4.1?復(fù)制操作的引入

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

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

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

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

5?對(duì)細(xì)菌覓食算法的趨向的操作的引入

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

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

趨向操作是指細(xì)菌覓食算法在模擬腸道中細(xì)菌尋找食物的過(guò)程中的所要進(jìn)行翻轉(zhuǎn)和前進(jìn)兩個(gè)基本的動(dòng)作。因?yàn)榧?xì)菌往往會(huì)尋找那些食物多的位置進(jìn)行前進(jìn)這個(gè)運(yùn)動(dòng)，同時(shí)在這個(gè)時(shí)候用翻轉(zhuǎn)運(yùn)動(dòng)去遠(yuǎn)離那些沒(méi)有食物以及環(huán)境差的地方。我們記錄細(xì)菌在某次趨向操作以及當(dāng)時(shí)的復(fù)制操作，還有第一次遷徙操作后的位置，通過(guò)公式記錄。

5.2?算法的具體過(guò)程

第一步：對(duì)整個(gè)細(xì)菌覓食算法的參數(shù)進(jìn)行初始化，將每只螞蟻當(dāng)前的地點(diǎn)和細(xì)菌一一對(duì)應(yīng)，同時(shí)計(jì)算城市間的距離矩陣。

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

第三步：計(jì)算各只螞蟻途經(jīng)的軌跡長(zhǎng)度，通過(guò)這步找到之前細(xì)菌剛開(kāi)始所處在的位置，記錄這些位置點(diǎn)，生成新的表。

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

第五步：引入細(xì)菌覓食算法的趨向操作，即翻轉(zhuǎn)操作，對(duì)各個(gè)細(xì)菌當(dāng)前所處的方位即螞蟻所前進(jìn)的路線進(jìn)行固定方向的翻轉(zhuǎn)操作。如果在這個(gè)翻轉(zhuǎn)操作結(jié)束后，我們所需的軌跡長(zhǎng)度變短即得到應(yīng)有的優(yōu)化，那么這時(shí)將目前細(xì)菌所處的位置更新改變，同時(shí)定點(diǎn)標(biāo)出為最佳的。

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

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

6?分析總結(jié)

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

6.1?主要?jiǎng)?chuàng)新點(diǎn)

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

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

（3）結(jié)合兩種算法，對(duì)算法的局限性的補(bǔ)足，提高算法的精確度與效率。

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

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

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

參考文獻(xiàn)：

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

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

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

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

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

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

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

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

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

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

項(xiàng)目：本文受到廣東高校重點(diǎn)領(lǐng)域?qū)ｍ?xiàng)新一代信息技術(shù)重點(diǎn)領(lǐng)域?qū)ｍ?xiàng)項(xiàng)目（2021ZDZX1019）的技術(shù)及經(jīng)費(fèi)支持

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