基于改進(jìn)布谷鳥(niǎo)算法的多無(wú)人機(jī)任務(wù)分配

紀(jì)良杰，趙曉林，魏兆恬，藺文軒

(1.空軍工程大學(xué) 研究生院， 西安 710043； 2.空軍工程大學(xué) 裝備管理與無(wú)人機(jī)工程學(xué)院， 西安 710043)

1 引言

隨著無(wú)人機(jī)的快速發(fā)展，因其具有低成本、低操作員傷亡等優(yōu)勢(shì)，被應(yīng)用于物流、農(nóng)業(yè)、搜救、軍事等多個(gè)領(lǐng)域，尤其在軍事領(lǐng)域應(yīng)用更為廣泛。為了能夠在復(fù)雜的戰(zhàn)場(chǎng)環(huán)境下更高效的完成任務(wù)，操作員需要在開(kāi)展無(wú)人機(jī)行動(dòng)之前進(jìn)行任務(wù)分配。

本文中主要對(duì)多無(wú)人機(jī)任務(wù)進(jìn)行分配，在滿足無(wú)人機(jī)性能約束及戰(zhàn)場(chǎng)信息的前提下完成對(duì)敵方目標(biāo)的偵察任務(wù)，盡可能的取得最大的任務(wù)總收益。為貼合戰(zhàn)場(chǎng)實(shí)際，本文中使用隨任務(wù)執(zhí)行序列變化的威脅概率和目標(biāo)收益代替固定威脅概率和目標(biāo)收益讓任務(wù)模型更加真實(shí)。

目前，眾多學(xué)者就任務(wù)分配問(wèn)題已經(jīng)取得了大量的研究成果。文獻(xiàn)[1]使用蟻群算法對(duì)任務(wù)鏈進(jìn)行子集劃分，提高了解決醫(yī)療資源分配問(wèn)題的效率。文獻(xiàn)[2]在蜂群算法的基礎(chǔ)上加入逆向、交叉和變異算子，讓其更適合求解火場(chǎng)救援問(wèn)題。文獻(xiàn)[3]通過(guò)在粒子群算法中引入死鎖檢查和修復(fù)機(jī)制，良好的解決了任務(wù)分配中的“死鎖”現(xiàn)象。文獻(xiàn)[4]細(xì)化了遺傳算法中交叉變異概率的公式，解決了倉(cāng)儲(chǔ)系統(tǒng)的調(diào)度問(wèn)題。文獻(xiàn)[5]在細(xì)菌覓食算法中加入動(dòng)態(tài)自適應(yīng)調(diào)節(jié)游動(dòng)參數(shù)，提高了算法的收斂能力；文獻(xiàn)[6]對(duì)傳統(tǒng)的合同網(wǎng)算法進(jìn)行流程優(yōu)化，提升了算法的分配效率。布谷鳥(niǎo)算法作為一種引入了生物進(jìn)化論的群智能算法的新型元啟發(fā)式搜索算法，因其具有參數(shù)少、魯棒性強(qiáng)、通用性好等優(yōu)點(diǎn)被廣泛用于優(yōu)化模型的求解。文獻(xiàn)[7]提出一種結(jié)合單純形的布谷鳥(niǎo)算法增加了解的精度，并在其中融合了粒子群思想增加了局部尋優(yōu)能力，但過(guò)于追求精度使得求解過(guò)程消耗了大量時(shí)間；文獻(xiàn)[8]通過(guò)交替及變異的操作改良了布谷鳥(niǎo)算法的早熟問(wèn)題，但是交替變異操作讓算法的隨機(jī)性增大，導(dǎo)致算法收斂速度下降；文獻(xiàn)[9]提出自適應(yīng)選取交叉操作算子的布谷鳥(niǎo)搜索算法，優(yōu)化了算法的尋優(yōu)精度，但步長(zhǎng)自適應(yīng)因子在前期搜索中啟動(dòng)速度緩慢；文獻(xiàn)[10]通過(guò)對(duì)鳥(niǎo)巢位置進(jìn)行正態(tài)隨機(jī)分布擾動(dòng)，提高了種群的多樣性，正態(tài)擾動(dòng)半徑參數(shù)對(duì)尋優(yōu)搜索結(jié)果起到了重要作用，但選取合適的參數(shù)較為困難。

針對(duì)布谷鳥(niǎo)算法在搜索尋優(yōu)過(guò)程中存在求解速度慢、容易陷入局部最優(yōu)等不足，本文中引入高斯遞減的自適應(yīng)步長(zhǎng)因子加快算法搜索速度，改善算法求解速度慢的問(wèn)題，同時(shí)引入模擬退火機(jī)制，增加算法全局搜索能力，避免陷入局部最優(yōu)解。

