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

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

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

2 仿真

移動(dòng)機(jī)器人最優(yōu)路徑規(guī)劃設(shè)計(jì)的環(huán)境信息主要包括移動(dòng)機(jī)器人活動(dòng)區(qū)域內(nèi)的各種障礙物信息識(shí)別。本文視各種障礙物都為不可行區(qū)域，并以任意形狀的多邊形來(lái)表示。在VC 2005環(huán)境中，對(duì)以上算法進(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代中，交叉概率p_c=0.6，擾動(dòng)概率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)向點(diǎn)較多，因此刪除概率應(yīng)當(dāng)取大一些，這樣可以使轉(zhuǎn)向點(diǎn)數(shù)量減少，從而縮小路徑的長(zhǎng)度；但在算法后期，路徑點(diǎn)已經(jīng)較少，再使用較大的刪除概率，容易使算法陷入局部解，且收斂到最優(yōu)解的概率大大減少，因此進(jìn)化后期的刪除概率應(yīng)減少，保證路徑的多樣性。初始刪除概率選0.8，大約20代以后，選取0.1，而擾動(dòng)算子1和插入算子1的概率始終為0.8。選取兩種不同的環(huán)境(見(jiàn)圖3)，分別運(yùn)行上述算法各10次，選出效果最好的路徑顯示在圖3(a)、圖3(b)中。從圖3中可以看出，改進(jìn)后的遺傳算法對(duì)各種環(huán)境都有良好的適應(yīng)性。其中，圖3(a)的情況最簡(jiǎn)單，只用了19代就得到了最優(yōu)結(jié)果；圖3(b)進(jìn)化了36代后；收斂到最優(yōu)解。



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



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

3 結(jié)  語(yǔ)

采用基于預(yù)選擇機(jī)制的小生境技術(shù)，且基于啟發(fā)式知識(shí)來(lái)設(shè)計(jì)遺傳算子。對(duì)標(biāo)準(zhǔn)遺傳算法進(jìn)行了改進(jìn)和擴(kuò)充，并應(yīng)用于移動(dòng)機(jī)器人行走的路徑規(guī)劃。該算法同時(shí)兼顧了遺傳進(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)化的不同階段選取合適的交叉和變異概率對(duì)于進(jìn)化結(jié)果有著關(guān)鍵性的影響，本文將算法分成了兩個(gè)階段，分別設(shè)定了不同的遺傳操作概率，這種方式還比較簡(jiǎn)單，不能完全適應(yīng)種群的變化情況。如何讓算法根據(jù)種群進(jìn)化情況自動(dòng)調(diào)整和優(yōu)化這些參數(shù)，還需進(jìn)一步的研究和改進(jìn)。