基于IAFSA和AGA混合算法的移動機器人路徑規劃

劉寧寧 陳志軍 閆學勤

關鍵詞： 移動機器人; 路徑規劃; 改進人工魚群算法; 自適應遺傳算法; 標準人工魚群算法; 標準遺傳算法

中圖分類號： TN911.1?34; TP242 ? ? ? ? ? ? ? ? ? ?文獻標識碼： A ? ? ? ? ? ? ? ? ?文章編號： 1004?373X（2019）03?0157?06

Abstract： The artificial fish swarm algorithm is easy to fall into local optimization， and has the problem of inaccurate result for path planning of mobile robot， and the genetic algorithm has the problems of easy prematurity and slow convergence speed for path planning. Therefore， a mobile robot path planning method based on improved artificial fish swarm algorithm （IAFSA） and adaptive genetic algorithm （AGA） is proposed. The grid method is used to establish the environment model of mobile robot， and then the IAFSA is used to search the initial feasible path of mobile robot. The searched initial feasible path is taken as the initial population of AGA. The AGA is adopted to optimize the global optimal path of mobile robot. The simulation results show that the hybrid algorithm is superior to the standard artificial fish swarm algorithm in the aspects of result accuracy and stability， and is superior to the standard genetic algorithm in the aspects of local optimization avoidance and convergence speed.

Keywords： mobile robot; path planning; improved artificial fish swarm algorithm; adaptive genetic algorithm; standard artificial fish swarm algorithm; standard genetic algorithm

0 ?引 ?言

路徑規劃被認為是根據距離、時間、成本、能量等標準進行最優路徑的計算，距離和時間是最常用的準則。移動機器人能夠根據距離和時間這兩個準則自主決策出一條連接起始位置和目標位置的避撞最優或次優路徑[1]。

目前，基于遺傳算法（GA）、蟻群算法（ACO）、人工神經網絡算法（ANN）、人工魚群算法（AFSA）等智能算法的移動機器人路徑規劃是非常普遍的應用，盡管這些智能算法優化了移動機器人的路徑，但是優化效果并不理想。像遺傳算法[2]易出現早熟現象且收斂速度慢;蟻群算法[3]的信息素在求解初期比較匱乏，所以蟻群算法的前期求解速度較慢;人工神經網絡[4]結構比較復雜，參數也不容易確定，且易生成局部最優路徑;人工魚群算法[5]由于魚群聚群和追尾而導致算法易陷入局部最優，同時在算法后期由于魚群隨機覓食而不能求取高精度的最優解等。針對單一智能算法的缺陷，現在需要解決的主要問題是如何選擇智能算法來優化移動機器人的路徑。

通過將兩種改進后的算法相結合來實現移動機器人的全局路徑規劃是近些年研究的熱點。因為遺傳算法種群進化能力強，所以對全局搜索的范圍十分有利，但是這種算法易受種群質量的影響，從而影響算法的計算效率和收斂速度。人工魚群算法的搜索速度快并且尋優能力強，但由于其存在隨機移動的特性，使得該算法較難獲取高精度的全局最優路徑。通過對上述遺傳算法和人工魚群算法的優點及其存在的缺陷進行分析，提出一種改進人工魚群算法和自適應遺傳算法相結合的混合算法優化移動機器人的路徑。該算法用改進人工魚群算法生成初始種群，解決遺傳算法容易受初始種群影響的缺點，用自適應遺傳算法彌補人工魚群算法后期搜索精度差及其后期尋優速度慢的缺陷，從而獲得了高精度、高質量、收斂速度快的尋優能力。

式中：[Fmax]表示群體最大適應度;[Fav]表示每代群體的平均適應度值;[F]表示要變異個體的適應度值;[k3]，[k4]表示[0，1]區間內的任意常數。

4） 刪除算子

在生成個體路徑時，由于初始路徑的產生和變異操作的連接過程可能會產生相同的柵格序號，從而影響尋優速度，所以用刪除算子刪除掉兩相同柵格中的一個柵格和兩相同柵格之間的冗余柵格，將得到的路徑作為下一代種群的個體。

