姜 彬， 喬紅宇， 施志剛

(1.江蘇航運(yùn)職業(yè)技術(shù)學(xué)院 機(jī)電工程系, 江蘇 南通 226000;2.江蘇航運(yùn)職業(yè)技術(shù)學(xué)院 輪機(jī)工程系, 江蘇 南通 226000)

0 引 言

航路規(guī)劃在存在一些障礙物的環(huán)境中，從一個(gè)初始位置S到達(dá)一個(gè)目標(biāo)位置G，通過(guò)一些優(yōu)化方法規(guī)劃出從初始位置能夠避開(kāi)障礙順利到達(dá)目標(biāo)位置的路徑。考慮航路規(guī)劃問(wèn)題本質(zhì)上是基于抽象環(huán)境的模型搜索優(yōu)化路徑問(wèn)題[1]。根據(jù)對(duì)環(huán)境的掌握情況，航路規(guī)劃可以劃分為全局規(guī)劃和局部規(guī)劃。目前對(duì)航路規(guī)劃問(wèn)題的求解算法主要有人工勢(shì)場(chǎng)法[2-3]、可視圖法[4-5]和智能規(guī)劃法[6-7]。

文中在研究各種改進(jìn)的螢火蟲(chóng)算法特點(diǎn)的基礎(chǔ)上，通過(guò)深入分析該問(wèn)題的特性,摒棄了以往算法的不足，采用了自適應(yīng)地選擇吸收系數(shù)γ和隨機(jī)系數(shù)α來(lái)增加算法的全局尋優(yōu)能力。針對(duì)傳統(tǒng)方法收斂慢的不足，提出了隨機(jī)步長(zhǎng)的改進(jìn)策略，在保證算法精確搜索的前提下，合理調(diào)整步長(zhǎng)來(lái)加快算法的收斂性。最后以仿真實(shí)驗(yàn)對(duì)比幾種算法的求解精度和速率，證明了文中提出改進(jìn)的螢火蟲(chóng)算法的有效性。

1 航路規(guī)劃問(wèn)題建模

1.1 航路規(guī)劃問(wèn)題任務(wù)描述

航路規(guī)劃是在一定的約束條件下設(shè)計(jì)和規(guī)劃航路，從而尋找到從出發(fā)點(diǎn)到目標(biāo)點(diǎn)的一個(gè)最優(yōu)路徑。例如無(wú)人機(jī)、無(wú)人地面探測(cè)車(chē)、無(wú)人水面艦艇等。它們需要在不同的場(chǎng)景下，規(guī)劃出不同的航路，從而完成相應(yīng)的任務(wù)，每次航行經(jīng)過(guò)的一些航路點(diǎn)順次連接起來(lái)的線(xiàn)段便是航路。航路規(guī)劃示意如圖1所示。

圖1 航路規(guī)劃示意圖

若用(r1,r2,…,rn)表示航路點(diǎn)序列，那么由該航路點(diǎn)構(gòu)成的航路可以表示為P=(S,r1,r2,…,rn,E)。其中S,E分別表示出發(fā)點(diǎn)和目標(biāo)點(diǎn)，而航路規(guī)劃的目的就是確定出這中間的N個(gè)點(diǎn)的位置和順序。

采用這種方式的航路表達(dá)有很多優(yōu)點(diǎn)。例如可以通過(guò)增加航路節(jié)點(diǎn)的數(shù)量來(lái)提高航路的精度，并且在對(duì)航路的設(shè)計(jì)過(guò)程中可以將一個(gè)較大的整體問(wèn)題劃分為幾個(gè)較小的區(qū)域路徑規(guī)劃子問(wèn)題，相對(duì)于直接求解大規(guī)模問(wèn)題，小規(guī)模的子問(wèn)題更易求解。

1.2 航路規(guī)劃模型設(shè)計(jì)

航路優(yōu)劣的評(píng)價(jià)依據(jù)便是設(shè)計(jì)航路的各種指標(biāo)。實(shí)際上航路規(guī)劃目標(biāo)函數(shù)的設(shè)計(jì)是要綜合考慮航路所需滿(mǎn)足的各種指標(biāo)，從而制定出合適的目標(biāo)函數(shù)，給搜索算法提供正確的尋優(yōu)方向。目標(biāo)函數(shù)的設(shè)計(jì)首先要保證將航路設(shè)計(jì)的各種指標(biāo)進(jìn)行一個(gè)全面綜合的考慮，然后盡可能地減少目標(biāo)函數(shù)的計(jì)算量。文中的航路規(guī)劃指標(biāo)主要考慮航路長(zhǎng)度和威脅對(duì)航路所產(chǎn)生的影響。

