張 錚, 柯子鵬, 周嘉政, 錢勤建, 胡新宇

(湖北工業(yè)大學(xué) 機(jī)械工程學(xué)院, 湖北 武漢 430068)

移動(dòng)機(jī)器人是集環(huán)境感知,自主規(guī)劃與自動(dòng)執(zhí)行任務(wù)的智能設(shè)備,通過預(yù)先的編程構(gòu)建機(jī)器人內(nèi)部控制系統(tǒng)。伴隨機(jī)電一體化技術(shù)的快速發(fā)展,移動(dòng)機(jī)器人受到廣泛關(guān)注,其應(yīng)用涵蓋太空、軍事、農(nóng)業(yè)、醫(yī)療、快遞、家庭等場(chǎng)合,對(duì)推動(dòng)科技、社會(huì)發(fā)展,提高生活質(zhì)量起重要作用。路徑規(guī)劃問題是在滿足現(xiàn)有環(huán)境限制的前提下完成最優(yōu)路徑的規(guī)劃。路徑規(guī)劃作為移動(dòng)機(jī)器人至關(guān)重要的部分,成為現(xiàn)今機(jī)器人領(lǐng)域的研究焦點(diǎn)。

移動(dòng)機(jī)器人發(fā)展的路徑規(guī)劃算法主要分為三種,第一種,傳統(tǒng)路徑規(guī)劃算法,例如A*算法、圖論算法等[1-4];第二種,基于采樣過程的路徑規(guī)劃算法,主要為RRT算法與PRM算法[5-8];第三種,智能仿生路徑規(guī)劃算法,根據(jù)仿生設(shè)計(jì)出的神經(jīng)網(wǎng)絡(luò)算法、蟻群算法、遺傳算法等[9-16]。

其中遺傳算法是一種啟發(fā)式搜索算法,相較于傳統(tǒng)路徑規(guī)劃固定式求解,能保證最優(yōu)解與效率的動(dòng)態(tài)平衡。具有較好的全局最優(yōu)搜索能力,但局部搜索能力差。通過各種方式改進(jìn)遺傳算法在機(jī)器人路徑規(guī)劃中應(yīng)用廣泛,并具有較多的研究成果。如文獻(xiàn)[9]提出一種雙重標(biāo)準(zhǔn)編碼方式,增加遺傳算法變異過程以避免局部最優(yōu)解產(chǎn)生,對(duì)多目標(biāo)路徑規(guī)劃高效適用。文獻(xiàn)[10]將精英主義族系策略融入遺傳算法中,利用精英標(biāo)記遺傳個(gè)體并引入多目標(biāo)適應(yīng)度評(píng)價(jià)函數(shù)以實(shí)現(xiàn)集群協(xié)同控制的需求。文獻(xiàn)[11]為解決傳統(tǒng)遺傳算法缺點(diǎn)同時(shí)確保最優(yōu)解質(zhì)量,將路徑拐點(diǎn)數(shù)量作為適應(yīng)度指標(biāo)。實(shí)現(xiàn)減少算法迭代次數(shù)與提高最優(yōu)解質(zhì)量。文獻(xiàn)[12]根據(jù)模糊算法調(diào)整遺傳算法參數(shù)用以提高尋優(yōu)速度,引入余弦平滑度因子改善路徑安全性。文獻(xiàn)[13]采用并行GA對(duì)無(wú)人機(jī)進(jìn)行路徑規(guī)劃,同時(shí)驗(yàn)證了并行GA較單GA有更快的速度與產(chǎn)生更好的結(jié)果,但對(duì)處理器有更高的要求。文獻(xiàn)[14]使用退火算法結(jié)合遺傳算法進(jìn)行路徑規(guī)劃,以表面局部最優(yōu)問題同時(shí)保證迭代過程中種群多樣性。文獻(xiàn)[15]采用粒子群算法結(jié)合遺傳算法優(yōu)化機(jī)器人運(yùn)動(dòng)規(guī)劃,并將能耗與時(shí)間融入目標(biāo)函數(shù),以提高機(jī)器人性能。文獻(xiàn)[16]提出改進(jìn)混合蟻群遺傳算法,以優(yōu)化遺傳操作與適應(yīng)度函數(shù),同時(shí)去除蟻群死鎖問題,合理減少了迭代次數(shù),并縮短了搜索時(shí)間。