2 多無(wú)人機(jī)任務(wù)分配問(wèn)題

2.1 問(wèn)題描述

我方通過(guò)情報(bào)獲取到敵方區(qū)域的個(gè)重要目標(biāo)的位置信息、目標(biāo)價(jià)值以及目標(biāo)威脅等基本信息，為進(jìn)一步掌握敵方目標(biāo)的詳細(xì)信息，我方需要派出無(wú)人機(jī)對(duì)該區(qū)域中重要目標(biāo)進(jìn)行偵察，我方有架偵察無(wú)人機(jī)，無(wú)人機(jī)均從基地起飛，有序完成對(duì)目標(biāo)的偵察任務(wù)使得完成任務(wù)效益最大化。

該問(wèn)題可描述為：無(wú)人機(jī)集合為={,,,…,}，無(wú)人機(jī)位置集合為={1,2,…,}，偵察目標(biāo)集合為={,,,…,}，偵察目標(biāo)位置集合為={1,2,…,}，無(wú)人機(jī)的價(jià)值={1,2,3,…,}，無(wú)人機(jī)完成偵察任務(wù)的概率為={,,,…,}，無(wú)人機(jī)任務(wù)載荷上限={,,,…,}，目標(biāo)的價(jià)值={1,2,3,…,}，目標(biāo)的威脅系數(shù)={,,,…,},目標(biāo)的威脅范圍的半徑為={,,,…,}。

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

為使多無(wú)人機(jī)執(zhí)行偵察任務(wù)效益最大化，本文中需要綜合考慮威脅代價(jià)、航程代價(jià)和任務(wù)目標(biāo)收益三者得到最大總收益。

(1)

航程代價(jià)考慮到無(wú)人機(jī)與目標(biāo)的距離遠(yuǎn)大于無(wú)人機(jī)的最小轉(zhuǎn)彎半徑，因此采用直線度量。

(2)

式中:指無(wú)人機(jī)執(zhí)行偵察任務(wù)的最遠(yuǎn)距離，指無(wú)人機(jī)到目標(biāo)的距離。

(3)

總收益適應(yīng)度函數(shù)：

(4)

(5)

2.3 約束條件

(6)

(7)

式(6)表示為所有任務(wù)目標(biāo)都完成；式(7)表示為每一架無(wú)人機(jī)執(zhí)行的任務(wù)數(shù)目不得超過(guò)無(wú)人機(jī)本身的任務(wù)載荷數(shù)目約束。

3 改進(jìn)布谷鳥(niǎo)算法

3.1 經(jīng)典布谷鳥(niǎo)搜索算法

布谷鳥(niǎo)算法(cuckoo search，CS)是借鑒布谷鳥(niǎo)尋找鳥(niǎo)窩位置找產(chǎn)卵的行為而提出的一種優(yōu)化算法。

布谷鳥(niǎo)既不會(huì)做巢也不會(huì)育雛，它在產(chǎn)卵前會(huì)在其他鳥(niǎo)類(lèi)(宿主鳥(niǎo))離開(kāi)鳥(niǎo)巢時(shí)，把宿主鳥(niǎo)的卵推出宿主鳥(niǎo)巢，將自己的蛋產(chǎn)在宿主的鳥(niǎo)巢里，讓宿主鳥(niǎo)喂養(yǎng)布谷鳥(niǎo)幼崽。而靠宿主鳥(niǎo)養(yǎng)大的幼年布谷鳥(niǎo)，也存在將宿主鳥(niǎo)幼鳥(niǎo)推出鳥(niǎo)巢的習(xí)慣，并且會(huì)模仿行為來(lái)降低被宿主鳥(niǎo)發(fā)現(xiàn)的概率。

假設(shè)布谷鳥(niǎo)搜索算法滿足下列3項(xiàng)理想化的條件：

① 布谷鳥(niǎo)每次隨機(jī)性的選擇合適的鳥(niǎo)巢產(chǎn)下一枚卵；

② 在隨機(jī)選擇的一組鳥(niǎo)窩中，最好的鳥(niǎo)窩將會(huì)被保留到下一代；

③ 能使用的鳥(niǎo)窩數(shù)目是固定的，鳥(niǎo)窩的主人能發(fā)現(xiàn)外來(lái)鳥(niǎo)蛋的概率，也稱(chēng)為∈[0,1]；

算法位置更新公式如下：

(8)

()～=-, 1<≤3

(9)

采用下列公式生成隨機(jī)數(shù)：

(10)

