(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ù)，還需進一步的研究和改進。