2.2.4 ?移動機器人路徑優化流程

首先用改進人工魚群算法產生移動機器人的初始路徑，然后用自適應遺傳算法中選擇、交叉和變異等操作對生成的初始路徑尋優，路徑優化步驟如下：

Step1：自適應遺傳算法初始化，設種群最大進化代數為MAX，設進化代數初始值[t=1]。

Step2：對移動機器人工作環境進行柵格建模，利用改進人工魚群算法得到機器人的初始路徑，將初始路徑作為自適應遺傳算法的初始種群。

Step3：采用適應度函數計算種群中的每個個體適應度值。

Step4：用輪盤賭的方法執行選擇操作，從而復制出下一代個體。

Step5：任意選擇兩個個體，判斷這兩個個體是否滿足交叉概率，若滿足，則分別在兩個個體中隨機產生一個交叉位，進而執行交叉操作。

Step6：根據變異概率執行變異操作。

Step7：路徑中若有重合路徑點，則執行刪除操作，直到滿足無重合路徑點的條件。

Step8：如果[t≥MAX]，轉Step9;否則，令[t=t+1]，轉Step3。

Step9：循環結束，輸出最優個體。

3 ?仿真研究

3.1 ?實驗1

在10[×]10的柵格環境下對本文混合算法和單一的標準人工魚群算法進行仿真比較，仿真過程中的相關參數設置為：人工魚總數[N=10]，視野域Visual=4，擁擠度因子[delta=0.7]，最大選擇次數try_number=3，最大迭代次數[M=10]，跳轉因子[η]=5，常系數[c=2]，[k1=0.8]，[k2=0.9]，[k3=0.1]，[k4=0.2]，種群最大進化代數MAX=10。在此環境下，仿真結果如圖3所示。

通過對圖3a），圖3b）的對比可以發現，本文算法比標準人工魚群算法能獲得更短的路徑。

為了更好地說明本文混合算法在優化精度和穩定性上要優于標準人工魚群算法，分別對標準人工魚群算法和本文混合算法進行10次仿真比較，仿真結果如表1所示。

從表1中可以看出，本文混合算法在結果精度和穩定性方面優于標準人工魚群算法。在最優結果精度上，本文混合算法較標準人工魚群算法提高4.2%;在穩定性方面，本文混合算法相比標準人工魚群算法提高了79.7%。

3.2 ?實驗2

在15[×]15的柵格環境下，對本文混合算法和標準遺傳算法應用到移動機器人路徑規劃方面進行了仿真比較，仿真過程中的相關參數設置為：人工魚的總數[N=]10，視野域Visual=4，擁擠度因子delta=0.7，最大選擇次數try_number=3，最大迭代次數[M=50]，跳轉因子[η]=5，常系數[c=2]，[k1=0.8]，[k2=0.9]，[k3=0.1]，[k4=0.2]，種群最大進化代數MAX=50;遺傳算法初始種群大小設置為50，最大迭代次數設置為50，標準遺傳算法的交叉概率設置為固定概率[pc]=0.6，變異概率設置為固定概率[pm]=0.01。在此環境下，本文混合算法和標準遺傳算法尋找最優路徑結果和收斂曲線分別如圖4，圖5所示。

從圖4和圖5能夠看出，本文混合算法在尋優能力上要優于標準遺傳算法。

為了更好地說明本文混合算法的優越性，分別對本文混合算法和標準遺傳算法進行多次仿真，仿真結果如表2所示。

通過表2可以看出，本文混合算法與標準遺傳算法相比，規劃長度、規劃時間和所需迭代次數都有明顯改善。實驗數據有力說明了本文混合算法具有路徑規劃能力強、搜索效率高以及收斂速度快等優點，驗證了本文混合算法的優越性。

4 ?結 ?論

本文所設計的IAFSA?AGA混合算法優化了移動機器人的路徑，為今后探索路徑規劃算法提供了一種思維模式及其較大的參考與學術價值。