更新鳥(niǎo)巢位置后，計(jì)算后比較鳥(niǎo)巢的適應(yīng)度值，選擇適應(yīng)度更優(yōu)的解。之后按照概率拋棄一部分差解后采用偏好隨機(jī)游走生成同等數(shù)量的新解。

(11)

3.2 布谷鳥(niǎo)算法的改進(jìn)

經(jīng)典布谷鳥(niǎo)算法在運(yùn)算中收斂速度較慢，影響運(yùn)算速度，而且在運(yùn)算中容易陷入局部最優(yōu)從而影響求解結(jié)果的精度。

321 自適應(yīng)步長(zhǎng)因子

在標(biāo)準(zhǔn)布谷鳥(niǎo)算法中，步長(zhǎng)控制因子是固定值，如果選取的步長(zhǎng)控制因子較大，算法搜索速度變快，但是相應(yīng)的求解精度降低；如果步長(zhǎng)控制因子較小，算法精度變高但是搜索速度變慢。所以本文中在算法搜索的時(shí)候采用自適應(yīng)步長(zhǎng)調(diào)節(jié)的方法，在運(yùn)算前期解的質(zhì)量不好的時(shí)候，采用較大的步長(zhǎng)控制因子進(jìn)行快速搜索，提高搜索速度；在算法搜索后期，算法求得的解比較接近最優(yōu)解，采用較小的步長(zhǎng)控制因子進(jìn)行精確搜索，提高搜索精度。為增加算法運(yùn)算時(shí)的動(dòng)態(tài)調(diào)節(jié)能力，這里引入一個(gè)自適應(yīng)步長(zhǎng)控制因子，隨著算法搜索過(guò)程的適應(yīng)度值自動(dòng)調(diào)整步長(zhǎng)的大小，從而更快速的獲得更精確的優(yōu)解。

(12)

3.2.2 模擬退火機(jī)制

模擬退火算法(simulated annealing，SA)是根據(jù)固體降溫現(xiàn)象提出的一種優(yōu)化算法，先加熱固體讓它的溫度達(dá)到較高水平，加熱期間固體粒子隨著溫度升高而逐漸混亂，能量逐漸變大。再讓它緩慢降溫，因?yàn)闇囟认陆档淖銐蚓徛?，整個(gè)降溫過(guò)程一直維持在平衡態(tài)，在降至室溫后，能量達(dá)到最小。SA先選擇一個(gè)隨機(jī)的初始高溫開(kāi)始，隨著溫度參數(shù)下降，算法不斷搜索從而得到全局最優(yōu)解。因?yàn)槟M退火機(jī)制具有使用靈活、運(yùn)行效率高且受初始條件限制較小的原因，在布谷鳥(niǎo)算法中引入模擬退火機(jī)制，來(lái)加強(qiáng)算法的全局尋優(yōu)能力，防止陷入局部最優(yōu)。

(13)

=-1

(14)

3.2.3 編碼方式

實(shí)驗(yàn)采用實(shí)數(shù)編碼如表1所示，實(shí)數(shù)的整數(shù)部分表示與任務(wù)對(duì)應(yīng)的無(wú)人機(jī)編號(hào),整數(shù)部分相同的目標(biāo)任務(wù)分配在同一架無(wú)人機(jī)的任務(wù)序列中；實(shí)數(shù)的小數(shù)部分表示執(zhí)行任務(wù)目標(biāo)中序列的優(yōu)先程度。編碼與無(wú)人機(jī)任務(wù)序列的關(guān)系如表2所示。

表1 編碼示意表Table 1 Code schematic table

表2 解碼示意表Table 2 Decoding schematic table

3.2.4 算法流程

算法流程如圖1所示，具體步驟為：

圖1 算法流程框圖Fig.1 Algorithm flow chart

1) 設(shè)置算法的溫度、種群數(shù)、發(fā)現(xiàn)概率、衰退因子、種群最大迭代次數(shù)等參數(shù)；

2) 初始化鳥(niǎo)巢并計(jì)算各個(gè)鳥(niǎo)巢的適應(yīng)度值，留下適應(yīng)度值最小的鳥(niǎo)巢；

3) 用改進(jìn)后的Levy飛行更新鳥(niǎo)窩位置，計(jì)算當(dāng)代鳥(niǎo)窩的適應(yīng)度值并與前一代對(duì)比，保留當(dāng)前最優(yōu)的鳥(niǎo)窩；

5) 保留當(dāng)前最優(yōu)解，判斷是否滿足最大迭代次數(shù)的條件，如果達(dá)到最大迭代次數(shù)則輸出最優(yōu)解；否則返回到第3步繼續(xù)計(jì)算。

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

4.1 仿真實(shí)驗(yàn)參數(shù)設(shè)置

