基于象群－蟻群算法改進(jìn)的小車路徑規(guī)劃

柏語蔓，于蓮芝

（上海理工大學(xué) 光電信息與計(jì)算機(jī)工程學(xué)院，上海 200093）

0 引 言

科技發(fā)展推動著智能移動機(jī)器人領(lǐng)域迅速發(fā)展，該領(lǐng)域需要多類技術(shù)相互融合［1］，其中路徑規(guī)劃是該領(lǐng)域研究的核心問題［2］。智能機(jī)器人在實(shí)際使用中能否高效、安全完成任務(wù)，主要取決于路徑規(guī)劃是否合理。目前主流的路徑規(guī)劃算法主要有人工勢場法［3］、模糊邏輯算法［4］、模擬退火算法［5］、蟻群算法等。

在眾多路徑規(guī)劃算法中，蟻群算法有較好的全局優(yōu)化能力、魯棒性、并行性［6］，適合復(fù)雜環(huán)境中的路徑規(guī)劃問題。該算法由MarcoDorigo在1992 年提出［7］，這是一種模仿螞蟻覓食的智能路徑規(guī)劃算法。模仿螞蟻通過釋放信息素尋找最優(yōu)覓食路徑，多輪覓食之后，根據(jù)正反饋機(jī)制選出信息素濃度最高路線為最優(yōu)路徑。

其中，螞蟻種群數(shù)量、信息素?fù)]發(fā)速度、信息素影響因子、啟發(fā)式影響因子這些參數(shù)值選取過大或者過小都會直接影響路徑搜索的隨機(jī)性，進(jìn)而影響算法收斂速度和全局搜索能力。隨機(jī)性較弱時，算法的搜索速度加快，但會導(dǎo)致全局搜索能力降低，結(jié)果為局部最優(yōu)。當(dāng)算法隨機(jī)性較強(qiáng)時，降低蟻群算法正反饋?zhàn)饔?，算法收斂速度變慢，拖慢運(yùn)行效率。所以如何選擇合適的參數(shù)是蟻群算法改進(jìn)的重點(diǎn)。

針對蟻群算法在路徑規(guī)劃應(yīng)用中存在的問題，目前主流的對蟻群算法的改進(jìn)方案有：

（1）單一蟻群算法的改進(jìn)［8］：單個蟻群算法通過改進(jìn)算法結(jié)構(gòu)、優(yōu)化參數(shù)、設(shè)置信息素初始值和調(diào)整信息素更新原則等方式，提高算法的尋優(yōu)能力。該改進(jìn)方案雖然在一定程度上改進(jìn)了蟻群算法的運(yùn)行速度、減少陷入局部最優(yōu)解的可能，但由于大部分參數(shù)改動都是需要人為去設(shè)定參數(shù)，存在算法不靈活的問題。

（2）多蟻群優(yōu)化算法［8］：采用不同算法結(jié)構(gòu)、運(yùn)行機(jī)制的螞蟻群去尋找最優(yōu)路徑，一般主流的運(yùn)行機(jī)制是順序和并行。該改進(jìn)方案是通過增加蟻群的多樣性，來提高結(jié)果為最優(yōu)解的可能性。其中順序運(yùn)行機(jī)制需要設(shè)置相遇判斷準(zhǔn)則，而并行運(yùn)行機(jī)制需要制定種群間信息交換機(jī)制，并且相遇判斷準(zhǔn)則和信息交換機(jī)制的設(shè)計(jì)直接影響整個算法的優(yōu)化結(jié)果，甚至?xí)档拖伻核惴ǖ男阅堋?/p>

（3）融合蟻群算法［8］：通過融合其它優(yōu)化算法，從初始信息素值、狀態(tài)轉(zhuǎn)移規(guī)則、算法參數(shù)、初始路這4 個方面優(yōu)化蟻群算法。該方案可以大大降低蟻群算法的迭代次數(shù)，提高尋優(yōu)速度。通過大量的文獻(xiàn)表明，該類改進(jìn)方案相對于前兩種方案具有更強(qiáng)的尋優(yōu)能力。但是，由于算法的復(fù)雜程度增加，會在一定程度上增加算法的運(yùn)行時間。

