基于粒子群優(yōu)化的多路徑規(guī)劃方法研究

王 丹

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

基于粒子群優(yōu)化的多路徑規(guī)劃方法研究

王 丹

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

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

粒子群優(yōu)化;多路徑規(guī)劃;多種群進化

0 引言

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

1 多路徑規(guī)劃算法的基本思想

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

2 多路徑規(guī)劃算法設(shè)計

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

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

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

3 粒子群的多樣化

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

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

3.1 粒子聚類分析方法

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

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

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

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

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

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

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

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

3.2 多樣化結(jié)束條件

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

1)粒子群經(jīng)聚類分析后得到的子群體穩(wěn)定，且沒有丟失。

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

3.3 粒子更新策略

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

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

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

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

3.4 適應(yīng)值評價與共享

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

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

4 多群體的隔離進化

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

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

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

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

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

5 算法仿真及分析

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

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

圖4給出了多路徑規(guī)劃仿真實驗的結(jié)果。

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

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

6 結(jié)語

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

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

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

［1］張京娟.基于遺傳算法的水下潛器自主導(dǎo)航規(guī)劃技術(shù)研究［D］.哈爾濱:哈爾濱工程大學(xué)，2003.1－30.

［2］劉利強.蟻群優(yōu)化方法研究及其在潛艇導(dǎo)航規(guī)劃中的應(yīng)用［D］.哈爾濱:哈爾濱工程大學(xué)，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］劉鐵男，陳廣義，劉延力，徐寶昌.模擬生物種族形成的進化算法與多峰函數(shù)優(yōu)化［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－)，女，碩士，助理工程師，研究方向為導(dǎo)航、制導(dǎo)與控制。