二進(jìn)制粒子群算法融合遺傳算法路徑規(guī)劃方法

夏梓堯

（安徽理工大學(xué)電氣與信息工程學(xué)院，淮南 232001）

0 引言

路徑規(guī)劃是移動機(jī)器人領(lǐng)域的一個研究熱點，是實現(xiàn)移動機(jī)器人自主導(dǎo)航的關(guān)鍵技術(shù)。隨著計算機(jī)智能技術(shù)的發(fā)展，機(jī)器學(xué)習(xí)和群體智能優(yōu)化算法被認(rèn)為是未來比較適合在復(fù)雜環(huán)境下進(jìn)行機(jī)器人避障和路徑規(guī)劃的學(xué)習(xí)方法［1-4］。目前，國內(nèi)外的許多學(xué)者在移動機(jī)器人的路徑規(guī)劃領(lǐng)域做了大量的研究工作，并取得了很多成果。文獻(xiàn)［5］提出改進(jìn)的自適應(yīng)蟻群算法（IAACO），引入啟發(fā)式信息自適應(yīng)調(diào)節(jié)因子和自適應(yīng)信息素?fù)]發(fā)因子提高機(jī)器人路徑規(guī)劃的實時性和安全性。文獻(xiàn)［6］設(shè)計了自適應(yīng)交叉算子和變異算子，提高規(guī)劃效果。文獻(xiàn)［7］將改進(jìn)的二進(jìn)制粒子群算法應(yīng)用于路徑規(guī)劃。

提出了一種改進(jìn)的二進(jìn)制粒子群算法融合自適應(yīng)遺傳算法（PSO-GA）應(yīng)用于柵格地圖路徑規(guī)劃。該算法以粒子群算法（PSO）為主體引入遺傳算法（GA）的操作，并采用自適應(yīng)性的交叉概率，避免了早熟收斂和局部最優(yōu)的問題，提高了算法適應(yīng)性。計算結(jié)果表明，該算法不僅能夠在復(fù)雜柵格環(huán)境下迅速地得到最優(yōu)解，而且得到的路徑長度更短，收斂更快，從而提高路徑規(guī)劃的效率。

1 柵格環(huán)境建模

柵格法［8］是路徑規(guī)劃中常用的環(huán)境地圖建模方法，該方法簡單有效，適應(yīng)性強(qiáng)。本文采用柵格法建立移動機(jī)器人的工作環(huán)境時，分別用0、1表示自由區(qū)域和障礙物，每一個柵格有唯一序號與之對應(yīng)，建立20×20的柵格環(huán)境作為移動機(jī)器人的運動場所，并設(shè)定左上角序號為1的柵格作為起點，右下角序號為400的柵格作為終點。

2 二進(jìn)制粒子群算法

粒子群算法源于對鳥群捕食行為的研究，搜索最簡單有效的策略就是搜尋目前離食物最近的鳥的周圍區(qū)域。每個優(yōu)化問題的潛在解都是搜索空間中的一只鳥，即粒子［9］。所有粒子都有適應(yīng)度值及包含方向和距離的初速度，適應(yīng)度值即為路徑長度，公式（1）如下：

粒子群算法首先在給定的解空間中生成隨機(jī)初始化粒子群，每個粒子被賦予初始位置與初始速度，然后通過迭代尋優(yōu)，通過個體極值和群體極值更新位置與速度。在此基礎(chǔ)上，標(biāo)準(zhǔn)粒子群算法引入了慣性權(quán)重ω概念，速度V和位置X更新見公式（2）：

其中，c1=0.8為認(rèn)知系數(shù)；c2=0.9為社會學(xué)習(xí)系數(shù)；k為當(dāng)前迭代次數(shù)；r1、r2為［0，1］隨機(jī)數(shù)。對ω進(jìn)行動態(tài)調(diào)整，規(guī)劃初期，ω值較大，全局收斂能力較強(qiáng)；搜索后期，ω值較小，局部收斂能力較強(qiáng)，以此權(quán)衡全局和局部搜索能力。目前，采用較多的是線性遞減權(quán)值策略，其表達(dá)式（3）如下：

其中，Tmax表示最大迭代次數(shù)；ωmin=0.4，ωmax=0.9；t表示當(dāng)前迭代次數(shù)。

