基于混合遺傳粒子群優(yōu)化算法的層次路徑規(guī)劃方法

歐陽海濱，全永彬，高立群，鄒徳旋

(1.廣州大學 機械與電氣工程學院,廣東 廣州 510006；2.東北大學 信息科學與工程學院,遼寧 沈陽 110819；3.江蘇師范大學 電氣工程及自動化學院，江蘇 徐州 221116)

0 引言

21世紀以來，隨著機器人在搜索救援、醫(yī)療援助、偵察和行星探測等領域的廣泛應用[1]，路徑規(guī)劃逐漸進入研究人員的視野，并成為當今機器人領域的一項重要研究課題。通常，路徑規(guī)劃分為環(huán)境建模、路徑搜索、路徑優(yōu)化這3個重要環(huán)節(jié)。針對第一層環(huán)境建模，常用的方法有C空間法[2]、柵格法[3]、自由空間法[4]、voronoi圖法[5]及三角形法[6]；針對第二、三層的路徑搜索和優(yōu)化，過去常用的方法有人工勢場法[7]、模擬退火算法[8-9]、蟻群算法[10-11]等，現(xiàn)在常用的方法有神經(jīng)網(wǎng)絡算法[12]、遺傳算法[13]和粒子群優(yōu)化算法[14-15]。其中，遺傳算法是由美國的Holland[16]于1975年首先提出一類借鑒生物界的進化規(guī)律演化而來的隨機搜索方法。遺傳算法具有良好的全局搜索能力，但遺傳算法對初始種群有較強的依賴性且搜索效率低。粒子群優(yōu)化算法是近年來由Eberhart等[14]開發(fā)的一種模擬鳥群覓食新的優(yōu)化算法，它通過追隨當前搜索到的最優(yōu)值來尋找全局最優(yōu)。同遺傳算法比較，粒子群優(yōu)化算法也屬于迭代算法，其優(yōu)勢在于操作簡單且搜索效率更高但易陷入局部最優(yōu)。

然而，上述單獨任何一種路徑規(guī)劃算法在耗時較少并且復雜的環(huán)境下不能得到最優(yōu)或次優(yōu)路徑。于是，研究人員考慮在機器人工作過程中利用層次結構結合各算法優(yōu)點進行路徑規(guī)劃。Zuo等[17]提出了一種用于復雜環(huán)境下移動機器人導航的層次路徑規(guī)劃方法。他們在第一層中利用基于網(wǎng)格的A算法快速查找初始幾何路徑，然后在第二層利用最小二乘策略迭代生成平滑的路徑。Yang等[18]提出了一種針對動態(tài)環(huán)境的基于模糊邏輯的分層目標運動規(guī)劃策略。首先，他們在第一層中利用全局目標信息和遠程感知信息生成中間路徑節(jié)點(即子目標)，然后在第二層中利用近程感知信息引導移動機器人避開障礙物的同時到達子目標。Mac等[19]提出了一種基于混沌環(huán)境的移動機器人層次全局路徑規(guī)劃方法。他們在第一層中采用三角型法進行環(huán)境建模，在第二層應用Dijkstra算法尋找初始幾何路徑，最后提出了一種新的粒子群優(yōu)化方法——約束多目標粒子群優(yōu)化方法來優(yōu)化路徑。

考慮單獨的路徑規(guī)劃算法存在著缺陷，筆者提出了基于混合遺傳粒子群優(yōu)化算法的層次路徑規(guī)劃方法。該方法的主要創(chuàng)新點：一是采用以時間為序的層次結構在路徑規(guī)劃過程中結合了三角形法、改進遺傳算法和粒子群優(yōu)化算法，實現(xiàn)復雜環(huán)境下的移動機器人路徑規(guī)劃；二是利用人工勢場法的方向性改進了遺傳算法，提高了遺傳算法的搜索效率。

1 相關工作

1.1 路徑規(guī)劃

快速有效的路徑規(guī)劃是移動機器人正常完成其作業(yè)的重要保證。根據(jù)移動機器人對環(huán)境信息的掌握程度可以將路徑規(guī)劃分為基于先驗信息的全局路徑規(guī)劃和基于傳感器信息的局部路徑規(guī)劃。層次路徑規(guī)劃，是指把路徑規(guī)劃分為環(huán)境建模、路徑搜索和路徑優(yōu)化3個基本環(huán)節(jié)，然后按時間順序操作每個環(huán)節(jié)逐步實現(xiàn)路徑規(guī)劃。在操作每個環(huán)節(jié)的過程中，可以使用同一算法或不同算法。

