改進粒子群算法的機器人路徑規劃

盛雪松

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

關鍵詞：傳統粒子群算法;線性慣性權重粒子群算法;遷移操作的粒子群算法

一、引 言

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

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

二、傳統粒子群算法的路徑規劃

（一）傳統的粒子群算法

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

式中：表示第次迭代中的第維速度;表示第次迭代中的第維的位置;為慣性權值;和為學習因子;為分布在之間的隨機數。

（二）算法的目標函數

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

三、改進的粒子群算法的路徑規劃

（一）線性慣性權重的粒子群算法

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

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

（二）生物地理學優化算法

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

針對上述物種數量和遷移的關系，總結如下：

（1）隨著區域內物種數量的不斷增加，外來物種的遷入會加劇擁擠程度，因此潛入率會逐漸減小，同時由于競爭關系，會導致一部分物種從該區域遷出，使得遷出率不斷增加;

（2）當物種數量S增加至極限時，處于飽和狀態，區域內的物種只能出不能進，對應的遷入率將至0，而遷出率會增長到最大，即最大遷出率;

（3）如果該區域內物種數量為0時，其遷出率必定為0。

（三）遷移操作

遷移操作是生物地理學優化算法的核心步驟，在優化的過程中，通過物種種群的不斷遷入、遷出操作，可以不斷的改變區域系統內的的適應度指標HSI。

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

遷出操作的更新過程需要借助隨機數，可總結為：

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

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

因此可以看出，當區域的適應度越大，表明所能接受的物種數量的總數就越高，當區域的適用度越小時，所能接受的物種數量的總數就越少。針對上述關系可以將物種數量用適應度函數值替換：

其中，和分別表示當前棲息地種群中適應度函數的最大值和最小值。

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

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

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

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

其中：表示遷移操作的力度;表示當前迭代下的全局最優值;表示個體在當前迭代下該粒子的歷史最優值;表示進行遷移操作的系數，其與粒子陷入死區的程度有關。

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

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

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

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

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

三、全局路徑規劃仿真和結果分析

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

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

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

四、結束語

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

參考文獻

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

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

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

[4]劉旭.粒子群算法及其應用發展[J].科技經濟導刊，2018，26（04）：138-139.

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