小生境遺傳算法的移動機器人路徑優(yōu)化技術(shù)

移動機器人路徑規(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)換的繁瑣操作，且易于進行遺傳算子操作。

1.3 種群初始化

執(zhí)行遺傳算法的最優(yōu)路徑設(shè)計是必須對種群進行初始化，由于初始路徑隨機產(chǎn)生，各轉(zhuǎn)向點坐標(biāo)可能分布在整個規(guī)劃區(qū)域范圍內(nèi)，包括可行的和不可行的，這樣便增加了搜索范圍。這里在可行區(qū)域內(nèi)限制初始轉(zhuǎn)向點，以加快遺傳算法的收斂速度。具體做法為：判斷該轉(zhuǎn)向點是否在可行區(qū)域內(nèi)，如果不是，則重新選取，直到坐標(biāo)點符合條件為止。

根據(jù)規(guī)劃環(huán)境的復(fù)雜度不同，最優(yōu)路徑中轉(zhuǎn)向點的個數(shù)也是不確定的，一般來說，環(huán)境越復(fù)雜，轉(zhuǎn)向點就越多，因此算法采用變長編碼技術(shù)，通過對染色體進行刪除、插入等操作，能夠確定合適的轉(zhuǎn)向點個數(shù)，使路徑達到最優(yōu)。但是，轉(zhuǎn)向點數(shù)目太多，占用資源也就會太大，它將使運算速度變慢。因此，在運算過程中，設(shè)定最大轉(zhuǎn)向點為N_max，種群中每個個體的長度n滿足2≤n≤N_max。

采用小生境原理，將每一代個體劃分為若干類，每個類中選出若干適應(yīng)度較大的個體，作為一個類的優(yōu)秀代表組成一個種群。

1.4?適應(yīng)度函數(shù)

所謂移動機器人的路徑規(guī)劃，指在起點和終點之間找出一條最短的可行路徑，其約束條件是不與障礙物相交，同時移動機器人在行走中的轉(zhuǎn)角不宜太大。該算法以兩個條件作為規(guī)劃路徑的可行性評價函數(shù)，即路徑總長度和各轉(zhuǎn)向點拐角的平均大小，對于不可行的路徑，對其適應(yīng)度進行懲罰，使它的適應(yīng)度差于可行路徑。

(1)路徑總長度。為了防止移動機器人與障礙物碰撞，應(yīng)盡量使其與障礙物保持一定的安全距離。假設(shè)移動機器人的安全半徑為r；移動機器人與障礙物的距離為d，則路徑總長度Len由式(1)計算：

式中：d(p_i-1，p_i)為轉(zhuǎn)向點p_i-1與p_i之間的長度。如果p_i-1與p_i之間的路徑不可行，則使用懲罰函數(shù)法對其適應(yīng)度進行懲罰。懲罰函數(shù)定義如下：



式中：ε為懲罰因子。路徑的評價函數(shù)可以寫為：


判斷兩點之間的路徑是否可行，只需判斷這兩點的連線與障礙物的各邊是否相交即可。根據(jù)幾何學(xué)原理，判斷兩條線段是否相交可由以下兩個步驟進行確定：快速排斥試驗；跨立試驗。鑒于文章篇幅，在此不再對這兩個試驗進行詳細闡述。

評價路徑是求路徑長度最短的問題，通過懲罰因子，可以使不可行路徑變長，從而降低它的適應(yīng)值。

(2)路徑平滑度。移動機器人的特點決定了它在行走過程中不宜以過大拐角進行轉(zhuǎn)向，因此整條行走路徑應(yīng)趨于平緩而光滑，即每一轉(zhuǎn)向點處的拐角值應(yīng)盡可能小。這里假設(shè)拐角最大值不能超過π／2，平滑度可以使用路徑的平均拐角值來計算：


