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

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

1 引言

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

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

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

粒子群算法是用位置、速度、適應(yīng)度來描述粒子的運動特征，每次迭代通過跟蹤粒子的個體極值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ū)間的隨機數(shù)。為了使粒子更好地搜索，通常將粒子的位置和速度限制在一定范圍內(nèi)[ -xmax,xmax]、[ -vmax,vmax]。

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

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

3.1 環(huán)境建模

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

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

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

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

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

式中：(xs,ys),(xf,yf)—路徑的起點坐標與終點坐標。

3.3 K均值聚類

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

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

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

3.4 交叉操作

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

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

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

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

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

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

3.5 變異操作

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

為了更直觀看出加入聚類算法的優(yōu)勢，對交叉粒子群算法和聚類融合交叉粒子群算法收斂情況進行比較（參數(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)路徑的總計算時間也大大縮短，對于智能路徑尋優(yōu)有很好的效果。

雖然加入聚類的思想可以明顯達到加速收斂速度的效果，但是聚類的數(shù)目不同，產(chǎn)生的效果也不完全相同。選取5000粒子，10000代，在相同環(huán)境下對以下聚類數(shù)目進行對比實驗，對比結(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é)果。在仿真實驗中，我們可以根據(jù)柵格地圖的復(fù)雜度，選擇適中的分區(qū)數(shù)目，在加快收斂速度的同時選擇相對運算成本較小、路徑長度較優(yōu)的參數(shù)設(shè)置。

5 結(jié)論

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

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

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

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