頭腦風暴優化算法求解帶轉角能耗多無人機路徑規劃問題

摘 要： 多臺無人機協同完成野外傳感器數據采集的工作中，建立具有精確能耗模型的多無人機路徑規劃問題模型尤為重要。提出了帶轉角能耗多無人機路徑規劃問題（multi-UAV path planning with angular energy consumption，MUPP-AEC）模型，該模型考慮了無人機在加速、減速、勻速、轉角等飛行條件下的能耗差異。針對MUPP-AEC的特點，提出目標空間聚類離散頭腦風暴優化算法（discrete brain storm optimization algorithm in objective space，DBSO-OS）。該算法采用個體空間整數編碼和帶2-opt的分階段貪婪法解碼策略，并對擾動算子和個體更新算子進行了離散化定義。個體更新算子中采用了混合隨機反轉變換和部分匹配變換的生成策略。實驗結果表明：DBSO-OS能有效地求解MUPP-AEC；所提離散頭腦風暴算子在全局收斂能力、求解精度和穩定性等方面均優于傳統頭腦風暴算子；在中小規模測試算例和較大規模測試算例的測試中，DBSO-OS優于對比算法。

關鍵詞： 頭腦風暴優化算法； 無人機； 路徑規劃問題； 分階段貪婪法解碼策略； 2-opt； 隨機反轉變換； 部分匹配變換

中圖分類號： TP301"" 文獻標志碼： A

文章編號： 1001-3695（2022）01-031-0177-06

doi：10.19734/j.issn.1001-3695.2021.04.0160

Brain storm optimization algorithm for multi-UAV path planning with angular energy consumption

Qi Yuanhang1，2， Huang Zijun1， Zeng Chuxiang1， Huang Gewen3， Wang Fujie4

（1.School of Computer Science， University of Electronic Science amp; Technology of China， Zhongshan Institute， Zhongshan Guangdong 528402， China； 2.School of Computer Science amp; Engineering， University of Electronic Science amp; Technology of China， Chengdu" 611731， China； 3.Information amp; Network Center， Jiaying University， Meizhou Guangdong 514015， China； 4.School of Electrical Engineering amp; Intelligentization， Dongguan University of Technology， Dongguan Guangdong 523808， China）

Abstract： In view of the application scenarios that multiple UAVs cooperate with each other to complete the field sensor data collection task，it is particularly important to establish a path planning problem model for multiple UAVs with accurate energy consumption model.This paper presented the MUPP-AEC problem.The MUPP-AEC toke into account the differences in energy consumption under UAV acceleration，deceleration，cruising in constant speed and turning.For solving the MUPP-AEC，this paper proposed the DBSO-OS.In DBSO-OS，this paper proposed individual space integer encoding and the phased greedy decoding strategy with 2-opt，and defined the perturbation operator and individual update operator discretely.The individual update operators adopted the new individual generation strategy utilizing the random inversion transformation and the partial matching transformation.The experimental results show that the proposed algorithm can effectively solve the MUPP-AEC.The proposed discrete brainstorm operator is superior to the traditional brainstorm operators in terms of global convergence ability，convergence precision，and stability.In the small and medium-sized test cases and the large test cases，the proposed algorithm is better than the compared algorithms.

Key words： brain storm optimization algorithm； UAV； path planning； phased greedy decoding strategy； 2-opt； random inversion transformation； partial matching transformation

0 引言

隨著物聯網技術的發展，具有近距離傳輸能力的傳感器網絡越來越被廣泛應用于各種野外應用場合中。傳感器較分散的場景中，存在傳感器數據采集耗費人力物力、實時性不高等問題。無人機技術作為一個新興的技術，具有速度快、使用方便靈活、成本低等特點，適合用于野外傳感器的數據采集。考慮無人機攜帶電池容量有限，需要規劃無人機的飛行路徑以優化無人機能耗并滿足問題的約束條件，近年來多個研究者對一些特定場景下無人機路徑優化進行了相關研究［1～5］。東方等人［1］考慮無人機電池容量限制，通過實驗得到了不同轉彎角度、飛行速度等條件下較為精確的無人機能耗模型，基于能耗模型進行了單無人機的路徑規劃。文獻［5］研究并求解了無人機編隊對特定區域持續監視的路徑規劃問題。Zhu等人［6］構建了滿足最大曲率約束的無人機最短飛行路徑，并提出了多無人機地震后快速評估路徑問題模型。據筆者所知，考慮無人機加速、減速、勻速、轉角等不同飛行條件下能耗差異的多臺無人機路徑問題還沒有被研究。

