宋宇 王志明

摘要：將遺傳算法用于路徑規(guī)劃時(shí)，傳統(tǒng)算法雖然簡(jiǎn)單，但不適用轉(zhuǎn)彎情況較多的復(fù)雜地圖。針對(duì)這一問(wèn)題，首先將RRT算法用于柵格環(huán)境下產(chǎn)生初始路徑，其次提出一種新的插入算子，最后進(jìn)行路徑優(yōu)化。根據(jù)不同地圖與其他文獻(xiàn)中的改進(jìn)遺傳算法，進(jìn)行對(duì)比研究與分析，制定路徑長(zhǎng)度與算法用時(shí)2個(gè)指標(biāo)來(lái)評(píng)判算法的優(yōu)劣。仿真結(jié)果表明，改進(jìn)算法得到的路徑長(zhǎng)度縮短了70%，路徑長(zhǎng)度達(dá)到最優(yōu)的用時(shí)減少了8%。

關(guān)鍵詞：移動(dòng)機(jī)器人;遺傳算法;路徑規(guī)劃;算法評(píng)判;插入算子;路徑優(yōu)化

中圖分類號(hào)：TN820.4-34;TP301.6

文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：1004-373X（2019）24-0172-04

遺傳算法是一種模擬自然界選擇進(jìn)化的全局優(yōu)化算法，利用遺傳算法求解最優(yōu)問(wèn)題是通過(guò)選擇交叉變異算子不斷迭代來(lái)實(shí)現(xiàn)的。采用遺傳算法路徑規(guī)劃的文獻(xiàn)并不少見[1-5]。文獻(xiàn)[1]提出了人工勢(shì)場(chǎng)法與遺傳算法相結(jié)合的方法，使得算法得到的路徑平滑度較高;文獻(xiàn)[2]采用了Dijstar算法初始化種群，用遺傳算法得到了安全度較高的路徑;文獻(xiàn)[5]提出了根據(jù)種群的適應(yīng)度方差自適應(yīng)選擇的選擇策略;文獻(xiàn)[6]在遺傳算法得到的路徑上重新排列基因優(yōu)化了路徑長(zhǎng)度與路徑平滑度;文獻(xiàn)[7]采用了在當(dāng)前點(diǎn)附近產(chǎn)生個(gè)體的方法，以距離為適應(yīng)度函數(shù)，用遺傳算法進(jìn)行了路徑規(guī)劃。

1 基于改進(jìn)遺傳算法的路徑規(guī)劃

在傳統(tǒng)遺傳算法柵格路徑規(guī)劃的基礎(chǔ)上提出了新的初始化方式、變異方式以及插入方式，改善了全局尋優(yōu)效果。

1.1 柵格模型

首先將給定地圖柵格化，將障礙物所占的柵格用黑色柵格表示，自由空間用白色柵格表示，圖1中黑色曲線表示一條典型的柵格環(huán)境路徑，該路徑是由從起點(diǎn)到終點(diǎn)的一系列路徑點(diǎn)組成的路徑規(guī)劃算法的任務(wù)，即尋找從起點(diǎn)到終點(diǎn)的一系列連續(xù)路徑點(diǎn)，使得連接路徑點(diǎn)的路徑長(zhǎng)度或安全度最優(yōu)。路徑點(diǎn)的位置可以用直角坐標(biāo)或柵格序號(hào)表示，給定柵格中心點(diǎn)的柵格序號(hào)P（i，j）與直角坐標(biāo)[X（i，j ），Y（i，j）]的轉(zhuǎn)換關(guān)系如下：

X（i，j）= mod （P（i，j），10）- 0.5

Y（i，j）= floor （P（i，J），10）+ 0.5

（1）

P（i，j）=X（i，j）+0.5+10（1，（i，j）一0.5）

