改進粒子群算法的機器人路徑規(guī)劃

盛雪松

摘 要：對于傳統(tǒng)的粒子群算法在路徑規(guī)劃時，粒子容易陷入局部的最優(yōu)解、路徑質(zhì)量較為差的問題，本文提出了相應(yīng)的改進的粒子群算法。主要有線性慣性權(quán)重的粒子群算法，可以隨著算法的迭代，慣性權(quán)重不斷減小，使得后期的局部搜索能力增強在采用該算法之后。以及通過粒子群算法與生物地理學(xué)優(yōu)化算法相結(jié)合，在路徑尋優(yōu)的過程中增加了遷移操作來幫助粒子脫離困境，從而避免了粒子陷入死循環(huán)或者局部最優(yōu)的結(jié)果。

關(guān)鍵詞：傳統(tǒng)粒子群算法;線性慣性權(quán)重粒子群算法;遷移操作的粒子群算法

一、引 言

移動機器人路徑的規(guī)劃問題一直是機器人導(dǎo)航領(lǐng)域的研究的焦點，移動機器人的路徑規(guī)劃是指機器人在有障礙物的工作環(huán)境中根據(jù)起止點和終止點的信息坐標，搜索出一條能耗低、所用時間少、距離更短并且能避開所有障礙物的有效路徑[1]。

近些年來，一些新興的算法，比如遺傳算法、蟻群算法、粒子群算法、蜂群算法等。相較于傳統(tǒng)的一些算法，通過模擬大自然生物的一種或幾種行為進而提出的一種智能仿生算法，為解決比較復(fù)雜的環(huán)境下的路徑規(guī)劃問題提供了新的思路[2]。本文在粒子群的基礎(chǔ)上進行改進，彌補了傳統(tǒng)粒子群算法在搜索過程中容易陷入局部最優(yōu)的這種缺點[3]。

二、傳統(tǒng)粒子群算法的路徑規(guī)劃

（一）傳統(tǒng)的粒子群算法

通過對鳥群捕食行為研究，提出了粒子群算法，其在求解優(yōu)化的問題時，問題的解對應(yīng)于搜索空間中的一只鳥的飛行位置，這樣成為一個“粒子”。每個粒子都通過跟蹤群體所經(jīng)過個體的最優(yōu)解和整個種群的全局最優(yōu)解的影響來不斷更新自己，從而產(chǎn)生下一輪新的群體[4]。粒子的速度以及位置更新公式如下：

式中：表示第次迭代中的第維速度;表示第次迭代中的第維的位置;為慣性權(quán)值;和為學(xué)習(xí)因子;為分布在之間的隨機數(shù)。

（二）算法的目標函數(shù)

粒子的路徑規(guī)劃就是搜索一條從起點到終點的無碰撞最短的路徑，其目標函數(shù)可以表示為

三、改進的粒子群算法的路徑規(guī)劃

（一）線性慣性權(quán)重的粒子群算法

在基本的粒子群算法中慣性權(quán)值是一個固定的值，當較大的時候，粒子的全局搜索能力較強，但是局部的搜索能力比較的弱，可能會使粒子飛過最低點。當較小的時候，可以使得粒子的局部搜索能力變強，但這樣粒子往往容易陷入局部最優(yōu)解，而失去全局的尋優(yōu)能力。通過改變權(quán)重對粒子群的搜索功能進行改進，即隨著迭代的過程，不斷的減少慣性權(quán)重的值，這樣算法在初期的探索能力較為強，可以再比較大的空間范圍內(nèi)搜索，在后期，權(quán)值的減小，使得可以收斂到較好的區(qū)域，進行更為細致的搜索，權(quán)重變化式如下：

式中：為最大權(quán)值;為最小權(quán)值;為最大迭代次數(shù);為粒子當前迭代次數(shù)。其算法流程和基本粒子群算法較為相似，只不過最后要進行判斷算法是否滿足終止條件，不滿足的話，則調(diào)整值，重新更新粒子的速度與位置繼續(xù)循環(huán)。不過隨著優(yōu)化問題的不同，線性慣性權(quán)重的調(diào)整策略也不相同，這就使得線性慣性權(quán)重的粒子群算法在應(yīng)用中有很大的局限性。

（二）生物地理學(xué)優(yōu)化算法

