基于改進(jìn)人工蜂群算法的多無(wú)人機(jī)滅火任務(wù)規(guī)劃

張小孟，胡永江，李文廣，龐強(qiáng)偉，袁國(guó)剛

（1.陸軍工程大學(xué) 無(wú)人機(jī)工程系，石家莊 050003；2.31700 部隊(duì)，遼陽(yáng) 111000）

隨著無(wú)人機(jī)技術(shù)的快速發(fā)展，其在情報(bào)搜集、電子偵察、指控通信、戰(zhàn)損評(píng)估等軍事領(lǐng)域，以及災(zāi)情預(yù)警、事故救援、消防滅火等民用領(lǐng)域都發(fā)揮著越來(lái)越重要的作用。無(wú)人機(jī)運(yùn)用模式也逐漸由單機(jī)向多機(jī)協(xié)同方向發(fā)展[1]，其中滅火救援是多無(wú)人機(jī)應(yīng)用的一個(gè)重要方面[2]。受到用火習(xí)俗以及氣候等多種因素的影響，山火災(zāi)害特別容易在短時(shí)間內(nèi)集中爆發(fā)。當(dāng)一個(gè)區(qū)域同時(shí)爆發(fā)多處山火時(shí)，需要迅速地根據(jù)各個(gè)火點(diǎn)的火情及位置情況，對(duì)其進(jìn)行滅火救援，而使用無(wú)人機(jī)投放滅火彈對(duì)山火火點(diǎn)進(jìn)行滅火是一種快速高效的滅火方法。

在火情高發(fā)期，通過(guò)使用多個(gè)無(wú)人機(jī)共同對(duì)多個(gè)火點(diǎn)目標(biāo)投放滅火彈，可以快速實(shí)現(xiàn)對(duì)多個(gè)火點(diǎn)火情的控制。無(wú)人機(jī)投放滅火彈需要針對(duì)具體的任務(wù)需求，為各無(wú)人機(jī)合理分配火點(diǎn)目標(biāo)，使各無(wú)人機(jī)以較小的代價(jià)完成滅火救援任務(wù)，該過(guò)程即為多無(wú)人機(jī)對(duì)多火點(diǎn)火場(chǎng)滅火救援任務(wù)規(guī)劃過(guò)程。

目前在多無(wú)人機(jī)任務(wù)規(guī)劃過(guò)程中,關(guān)于無(wú)人機(jī)航路的可行性以及避險(xiǎn)問(wèn)題規(guī)劃的研究已相對(duì)成熟[3-7]。但對(duì)于高效救援多個(gè)不同價(jià)值目標(biāo)時(shí)的任務(wù)規(guī)劃問(wèn)題，還有一定的研究空間。針對(duì)多無(wú)人機(jī)對(duì)多目標(biāo)任務(wù)規(guī)劃問(wèn)題，文獻(xiàn)[8]建立了混合整數(shù)線性規(guī)劃模型，文獻(xiàn)[9]建立了多目標(biāo)優(yōu)化問(wèn)題模型，文獻(xiàn)[10]建立了多旅行商問(wèn)題模型。根據(jù)這些模型，文獻(xiàn)[11]提出了一種改進(jìn)量子粒子群算法，文獻(xiàn)[12]通過(guò)引入Metropolis 準(zhǔn)則的方式提出改進(jìn)人工蜂群算法，文獻(xiàn)[13]設(shè)計(jì)了一種蝗蟲(chóng)仿生算法，但是這些算法局限于傳統(tǒng)單一約束問(wèn)題，無(wú)法求解多約束的實(shí)際問(wèn)題，算法的普適性很差。文獻(xiàn)[14]提出了一種基于整數(shù)編碼的多種群混合遺傳算法(Multi-Population Hybrid Genetic Algorithm,MPHGA)，該算法的收斂性較強(qiáng)，且任務(wù)規(guī)劃效果較好，但該算法僅適用于目標(biāo)價(jià)值固定的情況，對(duì)于目標(biāo)價(jià)值變化的情況普適性較差。

