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

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

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



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

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

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

1.6 遺傳算子概率選擇

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

1.7 終止條件

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

1.8 算法流程

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

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

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

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

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