王　芳，李昆鵬

(1.西安航空學(xué)院 機械工程學(xué)院，陜西 西安 710077；2.長安大學(xué) 道路施工技術(shù)與裝備教育部重點實驗室，陜西 西安 710064)

基于APF導(dǎo)向的蟻群航路規(guī)劃算法參數(shù)優(yōu)化研究

王芳1，李昆鵬2

(1.西安航空學(xué)院 機械工程學(xué)院，陜西 西安 710077；2.長安大學(xué) 道路施工技術(shù)與裝備教育部重點實驗室，陜西 西安 710064)

摘要：針對基于APF導(dǎo)向的蟻群航路規(guī)劃算法中的參數(shù)優(yōu)化問題，提出了算法中的參數(shù)優(yōu)化規(guī)則。分析了APFGA算法中參數(shù)m、α、β、γ、和ρ等的選取原則，通過合理選擇參數(shù)，使蟻群的搜索有效地避免陷入局部最優(yōu)，加快了算法的速度，提高了蟻群的搜索效率。實驗結(jié)果給出了參數(shù)選擇依據(jù)，通過合理設(shè)置算法參數(shù)可以有效地改善蟻群算法的性能，有利于APFGA算法在航路規(guī)劃等方面的應(yīng)用和推廣。

關(guān)鍵詞：航路規(guī)劃；參數(shù)優(yōu)化；搜索效率

0引言

航路規(guī)劃作為無人機任務(wù)規(guī)劃的重要組成部分之一，是在特定約束下尋找一條起點到目標(biāo)點之間最優(yōu)的可行航路。航路規(guī)劃問題一直是關(guān)乎無人機性能以及智能性的重要體現(xiàn)，目前航路規(guī)劃主要集中在環(huán)境模型構(gòu)建、規(guī)劃策略設(shè)計以及參數(shù)優(yōu)化等方面[1-4]。文獻(xiàn)[5]中提出了一種人工勢場導(dǎo)向的蟻群航路規(guī)劃算法，將人工勢場的目標(biāo)導(dǎo)向作用運用于蟻群優(yōu)化算法中，改善了螞蟻搜索的盲目性，提高了路徑搜索效率。但是，在運用蟻群算法求解問題時，參數(shù)值的選擇直接決定了算法的好壞，而算法中不僅參數(shù)的個體取值十分重要，并且參數(shù)之間的組合取值更是直接影響著整個算法的結(jié)果，如果參數(shù)取值不當(dāng)，會導(dǎo)致算法陷入局部最優(yōu)等問題。如何找到參數(shù)間的關(guān)系成為了算法優(yōu)劣的關(guān)鍵。

本文重點研究基于APF導(dǎo)向的蟻群算法對于航路搜索效果與算法本身參數(shù)配置的關(guān)系，從而更好地發(fā)揮算法航路尋優(yōu)的性能。針對基于APF導(dǎo)向的蟻群算法參數(shù)取值問題，分析算法參數(shù)設(shè)置，通過實驗分析確定參數(shù)合理取值區(qū)間。

1基于APF導(dǎo)向的蟻群航路規(guī)劃算法

蟻群算法是一種智能隨機搜索算法，多用于解決離散問題。算法中螞蟻是根據(jù)系統(tǒng)路徑上信息素的強度完成狀態(tài)轉(zhuǎn)移的，但在搜索初期，路徑上信息素較弱，難以實現(xiàn)信息素的導(dǎo)向作用，同時在搜索后期，會因為某條次優(yōu)路徑上信息素的短暫加強使得螞蟻搜索難以跳出局部極小，而利用人工勢場的導(dǎo)向作用可以將人工勢場規(guī)劃結(jié)果作為蟻群路徑搜索的初始解，以及通過構(gòu)建勢場導(dǎo)向權(quán)，使勢場法的引導(dǎo)作用于蟻群路徑搜索的始終，可以改善螞蟻路徑搜索的盲目性，從而顯著提高收斂速度。基于APF導(dǎo)向的蟻群算法基本模型如下[5]。