1.2 遺傳算法

遺傳算法是一種基于“適者生存、優(yōu)勝劣汰”原則的隨機搜索的優(yōu)化算法。遺傳算法模擬了達爾文自然選擇、物競天擇、適者生存的進化論，通過多代的選擇、交叉、變異等操作進化出問題的最優(yōu)解?；具z傳算法包含3種遺傳算子：選擇算子，交叉算子，變異算子。

1.2.1 選擇算子

從種群中選擇優(yōu)秀個體，淘汰劣質(zhì)個體的操作叫選擇。選擇的目的是把已優(yōu)化的個體通過交叉產(chǎn)生新的個體遺傳到下一代或直接復制到下一代。選擇操作是建立在種群中個體的適應度評估基礎上的。目前常用的選擇方法有以下幾種：適應度比例方法、隨機遍歷抽樣法、局部選擇法，其中適應度比例法是最簡單也是最常用的方法。個體li被選擇的概率：

(1)

式中：M為種群規(guī)模；i、j為個體序號；f為個體的適應度。

1.2.2 交叉算子

父代個體l1[24，64，10，13，4，15，26]；

父代個體l2[24，39，23，3，13，10，6，26]。

可以看出，兩父代個體的共有節(jié)點為10、13，隨機選擇其中一個節(jié)點作為切斷位置。假如選擇的是13，交叉后的子代個體如下：

1.2.3 變異算子

變異操作是指對種群中的個體的某些基因座上的基因值作變動。一般來說，變異算子操作的基本步驟如下：

Step1對種群中所有個體以事先設定的變異概率判斷其是否進行變異。

Step2對要進行變異的個體隨機選擇變異位置進行變異。

1.3 粒子群優(yōu)化算法

粒子群優(yōu)化算法是一種模擬鳥群覓食的優(yōu)化算法，它通過追隨當前搜索到的最優(yōu)值來尋找全局最優(yōu)。在粒子群優(yōu)化算法中，每個優(yōu)化問題的解都是搜索空間中的一只鳥，稱之為“粒子”，以符號p表示。所有的粒子都有一個由被優(yōu)化的函數(shù)決定的適應值，還有一個速度決定它們飛翔的方向和距離。在每一次迭代中，粒子通過跟蹤兩個“極值”來更新自己的速度及位置。第一個極值是粒子本身所找到的最優(yōu)解，這個解叫作個體極值。另一個極值是整個粒子群當前找到的最優(yōu)解，這個解叫作全局極值。

粒子速度、位置更新公式如下：

v(k+1)=c1·rand·(pBest(k)-p(k))+

c2·rand·(gBest(k)-p(k))+

w·v(k)；

(2)

p(k+1)=p(k)+v(k+1)，

(3)

式中：w為慣性權重；v(k)為k時刻粒子的速度；p(k)為k時刻粒子的位置；pBest(k)為k時刻粒子本身所找到的最好位置；gBest(k)為k時刻整個粒子群目前找到的最優(yōu)位置；rand為介于0～1之間的隨機因子；c1、c2是學習因子。

2 以時為序的多算法融合層次路徑規(guī)劃方法的設計

2.1 環(huán)境建模

環(huán)境建模是路徑規(guī)劃的基礎環(huán)節(jié)，其目的是建立一個便于計算機進行路徑規(guī)劃所使用的環(huán)境模型，即將實際的物理空間抽象成算法能夠處理的抽象空間，實現(xiàn)相互間的映射。盡管柵格法在路徑規(guī)劃環(huán)境建模中有廣泛的應用，但考慮其把現(xiàn)實物理空間過于理想化，筆者使用更加接近真實環(huán)境的三角形法對移動機器人的自由活動空間進行建模。三角形法是基于可視圖法創(chuàng)建的一種新的二維地圖構建方法，其作用是把除障礙物外的自由空間劃分為若干個鄰域相通三角形。具體實現(xiàn)步驟如下：

Step1將多邊形障礙物的頂點及運動空間的4個頂點進行相互連接。

