基于飛行角度優(yōu)化的蟻群改進(jìn)算法*

張晶晶，王建清，李桂芳，陳 川，石華云

(上海航天控制技術(shù)研究所·上?！?01109)

0 引 言

路徑規(guī)劃是依靠環(huán)境感知程度并在某些約束條件下，找出從出發(fā)點(diǎn)到目標(biāo)節(jié)點(diǎn)的最佳飛行路線。近年來，國內(nèi)外學(xué)者提出了多種路徑規(guī)劃算法，包括A算法、動(dòng)態(tài)規(guī)劃算法、PRM(Probabilistic Roadmaps)算法、遺傳算法、神經(jīng)網(wǎng)絡(luò)算法等，但由于路徑規(guī)劃問題存在著高時(shí)間復(fù)雜度的特性，求解時(shí)間會(huì)隨著問題規(guī)模成指數(shù)型增長，算法的運(yùn)算成本也會(huì)急劇增加，同時(shí)受限于無人飛行器飛行特征及算法本身的局限性，最終得出的路徑規(guī)劃與實(shí)際存在著較大的偏差。傳統(tǒng)的PRM算法基于隨機(jī)抽樣原理，依據(jù)環(huán)境內(nèi)的最小代價(jià)進(jìn)行路徑規(guī)劃，囿于基礎(chǔ)限制，規(guī)劃出的路徑并不一定符合無人飛行器的飛行特征。由此，提出了神經(jīng)網(wǎng)絡(luò)、蟻群優(yōu)化算法等為代表的無人飛行器路徑規(guī)劃新型仿生算法。改進(jìn)的蟻群算法在機(jī)器人或無人飛行器的路徑規(guī)劃中應(yīng)用越來越廣泛。文獻(xiàn)[9]在蟻群算法的基礎(chǔ)上提出了人工勢場方法，在蟻群的信息素中結(jié)合了人工勢場，降低了路徑規(guī)劃初期反饋不明顯的影響。文獻(xiàn)[10]提出了一種信息素初始值修改和狀態(tài)轉(zhuǎn)移規(guī)則的方法，加速了算法的收斂速度，提高了算法最優(yōu)解的質(zhì)量，但參數(shù)設(shè)置較為復(fù)雜,也未考慮無人飛行器的飛行特征。

本文針對(duì)無人飛行器路徑規(guī)劃問題的飛行特征，對(duì)傳統(tǒng)的RAS算法進(jìn)行了改進(jìn)。以柵格法為基礎(chǔ)建立了飛行區(qū)域地圖模型，以RAS算法作為全局路徑規(guī)劃算法，并在其中引入了無人飛行器的尖角優(yōu)化策略，完成全局最優(yōu)路徑規(guī)劃。最后與傳統(tǒng)RAS算法進(jìn)行對(duì)比仿真實(shí)驗(yàn)，以驗(yàn)證算法的有效性，證明了該算法在無人飛行器路徑規(guī)劃上符合飛行器的飛行特征，并具有良好的適應(yīng)性。

1 改進(jìn)蟻群算法原理

1.1 蟻群(AS)經(jīng)典算法

基本蟻群(Ant System，AS)實(shí)現(xiàn)路徑規(guī)劃需要完成兩個(gè)步驟，一個(gè)是路徑構(gòu)建，一個(gè)是信息素更新。

每個(gè)螞蟻在路徑選擇時(shí)都會(huì)按照一個(gè)概率從所處的節(jié)點(diǎn)往下一個(gè)節(jié)點(diǎn)遷移，該概率又被稱為啟發(fā)式，可以看成一種先驗(yàn)信息。若不考慮信息素，可以認(rèn)為啟發(fā)式是一種貪婪算法。其在路徑規(guī)劃中的更新規(guī)則如式(1)所示

(1)

式中，

P

為

i

節(jié)點(diǎn)到

j

節(jié)點(diǎn)的轉(zhuǎn)移概率；

τ

(

t

)為從

i

點(diǎn)到

j

點(diǎn)的信息素量；

η

(

t

)為啟發(fā)函數(shù)，又稱能見度；

allowed

為螞蟻在

i

點(diǎn)時(shí)的可選子集；

α

為信息素啟發(fā)因子；

β

為期望啟發(fā)式因子。其中能見度的運(yùn)算方式如式(2)所示

(2)

式中，

d

表示

i

節(jié)點(diǎn)到

j

