改進(jìn)粒子群算法在移動(dòng)機(jī)器人路徑規(guī)劃中的應(yīng)用研究

孫 冬，趙開新

（河南工學(xué)院 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，河南 新鄉(xiāng) 453003）

0 引言

目前常用的移動(dòng)機(jī)器人路徑規(guī)劃方法主要有蟻群算法、神經(jīng)網(wǎng)絡(luò)算法[1-2]、人工勢場法、遺傳算法、模擬退火算法、粒子群算法等[3-4]。與其他算法相比，粒子群算法具有參數(shù)設(shè)置少、實(shí)現(xiàn)簡單等優(yōu)點(diǎn)[5-6]。但粒子群算法本身還存在著一些缺陷，如收斂速度慢、有早熟現(xiàn)象等，目前對(duì)粒子群算法的改進(jìn)有基于動(dòng)態(tài)調(diào)整慣性權(quán)重和基于收縮因子兩種方法，但大多改進(jìn)算法不能突破經(jīng)典慣性權(quán)重呈線性遞減的約束，粒子不能根據(jù)自我的位置動(dòng)態(tài)調(diào)整對(duì)局部和全局信息的依賴度，導(dǎo)致粒子群算法效率低和次優(yōu)路徑的產(chǎn)生。文獻(xiàn)[7]針對(duì)粒子收斂速度慢、搜索精度不高和算法性能過度依賴參數(shù)的選取等缺點(diǎn)，提出了一種非線性指數(shù)慣性權(quán)重粒子優(yōu)化算法，使算法根據(jù)粒子最大、適應(yīng)度值最小的指數(shù)函數(shù)更新慣性權(quán)重，突破了經(jīng)典慣性權(quán)重呈線性遞減的約束，該算法有利于粒子在尋優(yōu)過程中跳出局部最優(yōu)，使粒子較快地收斂到全局最優(yōu)位置，但是算法收斂時(shí)迭代次數(shù)過多。本文通過優(yōu)化粒子群算法的權(quán)重系數(shù)來動(dòng)態(tài)調(diào)整粒子群算法的全局和局部搜索能力，通過優(yōu)化學(xué)習(xí)因子來動(dòng)態(tài)調(diào)整粒子對(duì)自我和群體的依賴程度，減少算法收斂時(shí)的迭代次數(shù)，并將改進(jìn)后的粒子群算法應(yīng)用到移動(dòng)機(jī)器人路徑規(guī)劃中，引導(dǎo)機(jī)器人快速高效地尋找全局最優(yōu)路徑。

1 粒子群算法

粒子群算法（Particle swarm optimization algorithm, PSO）是根據(jù)鳥群的捕食和返巢活動(dòng)提出的一種啟發(fā)式算法[8]，可設(shè)置數(shù)學(xué)模型的過程如下：搜索空間為D維，種群粒子個(gè)數(shù)為N，各粒子在D維空間上第t次迭代后位置為每個(gè)粒子的速度為其中i[1,m]，通過公式（1）和（2）來更新各粒子的速度和位置。

公式（1）中c1為個(gè)人認(rèn)知因子，c2為社會(huì)認(rèn)知因子，為權(quán)重系數(shù)，表示粒子個(gè)體位置最優(yōu)解，表示粒子群體位置最優(yōu)解,r1和r2為介于0 和1 之間的兩個(gè)隨機(jī)數(shù)。

在粒子群算法中，個(gè)體位置最優(yōu)解按公式（3）進(jìn)行更新，群體位置最優(yōu)解按公式（4）進(jìn)行更新[9-10]。

2 粒子群算法的改進(jìn)

在粒子群算法中，權(quán)重系數(shù)的值是恒定的，粒子不會(huì)根據(jù)自我位置的優(yōu)劣來動(dòng)態(tài)調(diào)整下一次迭代的速度和位置；個(gè)人認(rèn)知因子1c和社會(huì)認(rèn)知因子2c不會(huì)隨著時(shí)間的推移動(dòng)態(tài)調(diào)整下一次迭代的速度和位置，因此會(huì)導(dǎo)致算法局部收斂和收斂精度低的現(xiàn)象，本文通過動(dòng)態(tài)調(diào)整權(quán)重系數(shù)和動(dòng)態(tài)調(diào)整學(xué)習(xí)因子兩個(gè)方面對(duì)粒子群算法進(jìn)行改進(jìn)。

