一種改進(jìn)的遺傳算法求解機(jī)器人最優(yōu)路徑

梁亞楠 尹亞明

(成都理工大學(xué) 四川 成都 610059)

一種改進(jìn)的遺傳算法求解機(jī)器人最優(yōu)路徑

梁亞楠 尹亞明

(成都理工大學(xué) 四川 成都 610059)

遺傳算法具有全局搜索性強(qiáng)、魯棒性高、且具有較好的收斂性的有點(diǎn)。隨著人們逐漸對其深入的認(rèn)識，人們發(fā)現(xiàn)這種算法容易陷入早熟的狀態(tài)。對此，本文改進(jìn)了初始化種群的過程，并對選擇，交叉，變異三種算子進(jìn)行優(yōu)化。

遺傳算法；自適應(yīng)遺傳算法；機(jī)器人路徑優(yōu)化

一、引言

近幾年關(guān)于機(jī)器人路徑規(guī)劃的研究是一個熱點(diǎn)。高申勇等[1]基于虛擬彈簧模型，建立彈簧力學(xué)模型，尋找機(jī)器人移動的最優(yōu)路勁；李晉[2]將遺傳算法與蟻群算法相結(jié)合，提出了解決機(jī)器人路勁規(guī)劃的方法；王冬云等[3]采用改進(jìn)的具有群集智能的蜂群算法，結(jié)合三次貝塞爾曲線來描述路徑，以達(dá)到路徑最優(yōu)的目的。

二、機(jī)器人環(huán)境描述及編碼

(一)工作空間描述

本文采用柵欄法表示機(jī)器人的運(yùn)動空間[4]，如圖1所示。基于以下幾點(diǎn)：1.機(jī)器在一個二維平面內(nèi)活動。2.對每個空格進(jìn)行編號，每個空格的編號可由以下式子計算；H=10y+x。3.圖中陰影部分表示障礙物，空白表示自由柵欄，工作空間內(nèi)障礙物的數(shù)量和位置都是已知的。

圖1 機(jī)器人工作空間

(二)初始種群的產(chǎn)生及路徑的編碼

采用機(jī)器人移動經(jīng)過柵欄的編號的有序組合來進(jìn)行編碼，如圖1所示，0為機(jī)器人初始位置，99代表機(jī)器人移動的終點(diǎn)。所經(jīng)過的方格的編號的組合，就代表一個個體的編碼。如:0,11,21,30,41,42,43,54,64,74,85,86,87,97,98,99。由于初始群體產(chǎn)生具有隨機(jī)性，這就會同時產(chǎn)生有效路徑和無效路徑。有效路徑是指機(jī)器人所走過的路線不經(jīng)過障礙點(diǎn)，無效路徑是指機(jī)器人所走過的路線會經(jīng)過障礙點(diǎn)。

本文采用隨機(jī)生成的方法隨機(jī)來生成初始種群。對于無效路徑，采用變異調(diào)整的方法進(jìn)行處理：對任意一條無效路徑，找出這條路徑所經(jīng)過的所有的障礙物點(diǎn)，在障礙物點(diǎn)之前的第一個非障礙物點(diǎn)采用調(diào)整策略，即按照其他非障礙方向進(jìn)行調(diào)整，產(chǎn)生多條新的路徑，若產(chǎn)生的是無效路徑，則舍去該路徑。比較剩余的有效路徑的適應(yīng)度大小，將適應(yīng)度大的保留，其余的舍去，用這條新路徑替換原來調(diào)整之前的無效路徑。

如，初始生成的路線為A:0,11,21,31,41,42,52,63,73,74,84,85,96,87,97,98,99。由于63號柵欄存在障礙物，則這條路線成為無效路徑，機(jī)器人經(jīng)過63號柵欄點(diǎn)之前通過的第一個空白柵欄編號為52，在52號柵欄處對路徑進(jìn)行調(diào)整，按照上面提出的方法，共生成三條新的路勁，分別是：

路線B：1:0,11,21,31,41,42,52,62,72,82,83,84,85,96,87,97,98,99

路線C，1:0,11,21,31,41,42,52,53,54,64,65,75,85,96,87,97,98,99

路線D：1:0,11,21,31,41,42,52,43,44,54,64,65,75,85,96,87,97,98,99

由于路線B經(jīng)過72號柵欄為障礙物柵欄，所以舍去這條路徑，路線C和路線D均為有效路徑，經(jīng)過比較計算可知，路徑C的長度比路徑D短，舍去路徑D，用路徑C替換路徑A。

三、適應(yīng)度函數(shù)的確定