本文選用第三類改進(jìn)方案，將貪婪算法和象群算法融入到蟻群算法之中。針對蟻群算法初始信息素值相同導(dǎo)致的初次迭代過于隨機(jī)，影響算法的迭代速度的問題，本文在蟻群算法之前加入貪婪算法，選出次優(yōu)路徑，以此為依據(jù)設(shè)置初始信息素值。針對蟻群算法憑借經(jīng)驗(yàn)設(shè)計(jì)參數(shù)，導(dǎo)致參數(shù)設(shè)計(jì)不當(dāng)影響算法性能的現(xiàn)象，本文將象群算法融入到蟻群算法之中，并在象群算法的基礎(chǔ)上加入評價函數(shù)，為蟻群算法選取合適的算法參數(shù)，以此降低算法迭代次數(shù)，提升蟻群算法尋優(yōu)能力。最后將改進(jìn)后的蟻群算法帶入到已知運(yùn)行環(huán)境的機(jī)器人小車路徑規(guī)劃實(shí)驗(yàn)中，在創(chuàng)建的運(yùn)行環(huán)境柵格圖的基礎(chǔ)上，用MATLAB 進(jìn)行改進(jìn)后和初始蟻群算法的路徑規(guī)劃對比仿真實(shí)驗(yàn)，根據(jù)實(shí)驗(yàn)數(shù)據(jù)分析改進(jìn)后的算法優(yōu)劣。

1 柵格法創(chuàng)建環(huán)境模型

本文研究的是基于蟻群算法的全局路徑規(guī)劃，即已知環(huán)境中障礙物信息。在該情況下，對全局環(huán)境進(jìn)行建模是路徑規(guī)劃的基礎(chǔ)和前提。環(huán)境模型需要包含環(huán)境中所有的已知信息，并且該環(huán)境模型描述的方式要方便計(jì)算機(jī)去存儲和運(yùn)算，滿足環(huán)境信息隨機(jī)器人位置變換而隨時更新的要求。同時，在環(huán)境模型上搜索的最優(yōu)路徑，能讓移動機(jī)器人在實(shí)際運(yùn)行中少與障礙物發(fā)生碰撞。由于柵格法能夠滿足環(huán)境建模的要求，并且易于創(chuàng)建便于維護(hù)，因此本文選擇柵格法創(chuàng)建環(huán)境模型。

柵格法用坐標(biāo)系表示機(jī)器人運(yùn)動環(huán)境。首先在運(yùn)行環(huán)境邊界找一點(diǎn)為坐標(biāo)原點(diǎn)，并創(chuàng)建坐標(biāo)系，劃分運(yùn)行環(huán)境為等大小的柵格，障礙物等比例映射到柵格圖中，進(jìn)行障礙物標(biāo)注，由黑白兩色分別標(biāo)記柵格圖中的障礙物和自由柵格。

在路徑規(guī)劃仿真實(shí)驗(yàn)中，一般不考慮移動機(jī)器人的大小和形狀，只將其看作一個質(zhì)點(diǎn)，為了避免實(shí)際實(shí)驗(yàn)中移動機(jī)器人與障礙物發(fā)生碰撞，在進(jìn)行柵格法創(chuàng)建環(huán)境模型時，一般會膨脹處理柵格中的障礙物，即將障礙物的邊長擴(kuò)大半個柵格的長度，以此提高移動機(jī)器人在實(shí)際運(yùn)動中的安全性。柵格法創(chuàng)建的環(huán)境模型如圖1 所示。

圖1 柵格地圖Fig.1 Raster map

在柵格圖中可見，每一塊柵格都會由序號i和坐標(biāo)（x，y）共同去表示。序號是用從1 開始的自然數(shù)按照從左到右、從上到下的方式去逐一標(biāo)注每一塊柵格，坐標(biāo)是用創(chuàng)建的XOY坐標(biāo)系，來表示每一個柵格的坐標(biāo)。序號和坐標(biāo)之間的轉(zhuǎn)換關(guān)系為：

式中：mod表示的余數(shù)；ceil表示的整數(shù)；N表示每列柵格數(shù)。

2 蟻群算法改進(jìn)

2.1 初始信息素改進(jìn)