(1)

式中: (xi,yi,zi)----第i個(gè)航路點(diǎn)的坐標(biāo);

(xi-1,yi-1,zi-1)----第i-1個(gè)航路點(diǎn)的坐標(biāo)，1≤i

LS----從出發(fā)點(diǎn)開(kāi)始到達(dá)第一個(gè)航路規(guī)劃點(diǎn)的距離；

LE----最后一個(gè)航路規(guī)劃點(diǎn)和終點(diǎn)的距離；

ΔLi----相鄰的兩個(gè)航路規(guī)劃點(diǎn)之間的距離。

同時(shí),還要考慮在航路規(guī)劃過(guò)程中，無(wú)人機(jī)或者無(wú)人車(chē)等設(shè)備要盡可能地避開(kāi)一些障礙或者危險(xiǎn)。因此,給出如下目標(biāo)函數(shù):

J=ω1J1+ω2J2(2)

式(2)表示綜合的目標(biāo)函數(shù)，由兩部分構(gòu)成。這兩部分的重要程度通過(guò)加權(quán)的方式構(gòu)成。其中J1由式(1)給出，J表示整個(gè)航路的路程，J2則表示航路中對(duì)無(wú)人機(jī)產(chǎn)生的各種威脅。若有j個(gè)威脅目標(biāo)，那么當(dāng)航路進(jìn)入到距離該威脅目標(biāo)的威脅半徑Rj之內(nèi)時(shí)，我們認(rèn)為該威脅目標(biāo)會(huì)對(duì)無(wú)人機(jī)產(chǎn)生威脅，那么這樣的航路就是不安全的,Kj為威脅矯正因子。

2 改進(jìn)的螢火蟲(chóng)算法

2.1 基本螢火蟲(chóng)算法分析

螢火蟲(chóng)可以通過(guò)對(duì)光線(xiàn)的感知來(lái)獲得其它個(gè)體發(fā)出的信息來(lái)完成相應(yīng)的一些行為。對(duì)光線(xiàn)的感知主要有兩個(gè)因素:其一是光強(qiáng)度I與距離光源的距離r的平方成反比;其二是光在空氣中傳播會(huì)逐漸減弱，一般情況下螢火蟲(chóng)發(fā)出的光是能夠在幾百米外被感知到。

在螢火蟲(chóng)算法的構(gòu)建過(guò)程中，需要設(shè)定三個(gè)理想化的約束條件[13]：

約束1：螢火蟲(chóng)不存在性別的差異，它們都會(huì)飛向吸引力大、發(fā)光亮度較大的螢火蟲(chóng)。

約束2：螢火蟲(chóng)吸引力的大小和它的亮度成正比。亮度隨著個(gè)體間距離的增加而減小，該規(guī)則與空氣吸收光的實(shí)際情況是相似的。若某一個(gè)螢火蟲(chóng)沒(méi)有任何比它更具有吸引力的其它的螢火蟲(chóng)存在，那么該蟲(chóng)將會(huì)隨機(jī)自由飛行。

約束3：一個(gè)螢火蟲(chóng)的亮度或者吸引力由所需求解的目標(biāo)函數(shù)來(lái)確定。

基本的螢火蟲(chóng)算法的核心思想是每個(gè)螢火蟲(chóng)會(huì)被其它的絕對(duì)亮度大于自身的螢火蟲(chóng)吸引。每個(gè)螢火蟲(chóng)以此來(lái)移動(dòng)自身的位置。首先把螢火蟲(chóng)i的絕對(duì)亮度Ii和我們求解的優(yōu)化問(wèn)題目標(biāo)函數(shù)聯(lián)系起來(lái)。如果螢火蟲(chóng)i比螢火蟲(chóng)j的絕對(duì)亮度大，則螢火蟲(chóng)i吸引螢火蟲(chóng)j向它移動(dòng)。螢火蟲(chóng)i對(duì)螢火蟲(chóng)j的相對(duì)亮度可以決定它們之間的互相引力大小。定義了螢火蟲(chóng)i對(duì)螢火蟲(chóng)j的相對(duì)亮度,如下式:

(4)

式中:Ii----螢火蟲(chóng)i的絕對(duì)亮度；

γ----光吸收系數(shù)，可設(shè)為常數(shù)；

rij----螢火蟲(chóng)i到j(luò)的距離。