假設(shè)現(xiàn)有3架偵察無(wú)人機(jī)對(duì)9個(gè)目標(biāo)進(jìn)行偵察任務(wù)，無(wú)人機(jī)參數(shù)和目標(biāo)參數(shù)分別如表3、表4所示。

表3 無(wú)人機(jī)參數(shù)Table 3 UAVs parameters

表4 目標(biāo)參數(shù)Table 4 Target parameters

為了不影響多無(wú)人機(jī)任務(wù)分配結(jié)果，這里引入熵權(quán)法，對(duì)威脅代價(jià)函數(shù)、航程代價(jià)函數(shù)和任務(wù)目標(biāo)收益函數(shù)中的信息量進(jìn)行對(duì)比，經(jīng)過(guò)多次實(shí)驗(yàn)取適應(yīng)度函數(shù)中=03，=04，=03。改進(jìn)布谷鳥(niǎo)算法、布谷鳥(niǎo)算法、蟻群算法和蜂群算法的仿真結(jié)果如圖2所示。

圖2 算法適應(yīng)度曲線Fig.2 Comparison curve of algorithm fitness

改進(jìn)布谷鳥(niǎo)算法、布谷鳥(niǎo)算法、蟻群算法和蜂群算法的仿真結(jié)果分配表如表5—表8所示。

表5 改進(jìn)布谷鳥(niǎo)算法的任務(wù)分配表Table 5 Task allocation table of improved cuckoo algorithm

表6 布谷鳥(niǎo)算法的任務(wù)分配表Table 6 Task allocation table of cuckoo algorithm

表7 蟻群算法的任務(wù)分配表Table 7 Task assignment table of ant colony algorithm

表8 蜂群算法的任務(wù)分配表Table 8 Task allocation table of bee colony algorithm

改進(jìn)布谷鳥(niǎo)算法、布谷鳥(niǎo)算法、蟻群算法和蜂群算法的仿真結(jié)果示意圖如圖3—圖6。

圖3 改進(jìn)布谷鳥(niǎo)算法的任務(wù)分配示意圖Fig.3 Task allocation schematic diagram of improved cuckoo algorithm

圖4 布谷鳥(niǎo)算法的任務(wù)分配示意圖Fig.4 Task allocation schematic diagram of cuckoo algorithm

圖5 蟻群算法的任務(wù)分配示意圖Fig.5 Task allocation schematic diagram of ant colony algorithm

圖6 蜂群算法的任務(wù)分配示意圖Fig.6 Task allocation schematic diagram of bee colony algorithm

由圖3可知，改進(jìn)布谷鳥(niǎo)算法在算法迭代前期快速搜索，在算法迭代后期，算法搜索速度變慢。在改進(jìn)布谷鳥(niǎo)算法迭代到第18次的時(shí)候，其適應(yīng)度值就低于其余3種算法，此時(shí)改進(jìn)布谷鳥(niǎo)算法的適應(yīng)度值為0.224 16，當(dāng)算法迭代到32次時(shí)，改進(jìn)后的布谷鳥(niǎo)算法收斂，此時(shí)的適應(yīng)度值為0.170 90。布谷鳥(niǎo)算法在迭代了111代收斂，適應(yīng)度值為0.204 89。蟻群算法在迭代了75代收斂，適應(yīng)度值為0.297 00。蜂群算法在迭代了106代收斂，適應(yīng)度值為0.248 00。

根據(jù)表9可知，經(jīng)過(guò)多次的仿真實(shí)驗(yàn)結(jié)果顯示改進(jìn)布谷鳥(niǎo)算法比布谷鳥(niǎo)算法的求解精度提高了16.41%、速度提高了15.01%；和蟻群算法相比精度提高了39.66%、速度提高了30.55%；和蜂群算法相比精度提高了32.54%、速度提高了13.32%。

表9 算法結(jié)果Table 9 Comparison table of algorithm results

由此可知改進(jìn)布谷鳥(niǎo)算法與其他3種算法相比擁有更好的全局尋優(yōu)能力和更快的收斂速度，改進(jìn)布谷鳥(niǎo)算法能放棄局部最優(yōu)解，搜索全局最優(yōu)解，使得搜索出來(lái)的解更符合多無(wú)人機(jī)任務(wù)分配的要求。

5 結(jié)論

改進(jìn)布谷鳥(niǎo)算法應(yīng)用于多無(wú)人機(jī)任務(wù)分配問(wèn)題，比原布谷鳥(niǎo)算法、蟻群算法和蜂群算法具有更快的收斂速度；在任務(wù)分配過(guò)程中也不易陷入局部最優(yōu)。