考慮多因素的自適應(yīng)遺傳算法機(jī)器人路徑規(guī)劃

李航宇，郭曉利

（1.吉林電子信息職業(yè)技術(shù)學(xué)院，吉林 132021；2.東北電力大學(xué) 信息工程學(xué)院，吉林 132021）

0 引言

移動(dòng)機(jī)器人路徑規(guī)劃技術(shù)是機(jī)器人領(lǐng)域內(nèi)重要的研究方向。它是指機(jī)器人在一個(gè)特定的環(huán)境下，從起始點(diǎn)至終點(diǎn)搜索出一條符合約束條件的運(yùn)行路徑，同時(shí)完成相應(yīng)的工作。國(guó)內(nèi)外對(duì)機(jī)器人路徑規(guī)劃算法有許多的研究，常采用的方法有算法[1]、算法[2]、神經(jīng)網(wǎng)絡(luò)算法[3]、人工勢(shì)場(chǎng)法[4]等。同時(shí)隨著路徑規(guī)劃問(wèn)題復(fù)雜度的提升，出現(xiàn)了大量的仿生算法，例如蟻群算法[5]、蜂群算法[6]、粒子群算法[7]、遺傳算法等。上述算法在機(jī)器人路徑規(guī)劃問(wèn)題上都取得了良好的表現(xiàn)，但是其中大部分算法優(yōu)化目標(biāo)考慮的因素不足，無(wú)法滿足機(jī)器人實(shí)際中的工作。

遺傳算法作為一種優(yōu)化算法，在機(jī)器人路徑規(guī)劃領(lǐng)域內(nèi)有著大量應(yīng)用。基本的遺傳算法自身有著許多缺陷，因此大批學(xué)者對(duì)遺傳算法進(jìn)行了改進(jìn)。魏彤等[8]針對(duì)許多算法得出的路徑非最短及規(guī)劃間斷問(wèn)題,提出一種改進(jìn)遺傳算法的路徑規(guī)劃方法。在遺傳操作中，加入插入算子和刪除算子,提升了算法的計(jì)算準(zhǔn)確度，獲得了最優(yōu)路徑。徐夢(mèng)穎等[9]提出一種具有自適應(yīng)策略的遺傳算法，該算法模型引入克隆算子及自適應(yīng)算子，從而防止算法陷入局部極值,并且提高了算法運(yùn)行效率。孫波等[10]首先利用模擬退火法對(duì)種群進(jìn)行選擇,豐富了種群的多樣性；同時(shí)利用自適應(yīng)交叉、變異算子和精英策略，加快算法的收斂；另外在適應(yīng)度函數(shù)中加入路徑平滑度、擁擠度和車輛質(zhì)量等三個(gè)因素,從而規(guī)劃出更適應(yīng)實(shí)際環(huán)境的路徑。

結(jié)合上述提到的問(wèn)題，提出一種考慮多因素的自適應(yīng)遺傳算法進(jìn)行路徑規(guī)劃，根據(jù)實(shí)際的運(yùn)行環(huán)境同時(shí)考慮路徑長(zhǎng)度、轉(zhuǎn)向次數(shù)及環(huán)境坡度等多個(gè)因素，另外對(duì)遺傳操作進(jìn)行調(diào)整，從而提升最優(yōu)路徑的綜合性能及算法效率。

1 環(huán)境建模及問(wèn)題描述

機(jī)器人路徑規(guī)劃問(wèn)題指的是在特定的約束下，搜尋出一條最佳路徑，可表示為：

式(1)中，f(p)表示路徑的目標(biāo)函數(shù)，ps為起始點(diǎn)，po為目標(biāo)點(diǎn),(ps,po)表示起終點(diǎn)之間的路徑節(jié)點(diǎn)集合。

