基于小生境遺傳算法的移動機(jī)器人路徑優(yōu)化
加入技術(shù)交流群
(6)平滑算子。平滑算子只對可行路徑中最大的拐角進(jìn)行操作，如圖1(g)所示。刪除拐角α的頂點(diǎn)pj，依次連接點(diǎn)pj-1，p1，p2，pj+1構(gòu)成可行路徑段序列pj-1p1→p1p2→p2pj+1。
(7)倒位算子。隨機(jī)選取路徑中兩個中間轉(zhuǎn)向點(diǎn)，顛倒之間的轉(zhuǎn)向點(diǎn)。倒位算子可使路徑發(fā)生急劇變化，對于轉(zhuǎn)向點(diǎn)較多的路徑會有積極的意義。通常的交叉和變異算子不易取得此種效果，而且倒位算子能修正遺傳進(jìn)化過程中可能出現(xiàn)的基因誤差，如圖1(h)所示。
1.6 遺傳算子概率選擇
選擇合適的遺傳算子執(zhí)行概率是遺傳算法能否收斂到最優(yōu)解的關(guān)鍵之一。在進(jìn)化過程的前期，群體中存在大量的不可行解，因而交叉算子、擾動算子的概率應(yīng)該取得較大些，而平滑算子取較小的概率；隨著進(jìn)化過程的推進(jìn)，可行解增多，應(yīng)適當(dāng)提高平滑算子的概率，以提高可行解的平滑性能。同時，為了防止交叉算子和擾動算子對可行解的破壞，需降低其執(zhí)行概率，并取較小的擾動概率對可行解的形狀進(jìn)行微調(diào)。其中，擾動算子(1)和插入算子(1)是對路徑轉(zhuǎn)向點(diǎn)的啟發(fā)式操作，都是針對不可行路徑的優(yōu)化調(diào)整，對于這些算子應(yīng)當(dāng)始終選擇較高的概率。插入算子(2)會使路徑的轉(zhuǎn)向點(diǎn)數(shù)量增加，應(yīng)當(dāng)取較小的概率。
1.7 終止條件
一般在對問題無知的情況下，可以在目標(biāo)函數(shù)達(dá)到一個可以承受的范圍內(nèi)之后，即終止算法。另外，還可設(shè)置最大進(jìn)化代數(shù)，在給定的進(jìn)化代數(shù)之內(nèi)強(qiáng)行終止算法，從而保證運(yùn)算時間的要求。為了實(shí)用起見，在此采取最大進(jìn)化代數(shù)終止準(zhǔn)則，并選取適應(yīng)度最好的可行路徑。
1.8算法流程
改進(jìn)后的基于小生境遺傳算法流程如圖2所示。具體算法描述如下：
(1)初始化種群，沿起點(diǎn)和終點(diǎn)連線方向等距離選取N個點(diǎn)，在這些點(diǎn)的垂直線上隨機(jī)選取轉(zhuǎn)向點(diǎn)的縱坐標(biāo)，并且使這些轉(zhuǎn)向點(diǎ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)生的子代個體進(jìn)行變異、插入、擾動、刪除、平滑的操作。此過程中，采取預(yù)選擇機(jī)制，比較子串和父串適應(yīng)度的大小，如果子串的適應(yīng)度高于父串的適應(yīng)度，就替換父串；否則維持父串不變；
(5)重復(fù)第(3)和第(4)步直到獲得的新個體數(shù)量與父代群體數(shù)量相等；
(6)用保留的上一代最優(yōu)個體替換新種群中適應(yīng)度最差的個體；
(7)檢查算法停止條件。符合則中止，否則跳轉(zhuǎn)至第(3)步，算法繼續(xù)進(jìn)行。
2 仿真
移動機(jī)器人最優(yōu)路徑規(guī)劃設(shè)計的環(huán)境信息主要包括移動機(jī)器人活動區(qū)域內(nèi)的各種障礙物信息識別。本文視各種障礙物都為不可行區(qū)域，并以任意形狀的多邊形來表示。在VC 2005環(huán)境中，對以上算法進(jìn)行仿真。選取算法參數(shù)為路徑最大轉(zhuǎn)向點(diǎn)數(shù)30，初始轉(zhuǎn)向點(diǎn)數(shù)20，種群大小100，錦標(biāo)賽規(guī)模取5，最大進(jìn)化代數(shù)G=80。在算法的前20代中，交叉概率pc=0.6，擾動概率pm=0.6，插入算子2pi=0.6，平滑算子概率ps=0.1；在20代以后pc=0.1，pm=0.2，pi=0.01，ps=0.7。
在算法的初始階段，由于轉(zhuǎn)向點(diǎn)較多，因此刪除概率應(yīng)當(dāng)取大一些，這樣可以使轉(zhuǎn)向點(diǎn)數(shù)量減少，從而縮小路徑的長度；但在算法后期，路徑點(diǎn)已經(jīng)較少，再使用較大的刪除概率，容易使算法陷入局部解，且收斂到最優(yōu)解的概率大大減少，因此進(jìn)化后期的刪除概率應(yīng)減少，保證路徑的多樣性。初始刪除概率選0.8，大約20代以后，選取0.1，而擾動算子1和插入算子1的概率始終為0.8。選取兩種不同的環(huán)境(見圖3)，分別運(yùn)行上述算法各10次，選出效果最好的路徑顯示在圖3(a)、圖3(b)中。從圖3中可以看出，改進(jìn)后的遺傳算法對各種環(huán)境都有良好的適應(yīng)性。其中，圖3(a)的情況最簡單，只用了19代就得到了最優(yōu)結(jié)果；圖3(b)進(jìn)化了36代后；收斂到最優(yōu)解。
為了與標(biāo)準(zhǔn)遺傳算法的性能進(jìn)行對比，分別使用本文算法和標(biāo)準(zhǔn)遺傳算子對環(huán)境一和二進(jìn)行實(shí)驗(yàn)。標(biāo)準(zhǔn)遺傳算法的選擇采用錦標(biāo)賽選擇法，其交叉概率、變異概率與本文算法相同，運(yùn)行結(jié)果如表1和表2所示。
從表1，表2中數(shù)據(jù)可以看出，不管是運(yùn)行時間，還是收斂的路徑長度，本文算法都優(yōu)于標(biāo)準(zhǔn)遺傳算法。主要是由于本文算法針對規(guī)劃路徑有針對性地設(shè)計了新的遺傳算子，從而加快了進(jìn)化的速度，更容易收斂到最優(yōu)解。
3 結(jié) 語
采用基于預(yù)選擇機(jī)制的小生境技術(shù)，且基于啟發(fā)式知識來設(shè)計遺傳算子。對標(biāo)準(zhǔn)遺傳算法進(jìn)行了改進(jìn)和擴(kuò)充，并應(yīng)用于移動機(jī)器人行走的路徑規(guī)劃。該算法同時兼顧了遺傳進(jìn)化的快速性和群體的多樣性，有效地抑制了“早熟”現(xiàn)象的發(fā)生，能很好地搜索局部最優(yōu)解和全局最優(yōu)解。實(shí)驗(yàn)證明，該算法在不同的環(huán)境中都能夠在較小的進(jìn)化代數(shù)內(nèi)收斂到最優(yōu)解，算法的執(zhí)行速度和成功率明顯高于標(biāo)準(zhǔn)的遺傳算法。另外，在進(jìn)化的不同階段選取合適的交叉和變異概率對于進(jìn)化結(jié)果有著關(guān)鍵性的影響，本文將算法分成了兩個階段，分別設(shè)定了不同的遺傳操作概率，這種方式還比較簡單，不能完全適應(yīng)種群的變化情況。如何讓算法根據(jù)種群進(jìn)化情況自動調(diào)整和優(yōu)化這些參數(shù)，還需進(jìn)一步的研究和改進(jìn)。
評論