在上述研究中,針對(duì)遺傳算法的改進(jìn)主要通過改進(jìn)原始操作、結(jié)合其他優(yōu)化算法進(jìn)行缺點(diǎn)互補(bǔ)或引入相關(guān)操作實(shí)現(xiàn),雖然在某方面具有較好的效果,但是增加了算法整體復(fù)雜度,延長(zhǎng)了算法耗時(shí),提高了硬件的適配要求,同時(shí)優(yōu)化方向較為片面。本文提出一種改進(jìn)多目標(biāo)自適應(yīng)遺傳算法。通過限制性均勻隨機(jī)搜索算法初始化種群,同時(shí)建立限制性步長(zhǎng)對(duì)初始種群路徑長(zhǎng)度的先驗(yàn)?zāi)Ｐ?。綜合考慮路徑長(zhǎng)度,路徑安全度與路徑能耗搭建適應(yīng)度函。利用平衡閾值改進(jìn)自適應(yīng)交叉變異算子以提高提高自適應(yīng)交叉變異效率。提出自適應(yīng)進(jìn)化判斷操作,以縮短種群進(jìn)化停滯過程與放置種群進(jìn)化倒退現(xiàn)象。最后引入刪除操作去除最優(yōu)路徑冗雜節(jié)點(diǎn)來優(yōu)化最優(yōu)路徑。經(jīng)過與GA,ACO-GA、SSA算法對(duì)比實(shí)驗(yàn),本文改進(jìn)算法性能更具優(yōu)越性,在降低算法復(fù)雜度同時(shí),縮短了其迭代次數(shù)并加快了收斂過程,具有較好的魯棒性,在維持最優(yōu)路徑長(zhǎng)度的同時(shí),降低了路徑能耗。

1 環(huán)境建立

1.1 路徑規(guī)劃環(huán)境建模

由于柵格地圖容易創(chuàng)建,表示與保存,每個(gè)位置對(duì)應(yīng)點(diǎn)唯一,有助于機(jī)器人路徑規(guī)劃。故采用柵格地圖對(duì)移動(dòng)機(jī)器人環(huán)境進(jìn)行建模,每塊柵格的尺寸通過障礙物的大小與移動(dòng)機(jī)器人的大小共同決定。

在柵格地圖中利用黑塊表示障礙物,白塊表示無(wú)障礙物,并假設(shè)柵格地圖周圍全為障礙物。為方便仿真實(shí)驗(yàn)的進(jìn)行,假設(shè)所有的柵格地圖都為考慮機(jī)器人安全距離后擴(kuò)展的環(huán)境,同時(shí)假設(shè)移動(dòng)機(jī)器人為一質(zhì)點(diǎn),避免影響驗(yàn)證算法性能。柵格地圖建立方式見圖1。

圖1 標(biāo)記序號(hào)的柵格地圖Fig.1 Grid map with serial numbers

1.2 編碼方式

為減少直接用坐標(biāo)計(jì)算帶來的巨大計(jì)算量,故采用坐標(biāo)到序號(hào)的映射轉(zhuǎn)換來替代坐標(biāo)計(jì)算。設(shè)柵格地圖的大小rows×cols,按照1-rows·cols來表示柵格序號(hào)。序號(hào)與坐標(biāo)的映射公式如下:

(1)

2 本文算法介紹

2.1 初始化操作