近年來智能優化算法被廣泛應用于優化問題的求解。頭腦風暴算法（brain storm optimization algorithm，BSO）是由文獻［7］于2011年提出的一種群智能優化算法，該算法模擬人類通過頭腦風暴方法得到解決方案的機制，通過重復執行發散和聚類過程來進行問題空間的分布式搜索和全局優化。為了減少運算負載，文獻［8］于2015年進一步提出了目標空間聚類離散頭腦風暴優化算法（brain storm optimization algorithm in objective space，BSO-OS），該算法減低了計算負載并且具有良好的收斂速度和求解精度。Niu等人［9］對同一個投資組合優化問題分別采用BSO和BSO-OS進行求解，通過對比證明BSO-OS優于BSO。Nath等人［10］采用BSO-OS求解可靠性冗余分配問題。Rauniyar等人［11］采用BSO-OS對污染—路徑問題進行了求解。但傳統目標空間聚類頭腦風暴優化（BSO-OS）算法求解大規模離散問題存在收斂速度慢、求解精度不高等問題。

本文提出了求解帶轉角能耗多無人機路徑規劃問題（multi-UAV path planning with angular energy consumption，MUPP-AEC）的目標空間聚類離散頭腦風暴優化算法（discrete brain storm optimization algorithm in objective space，DBSO-OS）。首先，建立MUPP-AEC問題的數學模型，進一步地，本文提出目標空間聚類離散頭腦風暴優化算法，是對原始目標空間聚類頭腦風暴優化算法進行離散化改進，采用個體空間整數編碼和帶2-opt的分階段貪婪法解碼策略，對擾動算子和個體更新算子進行了離散化定義。最后，通過實驗證明了所提算法具有較好的全局優化能力、局部搜索能力和求解效率。

3 實驗與分析

3.1 實驗環境

本文算法實驗環境為：CPU為Intel CoreTM i3-8100 @3.60 GHz，內存為8 GB，操作系統為64位Windows 10，仿真軟件使用Visual Studio 2017。

本文選用了型號為X4108的六軸無人機進行仿真實驗，電池容量為10 000 mAh，電壓為11.1 V，視在電能為399 600 W·s。從文獻［1］可知，取SPc=15 m/s，PWc=429.870 5 W；無人機開始階段加速度=1 m/s，到達階段的加速度=-1 m/s，Ta=15 s，Da=112.5 m，由Pacc=1.3876t2-10.5910t+381.7900［1］得到Ea=6 096.3 J；Td=15 s，Dd=112.5 m，由Pdec=0.0114t4-0.7279t3+12.8450t2-69.9580t+389.7400［1］得到Ed=4944.1875 J；EAijl=5.3316θijl+104.65［1］。

3.2 實驗結果與分析

實驗1 為了具體分析DBSO-OS求解MUPP-AEC的有效性，本實驗中，本文基于一個CVRP基準算例設計了實驗算例，實驗1算例的相關信息如表1所示。其中，P0代表中心點，P1～P35代表巡航地點。DBSO-OS計算參數中，取ELITE_PERC=0.1，Pd=0.1，Pone=0.8，Pe=0.2。最大迭代次數為1 000，種群規模為80，算法獨立運行10次，取最優結果進行分析。實驗結果如表2和圖4所示。

從圖4可以看出，每臺無人機從中心點出發并返回中心點，形成一條完整的閉合路徑；每個巡航地點有且只有被訪問一次。因此，整個巡航路徑也滿足MUPP-AEC的式（5）～（7）（9）的約束。表2為DBSO-OS求解MUPP-AEC的結果，由表2可見，每條巡航路徑的能耗不超出電池容量，符合式（8）的約束。綜上，所提算法能夠有效地求解MUPP-AEC。