圖1中的路徑點(diǎn)組成的路徑點(diǎn)集合為{1，12，23，24，25，26，36，46，56，67，68，69，80，90，1001，移動(dòng)機(jī)器人的起點(diǎn)序號(hào)為1，終點(diǎn)序號(hào)為100。遺傳算法中的個(gè)體用路徑序號(hào)組成的向量表示，1個(gè)個(gè)體代表一條無(wú)碰撞路徑。

1.2 遺傳算法初始化

傳統(tǒng)遺傳算法用于柵格路徑規(guī)劃時(shí)，在初始化中采用較多的是中點(diǎn)插值法，即隨機(jī)產(chǎn)生一定數(shù)量的路徑點(diǎn)，在每?jī)蓚€(gè)路徑點(diǎn)之間采用中點(diǎn)插值的方式進(jìn)行路徑插補(bǔ)。文中將RRT算法用于遺傳算法種群的初始化，給定起點(diǎn)與終點(diǎn)，從起點(diǎn)開始產(chǎn)生隨機(jī)樹并不斷生長(zhǎng)，直到此隨機(jī)樹到達(dá)終點(diǎn)。

文中算法產(chǎn)生一條路徑的具體步驟如下：

1）將起點(diǎn)坐標(biāo)（如圖1中的[1，1]）加入隨機(jī)樹中;

2）在地圖范圍內(nèi)以50%的概率產(chǎn)生1個(gè)隨機(jī)點(diǎn)作為目標(biāo)點(diǎn)，其余50%的概率以終點(diǎn)為目標(biāo)點(diǎn)，計(jì)算得到距離此目標(biāo)點(diǎn)最近的樹節(jié)點(diǎn)P（x，y）;

3）在P（x，y）所在柵格的鄰居?xùn)鸥裰羞x出所有非障礙物柵格，若P（x，y）的所有鄰居?xùn)鸥穸荚谡系K物中，則跳到步驟2）;

4）在步驟3）產(chǎn)生的滿足條件的鄰居?xùn)鸥裰?，選擇距離步驟2）產(chǎn)生的隨機(jī)點(diǎn)最近的柵格中心點(diǎn)，若此點(diǎn)已經(jīng)在樹中，跳到步驟2），若此點(diǎn)不在樹中，將此點(diǎn)作為樹節(jié)點(diǎn)，即將此距離最近的點(diǎn)加入樹中。

5）檢查步驟4）新加入樹中的點(diǎn)的所有鄰居?xùn)鸥瘢艚K點(diǎn)在這些鄰居?xùn)鸥駜?nèi)，算法結(jié)束。若終點(diǎn)不在柵格內(nèi)，跳到步驟2）。

按照上述算法產(chǎn)生種群數(shù)量的路徑，初始化結(jié)束。

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

文中適應(yīng)度函數(shù)選擇為路徑長(zhǎng)度。

1.4 選擇算子

文中采用文獻(xiàn)[5]提出的自適應(yīng)選擇算法，個(gè)體被選擇的概率為：

P=α （1- a）i-l（2）式中：i為按個(gè)體距離長(zhǎng)度排序后的個(gè)體序號(hào)值;α為：

產(chǎn)生個(gè)體概率后，使用隨機(jī)遍及取樣（SUS）算法選擇個(gè)體。

1.5 交叉算子

文中采用單點(diǎn)交叉算法，即在種群內(nèi)隨機(jī)選擇2個(gè)待交叉?zhèn)€體，找到這兩個(gè)個(gè)體的除起點(diǎn)與終點(diǎn)外的公共點(diǎn)，隨機(jī)選擇公共點(diǎn)中的一個(gè)點(diǎn)，交換這兩個(gè)個(gè)體選擇到的點(diǎn)的后半部分路徑點(diǎn)產(chǎn)生兩個(gè)新的個(gè)體。個(gè)體交叉示意圖如圖2所示，圖中前兩個(gè)地圖中的個(gè)體在序號(hào)為56的點(diǎn)處交叉，產(chǎn)生后兩個(gè)個(gè)體。

1.6 變異算子

文中提出的變異算子步驟如下：

1）在種群中隨機(jī)選擇一個(gè)個(gè)體，在此個(gè)體中隨機(jī)選擇除起點(diǎn)與終點(diǎn)外的一個(gè)路徑點(diǎn)[X，Y]，此路徑點(diǎn)將個(gè)體分為前半段路徑與后半段路徑;

2）以50%的概率選擇坐標(biāo)X進(jìn)行變異，其余50%的概率選擇坐標(biāo)Y進(jìn)行變異，即在點(diǎn)[x，y]的同行或同列中選擇一個(gè)非障礙物柵格作為變異后的點(diǎn);

