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

周加全

(廣西科技師范學院， 數(shù)學與計算機科學學院， 廣西 來賓 546199)

0 引言

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

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

1 模擬退火算法的思想

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

2 改進遺傳算法的設計

2.1 編碼

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

2.2 種群初始化

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

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

(1)

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

(2)

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

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

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

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

(3)

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

(4)

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

2.4 遺傳算法

(1) 選擇操作

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

(2) 交叉操作

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

(3) 變異操作

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

3 算法實現(xiàn)及結果分析

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

算法設計原則如下。

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

(2) 路徑盡可能短,運行時間盡可能少；

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

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

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

圖1 改進遺傳算法流程圖

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

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

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

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

圖4 最小路徑長度的收斂曲線

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

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

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

圖6 改進遺傳算法的仿真實驗圖

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

4 總結

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