進一步，將本文算法與三個算法進行對比。其中：a）基本目標空間頭腦風暴算法（brain storm optimization algorithm in objective space，BSO-OS）［8］，采用實數編碼；b）遺傳算法（genetic algorithm，GA），采用整數編碼，采用部分匹配交叉算子和反轉變異算子產生新后代，采用輪盤選擇策略選擇下一代種群；c）混沌煙花算法（chaotic fireworks algorithm，CFWA）［15］，采用實數編碼。三個算法均采用2-opt作為局部優化策略，最大迭代次數為1 000，種群規模為80。BSO-SO計算參數中，取ELITE_PERC=0.1，P_one=0.8，P_elite=0.2。GA的計算參數中，取crossover_probability=0.5，mutate_probability=0.1。CFWO的計算參數中，取N=5，GM=5，DENSITY=16，RADIUS=2 000。每個算法獨立運行10次，取最優結果進行比較。每種算法在獲取最優解決方案過程中，適應度值隨著迭代次數改變的過程如圖5所示，四種算法求解本實驗算例的結果如表3所示。

從圖5和表3可以看出：

a）采用相同局部搜索策略的情況下，DBSO-OS的尋優結果優于BSO-OS。由此證明，本文離散的頭腦風暴相關算子優于傳統的連續頭腦風暴相關算子，能有效提高算法的全局收斂能力。

b）DBSO-OS、BSO-OS、GA和CFWO的最優解分別為2 196.41、2 792.9、2 267.86和4 121.54，收斂到最優方案的迭代次數分別是486、796、982和503。DBSO-OS收斂到最優方案的速度明顯優于BSO-OS、GA和CFWO，在求解精度DBSO-OS同樣占優。

接著，對四個算法的10次實驗結果進行討論和分析，結果如圖6所示。從圖6可以看出，DBSO-OS在10次計算結果的平均值最低，GA次之，BSO-OS再次之，CFWO最高。值得注意的是，DBSO-SO、GA在10次測試所得到的方案適應度變化范圍較小，表明穩定性優于BSO-OS，表明整數編碼的算法具有較好的穩定性。由此證明，本文所提離散頭腦風暴算子比傳統頭腦風暴算子具有更好的穩定性。

實驗2 為了進一步分析本文算法與其他算法的優劣性，本實驗分別將使用DBSO-OS與BSO-OS、GA和CFWO對set A、set B、set P基準算例中的24個代表算例進行求解，計算結果和運行時間如表4所示，算例中的1個單位距離代表實際距離50 m。表4中，best為所有結果最優解，avg為所有結果平均值，CT為10次計算的求解時間平均值，單位為s。計算參數與實驗1相同，10次結果最優解和平均值分別橫向比較，并將優勝的結果加粗標注。

由表4可以看出，在平均值比較上，DBSO-OS、BSO-OS、GA和CFWO取得優勝次數分別為20、1、5和1。在最優解比較上，DBSO-OS、BSO-OS、GA和CFWO取得優勝次數分別為20、1、7和1。從表4求解時間的比較上，DBSO-OS求解時間是BSO-OS的三倍左右，比GA高大約50%，但都在10 s以內，屬于合理范圍。實驗結果證明了離散頭腦風暴算法在中小規模算例上具有較好的求解精度和穩定性。

實驗3 為了進一步驗證DBSO-OS對較大規模算例的尋優能力，選取基準算例setM中的M-n101-k10、M-n121-k7、M-n151-k12、M-n200-k16、M-n200-k17進行實驗，設置MaxIter=4 000，其余計算參數與實驗1相同，計算結果和運行時間如表5所示。

由表5可以看出，在平均值和最優解來看，DBSO-OS均優于BSO-OS、GA和CFWO，證明DBSO-OS在求解精度和求解的穩定性方面在較大規模算例有較好的表現。從表5求解時間的比較上，DBSO-OS求解時間所有算例平均值是BSO-OS和GA的3.96倍和1.38倍，200個點規模算例在236.865 s和234.950 s，屬于合理范圍。實驗結果證明了離散頭腦風暴算法在較大規模算例上也具有較好的全局搜索能力和局部優化能力。

4 結束語

針對具有精確能耗模型的多無人機路徑規劃問題，本文提出MUPP-AEC模型。進一步地，本文以原始目標空間聚類頭腦風暴優化算法為基礎，提出目標空間聚類離散頭腦風暴優化算法（DBSO-OS），采用個體空間整數編碼和帶2-opt的分階段貪婪法解碼策略，對擾動算子和個體更新算子進行了離散化定義。實驗結果表明：本文算法能有效地求解帶轉角能耗多無人機路徑規劃問題；本文提出的離散頭腦風暴算子在全局收斂能力、求解精度、求解時間和穩定性等方面均優于傳統頭腦風暴算子；在中小規模測試算例和較大規模測試算例的測試中，目標空間聚類離散頭腦風暴優化算法優于BSO-OS、GA和CFA。對帶權重的多無人機路徑規劃問題、帶時間窗的多無人機路徑規劃問題將是下一步的研究方向。

