基于改進(jìn)遺傳算法路徑規(guī)劃問題的研究

周加全

(廣西科技師范學(xué)院， 數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院， 廣西 來(lái)賓 546199)

0 引言

隨著現(xiàn)代社會(huì)的發(fā)展，越來(lái)越多的人投入到人工智能的研究和發(fā)展中。而機(jī)器人的發(fā)展又是人工智能研究的基礎(chǔ)。在機(jī)器人研究當(dāng)中最重要的也是最基本的就是其相應(yīng)的路徑規(guī)劃[1]。路徑規(guī)劃的實(shí)質(zhì)就是在尋找最優(yōu)路徑的過程中，避開所有的障礙物，并順利到達(dá)終點(diǎn)的過程[2]。目前，路徑規(guī)劃的研究方法主要趨向于智能化的算法。這種類型的算法主要有模糊邏輯控制算法、蟻群算法和遺傳算法[3-5]，其中模糊邏輯控制算法的特點(diǎn)是魯棒性特別好，能夠?qū)崟r(shí)控制，而且對(duì)環(huán)境的依賴性較弱，但模糊規(guī)則需要結(jié)合人工經(jīng)驗(yàn)及其他方法共同制定，影響算法的性能[3]。蟻群算法是根據(jù)螞蟻留下的信息多少來(lái)找出一條最優(yōu)的路徑，這種算法需要存儲(chǔ)很多信息，在搜索過程中很容易出現(xiàn)混亂或停滯，導(dǎo)致算法不精確[4]。而遺傳算法具有全局搜索的能力，計(jì)算量小且具有魯棒性，大量的實(shí)驗(yàn)數(shù)據(jù)表明，傳統(tǒng)的遺傳算法在求解的過程中，精度較差，穩(wěn)定性也不好[5-6]。

為此，本研究提出了一種改進(jìn)型的遺傳算法——模擬退火優(yōu)化遺傳算法，并對(duì)遺傳過程中的交叉、變異進(jìn)行調(diào)整，這樣可以避免出現(xiàn)局部最優(yōu)解，提高全局搜索的能力，由仿真結(jié)果得出：改進(jìn)型的遺傳算法在路徑規(guī)劃中具有很好的應(yīng)用。

1 模擬退火算法的思想

模擬退火算法的原理是從某一較高初溫出發(fā)，伴隨溫度參數(shù)的不斷下降，在解空間中隨機(jī)尋找目標(biāo)函數(shù)并最終趨于全局最優(yōu)，也就是模擬退火算法是通過模擬高溫物體退火過程找到優(yōu)化問題的全局最優(yōu)解[7]。在這個(gè)過程中，把溫度T變化成控制程序當(dāng)中所要的參數(shù)t。具體做法是：首先由遺傳算法得到一個(gè)初始種群，并把它作為一個(gè)當(dāng)前解，并在這個(gè)解中選擇一個(gè)非局部最優(yōu)解，讓這個(gè)解重復(fù)進(jìn)行，隨著假想溫度的降低(對(duì)應(yīng)物體的退火)，在這個(gè)過程中要計(jì)算新的種群，然后根據(jù)Metropolis準(zhǔn)則，逐步減小t，最后算法結(jié)束，得到的值就是問題中的最優(yōu)解[8]。

2 改進(jìn)遺傳算法的設(shè)計(jì)

2.1 編碼

遺傳算法的編碼方式一般為二進(jìn)制編碼、浮點(diǎn)數(shù)編碼和符號(hào)編碼[9]。在研究路徑規(guī)劃的過程中，可以把一個(gè)染色體看成一條路徑，染色體中基因的排列順序是一條滿足條件路徑的解，所以采用實(shí)數(shù)編碼來(lái)表示相應(yīng)的路徑，這樣也有利于適應(yīng)值函數(shù)的選取與計(jì)算[10]。由于外部條件的復(fù)雜性以及機(jī)器人移動(dòng)的方向是靈活多變的，一般來(lái)說含有相同起點(diǎn)和終點(diǎn)的路徑不一定具有相同的最優(yōu)路徑，因此采用變長(zhǎng)度染色體編碼策略求解移動(dòng)機(jī)器人路徑規(guī)劃問題。

2.2 種群初始化

種群的初始化相對(duì)來(lái)說特別重要，它關(guān)系到在整個(gè)遺傳算法過程中能否最終收斂于一個(gè)全局當(dāng)中的最優(yōu)解。因?yàn)槌跏蓟^程中的種群規(guī)模，如果太大，則會(huì)影響進(jìn)化的時(shí)間，如果太小，則算法的時(shí)間比較短，很大可能不是最優(yōu)路徑[11]。隨機(jī)生成的初始種群，相對(duì)簡(jiǎn)單且容易出現(xiàn)一些經(jīng)過障礙物的染色體的不可行路徑。為了滿足種群在初始化過程中的多樣性要求，本研究通過使用定向和隨機(jī)兩種搜索方式來(lái)形成相應(yīng)的路徑，即分別采用下述計(jì)算來(lái)選擇下一路徑節(jié)點(diǎn)，當(dāng)距離終點(diǎn)比較近時(shí)，停止生成路徑節(jié)點(diǎn)，保存當(dāng)前路徑。若生成的路徑節(jié)點(diǎn)導(dǎo)致路徑穿過障礙物，則重新選擇路徑節(jié)點(diǎn)。如式(1)、式(2)。

