基于混合遺傳算法的機器人路徑規劃研究

焦合軍，周萬春，李淵博

(鄭州工程技術學院 機電與車輛工程學院，河南 鄭州 450044)

1 引言

移動機器人的路徑規劃是機器人導航技術中一個重要的組成部分。移動機器人可以在預先設定的條件下，按照一定的規則，從起點到終點并避開障礙物尋找一條最優路徑，該路徑長度小，消耗時間少。路徑規劃有全局和局部之分，全局路徑規劃著眼于已知路徑信息，局部路徑規劃著眼于未知的環境信息[1]。

目前在移動機器人全局路徑規劃中，常用的進化算法有遺傳算法、人工魚群算法[2]、粒子群算法和蟻群算法等。然而，傳統的遺傳算法求解過程耗時長，生成的路徑沒能達到最優避障；蟻群算法收斂的速度比較慢，容易出現停滯，陷入局部最優；人工魚群算法在優化初期有很好的收斂性，后期收斂較慢，并且隨著人工魚的增多，造成存儲需求大、計算量大的缺點；粒子群算法有較快逼近最優解的能力，可以對系統參數進行有效的優化，優勢在于對連續函數的優化，其缺點是容易早熟收斂，局部尋優能力變差。

本文針對一般的遺傳算法進行改進，在遺傳操作時加入A*算法，調整交叉和變異的概率，不僅使前期進化能力增強，改進交叉和變異方法，催生新的染色個體能力加強，又提高了算法的搜索效率。

2 路徑規劃

2.1 環境模型建立

在對機器人路徑建模時，首先要對其環境地圖進行平面化處理，使用柵格地圖是簡單有效的方法。在柵格圖中，黑格表示障礙物，白格代表機器人可以經過的自由空間。使用序號標記法進行柵格標記，按照從左到右，從上到下的原則依次加1進行標記。在圖1所示的模型中，S,2,3,…,99 ，E等稱為柵格節點，S 為機器人起始點位置，E為目標點位置。給定柵格序號T(i,j)與直角坐標點P(i,j)[X(i,j),Y(i,j)]的關系如下：

(1)

2.2 編碼方式

遺傳算法中的染色體是一組個體編碼，針對機器人路徑規劃問題，我們定義為從起始點到終點的一條路徑。為了保證路徑的可靠性和實用性，路徑中不可出現重復序號和障礙物序號[3]。如圖2所示，一條有效路徑可以表示為：S→12→23→33→44→54→65→75→85→86→87→88→98→99→E。

2.3 種群初始化

使用柵格法進行路徑規劃時，機器人在周圍無障礙的情況下可以向左、左上、左下、右、右上、右下、上、下8個方向移動。文中將A*算法用于遺傳算法的初始化，隨機分配一個無障礙點，在已有起始點和終點利用A*算法建立鏈接，具體的實現步驟如下：

第一步 將起點坐標和終點坐標(如圖 1中的S和E)加入染色體編碼中；

圖1 機器人路徑規劃地圖模型

第二步 在地圖模型中加入1 個無障礙隨機點作為目標點，利用A*算法分別建立起始點到該點以及該點到終點的路徑，在路徑建立過程中避免障礙點和外圍區域，之后將起始點和終點鏈接起來；

第三步 種群要保持染色體的差異性，對路徑節點一模一樣的進行刪除，最終生成一個集合。此刻結束初始化。

圖2 地圖序號標記

2.4 適應度函數

采用機器人從起始點到終點的路程作為路徑規劃的適應度評價，所以在路程的規劃指標下，分別得適應度函數為[4-5]：

(2)

2.5 遺傳操作

2.5.1 選擇算子

為了選出適應度較好的一部分個體，結合貪心算法，在初始種群中，算出適應度的平均值，每個染色體個體的適應度值與該平均值比較，如果大于平均值，保留該染色體個體，否則，丟棄該個體。每次迭代，重復此操作。這種選擇方法，保證了每次迭代使種群向優秀方向過渡。通過與平均值的比較，不僅保證了個體的多樣性，而且保證了種群的穩態繁殖。

2.5.2 交叉算子

在種群中找出一對有共同點的染色體，共同點不是起始點和終點，隨機選擇其中一個共同點，交換這兩個染色體的前半部分路徑點，染色體交叉示意如圖3所示，圖中a,c兩個圖的染色體在序號點處交叉，生成b,d圖中兩個染色體。

2.5.3 變異操作

變異操作對遺傳算法最優解的產生有積極的作用，變異操作可以防止遺傳算法陷入早熟和局部最優的環境。在一條全路徑上選取除了起始點和終點的兩個隨機節點，根據A*算法生成一條兩個節點間的路徑，代替兩個節點的原路徑。為了避免優秀路徑不被破壞，變異操作后期要考慮減少或停止變異操作。例如：個體變異前為 V ={S，11，…，96，87，98，99，E} ，變異節點為96和98，產生的新路徑為：C ={S，11，…，96，97，98，99，E}。

2.7 混合遺傳算法流程

首先利用A*算法產生原始種群，并得出各個個體的適應度值，之后選擇并以一定概率進行交叉和變異操作找出最優解的個體，最后判斷是否符合結束條件，在進行個體適應度數值和最優解之間進行比較，滿足結束條件，退出遺傳操作，否則繼續交叉和變異，生成新一代種群[6]。該算法的步驟如圖4所示。

3 仿真分析

為了證明算法的合理性，本文在Visual C++環境中分別編寫了路徑規劃的一般遺傳算法和混合遺傳算法，對比兩種算法的特點。由于具體尺寸上沒有指定，本文用數字表示相關參數。柵格的尺寸為10×10，起點為(0,0)，終點為(9,9)，在 2個地圖環境下得到的路徑長度和收斂速度如圖5、6所示。

圖3 交叉操作示意圖

圖4 混合遺傳算法的步驟

對于一般遺傳算法，遺傳種群數目為50，變異和交叉的概率為0.06和0.9，最大迭代數為50；對于本文提出的算法，種群數目為50，5次迭代前交叉率是0.9，5代后交叉率為0.3，5代前變異率為0.06，5代后變異率為0.01，最大遺傳代數為50。

兩種算法結果不同，一般遺傳算法最佳路徑長16.5228，混合遺傳算法的最優路徑長度為14.8173，一般遺傳算法的路徑長于混合遺傳算法，并且從適應度變化折現中看出，一般遺傳很快進入局部最優，一般遺傳算法的收斂速度沒有混合遺傳算法快。

4 結論

本文針對機器人的路徑規劃，討論了一種新的混合遺傳算法。通過實驗對比，混合了A*算法的遺傳算法在機器人路徑規劃方面是有效的。該算法有以下特點：

(1)引入隨機節點，通過A*算法保證了種群中染色體的多樣性，保證了路徑的局部最優。

(2)算法中的交叉和變異方法，催生新的染色個體能力強，方便個性差距大的個體出現。

(3)算法可以調整交叉和變異概率，算法的前期進化能力較強，算法的求解效率有所提高。

圖5 一般遺傳算法仿真結果

圖6 混合遺傳算法仿真結果