節(jié)點(diǎn)之間的距離。

從式(1)和式(2)可以看出，啟發(fā)式是一種局部信息，在路徑規(guī)劃的初始階段可以指導(dǎo)螞蟻快速地構(gòu)造較優(yōu)解，提高算法前期的搜索效率。

為使螞蟻在較短路徑上留下更多的信息素，在所有螞蟻到達(dá)終點(diǎn)時(shí)，對(duì)各個(gè)螞蟻形成的路徑的信息素濃度進(jìn)行更新，分為兩步：

第一步，在每一輪路徑構(gòu)建完畢后，所有路徑上的信息素?fù)]發(fā)；

第二步，所有的螞蟻依據(jù)自身構(gòu)建的路徑長度,在本輪經(jīng)過的路徑上釋放信息素。

信息素的揮發(fā)過程是每個(gè)路徑上的信息素濃度自動(dòng)逐漸減弱的過程，這個(gè)過程可以避免算法過快地向局部最優(yōu)解集中，有助于其他路徑的探索。AS算法中信息素更新分為兩步，第一步是所有路徑上信息素?fù)]發(fā)一部分， 第二步是螞蟻在其經(jīng)過的路徑上釋放信息素。

τ

=(1-

ρ

)

τ

+Δ

τ

(3)

式中，

ρ

表示信息素?fù)]發(fā)率；Δ

τ

表示信息素增量。有三種方式進(jìn)行更新。Δ

τ

=

Q

(4)

Δ

τ

=

Q/d

(5)

Δ

τ

=

Q/L

(6)

其中，

Q

為信息素強(qiáng)度；

d

表示節(jié)點(diǎn)

i

到節(jié)點(diǎn)

j

之間的距離；

L

表示一只螞蟻構(gòu)造回路的總距離。

式(4)被稱為蟻密系統(tǒng)模型，式(5)被稱為蟻量系統(tǒng)模型，式(6)被稱為蟻周模型。從3個(gè)式子中可以看出,前兩者都是在螞蟻完成一步后更新；而式(6)是以整條回路的視角在單位長度上釋放等量的信息素，螞蟻構(gòu)造的回路越短，信息素增量越多，反之越少。從另一方面來說，式(5)相對(duì)于式(4)，利用了局部信息來更新信息素；而式(6)則利用了全局信息。在實(shí)際求解過程中，需要找到全局最優(yōu)路徑，而非局部最優(yōu)。實(shí)驗(yàn)證明，前兩種更新方式效果遠(yuǎn)不如第三種。

實(shí)際上，AS算法這兩個(gè)部分成為后續(xù)改進(jìn)AS算法優(yōu)化的對(duì)象，很多算法都對(duì)這兩部分進(jìn)行了改進(jìn)。

1.2 改進(jìn)的AS算法

1.2.1 精英螞蟻蟻群(EAS)算法

在AS算法中，螞蟻釋放的信息素與其構(gòu)建路徑長度成反比，構(gòu)建路徑長度質(zhì)量越好，則留在路徑上的信息素越多，這些路徑在迭代過程中被后續(xù)螞蟻選擇的概率也越大。當(dāng)問題規(guī)模越來越大，僅靠集成單一的信息素更新機(jī)制引導(dǎo)搜索偏向，將會(huì)導(dǎo)致算法搜索效率越來越低。AS算法創(chuàng)始人在AS論文中也提出了精英螞蟻蟻群(Elitist Ant System，EAS)算法，通過進(jìn)一步地開發(fā)當(dāng)前最優(yōu)的路徑，強(qiáng)化某些最有可能成為最優(yōu)的路徑，使算法的搜索范圍更廣，提高算法的收斂速度。在進(jìn)行信息素更新時(shí)，對(duì)某些路徑予以加權(quán)，并將這些路徑上的螞蟻標(biāo)記為精英，以增加較好路徑被選擇的概率。其除了具有和AS相同的信息素更新方式外，還依據(jù)式(7)進(jìn)行更新

τ

=

τ

+

eQ/L

(7)

式中，

e

表示精英螞蟻的個(gè)數(shù)；

L

為當(dāng)前最優(yōu)解的總長度；

i

、

j

為當(dāng)前最優(yōu)路徑上的節(jié)點(diǎn)。

