周蘭鳳 楊麗娜 方 華

(上海應(yīng)用技術(shù)大學(xué) 上海 201418)

0 引 言

月球車作為探測月球的主要工具之一，它最重要的任務(wù)就是月球路徑規(guī)劃[1]。月球環(huán)境復(fù)雜多樣使月球車路徑規(guī)劃十分困難，有效地避免陷入危險地形、縮短最優(yōu)路徑長度和節(jié)約路徑規(guī)劃時間是月球路徑規(guī)劃研究的重點。月球地形的濕度和坡度的不同，產(chǎn)生的滑移率不同，一定程度使路徑規(guī)劃產(chǎn)生偏移，有效的預(yù)測滑移有利于找到最短最優(yōu)路徑。既包含傳統(tǒng)的算法(A*算法[2]，遺傳算法[3])，也帶有一些新型的智能算法(蟻群算法[4]，神經(jīng)網(wǎng)絡(luò)算法[5]，粒子群算法[6])，經(jīng)典遺傳算法存在搜索時間長、易陷入僵局、算法復(fù)雜度高的不足，無法求得最優(yōu)化路徑。

本文針對現(xiàn)有的遺傳算法容易陷入局部最優(yōu)解的問題，綜合考慮月球地形環(huán)境信息，通過加入地形因素的滑移預(yù)測綜合通過性代價函數(shù)。使用MATLAB仿真實驗，保持地形參數(shù)不變，調(diào)整滑移通過性函數(shù)參數(shù)，對比100次實驗仿真結(jié)果，綜合遺傳算法進化代數(shù)少于傳統(tǒng)遺傳算法。改進后的遺傳算法提高了月球車路徑規(guī)劃的平滑性，縮短了路徑的長度，節(jié)省了路徑規(guī)劃的時間和進化次數(shù)。

1 綜合遺傳算法

1.1 遺傳算法路徑規(guī)劃模型建立

本文遺傳編碼采用實數(shù)編碼，遺傳算法中每1個染色體對應(yīng)1個解決方案，在路徑規(guī)劃過程中，基因是由起點、終點和路徑規(guī)劃經(jīng)過的若干中間點組成。如圖1所示，起點(X1,Y1,Z1)、終點(Xn,Yn,Zn)和n-2個中間點構(gòu)成1條攜帶從起點到目標(biāo)點的路徑規(guī)劃信息的染色體。

圖1 路徑規(guī)劃中有n個基因的1條染色體

因此，一條完整的機器人路徑(P)就可以表示為若干條線段的有序組合，如下式所示：

P=∑Pi

(1)

式中：Pi表示第i段直線段的矢量表示。

1.2 初始種群的生成

本文中一條染色體由n個坐標(biāo)點組成，即一條可通過性的路徑，也稱這個路徑為一條染色體。從起點出發(fā)，隨機選擇可通過性的鄰節(jié)點，取其坐標(biāo)加入染色體中，依次循環(huán)，直到找到終點結(jié)束。重復(fù)上面操作，達到初始目標(biāo)種群數(shù)量，終止循環(huán)。

1.3 遺傳操作

遺傳算法是一種仿生的全局優(yōu)化概率搜索的自適應(yīng)算法[7]。其算法結(jié)構(gòu)設(shè)計需要預(yù)設(shè)的參數(shù)有：初始種群數(shù)量、最大進化迭代數(shù)、交叉概率和變異概率等。 算法過程包括選擇、交叉、變異三個階段。將遺傳算法應(yīng)用到路徑規(guī)劃規(guī)程的問題中，固定參數(shù)的交叉概率和變異概率適應(yīng)算法可以更好地找到最優(yōu)路徑[8]，通過不斷的迭代，最終得到問題最優(yōu)解。

本算法采用優(yōu)勝劣汰選擇策略，即用部分優(yōu)秀個體，根據(jù)一定策略實時替換部分低劣個體[9]，保持個體的最優(yōu)化。

