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

封建湖，張婷宇，封 碩，鄭寶娟

（1.長安大學(xué)理學(xué)院，陜西 西安710064；2.長安大學(xué)工程機(jī)械學(xué)院，陜西 西安710064）

1 引言

路徑規(guī)劃問題是在有復(fù)雜障礙物環(huán)境中搜索從初始點(diǎn)到目標(biāo)點(diǎn)的無碰撞路徑［1］。機(jī)器人的路徑規(guī)劃即對機(jī)器人行駛路徑進(jìn)行合理的決策。對于已知地圖環(huán)境的情況，粒子群優(yōu)化（PSO）算法是一種模擬鳥類飛行的優(yōu)化算法，具有收斂速度快、算法易于實(shí)現(xiàn)等優(yōu)點(diǎn)；遺傳算法（GA）是基于生物種群進(jìn)化的算法，具有全局收斂性的優(yōu)勢。然而這兩種算法都有各自的局限性：粒子群算法容易陷入早熟、遺傳算法收斂速度較慢等問題。針對這種情況，文獻(xiàn)［2］提出了一種PSO和GA的混合算法，混合算法的初始種群由PSO生成，文獻(xiàn)［3］人提出了一種只與GA突變算子結(jié)合的PSO算法，避免了粒子陷入局部最優(yōu)。文獻(xiàn)［4］在為旅客提供最佳路徑選擇的旅行商問題中提出PSO-GA算法，得到了很好的效果，但是會造成收斂代數(shù)大幅度增加。

針對算法中的不足，引入基于劃分的聚類方法中的Kmeans算法，對粒子進(jìn)行聚類，把粒子劃分為若干個子群，使相當(dāng)數(shù)量的具有較優(yōu)適應(yīng)度值的粒子位置信息傳遞到下一代粒子中。對每個子群采用一定規(guī)則的交叉和變異算子，從而提高粒子群算法的種群多樣性。在每個子區(qū)內(nèi)更新粒子速度和位置時，隨著代數(shù)的增加改變慣性權(quán)重和加速系數(shù)。最后通過計(jì)算機(jī)仿真實(shí)驗(yàn)驗(yàn)證了該算法的有效性。

2 傳統(tǒng)粒子群算法

粒子群算法是用位置、速度、適應(yīng)度來描述粒子的運(yùn)動特征，每次迭代通過跟蹤粒子的個體極值Pbest和群體極值Gbest動態(tài)更新［5］。個體極值Pbest是粒子在迭代過程中得到的適應(yīng)度值最優(yōu)的個體所在位置，群體極值Gbest是搜索到所有粒子的適應(yīng)度值最優(yōu)個體所在位置。

傳統(tǒng)粒子群算法通過以下公式在每次迭代過程中更新速度和位置：

式中：ω—慣性系數(shù)，j=1,2,…,n—維數(shù)，c1、c2—加速度因子，r1、r2—［0，1］區(qū)間的隨機(jī)數(shù)。為了使粒子更好地搜索，通常將粒子的位置和速度限制在一定范圍內(nèi)[ -xmax,xmax]、[ -vmax,vmax]。

傳統(tǒng)粒子群算法的劣勢在路徑規(guī)劃問題中體現(xiàn)為：粒子群算法是全局隨機(jī)搜索算法，但是如果缺少逃逸策略容易陷入局部最優(yōu)解［6］。對于智能機(jī)器人，不僅需要盡可能縮短路徑長度，更加需要在復(fù)雜環(huán)境中減少路徑的起伏，使其平滑地走到終止點(diǎn)，避免局部最優(yōu)的出現(xiàn)。

3 聚類融合交叉粒子群算法

3.1 環(huán)境建模

針對已知地圖情況下的機(jī)器人路徑規(guī)劃問題，柵格法是由文獻(xiàn)［7］于1968年提出。該方法將智能機(jī)器人實(shí)際運(yùn)動環(huán)境分解成具有二值信息的網(wǎng)格單元，并通過判斷障礙物是否占用此網(wǎng)格單元進(jìn)行分類，處理后的路徑規(guī)劃問題就轉(zhuǎn)化成在帶有序號表示的柵格網(wǎng)中尋找兩個網(wǎng)絡(luò)節(jié)點(diǎn)的最優(yōu)路徑問題。

將已知地圖柵格化，在柵格化的空間中分布著若干障礙物，0表示自由柵格，在圖中用白色表示；1表示障礙柵格，在圖中用黑色表示。

3.2 適應(yīng)度函數(shù)的選擇