環(huán)境建模是指將實(shí)際環(huán)境映射至一個(gè)抽象空間上。機(jī)器人路徑規(guī)劃建模環(huán)境主要有柵格圖、可視圖、自由空間等。其中柵格地圖創(chuàng)建簡(jiǎn)單且管理方便，因此采用柵格圖作為仿真環(huán)境。在柵格地圖中，黑色柵格代表障礙物，白色柵格代表可行區(qū)域，利用直角坐標(biāo)進(jìn)行定位。為了保證機(jī)器人運(yùn)行的安全，將實(shí)際環(huán)境轉(zhuǎn)換為柵格圖過(guò)程中規(guī)定，障礙物占用不足一個(gè)柵格時(shí)將其膨脹為一格，且機(jī)器人禁止沿著障礙物邊緣運(yùn)行。柵格地圖環(huán)境如圖1所示。假設(shè)柵格地圖環(huán)境中，柵格標(biāo)號(hào)按從下到上，從左至右的順序依次增大。柵格地圖大小為M行N列，柵格標(biāo)號(hào)為Y，則柵格標(biāo)號(hào)與柵格中心直角坐標(biāo)換算公式如式(2)所示：

圖1 柵格地圖

式(2)中，mod表示取余，int指取整。

2 改進(jìn)遺傳算法

2.1 改進(jìn)適應(yīng)度函數(shù)

遺傳算法中適應(yīng)度函數(shù)表示種群中個(gè)體質(zhì)量，它反映了個(gè)體可被選入到下代的概率，是整個(gè)算法的核心。在基本遺傳算法中適應(yīng)度函數(shù)只與路徑距離有關(guān)，可表示為：

式(3)中只考慮了路徑長(zhǎng)度，為了提升路徑的綜合性能，對(duì)適應(yīng)度函數(shù)做如下修改：

式(4)中表示距離因素，指轉(zhuǎn)向因素，是環(huán)境高度。

2.1.1 距離因素

基本遺傳算法只考慮路徑距離，忽略了鄰近個(gè)體之間的距離，若它們相隔較遠(yuǎn)可能會(huì)使得可行路徑減少，因此必須剔除兩點(diǎn)相隔較遠(yuǎn)的個(gè)體，擴(kuò)大搜索范圍。另外，為了提升算法的避障性能，在距離因素中引入懲罰項(xiàng)，減少種群中不良個(gè)體數(shù)。因此對(duì)距離因素做如下修改：

式(5)中，n為路徑經(jīng)過(guò)總柵格數(shù)，f(pipi+1)表示鄰近兩柵格之間障礙物的總數(shù)。

2.1.2 轉(zhuǎn)向因素

在機(jī)器人工作時(shí)除了要求路徑距離短，還應(yīng)避免轉(zhuǎn)向次數(shù)過(guò)多，從而減少自身的損耗。經(jīng)典遺傳算法中沒(méi)有考慮此因素，可能會(huì)導(dǎo)致能耗成本增加。因此在適應(yīng)度函數(shù)中引入轉(zhuǎn)向因素，其表達(dá)式如式(6)所示：

式(6)中，u為常數(shù)，θ是一個(gè)百分?jǐn)?shù)，反映了直行的重要度，t為當(dāng)前迭代數(shù)，dirz,i為z號(hào)柵格轉(zhuǎn)移至i號(hào)柵格的轉(zhuǎn)向標(biāo)號(hào)，card作用是求集合元素?cái)?shù)目，A為可行柵格集合，visited為已訪問(wèn)的柵格集合。通過(guò)式(6)，可以有效減少機(jī)器人轉(zhuǎn)向次數(shù)，從而降低自身?yè)p耗，提升使用壽命。

2.1.3 高度因素

在實(shí)際的機(jī)器人運(yùn)行環(huán)境中，周圍環(huán)境往往不是平地，經(jīng)常會(huì)遇到高度的變化，因此在遇到坡度變化大的環(huán)境時(shí)，應(yīng)該盡量減少爬坡次數(shù)且避免經(jīng)過(guò)坡度大的陡坡，從而降低能量的消耗。為使路徑更為平緩在適應(yīng)度函數(shù)中加入環(huán)境高度函數(shù)，公式如下：