Step2將頂點與頂點之間的線段兩兩進行比較。判斷兩線段是否相交，若相交，去除比較長的線段。

Step3判斷線段的兩頂點是否屬于同一多邊形障礙物,若是，刪除對應的線段。

Step4計算剩下所有線段的中點，并按其對應線段的長短由短到長進行標號排序。

至此，移動機器人的自由活動空間已被劃分為由若干個相互連通的三角形組成的環(huán)境模型，如圖1所示。

圖1 環(huán)境模型Figure 1 Environment model

2.2 改進遺傳算法的設計及初次路徑規(guī)劃

2.2.1 路徑編碼

路徑編碼是實現(xiàn)遺傳算法的重要環(huán)節(jié)，筆者以移動機器人從起點到終點所經(jīng)過的所有中點序號的集合表示一個個體，每個個體代表一條路徑，所有個體的集合代表一個種群。例如，圖1中，[24 40 43 31 25 41 44 26]可以表示由start(24)到goal(26)的某條路徑編碼。

2.2.2 種群初始化

種群初始化是遺傳算法必要的步驟，初始種群的質(zhì)量嚴重影響遺傳算法路徑搜索的結果。一般來說，遺傳算法中的初始種群是隨機產(chǎn)生的。盡管這種隨機產(chǎn)生種群的方式很簡單，但是由于產(chǎn)生的個體質(zhì)量通常不高，會導致遺傳算法收斂速度慢，最終影響路徑規(guī)劃的效率。因此，提高初始種群的質(zhì)量，對提高遺傳算法的性能有重大的意義。

人工勢場法基本思想是將機器人在周圍環(huán)境中的運動設計成一種抽象的人造引力場中的運動，目標點對移動機器人產(chǎn)生“引力”，障礙物對移動機器人產(chǎn)生“斥力”，最后通過求合力來控制移動機器人的運動。筆者采用人工勢場法的“引力”思想來改進傳統(tǒng)遺傳算法的種群初始化過程，移動機器人的引力勢函數(shù)可以表示為：

(4)

式中：katt代表引力比例因子，設為1；i為移動機器人當前點的中點序號；g為目標點序號；x為序號對應的實際坐標位置；Uatt為引力勢函數(shù)。

引力F通常取引力勢函數(shù)的負梯度：

F(i，g)=-Uatt(i，g)=-katt|xi-xg|。

(5)

利用人工勢場法初始化種群的具體步驟如下：

Step1初始化相關參數(shù)，包括移動機器人的起始點s、目標點g、種群規(guī)模M等。

Step2尋找移動機器人下一步的可選點集合V，即尋找與移動機器人相鄰的點。這里相鄰的點，是指以移動機器人當前點所在的邊構成的兩個連通三角形對應邊上的點，如圖1所示，start(24)相鄰的點為34、39和40。

Step3計算移動機器人下一步可選點集合V中所有點可選的概率pij，其公式如下：

(6)

式中：i表示移動機器人當前點的序號；j表示下一步可選點的序號；g為目標點序號;Fjg表示目標點g對j點的引力。

Step4判斷移動機器人是否經(jīng)過目標點g，若是，則成功生成一個個體；若否，則回到Step 2。

Step5判斷種群規(guī)模是否達到M，若是，停止種群初始化；若否，移動機器人回到起始點s,繼續(xù)產(chǎn)生個體。

2.2.3 優(yōu)化種群

(1)刪除冗余。在初始化種群的過程中，為了確保遺傳算法的全局性，常需要隨機搜索產(chǎn)生個體。然而，隨機搜索意味著產(chǎn)生的個體存在重復路徑，這會影響遺傳算法的效率，因此需要刪除冗余。假設生成的初始路徑個體l為[22，35，67，34，45，67，24，67，44],刪除冗余的具體步驟如下：

Step1判斷路徑個體l是否存在相同元素，若是，繼續(xù)下一步；若否，退出。

Step2查找相同元素所在數(shù)組中對應的位置，將位置相差最大的兩相同元素之間的元素全部刪除，包括兩相同元素的其中一個。如路徑個體l中，相同元素為67，所在數(shù)組中的位置分別為3、6和8，因此應將位置3和8之間的元素全部刪除，包括位置8的元素。刪除后的路徑個體l為[22，35，67，44]。