在尋找最優(yōu)路徑時，要綜合考慮路徑的長短和是否成功避開障礙物。在實(shí)際的三維地圖轉(zhuǎn)換為二維柵格表示中，障礙物點(diǎn)可能是機(jī)器不能穿過的點(diǎn)，也可能是坡度較大、易損失能量的點(diǎn)。綜合各種因素，改進(jìn)的算法選擇的適應(yīng)度函數(shù)如下所示：

式中：N－路徑段數(shù)，n－不可行的路徑段數(shù)目，D－已走的路徑總長度，通過公式（4）進(jìn)行計(jì)算。

式中：(xs,ys),(xf,yf)—路徑的起點(diǎn)坐標(biāo)與終點(diǎn)坐標(biāo)。

3.3 K均值聚類

為了保持目標(biāo)粒子種群的多樣性，引入K均值聚類算法。K均值聚類算法［8］是一種基于原型的目標(biāo)函數(shù)聚類方法，將一批現(xiàn)實(shí)或抽象的數(shù)據(jù)對象分組成為多個類或簇的過程，是根據(jù)目標(biāo)粒子的編碼設(shè)計(jì)，定義目標(biāo)粒子i與粒子j之間的距離的度量函數(shù)，改進(jìn)后的算法采用基于初始聚類質(zhì)心產(chǎn)生法。

在聚類融合交叉粒子群算法中，將初始種群N中的粒子根據(jù)K-means算法分為若干個子種群Ci，由每個子種群的最優(yōu)粒子以及個體最優(yōu)粒子的速度和位置信息指導(dǎo)下一代粒子更新進(jìn)行速度和位置值：

式中，(i=1,2,…,N)—粒子i目前搜索到的最優(yōu)個體位置，qi(i=1,2,…,K)—每個聚類區(qū)Ci(i=1,2,…,m)中的粒子搜索到的最優(yōu)位置。

3.4 交叉操作

交叉算子是指以某種方式對兩個染色體交換某部分基因，得到兩個新的個體［9］。改進(jìn)的具體思想是：

（1）交叉概率初始化。為了加快收斂速度，交叉概率初始化時采用在迭代過程中隨代數(shù)線性遞增的方式，記為Cross=(cross1,cross2,…,crossN)，其中N為粒子數(shù)。算法中迭代次數(shù)t越大，粒子進(jìn)行交叉操作的概率crosst也隨之增大。

（2）判斷是否交叉。對具有交叉可能性的粒子（i），隨機(jī)產(chǎn)生一個數(shù)字randi與之對應(yīng)，當(dāng)隨機(jī)數(shù)比交叉概率小時，即randi＜crosst，則對粒子i進(jìn)行交叉操作，進(jìn)入步驟3；反之，則粒子i跳過交叉操作（步驟3），執(zhí)行算法的下一步。

（3）交叉操作。若粒子i需要進(jìn)行交叉操作時，在粒子路徑點(diǎn)范圍內(nèi)，隨機(jī)產(chǎn)生一個位置區(qū)間[xa,xb]，把分區(qū)極值qi位置區(qū)間內(nèi)的路徑點(diǎn)覆蓋在被粒子i相應(yīng)位置區(qū)間內(nèi)，執(zhí)行算法的下一步。

假設(shè)粒子路徑交叉區(qū)間是［3，4］，則交叉過程，如表1所示。

表1 粒子交叉操作示例Tab.1 The Example of Crossover

3.5 變異操作

變異算子是指對染色體中的一部分進(jìn)行突變，使其轉(zhuǎn)化為一個新的個體［9］。相應(yīng)的改進(jìn)思路為：

（1）變異概率初始化。采用迭代過程中線性遞減的方式定義變異概率，記為Var′=(var1′,var2′,…,varN′)，算法中迭代次數(shù)t越大，粒子進(jìn)行變異操作的概率vart′也隨之減小。

（2）判斷是否變異。對具有變異可能性的粒子i，隨機(jī)產(chǎn)生一個數(shù)字randi與之對應(yīng)，當(dāng)隨機(jī)數(shù)比交叉概率小時，即randi＜vart′，則對粒子i進(jìn)行變異操作，進(jìn)入步驟3；反之，則粒子i跳過步驟3，執(zhí)行算法的下一步。

（3）變異操作。當(dāng)粒子i達(dá)到變異概率vart′時，隨機(jī)選擇粒子i的一個路徑點(diǎn)(xc,yc)，使新生成的路徑點(diǎn)代替舊的路徑點(diǎn)，繼續(xù)算法的下一步。假設(shè)隨機(jī)產(chǎn)生的變異路徑點(diǎn)位置為3，則變異后的粒子，如表2所示。