種群初始化在遺傳算法中往往容易被忽略,初始種群的質(zhì)量對(duì)算法整體迭代次數(shù)、最優(yōu)解質(zhì)量等都有巨大的影響。同時(shí)質(zhì)量高的初始種群能極大減少遺傳算法的收斂過程,以更快的速度達(dá)到最優(yōu)解。本文提出使用一種限制性啟發(fā)搜索算法結(jié)合中值插入算法用以初始化種群,節(jié)點(diǎn)生成庫(kù)見圖2。

圖2 節(jié)點(diǎn)生成庫(kù)示意圖Fig.2 Schematic diagram of node generation library

該算法的具體操作流程如下:

1) 根據(jù)柵格地圖的尺寸(rows,cols)計(jì)算出節(jié)點(diǎn)庫(kù)數(shù)量,計(jì)算公式如下;

N=rows+cols-3

(2)

k=ceil(N/2)

(3)

2) 生成節(jié)點(diǎn)庫(kù),用以隨機(jī)生成節(jié)點(diǎn),如圖2所示,節(jié)點(diǎn)庫(kù)為45度方向上非障礙物的節(jié)點(diǎn)集合,每個(gè)節(jié)點(diǎn)庫(kù)占據(jù)兩斜層?？偣?jié)點(diǎn)庫(kù)表示為:

ccan={can1,can2,can3,……,cank}

(4)

3) 根據(jù)如下限制性條件在節(jié)點(diǎn)庫(kù)中隨機(jī)生成節(jié)點(diǎn)。若不生成不滿足條件的節(jié)點(diǎn),則重新在節(jié)點(diǎn)庫(kù)cani中生成節(jié)點(diǎn),并滿足一定的循環(huán)次數(shù)。若超出訓(xùn)話次數(shù)仍不滿足條件,則刪除該路徑。

max(abs(xi-xi-1),abs(yi-yi-1))

(5)

4) 根據(jù)從節(jié)點(diǎn)庫(kù)中生成的間斷節(jié)點(diǎn)個(gè)體,利用中值插入方法使路徑連續(xù)。插入的節(jié)點(diǎn)是通過向下取整相鄰節(jié)點(diǎn)的平均值獲取,同時(shí)判斷該點(diǎn)是否為障礙物,若為障礙物,則通過4鄰域移動(dòng)尋找出非障礙物點(diǎn)。

(6)

5) 中值插入算法的終止條件如下,通過順序節(jié)點(diǎn)的橫縱坐標(biāo)的最大距離以判斷節(jié)點(diǎn)是相鄰節(jié)點(diǎn)。

max{abs(xi-xi+1),abs(yi-yi+1)}≤1

(7)

限制性步長(zhǎng)step對(duì)產(chǎn)生的初始路徑長(zhǎng)度length存在影響,通過最小二乘法建立限制性步長(zhǎng)的先驗(yàn)公式。二次曲線擬合公式為:

f(x)=ax2+bx+c

(8)

式中:x為路徑長(zhǎng)度;f(x)為擬合的步長(zhǎng)函數(shù)。

根據(jù)實(shí)際stepi與建立的擬合函數(shù)f(x)建立最小二乘目標(biāo)函數(shù)如下:

(9)

分別通過對(duì)a、b、c求導(dǎo),列出如下聯(lián)合算式:

(10)

為提高擬合的準(zhǔn)確性,通過每個(gè)step對(duì)應(yīng)的多個(gè)步長(zhǎng)的均值來反映兩者之間的關(guān)系,見圖3。

圖3 擬合步長(zhǎng)與路徑長(zhǎng)度Fig.3 Fitting step size and path length

擬合后的步長(zhǎng)先驗(yàn)公式為:

step=-0.00064x2+0.0519x-0.9058

(11)

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

適應(yīng)度函數(shù)作為遺傳算法中個(gè)體在既定條件下的適應(yīng)狀況指標(biāo),用以明確種群的進(jìn)化方向。根據(jù)多目標(biāo)適應(yīng)度函數(shù),可以從多個(gè)方面優(yōu)化路徑[17-21]。為減少機(jī)器人在路徑規(guī)劃中因轉(zhuǎn)向過多造成的能耗損失,并在實(shí)現(xiàn)路徑長(zhǎng)度最優(yōu)時(shí)保證路徑安全性問題,本文將路徑長(zhǎng)度,安全度與能耗三個(gè)因素作為評(píng)判路徑質(zhì)量?jī)?yōu)劣的依據(jù)。適應(yīng)度函數(shù)表示為:

(12)

式中:D(k)是距離函數(shù);S(k)是安全度函數(shù);T(k)是轉(zhuǎn)向次數(shù)函數(shù);ρ1、ρ2、ρ3分別為三個(gè)指標(biāo)對(duì)應(yīng)的系數(shù)。路徑的距離是根據(jù)鄰近節(jié)點(diǎn)的歐式距離求和得出,距離函數(shù)為:

(13)

式中k為路徑的總節(jié)點(diǎn)數(shù)量。路徑的安全函數(shù)如下,通過統(tǒng)計(jì)每個(gè)節(jié)點(diǎn)四鄰域(見圖4)的障礙物數(shù)量之和,判斷該路徑周圍的障礙情況,

圖4 四鄰域圖Fig.4 Four-neighbor graph

(14)

與8鄰域障礙物統(tǒng)計(jì)相比,四鄰域障礙物統(tǒng)計(jì)可以有效避免斜穿障礙物現(xiàn)象,同時(shí)減少搜索過程,以保證較高的統(tǒng)計(jì)效率。

路徑的轉(zhuǎn)向函數(shù)見式(15),通過控制路徑的轉(zhuǎn)向次數(shù),以提高路徑的平滑度與降低路徑能耗。

(15)

式中Ti為第二個(gè)節(jié)點(diǎn)開始的轉(zhuǎn)向統(tǒng)計(jì)。由于單個(gè)節(jié)點(diǎn)無(wú)對(duì)比,無(wú)需進(jìn)行判斷,故從第二個(gè)節(jié)點(diǎn)開始判斷,直至最優(yōu)一個(gè)節(jié)點(diǎn)k。

路徑的能耗通過路徑長(zhǎng)度與轉(zhuǎn)向次數(shù)共同確定,能耗表達(dá)式為:

(16)

2.3 選擇操作

選擇操作是遺傳算法中影響遺傳方向的重要一環(huán),必須考慮選擇操作過程選出有潛力的最優(yōu)個(gè)體,同時(shí)為防止結(jié)果陷入局部最優(yōu)值。盡量維持路徑的均勻多樣化,以消除種群壟斷。本文采用的選擇操作為改進(jìn)的輪盤選擇操作與3段式選擇操作。其中輪盤選擇的隨機(jī)性在迭代過程中保證每種個(gè)體都存在被選中的機(jī)會(huì),以實(shí)現(xiàn)維持物種多樣性。但由于輪盤選擇操作過于隨機(jī),每次個(gè)體的選擇不夠穩(wěn)定,進(jìn)而影響遺傳算法的迭代過程。這里結(jié)合貪心算法,將父代種群的最優(yōu)個(gè)體分成兩部分操作,一是直接保留父代最優(yōu)個(gè)體,不放入選擇操作結(jié)束后的種群,二是將最優(yōu)父代個(gè)體直接放入選擇操作后的種群。此種做法的目的是保留父代最優(yōu)個(gè)體的同時(shí),避免父代最優(yōu)個(gè)體在子代遺傳操作中喪失優(yōu)勢(shì),以保證種群始終穩(wěn)定不退化遺傳。輪盤操作是通過每個(gè)個(gè)體的適應(yīng)度值計(jì)算適應(yīng)度占比。通過輪盤選擇,重復(fù)抽取個(gè)體。每個(gè)個(gè)體的被隨機(jī)選中的概率公式為:

(17)

輪盤選擇通過累加概率,隨機(jī)選中相應(yīng)的個(gè)體,其概率累加公式為:

(18)