上述方法在一定程度上能夠解決多無(wú)人機(jī)對(duì)多目標(biāo)的任務(wù)規(guī)劃問(wèn)題，但在解決多無(wú)人機(jī)對(duì)多火點(diǎn)火場(chǎng)滅火救援任務(wù)規(guī)劃問(wèn)題時(shí)仍存在以下幾點(diǎn)不足：1）忽略了火點(diǎn)目標(biāo)救援價(jià)值的時(shí)變性對(duì)任務(wù)規(guī)劃效果的影響[15]。在實(shí)際應(yīng)用中，不同的目標(biāo)對(duì)救援效果有著不同的影響，甚至在救援過(guò)程的不同時(shí)期，同一個(gè)目標(biāo)產(chǎn)生的影響也是不同的，即目標(biāo)對(duì)整體救援態(tài)勢(shì)的影響是隨時(shí)間變化的。在任務(wù)規(guī)劃的過(guò)程中必須考慮目標(biāo)價(jià)值的時(shí)變性，進(jìn)而增強(qiáng)任務(wù)規(guī)劃的可靠性。2）沒(méi)有考慮救援資源的有限性[16]。在實(shí)際滅火救援過(guò)程中，可用的無(wú)人機(jī)數(shù)量和掛載滅火彈的數(shù)量有限，可能無(wú)法保證對(duì)所有目標(biāo)實(shí)施救援，指揮者需要根據(jù)目標(biāo)實(shí)際價(jià)值和位置情況進(jìn)行綜合決策。因此在救援資源有限的條件下，任務(wù)規(guī)劃必須考慮指揮者的綜合決策，以保證用有限的救援資源，收到盡可能大的救援效益。3）未考慮實(shí)際情況對(duì)任務(wù)規(guī)劃算法的約束性[14]。在多無(wú)人機(jī)對(duì)多火點(diǎn)火場(chǎng)滅火救援任務(wù)規(guī)劃過(guò)程中，由于無(wú)人機(jī)掛載滅火彈數(shù)量和任務(wù)無(wú)人機(jī)的航程有限，尋優(yōu)過(guò)程中的所有可行解都需要滿(mǎn)足載彈量和無(wú)人機(jī)航程限制，才能保證算法收斂的準(zhǔn)確性和快速性，防止無(wú)用解占用規(guī)劃資源。

針對(duì)以上問(wèn)題，本文提出了一種多無(wú)人機(jī)對(duì)多火點(diǎn)火場(chǎng)滅火救援任務(wù)規(guī)劃方法。首先，在考慮火點(diǎn)目標(biāo)價(jià)值時(shí)變性的基礎(chǔ)上，建立了目標(biāo)價(jià)值隨時(shí)間變化的多無(wú)人機(jī)任務(wù)規(guī)劃模型，可實(shí)現(xiàn)根據(jù)指揮者的決策意圖來(lái)進(jìn)行合理救援。然后，在標(biāo)準(zhǔn)人工蜂群算法的基礎(chǔ)上引入了整數(shù)編碼以及三種算子操作，用來(lái)解決有約束的任務(wù)規(guī)劃問(wèn)題。最后，進(jìn)行了仿真實(shí)驗(yàn)。結(jié)果表明該任務(wù)規(guī)劃算法具有尋優(yōu)能力強(qiáng)、尋優(yōu)效率高的優(yōu)點(diǎn)，不僅可以有效解決目標(biāo)價(jià)值隨時(shí)間變化的任務(wù)規(guī)劃問(wèn)題，而且可以在無(wú)人機(jī)數(shù)量不能滿(mǎn)足對(duì)所有火點(diǎn)目標(biāo)進(jìn)行飽和救援的情況下，根據(jù)指揮者的決策意圖進(jìn)行有效的任務(wù)規(guī)劃。

1 多目標(biāo)救援模型

1.1 問(wèn)題描述

假設(shè)在進(jìn)行滅火任務(wù)之前，通過(guò)前期對(duì)區(qū)域火情的分析，已確定各個(gè)火點(diǎn)目標(biāo)的位置信息、目標(biāo)價(jià)值以及價(jià)值隨時(shí)間變化情況等。在實(shí)施滅火任務(wù)過(guò)程中，各無(wú)人機(jī)均從地面站起飛，根據(jù)任務(wù)規(guī)劃結(jié)果有序完成對(duì)指定火點(diǎn)目標(biāo)的救援任務(wù)，并在任務(wù)結(jié)束后回到地面站。

多無(wú)人機(jī)對(duì)多火點(diǎn)火場(chǎng)滅火救援任務(wù)規(guī)劃問(wèn)題可描述為：給定待救援的火點(diǎn)目標(biāo)集合target = {T1,T2…TNt}和Nu架滅火無(wú)人機(jī)UAVi(i=1,2…Nu)，所有待救援目標(biāo)的價(jià)值集合為Value = {V1,V2…VNt}，各個(gè)目標(biāo)價(jià)值隨時(shí)間改變情況的集合為Change = {C1,C2…CNt}。

在選定地面站位置的條件下，設(shè)計(jì)一種可通過(guò)調(diào)節(jié)整體任務(wù)價(jià)值和路徑代價(jià)的權(quán)重系數(shù)來(lái)實(shí)現(xiàn)指揮員決策意圖的任務(wù)規(guī)劃方法。同時(shí)在救援資源有限的情況下實(shí)現(xiàn)救援目標(biāo)價(jià)值的最大化，增強(qiáng)規(guī)劃方法的普適性。

1.2 目標(biāo)函數(shù)