xi+1=(xG-xi)×rand+xi

(1)

yi+1=(yG-yi)×rand+yi

(2)

式中，xi+1和yi+1表示選擇的下一條路徑的節(jié)點(diǎn)的坐標(biāo)；(xi，yi)表示當(dāng)前路徑節(jié)點(diǎn)的坐標(biāo)；(xG，yG)表示終點(diǎn)的坐標(biāo)；rand是(0,1)之間的隨機(jī)數(shù)。

2.3 適應(yīng)度函數(shù)的確定

遺傳算法的穩(wěn)定性和收斂性與適應(yīng)度函數(shù)密切相關(guān)。一般情況下，適應(yīng)度值越高，通過遺傳算法的選擇操作獲得的機(jī)率就越大[12]?？梢娺m應(yīng)度函數(shù)能夠比較好地表達(dá)每條路徑的優(yōu)劣。在機(jī)器人的路徑規(guī)劃過程中，適應(yīng)度函數(shù)的設(shè)計(jì)是要確保能夠準(zhǔn)確地避開障礙物且路徑最短。避開障礙物實(shí)質(zhì)就是不與障礙物發(fā)生碰撞，也即兩個(gè)相鄰的路徑點(diǎn)之間的線路不能與障礙物相交。

其中，兩條相鄰路徑之間的距離可用式(3)表示。

(3)

則適應(yīng)度函數(shù)應(yīng)該為式(4)。

(4)

式中，cmax與當(dāng)時(shí)的環(huán)境復(fù)雜程度有關(guān)；α表示懲罰系數(shù)；smin表示最短距離。由式(4)可知，適應(yīng)度函數(shù)在取得最短路徑時(shí)不會(huì)碰到障礙物。

2.4 遺傳算法

(1) 選擇操作

選擇操作的實(shí)質(zhì)是從當(dāng)代的種群中選出優(yōu)秀的個(gè)體，從而讓這些優(yōu)秀的個(gè)體進(jìn)行遺傳的過程。其主要方法有輪盤賭方法、保留最優(yōu)個(gè)體法、聯(lián)賽選擇法[13]。其中輪盤賭選擇優(yōu)良個(gè)體的隨機(jī)性比較大，是一種概率的選擇方法，并不能夠很好地保證下一代個(gè)體的優(yōu)良性。保留最優(yōu)個(gè)體的方法實(shí)際上是選擇適應(yīng)度比較高的個(gè)體，為了能夠更好地遺傳到下一代，不參與任何運(yùn)算的操作，但容易形成局部最優(yōu)。本研究中選擇聯(lián)賽選擇和保留最優(yōu)個(gè)體相結(jié)合的方法，這種方法的實(shí)質(zhì)是每次都要從群體中選擇幾個(gè)適應(yīng)度較高的優(yōu)良個(gè)體，保留到下一代。直到所選擇的個(gè)體數(shù)量達(dá)到種群規(guī)模的要求。這種選擇方法既保持了種群個(gè)體的多樣性，又保證了進(jìn)化的方向，加快了收斂速度。

(2) 交叉操作

交叉操作是根據(jù)染色體基因進(jìn)行交叉，從而將上一代的優(yōu)良基因傳給下一代的一個(gè)操作過程[14]。采用傳統(tǒng)方法的交叉是將種群內(nèi)部的個(gè)體進(jìn)行匹配，對(duì)于任何一個(gè)個(gè)體的匹配，都是以一定的概率來(lái)交換他們的部分染色體，這樣會(huì)導(dǎo)致一些優(yōu)良的個(gè)體被破壞。所以本研究采用的是一種啟發(fā)式交叉算法。這種算法主要是根據(jù)上一代個(gè)體適應(yīng)度來(lái)產(chǎn)生新一代的過程。在這個(gè)過程中應(yīng)選擇距離最小的節(jié)點(diǎn)作為交叉點(diǎn)。這種方法不僅保留了上一代的優(yōu)良基因，還可以使節(jié)點(diǎn)間的距離最小。

(3) 變異操作

首先從種群中隨機(jī)選取兩個(gè)即將變異的個(gè)體的兩個(gè)節(jié)點(diǎn)P1和P2，然后把新生成的P1到P2間的路徑代替原來(lái)按照初始種群生成一條從P1到P2的平滑路徑[15]，如果在變異的過程中沒有發(fā)生變化，則變異無(wú)效，這個(gè)時(shí)候要按照原來(lái)的方法重新生成新的個(gè)體，再用變異操作進(jìn)行相應(yīng)的處理。