參考文獻：

［1］東方，吳媚，朱文捷，等.物聯網環境下面向能耗優化的無人機飛行規劃［J］.東南大學學報：自然科學版，2020，50（3）：555-562. （Dong Fang，Wu Mei，Zhu Wenjie，et al.Energy-efficient flight planning for UAV in IoT environment［J］.Journal of Southeast University：Natural Science Edition，2020，50（3）：555-562.）

［2］Bahabry A，Wan Xiangpeng，Ghazzai H，et al.Low-altitude navigation for multi-rotor drones in urban areas［J］.IEEE Access，2019，7：87716-87731.

［3］Lin Yu，Wang Tianyu，Wang Shaowei，et al.Trajectory planning for multi-UAV assisted wireless networks in post-disaster scenario［C］//Proc of IEEE Global Communications Conference.Piscataway，NJ：IEEE Press，2019：1-6.

［4］Zhen Lu，Li Miao，Laporte G，et al.A vehicle routing problem arising in unmanned aerial monitoring［J］.Computers amp; Operations Research，2019，105：1-11.

［5］Stodola P.Unmanned surveillance problem：mathematical formulation，solution algorithms，and experiments［J］.Military Operations Research，2020，25（2）：31-47.

［6］Zhu Moning，Zhang Xuehua，Luo He，et al.Optimization dubins path of multiple UAVs for post-earthquake rapid-assessment［J］.Applied Sciences-Basel，2020，10（4）：1388.

［7］Shi Yuhui.Brain storm optimization algorithm［M］//Tan Ying，Shi Yuihui，Chai Yi，et al.Advances in Swarm Intelligence.Berlin：Springer，2011：303-309.

［8］Shi Yuhui.Brain storm optimization algorithm in objective space［C］//Proc of IEEE Congress on Evolutionary Computation.Piscataway，NJ：IEEE Press，2015：1227-1234.

［9］Niu Ben，Liu Jia，Liu Jing，et al.Brain storm optimization for portfolio optimization［M］//Tan Ying，Shi Y，Li Li.Advances in Swarm Intelligence.Cham：Springer，2016：416-423.

［10］Nath R，Rauniyar A，Muhuri P K，et al.Brain storm optimization algorithm in objective space for reliability-redundancy allocation problem［C］//Proc of IEEE Congress on Evolutionary Computation.Piscata-way，NJ：IEEE Press，2019：248-253.

［11］Rauniyar A，Nath R，Muhuri P K，et al.Modified brain storm optimization algorithm in objective space for pollution-routing problem［C］//Proc of IEEE Congress on Evolutionary Computation.Piscataway，NJ：IEEE Press，2019：242-247.

［12］Larraaga P，Kuijpers C M H，Murga R H，et al.Genetic algorithms for the travelling salesman problem：a review of representations and operators［J］.Artificial Intelligence Review，1999，13（2）：129-170.

［13］蔡延光，王世豪，戚遠航，等.帝國競爭算法求解CVRP［J］.計算機應用研究，2021，38（3）：782-786. （Cai Yanguang，Wang Shihao，Qi Yuanhang，et al.Imperialist competitive algorithm for solving CVRP［J］.Application Research of Computers，2021，38（3）：782-786.）

［14］周克良，龔達欣，張宇龍.區域破壞重建的蟻群優化算法［J］.計算機工程與應用，2020，56（14）：62-67. （Zhou Keliang，Gong Da-xin，Zhang Yulong.Ant colony optimization algorithm for regional destructive reconstruction［J］.Computer Engineering and Applications，2020，56（14）：62-67.）

［15］蔡延光，陳厚仁，戚遠航.混沌煙花算法求解旅行商問題［J］.計算機科學，2019，46（S1）：85-88. （Cai Yanguang，Chen Houren，Qi Yuanhang.Chaotic fireworks algorithm for solving travelling salesman problem［J］.Computer Science，2019，46（S1）：85-88.）