具有修正策略的改進(jìn)NSGA－II 三維路徑規(guī)劃

封建湖，鄭寶娟，封 碩，張婷宇

（1.長(zhǎng)安大學(xué)理學(xué)院，陜西 西安 710064；2.長(zhǎng)安大學(xué)工程機(jī)械學(xué)院，陜西 西安 710064）

1 引言

路徑規(guī)劃是機(jī)器人定位與導(dǎo)航領(lǐng)域研究的熱點(diǎn)問題之一，目前的路徑規(guī)劃方法如蟻群算法，粒子群算法，蜂群算法，螢火蟲算法及混合算法等[1-3]多用于二維平面空間規(guī)劃。在復(fù)雜環(huán)境下三維空間的機(jī)器人路徑避障問題越來越受到學(xué)者們的關(guān)注。例如，文獻(xiàn)[4]提出了一種結(jié)合人工勢(shì)場(chǎng)思想的改進(jìn)蟻群算法并用于三維路徑規(guī)劃，并將路徑的長(zhǎng)度作為優(yōu)化準(zhǔn)則，但是只優(yōu)化了路徑長(zhǎng)度，實(shí)用性不高。文獻(xiàn)[5]提出在偏微分高程建模下蟻群算法的三維路徑規(guī)劃方法，但計(jì)算結(jié)果容易陷入局部最優(yōu)。

遺傳算法根據(jù)生物進(jìn)化過程的自然遺傳理論構(gòu)造的隨機(jī)搜索算法，其優(yōu)點(diǎn)是并行計(jì)算能力強(qiáng)，魯棒性和全局收斂性好，已經(jīng)成功地應(yīng)用于機(jī)器人的路徑規(guī)劃問題。對(duì)多目標(biāo)的遺傳算法，文獻(xiàn)[6]改進(jìn)了非支配排序遺傳算法（NSGA），提出了復(fù)雜度更低，更能保持種群多樣性，具有Pareto 占優(yōu)的NSGA-II 算法。文獻(xiàn)[7]考慮路徑長(zhǎng)度和難度，加入修正算子減少冗余路徑，從而改進(jìn)NSGA-II 算法并成功應(yīng)用于二維路徑規(guī)劃，取得了很好的效果。文獻(xiàn)[8]在二維空間中優(yōu)化了路徑長(zhǎng)度、路徑安全性和路徑平滑度，在NSGA-II 算法的基礎(chǔ)上加入輔助選擇算子，并證明了輔助選擇算子使算法得到的Pareto 解更優(yōu)，但對(duì)冗余路徑情況和路徑能耗未做考慮。

針對(duì)以上算法的優(yōu)勢(shì)和不足，嘗試基于NSGA-II 算法研究三維多目標(biāo)路徑規(guī)劃，首先，構(gòu)造復(fù)雜的三維曲面空間并柵格化；其次考慮路徑長(zhǎng)度，能耗，路徑起伏等優(yōu)化因子，建立多目標(biāo)優(yōu)化函數(shù)；最后基于文獻(xiàn)[7-8]的改進(jìn)成果，對(duì)NSGA-II 算法進(jìn)行改進(jìn)，在選擇算子中加入輔助選擇算子，得到更優(yōu)的Pareto 前沿解集，設(shè)計(jì)多種路徑優(yōu)化的遺傳算子，加快搜索能力，使其更好地應(yīng)用到路徑規(guī)劃問題上。

2 規(guī)劃空間的構(gòu)造

2.1 地形構(gòu)建及柵格化處理

使用柵格表示的方法，根據(jù)機(jī)器人的尺寸，將三維曲面空間離散成若干的柵格，建立笛卡爾坐標(biāo)系，每個(gè)柵格都對(duì)應(yīng)一個(gè)點(diǎn)坐標(biāo)（xi，yi，zi），如圖1（a）所示。xy 代表水平地理坐標(biāo)位置，z 代表地形地貌的高度（在柵格化的過程中對(duì)z 進(jìn)行取整），實(shí)際應(yīng)用中如果細(xì)化網(wǎng)格，將能逼近三維地形地貌。采取降維的思想，將三維地形表面分解為二維平面和高度變化的集合，從而簡(jiǎn)化三維空間的搜索難度，加快搜索能力?；疑碛懈叨刃畔⒌淖杂蓶鸥?，黑色代表障礙柵格，障礙物數(shù)目，位置，大小已知，離散化后將高度信息z 標(biāo)注于相應(yīng)柵格上，反應(yīng)機(jī)器人在經(jīng)過不同柵格時(shí)的高度變化，如圖1（b）所示。

圖1 建立的三維規(guī)劃空間Fig.1 The Established Three-Dimensional Planning Space

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

