基于混合遺傳算法的機(jī)器人路徑規(guī)劃研究

焦合軍，周萬(wàn)春，李淵博

(鄭州工程技術(shù)學(xué)院 機(jī)電與車輛工程學(xué)院，河南 鄭州 450044)

1 引言

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

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

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

2 路徑規(guī)劃

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

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

(1)

2.2 編碼方式

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

2.3 種群初始化

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

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

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

第二步 在地圖模型中加入1 個(gè)無(wú)障礙隨機(jī)點(diǎn)作為目標(biāo)點(diǎn)，利用A*算法分別建立起始點(diǎn)到該點(diǎn)以及該點(diǎn)到終點(diǎn)的路徑，在路徑建立過(guò)程中避免障礙點(diǎn)和外圍區(qū)域，之后將起始點(diǎn)和終點(diǎn)鏈接起來(lái)；

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

圖2 地圖序號(hào)標(biāo)記

2.4 適應(yīng)度函數(shù)

采用機(jī)器人從起始點(diǎn)到終點(diǎn)的路程作為路徑規(guī)劃的適應(yīng)度評(píng)價(jià)，所以在路程的規(guī)劃指標(biāo)下，分別得適應(yīng)度函數(shù)為[4-5]：

(2)

2.5 遺傳操作

2.5.1 選擇算子

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

2.5.2 交叉算子

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

2.5.3 變異操作

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

2.7 混合遺傳算法流程

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

3 仿真分析

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

圖3 交叉操作示意圖

圖4 混合遺傳算法的步驟

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

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

4 結(jié)論

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

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

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

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

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

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