基于小生境遺傳算法的移動(dòng)機器人路徑優(yōu)化
加入技術(shù)交流群
1.3 種群初始化
執行遺傳算法的最優(yōu)路徑設計是必須對種群進(jìn)行初始化，由于初始路徑隨機產(chǎn)生，各轉向點(diǎn)坐標可能分布在整個(gè)規劃區域范圍內，包括可行的和不可行的，這樣便增加了搜索范圍。這里在可行區域內限制初始轉向點(diǎn)，以加快遺傳算法的收斂速度。具體做法為：判斷該轉向點(diǎn)是否在可行區域內，如果不是，則重新選取，直到坐標點(diǎn)符合條件為止。
根據規劃環(huán)境的復雜度不同，最優(yōu)路徑中轉向點(diǎn)的個(gè)數也是不確定的，一般來(lái)說(shuō)，環(huán)境越復雜，轉向點(diǎn)就越多，因此算法采用變長(cháng)編碼技術(shù)，通過(guò)對染色體進(jìn)行刪除、插入等操作，能夠確定合適的轉向點(diǎn)個(gè)數，使路徑達到最優(yōu)。但是，轉向點(diǎn)數目太多，占用資源也就會(huì )太大，它將使運算速度變慢。因此，在運算過(guò)程中，設定最大轉向點(diǎn)為Nmax，種群中每個(gè)個(gè)體的長(cháng)度n滿(mǎn)足2≤n≤Nmax。
采用小生境原理，將每一代個(gè)體劃分為若干類(lèi)，每個(gè)類(lèi)中選出若干適應度較大的個(gè)體，作為一個(gè)類(lèi)的優(yōu)秀代表組成一個(gè)種群。
1.4適應度函數
所謂移動(dòng)機器人的路徑規劃，指在起點(diǎn)和終點(diǎn)之間找出一條最短的可行路徑，其約束條件是不與障礙物相交，同時(shí)移動(dòng)機器人在行走中的轉角不宜太大。該算法以?xún)蓚€(gè)條件作為規劃路徑的可行性評價(jià)函數，即路徑總長(cháng)度和各轉向點(diǎn)拐角的平均大小，對于不可行的路徑，對其適應度進(jìn)行懲罰，使它的適應度差于可行路徑。
(1)路徑總長(cháng)度。為了防止移動(dòng)機器人與障礙物碰撞，應盡量使其與障礙物保持一定的安全距離。假設移動(dòng)機器人的安全半徑為r；移動(dòng)機器人與障礙物的距離為d，則路徑總長(cháng)度Len由式(1)計算：
式中：d(pi-1，pi)為轉向點(diǎn)pi-1與pi之間的長(cháng)度。如果pi-1與pi之間的路徑不可行，則使用懲罰函數法對其適應度進(jìn)行懲罰。懲罰函數定義如下：
式中：ε為懲罰因子。路徑的評價(jià)函數可以寫(xiě)為：
判斷兩點(diǎn)之間的路徑是否可行，只需判斷這兩點(diǎn)的連線(xiàn)與障礙物的各邊是否相交即可。根據幾何學(xué)原理，判斷兩條線(xiàn)段是否相交可由以下兩個(gè)步驟進(jìn)行確定：快速排斥試驗；跨立試驗。鑒于文章篇幅，在此不再對這兩個(gè)試驗進(jìn)行詳細闡述。
評價(jià)路徑是求路徑長(cháng)度最短的問(wèn)題，通過(guò)懲罰因子，可以使不可行路徑變長(cháng)，從而降低它的適應值。
(2)路徑平滑度。移動(dòng)機器人的特點(diǎn)決定了它在行走過(guò)程中不宜以過(guò)大拐角進(jìn)行轉向，因此整條行走路徑應趨于平緩而光滑，即每一轉向點(diǎn)處的拐角值應盡可能小。這里假設拐角最大值不能超過(guò)π／2，平滑度可以使用路徑的平均拐角值來(lái)計算：
式中：ξ為一個(gè)趨于零的常數(ξ>0)；αi(0≤αi≤π，i=2，3，…，n-1)表示兩向量AC，CB之間的夾角，B，C點(diǎn)的坐標分別為(xi-2，yi-1)，(xi，yi)，(xi-1，yi-1)；k為αi中大于或等于π／2的個(gè)數，即當某一夾角大于或等于π／2時(shí)，對適應度進(jìn)行懲罰。當n=2時(shí)，路徑為起始點(diǎn)與終止點(diǎn)的連線(xiàn)。若其可行，則M值趨于0?？梢钥闯?，M值越小，路徑的平滑度越好。
得到了以上兩個(gè)條件的評價(jià)函數，就可以獲得整條路徑的適應度函數。采用各項評價(jià)函數加權求和是常用的確定適應度函數的方法。因為各個(gè)加權系數不是恒定不變的，而是隨路徑和障礙物的情況變化而變化的，所以這種情況下各個(gè)加權系數就很難調整和確定。因此，在確定適應度函數時(shí)，盡量使適應度函數的項數最少，但又必須把路徑規劃的兩個(gè)條件融合在遺傳優(yōu)化過(guò)程中。這里采用評價(jià)函數相乘的形式，如式(6)所示。
f=1／(ML) (6)
以f作為選擇操作的依據，則路徑的長(cháng)度和平均拐角越小，其適應度越好。
1.5 遺傳算子
(1)選擇算子。使用錦標賽選擇法和精英保留法相結合的選擇策略。采用在錦標賽選擇法選擇時(shí)，先隨機在群體中選擇K個(gè)個(gè)體進(jìn)行比較，適應度最好的個(gè)體將被選擇作為生成下一代的父體，參數K稱(chēng)為競賽規模。這種選擇方式能使種群中適應度好的個(gè)體具有較大的“生存”機會(huì )。同時(shí)，由于它只使用適應度的相對值作為選擇的標準，而與適應度的數值大小不成直接比例，從而避免了超級個(gè)體的影響，在一定程度上避免了過(guò)早收斂和停滯現象的發(fā)生。精英保留法是當前種群中適應度最好的個(gè)體，它不參加遺傳操作，可直接復制到下一代，替換經(jīng)交叉和變異操作產(chǎn)生的子種群中適應度最差的個(gè)體，其優(yōu)點(diǎn)是在搜索過(guò)程中可以使某一代最優(yōu)個(gè)體不被遺傳操作所破壞，這樣可保證遺傳算法以概率收斂到最優(yōu)解。經(jīng)驗證明，保留占種群總體2％～5％數量的個(gè)體，效果最為理想。
(2)交叉算子。采用單點(diǎn)交叉法，在兩個(gè)父體上分別隨機選取一個(gè)交叉點(diǎn)(起點(diǎn)和終點(diǎn)除外)，交換兩個(gè)個(gè)體在各自交叉點(diǎn)之后的染色體?？紤]到規劃路徑的長(cháng)度是可變的，為了防止交叉操作后出現過(guò)于繁瑣或簡(jiǎn)單的路徑，對生成的新個(gè)體長(cháng)度進(jìn)行限制，即最大長(cháng)度不能超過(guò)Nmax，并且不能產(chǎn)生回路，若不符合要求，重新獲取兩個(gè)父個(gè)體的交叉點(diǎn)。
(3)插入算子。設計了兩種插入算子。第一種是有針對性的，即在連線(xiàn)穿過(guò)障礙物的兩個(gè)轉向點(diǎn)之間插入一個(gè)或多個(gè)轉向點(diǎn)，使產(chǎn)生的路徑避開(kāi)障礙物，如圖1(a)所示；第二種是一般意義上的插入，以一定概率插入一個(gè)隨機產(chǎn)生的轉向點(diǎn)，如圖1(b)所示。
(4)擾動(dòng)算子。同樣設計了兩種擾動(dòng)算子，第一種只選取路徑不可行的轉向點(diǎn)來(lái)進(jìn)行小范圍的調整，使其路徑可行，如圖1(c)所示；第二種是不管路徑是否可行，任意選取一個(gè)位置，以概率pm對其轉向點(diǎn)坐標進(jìn)行調整。在進(jìn)化初期，不可行的解數量較多，調整的范圍大一些。在進(jìn)化后期調整范圍逐漸縮小，如圖1(d)所示。
(5)刪除算子。建立一個(gè)存儲空間REC，在一條路徑中，如果點(diǎn)(xi-1，yi-1)與點(diǎn)(xi，yi)的連線(xiàn)經(jīng)過(guò)障礙物，但(xi-1，yi-1)與(xi+1，yi-1)的連線(xiàn)不經(jīng)過(guò)障礙物，則將點(diǎn)(xi，yi)添加到REC中。如果REC不為空，則從中隨機選取一點(diǎn)刪除(見(jiàn)圖1(e))；否則，在路徑中任意選取一個(gè)路徑點(diǎn)，以概率pd進(jìn)行刪除，如圖1(f)所示。
評論