式(7)中，h為高度矩陣，λ，σ指高度修正常數(shù)。maxh，minh分別是相鄰柵格中與當(dāng)前柵格的最大和最小高度差，0.01保證分母不為零。

2.2 改進(jìn)遺傳操作

僅通過(guò)經(jīng)典的遺傳操作，難以達(dá)到良好的避障效果，無(wú)法適應(yīng)機(jī)器人實(shí)際作業(yè)環(huán)境。因此本文在傳統(tǒng)的操作過(guò)程中加入刪減及增添算子，具體的改進(jìn)如下：

1）刪減算子。在規(guī)劃時(shí)路徑可能會(huì)產(chǎn)生自交現(xiàn)象，導(dǎo)致出現(xiàn)無(wú)用路徑，不利于節(jié)省運(yùn)算空間。因此可以引入刪減算子檢查路徑中是否有重復(fù)的柵格，如果存在則表示路徑中有自交現(xiàn)象，可以利用刪減算子去除此段路經(jīng)，從而減少無(wú)用路徑。

2）增添算子。路徑中相鄰兩節(jié)點(diǎn)可能出現(xiàn)相距較遠(yuǎn)，鄰域不可達(dá)等情形，使得無(wú)法找出所有尋優(yōu)路徑。因此通過(guò)加入增添算子，保證相鄰節(jié)點(diǎn)位于同一鄰域。如果出現(xiàn)鄰域不統(tǒng)一的相鄰節(jié)點(diǎn)，則在它們之間連線中點(diǎn)處增加一個(gè)節(jié)點(diǎn)柵格，不斷重復(fù)此操作，直到路徑中所有節(jié)點(diǎn)滿足條件。

2.3 自適應(yīng)遺傳算子

基本遺傳算法中遺傳操作的交叉及變異概率是保持不變的，無(wú)法適應(yīng)動(dòng)態(tài)的環(huán)境。為提升算法的搜索性能及效率，在遺傳操作中采用自適應(yīng)交叉概率及變異概率，具體公式如式(8)、式(9)所示：

式(8)、式(9)中，pc1和pc2分別為最大及最小交叉概率，pm1和pm2為最大及最小變異概率，f0為交叉時(shí)數(shù)值更大的個(gè)體的適應(yīng)度，fa為平均適應(yīng)度值，f為變異個(gè)體的適應(yīng)度大小，fmax為適應(yīng)度最大值。通過(guò)調(diào)整變異及交叉概率，可在算法的初期保留更多的優(yōu)良個(gè)體，而在算法后期能防止算法進(jìn)入局部最優(yōu)。

2.4 改進(jìn)算法實(shí)現(xiàn)流程

步驟1：建立柵格環(huán)境，設(shè)置算法參數(shù)的初始值。

步驟2：生成遺傳算法的初始種群。

步驟3：進(jìn)行遺傳操作，首先進(jìn)行輪盤賭選擇操作，然后根據(jù)式(7)和式(8)自適應(yīng)調(diào)節(jié)交叉與變異概率，進(jìn)行交叉與變異操作，產(chǎn)生相應(yīng)種群。

步驟4：將上一步驟中得到的種群個(gè)體，代入式(4)中計(jì)算出各自的適應(yīng)度值。

步驟5：判斷本輪迭代是否結(jié)束，如果結(jié)束繼續(xù)執(zhí)行下一步驟，反之則返回步驟3。

步驟6：判斷是否達(dá)到最大迭代數(shù)，若是執(zhí)行下一步驟，否則，返回步驟2。

步驟7：得到最優(yōu)的路徑。

上述步驟對(duì)應(yīng)的算法流程圖，如圖2所示。

圖2 算法流程圖

3 仿真實(shí)驗(yàn)及分析

3.1 常規(guī)環(huán)境仿真