由于初始信息素濃度相同會導(dǎo)致螞蟻初次搜索路徑過于隨機(jī)，從而使算法收斂速度減慢。因此本文通過差異化設(shè)置柵格圖各塊信息素濃度的方式，使初始信息素濃度按一定規(guī)則分布，降低蟻群初次迭代的隨機(jī)性，以此縮短收斂時間，提高蟻群算法的效率。

本文選用最佳優(yōu)先搜索算法（Best－ First Search，BFS），在蟻群算法運(yùn)行之前選擇一條次優(yōu)路徑。BFS 算法是一種啟發(fā)式搜索算法［9］，有別于窮舉類型的搜索算法，不需要逐個搜索所有的點(diǎn)，運(yùn)行效率更高，更適合復(fù)雜、面積較大的運(yùn)行環(huán)境，適合用作尋找環(huán)境中的次優(yōu)路徑。BFS 找出的次優(yōu)路徑如圖2 所示。

圖2 次優(yōu)路徑圖Fig.2 Suboptimal path diagram

以BFS 算法選擇的路徑結(jié)果為依據(jù)，初始化路徑中的信息素濃度。初始信息素濃度以次優(yōu)路徑為中心向兩邊呈標(biāo)準(zhǔn)正態(tài)分布，如公式（2）：

式中：x表示點(diǎn)到次優(yōu)路徑的垂直距離，a的值為次優(yōu)路徑信息素濃度值。

2.2 參數(shù)改進(jìn)

在蟻群算法中，參數(shù)對算法結(jié)果的準(zhǔn)確度起著至關(guān)重要的作用。原始蟻群算法是憑借實(shí)驗(yàn)者的經(jīng)驗(yàn)來選取參數(shù)值［10］，使用象群算法較強(qiáng)的尋優(yōu)能力選取蟻群算法中的重要參數(shù)。象群算法（Elephant Herding Optimization，EHO）［11］是一種新元啟發(fā)式優(yōu)化算法，較其它優(yōu)化算法公式簡單、便于理解，具有收斂速度快尋優(yōu)能力強(qiáng)等優(yōu)點(diǎn)。

象群優(yōu)化算法是根據(jù)象群的游牧行為啟發(fā)得來的［12］。大象成群生活由多個氏族在一位最優(yōu)秀母象女部長的領(lǐng)導(dǎo)下組成，每個氏族由母象和她的小象或某些有血緣關(guān)系的母象和小象組成，氏族里也會選出優(yōu)秀的母象擔(dān)任族長，成年后公象會離開群體獨(dú)自生活，雖然公象遠(yuǎn)離其家族，但其可以通過低頻振動與家族中的大象保持聯(lián)系。

為了使用大象的放牧行為解決各種全局優(yōu)化問題，對其做以下理想化規(guī)則。

（1）一個象群部落由多個氏族和一個最優(yōu)母象女族長組成，每個氏族都有固定數(shù)量的大象。

（2）每代中每個氏族都會選出一個優(yōu)秀女族長，并有固定數(shù)量公象離開，且產(chǎn)生其相同數(shù)量的新小象。

象群算法分為兩個階段，分別是氏族更新階段和分離階段。具體過程如下：

2.2.1 氏族更新階段

氏族里每頭大象的位置都會受到女族長的影響，對于氏族ci中的大象j，位置更新如公式（3）：

式中：φ∈［0，1］為比例因子；為氏族ci中大象j的新位置；xci，j為氏族ci中大象j的舊位置；xbest，ci為氏族ci女族長；r∈［0，1］ 為隨機(jī)數(shù)。

女族長位置更新位置如公式（4）：

式中：δ∈［0，1］為xcenter，ci對xbest，ci的影響因子，xbest，ci為氏族ci的中心位置。其中，xcenter，ci，d的表達(dá)式如公式（5）：

式中：d∈［1，D］ 為維度；D為最大維度；nci為氏族ci的大象總數(shù)。

2.2.2 分離階段

為了模擬成年后的公象離開群體獨(dú)自生活這一過程，并獲得更大搜索能力，假設(shè)適應(yīng)度最差的大象個體，在每代中執(zhí)行分離算子，如公式（6）：

式中：xmax和xmin分別為大象個體位置上界和下界，xworst，ci為ci氏族中最差大象個體。