式中：ξ為一個趨于零的常數(shù)(ξ>0)；α_i(0≤α_i≤π，i=2，3，…，n-1)表示兩向量AC，CB之間的夾角，B，C點的坐標(biāo)分別為(x_i-2，y_i-1)，(x_i，y_i)，(x_i-1，y_i-1)；k為α_i中大于或等于π／2的個數(shù)，即當(dāng)某一夾角大于或等于π／2時，對適應(yīng)度進行懲罰。當(dāng)n=2時，路徑為起始點與終止點的連線。若其可行，則M值趨于0?？梢钥闯?，M值越小，路徑的平滑度越好。

得到了以上兩個條件的評價函數(shù)，就可以獲得整條路徑的適應(yīng)度函數(shù)。采用各項評價函數(shù)加權(quán)求和是常用的確定適應(yīng)度函數(shù)的方法。因為各個加權(quán)系數(shù)不是恒定不變的，而是隨路徑和障礙物的情況變化而變化的，所以這種情況下各個加權(quán)系數(shù)就很難調(diào)整和確定。因此，在確定適應(yīng)度函數(shù)時，盡量使適應(yīng)度函數(shù)的項數(shù)最少，但又必須把路徑規(guī)劃的兩個條件融合在遺傳優(yōu)化過程中。這里采用評價函數(shù)相乘的形式，如式(6)所示。

f=1／(ML)??? (6)

以f作為選擇操作的依據(jù)，則路徑的長度和平均拐角越小，其適應(yīng)度越好。

1.5 遺傳算子

(1)選擇算子。使用錦標(biāo)賽選擇法和精英保留法相結(jié)合的選擇策略。采用在錦標(biāo)賽選擇法選擇時，先隨機在群體中選擇K個個體進行比較，適應(yīng)度最好的個體將被選擇作為生成下一代的父體，參數(shù)K稱為競賽規(guī)模。這種選擇方式能使種群中適應(yīng)度好的個體具有較大的“生存”機會。同時，由于它只使用適應(yīng)度的相對值作為選擇的標(biāo)準(zhǔn)，而與適應(yīng)度的數(shù)值大小不成直接比例，從而避免了超級個體的影響，在一定程度上避免了過早收斂和停滯現(xiàn)象的發(fā)生。精英保留法是當(dāng)前種群中適應(yīng)度最好的個體，它不參加遺傳操作，可直接復(fù)制到下一代，替換經(jīng)交叉和變異操作產(chǎn)生的子種群中適應(yīng)度最差的個體，其優(yōu)點是在搜索過程中可以使某一代最優(yōu)個體不被遺傳操作所破壞，這樣可保證遺傳算法以概率收斂到最優(yōu)解。經(jīng)驗證明，保留占種群總體2％～5％數(shù)量的個體，效果最為理想。

(2)交叉算子。采用單點交叉法，在兩個父體上分別隨機選取一個交叉點(起點和終點除外)，交換兩個個體在各自交叉點之后的染色體?？紤]到規(guī)劃路徑的長度是可變的，為了防止交叉操作后出現(xiàn)過于繁瑣或簡單的路徑，對生成的新個體長度進行限制，即最大長度不能超過Nmax，并且不能產(chǎn)生回路，若不符合要求，重新獲取兩個父個體的交叉點。

(3)插入算子。設(shè)計了兩種插入算子。第一種是有針對性的，即在連線穿過障礙物的兩個轉(zhuǎn)向點之間插入一個或多個轉(zhuǎn)向點，使產(chǎn)生的路徑避開障礙物，如圖1(a)所示；第二種是一般意義上的插入，以一定概率插入一個隨機產(chǎn)生的轉(zhuǎn)向點，如圖1(b)所示。

(4)擾動算子。同樣設(shè)計了兩種擾動算子，第一種只選取路徑不可行的轉(zhuǎn)向點來進行小范圍的調(diào)整，使其路徑可行，如圖1(c)所示；第二種是不管路徑是否可行，任意選取一個位置，以概率pm對其轉(zhuǎn)向點坐標(biāo)進行調(diào)整。在進化初期，不可行的解數(shù)量較多，調(diào)整的范圍大一些。在進化后期調(diào)整范圍逐漸縮小，如圖1(d)所示。



