二進制粒子群算法融合遺傳算法路徑規劃方法

夏梓堯

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

0 引言

路徑規劃是移動機器人領域的一個研究熱點，是實現移動機器人自主導航的關鍵技術。隨著計算機智能技術的發展，機器學習和群體智能優化算法被認為是未來比較適合在復雜環境下進行機器人避障和路徑規劃的學習方法［1-4］。目前，國內外的許多學者在移動機器人的路徑規劃領域做了大量的研究工作，并取得了很多成果。文獻［5］提出改進的自適應蟻群算法（IAACO），引入啟發式信息自適應調節因子和自適應信息素揮發因子提高機器人路徑規劃的實時性和安全性。文獻［6］設計了自適應交叉算子和變異算子，提高規劃效果。文獻［7］將改進的二進制粒子群算法應用于路徑規劃。

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

1 柵格環境建模

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

2 二進制粒子群算法

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

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

其中，c1=0.8為認知系數；c2=0.9為社會學習系數；k為當前迭代次數；r1、r2為［0，1］隨機數。對ω進行動態調整，規劃初期，ω值較大，全局收斂能力較強；搜索后期，ω值較小，局部收斂能力較強，以此權衡全局和局部搜索能力。目前，采用較多的是線性遞減權值策略，其表達式（3）如下：

其中，Tmax表示最大迭代次數；ωmin=0.4，ωmax=0.9；t表示當前迭代次數。

標準粒子群算法局限于連續區間中運用，如果將連續粒子運動空間映射到離散問題空間，并適當修改算法，在計算上仍保留經典粒子群算法速度位置更新運算規則，從而構成二進制粒子群算法［10］。算法通過運用sigmoid函數實現實數與二進制數的映射，粒子在狀態空間的取值和變化只限于0和1。

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

3 二進制粒子群算法與遺傳算法融合

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

（1）選擇操作：以適應度函數值為參照，從第k代種群中選擇適應度高的優良個體，將其遺傳信息傳遞給下一代，即第k+1代個體。這里引入動態調整的選擇概率，以增強其自適應性。概率的數學表達如式（5）所示：

其中，個體i的適應度為fiti，fitmax為當次迭代最大適應度值，fitaverage為當次迭代平均適應度值。

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

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

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

（1）運用二進制粒子群算法結合遺傳算法，引入的選擇、交叉、變異操作，通過二進制編碼降低計算復雜度，增強算法跳出局部最優解的能力。

（2）在遺傳算法中引入自適應選擇概率，并根據迭代次數自適應調整慣性權重，避免了傳統粒子群算法容易早熟收斂陷入局部最優解的問題，提高算法的自適應性。

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

（1）初始化粒子群參數，包括群體規模N，每個粒子的適應度值fitness，位置和速度。

（2）運用sigmoid函數進行二進制編碼。

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

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

（5）選擇適應度較高的個體進行復制，然后按照交叉概率選擇個體執行交叉，按變異概率執行變異，并形成新的種群。

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

4 仿真結果與分析

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

4.1 簡單環境仿真

為驗證粒子群-遺傳算法的優勢，首先在簡單環境下利用該算法進行路徑規劃。設定粒子種群規模為30，最大迭代次數為100次，變異概率Pm=0.1，c1=0.8，c2=0.9。計算結果如圖2所示。

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

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

4.2 復雜環境仿真

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

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

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

5 結語

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