算法執(zhí)行時，先計算機器人在虛擬勢場中受到的引力、斥力，并計算勢場導(dǎo)向權(quán)。設(shè)Fatt、Frep分別為人工勢場的引力和斥力，則螞蟻在人工勢場中的避障角度為：

θ=∠(Fatt+∑Frep)

(1)

假設(shè)當(dāng)前螞蟻在某柵格中，其向鄰域柵格轉(zhuǎn)移的方向角為φ，則定義該柵格方向的人工勢場導(dǎo)向權(quán)為：

q(t)=λ·exp(cos(θ-φ)

(2)

式中，λ為調(diào)整系數(shù)。由上式可以看出，螞蟻鄰域某柵格方向與勢場法避障方向越接近，其導(dǎo)向權(quán)值越大。

利用人工勢場修正螞蟻狀態(tài)轉(zhuǎn)移概率pk(begin,end)，按概率隨機得到螞蟻下一步的移動位置，并更新禁忌表。

(3)

式中，τij(t)為t時刻節(jié)點i和j之間殘留的信息素；α為信息素啟發(fā)因子；ηij(t)為t時刻節(jié)點i和j之間的期望啟發(fā)函數(shù)；β為期望啟發(fā)因子；qij(t)為導(dǎo)向權(quán)；γ為導(dǎo)向權(quán)啟發(fā)因子。ηij(t)為距離定義式。

螞蟻走過的路徑上會留下信息素，同時為了避免路徑上因殘留信息素過多而造成啟發(fā)信息被淹沒，信息素會隨著時間的流逝而揮發(fā)，設(shè)ρ為信息素?fù)]發(fā)系數(shù)且(0≤ρ<1)，t+Δt時刻節(jié)點i和j上的信息素更新規(guī)則為[6]：

τij(t+Δt)=(1-ρ)·τij(t)+Δτij(t)

(4)

(5)

(6)

式中，Q為信息素強度；Lk為螞蟻k在本次循環(huán)中所走過路徑的總長度。

2算法參數(shù)優(yōu)化

基于勢場導(dǎo)向權(quán)優(yōu)化的蟻群算法由于融合了人工勢場和蟻群算法的優(yōu)勢，因而其搜索性能得到很好提升。從上面的分析不難看出，在算法中螞蟻數(shù)m，信息素啟發(fā)因子α，期望啟發(fā)因子β，導(dǎo)向權(quán)啟發(fā)因子γ和清晰度衰減系數(shù)ρ等參數(shù)最為重要，但是，通過大量的數(shù)學(xué)計算和分析，參數(shù)選擇尚無嚴(yán)格的理論依據(jù)，因此，先采用一些文獻(xiàn)提出的參數(shù)[3-4,7]，通過逐步調(diào)整各個參數(shù)的取值，再進(jìn)行一系列的仿真實驗，找到蟻群算法中最佳的參數(shù)選擇。針對文獻(xiàn)[5]中給出的環(huán)境對基于導(dǎo)向權(quán)優(yōu)化的蟻群算法參數(shù)進(jìn)行了性能測試研究。

2.1螞蟻數(shù)(m)

在蟻群路徑規(guī)劃算法中，增大螞蟻數(shù)勢必會提高算法的搜索能力，但是螞蟻數(shù)越大，算法的計算量越大，運行效率越低；而螞蟻數(shù)太小，也不利于體現(xiàn)算法的正反饋機制，使其快速收斂于最優(yōu)解。因此，選擇合適的螞蟻數(shù)m對充分發(fā)揮算法性能具有重要意義。

(a)平均路徑長度

(b)平均收斂代數(shù)