(5)刪除算子。建立一個存儲空間REC，在一條路徑中，如果點(x_i-1，y_i-1)與點(x_i，y_i)的連線經(jīng)過障礙物，但(x_i-1，y_i-1)與(x_i+1，y_i-1)的連線不經(jīng)過障礙物，則將點(x_i，y_i)添加到REC中。如果REC不為空，則從中隨機選取一點刪除(見圖1(e))；否則，在路徑中任意選取一個路徑點，以概率p_d進行刪除，如圖1(f)所示。

(6)平滑算子。平滑算子只對可行路徑中最大的拐角進行操作，如圖1(g)所示。刪除拐角α的頂點p_j，依次連接點p_j-1，p₁，p₂，p_j+1構(gòu)成可行路徑段序列p_j-1p₁→p₁p₂→p₂p_j+1。

(7)倒位算子。隨機選取路徑中兩個中間轉(zhuǎn)向點，顛倒之間的轉(zhuǎn)向點。倒位算子可使路徑發(fā)生急劇變化，對于轉(zhuǎn)向點較多的路徑會有積極的意義。通常的交叉和變異算子不易取得此種效果，而且倒位算子能修正遺傳進化過程中可能出現(xiàn)的基因誤差，如圖1(h)所示。

1.6 遺傳算子概率選擇

選擇合適的遺傳算子執(zhí)行概率是遺傳算法能否收斂到最優(yōu)解的關(guān)鍵之一。在進化過程的前期，群體中存在大量的不可行解，因而交叉算子、擾動算子的概率應(yīng)該取得較大些，而平滑算子取較小的概率；隨著進化過程的推進，可行解增多，應(yīng)適當(dāng)提高平滑算子的概率，以提高可行解的平滑性能。同時，為了防止交叉算子和擾動算子對可行解的破壞，需降低其執(zhí)行概率，并取較小的擾動概率對可行解的形狀進行微調(diào)。其中，擾動算子(1)和插入算子(1)是對路徑轉(zhuǎn)向點的啟發(fā)式操作，都是針對不可行路徑的優(yōu)化調(diào)整，對于這些算子應(yīng)當(dāng)始終選擇較高的概率。插入算子(2)會使路徑的轉(zhuǎn)向點數(shù)量增加，應(yīng)當(dāng)取較小的概率。

1.7 終止條件

一般在對問題無知的情況下，可以在目標(biāo)函數(shù)達到一個可以承受的范圍內(nèi)之后，即終止算法。另外，還可設(shè)置最大進化代數(shù)，在給定的進化代數(shù)之內(nèi)強行終止算法，從而保證運算時間的要求。為了實用起見，在此采取最大進化代數(shù)終止準(zhǔn)則，并選取適應(yīng)度最好的可行路徑。

1.8?算法流程

改進后的基于小生境遺傳算法流程如圖2所示。具體算法描述如下：

(1)初始化種群，沿起點和終點連線方向等距離選取N個點，在這些點的垂直線上隨機選取轉(zhuǎn)向點的縱坐標(biāo)，并且使這些轉(zhuǎn)向點不在障礙物內(nèi)；

(2)將每一代個體劃分為n個類，每個類中選出若干適應(yīng)度較大的個體，作為一個類的優(yōu)秀代表，組成一個種群。種群規(guī)模Gi(i=1，2，…，n+1)；

(3)計算種群中所有個體的適應(yīng)度，將其最好的個體保留，然后采用錦標(biāo)賽選擇法，挑選父個體，以執(zhí)行交叉操作，并且檢查獲得的子代個體染色體長度是否超過N，如果沒有超過，則保留，否則丟棄。

(4)以設(shè)定的概率對新產(chǎn)生的子代個體進行變異、插入、擾動、刪除、平滑的操作。此過程中，采取預(yù)選擇機制，比較子串和父串適應(yīng)度的大小，如果子串的適應(yīng)度高于父串的適應(yīng)度，就替換父串；否則維持父串不變；

(5)重復(fù)第(3)和第(4)步直到獲得的新個體數(shù)量與父代群體數(shù)量相等；

