(解放軍91635部隊  北京  102249)

0 引  言

移動機器人路徑規(guī)劃是機器人學(xué)的一個重要研究領(lǐng)域，也是人工智能與機器人學(xué)的一個結(jié)合點。不論是哪種類別的移動機器人，都要求根據(jù)某一準(zhǔn)則(如行走路線總長度最短，能量消耗最少等)，在工作空間中沿一條最優(yōu)(或次優(yōu))的路徑行走。

路徑規(guī)劃的典型方法有圖搜索法、柵格法、人工勢場法等，這些算法都有一定局限性，易陷入局部最優(yōu)解，而遺傳算法在解決非線性問題上具有良好的適用性，已成為路徑規(guī)劃中使用較多的一種方法。但是標(biāo)準(zhǔn)的遺傳算法本身也存在著早熟，易陷入局部最優(yōu)解等缺陷，不能保證對路徑規(guī)劃上計算效率和可靠性的要求。為了提高路徑規(guī)劃的求解質(zhì)量和求解效率，提出一種基于預(yù)選擇機制小生境技術(shù)的改進遺傳算法，并將其應(yīng)用于移動機器人的路徑規(guī)劃，采用化復(fù)雜的二維坐標(biāo)為一維坐標(biāo)的編碼方式，有效降低了遺傳算法的搜索空間；根據(jù)移動機器人的行走特點，設(shè)計了自適應(yīng)交叉算子、自適應(yīng)變異算子、插入算子、刪除算子、擾動算子和倒位算子。通過計算機仿真證明了改進后的遺傳算法明顯提高了搜索效率和收斂速度，并能保證收斂到全局最優(yōu)解，克服了標(biāo)準(zhǔn)遺傳算法的缺點，為機器人快速尋求一條無碰的最優(yōu)路徑。

1 基于遺傳算法的機器人路徑規(guī)劃算法的改進與應(yīng)用

本文的移動機器人路徑規(guī)劃，目標(biāo)是在一幅已知障礙物分布的二維地圖上尋找一條最優(yōu)路徑，使其到達目標(biāo)點的距離最短，同時盡可能地使其與障礙物的距離最大化。為了簡化討論，將移動機器考慮為一個質(zhì)點，而障礙物的邊界向外擴張，這是移動機器人的最大安全距離。

1.1 基于預(yù)選擇機制技術(shù)的小生境遺傳算法機理

由于簡單遺傳算法是一種隨機的方法，旨在對多個不同的個體進行隱并行尋優(yōu)，其運行過程和實現(xiàn)方法在本質(zhì)上仍是串行的，這樣的進化運算過程相對緩慢；同時，基本遺傳算法常在各個個體未達到最優(yōu)解之前就收斂于一個局部最優(yōu)點，從而導(dǎo)致染色體趨于一致，即產(chǎn)生“早熟”現(xiàn)象。為了克服這些不足，引入了小生境遺傳機理，用基于預(yù)選擇機制技術(shù)的小生境方法維持群體的多樣性，避免群體內(nèi)個別個體的大量增加，實現(xiàn)解空間內(nèi)對局部最優(yōu)解和全局最優(yōu)解的尋優(yōu)。

小生境技術(shù)就是將每一代個體劃分為若干類，每個類中選出若干適應(yīng)度較大的個體作為一個類的優(yōu)秀代表組成一個種群，再在種群中以及不同種群之間，通過雜交、變異產(chǎn)生新一代個體群，同時采用預(yù)選擇機制完成選擇操作?；谶@種小生境技術(shù)的遺傳算法，可以更好地保持解的多樣性，同時具有很高的全局尋優(yōu)能力和收斂速度。

在預(yù)選擇機制中，只有在子串的適應(yīng)度超過其父串的情況下，子串才能替換其父串，進入下一代群體。這種方式趨向于替換與其本身相似的個體(父與子之間的性狀遺傳)，因而能夠較好地維持群體的分布特性，即使在群體規(guī)模相對較小的情況下，仍可維持較高的群體分布特性。具體算法的實現(xiàn)步驟如下：

(1)初始化(建立初始群體，確定遺傳參數(shù))；

(2)計算個體的適應(yīng)度；
   
(3)遺傳操作(選擇、交叉、變異)；

(4)比較子串和父串的適應(yīng)度大小，如果子串的適應(yīng)度高于父串的適應(yīng)度，就替換父串；否則維持父串不變；

(5)如果沒有滿足算法的終止條件，則返回第(2)步；否則，算法終止。

1.2 路徑編碼

基因的編碼方式確定了問題在遺傳算法中的表現(xiàn)形式，也決定了所采用的遺傳進化操作。每個染色體表示為給定符號集中的字符組成基因串。在早期的遺傳算法中，符號集僅限于二進制數(shù)，因此遺傳基因型是一個二進制符號串，其優(yōu)點在于編碼、解碼的操作簡單，交叉、變異等的遺傳操作便于實現(xiàn)；缺點是不便反映所求問題的特定知識，以及對一些連續(xù)函數(shù)的優(yōu)化問題等。由于遺傳算法的隨機特性使得其局部搜索能力較差，對于一些要求多維、高精度的連續(xù)函數(shù)優(yōu)化，二進制編碼存在連續(xù)函數(shù)離散化時的映射誤差，當(dāng)個體編碼串較短時，可能達不到精度要求；當(dāng)個體編碼串較長時，雖然能提高精度，但卻會使算法的搜索空間急劇增大。

實數(shù)編碼適用于表示范圍大、精度高的數(shù)，能有效地克服二進制編碼的海明懸崖缺點，且可直接采用真值編碼，便于與問題相關(guān)的啟發(fā)知識，可以提高算法的搜索效率。移動機器人的路徑可以視為一系列坐標(biāo)點連接而成的線段，對移動機器人的路徑規(guī)劃也就是對這些坐標(biāo)點做各種操作，以使它們符合移動機器人行走的需要?？紤]到移動機器人自身的特點(不僅需要避開障礙物，還要保證路徑的平滑性)，以及移動機器人路徑中轉(zhuǎn)向點個數(shù)的不確定性，采用可變長染色體的實數(shù)編碼方式，用實數(shù)直接對路徑坐標(biāo)點進行編碼，以便于對路徑點的靈活操作，從而避免在使用二進制編碼時，二進制位串與直角坐標(biāo)點之間互相轉(zhuǎn)換的繁瑣操作，且易于進行遺傳算子操作。