改進(jìn)方案是將信息素?fù)]發(fā)速度、信息素影響因子、啟發(fā)式影響因子和螞蟻種群數(shù)量這4 個參數(shù)，作為象群的位置信息，創(chuàng)建一個四維的坐標(biāo)矩陣。由象群算法不斷迭代更新象群位置，選出最優(yōu)的母象位置，同時設(shè)計(jì)評價函數(shù)來鑒定所選參數(shù)的合理性，以此使象群算法得出的參數(shù)值可以更好的適應(yīng)蟻群算法。

設(shè)計(jì)評價函數(shù)的目的，是評估象群算法選取參數(shù)是否適合蟻群算法。所以評價函數(shù)設(shè)計(jì)過程需要考慮到蟻群算法的幾個重要性能指標(biāo)。這些指標(biāo)分別為尋優(yōu)能力、穩(wěn)定性、收斂速度、運(yùn)算時間，該評價函數(shù)設(shè)計(jì)如公式（7）～（9）：

式中：Fitk(s) 為將當(dāng)前大象k的位置矩陣作為參數(shù)，運(yùn)行蟻群算法后的適應(yīng)值；ω1、ω2、ω3、ω4為尋優(yōu)能力、穩(wěn)定性、收斂速度和運(yùn)算時間各指標(biāo)對應(yīng)的權(quán)值，權(quán)值相加為1；Lk(s) 為使用當(dāng)前大象位置作為參數(shù)的蟻群算法的尋優(yōu)能力；f為正態(tài)分布函數(shù)；Llocal表示此時蟻群算法的最優(yōu)解；Sk(s) 為此時蟻群算法穩(wěn)定性；Lstd為每次迭代所得最短距離方差；Ek(s) 表示此時蟻群算法尋找到最優(yōu)解所需迭代次數(shù)；Tk(s) 表示此次蟻群算法運(yùn)算時間。

2.3 算法實(shí)現(xiàn)

該算法的主要實(shí)現(xiàn)步驟如下：

Step 1使用柵格法創(chuàng)建環(huán)境模型；

Step 2貪心算法選出次優(yōu)路徑，并根據(jù)路徑選擇結(jié)果，初始化各節(jié)點(diǎn)之間的信息素濃度；

Step 3初始化象群算法，給各個大象隨機(jī)選取初始位置和速度，并為比例因子φ和影響因子δ賦值；

Step 4將每個大象的位置信息作為參數(shù)帶入蟻群算法中，計(jì)算在各參數(shù)下運(yùn)行蟻群算法獲得的Llocal、Lstd、Ek、Tk。

Step 5將步驟4 中每個大象對應(yīng)的Lk(s)、Sk(s)、Ek(s) 和Tk(s) 值帶入適應(yīng)度函數(shù)中，算出各個大象的適應(yīng)度值；

Step 6比較各大象的適應(yīng)度值，選取適應(yīng)度最優(yōu)的大象為族長，同時選出適應(yīng)度最差的大象；

Step 7用公式（4）更新族長的位置，用公式（5）更新適應(yīng)度較差大象的位置，用公式（3）更新其余大象的位置；

Step 8判斷象群算法的迭代次數(shù)是否達(dá)到設(shè)定的最大值，若為最大值，就將未更新位置前族長的位置輸出；否則，回到步驟4；

Step 9用輸出的最優(yōu)位置為參數(shù)，帶入到蟻群算法中，用蟻群算法選出最優(yōu)路徑，得到全局最優(yōu)解。

改進(jìn)后蟻群算法流程如圖3 所示：

圖3 改進(jìn)后蟻群算法流程圖Fig.3 Flow chart of improved ant colony algorithm

3 仿真結(jié)果與分析

本文選用的仿真環(huán)境為MATLAB2018b，環(huán)境模型為20*20 的柵格。對比改進(jìn)前后的蟻群算法的仿真結(jié)果，驗(yàn)證改進(jìn)算法的可行性和優(yōu)越性。

