1.3 種群初始化

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

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

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

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

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

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

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



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


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

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

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


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

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

f=1／(ML)    (6)

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

1.5 遺傳算子

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