2.1 動(dòng)態(tài)調(diào)整權(quán)重系數(shù)

優(yōu)化后的權(quán)重系數(shù)值由公式（5）得出。

式（5）中，i為第i個(gè)粒子在第t次迭代的慣性系數(shù)值，max_iter為第i個(gè)粒子的最大迭代次數(shù)，min和max分別為第i個(gè)粒子慣性系數(shù)的最小值和最大值，粒子i的適應(yīng)度值為fi，當(dāng)前粒子群適應(yīng)度的平均值為favg、最小值為fmin。

2.2 動(dòng)態(tài)調(diào)整學(xué)習(xí)因子

在粒子群算法中，個(gè)人認(rèn)知因子1c和社會(huì)認(rèn)知因子2c不會(huì)隨著時(shí)間的推移動(dòng)態(tài)調(diào)整下一次迭代的速度和位置，改進(jìn)后的個(gè)人認(rèn)知因子由式（6）得出，社會(huì)認(rèn)知因子由式（7）得出。

式（6）中1ic介于c1max和c1min之間，為粒子的動(dòng)態(tài)個(gè)人認(rèn)知因子，2ic介于c2max和c2min之間，為粒子群的動(dòng)態(tài)社會(huì)認(rèn)知因子。從式（6）可以看出，隨著時(shí)間的推移，1ic的值逐漸減?。粡氖剑?）看出，隨著時(shí)間的推移，2ic的值逐漸增大。

從改進(jìn)后的個(gè)人認(rèn)知因子和社會(huì)認(rèn)知因子的算式可以看出，在搜索開始時(shí)，粒子的自我學(xué)習(xí)能力比較弱、向社會(huì)群體學(xué)習(xí)能力比較強(qiáng)，全局搜索能力比較強(qiáng)，保持了種群的多樣性；在搜索將要結(jié)束時(shí)粒子的自我學(xué)習(xí)能力比較強(qiáng)、向社會(huì)群體學(xué)習(xí)能力比較弱，因此具有較強(qiáng)的局部搜索能力，從而提高了搜索的效率和精度。調(diào)整粒子群算法的權(quán)重系數(shù)和學(xué)習(xí)因子后粒子速度更新公式為（8）。

3 改進(jìn)后粒子群算法在移動(dòng)機(jī)器人路徑規(guī)劃中的應(yīng)用

3.1 算法步驟

移動(dòng)機(jī)器人路徑規(guī)劃的目的就是從初始節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)找到一條無碰撞的距離最短路徑，而粒子群算法正是解決粒子從起始點(diǎn)到終點(diǎn)的最優(yōu)路徑問題，把改進(jìn)后的粒子群算法應(yīng)用到移動(dòng)機(jī)器人路徑規(guī)劃中，可以協(xié)助機(jī)器人快速高效地搜索最優(yōu)路徑。具體步驟如下：

步驟1：設(shè)置機(jī)器人運(yùn)動(dòng)的初始環(huán)境，初始化粒子速度、位置等參數(shù)。

步驟2：通過適應(yīng)度函數(shù)計(jì)算粒子群中各粒子適應(yīng)度的值。

步驟3：由公式（3）更新粒子個(gè)體最優(yōu)值，根據(jù)公式（4）更新種群最優(yōu)值。

步驟4：由公式（5）求出該粒子權(quán)重系數(shù)的值。

步驟5：根據(jù)時(shí)間t和粒子自我因子的最大、最小值，由公式（6）求解個(gè)人認(rèn)知因子的值。

步驟6：根據(jù)時(shí)間t和社會(huì)認(rèn)知因子的最大最小值，由公式（7）求解社會(huì)認(rèn)知因子的值。

步驟7：由公式（8）更新粒子的速度，由公式（2）更新粒子的位置。