多無(wú)人機(jī)執(zhí)行對(duì)多火點(diǎn)火場(chǎng)滅火救援任務(wù)需要在獲取盡可能大的救援總收益同時(shí)，盡可能地減小無(wú)人機(jī)的滯空時(shí)間，降低任務(wù)執(zhí)行過(guò)程中的能量損耗，即需要在目標(biāo)總收益與無(wú)人機(jī)總滯空時(shí)間之間進(jìn)行綜合優(yōu)化。

在無(wú)人機(jī)實(shí)施目標(biāo)救援的過(guò)程中，設(shè)Xi j為決策變量，其取值為1 時(shí)表示無(wú)人機(jī)UAVi對(duì)救援目標(biāo)Tj實(shí)施救援，0 表示不實(shí)施救援。

（1）救援目標(biāo)的總收益。假設(shè)目標(biāo)價(jià)值隨時(shí)間的改變情況為目標(biāo)價(jià)值關(guān)于時(shí)間的負(fù)指數(shù)函數(shù)，則總價(jià)值收益為：

其中C j=e-d jt為目標(biāo)價(jià)值隨時(shí)間變化的函數(shù)，dj為目標(biāo)Tj隨時(shí)間的衰減的系數(shù)；ti為無(wú)人機(jī)UAVi從離開(kāi)基地到救援目標(biāo)Tj時(shí)所經(jīng)歷的時(shí)間。

（2）總滯空時(shí)間。隨著無(wú)人機(jī)在執(zhí)行滅火任務(wù)過(guò)程中滯空時(shí)間的增長(zhǎng)，火情引起的強(qiáng)上升氣流及強(qiáng)熱輻射對(duì)無(wú)人機(jī)造成損傷的概率增加，能量損耗增多，因此要求無(wú)人機(jī)總滯空時(shí)間要盡可能的短，即：

其中pathi為第i架無(wú)人機(jī)UAVi執(zhí)行滅火任務(wù)所分配到的目標(biāo)序列時(shí)所需的路徑代價(jià)，vi為UAVi的巡航速度。

（3）目標(biāo)函數(shù)?？紤]到指揮員需要根據(jù)救援目標(biāo)總收益與總滯空時(shí)間進(jìn)行綜合決策，目標(biāo)函數(shù)通過(guò)分配不同的權(quán)重將多目標(biāo)尋優(yōu)問(wèn)題轉(zhuǎn)換為單目標(biāo)尋優(yōu)問(wèn)題。

其中p，q為權(quán)重系數(shù)，β為補(bǔ)償系數(shù)（使兩個(gè)目標(biāo)函數(shù)處于同一數(shù)量級(jí)）。

1.3 約束條件

（1）單架無(wú)人機(jī)執(zhí)行任務(wù)的能力約束：

其中Bi為第i架無(wú)人機(jī)UAVi的最大掛載滅火彈數(shù)量。

（2）無(wú)人機(jī)的航程約束。受無(wú)人機(jī)機(jī)載能源的限制，無(wú)人機(jī)的航程不能超過(guò)自身最大航程Di，則

（3）目標(biāo)價(jià)值約束。無(wú)人機(jī)執(zhí)行任務(wù)的最大價(jià)值之和不能超過(guò)所有目標(biāo)的總價(jià)值：

2 預(yù)先路徑規(guī)劃

由于在任務(wù)區(qū)域內(nèi)可能存在障礙物、火情引起的強(qiáng)上升氣流及強(qiáng)熱輻射等因素產(chǎn)生的禁飛區(qū)影響無(wú)人機(jī)飛行，為了確保無(wú)人機(jī)在任務(wù)區(qū)域內(nèi)有可飛路徑，在進(jìn)行任務(wù)規(guī)劃之前，需要對(duì)無(wú)人機(jī)的可飛路徑進(jìn)行預(yù)先規(guī)劃，以增強(qiáng)任務(wù)規(guī)劃的可行性及準(zhǔn)確性。

可飛路徑的預(yù)先規(guī)劃首先需要用柵格法在任務(wù)區(qū)域內(nèi)建立包含目標(biāo)位置和禁飛區(qū)的路徑規(guī)劃空間模型，然后利用A 星算法求得初始較優(yōu)路徑，最后在上述求得的較優(yōu)路徑的基礎(chǔ)上，利用遺傳算法求得最優(yōu)路徑。通過(guò)以上算法獲取無(wú)人機(jī)基地到每個(gè)目標(biāo)點(diǎn)和任意兩目標(biāo)點(diǎn)之間的可飛路徑，并準(zhǔn)確計(jì)算得到所有路徑代價(jià)矩陣，為任務(wù)規(guī)劃提供有效依據(jù)。預(yù)先路徑規(guī)劃流程如圖1所示。

圖1 預(yù)先路徑規(guī)劃流程圖Fig.1 Flow chart of advance path planning

3 改進(jìn)的人工蜂群算法

3.1 標(biāo)準(zhǔn)人工蜂群算法