由于后續(xù)提出種群進(jìn)化判斷操作,在進(jìn)化判斷中使用三段式選擇操作,提高算法運(yùn)行速度同時(shí),能加快種群收斂過程。其原理為,先將種群按照適應(yīng)度大小排序,此時(shí)按照數(shù)量將種群分成低適應(yīng)度,中適應(yīng)度,高適應(yīng)度。刪除低適應(yīng)度段,同時(shí)將一倍中適應(yīng)度段與雙倍高適應(yīng)段放入選擇后的種群中進(jìn)行后續(xù)操作。三段式選擇具體操作見圖5。

圖5 三段式選擇操作Fig.5 Three-stage selection operation

2.4 自適應(yīng)交叉變異操作

交叉變異操作作為遺傳算法中群體進(jìn)化的主要操作,需要在維持種群多樣性的同時(shí),盡可能使得交叉后的群體優(yōu)于交叉之前,同時(shí)保證獲得更優(yōu)種群與加快種群收斂速度。由于全自適應(yīng)交叉變異概率對(duì)處于中等適應(yīng)度群體的影響較小,同時(shí)增加了算法的計(jì)算復(fù)雜度,這里通過分段閾值thresh來平衡交叉變異概率自適應(yīng)性與計(jì)算復(fù)雜度的影響。自適應(yīng)方式主要分為兩種,一是隨迭代次數(shù)自適應(yīng)變化;二是根據(jù)個(gè)體適應(yīng)度大小自適應(yīng)變化。第一種自適應(yīng)方式受迭代次數(shù)的影響明顯,雖然對(duì)遺傳算法改進(jìn)有一定效果,但因迭代次數(shù)限制,收斂速度提高有局限。第二種自適應(yīng)方式不受迭代次數(shù)的影響,每次迭代都進(jìn)行相同的自適應(yīng)操作,根據(jù)個(gè)體適應(yīng)度值更改其交叉率。本文采用不受迭代次數(shù)影響的自適應(yīng)交叉操作,第一段針對(duì)適應(yīng)度較差個(gè)體自適應(yīng)提高其交叉變異概率,中間一段為數(shù)量最多的群體,采用固定的交叉變異概率,最后一段針對(duì)高適應(yīng)度個(gè)體,通過降低其交叉變異概率以減小高適應(yīng)度個(gè)體流失的概率。

(19)

(20)

式中:fitmax為當(dāng)前種群最大適應(yīng)度;fitmin為當(dāng)前種群最小適應(yīng)度;fit(i)為個(gè)體i的適應(yīng)度;thresh為概率分段閾值。交叉變異的自適應(yīng)概率分布見圖6。

圖6 交叉變異概率自適應(yīng)變化圖Fig.6 Cross-mutation probability adaptive change graph

若隨機(jī)數(shù)比自適應(yīng)交叉率小,則個(gè)體進(jìn)行單點(diǎn)交叉操作,交叉過程見圖7,設(shè)待交叉的個(gè)體為a-b-c-d-e與a-b-g-h-e,設(shè)交叉點(diǎn)為第三個(gè),則兩個(gè)個(gè)體在節(jié)點(diǎn)3之后的節(jié)點(diǎn)將共同進(jìn)行交叉。經(jīng)過單點(diǎn)交叉后的個(gè)體分別為a-b-c-h-e與a-b-g-d-e。

圖7 單點(diǎn)交叉過程Fig.7 Single point crossover process

變異操作是遺傳算法模仿生物基因突變的過程,在路徑規(guī)劃中的變異操作常采用隨機(jī)點(diǎn)的八鄰域范圍內(nèi)隨機(jī)突變。由于突變具有不定向性,無(wú)法控制變異本身以控制進(jìn)化方向,若變異后的節(jié)點(diǎn)為對(duì)角鄰域,同時(shí)四鄰域存在障礙物,則易出現(xiàn)橫穿障礙物現(xiàn)象,故采用四鄰域變異。經(jīng)過變異操作后的節(jié)點(diǎn)需要經(jīng)過障礙物判斷,以保證變異后路徑的有效性。在一定搜尋次數(shù)條件下尋找出非障礙物點(diǎn)。若超出搜索次數(shù),則停止操作以避免計(jì)算量過大影響整體速度。最后將變異后的節(jié)點(diǎn)通過中值插入算法與其他路徑段連續(xù)連接。