3 算法實(shí)現(xiàn)及結(jié)果分析

這種改進(jìn)型的遺傳算法通過選擇、交叉、變異等遺傳操作產(chǎn)生一組新的個(gè)體，然后對(duì)所產(chǎn)生的各個(gè)體進(jìn)行模擬退火過程，以其結(jié)果作為下一代群體中的個(gè)體。

算法設(shè)計(jì)原則如下。

(1) 與任何障礙物不發(fā)生碰撞；

(2) 路徑盡可能短,運(yùn)行時(shí)間盡可能少；

(3) 應(yīng)與障礙物保持一定的安全距離；

(4) 路徑曲線盡可能平滑。

該算法的基本流程圖如圖1所示。

圖1 改進(jìn)遺傳算法流程圖

本研究是在MATLAB的環(huán)境下進(jìn)行仿真運(yùn)行的。首先將傳統(tǒng)的遺傳算法與改進(jìn)的遺傳算法進(jìn)行比較，如圖2、圖3所示。

圖2 基本遺傳算法的最優(yōu)解的進(jìn)化曲線

圖3 改進(jìn)遺傳算法的最優(yōu)解的進(jìn)化曲線

圖2是采用傳統(tǒng)的遺傳算法得到的最優(yōu)的結(jié)果，而圖3是采用改進(jìn)后的遺傳算法得到的最優(yōu)結(jié)果，由這兩個(gè)圖可以看出傳統(tǒng)遺傳算法和改進(jìn)后的遺傳算法的解和種群均值的變化，傳統(tǒng)遺傳算法在70和200代左右就會(huì)容易陷入局部最優(yōu)解，沒有達(dá)到理想的效果。而經(jīng)過改進(jìn)后的遺傳算法在第40代左右基本上穩(wěn)定于一個(gè)值，從而確保了種群中的解的質(zhì)量，這種改進(jìn)的算法既保證了種群個(gè)體的多樣性，又避免優(yōu)良個(gè)體被破壞的可能。該算法克服了陷入局部最優(yōu)解的缺點(diǎn)，能夠搜索到全局的最優(yōu)解，具有快速收斂的能力。采用改進(jìn)型的遺傳算法的收斂曲線基本上也在40代左右趨于一個(gè)穩(wěn)定的值，其具體的變化過程如圖4所示。

圖4 最小路徑長(zhǎng)度的收斂曲線

由圖3和圖4可以得出選取遺傳代數(shù)為200代，種群初始規(guī)模為50，交叉概率為0.7，變異概率為0.001，相應(yīng)的參數(shù)設(shè)置可以參考文獻(xiàn)[7]，采用上述參數(shù)，同時(shí)也是為了說明改進(jìn)型的遺傳算法在動(dòng)態(tài)路徑規(guī)劃中的應(yīng)用，本研究對(duì)改進(jìn)后的遺傳算法(模擬退火的遺傳算法)進(jìn)行了仿真研究，其仿真圖如圖5所示。

由圖5可知該算法在不觸碰障礙物的條件下，由起點(diǎn)到終點(diǎn)的一個(gè)過程，從而獲得了一個(gè)較短的路徑。圖5很好地說明了改進(jìn)遺傳算法在移動(dòng)機(jī)器人路徑規(guī)劃中的應(yīng)用。

為了進(jìn)一步說明改進(jìn)后的遺傳算法的有效性及可行性，本研究再一次對(duì)改進(jìn)型的遺傳算法進(jìn)行了仿真，如圖6所示。

圖6 改進(jìn)遺傳算法的仿真實(shí)驗(yàn)圖

由圖6可知，該機(jī)器人從起始位置(5,5)到達(dá)目標(biāo)位置(25,25)的運(yùn)動(dòng)軌跡，該運(yùn)動(dòng)軌跡不僅很好地避開了障礙物，還能夠順利地到達(dá)目標(biāo)位置，完成相應(yīng)的任務(wù)。

4 總結(jié)

改進(jìn)型遺傳算法主要是結(jié)合了模擬退火算法，這樣可以很好地保證了種群中的個(gè)體多樣性，改善了基本遺傳算法的收斂速度，增強(qiáng)了該算法的全局搜索的能力。實(shí)驗(yàn)結(jié)果表明該算法具有比較好的收斂能力，能夠克服傳統(tǒng)遺傳算法存在局部最優(yōu)解的問題，還能夠有效地避開障礙物，以較短的路徑到達(dá)目標(biāo)點(diǎn)，對(duì)后續(xù)有關(guān)機(jī)器人的運(yùn)動(dòng)軌跡及相應(yīng)任務(wù)的研究奠定了基礎(chǔ)。