針對給出的兩種環(huán)境，在保持其它參數(shù)不變的前提下，使m值在[1,80]范圍內(nèi)由小到大變化進(jìn)行50次獨立隨機測試，考察螞蟻平均路徑長度和平均收斂代數(shù)的變化情況，如圖1所示。由圖可見，兼顧算法的計算精度和運行效率，m值選取15較為合適。

2.2信息素啟發(fā)因子(α)

螞蟻依靠信息素的強弱進(jìn)行轉(zhuǎn)移，完成路徑搜索，因此，路徑上信息素的強弱是螞蟻進(jìn)行狀態(tài)轉(zhuǎn)移的重要依據(jù)。在保持其它參數(shù)不變的前提下，使α值在[0,5]范圍內(nèi)由小到大變化進(jìn)行50次獨立隨機測試，考察螞蟻平均路徑長度和平均收斂代數(shù)的變化情況，如圖2所示。隨著α值的增大，螞蟻傾向于沿著先前螞蟻走過的路徑轉(zhuǎn)移，從收斂代數(shù)也可見，隨著α值的增大，算法很容易收斂到局部極?。欢?dāng)α值過小時，螞蟻搜索新路徑的能力增強，但收斂速度變慢。參考測試結(jié)果，選取α值為1時能同時兼顧算法性能和搜索效率，較為合適。

(a)平均路徑長度

(b)平均收斂代數(shù)

2.3期望啟發(fā)因子(β)

期望啟發(fā)因子β反映的是螞蟻在運動過程中距離啟發(fā)信息在螞蟻選擇路徑中受重視程度。同樣，在保持其它參數(shù)不變的前提下，使β值在[0,5]范圍內(nèi)由小到大變化進(jìn)行50次獨立隨機測試，考察螞蟻平均路徑長度和平均收斂代數(shù)的變化情況，如圖3所示。由圖可見，增大β值，算法收斂速度加快，螞蟻選擇距離近的路徑可能性加大，但是，β值過大，將淡化螞蟻信息素的指導(dǎo)作用，使其容易陷入局部極??；而β值過小，算法搜索效率會大大降低。依據(jù)測試結(jié)果，為保證規(guī)劃性能，β值選取2左右為宜。

(a)平均路徑長度

(b)平均收斂代數(shù)

2.4導(dǎo)向權(quán)啟發(fā)因子(γ)

導(dǎo)向權(quán)啟發(fā)因子γ是勢場法優(yōu)化規(guī)劃算法的重要體現(xiàn)，反映的是勢場法在螞蟻狀態(tài)轉(zhuǎn)移過程中指導(dǎo)作用的重要程度。同樣，在保持其它參數(shù)不變的前提下，使γ值在[0,5]范圍內(nèi)由小到大變化進(jìn)行50次獨立隨機測試，考察螞蟻平均路徑長度和平均收斂代數(shù)的變化情況，如圖4所示。由結(jié)果可見，減小γ值，相當(dāng)于削弱勢場法的導(dǎo)向作用，算法趨向于單一的蟻群搜索，其收斂代數(shù)增大，搜索性能會變差；而增大γ值，算法的性能則主要由勢場法來體現(xiàn)，其全局搜索能力下降，容易陷入局部極小。因此，為兼顧兩種算法的優(yōu)勢，依據(jù)測試結(jié)果，選取γ值為2左右較為理想。

(a)平均路徑長度

(b)平均收斂代數(shù)

2.5清晰度衰減系數(shù)(ρ)

清晰度衰減系數(shù)ρ表示的是路徑上螞蟻信息素隨時間推移揮發(fā)后的殘余量。同樣，在保持其它參數(shù)不變的前提下，使ρ值在[0,1]范圍內(nèi)由小到大變化進(jìn)行50次獨立隨機測試，考察螞蟻平均路徑長度和平均收斂代數(shù)的變化情況，如圖5所示。由結(jié)果可見，ρ值越大，算法收斂性能加快，但是，算法很容易陷入局部極小，其全局搜索性能變差；而減小ρ值，螞蟻信息素啟發(fā)作用變?nèi)?，算法趨向于隨機搜索，影響其規(guī)劃性能。權(quán)衡算法收斂性及全局搜索性能，選取ρ值為0.2左右為宜。