四鄰域變異的模板mask與其x、y方向上的算子如下。通過隨機(jī)選取模板mask為1的位置,根據(jù)位置計(jì)算出x、y方向算子對(duì)應(yīng)的值,用以更新變異節(jié)點(diǎn)的x、y坐標(biāo)。

(21)

(22)

2.5 自適應(yīng)進(jìn)化判斷操作

為避免種群在迭代過程出現(xiàn)較多維持停滯或退化現(xiàn)象,采用自適應(yīng)進(jìn)化判斷操作,用以判斷種群的進(jìn)化狀況,若種群未進(jìn)化,則通過進(jìn)行多次遺傳操作。利用threshold平衡閾值以平衡進(jìn)化過程與進(jìn)化耗時(shí)的影響。針對(duì)退化現(xiàn)象,通過貪心算法,保留局部最優(yōu)個(gè)體,以防止種群進(jìn)化出現(xiàn)震蕩過程。經(jīng)過遺傳進(jìn)化判斷,進(jìn)化判斷公式為:

iter

(23)

式中:fitnext為子種群的最佳適應(yīng)度;fitpre為父種群的最佳適應(yīng)度;iter為自適應(yīng)進(jìn)化操作中的循環(huán)次數(shù);threshold為自適應(yīng)進(jìn)化操作中的最大循環(huán)次數(shù),以避免降低算法整體速度。

若每代子種群最佳適應(yīng)度不小于父種群的最佳適應(yīng)度,則經(jīng)過三段式選擇去除低適應(yīng)度個(gè)體,再進(jìn)行多次自適應(yīng)交叉變異操作,并重新計(jì)算適應(yīng)度,然后經(jīng)過自適應(yīng)進(jìn)化判斷。

2.6 刪除操作

刪除操作為完善遺傳算法最優(yōu)個(gè)體的必要步驟,相應(yīng)地圖中初始節(jié)點(diǎn)的數(shù)量具有固定。雖然遺傳算法實(shí)現(xiàn)固定節(jié)點(diǎn)的最優(yōu)個(gè)體,但對(duì)少于固定節(jié)點(diǎn)數(shù)量的路徑不一定具有優(yōu)越性,因此為解決冗雜節(jié)點(diǎn)影響最優(yōu)個(gè)體質(zhì)量問題,通過刪除操作實(shí)現(xiàn)個(gè)體去除冗雜節(jié)點(diǎn)以提高最優(yōu)個(gè)體質(zhì)量。刪除操作前后的路徑對(duì)比圖見圖8。

圖8 無(wú)刪除操作與刪除操作路徑Fig.8 No delete operation and delete operation path

該刪除操作算法通過檢測(cè)某節(jié)點(diǎn)的左右鄰點(diǎn)是否能無(wú)障礙直線連接來判斷該節(jié)點(diǎn)是否為冗雜節(jié)點(diǎn)。式(24)多次利用式(25),循環(huán)遍歷中點(diǎn)的中點(diǎn)并判斷是否為障礙物,若整個(gè)遍歷過程都無(wú)障礙物,則返回?zé)o障礙物標(biāo)志,表示當(dāng)前節(jié)點(diǎn)的左右節(jié)點(diǎn)直線連接不經(jīng)過障礙物,故可以刪除該節(jié)點(diǎn);若有一個(gè)中點(diǎn)被判斷為障礙物,則返回障礙物標(biāo)志,表示當(dāng)前節(jié)點(diǎn)的前后節(jié)點(diǎn)直線連接會(huì)經(jīng)過障礙物,故該節(jié)點(diǎn)不可刪除。其判斷表達(dá)式為:

