一種融合模擬退火的改進(jìn)遺傳算法多任務(wù)路徑規(guī)劃*

孫麗娜，田軍委，劉雪松，王 沁

(1.西安工業(yè)大學(xué) 機(jī)電工程學(xué)院，西安 710021；2.內(nèi)蒙古北方重工業(yè)集團(tuán)有限公司，包頭 014033)

在“中國制造2025”飛速發(fā)展和創(chuàng)新中國戰(zhàn)略實行下，移動機(jī)器人技術(shù)不斷進(jìn)步[1]。為了提高機(jī)器人作業(yè)效率和整體效益，常常將多個任務(wù)同時賦予單個機(jī)器人以實現(xiàn)最佳作業(yè)能力[2]。田間作業(yè)有任務(wù)多樣性和環(huán)境復(fù)雜性的特點，路徑規(guī)劃作為機(jī)器人田間正常工作的基礎(chǔ)之一，研究工作十分必要。

路徑規(guī)劃是指以順利到達(dá)目標(biāo)位置的代價最小化為目標(biāo)，規(guī)劃出一條機(jī)器人行走的路徑[3]。遺傳算法是機(jī)器人路徑規(guī)劃較常用的算法之一，但是經(jīng)典遺傳算法存在局部搜索能力較差、易產(chǎn)生早熟收斂等缺陷，所以不少學(xué)者對經(jīng)典遺傳算法進(jìn)行了改進(jìn)。文獻(xiàn)[4-9]從遺傳算法的操作算子進(jìn)行改進(jìn)，重新定義各個算子、自適應(yīng)交叉概率和變異概率。改進(jìn)后加快算法的收斂速度，但當(dāng)任務(wù)復(fù)雜度增加時算法會過早陷入局部收斂。文獻(xiàn)[10-13]對適應(yīng)度函數(shù)進(jìn)行了改進(jìn)，如添加轉(zhuǎn)彎角度控制因子、路徑連貫性，同時考慮多個適應(yīng)度影響因素時不能有效保證路徑值最短。文獻(xiàn)[14-16]遺傳算法分別與不同算法進(jìn)行融合，解決了局部最優(yōu)解的問題，但沒有考慮多個任務(wù)點的情況，不能驗證改進(jìn)算法在增加任務(wù)點后的算法可行性。

本文針對多個任務(wù)點的作業(yè)環(huán)境，將模擬退火算法的進(jìn)化機(jī)制融合至遺傳算法,改善遺傳算法的局部搜索能力和算法收斂速度。

1 環(huán)境地圖建模

環(huán)境地圖包含了大量的空間準(zhǔn)確位置信息：機(jī)器人的起點、終點、任務(wù)點、障礙物等,如圖1所示。

圖1 柵格地圖模型

文中環(huán)境是二維平面靜態(tài)地圖，用柵格法來建立環(huán)境模型(20 m×20 m的尺寸)，柵格法是環(huán)境建模方面應(yīng)用最廣泛的方法之一，它將機(jī)器人所在空間抽象為二維空間。每個單元格具備一種環(huán)境信息，占據(jù)柵格的數(shù)值為1，未占據(jù)的柵格數(shù)值為0。圖1中的白色網(wǎng)格表示機(jī)器人可以穿越的區(qū)域，黑色網(wǎng)格表示障礙物。

2 改進(jìn)的多任務(wù)機(jī)器人路徑規(guī)劃

遺傳算法作為一種群體智能算法，具有較強(qiáng)的全局尋優(yōu)能力。文中以遺傳算法作為模型求解算法，針對其易于早熟收斂、收斂速度慢等問題進(jìn)行改進(jìn)，融合模擬退火算法Metropolis準(zhǔn)則提高算法的局部尋優(yōu)能力。模擬退火算法源于現(xiàn)實的物理退火過程，通過抽象真實物理退火過程中的加溫過程、等溫過程、冷卻過程來求得最優(yōu)解，通過其特有的接受準(zhǔn)則來保證算法局部尋優(yōu)能力。

2.1 編碼方式

柵格序號與柵格坐標(biāo)相比，具有形式簡單的優(yōu)點。因此，本文對染色體的編碼采用柵格序號。即在柵格地圖中按照從上到下、從左到右的順序?qū)⑿鸥襁M(jìn)行編號，0代表機(jī)器人移動起點，399代表移動終點，中間任務(wù)點的位置編號同樣。

為確保機(jī)器人路徑規(guī)劃的可靠性，要求每條可行路徑不能出現(xiàn)障礙物序號和重復(fù)序號。如：P={S,P1,P2,P3…Pn,G}表示一條可行路徑，其中S為起點，G為終點，Pi(i=1,2,3…n)是柵格中的可行節(jié)點。

2.2 種群初始化

