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

王　芳，李昆鵬

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

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

王芳1，李昆鵬2

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

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

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

0引言

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

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

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

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

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

θ=∠(Fatt+∑Frep)

(1)

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

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

(2)

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

利用人工勢場修正螞蟻狀態(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)為導向權；γ為導向權啟發(fā)因子。ηij(t)為距離定義式。

螞蟻走過的路徑上會留下信息素，同時為了避免路徑上因殘留信息素過多而造成啟發(fā)信息被淹沒，信息素會隨著時間的流逝而揮發(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)化

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

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)由小到大變化進行50次獨立隨機測試，考察螞蟻平均路徑長度和平均收斂代數(shù)的變化情況，如圖1所示。由圖可見，兼顧算法的計算精度和運行效率，m值選取15較為合適。

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

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

(a)平均路徑長度

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

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

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

(a)平均路徑長度

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

2.4導向權啟發(fā)因子(γ)

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

(a)平均路徑長度

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

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

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

(a)平均路徑長度

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

3結(jié)語

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

參考文獻

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

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

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

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

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

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

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

[責任編輯、校對：周千]

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è)務費專項資金資助項目(0009-2014G1251028);西安航空學院校級科研項目(12XP818)

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

中圖分類號：V279;TP301.6

文獻標識碼：A

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