flag=delete_node(nodei)

(24)

(25)

式中:(xi-1,yi-1),(xi-1,yi-1)分別為判斷刪除節(jié)點(diǎn)的前后節(jié)點(diǎn)坐標(biāo);通過前后節(jié)點(diǎn)坐標(biāo)的均值四舍五入取整為(mx,my),判斷(mx,my)在柵格地圖中是否為障礙物。

flag為全局標(biāo)志位,且初始化為0。若flag返回為1表示經(jīng)過障礙物,直接退出判斷函數(shù);若不經(jīng)過障礙物,則繼續(xù)判斷節(jié)點(diǎn)nodei+1,直至倒數(shù)第二個(gè)節(jié)點(diǎn)nodek-1;若flag返回0表示不經(jīng)過障礙物,則刪除節(jié)點(diǎn)nodei,并重新計(jì)算個(gè)體節(jié)點(diǎn)總數(shù),后續(xù)節(jié)點(diǎn)判斷從刪除節(jié)點(diǎn)的后一節(jié)點(diǎn)nodei+1開始刪除判斷,同樣直至倒數(shù)第二節(jié)點(diǎn)nodek-1。見圖8,紅色路徑為未刪除節(jié)點(diǎn)的路徑,藍(lán)色路徑為刪除節(jié)點(diǎn)后的路徑。

2.7 本文算法流程

本文改進(jìn)的多目標(biāo)自適應(yīng)遺傳算法見圖9。

圖9 本文改進(jìn)算法流程圖Fig.9 Flow chart of the improved algorithm in this paper

先通過限制性均勻隨機(jī)搜索算法生成初始種群,利用初始路徑長(zhǎng)度建立限制性步長(zhǎng)的先驗(yàn)?zāi)Ｐ?并根據(jù)路徑長(zhǎng)度、路徑安全性與路徑能耗構(gòu)建種群的適應(yīng)度函數(shù),以從多目標(biāo)優(yōu)化路徑。然后開始遺傳迭代過程,使用輪盤選擇結(jié)合貪心算法維持種群多樣性,同時(shí)保留當(dāng)代全局最優(yōu)個(gè)體。通過改進(jìn)自適應(yīng)交叉變異操作對(duì)種群進(jìn)行節(jié)點(diǎn)更替。通過自適應(yīng)進(jìn)化判斷操作,對(duì)持續(xù)未進(jìn)化的種群進(jìn)行多次遺傳操作。采用三段式選擇操作淘汰低適應(yīng)度個(gè)體,再經(jīng)過改進(jìn)自適應(yīng)交叉變異操作,最后重新計(jì)算適應(yīng)度并判斷種群是否進(jìn)化,若出現(xiàn)進(jìn)化則退出進(jìn)化循環(huán),否則重復(fù)以上進(jìn)化循環(huán)過程。最后通過刪除操作,優(yōu)化最終路徑并輸出。

3 仿真實(shí)驗(yàn)

為了驗(yàn)證改進(jìn)多目標(biāo)自適應(yīng)遺傳算法的優(yōu)越性,通過在配置Inter(R) Core (TM) i5-6200U CPU @ 2.30GHz (4 CPUs) ～2.4GHz的Windows 10系統(tǒng)筆記本中,運(yùn)用MATLAB 2017b軟件進(jìn)行仿真實(shí)驗(yàn)。為了更好的展示各算法性能,本文算法與對(duì)比的GA、ACO-GA、SSA算法均采用自身最優(yōu)效果參數(shù)。同時(shí)為體現(xiàn)算法整體的應(yīng)用廣泛性,通過不同維度的柵格地圖與同緯度地圖中不同數(shù)量障礙物分別設(shè)立50次對(duì)比實(shí)驗(yàn)。分別通過對(duì)比50次實(shí)驗(yàn)的最優(yōu)路徑長(zhǎng)度,平均路徑長(zhǎng)度,平均耗時(shí),平均轉(zhuǎn)向次數(shù),平均能耗等因素,比較算法的有效性。

