(解放軍91635部隊(duì)  北京  102249)

0 引  言

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

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

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

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

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

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

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

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

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

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

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

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

1.2 路徑編碼

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

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