表2 粒子變異操作示例Tab.2 The Example of Mutation.

3.6 自適應(yīng)調(diào)整加速系數(shù)和慣性權(quán)重

在機(jī)器人路徑規(guī)劃過程中，早期希望機(jī)器人能有更多探索的能力，這樣保持路徑的多樣性；在后期希望機(jī)器人根據(jù)走過的路徑信息，有較多的自我學(xué)習(xí)能力，這樣使路徑能較快地收斂于全局最優(yōu)解。為此，對傳統(tǒng)的粒子群加速系數(shù)進(jìn)行改進(jìn)，具體為：

式中：c1max和c1min—加速系數(shù)c1的上下限。c2max和c2min—加速系數(shù)c2的上下限。tmax—迭代的最大次數(shù)，t—當(dāng)前迭代次數(shù)。

3.7 聚類融合交叉粒子群算法流程圖

圖1 聚類融合交叉粒子群算法流程圖Fig.1 Process of Clustering Combined with Crossed PSO Algorithm

4 仿真及結(jié)果分析

在MATLAB上分別用傳統(tǒng)粒子群算法、具有交叉、變異算子的粒子群算法和聚類融合交叉粒子群算法對虛擬輪式機(jī)器人進(jìn)行了對比仿真實(shí)驗(yàn)。

首先對復(fù)雜地圖初始柵格化，仿真過程中地圖大小從10×10逐步擴(kuò)充到40×40，起始點(diǎn)定為（1，1），終止點(diǎn)為相應(yīng)矩陣的對角點(diǎn)，并隨機(jī)生成一定比例的障礙物。

隨著柵格地圖的規(guī)模擴(kuò)大，收斂代數(shù)和粒子數(shù)量都需要以一定比例增長才可以得到較為理想的路線。為了更好展示不同粒子群算法的應(yīng)用效果，以40×40的路徑規(guī)劃效果為例說明。實(shí)驗(yàn)中參數(shù)設(shè)置，如表3所示。

表3 路徑規(guī)劃參數(shù)表Tab.3 Parameter Setting for Path Planning

為了更加直觀看出算法的優(yōu)勢，將算法運(yùn)行50次效果，比較，如表4所示。

表4 算法運(yùn)行50次仿真結(jié)果Tab.4 The Simulation Result for Three Algorithms Run Fifty Times

根據(jù)適應(yīng)度公式（3）可以得到，適應(yīng)度值越大，路徑長度越小，路徑表現(xiàn)越優(yōu)秀。在柵格地圖較大、環(huán)境較為復(fù)雜的情況下，當(dāng)總的迭代次數(shù)和粒子數(shù)目一定時，交叉粒子群算法比傳統(tǒng)粒子群算法的最優(yōu)路徑長度縮短約16.3%，其中傳統(tǒng)粒子群算法收斂過快，容易陷入早熟；交叉粒子群則有效避免了早熟現(xiàn)象，從而減少了產(chǎn)生局部最優(yōu)路徑的可能性，但是交叉粒子群算法比基礎(chǔ)粒子群的每一代迭代時間多了約64.8%，收斂代數(shù)增加了約90.8%，計(jì)算成本較高。聚類融合交叉粒子群是在交叉粒子群的基礎(chǔ)上，加了K-means聚類分析算法，比交叉粒子群算法收斂代數(shù)減少約23.8%。在保證相對最短路徑的情況下，跳出局部最優(yōu)有很好的效果，同時程序運(yùn)行過程中，聚類融合交叉粒子群中的分區(qū)操作，雖然使存儲空間有少許增加，卻大大減小了收斂代數(shù)，加快了收斂速度，且每一代的運(yùn)行時間與交叉粒子群相差細(xì)微，最終得到最優(yōu)路徑的總時間減少約45.9%，可以看出改進(jìn)后的算法對點(diǎn)到點(diǎn)的機(jī)器人路徑規(guī)劃具有較好的應(yīng)用價值。

從上述比較效果來看，本文改進(jìn)后的算法搜索結(jié)果在精度上有明顯的提高。算法在迭代的開始對初始群體按照K-means聚類法分成若干個子群體，從而在迭代過程中每個粒子根據(jù)其個體極值和所在子種群中的最好個體更新自己的位置和速度，增加粒子的信息交換，有助于引導(dǎo)算法向可行路徑方向搜索。為了克服傳統(tǒng)算法在后期易于陷入局部最優(yōu)的缺陷，引入交叉、變異算子，幫助算法擺脫局部極值點(diǎn)的束縛，極大地提高了算法的搜索效率，有效地實(shí)現(xiàn)了全局搜索能力及收斂速度方面的平衡。