現(xiàn)在假定螢火蟲(chóng)i對(duì)螢火蟲(chóng)j的吸引力是與兩個(gè)螢火蟲(chóng)之間的相對(duì)亮度成正比例，那么根據(jù)螢火蟲(chóng)i相對(duì)亮度公式，可得螢火蟲(chóng)i對(duì)螢火蟲(chóng)j的吸引力為:

(5)

式中:β0----最大吸引力，根據(jù)經(jīng)驗(yàn)給出取值β0=1;

γ----空氣對(duì)光的吸收率，代表了吸引力隨著距離變化的情況，對(duì)于很多的問(wèn)題可以取γ∈[0.01,100];

rij----螢火蟲(chóng)i對(duì)螢火蟲(chóng)j的距離，可以定義為笛卡爾距離，即

(6)

螢火蟲(chóng)j被螢火蟲(chóng)i吸引并向其移動(dòng)，文中算法的位置更新公式為：

(7)

式中:xi,xj----螢火蟲(chóng)i,j所處的空間位置；

βij(rij)----螢火蟲(chóng)i對(duì)螢火蟲(chóng)j的吸引力；

α----常數(shù)，一般取α∈[0,1];

εi----高斯分布、均勻分布或者其它分布得到的隨機(jī)向量;

l----隨機(jī)運(yùn)動(dòng)步長(zhǎng)，是一個(gè)常數(shù)。

由上式分析可知，更新的位置取決于吸引力大小和帶有特定系數(shù)的隨機(jī)數(shù)。

2.2 改進(jìn)的螢火蟲(chóng)算法

2.2.1 基本螢火蟲(chóng)算法缺陷分析

由于每次每只螢火蟲(chóng)的位置更新要受到比它更優(yōu)的螢火蟲(chóng)的影響，而這些更優(yōu)的螢火蟲(chóng)不一定就是合理的解。這種錯(cuò)誤的搜索方向可以依靠整個(gè)種群中其它較為優(yōu)秀的螢火蟲(chóng)來(lái)修正，但這一過(guò)程顯然是影響了算法的收斂速率。

2.2.2 參數(shù)自適應(yīng)調(diào)整策略的改進(jìn)

由螢火蟲(chóng)的運(yùn)動(dòng)公式可以看出，決定螢火蟲(chóng)下一步位置的因素有3個(gè)，分別是當(dāng)前的螢火蟲(chóng)和比較優(yōu)秀的螢火蟲(chóng)的距離、光吸收系數(shù)γ、隨機(jī)系數(shù)α。由于螢火蟲(chóng)的位置是隨機(jī)分布的，所以第一個(gè)因素具有很大的隨機(jī)性。因此我們考慮對(duì)后兩個(gè)參數(shù)進(jìn)行改進(jìn)，依據(jù)算法的搜索過(guò)程設(shè)計(jì)自適應(yīng)的參數(shù)調(diào)整策略來(lái)修改參數(shù)，從而控制算法的搜索性能。

首先介紹吸收系數(shù)γ的調(diào)整策略。吸收系數(shù)控制著光強(qiáng)度的變化，在決定算法的收斂速度和行為方面起到非常重要的作用。從理論上來(lái)分析，當(dāng)γ→0,β=β0，那么此時(shí)的吸收系數(shù)作為一個(gè)常數(shù)出現(xiàn)，也就是說(shuō)螢火蟲(chóng)發(fā)出的光不會(huì)隨著距離增大而出現(xiàn)衰減。當(dāng)γ→,β(r)=δ(r)，即一個(gè)狄拉克函數(shù)，它表示螢火蟲(chóng)的吸引力接近于0，螢火蟲(chóng)近似的做隨機(jī)搜索。要使得螢火蟲(chóng)算法在前期能夠較快地確定最優(yōu)解的位置，后期具備較強(qiáng)的局部搜索能力。我們?cè)O(shè)計(jì)了如下的自適應(yīng)調(diào)節(jié)公式：

(8)

式中:γb----初始值;

γe----最終值，γe>γb;

k----調(diào)節(jié)參數(shù),k>0。

吸收系數(shù)隨著螢火蟲(chóng)種群位置方程的變化曲線(xiàn)如圖2所示。

圖2 吸收系數(shù)變化關(guān)系