(1) 交叉操作是遺傳學(xué)中基因重組的重要過程，也是遺傳算法產(chǎn)生新個體的重要途徑[10]。本文采用部分映射方式進行染色體的交叉操作，生成兩個隨機數(shù)m、n，將x、y染色體位于m和n之間的基因片段互換。交叉概率公式為：

(2)

式中：Pc表示動態(tài)路徑規(guī)劃中交叉概率；Pcmax表示交叉概率的最大值；Pcmin表示交叉概率的最小值；Fmax表示最大適應(yīng)度值；Fmin表示最小適應(yīng)度值；Fc表示兩個要交叉?zhèn)€體中較大的適應(yīng)度值。

(2) 變異操作類似遺傳學(xué)中的基因突變，更新過程中一條染色體上的點坐標(biāo)發(fā)生隨機變化，即產(chǎn)生變異個體。變異概率公式為：

(3)

式中：Pm表示動態(tài)路徑規(guī)劃中變異概率；Pmmax表示變異率的最大值；Pmmin表示變異概率的最小值；Fmax表示最大適應(yīng)度值；Fmin表示最小適應(yīng)度值；Fm表示要變異個體的適應(yīng)度值。

2 適應(yīng)度函數(shù)設(shè)計

適應(yīng)度函數(shù)作為評判種群中個體的存活率的標(biāo)準(zhǔn)之一，依據(jù)目標(biāo)函數(shù)而確定，路徑規(guī)劃過程中，適應(yīng)度函數(shù)的值越大越好。在本文路徑規(guī)劃中路徑最短和進化代數(shù)最小是首要目標(biāo)。除此之外，本文還加入了地形評估綜合通過性代價函數(shù)。地形評估綜合通過性代價函數(shù)是綜合了地形的一些主要因素，如階梯障礙、地形粗糙程度、坡度等，同時還加入了最主要的滑移因素，從而在滑移預(yù)測的基礎(chǔ)上形成了地形評估綜合通過性代價函數(shù)。該函數(shù)可以準(zhǔn)確描述地形上兩點之間的綜合通過能力。這里將上述地形評估綜合通過性代價函數(shù)f(p,n)，并入遺傳算法的適應(yīng)度函數(shù)，采用綜合遺傳算法進行路徑規(guī)劃。

設(shè)置節(jié)點p到節(jié)點n的基因片段的地形綜合代價函數(shù)如下：

f(p,n)=f1×ftrav(p,n)+f2×frisky(p,n)+

f3×fguide(p,n)+f4×fsmooth(p,n)

(4)

式中：ftrav(p,n)為從節(jié)點p到節(jié)點n的可通過性代價函數(shù)(一般取值為0或1)；frisky(p,n)為潛在危險性代價函數(shù)；fguide(p,n)為綜合考慮了地形的角度和坡度等因素的指導(dǎo)性路徑代價函數(shù)，它與地形的坡度角度有關(guān)；fsmooth(p,n)是描述路徑平滑程度的代價函數(shù)，取值為固定常數(shù)值f1、f2、f3、f4分別為ftrav(p,n)、frisky(p,n)、fguide(p,n)和fsmooth(p,n)的權(quán)值，一般將它們?nèi)橥还潭ǖ某?shù)值。

綜上，在滑移預(yù)測的基礎(chǔ)上形成了地形評估綜合通過性代價函數(shù)f(p,n)，將它與遺傳算法融合，改變其適應(yīng)度函數(shù)，構(gòu)造成一個具有滑移預(yù)測地形評估綜合通過性代價的適應(yīng)度函數(shù)f′(p,n)，本文稱為綜合適應(yīng)度函數(shù)，公式如下：

f′(p,n)=f(p,n)+f0(p,n)

(5)

式中：f′(p,n)為綜合遺傳算法的函數(shù)的適應(yīng)度函數(shù)；f(p,n)地形綜合代價函數(shù)；f0(p,n)基于遺傳算法適應(yīng)度函數(shù)。

