孫 冬，趙開新

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

0 引言

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

1 粒子群算法

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

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

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

2 粒子群算法的改進

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

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

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

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

2.2 動態(tài)調(diào)整學習因子

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

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

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

3 改進后粒子群算法在移動機器人路徑規(guī)劃中的應用

3.1 算法步驟

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

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

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

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

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

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

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

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

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

3.2 仿真實驗

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

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

圖1 仿真柵格圖

3.2.2 實驗結(jié)果及分析

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

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

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

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

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

4 結(jié)語

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