種群初始化時，由機(jī)器人移動環(huán)境中障礙物信息已知，柵格化環(huán)境地圖后，自由柵格和障礙柵格容易區(qū)分。所以采用在移動機(jī)器人運動起點到終點之間，隨機(jī)選擇一系列標(biāo)記為0的自由柵格作為路徑節(jié)點。連接起點、終點和選定的路徑節(jié)點作為機(jī)器人移動的一條無障礙路徑。

2.3 建立適應(yīng)度函數(shù)

算法的適應(yīng)度函數(shù)即模型優(yōu)化目標(biāo)函數(shù)。文中以路徑距離作為函數(shù)評價指標(biāo)，一條可行路徑上是由許多個節(jié)點連接而成，則路徑距離L為

(1)

式中：n為機(jī)器人通過的柵格總數(shù)；xi為第i個節(jié)點的橫坐標(biāo)；yi為第i個節(jié)點的縱坐標(biāo)。

對機(jī)器人路徑選擇，路徑越短則為更優(yōu)，則目標(biāo)函數(shù)即適應(yīng)度函數(shù)F為路徑距離L的倒數(shù)。

2.4 遺傳算子操作

2.4.1 選擇算子

在遺傳算法開始時，總是隨機(jī)的產(chǎn)生一些個體(即初始解)，根據(jù)預(yù)定的目標(biāo)函數(shù)對每一個體進(jìn)行評估，給出一個適應(yīng)度值，基于此適應(yīng)度值選擇一些個體用來產(chǎn)生下一代。較優(yōu)的個體被留下，經(jīng)過交叉和變異算子進(jìn)行組合再生成新的一代，這樣逐步朝著最優(yōu)解的方向進(jìn)化。文中采用輪盤賭選擇方法，個體被選中的概率與適應(yīng)度函數(shù)值大小成正比。即N個的適應(yīng)值變換為1至N，則編號為m的個體被選中的概率P為

(2)

2.4.2 交叉算子

遺傳算法通過交叉算子來維持種群的多樣性。文中采用常見單點交叉方法，即隨機(jī)選擇兩條父代路徑，在兩條路徑的相同節(jié)點處進(jìn)行交叉操作，不包含起點和終點，若相同節(jié)點有多個則隨機(jī)選擇一個節(jié)點交叉。當(dāng)兩條父代路徑?jīng)]有相同節(jié)點或者交叉后基因相同時，則放棄本次交叉操作，父代個體為

V1={0,23,89,156,235,289,376,399},

V2={0,34,93,158,321,289,364,399}。

選擇父代的相同節(jié)點289作為交叉點，則生成的兩條子代個體為

C1={0,23,89,156,235,289,364,399}，

C2={0,34,93,158,321,289,376,399}。

2.4.3 變異算子

采取隨機(jī)變異的方法進(jìn)行變異操作。從個體中除終點和起點之外隨機(jī)選擇一個序號視為變異點，然后刪除該序號，這樣可避免出現(xiàn)不可行解。

2.5 融合Metropolis準(zhǔn)則

模擬退火算法具有較強(qiáng)的局部尋優(yōu)能力，為了解決遺傳算法易陷入局部最優(yōu)解的問題，文中將模擬退火算法的進(jìn)化機(jī)制融合至遺傳算法中。

模擬退火算法存在一定的容錯能力，能以一定概率接受劣質(zhì)解，概率P為新解接受概率，大小受當(dāng)前溫度T及新舊解適應(yīng)度E差的影響，總的趨勢是溫度越低接受概率越低，差值越大接受概率越低。

當(dāng)E(xnew)

當(dāng)E(xnew)≥E(xold)時，

(3)

得到接受概率后隨機(jī)產(chǎn)生一個隨機(jī)數(shù)，介于0到1之間，當(dāng)其大于接受概率P時，不接受新解，當(dāng)其小于P時，接受新解。故在遺傳算法操作產(chǎn)生新解后可采用Metropolis準(zhǔn)則決定是否保留新解。

2.6 多任務(wù)分解

文中設(shè)置了多個任務(wù)點，機(jī)器人在移動過程中從起點出發(fā)經(jīng)歷多個任務(wù)點最終到達(dá)終點。要使機(jī)器人行走的總路徑最短，將多任務(wù)路徑分解成單任務(wù)路徑，保證單任務(wù)路徑最短則總路徑即為最短。柵格圖中起點編號為0，終點編號為399，兩個任務(wù)點編號分別為110和246，則可以分解為：[0,110],[110,246],[246,399]，總路徑即為三段路徑之和。

3 仿真結(jié)果及分析

為驗證文中提出算法的合理性和有效性，運用Matlab軟件在20 m×20 m的柵格環(huán)境模型中進(jìn)行仿真分析。參數(shù)設(shè)置見表1。

表1 參數(shù)設(shè)置

在仿真實驗中分別設(shè)置障礙物個數(shù)為31個和69個，在不同任務(wù)點個數(shù)下對移動機(jī)器人進(jìn)行路徑規(guī)劃，實驗圖中路徑長度取單位為米。