標(biāo)準(zhǔn)人工蜂群算法（Artificial Bee Colony，ABC）包括三個(gè)組成部分，即蜜源位置、花蜜量和三種蜜蜂（雇傭蜂、跟隨蜂和偵察蜂）[17]。每個(gè)蜜源位置代表了需要優(yōu)化問(wèn)題的一個(gè)可行的解決方案，其花蜜量對(duì)應(yīng)于解決方案的質(zhì)量即適應(yīng)度值。每一種蜜蜂都會(huì)執(zhí)行一個(gè)特定的操作來(lái)產(chǎn)生新的候選蜜源位置。雇傭蜂也稱(chēng)為引領(lǐng)蜂，其存儲(chǔ)有某一蜜源的相關(guān)信息，并且可以在蜜源周?chē)褜ば碌拿墼?；跟隨蜂在蜂巢中通過(guò)雇傭蜂分享的信息尋找相關(guān)蜜源，偵察蜂是在雇傭蜂和跟隨蜂都找不到更好的鄰近蜜源時(shí)，進(jìn)行隨機(jī)搜索以尋找新的蜜源位置。因此，標(biāo)準(zhǔn)ABC 算法將雇傭蜂和跟隨蜂視為執(zhí)行局部搜索，而偵察蜂則執(zhí)行全局搜索。

3.2 改進(jìn)的ABC 算法

標(biāo)準(zhǔn)ABC 算法只能用于求解無(wú)約束連續(xù)問(wèn)題，針對(duì)有約束的無(wú)人機(jī)任務(wù)規(guī)劃問(wèn)題，本章采取一種基于整數(shù)編碼的改進(jìn)人工蜂群算法，用以解決有約束的任務(wù)規(guī)劃問(wèn)題，其核心包括種群初始化、改進(jìn)雇傭蜂階段、改進(jìn)跟隨蜂階段以及改進(jìn)偵察蜂階段。

3.2.1 種群初始化

根據(jù)無(wú)人機(jī)以及任務(wù)目標(biāo)的序列信息，借鑒遺傳算法的編碼形式，隨機(jī)生成一個(gè)m=Nt+Nu-1 位的整數(shù)序列（M1,M2…Mm），代表一個(gè)蜜源位置。其中編碼值小于或等于Nt的為目標(biāo)編碼；大于Nt的為無(wú)人機(jī)編碼，假設(shè)為Hj，則無(wú)人機(jī)真實(shí)序列號(hào)為：j=Hj-Nt+1。從左邊開(kāi)始到第一個(gè)無(wú)人機(jī)編碼之前的編碼序列為UAV1救援序列，之后的兩個(gè)相鄰無(wú)人機(jī)編碼之間所對(duì)應(yīng)目標(biāo)編碼組成的序列為UAVj救援序列，UAVj為對(duì)應(yīng)序列最左側(cè)編碼對(duì)應(yīng)無(wú)人機(jī)序列，以此類(lèi)推。

假設(shè)待救援目標(biāo)數(shù)Nt=10，無(wú)人機(jī)數(shù)Nu=3，無(wú)人機(jī)的載彈量B=4，則m=12。如圖2所示，該編碼對(duì)應(yīng)的UAV1救援序列為T(mén)2-T5-T9-T3-T10，UAV2救援序列為T(mén)4-T8-T7，UAV3救援序列為T(mén)1-T6。

圖2 初始蜜源編碼Fig.2 Initial honey source coding

因無(wú)人機(jī)載彈量有限，則兩個(gè)無(wú)人機(jī)編碼之間的目標(biāo)編碼個(gè)數(shù)不能超過(guò)無(wú)人機(jī)最大載彈量，當(dāng)判斷目標(biāo)個(gè)數(shù)超出載彈量時(shí)，對(duì)當(dāng)前的蜜源位置重新初始化，直至滿(mǎn)足條件，因圖2中，UAV1救援目標(biāo)為5 個(gè)，超過(guò)載彈量B=4，不滿(mǎn)足條件，則重新生成蜜源序列，如圖3所示，新序列中各個(gè)無(wú)人機(jī)救援序列分別為：UAV1救援序列為T(mén)2-T5-T9-T3，UAV2救援序列為T(mén)1-T6，UAV3救援序列為T(mén)10-T4-T8-T7,均滿(mǎn)足載彈量要求。

圖3 載彈量約束編碼Fig.3 Payload constraint coding

考慮到無(wú)人機(jī)存在航程約束，當(dāng)無(wú)人機(jī)從基地起飛經(jīng)過(guò)救援目標(biāo)序列再回到基地時(shí)出現(xiàn)路徑代價(jià)之和超過(guò)最大航程約束時(shí)，當(dāng)前蜜源位置也需要重新初始化。

用以上編碼方式生成SN個(gè)整數(shù)序列作為改進(jìn)ABC 算法初始化種群，其中SN是蜜源數(shù)量。