下面將更加直觀地給出采用傳統(tǒng)粒子群算法、帶有交叉、變異算子的粒子群算法和聚類融合交叉粒子群算法的最優(yōu)路徑圖，從起始點(diǎn)到目標(biāo)點(diǎn)單獨(dú)執(zhí)行10000代得到的路徑中，長度最短即適應(yīng)度值最大的一次規(guī)劃路徑圖，如圖2所示。

圖2 三種算法的路徑圖Fig.2 Path Map of Three Algorithms

從上圖中容易看出，圖2（a）傳統(tǒng)粒子群優(yōu)化算法在相同迭代次數(shù)下走出的路徑效果最差，雖然找出一條不和障礙物重疊的路線，但是粒子路線跳躍起伏較大，使機(jī)器人耗能隨之增大，明顯是一條局部最優(yōu)路徑。圖2（b）是在傳統(tǒng)粒子群中加入交叉、變異算子后的結(jié)果，可以看出減少了一些冗余路線，效果雖然有所改進(jìn)，但是耗費(fèi)時間長，一些區(qū)域還存在可以優(yōu)化的可能性。而在交叉粒子群的基礎(chǔ)上加入K-means聚類分析的改進(jìn)算法，圖2（c）得到的最優(yōu)路徑精度相對較高，在相同運(yùn)行代數(shù)下，路徑長度明顯最短，路線較為順滑，相對而言降低了拐點(diǎn)數(shù)和無效路徑段，實(shí)際過程中可以達(dá)到減少能量消耗、機(jī)器損耗的效果。

為了更直觀看出加入聚類算法的優(yōu)勢，對交叉粒子群算法和聚類融合交叉粒子群算法收斂情況進(jìn)行比較（參數(shù)設(shè)置：粒子數(shù)為3000，迭代次數(shù)為10000，聚類數(shù)為10），如圖3所示。

圖3 兩種算法收斂情況對比圖Fig.3 Comparison of the Convergence Curve

對比結(jié)果可以看出，加入K-means聚類分析算法，能夠使收斂代數(shù)穩(wěn)定下降，加快收斂速度，使得獲得最優(yōu)路徑的總計(jì)算時間也大大縮短，對于智能路徑尋優(yōu)有很好的效果。

雖然加入聚類的思想可以明顯達(dá)到加速收斂速度的效果，但是聚類的數(shù)目不同，產(chǎn)生的效果也不完全相同。選取5000粒子，10000代，在相同環(huán)境下對以下聚類數(shù)目進(jìn)行對比實(shí)驗(yàn)，對比結(jié)果，如表5所示。

表5 聚類效果對比Tab.5 Clustering’s Comparison of Effects

如果初始化參數(shù)時選擇的聚類數(shù)目過多，會導(dǎo)致這些群體極值中保留很多適應(yīng)度值適中甚至偏差的粒子信息，將直接影響下一代的優(yōu)化結(jié)果，最終導(dǎo)致形成的最優(yōu)路徑趨于局部最優(yōu)的結(jié)果。在仿真實(shí)驗(yàn)中，我們可以根據(jù)柵格地圖的復(fù)雜度，選擇適中的分區(qū)數(shù)目，在加快收斂速度的同時選擇相對運(yùn)算成本較小、路徑長度較優(yōu)的參數(shù)設(shè)置。

5 結(jié)論

在機(jī)器人路徑規(guī)劃虛擬仿真過程中，通過引入聚類分析的思想和遺傳算法中的交叉、變異算子到傳統(tǒng)粒子群算法中，避免了粒子群算法在復(fù)雜環(huán)境下容易出現(xiàn)停滯現(xiàn)象，最終出現(xiàn)局部最優(yōu)的結(jié)果，有效的幫助機(jī)器人找到最優(yōu)路徑。通過對比仿真實(shí)驗(yàn)可以看出，改進(jìn)后的算法有以下三個優(yōu)點(diǎn)：

（1）加入交叉、變異算子，增加了粒子多樣性。

（2）引入復(fù)雜環(huán)境下適合的聚類數(shù)目，可以加快算法收斂速度。

（3）在路徑規(guī)劃的應(yīng)用中，改進(jìn)后的算法搜索出的路徑明顯優(yōu)于傳統(tǒng)粒子群算法和交叉粒子群算法。