Step3繼續(xù)判斷路徑個體l是否存在相同元素，若是，返回step 2；若否，退出。圖2是路徑個體刪除冗余的示意圖。

圖2 刪除冗余示意圖Figure 2 The schematic of removing the redundace

(2)判斷三角形。在初始種群的過程中，生成的路徑個體可能存在一些不必要的路徑點，導致遺傳算法的搜索效率降低。判斷路徑個體相鄰的3個路徑點對應的邊是否可以組成1個三角形來刪除這些不必要的點。圖3是判斷三角形前后的路徑個體對比圖。

圖3 判斷三角形Figure 3 Judging triangle

2.2.4 交叉、變異操作

為了保證路徑的連續(xù)性，本文的交叉操作采用1.2.2所述的單點交叉方式，交叉操作的步驟如下：

Step1對種群中個體以事先設定的交叉概率判斷其是否進行交叉。

Step2從種群中隨機抽取另外一個個體，判斷其與需要交叉的個體是否存在相同的路徑點，若是，進行單點交叉；若否，繼續(xù)下一步。

Step3是否遍歷種群所有個體，若是，結束；若否，返回Step 1。

由于產(chǎn)生的初始種群均為連續(xù)路徑，若采用隨機變異操作將使間斷路徑導致種群退化。為解決這個問題，筆者首先隨機選取需變異個體兩個路徑點，然后將兩個路徑點間所有路徑點刪除，然后用種群初始化辦法修補間斷路徑，修補后的路徑個體為已經(jīng)變異的個體。

2.3 基于粒子群算法的路徑優(yōu)化

2.3.1 粒子群初始化

粒子群初始化是實現(xiàn)粒子群優(yōu)化算法的基本步驟。在已獲得初始全局最優(yōu)路徑的情況下，筆者將初始全局最優(yōu)路徑作為粒子群算法的初始粒子產(chǎn)生的母體，這里稱之為粒子母體。初始的全部粒子均由粒子母體隨機擴展產(chǎn)生，如圖4所示。粒子群初始化的步驟具體如下：

圖4 粒子群初始化Figure 4 The initialization of particle swarm

Step1初始化相關參數(shù)，包括粒子群規(guī)模M等。

Step2在粒子母體每個路徑點對應的線段上隨機生成一個子路徑點，所有的子路徑點的集合p表示為一個 隨機生成的子粒子，這里的每個粒子和遺傳算法中的個體含義一樣，也代表一條路徑。

Step3判斷是否達到粒子群規(guī)模M，若是，結束；反之，回到Step 2。

2.3.2 適應度函數(shù)

在粒子群迭代尋找最優(yōu)路徑的過程中，需要一個目標函數(shù)來約束粒子群的運動，以達到優(yōu)化路徑的期望，筆者以路徑最短作為迭代過程中粒子的約束條件。粒子的適應度計算公式如下：

(7)

f(p)=D(p)，

(8)

式中:xi為第i個路徑點的位置；xi+1為第i+1個路徑點的位置；p為粒子；n為該粒子含有路徑點的總數(shù)；D為粒子長度；f為粒子的適應度，在粒子群迭代的過程中，筆者期望其最小化。

2.4 全局層次路徑規(guī)劃的實現(xiàn)

圖5是全局層次路徑規(guī)劃的實現(xiàn)流程。筆者將移動機器人的路徑規(guī)劃按時間順序分為3個層次。第1層是采用三角形法進行環(huán)境建模；第2層是采用筆者所設計的改進遺傳算法進行初次路徑規(guī)劃以尋找初始全局最優(yōu)路徑；第3層是在獲取初始全局最優(yōu)路徑的情況下，運用粒子群優(yōu)化算法對初始最優(yōu)路徑進一步優(yōu)化以獲得全局最優(yōu)路徑。

圖5 全局層次路徑規(guī)劃的實現(xiàn)流程Figure 5 The process of global hierarchical path planning

需要注意的是，在第2層遺傳迭代搜索初始全局路徑的過程中，種群中的個體的約束函數(shù)和第3層的粒子約束函數(shù)一樣，即式(8)。

3 仿真實驗結果與分析