基于MATLAB R2017b平臺(tái)對(duì)算法進(jìn)行實(shí)例仿真。其他仿真運(yùn)行條件為：Windows9操作系統(tǒng)；GPU 2.4GHz；運(yùn)行內(nèi)存為8GB。算法主要參數(shù)值為：種群規(guī)模80，最大迭代數(shù)為200，u為20，θ為50%，高度修正常數(shù)λ=5，σ=1，選擇概率為0.9，變異概率初始值為0.01，最大變異概率為0.1，最小變異概率為0.01，交叉概率初始值為0.7，最大交叉概率為0.8，最小交叉概率為0.6。

柵格地圖環(huán)境大小為15×15，起點(diǎn)為(0.5,0.5),終點(diǎn)為(14.5,14.5)。其中圖中灰色越深表示高度越高。改進(jìn)遺傳算法及基本遺傳算法的實(shí)例仿真圖如圖3和圖4所示，多次實(shí)驗(yàn)得出的各個(gè)指標(biāo)平均值的對(duì)比結(jié)果如表1所示。

圖3 基本遺傳算法仿真圖

圖4 改進(jìn)遺傳算法仿真圖

表1 算法結(jié)果對(duì)比

由圖(3)和圖(4)能夠直觀的看出，基本遺傳算法規(guī)劃出的路徑轉(zhuǎn)折次數(shù)多于改進(jìn)的遺傳算法，另外基本遺傳算法無(wú)法避開(kāi)坡度大的區(qū)域，而改進(jìn)的遺傳算法則解決了這一問(wèn)題，其規(guī)劃的路徑更為平坦。從表1能夠精確的看出兩種算法具體指標(biāo)上的差異，本文改進(jìn)算法雖在路徑長(zhǎng)度上稍遜于基本遺傳算法，但是因?yàn)楦倪M(jìn)的遺傳算法加入考慮了轉(zhuǎn)彎和高度等因素，在綜合指標(biāo)上明顯優(yōu)于基本遺傳算法，且規(guī)劃速度更快。從上述分析可知，在同一環(huán)境下，改進(jìn)遺傳算法的綜合表現(xiàn)更好，更加適合機(jī)器人的實(shí)際工作情景。

3.2 極端環(huán)境仿真

在特殊的極端地形下，基于規(guī)格的柵格地圖進(jìn)行仿真分析，其他參數(shù)值保持不變。改進(jìn)前后的算法仿真圖如圖5和6所示。

圖5 基本遺傳算法仿真圖

圖6 改進(jìn)遺傳算法仿真圖

根據(jù)以上兩圖，可以看出在特殊的地形下，改進(jìn)的算法在轉(zhuǎn)向次數(shù)上遠(yuǎn)少于基本遺傳算法，使得機(jī)器人在轉(zhuǎn)向上的能量消耗大大減少。因此在極端環(huán)境下，改進(jìn)的遺傳算法優(yōu)勢(shì)更加明顯，展現(xiàn)出更強(qiáng)的環(huán)境適應(yīng)能力。

4 結(jié)語(yǔ)

針對(duì)當(dāng)前機(jī)器人路徑規(guī)劃算法存在的不足，提出一種考慮多因素的自適應(yīng)遺傳算法，可以得到下列結(jié)論：

1）在基本遺傳算法的適應(yīng)度函數(shù)中，加入轉(zhuǎn)向及環(huán)境高度因素，更加符合實(shí)際環(huán)境，改進(jìn)遺傳算法得出的路徑綜合指標(biāo)得到了較大提升。

2）改進(jìn)遺傳操作中的交叉及變異概率的調(diào)節(jié)機(jī)制，設(shè)計(jì)了自適應(yīng)方案，動(dòng)態(tài)調(diào)整交叉及變異因子，從而提升算法的計(jì)算效率及搜索性能。

3）在遺傳操作中，引進(jìn)刪減及增添算子，從而增強(qiáng)算法避障能力。