(6)用保留的上一代最優(yōu)個體替換新種群中適應(yīng)度最差的個體；

(7)檢查算法停止條件。符合則中止，否則跳轉(zhuǎn)至第(3)步，算法繼續(xù)進行。

2 仿真

移動機器人最優(yōu)路徑規(guī)劃設(shè)計的環(huán)境信息主要包括移動機器人活動區(qū)域內(nèi)的各種障礙物信息識別。本文視各種障礙物都為不可行區(qū)域，并以任意形狀的多邊形來表示。在VC 2005環(huán)境中，對以上算法進行仿真。選取算法參數(shù)為路徑最大轉(zhuǎn)向點數(shù)30，初始轉(zhuǎn)向點數(shù)20，種群大小100，錦標(biāo)賽規(guī)模取5，最大進化代數(shù)G=80。在算法的前20代中，交叉概率p_c=0.6，擾動概率p_m=0.6，插入算子2p_i=0.6，平滑算子概率p_s=0.1；在20代以后p_c=0.1，p_m=0.2，p_i=0.01，p_s=0.7。

在算法的初始階段，由于轉(zhuǎn)向點較多，因此刪除概率應(yīng)當(dāng)取大一些，這樣可以使轉(zhuǎn)向點數(shù)量減少，從而縮小路徑的長度；但在算法后期，路徑點已經(jīng)較少，再使用較大的刪除概率，容易使算法陷入局部解，且收斂到最優(yōu)解的概率大大減少，因此進化后期的刪除概率應(yīng)減少，保證路徑的多樣性。初始刪除概率選0.8，大約20代以后，選取0.1，而擾動算子1和插入算子1的概率始終為0.8。選取兩種不同的環(huán)境(見圖3)，分別運行上述算法各10次，選出效果最好的路徑顯示在圖3(a)、圖3(b)中。從圖3中可以看出，改進后的遺傳算法對各種環(huán)境都有良好的適應(yīng)性。其中，圖3(a)的情況最簡單，只用了19代就得到了最優(yōu)結(jié)果；圖3(b)進化了36代后；收斂到最優(yōu)解。



為了與標(biāo)準(zhǔn)遺傳算法的性能進行對比，分別使用本文算法和標(biāo)準(zhǔn)遺傳算子對環(huán)境一和二進行實驗。標(biāo)準(zhǔn)遺傳算法的選擇采用錦標(biāo)賽選擇法，其交叉概率、變異概率與本文算法相同，運行結(jié)果如表1和表2所示。



從表1，表2中數(shù)據(jù)可以看出，不管是運行時間，還是收斂的路徑長度，本文算法都優(yōu)于標(biāo)準(zhǔn)遺傳算法。主要是由于本文算法針對規(guī)劃路徑有針對性地設(shè)計了新的遺傳算子，從而加快了進化的速度，更容易收斂到最優(yōu)解。

3 結(jié)? 語

采用基于預(yù)選擇機制的小生境技術(shù)，且基于啟發(fā)式知識來設(shè)計遺傳算子。對標(biāo)準(zhǔn)遺傳算法進行了改進和擴充，并應(yīng)用于移動機器人行走的路徑規(guī)劃。該算法同時兼顧了遺傳進化的快速性和群體的多樣性，有效地抑制了“早熟”現(xiàn)象的發(fā)生，能很好地搜索局部最優(yōu)解和全局最優(yōu)解。實驗證明，該算法在不同的環(huán)境中都能夠在較小的進化代數(shù)內(nèi)收斂到最優(yōu)解，算法的執(zhí)行速度和成功率明顯高于標(biāo)準(zhǔn)的遺傳算法。另外，在進化的不同階段選取合適的交叉和變異概率對于進化結(jié)果有著關(guān)鍵性的影響，本文將算法分成了兩個階段，分別設(shè)定了不同的遺傳操作概率，這種方式還比較簡單，不能完全適應(yīng)種群的變化情況。如何讓算法根據(jù)種群進化情況自動調(diào)整和優(yōu)化這些參數(shù)，還需進一步的研究和改進。