在每一次迭代中，全局最優(yōu)(從第一代到當(dāng)前這一代的最優(yōu))螞蟻所經(jīng)過的路徑，可以獲得額外的信息素更新，相當(dāng)于多只螞蟻經(jīng)過了此最優(yōu)路徑并釋放了信息素。這加強(qiáng)了全局最優(yōu)螞蟻對(duì)后續(xù)螞蟻的影響，使后面的螞蟻在全局最優(yōu)路徑及其附近路徑上的選擇概率增加，在當(dāng)前最優(yōu)的路徑上進(jìn)一步的開發(fā)，提高了算法的收斂速度。但精英螞蟻也存在劣勢，在對(duì)應(yīng)路徑上增加了信息素，降低了后續(xù)螞蟻構(gòu)造解的多樣性。單純的精英算法犧牲了算法的多樣性以提升收斂速度，這種缺陷與遺傳算法中最優(yōu)個(gè)體才能生存的行為相似，容易造成算法快速停滯，使得某一條路徑上的信息素急劇增加，從而嚴(yán)重影響了后續(xù)螞蟻構(gòu)造解的多樣性。

1.2.2 排序螞蟻蟻群(RAS)算法

排序螞蟻群(Ranked Ant System, RAS)算法在 EAS 的基礎(chǔ)上，針對(duì)EAS算法多樣性較小的特征，參考遺傳算法中依據(jù)適應(yīng)度進(jìn)行評(píng)價(jià)的方法，更新不同路徑上的信息素。在RAS算法中，首先會(huì)對(duì)形成的路徑進(jìn)行排序，給予最優(yōu)路徑上信息素更新的量最多，并將較優(yōu)路徑上的螞蟻也納入信息素更新原則中。

(8)

(9)

(10)

式中，

n

為預(yù)設(shè)的排序螞蟻的個(gè)數(shù)；

L

為當(dāng)前最優(yōu)螞蟻的路徑長度；

L

為第

n

只較優(yōu)螞蟻的路徑長度。排序策略不僅增加了最優(yōu)路徑上的信息素增量，還增加了次優(yōu)路徑上的信息素增量。這種算法一方面可以吸引后續(xù)螞蟻選擇較短路徑，另一方面又可以讓較優(yōu)螞蟻構(gòu)建的路徑能夠被后續(xù)螞蟻發(fā)現(xiàn)，拓展了算法的探索空間，增加了算法的多樣性。排序策略保留了精英策略讓當(dāng)前最優(yōu)的螞蟻指導(dǎo)后續(xù)螞蟻解的構(gòu)造過程，更進(jìn)一步地考慮了每代螞蟻中較優(yōu)個(gè)體的智能行為，并且還考慮了不同優(yōu)化程度螞蟻之間的差別，即給予不同的權(quán)重。文獻(xiàn)[11]中提出了排序策略，通過選擇多個(gè)較優(yōu)個(gè)體的方法來減少精英策略或者是全局優(yōu)化策略帶來的潛在缺陷。

2 基于飛行角度優(yōu)化的RAS算法

2.1 飛行角度優(yōu)化策略

無人飛行器受機(jī)體性能的約束，在飛行過程中存在著轉(zhuǎn)彎機(jī)動(dòng)特征的限制，其轉(zhuǎn)彎角度的變化范圍在[

ξ

-

ξ

,

ξ

+

ξ

]。其中，

ξ

為無人飛行器當(dāng)前的飛行角度；

ξ

為無人飛行器可承受的最大轉(zhuǎn)彎角度，如圖1所示。

圖1 無人飛行器最大轉(zhuǎn)彎角度Fig.1 Maximum turning angle of UAV

受最大轉(zhuǎn)彎角度的限制，無人飛行器在使用算法進(jìn)行下一節(jié)點(diǎn)的選擇時(shí)，除去障礙，不能再將其周圍的所有節(jié)點(diǎn)作為可飛行節(jié)點(diǎn)。傳統(tǒng)的RAS算法未將無人飛行器的性能特征納入需求，可能導(dǎo)致路徑出現(xiàn)折返或者尖角，如圖2所示。

圖2 折返和尖角示意圖Fig.2 Diagram of retrace and sharp angle phenomenon

圖2中圈出的是折返和尖角現(xiàn)象，不符合無人飛行器的飛行特征。將飛行角度優(yōu)化策略納入RAS算法，飛行最大轉(zhuǎn)彎角度的限制可能使候選節(jié)點(diǎn)縮小至1～3個(gè)節(jié)點(diǎn)，如圖3所示。