文獻(xiàn)[9]用柵格高度值代表能耗，對(duì)上下坡能耗變化不同未分類討論，有一定缺陷。在三維路徑規(guī)劃中實(shí)現(xiàn)的目標(biāo)有：在環(huán)境靜態(tài)、地圖有界、障礙物已知、起點(diǎn)和終點(diǎn)已知的條件下，機(jī)器人行走路徑長(zhǎng)度最短，上下坡總能耗最小，減少上下坡的起伏，且每條路徑都規(guī)避障礙物。

其中，gi路徑中第i 段相鄰兩點(diǎn)的能耗值，為了更加貼近真實(shí)設(shè)備上下坡所耗能量不同的狀況，將上坡和下坡進(jìn)行差異化分析，簡(jiǎn)單起見，文中只對(duì)上坡動(dòng)作和下坡動(dòng)作乘以不同的權(quán)重系數(shù)，考慮到下坡省力，上坡費(fèi)力，對(duì)上坡和下坡分段處理：

（4）障礙物的規(guī)避采用約束條件來表達(dá)，將障礙物點(diǎn)的集合記為O=（o1，o2，…ok）則規(guī)劃的路徑點(diǎn)pi不能取集合O 中的點(diǎn)，且線段pipi+1不能穿過點(diǎn)集O。

3 改進(jìn)NSGA-II 的多目標(biāo)路徑規(guī)劃

3.1 傳統(tǒng)多目標(biāo)遺傳算法

針對(duì)以上規(guī)劃空間及優(yōu)化目標(biāo)函數(shù)，選擇NSGA-II 算法來解決多目標(biāo)函數(shù)路徑優(yōu)化問題，對(duì)多目標(biāo)函數(shù)的優(yōu)化，傳統(tǒng)的遺傳算法是將多目標(biāo)函數(shù)加權(quán)組合成單目標(biāo)函數(shù)來處理，需要不斷調(diào)整權(quán)重參數(shù)來得到近似最優(yōu)解，往往不能很好地解決實(shí)際問題。智能的多目標(biāo)優(yōu)化算法是找到Pareto 占優(yōu)解，NSGA-II 算法是目前解決多目標(biāo)遺傳算法影響大，應(yīng)用范圍廣的優(yōu)化算法之一[10]，突出優(yōu)點(diǎn)是快速非支配排序的方法，且得到的解具有多樣性和均勻性。文獻(xiàn)[7-8]將NSGA-II 算法成功地應(yīng)用到了二維路徑規(guī)劃問題上，然而對(duì)三維柵格路徑規(guī)劃問題的應(yīng)用比較少。基于文獻(xiàn)[7-8]的研究成果，考慮路徑規(guī)劃結(jié)果的連續(xù)性，快速收斂性和Pareto 最優(yōu)，對(duì)NSGA-II 算法進(jìn)行改進(jìn)，改進(jìn)的遺傳算法包括以下編碼方式和遺傳算子的設(shè)計(jì)，其中在具有非支配排序的選擇算子中加入輔助決策算子及修正算子的設(shè)計(jì)頗為關(guān)鍵。

3.2 改進(jìn)NSGA-II 算法

3.2.1 編碼及初始種群的產(chǎn)生

m×m×m 規(guī)格地圖下，采用柵格序號(hào)編碼，并與坐標(biāo)法相結(jié)合。每一個(gè)柵格降維后分解為（xi，yi）和高度zi的集合。對(duì)降維后的空間從左到右，從下到上為每個(gè)柵格編號(hào)，每個(gè)坐標(biāo)（xi，yi）對(duì)應(yīng)一個(gè)編號(hào)N。

在初始種群生成時(shí)，對(duì)當(dāng)前柵格，有8 種可選擇的方向，當(dāng)柵格位于四頂角或者邊界時(shí)，可選擇的柵格分別為3 個(gè)和5 個(gè)。根據(jù)當(dāng)前點(diǎn)和目標(biāo)點(diǎn)的位置關(guān)系，對(duì)可供選擇的柵格，以概率隨機(jī)選擇一個(gè)自由柵格作為下個(gè)路徑點(diǎn)，以此直到到達(dá)路徑終點(diǎn)。用這種方式產(chǎn)生的初始種群保持了有效性，連續(xù)性和多樣性，而且避免了路徑反復(fù)出現(xiàn)和原地轉(zhuǎn)圈。

3.2.2 選擇算子