3）在前半段路徑中隨機(jī)選擇一個(gè)路徑點(diǎn)[X1，Y1]，在后半段路徑中隨機(jī)選擇一個(gè)路徑點(diǎn)[X2，Y2]，使用插入算子連接[X1，Y1]與[X，Y]，[X，Y]與[X2，Y2】，若兩段路徑都連接成功，將原個(gè)體中的起點(diǎn)到點(diǎn)[X1，Y1]的路徑與[X1，Y1]與[x，y]的路徑和[X，Y]與[X2，Y2]與原個(gè)體中的點(diǎn)[X2，Y2]到終點(diǎn)的路徑拼接產(chǎn)生變異后的新個(gè)體，若兩段路徑有1段連接失敗，則令新個(gè)體與原個(gè)體相同。

1.7 插入算予

對(duì)于給定的兩個(gè)點(diǎn)，稱為start點(diǎn)與goal點(diǎn)，令start點(diǎn)為當(dāng)前點(diǎn)，創(chuàng)建一個(gè)鄰居列表（此時(shí)為空數(shù)組），創(chuàng)建一個(gè)與地圖同型的考察標(biāo)志矩陣（此時(shí)只有start點(diǎn)處的值為1，其余為0），創(chuàng)建一個(gè)路徑點(diǎn)列表（此時(shí)為空）。

1）檢查當(dāng)前點(diǎn)的8個(gè)鄰居?xùn)鸥?，將不在障礙物中且未考察過(guò)的點(diǎn)加入鄰居列表，同時(shí)令這些點(diǎn)的考察標(biāo)志為1。

2）如果鄰居列表為空，則插入失敗，算法結(jié)束，否則繼續(xù)執(zhí)行步驟3）。

3）如果goal點(diǎn)在鄰居列表中，插入成功，算法結(jié)束;如果goal點(diǎn)不在鄰居列表中，從鄰居列表中選擇距離goal點(diǎn)最近的點(diǎn)P，將點(diǎn)P從鄰居列表刪除。

4）若點(diǎn)P與當(dāng)前點(diǎn)是相鄰柵格，則令點(diǎn)P為當(dāng)前點(diǎn)，同時(shí)將點(diǎn)P加入路徑點(diǎn)列表，跳到步驟1）;若點(diǎn)P與當(dāng)前點(diǎn)不是相鄰柵格，連接失敗，算法結(jié)束。

1.8 刪除算子

刪除算子是將個(gè)體中相同路徑點(diǎn)之間的路徑點(diǎn)與這兩個(gè)相同路徑點(diǎn)中的一個(gè)刪除，去除了冗余路徑點(diǎn)。

1.9 優(yōu)化算子

優(yōu)化算子是檢查個(gè)體中連接第i個(gè)路徑點(diǎn)（path（i））的前一個(gè)路徑點(diǎn)（path（i-l））與后一個(gè)路徑點(diǎn)（path（i+l））的直線是否經(jīng)過(guò)障礙物柵格，若不經(jīng)過(guò)，則將此指定點(diǎn)從個(gè)體中刪除。優(yōu)化算子的偽代碼如下：

flag=1;

while flag==l

for i=2： size（ path， 2）-1

if deletable（i，path）

delete path（i）from path

flag=1;

break

end

flag=0;

end

end

其中deletable（i，path）指的是判斷第i個(gè)路徑點(diǎn)是否可刪除。

1.10 改進(jìn)遺傳算法柵格法路徑規(guī)劃流程

1）路徑初始化，產(chǎn)生給定數(shù)量的個(gè)體;

2）使用選擇算子產(chǎn)生下一代個(gè)體;

3）從種群中隨機(jī)選擇2個(gè)個(gè)體，使用交叉算子進(jìn)行交叉;

4）從種群中隨機(jī)選擇一個(gè)個(gè)體，使用變異算子進(jìn)行變異;

5）對(duì)種群中所有個(gè)體分別調(diào)用刪除算子，優(yōu)化算子，若未達(dá)到指定迭代次數(shù)，跳到步驟2），否則，算法結(jié)束。

2 仿真

在Matlab 2014a，13 -4000M的CPU環(huán)境下進(jìn)行仿真。仿真部分比較了文中算法與文獻(xiàn)[3]算法在3個(gè)地圖環(huán)境下得到的路徑長(zhǎng)度與路徑達(dá)到最優(yōu)所用時(shí)間（算法效率），如圖3、表1所示。