3.2.2 改進(jìn)雇傭蜂階段

雇傭蜂通常在蜜源附近進(jìn)行鄰域搜索。為了表示鄰域搜索的行為，引入逆向算子操作，其過(guò)程如圖4根據(jù)以下步驟進(jìn)行：

圖4 逆向算子操作Fig.4 Reverse operator operation

步驟1 從1 到m（位置總數(shù)）之間隨機(jī)生成兩個(gè)整數(shù)r1和r2；

步驟2 將r1到r2之間的編碼序列反轉(zhuǎn)，得到新序列；

步驟3 檢驗(yàn)新序列是否滿(mǎn)足載彈量和航程約束要求，若滿(mǎn)足則使用新序列碼作為新的蜜源，若不滿(mǎn)足則轉(zhuǎn)至步驟1。

為進(jìn)一步提高鄰域搜索能力，雇傭蜂階段再引入交叉算子操作，用選擇的蜜源和現(xiàn)有最優(yōu)蜜源做為雙親，創(chuàng)造出更好的后代，其操作過(guò)程如圖5按以下步驟進(jìn)行。

圖5 交叉算子操作Fig.5 Crossover operator operation

步驟1 從1 到m之間隨機(jī)生成兩個(gè)整數(shù)r1和r2；

步驟2 選擇r1和r2作為兩個(gè)交叉點(diǎn)；

步驟3 從步驟2 交換的數(shù)據(jù)中通過(guò)映射關(guān)系替換子代中的重復(fù)數(shù)，得到新序列；

步驟4 檢驗(yàn)新序列是否滿(mǎn)足載彈量和航程約束要求，若滿(mǎn)足則使用新編碼序列作為新的蜜源，若不滿(mǎn)足則轉(zhuǎn)至步驟1。

使用逆向算子操作和交叉算子操作對(duì)雇傭蜂進(jìn)行鄰域搜索，并在當(dāng)前蜜源和新的鄰近蜜源之間進(jìn)行貪婪選擇，以保證更好的蜜源被保留下來(lái)供進(jìn)一步進(jìn)化。貪婪選擇是基于蜜源的適應(yīng)度值，計(jì)算公式為：

其中fi是模型的目標(biāo)函數(shù)，fiti為適應(yīng)度函數(shù)。

3.2.3 改進(jìn)跟隨蜂階段

跟隨蜂是按輪盤(pán)賭方式在雇傭蜂種群中選擇的較優(yōu)的種群，計(jì)算公式為：

跟隨蜂階段同樣根據(jù)收益率大小來(lái)選擇蜜源位置，使用逆向算子操作和交叉算子操作來(lái)進(jìn)行鄰域搜索產(chǎn)生新的蜜源，收益率通過(guò)適應(yīng)度值來(lái)表示。同雇傭蜂階段一樣，使用貪婪選擇保留更優(yōu)蜜源。

3.2.4 改進(jìn)偵察蜂階段

如果在有限的迭代次數(shù)內(nèi)，雇傭蜂和跟隨蜂鄰域搜索沒(méi)有找到更優(yōu)蜜源時(shí)，則將其作為偵察蜂。

通過(guò)在現(xiàn)有的最優(yōu)蜜源的基礎(chǔ)上應(yīng)用變異算子操作，使偵察蜂可以在全局范圍內(nèi)發(fā)現(xiàn)新的蜜源，其操作過(guò)程如圖6按以下步驟進(jìn)行。

圖6 變異算子操作Fig.6 Mutation operator operation

步驟1 從1 到m之間隨機(jī)生成一個(gè)整數(shù)r1；

步驟2 將所選序列碼中的r1位置的編碼隨機(jī)變異為另一位置的編碼，假設(shè)為r2位置，交換r1位置和r2位置，得到新序列；

步驟3 檢驗(yàn)新序列是否滿(mǎn)足載彈量和航程約束要求，若滿(mǎn)足則使用新序列碼作為新的蜜源，若不滿(mǎn)足則轉(zhuǎn)至步驟1。

通過(guò)逆向算子操作，雇傭蜂可以生成新的鄰近蜜源，跟隨蜂可以通過(guò)鄰域搜索生成更多的蜜源，用來(lái)提高其局部搜索能力。通過(guò)交叉算子操作，可以進(jìn)一步提高蜂群的局部搜索能力。通過(guò)變異算子操作，偵察蜂可以根據(jù)當(dāng)前最優(yōu)解生成新的蜜源，防止搜索陷入局部最優(yōu)。

為了提高收斂速度和解的多樣性，逆向算子操作和交叉算子操作是在滿(mǎn)足逆向概率Pr和交叉概率Pc（0 ＜Pr，Pc＜ 1）的情況下進(jìn)行的，而變異算子操作是在偵察蜂階段進(jìn)行的，只有當(dāng)雇傭蜂和跟隨蜂在有限次迭代內(nèi)都無(wú)法找到更優(yōu)的蜜源時(shí)，變異算子操作才被激活。