適應(yīng)度函數(shù)是用來評價個體滿足環(huán)境的適應(yīng)能力的大小，適應(yīng)度的大小決定著個體繼續(xù)生存的概率，適應(yīng)度函數(shù)越大，個體生存能力越優(yōu)，越能適應(yīng)惡劣的環(huán)境。我們采用機(jī)器人路徑長短的倒數(shù)作為適應(yīng)度函數(shù)：

四、遺傳算子

(一)選擇算子

傳統(tǒng)的遺傳算法采用了輪盤賭的方法進(jìn)行樣本的選擇，本文結(jié)合了精英策略和聯(lián)賽制。先對初始樣本進(jìn)行相應(yīng)的處理。算法陷入早熟和局部最優(yōu)的原因是因為存在某些個體的適應(yīng)度遠(yuǎn)遠(yuǎn)大于其他個體的適應(yīng)度，我們用標(biāo)準(zhǔn)差δ來評判種群離散程度。

我們利用三倍標(biāo)準(zhǔn)差法篩選初始種群。然后采用精英策略，按照一定的比例保留初始種群中適應(yīng)度大的，讓他們直接參與下一代遺傳，剩下的個體，采用聯(lián)賽制度，設(shè)置參數(shù)I=2，即從剩下的個體中每次隨機(jī)挑選出兩個個體，比較這兩個個體的適應(yīng)度大小，讓適應(yīng)度大的參與下一代遺傳運(yùn)算，適應(yīng)度小的個體放回原種群。

(二)交叉算子

交叉運(yùn)算是產(chǎn)生新個體的重要方式，機(jī)器人路徑編碼不能任意交叉，否則會產(chǎn)生不連續(xù)路徑。我們采用單點(diǎn)交叉的方式，對選中的兩個個體，若存在相同的柵欄節(jié)點(diǎn)，則隨機(jī)選取其中一個節(jié)點(diǎn)，在該節(jié)點(diǎn)處進(jìn)行交叉操作，否則，不進(jìn)行交叉。例如：

路線A：0,10,20,30,40,41,51,52,43,54,64,65,75,76,86,87,97,98,99

路線B：0,11,21,31,41,42,43,34,35,36,46,47,48,49,58,68,78,79,89,99

路線A和路線B存在共同節(jié)點(diǎn)41和43，我們隨機(jī)選取43號節(jié)點(diǎn)，則交叉都得到兩條新路線：

A’:0,10,20,30,40,41,51,52,43,34,35,36,46,47,48,49,58,68,78,79,89,99

B’:0,11,21,31,41,42,43,54,64,65,75,76,86,87,97,98,99

(三)變異算子

本文采用下面這種變異方式：

1.隨機(jī)選取個體中某個節(jié)點(diǎn)為變異點(diǎn)；

2.考察變異點(diǎn)的上、右上、右、右下、下五個方向，若這五個方向為空白柵欄，不存在障礙物，則分別進(jìn)行五個方向的變異；

3.若某條路徑通過障礙物節(jié)點(diǎn)，則刪除這條路徑；

4.比較剩下的路徑的適應(yīng)度大小，用適應(yīng)度大的路徑替換原來變異前的路勁，其余的路徑舍去。

五、結(jié)論

這種改進(jìn)過后的遺傳算法，相比于傳統(tǒng)的遺傳算法，在算法的機(jī)制上有了很大的改進(jìn)，通過這種改進(jìn)有效的避免了算法陷入局部最優(yōu)和早熟的現(xiàn)象，同時，大大提高了算法的運(yùn)行速度。通過實驗仿真表明，采用本文所述的改進(jìn)方法，相比于傳統(tǒng)遺傳算法，運(yùn)行速度提高了31%，在遺傳的代數(shù)上，找到最優(yōu)解的代數(shù)從121代減少到84代，明顯加快的算法的收斂速度。

[1]高申勇,許方鎮(zhèn),郭鴻杰.基于彈簧模型的移動機(jī)器人路徑規(guī)劃研究[J].儀器儀表學(xué)報,2016,37(4):796-803.

[2]李晉.基于蟻群算法和遺傳算法的機(jī)器人路徑規(guī)劃研究[D].哈爾濱工業(yè)大學(xué),2012.

[3]王東云,徐艷平,瞿博陽,等.基于改進(jìn)蜂群算法的機(jī)器人路徑規(guī)劃[J].計算機(jī)系統(tǒng)應(yīng)用,2017,26(2):145-150.

[4]石欣,印愛民,陳曦.基于RSSI的多維標(biāo)度室內(nèi)定位算法[J].儀器儀表學(xué)報,2014,35(2):261-268.