起點(diǎn)為左下角柵格，終點(diǎn)為右上角柵格，種群大小為5，迭代次數(shù)500。在地圖3中，由于文獻(xiàn)[3]算法初始化方法只選擇固定幾個(gè)方向進(jìn)行移動(dòng)，故對(duì)轉(zhuǎn)彎過(guò)多的環(huán)境不適用，從地圖3可以看出文中算法在復(fù)雜環(huán)境下的可行性。

3 結(jié)語(yǔ)

根據(jù)本文提出的初始化方式，變異及插入與優(yōu)化算子，在Matlab中與文獻(xiàn)[3]中的改進(jìn)遺傳算法對(duì)比，仿真結(jié)果表明本文提出的算法在不同環(huán)境下得到的路徑可行、有效。

注：本文通訊作者為王志明。

參考文獻(xiàn)

[1]喬莎莎，吳勇，張建東，等，基于遺傳算法和人T勢(shì)場(chǎng)法的路徑規(guī)劃[J]現(xiàn)代電子技術(shù)，2012，35（12）：75-78.

QIAO Shasha. WU Yong， ZHANG Jiandong， et aI.Path plan-ning based on genetic algorithm and artificial potential fieldmethod[J]. Modern electronics technique， 2012， 35（ 12）： 75-78.

[2]盧月品，趙陽(yáng)，孟躍強(qiáng)，等.基于改進(jìn)遺傳算法的狹窄空間路徑規(guī)劃[J]計(jì)算機(jī)應(yīng)用研究，2015，32（2）：413-418.

LU Yuepin. ZHAO Yang， MENG Yueqiang， et al.Path plan-ning in narrow space by improved genetic algorithm [J]. Appli-cation research of computers， 2015， 32（2）：413-418.

[3]田欣，劉廣瑞，周文博，等.基于改進(jìn)白適應(yīng)遺傳算法的機(jī)器人路徑規(guī)劃研究[J]機(jī)床與液壓，2016，44（ 17）：24-28.

TIAN Xin. LIU Guangrui， ZHOU Wenbo. et al.Research ofrobot path planning based on improved adaptive genetic algo-rithm [J]. Machine tool and hydraulics， 2016. 44（17） ： 24-28.

[4]楊獻(xiàn)峰，付俊輝 .移動(dòng)機(jī)器人路徑規(guī)劃的仿真研究[J]. 計(jì)算機(jī)仿真， 2012.29（ 7） ：223-226.

YANG Xianfeng， FU Junhui. Mobile robot path planning basedon grid algorithm and CGA [J]. Computer simulation. 2012， 29（7） ： 223-226.

[5] KARAMI A H. HASANZADEH M. An adaptive genetic algo-rithm for robot motion planning in 2D complex environments[J]. Computers & electrical engineering， 2015. 43 ： 317-329.

[6] 11 M F， WANG C J， CHEN Z Q， et al. Pathplanning of mo-hile rohot based on genetic algorithm and gene rearrangement[C]// Chinese Automation Congress. Jinan： IEEE， 2017： 6999- 7004.

[7] ARORA T， GIGRAS Y， ARORA V. Robotic path planning us-ing genetic algorithm in dynamic environment [J]. Internationaljournal of computer applications ， 2014. 89（ 11 ） ： 8-12.

[8] FU B. CHEN L， ZHOU Y T， et al. An improved A' algorithmfor the industrial robot path planning with high success rateand shortlength [J]. Robotics & autonomous systems. 2018，106： 26-37.

[9] PATLE B K. PARHI D R K. JAGADEESH A. et al. Matrix-Binary codes based Genetic Algorithm for path planning of mo-bile robot [J]. Computers & electrical engineering， 2017. 45 ： 1-

[10] ISLAM F， NASIR J. MALIK U. et al. RRT#-Smart： Rapidconvergence implementation of RRT* towards optimal solution[C]// International Conference on Mechatronics and Automa-tion. Chengdu ： IEEE . 2012 ： 1651-1656.

作者簡(jiǎn)介：宋宇（1969-），男，黑龍江呼蘭人，教授，主要研究領(lǐng)域?yàn)榍度胧较到y(tǒng)設(shè)計(jì)與研究。

王志明（1991-），男，山西神池人，碩士研究生，主要研究領(lǐng)域?yàn)槁窂揭?guī)劃。