3 仿真實驗

基于MATLAB 2014環(huán)境下建立虛擬三維地形環(huán)境，虛擬三維空間抽象為網(wǎng)格或柵格，然后設(shè)置參數(shù)，如路徑中的起點、終點、高度以及初始種群的數(shù)量。本次實驗設(shè)置種群個數(shù)30，最大進化迭代次數(shù)200。從圖2可以看出，該三維遺傳算法路徑規(guī)劃，比二維的柵格模型更直觀有效。

圖2 基于遺傳算法的三維模型路徑規(guī)劃圖

3.1 遺傳算法與綜合遺傳算法實驗對比

本文遺傳算法和綜合遺傳算法(簡稱IGA)一次進化代數(shù)及綜合適應(yīng)度變化圖如圖3、圖4所示。從圖3可以看出，基本遺傳算法進化到10代左右就進入了局部最優(yōu)解，50代之后更新最優(yōu)解，140代得到1次實驗最優(yōu)解，綜合適應(yīng)度值為130。從圖4可以看出，進化代數(shù)20次時得到1次試驗最優(yōu)解，綜合適應(yīng)度值為125，一定程度上縮短了路徑規(guī)劃時間，提高了工作效率。

圖3 遺傳算法

圖4 綜合遺傳算法

為了進一步證明算法的合理性，規(guī)避偶然因素對算法的影響，對兩種路徑規(guī)劃算法分別實驗100次，統(tǒng)計實驗結(jié)果如表1所示?？梢钥闯?，綜合遺傳算法的平均最大路徑比遺傳算法最大路徑縮短了34.7%、平均適應(yīng)度值提高了12.4%、平均進化代數(shù)縮小了49.2%。

3.2 改進蟻群算法與綜合遺傳算法對比

通過設(shè)置相同參數(shù)的滑移預(yù)測函數(shù)和地形通過性代價函數(shù)，使用改進蟻群算法和綜合遺傳算法各實驗n次，各隨機抽取兩種算法的6次試驗進行對比，結(jié)果如表2所示。

表2 兩種算法的最大路徑長度比較 km

可以看出，綜合遺傳算法比改進蟻群算法在最大路徑長度性能更加優(yōu)化。

綜合兩個實驗得知，通過引入帶有滑移預(yù)測函數(shù)可通過性的代價函數(shù)，使得算法在尋找路徑的過程中，更加注重路徑的曲折性且避免機器人搜索產(chǎn)生無效的移動距離。由表1可以看出，綜合遺傳算法在找到最優(yōu)的路徑的時間效率上也得到了一定的改善。因為在考慮了滑移預(yù)測的地形可通過性函數(shù)的基礎(chǔ)上，綜合遺傳算法路徑規(guī)劃的搜索能力更加優(yōu)化，不會在一些不合理的路徑上繼續(xù)進行后續(xù)的搜索。

4 結(jié) 語

由于遺傳算法應(yīng)用在路徑規(guī)劃問題上，存在諸多問題，如收斂效率低、陷入局部最優(yōu)解、復(fù)雜度高等，引入了地形綜合代價函數(shù)進行適應(yīng)度函數(shù)設(shè)計，根據(jù)綜合適應(yīng)度值動態(tài)獲得交叉算子和變異算子值，提出了一種綜合遺傳算法路徑規(guī)劃算法。通過實驗仿真得知, 改進的綜合遺傳算法在搜索最優(yōu)路徑、時間復(fù)雜度上比傳統(tǒng)遺傳算法都有了更好的優(yōu)化。這也說明本文在算法上的創(chuàng)新應(yīng)用，在某種程度上彌補了傳統(tǒng)遺傳算法的缺點。加入可通過性滑移預(yù)測算法的遺傳算法，為月球車避障提供有效方法，一定程度上提高了路徑搜索的效率、節(jié)約了時間成本、規(guī)避了地形風(fēng)險。