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

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

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



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

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

(7)倒位算子。隨機(jī)選取路徑中兩個中間轉(zhuǎn)向點，顛倒之間的轉(zhuǎn)向點。倒位算子可使路徑發(fā)生急劇變化，對于轉(zhuǎ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)向點的啟發(fā)式操作，都是針對不可行路徑的優(yōu)化調(diào)整，對于這些算子應(yīng)當(dāng)始終選擇較高的概率。插入算子(2)會使路徑的轉(zhuǎ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)行終止算法，從而保證運算時間的要求。為了實用起見，在此采取最大進(jìn)化代數(shù)終止準(zhǔn)則，并選取適應(yīng)度最好的可行路徑。

1.8 算法流程

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

(1)初始化種群，沿起點和終點連線方向等距離選取N個點，在這些點的垂直線上隨機(jī)選取轉(zhuǎn)向點的縱坐標(biāo)，并且使這些轉(zhuǎ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)度，就替換父串；否則維持父串不變；