見圖10,在75障礙物的20×20地圖中,改進(jìn)GA算法路徑較為波折,SSA算法路徑較為平順,但其規(guī)劃路徑長(zhǎng)度較長(zhǎng)。ACO-GA算法與本文改進(jìn)算法規(guī)劃路徑較為相似,但在平滑細(xì)節(jié)上與整體路徑長(zhǎng)度上都展示更好的效果。見圖11,在102障礙物的20×20地圖中,GA算法仍然波折,相比而言,ACO-GA算法,SSA算法與本文算法路徑更加平滑。在節(jié)點(diǎn)細(xì)節(jié)上,本文算法具有更好的效果。

圖10 四種算法在75障礙物的20×20地圖中的規(guī)劃路徑Fig.10 Four algorithms for planning paths in a 20×20 map with 75 obstacles

圖11 四種算法在102障礙物的20×20地圖中的規(guī)劃路徑Fig.11 Four algorithms for planning paths in a 20×20 map with 102 obstacles

四種算法經(jīng)兩幅地圖路徑規(guī)劃,其迭代過程見圖12。GA算法在迭代過程具有較差的穩(wěn)定性,同時(shí)需要較多的迭代次數(shù)達(dá)到最優(yōu)規(guī)劃,ACO-GA算法在規(guī)劃路徑時(shí),穩(wěn)定性不足,而SSA算法在迭代過程中具有較好的穩(wěn)定性,相比而言,本文算法迭代過程更加穩(wěn)定,同時(shí)以更少的迭代次數(shù)達(dá)到最優(yōu)規(guī)劃。

圖12 四種算法在75與102障礙物地圖的迭代過程Fig.12 Iterative process of four algorithms in 75 and 102 obstacle maps

四種算法在兩個(gè)地圖路徑規(guī)劃的統(tǒng)計(jì)數(shù)據(jù)見表1和表2,通過對(duì)比發(fā)現(xiàn),本文算法規(guī)劃的路徑最優(yōu)長(zhǎng)度與平均長(zhǎng)度均優(yōu)于其他算法,并具有更小的轉(zhuǎn)向次數(shù),以優(yōu)化機(jī)器人因過多轉(zhuǎn)向而增加耗能。

表2 障礙物為102的20×20地圖Tab.2 20×20 map with 102 obstacles

4 結(jié) 論

本文提出一種改進(jìn)初始化操作的遺傳算法進(jìn)行路徑規(guī)劃研究,通過提出一種限制性均勻隨機(jī)搜索算法結(jié)合中值插入算法提高初始化種群質(zhì)量,并根據(jù)限制步長(zhǎng)與產(chǎn)生的種群長(zhǎng)度建立限制性步長(zhǎng)的先驗(yàn)?zāi)Ｐ?。在適應(yīng)度函數(shù)中同時(shí)考慮路徑長(zhǎng)度、路徑安全性與路徑能耗。優(yōu)化了自適應(yīng)交叉變異操作,通過平衡閾值優(yōu)化其性能。并引入了自適應(yīng)進(jìn)化操作結(jié)合貪心算法,以縮短種群進(jìn)化停滯現(xiàn)象和防止進(jìn)化倒退現(xiàn)象。最后刪除操作,去除冗余節(jié)點(diǎn),平滑路徑。改進(jìn)后的遺傳算法在保證最優(yōu)路徑同時(shí),能耗較低,其迭代過程更加穩(wěn)定,具備良好的魯棒性,能以更少的迭代次數(shù)達(dá)到收斂。但是,本文算法針對(duì)多目標(biāo)的參數(shù)配置有待進(jìn)一步優(yōu)化。算法的速度有待進(jìn)一步提高,同時(shí)只適用靜態(tài)全局路徑規(guī)劃,后續(xù)可通過與實(shí)時(shí)動(dòng)態(tài)局部路徑規(guī)劃結(jié)合,完善本文算法。