(a)平均路徑長度

(b)平均收斂代數(shù)

3結(jié)語

本文在研究基于APF導(dǎo)向的蟻群算法模型的基礎(chǔ)上，通過一系列仿真數(shù)值實驗，利用大量的數(shù)據(jù)分析了算法中m、α、β、γ、和ρ等參數(shù)的不同取值對算法性能的影響。通過仿真實驗驗證，提出了最優(yōu)參數(shù)組合方法，對于大多數(shù)蟻群優(yōu)化問題而言，本文提出的參數(shù)優(yōu)化方法都能使算法快速、有效地找到全局最優(yōu)解，提高了算法的效率，對基于APF導(dǎo)向的蟻群算法在航路搜索應(yīng)用中有一定的參考價值。

參考文獻(xiàn)

[1] 董文洪,易波,栗飛.無人機航路規(guī)劃環(huán)境模型研究[J].計算機工程與應(yīng)用,2012,48(15):236-239.

[2] 林娜,張亞倫.自適應(yīng)RRT無人機航路規(guī)劃算法研究與仿真[J].計算機仿真,2015,32(1):73-77.

[3] 魏星,李燕.蟻群算法中參數(shù)優(yōu)化及其仿真研究[J].制造業(yè)自動化,2015,37(5)：33-35.

[4] 梁亞瀾,聶長海.覆蓋表生成的遺傳算法配置參數(shù)優(yōu)化[J].計算機學(xué)報,2012,35(7):1522-1538.

[5] 王芳,李昆鵬,袁明新.一種人工勢場導(dǎo)向的蟻群路徑規(guī)劃算法[J].計算機科學(xué)，2014，41(11A)：47-50.

[6] 袁明新,王孫安,李昆鵬,等.基于勢場法優(yōu)化的蟻群免疫網(wǎng)絡(luò)路徑規(guī)劃研究[J].系統(tǒng)仿真學(xué)報,2009,21(15):4686-4690.

[7] 趙英淳,何雅玲,席奐,等.采用蟻群算法的中溫余熱有機朗肯循環(huán)性能參數(shù)優(yōu)化[J].西安交通大學(xué)學(xué)報,2013,47(11):29-34.

[責(zé)任編輯、校對：周千]

Study on Parameter Optimization of Path Planning Based on APF-Guided Ant Colony Algorithm

WANGFang1,LIKun-peng2

(1.College of Mechanical Engineering,Xi′an Aeronautical University,Xi′an 710077,China;2.Key Laboratory of Road Construction Technology and Equipment of MOE,Chang′an University,Xi′an 710064,China)

Abstract：Parameter optimization rules are proposed for APF-guided ant colony algorithm,which is used for path planning.The paper analyzes the principles for selecting parameters such as m,α,β,γ,and ρ in APFGA algorithm.The reasonable selection of these parameters effectively prevents ant colony search from falling into local optimization,accelerates the speed of the algorithm,and enhances the efficiency of ant colony search.Experiment results offer the basis of parameter selection.The performance of the ant colony algorithm can be effectively improved through reasonably setting parameters,which is favorable for the application and promotion of APFGA algorithm in path planning.

Key words：path planning;parameter optimization;search efficiency

收稿日期：2016-04-17

基金項目：中央高?；究蒲袠I(yè)務(wù)費專項資金資助項目(0009-2014G1251028);西安航空學(xué)院校級科研項目(12XP818)

作者簡介：王芳(1987-)，女，山西長治人，講師，主要從事優(yōu)化設(shè)計及智能優(yōu)化算法研究。

中圖分類號：V279;TP301.6

文獻(xiàn)標(biāo)識碼：A

文章編號：1008-9233(2016)03-0046-05