圖3 優(yōu)化后候選節(jié)點(diǎn)示意圖Fig.3 Diagram of potential nodes after optimization

圖3中，

N

代表上一節(jié)點(diǎn)；

N

代表當(dāng)前節(jié)點(diǎn)；

N

代表下一可選節(jié)點(diǎn)；

ξ

為引入的限制飛行角度最大值。

2.2 轉(zhuǎn)移概率更新策略

假定螞蟻上一節(jié)點(diǎn)處為

N

，當(dāng)前處于節(jié)點(diǎn)

N

，下次轉(zhuǎn)移節(jié)點(diǎn)為

N

，三點(diǎn)之間的夾角為

ε

，則飛行角度優(yōu)化策略如下所述。

(1)對(duì)于當(dāng)前節(jié)點(diǎn)的任意鄰接節(jié)點(diǎn)滿足

ε

<=

ε

(11)

則認(rèn)為

N

∈

N

其中，

N

為允許的節(jié)點(diǎn)集。(2)若不存在任何鄰接節(jié)點(diǎn)滿足

ε

<=

ε

，則更新

N

=

N

，將在新的鄰接節(jié)點(diǎn)中隨機(jī)抽樣作為下次移動(dòng)的目標(biāo)節(jié)點(diǎn)，概率更新原則為

(12)

其中，

p

為轉(zhuǎn)移概率；

τ

為鄰接節(jié)點(diǎn)中第

i

節(jié)點(diǎn)的信息素；

τ

為已經(jīng)走過的路徑節(jié)點(diǎn)的信息素。

2.3 算法實(shí)現(xiàn)及步驟流程

將飛行角度優(yōu)化策略融入RAS算法，則優(yōu)化后的全局RAS算法步驟如下所述。

1)創(chuàng)建柵格化地圖模型，模擬實(shí)際飛行環(huán)境，建立AS算法數(shù)據(jù)模型。

2)狀態(tài)及參數(shù)初始化。根據(jù)障礙物表格信息生成鄰接矩陣，初始化試驗(yàn)次數(shù)

E

、迭代次數(shù)

N

、路徑起點(diǎn)和終點(diǎn)、全局信息素濃度、信息素?fù)]發(fā)因子，并將起點(diǎn)加入到禁忌表格tabu中，其中存儲(chǔ)了螞蟻已經(jīng)走過的路徑節(jié)點(diǎn)，防止螞蟻再次走回該節(jié)點(diǎn)。3)按照試驗(yàn)次數(shù)、迭代次數(shù)和螞蟻個(gè)數(shù)

A

進(jìn)行路徑搜索，按照尖角優(yōu)化策略和實(shí)際障礙物矩陣進(jìn)行角度篩選，并根據(jù)式(11)或者式(12)篩選下一節(jié)點(diǎn)的可行區(qū)域。

4)按照RAS算法計(jì)算當(dāng)前螞蟻的轉(zhuǎn)移概率，在可行區(qū)域內(nèi)確定下一節(jié)點(diǎn)，并將當(dāng)前節(jié)點(diǎn)更新至禁忌表格tabu中。

5)螞蟻數(shù)量循環(huán)結(jié)束后，確定

A

條路徑，取最小值作為本次模擬的最優(yōu)路徑。

6)按照當(dāng)前最優(yōu)軌跡及較優(yōu)軌跡進(jìn)行信息素更新。

7)試驗(yàn)次數(shù)循環(huán)結(jié)束后，綜合所有路徑的解，輸出最優(yōu)路徑。

詳細(xì)算法實(shí)現(xiàn)完畢后，對(duì)算法輸入模型進(jìn)行數(shù)值模擬，輸出最優(yōu)路徑及相關(guān)結(jié)果信息。

3 仿真試驗(yàn)及結(jié)果分析

3.1 算法參數(shù)的選擇

理論上，螞蟻數(shù)量

A

關(guān)系到全局路徑的搜索能力，

A

越大，得到的最優(yōu)解越精確。但實(shí)際上，

A

越大，最優(yōu)路徑的解也會(huì)產(chǎn)生冗余，大量的重復(fù)運(yùn)算也會(huì)消耗時(shí)間資源，增加了時(shí)間的復(fù)雜度。在路徑規(guī)劃過程中，信息素啟發(fā)因子

α

反映了信息素的相對(duì)重要程度。

α

