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

王 丹

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

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

王 丹

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

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

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

0 引言

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

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

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

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

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

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

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

3 粒子群的多樣化

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

下面對(duì)粒子群多樣化過(guò)程中的幾個(gè)主要內(nèi)容進(jìn)行詳細(xì)說(shuō)明。

3.1 粒子聚類(lèi)分析方法

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

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

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

1)取第1個(gè)粒子c1，令其屬于聚類(lèi)Z1，即 c1∈Z1。

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

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

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

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

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

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

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

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

3.3 粒子更新策略

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

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

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

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

3.4 適應(yīng)值評(píng)價(jià)與共享

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

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

4 多群體的隔離進(jìn)化

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

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

由于粒子群多樣化后形成的每個(gè)子群體是圍繞在1個(gè)局部最優(yōu)周?chē)纬傻男…h(huán)境，每個(gè)子群體應(yīng)只含有1個(gè)最優(yōu)解，沒(méi)有陷入局部最優(yōu)的顧慮，因此，對(duì)于每個(gè)子群體采用標(biāo)準(zhǔn)粒子群算法進(jìn)行求解。

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

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

5 算法仿真及分析

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

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

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

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

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

6 結(jié)語(yǔ)

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

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

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

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

［2］劉利強(qiáng).蟻群優(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］劉鐵男，陳廣義，劉延力，徐寶昌.模擬生物種族形成的進(jìn)化算法與多峰函數(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－)，女，碩士，助理工程師，研究方向?yàn)閷?dǎo)航、制導(dǎo)與控制。