生物地理學(xué)優(yōu)化算法，也常被稱作BBO算法。在該算法中，我們用適用度指標（habitat suitability index，HSI）來具體量化所研究的地區(qū)物種的適應(yīng)情況，如果計算顯示的HSI指標較高，說明該地區(qū)物種種類比較豐富，處于相對穩(wěn)定的狀態(tài)，比較適合物種的生存;同樣，當研究顯示的HSI指標較低時，表明該地區(qū)物種種類比較匱乏，尚未飽和[5]。在生物地理學(xué)的理論中，該地區(qū)是否適合生存，必然會引起物種的遷移，即：HSI越高，說明該地區(qū)能容納的外來物種相對有限，其對應(yīng)的遷入率和遷出率都會比較小;當HSI越高，表明可容納的物種比較充裕，對應(yīng)的遷入率會比較大，而遷出率比較小。

針對上述物種數(shù)量和遷移的關(guān)系，總結(jié)如下：

（1）隨著區(qū)域內(nèi)物種數(shù)量的不斷增加，外來物種的遷入會加劇擁擠程度，因此潛入率會逐漸減小，同時由于競爭關(guān)系，會導(dǎo)致一部分物種從該區(qū)域遷出，使得遷出率不斷增加;

（2）當物種數(shù)量S增加至極限時，處于飽和狀態(tài)，區(qū)域內(nèi)的物種只能出不能進，對應(yīng)的遷入率將至0，而遷出率會增長到最大，即最大遷出率;

（3）如果該區(qū)域內(nèi)物種數(shù)量為0時，其遷出率必定為0。

（三）遷移操作

遷移操作是生物地理學(xué)優(yōu)化算法的核心步驟，在優(yōu)化的過程中，通過物種種群的不斷遷入、遷出操作，可以不斷的改變區(qū)域系統(tǒng)內(nèi)的的適應(yīng)度指標HSI。

如果將最大遷出率E、最大遷入率I設(shè)置為1，可容納物種的區(qū)域數(shù)量用來表示，對應(yīng)的某一個區(qū)域用表示，其對應(yīng)的第維的適宜度分量用來表示。通過上述的分析可以看出，遷入和遷出操作實際上是通過區(qū)域間信息的不斷交互實現(xiàn)對大面積區(qū)域的空間搜索。

遷出操作的更新過程需要借助隨機數(shù)，可總結(jié)為：

對于區(qū)域，如果，則由遷入率決定將要被替換的區(qū)域，執(zhí)行遷移操作.，并且。如果，則不執(zhí)行遷移操作。如此循環(huán)，直到對所有的變量都執(zhí)行完上述操作，就產(chǎn)生了一個新的區(qū)域。然后對下一個區(qū)域進行操作，如此循環(huán)，直到所有區(qū)域都完成此操作。利用遷入率的選擇方法為：計算其余max-1個區(qū)域的遷入率，根據(jù)貪婪算法求出第一個滿足的區(qū)域。

同樣的遷入操作的更新過程與此相似

因此可以看出，當區(qū)域的適應(yīng)度越大，表明所能接受的物種數(shù)量的總數(shù)就越高，當區(qū)域的適用度越小時，所能接受的物種數(shù)量的總數(shù)就越少。針對上述關(guān)系可以將物種數(shù)量用適應(yīng)度函數(shù)值替換：

其中，和分別表示當前棲息地種群中適應(yīng)度函數(shù)的最大值和最小值。

（四）基于遷移操作的改進粒子群算法

為了有效避免粒子群算法在迭代過程中容易陷入局部最優(yōu)的缺點，充分提高粒子的全局以及局部的搜索能力，提高算法的收斂性能，將生物地理學(xué)優(yōu)化算法與改進后的粒子群算法相結(jié)合，當粒子適應(yīng)度較差時，通過對該粒子施加一定概率的遷移操作，增加粒子的遷入和遷出效果，使得該被困粒子可以順利的離開被困區(qū)域，達到動態(tài)調(diào)整搜索步長和優(yōu)化粒子的更新策略，從而避免了粒子陷入死循環(huán)或者局部最優(yōu)的結(jié)果，使得算法性能更優(yōu)[8]。

在粒子迭代的過程中，如果經(jīng)過連續(xù)的三次更新后，該粒子的適應(yīng)度值仍然小時，我們則定義該粒子陷入了死區(qū)，此時，需要外力強制介入遷移操作，幫助粒子脫離困境。因此，本文將判斷粒子是否處于死區(qū)的方法設(shè)定為：對適宜度值的粒子，需要計算其最近三次迭代（包含本次）目標函數(shù)值的方差，若小于設(shè)定值，則認為該粒子陷入死區(qū)。

