基于改進(jìn)螢火蟲算法的航路規(guī)劃問題求解

姜 彬， 喬紅宇， 施志剛

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

0 引 言

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

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

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

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

航路規(guī)劃是在一定的約束條件下設(shè)計(jì)和規(guī)劃航路，從而尋找到從出發(fā)點(diǎn)到目標(biāo)點(diǎn)的一個最優(yōu)路徑。例如無人機(jī)、無人地面探測車、無人水面艦艇等。它們需要在不同的場景下，規(guī)劃出不同的航路，從而完成相應(yīng)的任務(wù)，每次航行經(jīng)過的一些航路點(diǎ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個點(diǎn)的位置和順序。

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

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

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

(1)

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

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

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

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

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

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

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

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

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

2.1 基本螢火蟲算法分析

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

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

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

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

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

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

(4)

式中:Ii----螢火蟲i的絕對亮度；

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

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

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

(5)

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

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

rij----螢火蟲i對螢火蟲j的距離，可以定義為笛卡爾距離，即

(6)

螢火蟲j被螢火蟲i吸引并向其移動，文中算法的位置更新公式為：

(7)

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

βij(rij)----螢火蟲i對螢火蟲j的吸引力；

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

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

l----隨機(jī)運(yùn)動步長，是一個常數(shù)。

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

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

2.2.1 基本螢火蟲算法缺陷分析

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

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

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

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

(8)

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

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

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

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

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

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

(9)

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

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

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

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

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

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

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

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

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

式中:rij----第i,j個螢火蟲的間距。

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

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

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

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

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

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

表1 測試函數(shù)

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

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

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

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

通過實(shí)驗(yàn)驗(yàn)證了螢火蟲算法在一般優(yōu)化問題中的性能，將改進(jìn)的螢火蟲算法和基本的螢火蟲算法進(jìn)行對比實(shí)驗(yàn)，來測試該算法的特性。算法種群規(guī)模都設(shè)置為10，維數(shù)分別取5、10、20、30、40、50等6種情況進(jìn)行航路規(guī)劃實(shí)驗(yàn)。若算法能找到規(guī)避障礙物的航路，則表明搜索成功。針對每一種情況，螢火蟲算法和粒子群算法的停止條件是連續(xù)迭代400次。分別獨(dú)立運(yùn)行算法60次，統(tǒng)計(jì)每種算法的成功率、航路長度和計(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é)果對比

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

4 結(jié) 語

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