為了驗證基于混合遺傳粒子群優(yōu)化算法的層次路徑規(guī)劃方法的有效性和可行性，筆者對該方法進行了仿真，圖6是層次路徑規(guī)劃的結果。該實驗中，設置了3個目標點，其中綠色實線是程序執(zhí)行完第2層獲得初始全局最優(yōu)路徑，紅色虛線是執(zhí)行完第3層程序的優(yōu)化結果。實驗結果表明，筆者設計的全局層次路徑規(guī)劃方法是有效的。

圖6 全局層次路徑規(guī)劃Figure 6 Global hierarchical path planning

圖6實驗的參數(shù)設置：針對第2層改進遺傳算法，初始種群規(guī)模M=10，最大迭代次數(shù)n1=15，交叉概率pc=0.5，變異概率pm=0.5；針對第3層粒子群優(yōu)化算法，初始粒子群規(guī)模M=100,最大迭代次數(shù)n2=50，學習因子c1=0.2，c2=0.1，慣性權重w=0.15。

為了更清楚觀察全局層次路徑規(guī)劃方法各層次的工作效率，設定移動機器人從start運動到goal2，在路徑長度幾乎一致的情況下，做了3次獨立實驗，并分別統(tǒng)計每次實驗各層所花費的時間。表1是移動機器人在各層所損失時間的仿真結果(表中第2層的時間分別為采用傳統(tǒng)遺傳算法和筆者設計的改進遺傳算法所消耗的時間，括號內(nèi)是改進后的時間)。

表1實驗結果表明，主要影響全局層次路徑規(guī)劃方法的工作效率是第2層搜索初始全局最優(yōu)路徑的過程，而筆者提出的改進遺傳算法在搜索初始全局最優(yōu)路徑的過程中所耗費的時間遠比傳統(tǒng)遺傳算法少，能夠提高全局層次路徑規(guī)劃方法的整體效率。

表1 層次路徑規(guī)劃各層的時間損失Table 1 Time loss of layers in hierarchical path planning s

為了觀察所設計的層次路徑規(guī)劃方法時移動機器人路徑長度隨時間的變化，設定移動機器人從start運動到goal2,圖7是路徑長度隨時間的變化結果。圖7中，橫坐標表示層次路徑規(guī)劃方法的整體迭代次數(shù)，包括第2層的遺傳迭代次數(shù)和第3層的粒子群迭代次數(shù)。綠色虛線左半部分，表示程序正在執(zhí)行第2層搜索初始全局最優(yōu)路徑的操作，15為改進遺傳算法設置的迭代次數(shù)。綠色虛線右半部分表示程序正在執(zhí)行第3層優(yōu)化路徑操作，此時粒子群的迭代次數(shù)設置為50。圖7結果表明，針對第2層改進遺傳算法，其最佳迭代次數(shù)為12左右；針對第3層粒子群優(yōu)化算法，其最佳迭代次數(shù)為25左右。

圖7 路徑長度變化Figure 7 Change of path length

為了進一步比較所設計的層次路徑規(guī)劃方法和當今主流算法性能的差異，在設定移動機器人從start運動到goal2的情況下，圖8和表2分別是采用筆者提出的層次路徑規(guī)劃算法和采用文獻[20]中的改進差分進化算法進行路徑規(guī)劃實際效果圖和數(shù)值比較表。

圖8 層次規(guī)劃法和差分進化法對比Figure 8 Comparison between hierarchical planning and differential evolution

表2 數(shù)值比較Table 2 Numerical comparison s

圖8中，采用文獻[19]中的改進差分進化方法進行路徑規(guī)劃時需要先用外接圓將多邊形障礙物覆蓋起來，外接圓內(nèi)均為不可運動空間。針對表2，分別為6次實驗中移動機器人從start運動到goal2的最短距離的最大值、最小值、平均值、均方根和平均耗時。其結果表明，在相同的環(huán)境和目標要求下，筆者提出層次路徑規(guī)劃算法和文獻[20]中改進差分進化算法均能獲得較好的結果，層次路徑規(guī)劃方法的穩(wěn)定性和搜索效率優(yōu)于改進差分進化算法。

4 結論

仿真結果表明，筆者提出的基于混合遺傳粒子群優(yōu)化算法的全局層次路徑規(guī)劃方法能夠在復雜的環(huán)境中快速有效地尋找到無碰撞、最優(yōu)的路徑。同時，提高了遺傳算法的搜索效率，使得層次路徑規(guī)劃方法整體上的搜索效率高于現(xiàn)階段一些主要的算法。