3.3 算法步驟

改進(jìn)ABC 算法步驟如圖7所示。

圖7 改進(jìn)ABC 算法流程圖Fig.7 Improved ABC algorithm flowchart

步驟1：種群初始化。設(shè)置初始化參數(shù)，對(duì)初始蜜源編碼，生成初始種群；

步驟2：改進(jìn)雇傭蜂階段。使用帶概率的逆向算子、交叉算子操作對(duì)每個(gè)雇傭蜂進(jìn)行鄰域搜索，使用貪婪選擇保留更好的解；

步驟3：選擇產(chǎn)生跟隨蜂。按輪盤(pán)賭方式選擇較優(yōu)種群作為跟隨蜂種群；

步驟4：改進(jìn)跟隨蜂階段。同雇傭蜂一樣，使用帶概率的逆向算子、交叉算子操作對(duì)每個(gè)跟隨蜂進(jìn)行鄰域搜索，使用貪婪選擇保留更好的解；

步驟5：判斷是否產(chǎn)生偵察蜂。如果產(chǎn)生，對(duì)當(dāng)前最佳蜜源實(shí)施變異算子操作進(jìn)行全局搜索；

步驟6：判斷是否滿(mǎn)足終止條件。若滿(mǎn)足則輸出最優(yōu)解，否則轉(zhuǎn)至步驟2。

3.4 收斂性分析

假設(shè)人工蜂群中蜂群個(gè)體的更新概率為P，由改進(jìn)人工蜂群算法中蜂群個(gè)體的逆向算子操作和交叉算子操作概率（0 ＜Pr，Pc＜ 1）,可知P∈(0,1)，因此，蜂群個(gè)體的每一步更新概率都小于1，且更新過(guò)程中構(gòu)成 Markov 鏈，即任意解間依概率可達(dá)，并對(duì)其它蜂群個(gè)體的更新不產(chǎn)生影響（獨(dú)立同分布）。同時(shí)，蜂群的種群序列是單調(diào)的。由上述理論分析及依概率收斂定理可知，該算法滿(mǎn)足依概率1 收斂到全局最優(yōu)解的充要條件。

4 仿真實(shí)驗(yàn)

仿真實(shí)驗(yàn)平臺(tái)為Inter Core i5-7300HQ CPU,8GB,64 位Win10 操作系統(tǒng)惠普筆記本。編程工具為Matlab R2017b（64 位）。

4.1 參數(shù)設(shè)置

假設(shè)某基地機(jī)場(chǎng)有3 架無(wú)人機(jī)，現(xiàn)有30 個(gè)待救援的火點(diǎn)目標(biāo)，每架無(wú)人機(jī)的最大載彈量為6，無(wú)人機(jī)參數(shù)如表1，目標(biāo)位置參數(shù)如表2，目標(biāo)的價(jià)值及衰減參數(shù)情況如表3。為直觀反映任務(wù)規(guī)劃效果，在仿真實(shí)驗(yàn)中將無(wú)人機(jī)基地到每個(gè)火點(diǎn)目標(biāo)和任意兩個(gè)火點(diǎn)目標(biāo)之間的直線路徑作為可飛路徑，距離作為路徑代價(jià)。

由表1、2、3 可得出目標(biāo)和無(wú)人機(jī)位置參數(shù)如圖8所示，其中初始價(jià)值大于0.5 的為重要目標(biāo)，其余為一般目標(biāo)。

表1 無(wú)人機(jī)參數(shù)Tab.1 UAV parameters

表2 目標(biāo)位置參數(shù)Tab.2 Target position parameters

表3 目標(biāo)的價(jià)值及衰減參數(shù)Tab.3 Target value and attenuation parameters

圖8 無(wú)人機(jī)和目標(biāo)位置Fig.8 UAVs and target location

4.2 實(shí)驗(yàn)結(jié)果及分析

實(shí)驗(yàn)一：在目標(biāo)價(jià)值不存在時(shí)變的情況下，對(duì)提出的改進(jìn)ABC 算法有效性進(jìn)行驗(yàn)證。

如表2所示，重要目標(biāo)有15 個(gè)，每架無(wú)人機(jī)的載彈量為6 發(fā)，需要3 架無(wú)人機(jī)完成任務(wù)。用改進(jìn)ABC算法和文獻(xiàn)[11]提出的多種群遺傳算法（MPHGA）進(jìn)行對(duì)比實(shí)驗(yàn)。實(shí)驗(yàn)次數(shù)為100 次，種群規(guī)模為100，最大迭代次數(shù)為100，改進(jìn)ABC 算法中蜜源最大搜索次數(shù)limit為10，逆向概率Pc和交叉概率Pr均為0.85；MPHGA 算法中子種群數(shù)為4。仿真結(jié)果如圖9、圖10、圖11 所示，代價(jià)結(jié)果如表4所示。