NSGA-II 算法的選擇算子采用精英策略，能很好地保持種群的多樣性，但存在如文獻(xiàn)[8]所證明的缺陷。當(dāng)有三個(gè)優(yōu)化目標(biāo)時(shí)，若第三個(gè)目標(biāo)函數(shù)不是絕對(duì)重要，將其中兩個(gè)目標(biāo)作為優(yōu)化函數(shù)，第三個(gè)目標(biāo)作為輔助選擇算子，所得到的優(yōu)化結(jié)果更能保持種群的多樣性，比三個(gè)目標(biāo)所得到的Pareto 前沿分布更優(yōu)[8]。建立的第二個(gè)目標(biāo)函數(shù)能耗最小可間接反映路徑的起伏，所以路徑起伏的優(yōu)化不是絕對(duì)重要的，對(duì)NSGA-II 選擇策略進(jìn)行了一定的修改：對(duì)于在選擇算子中比較的兩條路徑的優(yōu)先級(jí)時(shí)，先檢查相同級(jí)別的路徑對(duì)應(yīng)的高度值f3，其次再比較擁擠距離值。這樣得到的路徑既能保持路徑最短，又能減少爬坡起伏及控制爬坡高度。具體選擇關(guān)鍵過程為：

（1）種群Rt進(jìn)行非支配排序，求解出一系列非支配集Zi，計(jì)算個(gè)體擁擠度及適應(yīng)度f3；

（2）經(jīng)過非支配排序后的非支配集Z1所包含的個(gè)體是整個(gè)Rt中最好的個(gè)體，將Z1放到新的父代種群Pt+1中；

（3）判斷種群Pt+1的規(guī)模是否小于N，若是，則繼續(xù)向Pt+1中添加下一級(jí)的非支配集Z2，直到添加到非支配集Zn時(shí)，種群規(guī)模超出N，則對(duì)Zn中每個(gè)個(gè)體比較f3，使f3值小的優(yōu)先選擇，如果f3相等，再對(duì)Zn中每個(gè)個(gè)體比較擁擠度距離，使擁擠度距離高的種群獲勝，取前｛num（Zn）-（num（Pt+1）-N）｝個(gè)個(gè)體，使種群Pt+1規(guī)模達(dá)到N。

3.2.3 交叉、變異、刪除算子

選擇一點(diǎn)交叉方法，隨機(jī)選擇一個(gè)交叉點(diǎn)，交換掉兩個(gè)父代交叉點(diǎn)之后的路徑結(jié)點(diǎn)，產(chǎn)生新的子代。

在移動(dòng)機(jī)器人的路徑規(guī)劃中，產(chǎn)生的路徑均為連續(xù)路徑，出于防止高變異概率造成個(gè)體優(yōu)越性破壞和種群退化的目的，選擇很小的突變概率進(jìn)行擾動(dòng)，取pm=0.01。變異的過程為：隨機(jī)選擇一個(gè)變異位置，隨機(jī)產(chǎn)生一個(gè)無障礙柵格的編號(hào)，代替原來位置的編號(hào)。

刪除算子的作用是用來判斷所產(chǎn)生的路徑是否有環(huán)路，如果路徑產(chǎn)生的序號(hào)有重復(fù)的點(diǎn)，則刪除兩個(gè)重復(fù)點(diǎn)之間的所有路徑段及一個(gè)重復(fù)點(diǎn)。

3.2.4 修正算子

在NSGA-II 算法的基礎(chǔ)上，提出對(duì)路徑中對(duì)角，水平，垂直方向的修正算子，考慮生成的路徑產(chǎn)生如圖2 圈黑的非環(huán)路冗余，為了避免機(jī)器人繞路和能量的消耗，可用箭頭所指的兩個(gè)對(duì)角路徑點(diǎn)來代替?，F(xiàn)僅對(duì)對(duì)角修正算子作出說明。

圖2 對(duì)角冗余的修正算子示例Fig.2 An Example of a Modified Operator for Diagonal Redundancy

（1）路徑中隨機(jī)選擇一個(gè)狀態(tài)點(diǎn)pi；

（2）將pi的所有斜對(duì)角點(diǎn)記為Dpi；

（3）遍歷路徑中的點(diǎn)S；

（4）若S 在Dpi中，則移除S 和pii中所有的路徑點(diǎn)。

整個(gè)進(jìn)化過程，如圖3 所示。

圖3 算法流程圖Fig.3 The Flowchart of Algorithm

4 仿真分析

采用MATLAB 對(duì)上述算法進(jìn)行仿真測(cè)試，實(shí)驗(yàn)分別在柵格（10×10）規(guī)格，（20×20）規(guī)格環(huán)境測(cè)試，各個(gè)參數(shù)設(shè)定，如表1 所示。

表1 參數(shù)設(shè)置Tab.1 Preferences

4.1 修正算子有效性驗(yàn)證