標(biāo)準(zhǔn)粒子群算法局限于連續(xù)區(qū)間中運用，如果將連續(xù)粒子運動空間映射到離散問題空間，并適當(dāng)修改算法，在計算上仍保留經(jīng)典粒子群算法速度位置更新運算規(guī)則，從而構(gòu)成二進(jìn)制粒子群算法［10］。算法通過運用sigmoid函數(shù)實現(xiàn)實數(shù)與二進(jìn)制數(shù)的映射，粒子在狀態(tài)空間的取值和變化只限于0和1。

二進(jìn)制粒子群算法中速度更新公式依然保持不變，但是個體極值和群體極值只在［0，1］內(nèi)取值，位置更新見公式（4），其中，r為［0，1］中隨機(jī)數(shù)。

3 二進(jìn)制粒子群算法與遺傳算法融合

遺傳算法是一種仿生學(xué)算法，模仿自然界中生物演化的自然過程，父代經(jīng)過自然選擇把優(yōu)秀的、更適應(yīng)環(huán)境的遺傳信息傳遞給子代，同時保持一定變異概率，來不斷豐富種群整體的基因庫。遺傳算法的操作包括：

（1）選擇操作：以適應(yīng)度函數(shù)值為參照，從第k代種群中選擇適應(yīng)度高的優(yōu)良個體，將其遺傳信息傳遞給下一代，即第k+1代個體。這里引入動態(tài)調(diào)整的選擇概率，以增強(qiáng)其自適應(yīng)性。概率的數(shù)學(xué)表達(dá)如式（5）所示：

其中，個體i的適應(yīng)度為fiti，fitmax為當(dāng)次迭代最大適應(yīng)度值，fitaverage為當(dāng)次迭代平均適應(yīng)度值。

（2）交叉操作：將之前從種群中選擇出來的個體進(jìn)行隨機(jī)搭配，通過信息交互提高算法整體的搜索效率，同時避免各項參數(shù)過早收斂陷入局部最優(yōu)。首先選擇一對備選個體；然后根據(jù)位串長度n，隨機(jī)選?。?，n-1］中的一個整數(shù)作為交叉位置；最后成對個體在交叉位置處交換各自的部分信息，進(jìn)而產(chǎn)生一對全新的個體。

（3）變異操作：對于種群中的全部個體，以變異概率Pm選擇突變個體，隨機(jī)改變個體信息的值。這里采用運算簡便的二進(jìn)制變異，即0、1變換。

運用二進(jìn)制粒子群算法融合改進(jìn)自適應(yīng)性的遺傳算法進(jìn)行路徑規(guī)劃，兩種算法的融合綜合了兩者的優(yōu)勢，使算法收斂性更好。融合的策略是通過在粒子群算法中引入遺傳算法的交叉操作，并用二進(jìn)制變異算子進(jìn)行算法的改進(jìn)，從而構(gòu)成混合算法。該算法主要有如下特點：

（1）運用二進(jìn)制粒子群算法結(jié)合遺傳算法，引入的選擇、交叉、變異操作，通過二進(jìn)制編碼降低計算復(fù)雜度，增強(qiáng)算法跳出局部最優(yōu)解的能力。

（2）在遺傳算法中引入自適應(yīng)選擇概率，并根據(jù)迭代次數(shù)自適應(yīng)調(diào)整慣性權(quán)重，避免了傳統(tǒng)粒子群算法容易早熟收斂陷入局部最優(yōu)解的問題，提高算法的自適應(yīng)性。

融合算法流程圖如圖1所示，運算步驟如下：

（1）初始化粒子群參數(shù)，包括群體規(guī)模N，每個粒子的適應(yīng)度值fitness，位置和速度。

（2）運用sigmoid函數(shù)進(jìn)行二進(jìn)制編碼。

（3）迭代更新粒子的適應(yīng)度值，位置和速度。

（4）對每個粒子，用它的適應(yīng)度值和個體極值Pbest比較。如 果fitness＜Pbest，則用fitness替 換掉Pbest；同理，更新全局極值Gbest。

（5）選擇適應(yīng)度較高的個體進(jìn)行復(fù)制，然后按照交叉概率選擇個體執(zhí)行交叉，按變異概率執(zhí)行變異，并形成新的種群。

（6）判斷算法終止條件是否滿足：如果是，則結(jié)束算法并輸出優(yōu)化結(jié)果；否則返回步驟（3）。

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