然后我們對(duì)隨機(jī)系數(shù)參數(shù)α進(jìn)行調(diào)整。隨機(jī)系數(shù)很大程度上會(huì)影響螢火蟲(chóng)的隨機(jī)運(yùn)動(dòng)。要使螢火蟲(chóng)的隨機(jī)搜索能力增強(qiáng)，則增大α，此時(shí)算法有著較強(qiáng)的全局搜索能力；要使螢火蟲(chóng)的隨機(jī)搜索能力下降，則減小α，此時(shí)算法有著較強(qiáng)的局部搜索能力。前面分析了常見(jiàn)的優(yōu)化算法搜索策略，搜索初期要進(jìn)行大范圍的搜索，以便確定全局最優(yōu)的位置，搜索的末期由于距離最優(yōu)點(diǎn)很近了，此時(shí)需要加強(qiáng)局部搜索能力提高算法的收斂速率。通過(guò)以上分析大致可以給出α的定性選擇策略，即前期較大，后期要減小α。我們?cè)O(shè)計(jì)了自適應(yīng)的α的改變策略如下：

(9)

式中:αb----初始值;

αe----最終值，αe<αb;

k----調(diào)節(jié)參數(shù).k>0。

隨機(jī)系數(shù)的變化趨勢(shì)如圖3所示。

圖3 隨機(jī)系數(shù)變化關(guān)系

分析圖3可知，隨機(jī)系數(shù)在螢火蟲(chóng)位置方差較大的時(shí)候，近似于線(xiàn)性的由大變小，最后當(dāng)種群位置方差較小的時(shí)候，其值保持在最小值附近。這樣的變化過(guò)程綜合考慮了全局搜索和局部搜索能力的平衡，提高了算法的尋優(yōu)性能。

2.2.3 隨機(jī)步長(zhǎng)的改進(jìn)

螢火蟲(chóng)算法一直有著收斂速度較慢的不足。螢火蟲(chóng)算法中若增大隨機(jī)步長(zhǎng)，則螢火蟲(chóng)自助的搜索能力會(huì)增強(qiáng)，這樣螢火蟲(chóng)可以在更廣闊的空間上去全局搜索。當(dāng)螢火蟲(chóng)之間的距離較近的時(shí)候，我們要適當(dāng)?shù)乜刂莆灮鹣x(chóng)的自主搜索能力，以便加快螢火蟲(chóng)算法的收斂性。

根據(jù)以上的定性分析，隨著螢火蟲(chóng)之間的距離來(lái)調(diào)節(jié)隨機(jī)步長(zhǎng)，給出下面的公式。

式中:rij----第i,j個(gè)螢火蟲(chóng)的間距。

從式(10)分析可知，螢火蟲(chóng)的隨機(jī)步長(zhǎng)隨著rij變化。兩個(gè)螢火蟲(chóng)距離較遠(yuǎn)的時(shí)候，螢火蟲(chóng)被吸引力指導(dǎo)的可能性較小，螢火蟲(chóng)會(huì)在一定范圍內(nèi)隨機(jī)搜索。當(dāng)螢火蟲(chóng)距離較近的時(shí)候，吸引力占據(jù)主導(dǎo)地位，螢火蟲(chóng)的隨機(jī)搜索行為減小。從而加速整個(gè)改進(jìn)螢火蟲(chóng)算法的收斂速率。

2.2.4 改進(jìn)螢火蟲(chóng)算法描述

根據(jù)上述改進(jìn)策略，結(jié)合基本螢火蟲(chóng)算法，給出了改進(jìn)螢火蟲(chóng)算法的定義。

首先定義算法的相關(guān)參數(shù)，并在一定范圍內(nèi)隨機(jī)生成螢火蟲(chóng)的初始種群。然后根據(jù)目標(biāo)函數(shù)計(jì)算螢火蟲(chóng)的亮度，依據(jù)亮度對(duì)螢火蟲(chóng)進(jìn)行排序。判斷算法是否滿(mǎn)足收斂條件，若滿(mǎn)足,則輸出最優(yōu)解；不滿(mǎn)足,則繼續(xù)進(jìn)行下一步操作。計(jì)算螢火蟲(chóng)的亮度方差，依據(jù)亮度方差給出改進(jìn)螢火蟲(chóng)算法的吸收系數(shù)和隨機(jī)系數(shù)。然后再更新螢火蟲(chóng)的位置信息。最后再根據(jù)自主飛行策略，確定螢火蟲(chóng)是否進(jìn)行自主飛行，然后跳轉(zhuǎn)。

3 仿真實(shí)驗(yàn)(改進(jìn)的螢火蟲(chóng)算法性能測(cè)試實(shí)驗(yàn))

在經(jīng)典的Benchmark上對(duì)文中所提出的改進(jìn)的螢火蟲(chóng)算法進(jìn)行測(cè)試，仿真實(shí)驗(yàn)選取的目標(biāo)函數(shù)見(jiàn)表1。

表1 測(cè)試函數(shù)