圖9 改進(jìn)ABC 算法救援路徑Fig.9 Rescue path of improved ABC algorithm

圖10 MPHGA 算法救援路徑Fig.10 Rescue path of MPHGA algorithm

圖11 兩種算法對(duì)比Fig.11 Comparison of two algorithms

表4 兩種算法對(duì)比Tab.4 Comparison of two algorithms

結(jié)果分析如下：

（1）由圖9，圖10 可得，兩種算法均能有效完成對(duì)所有重要目標(biāo)的救援，驗(yàn)證了所提算法的可行性。

（2）由表4兩種算法對(duì)比可得，在目標(biāo)價(jià)值不存在時(shí)間衰減的情況下，所有被救援目標(biāo)的總價(jià)值不變，主要影響因素為完成所有救援任務(wù)的時(shí)間代價(jià)，其中100 次仿真中MPHGA 算法的3 架無(wú)人機(jī)對(duì)15 個(gè)重點(diǎn)目標(biāo)有效救援的總滯空時(shí)間平均為43 min，改進(jìn)ABC算法則為42 min，滯空時(shí)間即完成任務(wù)時(shí)間降低了2.3%，說(shuō)明改進(jìn)ABC 算法的尋優(yōu)能力優(yōu)于MPHGA算法。

（3）由圖11 兩種算法有限次迭代的收斂狀況對(duì)比可得，改進(jìn)ABC 算法平均在迭代12 次就達(dá)到了全局最優(yōu)解；而MPHGA 算法在迭代79 次后最終陷入局部最優(yōu)，得出次優(yōu)解。改進(jìn)算法的尋優(yōu)時(shí)間僅為MPHGA 算法的15.2%，說(shuō)明改進(jìn)ABC 算法的尋優(yōu)效率優(yōu)于MPHGA 算法。

實(shí)驗(yàn)二：在考慮目標(biāo)價(jià)值時(shí)變的情況下，通過(guò)調(diào)整權(quán)重系數(shù)來(lái)反映決策者意圖，從而來(lái)驗(yàn)證所提算法的普適性。

當(dāng)無(wú)人機(jī)數(shù)量不能滿(mǎn)足救援所有目標(biāo)的情況時(shí)，決策者就必須有取舍的去選擇救援一些更有價(jià)值的目標(biāo)。因此，針對(duì)決策者對(duì)目標(biāo)價(jià)值和滯空時(shí)間的權(quán)重要求，分別對(duì)權(quán)重系數(shù)分配不同時(shí)無(wú)人機(jī)救援任務(wù)規(guī)劃情況進(jìn)行仿真，能夠更加體現(xiàn)算法在應(yīng)對(duì)各種情況時(shí)的適用性，同時(shí)通過(guò)對(duì)比其仿真結(jié)果，也能夠?yàn)闆Q策者提供最佳決策。

圖12 p = 1,q = 0 時(shí)改進(jìn)ABC 算法救援路徑Fig.12 p = 1,q = 0 improved ABC algorithm rescue path

圖13 p = 1,q = 0 時(shí)MPHGA 算法救援路徑Fig.13 p = 1,q = 0 MPHGA algorithm rescue path

假設(shè)無(wú)人機(jī)的數(shù)量為3，改進(jìn)ABC 算法中種群規(guī)模為100，最大迭代次數(shù)為200，蜜源最大搜索次數(shù)limit為10，逆向概率Pc和交叉概率Pr均為0.85，MPHGA 算法中子種群數(shù)為4。在權(quán)重系數(shù)為p= 1,q= 0；p=q= 0.5；p= 0,q= 1 時(shí)兩種算法的仿真結(jié)果如圖12、圖13、圖14、圖15、圖16、圖17 及表5。

圖14 p = q = 0.5 時(shí)改進(jìn)ABC 算法救援路徑Fig.14 p = q = 0.5 improved ABC algorithm rescue path

圖15 p = q = 0.5 時(shí)MPHGA 算法救援路徑Fig.15 p = q = 0.5 MPHGA algorithm rescue path

圖16 p = 0,q = 1 時(shí)改進(jìn)ABC 算法救援路徑Fig.16 p = 0,q = 1 improved ABC algorithm rescue path

圖17 p = 0,q = 1 時(shí)MPHGA 算法救援路徑Fig.17 p = 0,q = 1 MPHGA algorithm rescue path

表5 三種不同權(quán)重情況對(duì)比Tab.5 Comparison of three different weights

結(jié)果分析如下：