實(shí)驗(yàn)在10×10 規(guī)格柵格環(huán)境下，忽略高度信息，只考慮路徑最短，建立二維路徑規(guī)劃問題來驗(yàn)證修正算子的有效性，參數(shù)設(shè)置如表1 中10×10 規(guī)格環(huán)境。兩種算法最優(yōu)路徑的收斂曲線對(duì)比，如圖4（a）所示。圖4（b）為兩種算法尋得的最優(yōu)路徑結(jié)果，不加入修正算子時(shí)在進(jìn)化第27 代達(dá)到收斂，而加入修正算子使算法在進(jìn)化第10 代達(dá)到了收斂，相比之下修正算子使迭代次數(shù)減少了約63%，加入修正算子能明顯提高算法的收斂性，驗(yàn)證了修正算子的有效性。

圖4 修正算子驗(yàn)證結(jié)果Fig.4 Results of Modify Operator Validation

4.2 10×10 規(guī)格地圖

加入高度信息，為了驗(yàn)證所提出改進(jìn)遺傳算法的有效性，與文獻(xiàn)[9]選擇相同的機(jī)器人工作環(huán)境。用提出的改進(jìn)的NSGA-II 算法來解決文獻(xiàn)[9]所構(gòu)造的規(guī)劃問題，參數(shù)設(shè)置如表1 中10×10 規(guī)格環(huán)境。改進(jìn)算法所得到的Pareto 前沿分布集，如圖5 所示?？梢钥闯?，改進(jìn)算法具有不同的Pareto 前沿解集。前沿集中的一個(gè)路徑和文獻(xiàn)[9]所得的最優(yōu)路徑結(jié)果對(duì)比，如圖6 所示。兩種算法所得到的最優(yōu)路徑信息對(duì)比，如表2 所示。兩種算法所得到的路徑長(zhǎng)度值相等時(shí)路徑所消耗的能量明顯低于文獻(xiàn)[9]，且得到的前沿路徑所有的能耗值均低于文獻(xiàn)[9]的最優(yōu)路徑能耗，如圖6 所示?？梢妼⒍嗄繕?biāo)加權(quán)處理成單目標(biāo)所得到的結(jié)果往往不能Pareto 占優(yōu)，且無法衡量結(jié)果是否最好。通過表2 發(fā)現(xiàn)得到的Pareto 前沿路徑在權(quán)衡能耗最小和路徑最短的條件下做出了很好的折中。

圖5 Pareto 前沿分布1Fig.5 Pareto Optimal Fronts Distribution 1

圖6 路徑結(jié)果對(duì)比Fig.6 Comparison of Routs

表2 兩種算法最優(yōu)解對(duì)比Tab.2 Comparison of Optimal Solutions Between Two Algorithms

4.3 20×20 規(guī)格地圖

在（2）的基礎(chǔ)上加大柵格環(huán)境和障礙物個(gè)數(shù)進(jìn)行仿真測(cè)試，參數(shù)設(shè)置如表1 中20×20 規(guī)格環(huán)境。結(jié)果顯示當(dāng)加大柵格數(shù)目時(shí)，算法依然能找到Pareto 最優(yōu)路徑，而且具有多個(gè)Pareto 前沿分布解，如圖7 所示。具有很好的實(shí)際應(yīng)用價(jià)值。前沿解集中的其中一個(gè)路徑結(jié)果，如圖8 所示。

圖7 Pareto 前沿分布2Fig.7 Pareto Optimal Fronts Distribution 2

圖8 路徑尋優(yōu)結(jié)果Fig.8 Result of Path Optimization

5 結(jié)論

針對(duì)有障礙的三維空間機(jī)器人路徑規(guī)劃問題考慮路徑最短，能耗最小，起伏最少，構(gòu)建了多目標(biāo)優(yōu)化函數(shù)，提出了一種改進(jìn)的NSGA-II 算法，對(duì)算例進(jìn)行優(yōu)化分析，結(jié)果表明：（1）修正算子的加入能有效提高最優(yōu)路徑的收斂代數(shù)，使迭代次數(shù)減少了約63%。（2）多目標(biāo)加權(quán)處理成單目標(biāo)得到的結(jié)果往往不能Pareto 占優(yōu)，且需要人為不斷調(diào)整權(quán)重，實(shí)用性不高。改進(jìn)的NSGA-II 算法具有多個(gè)Pareto 前沿分布解，且分布均勻，比傳統(tǒng)算法結(jié)果更占優(yōu)。（3）加大規(guī)劃空間規(guī)模和障礙物時(shí)改進(jìn)的算法依然能找到多個(gè)Pareto 最優(yōu)路徑，驗(yàn)證了算法在不同復(fù)雜度的環(huán)境均具有較好的適應(yīng)能力。