在信息素加強(qiáng)系數(shù)都為1 的情況下，根據(jù)文獻(xiàn)［13］給出的傳統(tǒng)蟻群算法參數(shù)，其中螞蟻的數(shù)量為40、信息素?fù)]發(fā)速度為0.3、信息素影響因子為5、啟發(fā)式影響因子為2。通過象群算法改進(jìn)后的蟻群算法參數(shù)選擇見表1，次優(yōu)路徑的信息素濃度值為8。將兩種情況，進(jìn)行100 次迭代，20 次重復(fù)實(shí)驗(yàn)，比較兩者的性能。表2 給出了運(yùn)行20 次象群算法后選取最佳優(yōu)化結(jié)果所對應(yīng)的優(yōu)化蟻群算法參數(shù)。

表1 算法參數(shù)表Tab.1 Algorithm parameter

表2 優(yōu)化參數(shù)值Tab.2 Optimized parameter values

由圖4、5 結(jié)果顯示，采用傳統(tǒng)蟻群算法和改進(jìn)后的蟻群算法，在路徑規(guī)劃上結(jié)果具有一定差異。通過對比圖6、7 的結(jié)果（即改進(jìn)前后的收斂曲線）可以看出，改進(jìn)后的蟻群算法結(jié)果更優(yōu)，收斂更快，且算法運(yùn)行穩(wěn)定性更高。因此，可以預(yù)測該改進(jìn)方案在復(fù)雜的運(yùn)行環(huán)境中優(yōu)勢會更加明顯。

圖4 傳統(tǒng)蟻群算法仿真結(jié)果Fig.4 Simulation results of traditional ant colony algorithm

圖5 改進(jìn)后蟻群算法仿真結(jié)果Fig.5 Simulation results of the improved ant colony algorithm

圖6 傳統(tǒng)蟻群算法收斂曲線圖Fig.6 Convergence curve of traditional ant colony algorithm

圖7 改進(jìn)后蟻群算法收斂曲線圖Fig.7 Convergence curve of improved ant colony algorithm

傳統(tǒng)蟻群算法和改進(jìn)后蟻群算法的仿真數(shù)據(jù)對比結(jié)果見表3。從這些數(shù)據(jù)中可以清晰看出，在路徑長度上，改進(jìn)算法路徑更優(yōu)，且其到達(dá)收斂時的迭代次數(shù)遠(yuǎn)遠(yuǎn)少于改進(jìn)之前。改進(jìn)的蟻群算法運(yùn)行時間長于傳統(tǒng)蟻群算法，是因?yàn)樵摃r間包含了象群算法的運(yùn)行時間，由于在移動小車運(yùn)行前進(jìn)行路徑規(guī)劃，所以滿足本文實(shí)驗(yàn)要求。從20 次實(shí)驗(yàn)路徑長度的平均值和方差可以看出，改進(jìn)后的算法更加穩(wěn)定。由此證明，使用象群算法選擇參數(shù)，在算法收斂速度、穩(wěn)定性和結(jié)果精確度上會優(yōu)于憑借經(jīng)驗(yàn)選取參數(shù)。

表3 仿真結(jié)果對比Tab.3 Comparison table of simulation results

4 結(jié)束語

本文研究了基于蟻群算法改進(jìn)的移動機(jī)器人路徑規(guī)劃，改進(jìn)措施針對蟻群算法在尋優(yōu)時收斂速度不夠快［14］，并且因參數(shù)選擇不當(dāng)而導(dǎo)致結(jié)果陷入局部最優(yōu)解的情況［15］。在使用柵格法創(chuàng)建環(huán)境地圖的基礎(chǔ)上，使用貪婪算法找到次優(yōu)路徑，以此為依據(jù)初始化信息素濃度，提高蟻群算法的收斂速度；加入象群算法解決蟻群算法憑借經(jīng)驗(yàn)選擇參數(shù)的問題，同時用蟻群算法的各項(xiàng)指標(biāo)設(shè)置了象群算法的適應(yīng)度函數(shù)，讓象群朝著適應(yīng)度值高的位置移動，以此選出適合的蟻群算法參數(shù)，解決蟻群算法因?yàn)閰?shù)選擇不當(dāng)而導(dǎo)致的局部最優(yōu)解問題。仿真結(jié)果證明，該改進(jìn)方案是具有可行性的，并且有助于蟻群算法快速選取全局最優(yōu)路徑。