（1）分析圖12 及表5在p= 1，q= 0 時(shí)可以得出，決策者在不考慮滯空時(shí)間代價(jià)，只關(guān)注目標(biāo)價(jià)值的情況下，無(wú)人機(jī)救援序列中沒(méi)有重點(diǎn)目標(biāo)T8，因?yàn)槠涑跏純r(jià)值參數(shù)為0.6 較小，衰減參數(shù)為較大的0.9，并且離基地的距離較遠(yuǎn)，其價(jià)值衰減嚴(yán)重，當(dāng)無(wú)人機(jī)數(shù)量不足時(shí)，相對(duì)于其他重要目標(biāo)救援的價(jià)值較小，進(jìn)一步驗(yàn)證了目標(biāo)價(jià)值隨時(shí)間變化是決策者在進(jìn)行任務(wù)規(guī)劃時(shí)必須要考慮的因素，圖14、圖15 中較遠(yuǎn)的重要目標(biāo)沒(méi)有被救援也間接說(shuō)明了所提因素。

（2）分析圖16、圖17 及表5在p= 0，q= 1 時(shí)可以得出，決策者在不考慮目標(biāo)價(jià)值大小，只關(guān)注滯空時(shí)間的情況下，算法按照無(wú)人機(jī)最大載彈就近救援任務(wù)目標(biāo)，滯空時(shí)間最短，符合決策者意圖，驗(yàn)證了算法的有效性。

（3）對(duì)比圖12、圖14、圖16 及圖13、圖15、圖17 和表5可得出，因目標(biāo)函數(shù)中目標(biāo)價(jià)值收益取負(fù)相關(guān)（即“-p”），則當(dāng)目標(biāo)價(jià)值收益權(quán)重系數(shù)p變小，而滯空時(shí)間權(quán)重系數(shù)q變大時(shí)，無(wú)人機(jī)對(duì)重點(diǎn)目標(biāo)的救援?dāng)?shù)量呈現(xiàn)遞減趨勢(shì)，無(wú)人機(jī)救援目標(biāo)總價(jià)值減小，又滯空時(shí)間權(quán)重系數(shù)q決定的總路徑代價(jià)在減小，使得無(wú)人機(jī)的飛行安全價(jià)值增加。說(shuō)明兩種算法都可以有效根據(jù)決策者的意圖通過(guò)調(diào)整權(quán)重系數(shù)對(duì)救援任務(wù)進(jìn)行規(guī)劃。

（4）分別對(duì)比圖12 和圖13、圖16 和圖17、圖14 和圖15 以及表5中兩種算法在權(quán)重系數(shù)相同情況下的相關(guān)數(shù)據(jù)可得，在只關(guān)注目標(biāo)價(jià)值時(shí)所提算法目標(biāo)總價(jià)值高于現(xiàn)有算法1.4%；只關(guān)注滯空時(shí)間時(shí)所提算法的滯空時(shí)間短于現(xiàn)有算法4.9%；當(dāng)滯空時(shí)間和目標(biāo)價(jià)值的權(quán)重系數(shù)都為0.5 時(shí)所提算法的滯空時(shí)間短于現(xiàn)有算法6.5%，同時(shí)目標(biāo)總價(jià)值高于現(xiàn)有算法3.2%。說(shuō)明所提改進(jìn)ABC 算法的尋優(yōu)能力高于現(xiàn)有的MPHGA 算法。

5 結(jié) 論

針對(duì)當(dāng)前多無(wú)人機(jī)對(duì)多火點(diǎn)火場(chǎng)滅火救援任務(wù)規(guī)劃中，因目標(biāo)價(jià)值時(shí)變而導(dǎo)致任務(wù)規(guī)劃效率低下的問(wèn)題，提出了一種基于改進(jìn)ABC 的任務(wù)規(guī)劃算法，并通過(guò)仿真實(shí)驗(yàn)驗(yàn)證了算法的有效性，主要得到以下結(jié)論：

（1）在考慮到目標(biāo)價(jià)值時(shí)變性的基礎(chǔ)上，提出了一種目標(biāo)價(jià)值隨時(shí)間變化的多無(wú)人機(jī)對(duì)多火點(diǎn)火場(chǎng)滅火救援任務(wù)規(guī)劃模型，該模型相對(duì)于現(xiàn)有模型具有更強(qiáng)的普適性。

（2）在目標(biāo)價(jià)值非時(shí)變，且救援資源滿(mǎn)足任務(wù)要求的條件下，改進(jìn)ABC 算法可以有效解決多無(wú)人機(jī)對(duì)多火點(diǎn)火場(chǎng)滅火救援問(wèn)題，其尋優(yōu)效率和尋優(yōu)能力均優(yōu)于現(xiàn)有的MPHGA 算法；

（3）當(dāng)目標(biāo)價(jià)值時(shí)變且救援資源不足時(shí)，在使用相同權(quán)重系數(shù)決策模型的條件下，改進(jìn)ABC 算法與現(xiàn)有算法進(jìn)行對(duì)比，目標(biāo)總價(jià)值相對(duì)提高，滯空時(shí)間相對(duì)減少，驗(yàn)證了所建模型的普適性以及所提算法的高效性。