越大，本代后續(xù)螞蟻以及后代螞蟻選擇本只螞蟻所搜索的路徑的概率越大，但同時(shí)也降低了其他螞蟻探索新路徑的可能性；而

α

越小，則有可能導(dǎo)致螞蟻困于局部解中而無法找到全局最優(yōu)解。期望啟發(fā)因子

β

反映了路徑規(guī)劃過程中啟發(fā)函數(shù)的相對(duì)重要程度。

β

越大，在此節(jié)點(diǎn)上選擇局部最優(yōu)解的可能性越大，同時(shí)加速了算法收斂，但是同樣會(huì)使后續(xù)螞蟻的探索能力降低。信息素?fù)]發(fā)系數(shù)

ρ

表征路徑上信息素的揮發(fā)程度。過大的

ρ

會(huì)加速信息素的揮發(fā)，導(dǎo)致算法的全局路徑探索能力降低，從而影響最優(yōu)解的結(jié)果；過小的

ρ

會(huì)降低信息素的揮發(fā)，全局路徑探索能力得到提升，但降低了算法的收斂速度。

文獻(xiàn)[14]和文獻(xiàn)[15]對(duì)影響算法的各個(gè)參數(shù)進(jìn)行了仿真分析，得出了較為優(yōu)化的參數(shù)。參考此類優(yōu)化算法，結(jié)合無人飛行器的飛行特征，本文最大轉(zhuǎn)彎角度選擇90°，仿真試驗(yàn)的參數(shù)如表1所示。

表1 算法參數(shù)選擇Tab.1 Algorithm parameters selection

3.2 仿真結(jié)果與分析

將選擇的算法參數(shù)輸入模型進(jìn)行仿真驗(yàn)證，以30×30的柵格化地圖模型為問題空間。為驗(yàn)證算法不會(huì)產(chǎn)生折返和尖角，統(tǒng)計(jì)10×10次試驗(yàn)輸出的最優(yōu)路徑結(jié)果中可能存在的最大角度。

本次試驗(yàn)輸出的最優(yōu)路徑與最大轉(zhuǎn)彎角度(絕對(duì)值)結(jié)果如表2所示。

表2 優(yōu)化后算法輸出結(jié)果Tab.2 Algorithm output result

從圖4和表2中可以看出，優(yōu)化后的RAS算法輸出的最優(yōu)路徑曲線平滑，最大轉(zhuǎn)彎角度限制在90°以內(nèi)，未再出現(xiàn)圖2中的尖角現(xiàn)象，符合無人飛行器的飛行特征需求，收斂迭代次數(shù)也很快。

圖4 優(yōu)化后的最優(yōu)路徑與收斂曲線Fig.4 Optimal path and convergence curve after optimization

分別以傳統(tǒng)的RAS算法和優(yōu)化后的RAS算法作為對(duì)象，使用相同的柵格化地圖模型進(jìn)行仿真模擬，對(duì)比了兩種算法的輸出結(jié)果，如圖5所示。

圖5 算法路徑對(duì)比圖Fig.5 Optimal path comparison table

圖5中，RAS算法依然存在尖角特征，而優(yōu)化后的RAS算法已經(jīng)消除了尖角特征，更好地符合飛行特征。

圖6和表3比較了RAS算法優(yōu)化前后的迭代次數(shù)一級(jí)路徑最優(yōu)值，從實(shí)驗(yàn)結(jié)果可以看出，本文的改進(jìn)算法無論從最優(yōu)路徑求解和收斂速度，還是從飛行角度特征方面，都達(dá)到了良好的效果。

圖6 收斂曲線對(duì)比結(jié)果Fig.6 Convergence curve comparison table

表3 優(yōu)化后算法比對(duì)結(jié)果Tab.3 Algorithm output result comparison table

4 結(jié) 論

傳統(tǒng)RAS算法在無人飛行器路徑規(guī)劃中存在尖角的現(xiàn)象，不符合無人飛行器特征。本文將飛行角度優(yōu)化策略引入RAS算法后進(jìn)行仿真模擬，并與傳統(tǒng)的RAS算法進(jìn)行對(duì)比，結(jié)果表明，優(yōu)化后的RAS算法消除了尖角特征，使得規(guī)劃的最優(yōu)路徑更加平滑，更加符合無人飛行器的特征。本文實(shí)現(xiàn)的算法在路徑規(guī)劃時(shí)未納入時(shí)耗問題，可以作為下一步的研究目標(biāo)。