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

梁亞楠 尹亞明

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

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

梁亞楠 尹亞明

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

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

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

一、引言

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

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

(一)工作空間描述

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

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

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

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

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

如，初始生成的路線為A:0,11,21,31,41,42,52,63,73,74,84,85,96,87,97,98,99。由于63號(hào)柵欄存在障礙物，則這條路線成為無(wú)效路徑，機(jī)器人經(jīng)過(guò)63號(hào)柵欄點(diǎn)之前通過(guò)的第一個(gè)空白柵欄編號(hào)為52，在52號(hào)柵欄處對(duì)路徑進(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)過(guò)72號(hào)柵欄為障礙物柵欄，所以舍去這條路徑，路線C和路線D均為有效路徑，經(jīng)過(guò)比較計(jì)算可知，路徑C的長(zhǎng)度比路徑D短，舍去路徑D，用路徑C替換路徑A。

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

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

四、遺傳算子

(一)選擇算子

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

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

(二)交叉算子

交叉運(yùn)算是產(chǎn)生新個(gè)體的重要方式，機(jī)器人路徑編碼不能任意交叉，否則會(huì)產(chǎn)生不連續(xù)路徑。我們采用單點(diǎn)交叉的方式，對(duì)選中的兩個(gè)個(gè)體，若存在相同的柵欄節(jié)點(diǎn)，則隨機(jī)選取其中一個(gè)節(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號(hào)節(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ī)選取個(gè)體中某個(gè)節(jié)點(diǎn)為變異點(diǎn)；

2.考察變異點(diǎn)的上、右上、右、右下、下五個(gè)方向，若這五個(gè)方向?yàn)榭瞻讝艡?，不存在障礙物，則分別進(jìn)行五個(gè)方向的變異；

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

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

五、結(jié)論

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

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

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

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

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