焦合軍，周萬春，李淵博

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

1 引言

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

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

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

2 路徑規(guī)劃

2.1 環(huán)境模型建立

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

(1)

2.2 編碼方式

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

2.3 種群初始化

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

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

圖1 機器人路徑規(guī)劃地圖模型

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

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

圖2 地圖序號標記

2.4 適應度函數(shù)

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

(2)

2.5 遺傳操作

2.5.1 選擇算子

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

2.5.2 交叉算子

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

2.5.3 變異操作

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

2.7 混合遺傳算法流程

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

3 仿真分析

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

圖3 交叉操作示意圖

圖4 混合遺傳算法的步驟

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

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

4 結(jié)論

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

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

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

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

圖5 一般遺傳算法仿真結(jié)果

圖6 混合遺傳算法仿真結(jié)果