為了驗證不同算法應(yīng)用于路徑規(guī)劃的效果，利用Matlab軟件對路徑規(guī)劃過程進(jìn)行仿真模擬，操作系統(tǒng)為Win10。在20×20的柵格地圖區(qū)域范圍內(nèi)，分別采用粒子群算法（PSO）、遺傳算法（GA）、粒子群-遺傳融合算法（PSO-GA）進(jìn)行全局路徑規(guī)劃。

4.1 簡單環(huán)境仿真

為驗證粒子群-遺傳算法的優(yōu)勢，首先在簡單環(huán)境下利用該算法進(jìn)行路徑規(guī)劃。設(shè)定粒子種群規(guī)模為30，最大迭代次數(shù)為100次，變異概率Pm=0.1，c1=0.8，c2=0.9。計算結(jié)果如圖2所示。

圖2（a）是粒子群算法規(guī)劃結(jié)果，路徑長度30.6569，規(guī)劃結(jié)果整體較為平滑，轉(zhuǎn)角共有7處，在三種算法中最少，基本符合最優(yōu)解的預(yù)期；圖2（b）是粒子群算法結(jié)合遺傳算法規(guī)劃結(jié)果，路徑長度30.6569，同樣符合最優(yōu)解預(yù)期，但是轉(zhuǎn)角稍多，有9處；圖2（c）是遺傳算法規(guī)劃最短路徑，轉(zhuǎn)角9處，部分轉(zhuǎn)直角不夠平滑，路徑長度31.8995，在三種算法中最長，仍有繼續(xù)優(yōu)化空間。

綜合三種優(yōu)化路徑形狀以及圖2（d）三種算法進(jìn)化曲線的對比可以看出，融合算法相較于單一算法，適應(yīng)度函數(shù)值（即最短路徑長度）曲線大部分區(qū)間位于曲線圖底部，起點更低，收斂更快，最終結(jié)果較好。但此處融合算法的比較優(yōu)勢并不突出，粒子群算法規(guī)劃路徑長度與融合算法的相同，且整體更加平滑，轉(zhuǎn)角更少。

4.2 復(fù)雜環(huán)境仿真

進(jìn)一步把該融合算法應(yīng)用于復(fù)雜環(huán)境，分析該算法的適應(yīng)情況。環(huán)境的復(fù)雜性主要是由環(huán)境中障礙物的比例和密度來定義的。這里種群規(guī)模比簡單環(huán)境仿真小，設(shè)定粒子種群規(guī)模為10，最大迭代次數(shù)為500次，變異概率Pm=0.1，c1=0.8，c2=0.9。仿真結(jié)果如圖3所示。

圖3（a）為遺傳算法最優(yōu)路徑，路徑前半段迂回較多，轉(zhuǎn)角15處，且存在尖銳折角，路徑長度34.3848，在三種算法中路徑最長，仍然存在較大優(yōu)化空間；圖3（b）為粒子群算法規(guī)劃結(jié)果，路徑長度32.6274，比遺傳算法略短，多數(shù)轉(zhuǎn)角為鈍角，但路徑整體較為曲折，轉(zhuǎn)角共16處；圖3（c）為融合算法規(guī)劃結(jié)果，路徑長度30.6274，在三種算法中結(jié)果最好，基本符合最優(yōu)路徑的預(yù)期，只有接近起點處的直角轉(zhuǎn)彎仍有局部優(yōu)化空間，而且路徑更為平滑，轉(zhuǎn)角僅有11處。

從圖3（d）的適應(yīng)度值曲線比較中可以明顯看到，融合算法的曲線全程位于折線圖底端，且起點更低，收斂更快，最短路徑長度更小，由此驗證了該融合算法在復(fù)雜環(huán)境中適應(yīng)性更好，可以獲得更好的最優(yōu)解，路徑也相對較為平滑，轉(zhuǎn)角更少，有較強(qiáng)的比較優(yōu)勢。

5 結(jié)語

針對傳統(tǒng)單一算法在全局靜態(tài)環(huán)境路徑規(guī)劃方面的不足，運用融合算法避免單一算法容易早熟收斂陷入局部最優(yōu)解的問題。通過融合算法、粒子群算法和遺傳算法分別在簡單和復(fù)雜環(huán)境中的仿真實驗對比分析，驗證了融合算法在保證最優(yōu)解質(zhì)量的前提下，具有更快的收斂速度，更好緩解早熟收斂，縮短全局路徑總長。