三種算法計(jì)算結(jié)果對(duì)比見(jiàn)表2。

表2 三種算法計(jì)算結(jié)果對(duì)比

將文中所提的螢火蟲(chóng)算法和基本螢火蟲(chóng)算法(GA以及PSO算法)在航路規(guī)劃問(wèn)題的求解結(jié)果進(jìn)行比較。搜索范圍定為[-100,100]n。改進(jìn)的螢火蟲(chóng)算法的參數(shù)設(shè)置為：β0=1，γe=1，γb=0.8，αe=0.1，αb=1，k=5。

兩種算法在不同維數(shù)求解結(jié)果對(duì)比見(jiàn)表3。

通過(guò)實(shí)驗(yàn)驗(yàn)證了螢火蟲(chóng)算法在一般優(yōu)化問(wèn)題中的性能，將改進(jìn)的螢火蟲(chóng)算法和基本的螢火蟲(chóng)算法進(jìn)行對(duì)比實(shí)驗(yàn)，來(lái)測(cè)試該算法的特性。算法種群規(guī)模都設(shè)置為10，維數(shù)分別取5、10、20、30、40、50等6種情況進(jìn)行航路規(guī)劃實(shí)驗(yàn)。若算法能找到規(guī)避障礙物的航路，則表明搜索成功。針對(duì)每一種情況，螢火蟲(chóng)算法和粒子群算法的停止條件是連續(xù)迭代400次。分別獨(dú)立運(yùn)行算法60次，統(tǒng)計(jì)每種算法的成功率、航路長(zhǎng)度和計(jì)算時(shí)間。出發(fā)點(diǎn)與目標(biāo)點(diǎn)深度均為300 m。出發(fā)點(diǎn)的經(jīng)緯度為(111.10E,17.07N), 目標(biāo)點(diǎn)的經(jīng)緯度為(112.50E,16.69N)。

表3 兩種算法在不同維數(shù)求解結(jié)果對(duì)比

從以上實(shí)驗(yàn)數(shù)據(jù)可知，針對(duì)該航路規(guī)劃問(wèn)題，改進(jìn)的螢火蟲(chóng)算法均能成功搜索到從起點(diǎn)到終點(diǎn)的航路，且航路能夠成功規(guī)避障礙物，從而證明了算法的有效性。除了維數(shù)為5的情況外，利用螢火蟲(chóng)算法進(jìn)行航路規(guī)劃的成功率均較高，航路長(zhǎng)度較短，說(shuō)明該算法具有較好的性能。但是，在維數(shù)較小的時(shí)候，兩種算法的成功率均較低，這是由于算法的維數(shù)對(duì)于規(guī)劃航路的航路點(diǎn)數(shù)，較少的維數(shù)會(huì)導(dǎo)致算法在沒(méi)有航路點(diǎn)的區(qū)域失去避障能力，造成規(guī)劃航路穿過(guò)了障礙物。從平均的計(jì)算時(shí)間可以看出，螢火蟲(chóng)算法耗時(shí)較粒子群算法長(zhǎng)，這主要是由于螢火蟲(chóng)算法在執(zhí)行過(guò)程中，每一個(gè)螢火蟲(chóng)均要根據(jù)比它亮的螢火蟲(chóng)調(diào)節(jié)自身位置。隨著維數(shù)的增加，兩種算法在規(guī)劃的速率都會(huì)越來(lái)越慢，隨之而來(lái)的計(jì)算時(shí)間也會(huì)大大增加。

4 結(jié) 語(yǔ)

在對(duì)各種螢火蟲(chóng)算法的研究基礎(chǔ)上提出了一種新的螢火蟲(chóng)算法。給出了吸收系數(shù)、隨機(jī)系數(shù)和隨機(jī)步長(zhǎng)對(duì)螢火蟲(chóng)算法求解結(jié)果的不同影響。通過(guò)自適應(yīng)調(diào)整吸收系數(shù)和隨機(jī)系數(shù)來(lái)平衡算法的全局尋優(yōu)能力和局部尋優(yōu)能力，然后依靠改進(jìn)的隨機(jī)步長(zhǎng)選擇方法，分別在優(yōu)化過(guò)程的前期和后期采用不同的隨機(jī)步長(zhǎng)策略來(lái)調(diào)整螢火蟲(chóng)算法的收斂性。實(shí)驗(yàn)結(jié)果表明，該算法比基本螢火蟲(chóng)在優(yōu)化問(wèn)題的求解上有著更好的效果。證明了該算法在航路規(guī)劃問(wèn)題求解中的有效性和準(zhǔn)確性。