3.1 雙任務(wù)實驗

障礙物個數(shù)為31個時的仿真實驗結(jié)果如圖2和圖3所示，經(jīng)典遺傳算法在進(jìn)化8代得到路徑值為39.799 0 m。改進(jìn)遺傳算法在進(jìn)化第5代后趨于穩(wěn)定，得到路徑值為37.799 0 m。為了驗證本文所提出改進(jìn)遺傳算法的有效性，與文獻(xiàn)[7]提出的自適應(yīng)改進(jìn)遺傳算法選擇相同的工作環(huán)境，即障礙物的個數(shù)設(shè)置為31個。雙任務(wù)點下三種算法的仿真實驗結(jié)果對比見表2。

表2 仿真實驗結(jié)果對比

圖2 實驗運動軌跡圖

圖3 算法收斂曲線圖

當(dāng)障礙物數(shù)量增加到69個時，三種算法的仿真實驗結(jié)果如圖4和圖5所示，結(jié)果對比見表3。

圖4 實驗運動軌跡圖

圖5 算法收斂曲線圖

表3 仿真實驗結(jié)果對比

經(jīng)典遺傳算法在進(jìn)化11代陷入了局部最優(yōu)解，自適應(yīng)改進(jìn)算法在進(jìn)化6代收斂，而文中的改進(jìn)遺傳算法進(jìn)化4代達(dá)到穩(wěn)定。由此可得，改進(jìn)遺傳算法的收斂速度優(yōu)于這兩種算法，且路徑值更短。

3.2 三任務(wù)實驗

障礙物個數(shù)為31個時，機(jī)器人在工作時需要經(jīng)歷三個任務(wù)點的仿真實驗結(jié)果如圖6和圖7所示，標(biāo)準(zhǔn)遺傳算法的路徑長度為37.799 0 m，自適應(yīng)改進(jìn)算法的路徑長度為37.799 0 m，而文中的改進(jìn)算法路徑長度為36.627 4 m。經(jīng)典遺傳算法在12代時陷入了局部最優(yōu)解，自適應(yīng)改進(jìn)算法在8代達(dá)到收斂，實驗結(jié)果如圖8所示，而改進(jìn)后的算法在4代時候趨于穩(wěn)定狀態(tài)，改進(jìn)后的算法對移動機(jī)器人的靜態(tài)最優(yōu)路徑優(yōu)于標(biāo)準(zhǔn)遺傳算法。三種算法在收斂速度、最短路徑長度方面的對比見表4。

圖6 實驗運動軌跡圖

圖7 算法收斂曲線圖

圖8 自適應(yīng)改進(jìn)算法仿真實驗結(jié)果

表4 仿真實驗結(jié)果對比

移動機(jī)器人作業(yè)需要在69個障礙物下遍歷三個任務(wù)點時，實驗結(jié)果如圖9和圖10所示。自適應(yīng)改進(jìn)算法的實驗結(jié)果如圖11所示。經(jīng)典遺傳算法在進(jìn)化18代得到路徑值為36.727 9 m；自適應(yīng)改進(jìn)算法算法在進(jìn)化9代得到路徑值35.313 7 m，而本文的改進(jìn)遺傳算法克服了局部最優(yōu)解的缺陷，在進(jìn)化7代后趨于穩(wěn)定，得到路徑值為34.729 7 m。三種算法的仿真實驗結(jié)果對比見表5。

圖9 實驗運動軌跡圖

圖10 算法收斂曲線圖

圖11 自適應(yīng)改進(jìn)算法仿真實驗結(jié)果

表5 仿真實驗結(jié)果對比

4 結(jié) 論

1) 本文以遺傳算法為求解算法模型，提出一種融合模擬退火的改進(jìn)算法。

2) 在雙任務(wù)作業(yè)要求下，障礙物個數(shù)設(shè)置為31個和69個時，文中提出的算法較經(jīng)典遺傳算法的路徑值分別縮短了約5%和9%，收斂速度分別提高了約44%和64%；對比自適應(yīng)改進(jìn)算法，路徑值分別縮短了約5%和2%，收斂速度分別提高了約29%和33%。

3) 任務(wù)點增加到三個時，同樣在障礙物個數(shù)為31個和69個中驗證改進(jìn)算法，對比遺傳算法路徑值分別縮短了約3%和5%，收斂速度分別提高了約67%和61%；與自適應(yīng)改進(jìn)算法作比較，路徑值分別縮短了約3%和2%，收斂速度分別提高了約50%和22%。

4) 文中提出的融合模擬退火改進(jìn)遺傳算法適用于二維環(huán)境下的地面移動機(jī)器人路徑規(guī)劃，尚未擴(kuò)展到無人機(jī)以及水下機(jī)器人的應(yīng)用，可將多任務(wù)路徑規(guī)劃問題逐步拓展到如海洋探測、山林探險、自然災(zāi)害救災(zāi)等三維環(huán)境。