基于粒子群優化的多路徑規劃方法研究

王 丹

(中國艦船研究院，北京 100192)

基于粒子群優化的多路徑規劃方法研究

王 丹

(中國艦船研究院，北京 100192)

借鑒遺傳算法求解多峰函數優化問題的思想，開展了基于粒子群優化的多路徑規劃方法研究。給出了多路徑規劃算法的基本思想和算法流程，討論了算法中粒子群的多樣化方法以及多種群的隔離進化策略，并針對多個仿真環境進行了仿真實驗。仿真結果表明，本文設計的多路徑規劃算法能針對不同的環境模型進行環境劃分，正確、有效地規劃出多條運動路徑。

粒子群優化;多路徑規劃;多種群進化

0 引言

全局路徑規劃是船舶智能化航行的關鍵技術之一，其主要任務是在對環境已知的情況下，使船舶避開環境中的障礙物，按照某一最優指標安全到達預定的位置［1－2］。在通常的路徑規劃算法中，對規劃路徑優劣的評價完全是依靠適應值評價函數來進行的，算法求得的最優路徑的性能與評價函數密切相關。但在實際使用過程中，由于路徑規劃問題本身的復雜性、船舶運動的復雜性以及外部環境的復雜性，采用任何一個單一的評價函數都是不完善的，很難用一個統一的適應值評價函數把所有要考慮的重要因素都包括進去。而且，人的思維總有一定的片面性，不能兼顧到所有的限制因素。因此，本論文借鑒遺傳算法求解多峰函數優化問題的思想［3－5］，在標準粒子群優化算法的基礎上設計了多路徑規劃算法，并通過對多個不同環境的仿真實驗，驗證了算法的正確性和有效性。

1 多路徑規劃算法的基本思想

多路徑規劃的目的是同時尋找多個最優及次優可行路徑，供決策者選擇使用。也就是說，規劃算法不僅要搜索到全局最優解，同時還要獲得若干個次優解。由此看來，多路徑規劃問題也就是多峰函數優化問題。本文設計的多路徑規劃算法的思想是以標準粒子群算法為基本算法，借鑒并結合遺傳算法多峰函數優化求解中的適應值共享技術和多種群進化策略，從而實現群體的多樣性，同時獲得若干最優和次優解。

2 多路徑規劃算法設計

多路徑規劃算法流程如圖1所示。算法主要分為粒子群多樣化和多群體隔離進化2個階段，每個階段的算法均在文獻［6］給出的標準粒子群算法模型的基礎上改進得到。

圖1 多路徑規劃算法基本流程Fig.1 Basic flow chart of multi-path planning method

粒子群多樣化階段主要是進行全局搜索，通過在標準粒子群算法的基礎上引入聚類分析和適應值共享等策略，從而確保粒子的充分多樣化，產生大量符合不同特性的子群體;多群體隔離進化階段主要是進行局部開發，通過在多個子群體間采用隔離進化策略，從而確保多路徑的快速生成。

3 粒子群的多樣化

粒子群的多樣化階段算法流程如圖2所示。算法首先對所有粒子進行聚類分析，形成多個子群體;然后對各粒子進行適應值評價與共享，并采用標準粒子群算法進行位置、速度更新;當粒子位置更新后，得到子代粒子，在子代粒子和父代粒子中進行粒子選取。算法重復執行，直到滿足多樣化結束條件為止。

下面對粒子群多樣化過程中的幾個主要內容進行詳細說明。

3.1 粒子聚類分析方法

粒子聚類分析的目的是要按照各粒子所代表路徑的不同特點將整個粒子群劃分為多個子群體，從而保證具有不同特性的各子群體均能被充分的多樣化。該方法將各粒子所代表的路徑之間是否存在障礙物作為聚類分析的判據。若2個粒子所代表的路徑之間不存在障礙物，則這2個粒子屬于同1個子群體;若2個粒子所代表的路徑之間存在障礙物，則這2個粒子屬于不同的子群體。這樣，所有的粒子就按其所對應路徑的空間分布被聚類為多個子群體。

圖2 粒子群多樣化階段算法流程Fig.2 Algorithm flow chart of particle swarm diversified moment

假設粒子群 C 表示為{c1，c2，…，cN}，其中，N 為粒子個數，ci(i=1，2，…，N)為粒子群中的任意粒子。粒子群聚類后形成的子群體表示為Z={Z1，Z2，…，ZpopNum}，其中，popNum 為聚類個數，Zi(i=1，2，…，popNum)代表聚類后的各子群體。則粒子群聚類分析的具體過程如下:

1)取第1個粒子c1，令其屬于聚類Z1，即 c1∈Z1。

2)計算c2與Z1中任意粒子所代表的路徑之間是否存在障礙物，若不存在障礙物，則c2∈Z1;否則，形成新聚類 Z2，即 c2∈Z2。

3)假設在2)中，粒子c1和c2分別屬于不同的聚類Z1和Z2。取粒子c3，計算該粒子與Z1和Z2中任意粒子所代表的路徑之間是否存在障礙物，若均存在障礙物，則形成新聚類Z3，即c3∈Z3;否則，粒子c3屬于聚類Z1或Z2。

4)按上述過程判斷剩余所有粒子。

重復上述過程，直至整個粒子群C中所有的粒子都已經被劃分進相應的子種群為止。同時計算子種群的個數和每個子種群中所擁有個體路徑的數量。

3.2 多樣化結束條件

粒子群多樣化的目的是為了確保生成的粒子能盡可能多的反映不同特性的路徑。在上面的內容中我們已經知道，每個子群體代表一類具有相同特性的路徑，因此，多樣化結束的選取條件如下:

1)粒子群經聚類分析后得到的子群體穩定，且沒有丟失。

2)每個子群體中的粒子數量要大于某一數值cNum(本文仿真實驗中取為20)。

3.3 粒子更新策略

在標準粒子群優化算法中，每次粒子位置更新和速度更新后，父代粒子被直接轉化為子代粒子。因此，算法尋優過程的每一迭代步中，粒子群的總數是不變的。而本文討論的用于求解多路徑規劃問題的粒子群優化算法需要充分實現粒子群的多樣化，子群體的數目是不定的，而且每個子群體中均要保證生成一定數量的粒子，因此，無法采用標準粒子群優化算法中的粒子更新策略。

在粒子群多樣化階段，粒子更新策略如下:

1)在每一迭代步粒子進行位置更新后，父代粒子要被保存，與子代粒子共同競爭，形成新的粒子。算法維持總的粒子數目取為1.5*popNum*cNum。其中，popNum為子群體個數，cNum為多樣化結束時每個子群體需要達到的粒子數目。

2)在每一迭代步中，若父代粒子與子代粒子的總和大于算法所要維持的總粒子數，則按適應值大小從高到低選取適量粒子保存即可;若父代粒子與子代粒子的總和小于算法所要維持的總粒子數，則保存所有粒子，待下一迭代步中再做判斷。

3.4 適應值評價與共享

適應值評價與共享首先采用適應值評價函數對各粒子所代表的路徑進行優劣評估，得到各路徑的適應值;然后采用適應值共享方式對各粒子適應值進行再處理，從而改善粒子群優化算法的全局搜索能力，保持粒子的多樣性。本文算法采用的適應值評價函數FitBase(c)和適應值共享處理函數Fit(c)分別如式(1)和式(2)所示:

式中:S(c)為路徑的安全性因素，用路徑到障礙物的最短距離來評估;D(c)為路徑的快速性因素，用路徑的總長度來評估;M(c)為路徑的適航性因素，用路徑的平滑程度來評估;w1，w2，w3分別為各因素的權值;Ni為粒子c所屬的第i個子群體中所含有的粒子數目;popNum為子群體的個數。

4 多群體的隔離進化

在粒子群多樣化階段結束后，算法進入多群體隔離進化階段。多群體隔離進化階段的算法流程如圖3所示。

圖3 多群體隔離進化階段算法流程Fig.3 Algorithm flow chart of evolution moment of multi-population segregation

由于粒子群多樣化后形成的每個子群體是圍繞在1個局部最優周圍形成的小環境，每個子群體應只含有1個最優解，沒有陷入局部最優的顧慮，因此，對于每個子群體采用標準粒子群算法進行求解。

由于算法在經過位置更新后，很有可能會跳出當前的子群體，從而產生不屬于該子群體的粒子。因此，在各子群體尋優一定代數后(本文取為10)，需要對所有粒子進行重新聚類分析。聚類分析的方法與第1.1節中所述方法相同。

在進行聚類分析后，新形成的各子群體中的粒子數會發生變化，需要進行子群體調整。對于粒子數大于cNum的子群體，按粒子適應值大小保存適應值最高的cNum個粒子;對于粒子數小于cNum的子群體，采用高斯變異方法生成新的粒子。算法如此循環，直至滿足總的迭代次數，或者各子群體收斂到各自的最優解。

