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

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

盛雪松摘要：對(duì)于傳統(tǒng)的粒子群算法在路徑規(guī)劃時(shí)，粒子容易陷入局部的最優(yōu)解、路徑質(zhì)量較為差的問(wèn)題，本文提出了相應(yīng)的改進(jìn)的粒子群算法。主要有線(xiàn)性慣性權(quán)重的粒子群算法，可以隨著算法的迭代，慣性權(quán)重不斷減小，使得后期的局部搜索能力增強(qiáng)在采用該算法之后。以及通過(guò)粒子群算法與生物地理學(xué)優(yōu)化算法相結(jié)合，在路徑尋優(yōu)的過(guò)程中增加了遷移操作來(lái)幫助粒子脫離困境，從而避免了粒子陷入死循環(huán)或者局部最優(yōu)的結(jié)果。Key：傳統(tǒng)粒子群算法;線(xiàn)性慣性權(quán)重粒子群算法;遷移操作的粒子群算法一、引言移動(dòng)機(jī)器人路徑的規(guī)劃問(wèn)題一直是機(jī)器人導(dǎo)航領(lǐng)域的研究的焦點(diǎn)，移動(dòng)機(jī)器人的路徑規(guī)劃是指機(jī)器人在有障礙物的工作環(huán)境中根據(jù)起止點(diǎn)和終止點(diǎn)的信息坐標(biāo)，搜索出一條能耗低、所用時(shí)間少、距離更短并且能避開(kāi)所有障礙物的有效路徑[1]。近些年來(lái)，一些新興的算法，比如遺傳算法、蟻群算法、粒子群算法、蜂群算法等。相較于傳統(tǒng)的一些算法，通過(guò)模擬大自然生物的一種或幾種行為進(jìn)而提出的一種智能仿生算法，為解決比較復(fù)雜的環(huán)境下的路徑規(guī)劃問(wèn)題提供了新的思路[2]。本文在粒子群的基礎(chǔ)上進(jìn)行改進(jìn)，彌補(bǔ)了傳統(tǒng)粒子群算法在搜索過(guò)程中容易陷入局部最優(yōu)的這種缺點(diǎn)[3]。二、傳統(tǒng)粒子群算法的路徑規(guī)劃（一）傳統(tǒng)的粒子群算法通過(guò)對(duì)鳥(niǎo)群捕食行為研究，提出了粒子群算法，其在求解優(yōu)化的問(wèn)題時(shí)，問(wèn)題的解對(duì)應(yīng)于搜索空間中的一只鳥(niǎo)的飛行位置，這樣成為一個(gè)“粒子”。每個(gè)粒子都通過(guò)跟蹤群體所經(jīng)過(guò)個(gè)體的最優(yōu)解和整個(gè)種群的全局最優(yōu)解的影響來(lái)不斷更新自己，從而產(chǎn)生下一輪新的群體[4]。粒子的速度以及位置更新公式如下：式中：表示第次迭代中的第維速度;表示第次迭代中的第維的位置;為慣性權(quán)值;和為學(xué)習(xí)因子;為分布在之間的隨機(jī)數(shù)。（二）算法的目標(biāo)函數(shù)粒子的路徑規(guī)劃就是搜索一條從起點(diǎn)到終點(diǎn)的無(wú)碰撞最短的路徑，其目標(biāo)函數(shù)可以表示為三、改進(jìn)的粒子群算法的路徑規(guī)劃（一）線(xiàn)性慣性權(quán)重的粒子群算法在基本的粒子群算法中慣性權(quán)值是一個(gè)固定的值，當(dāng)較大的時(shí)候，粒子的全局搜索能力較強(qiáng)，但是局部的搜索能力比較的弱，可能會(huì)使粒子飛過(guò)最低點(diǎn)。當(dāng)較小的時(shí)候，可以使得粒子的局部搜索能力變強(qiáng)，但這樣粒子往往容易陷入局部最優(yōu)解，而失去全局的尋優(yōu)能力。通過(guò)改變權(quán)重對(duì)粒子群的搜索功能進(jìn)行改進(jìn)，即隨著迭代的過(guò)程，不斷的減少慣性權(quán)重的值，這樣算法在初期的探索能力較為強(qiáng)，可以再比較大的空間范圍內(nèi)搜索，在后期，權(quán)值的減小，使得可以收斂到較好的區(qū)域，進(jìn)行更為細(xì)致的搜索，權(quán)重變化式如下：式中：為最大權(quán)值;為最小權(quán)值;為最大迭代次數(shù);為粒子當(dāng)前迭代次數(shù)。其算法流程和基本粒子群算法較為相似，只不過(guò)最后要進(jìn)行判斷算法是否滿(mǎn)足終止條件，不滿(mǎn)足的話(huà)，則調(diào)整值，重新更新粒子的速度與位置繼續(xù)循環(huán)。不過(guò)隨著優(yōu)化問(wèn)題的不同，線(xiàn)性慣性權(quán)重的調(diào)整策略也不相同，這就使得線(xiàn)性慣性權(quán)重的粒子群算法在應(yīng)用中有很大的局限性。（二）生物地理學(xué)優(yōu)化算法生物地理學(xué)優(yōu)化算法，也常被稱(chēng)作BBO算法。在該算法中，我們用適用度指標(biāo)（habitatsuitabilityindex，HSI）來(lái)具體量化所研究的地區(qū)物種的適應(yīng)情況，如果計(jì)算顯示的HSI指標(biāo)較高，說(shuō)明該地區(qū)物種種類(lèi)比較豐富，處于相對(duì)穩(wěn)定的狀態(tài)，比較適合物種的生存;同樣，當(dāng)研究顯示的HSI指標(biāo)較低時(shí)，表明該地區(qū)物種種類(lèi)比較匱乏，尚未飽和[5]。在生物地理學(xué)的理論中，該地區(qū)是否適合生存，必然會(huì)引起物種的遷移，即：HSI越高，說(shuō)明該地區(qū)能容納的外來(lái)物種相對(duì)有限，其對(duì)應(yīng)的遷入率和遷出率都會(huì)比較小;當(dāng)HSI越高，表明可容納的物種比較充裕，對(duì)應(yīng)的遷入率會(huì)比較大，而遷出率比較小。針對(duì)上述物種數(shù)量和遷移的關(guān)系，總結(jié)如下：（1）隨著區(qū)域內(nèi)物種數(shù)量的不斷增加，外來(lái)物種的遷入會(huì)加劇擁擠程度，因此潛入率會(huì)逐漸減小，同時(shí)由于競(jìng)爭(zhēng)關(guān)系，會(huì)導(dǎo)致一部分物種從該區(qū)域遷出，使得遷出率不斷增加;（2）當(dāng)物種數(shù)量S增加至極限時(shí)，處于飽和狀態(tài)，區(qū)域內(nèi)的物種只能出不能進(jìn)，對(duì)應(yīng)的遷入率將至0，而遷出率會(huì)增長(zhǎng)到最大，即最大遷出率;（3）如果該區(qū)域內(nèi)物種數(shù)量為0時(shí)，其遷出率必定為0。（三）遷移操作遷移操作是生物地理學(xué)優(yōu)化算法的核心步驟，在優(yōu)化的過(guò)程中，通過(guò)物種種群的不斷遷入、遷出操作，可以不斷的改變區(qū)域系統(tǒng)內(nèi)的的適應(yīng)度指標(biāo)HSI。如果將最大遷出率E、最大遷入率I設(shè)置為1，可容納物種的區(qū)域數(shù)量用來(lái)表示，對(duì)應(yīng)的某一個(gè)區(qū)域用表示，其對(duì)應(yīng)的第維的適宜度分量用來(lái)表示。通過(guò)上述的分析可以看出，遷入和遷出操作實(shí)際上是通過(guò)區(qū)域間信息的不斷交互實(shí)現(xiàn)對(duì)大面積區(qū)域的空間搜索。遷出操作的更新過(guò)程需要借助隨機(jī)數(shù)，可總結(jié)為：對(duì)于區(qū)域，如果，則由遷入率決定將要被替換的區(qū)域，執(zhí)行遷移操作.，并且。如果，則不執(zhí)行遷移操作。如此循環(huán)，直到對(duì)所有的變量都執(zhí)行完上述操作，就產(chǎn)生了一個(gè)新的區(qū)域。然后對(duì)下一個(gè)區(qū)域進(jìn)行操作，如此循環(huán)，直到所有區(qū)域都完成此操作。利用遷入率的選擇方法為：計(jì)算其余max-1個(gè)區(qū)域的遷入率，根據(jù)貪婪算法求出第一個(gè)滿(mǎn)足的區(qū)域。同樣的遷入操作的更新過(guò)程與此相似因此可以看出，當(dāng)區(qū)域的適應(yīng)度越大，表明所能接受的物種數(shù)量的總數(shù)就越高，當(dāng)區(qū)域的適用度越小時(shí)，所能接受的物種數(shù)量的總數(shù)就越少。針對(duì)上述關(guān)系可以將物種數(shù)量用適應(yīng)度函數(shù)值替換：其中，和分別表示當(dāng)前棲息地種群中適應(yīng)度函數(shù)的最大值和最小值。（四）基于遷移操作的改進(jìn)粒子群算法為了有效避免粒子群算法在迭代過(guò)程中容易陷入局部最優(yōu)的缺點(diǎn)，充分提高粒子的全局以及局部的搜索能力，提高算法的收斂性能，將生物地理學(xué)優(yōu)化算法與改進(jìn)后的粒子群算法相結(jié)合，當(dāng)粒子適應(yīng)度較差時(shí)，通過(guò)對(duì)該粒子施加一定概率的遷移操作，增加粒子的遷入和遷出效果，使得該被困粒子可以順利的離開(kāi)被困區(qū)域，達(dá)到動(dòng)態(tài)調(diào)整搜索步長(zhǎng)和優(yōu)化粒子的更新策略，從而避免了粒子陷入死循環(huán)或者局部最優(yōu)的結(jié)果，使得算法性能更優(yōu)[8]。在粒子迭代的過(guò)程中，如果經(jīng)過(guò)連續(xù)的三次更新后，該粒子的適應(yīng)度值仍然小時(shí)，我們則定義該粒子陷入了死區(qū)，此時(shí)，需要外力強(qiáng)制介入遷移操作，幫助粒子脫離困境。因此，本文將判斷粒子是否處于死區(qū)的方法設(shè)定為：對(duì)適宜度值的粒子，需要計(jì)算其最近三次迭代（包含本次）目標(biāo)函數(shù)值的方差，若小于設(shè)定值，則認(rèn)為該粒子陷入死區(qū)?；谏锏乩韺W(xué)優(yōu)化的算法的原理，結(jié)合粒子群的特點(diǎn)，可將遷移操作定義如下：其中：表示遷移操作的力度;表示當(dāng)前迭代下的全局最優(yōu)值;表示個(gè)體在當(dāng)前迭代下該粒子的歷史最優(yōu)值;表示進(jìn)行遷移操作的系數(shù)，其與粒子陷入死區(qū)的程度有關(guān)。當(dāng)粒子并未陷入死區(qū)時(shí)，，表示不進(jìn)行遷移操作;而當(dāng)系統(tǒng)判定粒子陷入死區(qū)時(shí)，參考，生物地理學(xué)的遷入率和遷出率，將定義為：其中：表示當(dāng)前粒子的適用度值;表示粒子種群中適應(yīng)度最小值;表示粒子種群中平均適應(yīng)度。由上式可以看出，當(dāng)粒子的適應(yīng)度越差，即陷入死區(qū)的程度越深，遷移系數(shù)越大，即表示將要執(zhí)行的遷移力度越大，通過(guò)較大的遷移來(lái)影響該粒子的速度和位置更新。本文將在改進(jìn)后的粒子群算法中加入遷移操作，將粒子群的迭代過(guò)程中增加了遷入、遷出操作，具體表現(xiàn)如下：置一個(gè)概率值，對(duì)于第個(gè)粒子，如果>，則對(duì)進(jìn)行遷移操作，使用基于遷入率的遷移操作進(jìn)行位置更新;如果，則進(jìn)行遷移率的操作，執(zhí)行基于遷出率的遷移操作進(jìn)行位置更新;如果值相等，則進(jìn)行到執(zhí)行不進(jìn)行遷移操作。其中randn（0，1）表示均值為0，方差為1的高斯分布。通過(guò)上述改進(jìn)之后，當(dāng)經(jīng)過(guò)三次判斷該粒子陷入死區(qū)時(shí)，使用下式對(duì)粒子進(jìn)行更新：三、全局路徑規(guī)劃仿真和結(jié)果分析應(yīng)用柵格法建立環(huán)境地圖，在環(huán)境中采用上述的粒子群算法、慣性權(quán)重粒子群算法、遷移操作的粒子群算法進(jìn)行路徑的規(guī)劃并比較分析三種算法在簡(jiǎn)單以及復(fù)雜環(huán)境中的尋找最佳路徑長(zhǎng)度的能力。進(jìn)行了五次仿真，在復(fù)雜情況下，遷移操作的粒子群算法都可以得到更小的目標(biāo)函數(shù)即路徑長(zhǎng)度。由以上的仿真圖還有收斂曲線(xiàn)可以得知：在復(fù)雜的環(huán)境下，基本粒子群算法迭代了182次之后陷入了局部最優(yōu)解，其最優(yōu)的路徑適應(yīng)度函數(shù)為72.8112。線(xiàn)性慣性權(quán)重的粒子群算法在21次迭代得到局部最優(yōu)解，其路徑的函數(shù)為69.98291。而采用了遷移操作的粒子群算法，在進(jìn)行路徑的規(guī)劃時(shí)，當(dāng)?shù)?80次時(shí)跳出局部的最優(yōu)解，在當(dāng)前最大迭代次數(shù)下，最優(yōu)最有效的路徑適應(yīng)度函數(shù)為64.3259。綜上所述，遷移操作的粒子群算法在復(fù)雜的環(huán)境下所能得到的路徑長(zhǎng)度更短。四、結(jié)束語(yǔ)傳統(tǒng)的粒子群算法對(duì)于機(jī)器人路徑規(guī)劃中具有建模簡(jiǎn)單、計(jì)算過(guò)程簡(jiǎn)單、收斂性速度快以及參數(shù)較少等優(yōu)點(diǎn)，但是也較容易陷入局部的最優(yōu)解，從而在一下復(fù)雜環(huán)境下得不到全局的最優(yōu)解，使得優(yōu)化結(jié)果不理想。因此結(jié)合了遷移操作的粒子群算法，能夠彌補(bǔ)以上缺點(diǎn)。并通過(guò)計(jì)算機(jī)仿真驗(yàn)證了該算法的有效性，合理性，是優(yōu)于傳統(tǒng)的粒子群算法的。Reference[1]張穎，吳成東，原寶龍.機(jī)器人路徑規(guī)劃方法綜述[J].控制工程，2003，10（5）;152-155.[2]孫波，陳衛(wèi)東，席裕庚.基于粒子群優(yōu)化算法的移動(dòng)機(jī)器人全局路徑規(guī)劃[J].控制與決策，2005，20（9）;1052-1055.[3]李偉莉，趙東輝.基于柵格法與神經(jīng)元的機(jī)器人全區(qū)域覆蓋算法[J].機(jī)械設(shè)計(jì)與制造，2017（08）：232-238.[4]劉旭.粒子群算法及其