步驟8：當(dāng)達(dá)到算法結(jié)束的條件則終止搜索，否則轉(zhuǎn)到步驟2 繼續(xù)執(zhí)行。

3.2 仿真實(shí)驗(yàn)

3.2.1 實(shí)驗(yàn)環(huán)境及參數(shù)

用 MATLAB 構(gòu)建柵格環(huán)境的仿真平臺(tái)如圖1 所示，障礙物分布在已知的全局靜態(tài)10×10 的柵格矩陣中并用黑色填充單元格表示。設(shè)置機(jī)器人起點(diǎn)坐標(biāo)為S(0，0)，終點(diǎn)坐標(biāo)為E（10,10）。粒子群算法中種群規(guī)模為100，粒子維數(shù)為10，迭代次數(shù)為40，權(quán)重系數(shù)最大值max 為0.9，權(quán)重系數(shù)最小值min 為0.4，個(gè)人認(rèn)知因子最大值c1max為1.2，個(gè)人認(rèn)知因子最小值c1min為0.6，社會(huì)認(rèn)知因子最大值c2max為1.2，社會(huì)認(rèn)知因子最小值c2min為0.6。在上述環(huán)境中分別采用粒子群算法PSO、文獻(xiàn)[7]粒子群算法EIW-PSO 和本文改進(jìn)的粒子群算法進(jìn)行機(jī)器人路徑規(guī)劃。

圖1 仿真柵格圖

3.2.2 實(shí)驗(yàn)結(jié)果及分析

采用三種不同的算法進(jìn)行移動(dòng)機(jī)器人路徑規(guī)劃后仿真結(jié)果如圖2 所示，可以看出本文算法搜索到的路徑最短。各路徑的詳細(xì)距離長度如表1 所示，可以看出，在同一仿真環(huán)境下，采用粒子群算法求得的路徑長度為18.4275，距離平均值為18.7543；采用EIW-PSO 算法求得的路徑長度為17.8562，距離平均值為18.1278；采用本文改進(jìn)的粒子群算法求得的路徑長度為15.2471，距離平均值為16.6827；采用本文優(yōu)化后的算法所得到的路徑長度和距離平均值均比粒子群算法和文獻(xiàn)[7]粒子群算法EIW-PSO 有了明顯縮短。

圖2 三種算法的路徑規(guī)劃對(duì)比

表1 三種算法的路徑長度比較

三種算法找到路徑所需要的迭代次數(shù)如圖3 所示，可以看出采用本文改進(jìn)的粒子群算法進(jìn)行路徑規(guī)劃，當(dāng)算法收斂時(shí)迭代次數(shù)明顯小于粒子群算法PSO 和文獻(xiàn)[7]粒子群算法EIW-PS0。算法收斂后，本文算法在相同的迭代次數(shù)下粒子適應(yīng)度值最小。這正是由于通過優(yōu)化粒子群算法的權(quán)重系數(shù)和學(xué)習(xí)因子后，搜索前期增強(qiáng)全局搜索能力，并增強(qiáng)了自我學(xué)習(xí)能力；搜索后期加大局部搜索能力，增強(qiáng)了向群體學(xué)習(xí)能力。仿真結(jié)果表明，應(yīng)用本文算法進(jìn)行路徑搜索提高了搜索效率，加快了收斂速度。

圖3 三種算法迭代次數(shù)比較

4 結(jié)語

隨著智能機(jī)器人技術(shù)的快速發(fā)展，路徑規(guī)劃問題逐漸成為國內(nèi)外許多學(xué)者研究的熱點(diǎn)。本文從權(quán)重系數(shù)和學(xué)習(xí)因子兩個(gè)方面對(duì)粒子群算法進(jìn)行改進(jìn)，改進(jìn)的算法突破了經(jīng)典慣性權(quán)重呈線性遞減的約束，提高了收斂速度。把改進(jìn)的粒子群算法應(yīng)用在移動(dòng)機(jī)器人路徑規(guī)劃中，結(jié)果表明該算法具有一定的優(yōu)勢，對(duì)未來移動(dòng)機(jī)器人路徑規(guī)劃有一定的指導(dǎo)意義。