5 算法仿真及分析

為測試本文提出的多路徑規劃算法的正確性和有效性，使用VC++6.0實現算法，在不同的環境下進行仿真實驗。

在算法運行過程中，粒子群初始規模設置為50個粒子。慣性權值w采用線性遞減策略，在粒子群的多樣化階段，慣性權值w的變化范圍取為wmax=0.5，wmin=0.2;在多群體隔離進化階段，慣性權值w的變化范圍取為wmax=0.95，wmin=0.2。參數c1和c2在算法中取相同數值2。粒子群多樣化階段的結束條件設置為每個子群體中的粒子數目不少于20個。多群體隔離進化階段的結束條件設置為算法外循環迭代100次或各子群體均收斂。即若在100次迭代過程中，各子群體均收斂到各自最優解，則算法退出，否則，算法迭代100次后退出。

圖4給出了多路徑規劃仿真實驗的結果。

圖4 多路徑規劃算法仿真實驗結果Fig.4 Simulation experimentation result of multi-path planning method

由該仿真結果可以看到，本文設計的基于粒子群優化的多路徑規劃方法能正確有效的規劃出多條路徑。但同時也看到，當障礙物離環境邊界較近或者環境較復雜時(例如仿真環境2～仿真環境4)，算法較難規劃出繞過邊界障礙的路徑。這一問題的出現一方面原因是當障礙物離環境邊界較近時，很難得到繞過障礙物和環境邊界的可行路徑，這就導致無法得到對應的子群體，因此無法規劃出相應路徑;另一方面原因是在評價路徑的適應值評價函數中，往往將路徑長度設置為主要的評價標準，而繞過邊界障礙的路徑一般會較長，因此無法得到與其相對應的路徑。

6 結語

本文針對船舶全局多路徑規劃問題展開研究，在基本粒子群優化算法的基礎上，引入聚類分析、隔離進化等策略實現多路徑規劃方法，給出了算法的設計思想、基本流程和主要設計內容，并針對多個仿真環境進行了仿真實驗，得到結論如下:

1)基于粒子群優化的多路徑規劃方法能針對不同的環境模型進行環境劃分，正確、有效的規劃出多條運動路徑。

2)當障礙物離環境邊界較近或者環境較復雜時，算法較難規劃出繞過邊界障礙的路徑，還有待進一步深入研究。

［1］張京娟.基于遺傳算法的水下潛器自主導航規劃技術研究［D］.哈爾濱:哈爾濱工程大學，2003.1－30.

［2］劉利強.蟻群優化方法研究及其在潛艇導航規劃中的應用［D］.哈爾濱:哈爾濱工程大學，2007.8－25.

［3］MILLER B L，SHAW M J.Genetic algorithms with dynamic niche sharing for multi-modal function optimization［C］.Proc 3rdIEEE Conf.Evolutionary Computation.Piscataway，NJ:IEEE Press.1996.786 －791.

［4］劉鐵男，陳廣義，劉延力，徐寶昌.模擬生物種族形成的進化算法與多峰函數優化［J］.控制與決策，1999，14(2):185－188.

［5］SPEARS W M.Simple sub-population schemes［C］.proc.of the third annual conference on evolutionary programming.San Diego，1994.296 －307.

［6］KENNEDY J，EBERHART R C.Particle swarm optimization［A］.Proceedings of IEEE International Conference on Neural Networks.Piscataway，1995.193 －197.

Research on multi-path planning method based on particle swarm optimization

WANG Dan
(China Ship Research and Development Academy，Beijing 100192，China)

Based on the idea of genetic algorithm to solve the multi-modal function optimization，research of multi-path planning method based on particle swarm optimization has been carried out.Basic idea and algorithm flow of multi-path planning algorithm were given，methods of particle swarm diversified and evolution strategy of multi-population segregation were discussed，and simulation experiments aimed at multiple simulation environments were performed.Simulation result shows，multi-path planning algorithm in this article can make environment division aimed at different environmental models and plan multiple motion paths rightly and efficiently.

particle swarm optimization;multi-path planning;multi-population evolution

O221

A

1672－7649(2011)06－0156－04

10.3404/j.issn.1672－7649.2011.06.036

2011－05－06

王丹(1983－)，女，碩士，助理工程師，研究方向為導航、制導與控制。