基于生物地理學(xué)優(yōu)化的算法的原理，結(jié)合粒子群的特點，可將遷移操作定義如下：

其中：表示遷移操作的力度;表示當前迭代下的全局最優(yōu)值;表示個體在當前迭代下該粒子的歷史最優(yōu)值;表示進行遷移操作的系數(shù)，其與粒子陷入死區(qū)的程度有關(guān)。

當粒子并未陷入死區(qū)時，，表示不進行遷移操作;而當系統(tǒng)判定粒子陷入死區(qū)時，參考，生物地理學(xué)的遷入率和遷出率，將定義為：

其中：表示當前粒子的適用度值;表示粒子種群中適應(yīng)度最小值;表示粒子種群中平均適應(yīng)度。

由上式可以看出，當粒子的適應(yīng)度越差，即陷入死區(qū)的程度越深，遷移系數(shù)越大，即表示將要執(zhí)行的遷移力度越大，通過較大的遷移來影響該粒子的速度和位置更新。

本文將在改進后的粒子群算法中加入遷移操作，將粒子群的迭代過程中增加了遷入、遷出操作，具體表現(xiàn)如下：置一個概率值，對于第個粒子，如果>，則對進行遷移操作，使用基于遷入率的遷移操作進行位置更新;如果，則進行遷移率的操作，執(zhí)行基于遷出率的遷移操作進行位置更新;如果值相等，則進行到執(zhí)行不進行遷移操作。其中randn（0，1）表示均值為0，方差為1的高斯分布。

通過上述改進之后，當經(jīng)過三次判斷該粒子陷入死區(qū)時，使用下式對粒子進行更新：

三、全局路徑規(guī)劃仿真和結(jié)果分析

應(yīng)用柵格法建立環(huán)境地圖，在環(huán)境中采用上述的粒子群算法、慣性權(quán)重粒子群算法、遷移操作的粒子群算法進行路徑的規(guī)劃并比較分析三種算法在簡單以及復(fù)雜環(huán)境中的尋找最佳路徑長度的能力。

進行了五次仿真，在復(fù)雜情況下，遷移操作的粒子群算法都可以得到更小的目標函數(shù)即路徑長度。

由以上的仿真圖還有收斂曲線可以得知：在復(fù)雜的環(huán)境下，基本粒子群算法迭代了182次之后陷入了局部最優(yōu)解，其最優(yōu)的路徑適應(yīng)度函數(shù)為72.8112。線性慣性權(quán)重的粒子群算法在21次迭代得到局部最優(yōu)解，其路徑的函數(shù)為69.98291。而采用了遷移操作的粒子群算法，在進行路徑的規(guī)劃時，當?shù)?80次時跳出局部的最優(yōu)解，在當前最大迭代次數(shù)下，最優(yōu)最有效的路徑適應(yīng)度函數(shù)為64.3259。綜上所述，遷移操作的粒子群算法在復(fù)雜的環(huán)境下所能得到的路徑長度更短。

四、結(jié)束語

傳統(tǒng)的粒子群算法對于機器人路徑規(guī)劃中具有建模簡單、計算過程簡單、收斂性速度快以及參數(shù)較少等優(yōu)點，但是也較容易陷入局部的最優(yōu)解，從而在一下復(fù)雜環(huán)境下得不到全局的最優(yōu)解，使得優(yōu)化結(jié)果不理想。因此結(jié)合了遷移操作的粒子群算法，能夠彌補以上缺點。并通過計算機仿真驗證了該算法的有效性，合理性，是優(yōu)于傳統(tǒng)的粒子群算法的。

參考文獻

[1]張穎，吳成東，原寶龍.機器人路徑規(guī)劃方法綜述[J].控制工程，2003，10（5）;152-155.

[2]孫波，陳衛(wèi)東，席裕庚.基于粒子群優(yōu)化算法的移動機器人全局路徑規(guī)劃[J].控制與決策，2005，20（9）;1052-1055.

[3]李偉莉，趙東輝.基于柵格法與神經(jīng)元的機器人全區(qū)域覆蓋算法[J].機械設(shè)計與制造，2017（08）：232-238.

[4]劉旭.粒子群算法及其應(yīng)用發(fā)展[J].科技經(jīng)濟導(dǎo)刊，2018，26（04）：138-139.

[5]秦樹輝等著.生物地理學(xué).北京：科學(xué)出版社，2010.