頭腦風(fēng)暴優(yōu)化算法求解帶轉(zhuǎn)角能耗多無人機(jī)路徑規(guī)劃問題

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

關(guān)鍵詞： 頭腦風(fēng)暴優(yōu)化算法； 無人機(jī)； 路徑規(guī)劃問題； 分階段貪婪法解碼策略； 2-opt； 隨機(jī)反轉(zhuǎn)變換； 部分匹配變換

中圖分類號： TP301"" 文獻(xiàn)標(biāo)志碼： 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 引言

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

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

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

3 實驗與分析

3.1 實驗環(huán)境

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

本文選用了型號為X4108的六軸無人機(jī)進(jìn)行仿真實驗，電池容量為10 000 mAh，電壓為11.1 V，視在電能為399 600 W·s。從文獻(xiàn)［1］可知，取SPc=15 m/s，PWc=429.870 5 W；無人機(jī)開始階段加速度=1 m/s，到達(dá)階段的加速度=-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 實驗結(jié)果與分析

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

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

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

從圖5和表3可以看出：

a）采用相同局部搜索策略的情況下，DBSO-OS的尋優(yōu)結(jié)果優(yōu)于BSO-OS。由此證明，本文離散的頭腦風(fēng)暴相關(guān)算子優(yōu)于傳統(tǒng)的連續(xù)頭腦風(fēng)暴相關(guān)算子，能有效提高算法的全局收斂能力。

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

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

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

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

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

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

4 結(jié)束語

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

參考文獻(xiàn)：

［1］東方，吳媚，朱文捷，等.物聯(lián)網(wǎng)環(huán)境下面向能耗優(yōu)化的無人機(jī)飛行規(guī)劃［J］.東南大學(xué)學(xué)報：自然科學(xué)版，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］蔡延光，王世豪，戚遠(yuǎn)航，等.帝國競爭算法求解CVRP［J］.計算機(jī)應(yīng)用研究，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］周克良，龔達(dá)欣，張宇龍.區(qū)域破壞重建的蟻群優(yōu)化算法［J］.計算機(jī)工程與應(yīng)用，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］蔡延光，陳厚仁，戚遠(yuǎn)航.混沌煙花算法求解旅行商問題［J］.計算機(jī)科學(xué)，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.）