基于改進布谷鳥算法的多無人機任務分配

紀良杰，趙曉林，魏兆恬，藺文軒

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

1 引言

隨著無人機的快速發展，因其具有低成本、低操作員傷亡等優勢，被應用于物流、農業、搜救、軍事等多個領域，尤其在軍事領域應用更為廣泛。為了能夠在復雜的戰場環境下更高效的完成任務，操作員需要在開展無人機行動之前進行任務分配。

本文中主要對多無人機任務進行分配，在滿足無人機性能約束及戰場信息的前提下完成對敵方目標的偵察任務，盡可能的取得最大的任務總收益。為貼合戰場實際，本文中使用隨任務執行序列變化的威脅概率和目標收益代替固定威脅概率和目標收益讓任務模型更加真實。

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

針對布谷鳥算法在搜索尋優過程中存在求解速度慢、容易陷入局部最優等不足，本文中引入高斯遞減的自適應步長因子加快算法搜索速度，改善算法求解速度慢的問題，同時引入模擬退火機制，增加算法全局搜索能力，避免陷入局部最優解。

2 多無人機任務分配問題

2.1 問題描述

我方通過情報獲取到敵方區域的個重要目標的位置信息、目標價值以及目標威脅等基本信息，為進一步掌握敵方目標的詳細信息，我方需要派出無人機對該區域中重要目標進行偵察，我方有架偵察無人機，無人機均從基地起飛，有序完成對目標的偵察任務使得完成任務效益最大化。

該問題可描述為：無人機集合為={,,,…,}，無人機位置集合為={1,2,…,}，偵察目標集合為={,,,…,}，偵察目標位置集合為={1,2,…,}，無人機的價值={1,2,3,…,}，無人機完成偵察任務的概率為={,,,…,}，無人機任務載荷上限={,,,…,}，目標的價值={1,2,3,…,}，目標的威脅系數={,,,…,},目標的威脅范圍的半徑為={,,,…,}。

2.2 目標函數

為使多無人機執行偵察任務效益最大化，本文中需要綜合考慮威脅代價、航程代價和任務目標收益三者得到最大總收益。

(1)

航程代價考慮到無人機與目標的距離遠大于無人機的最小轉彎半徑，因此采用直線度量。

(2)

式中:指無人機執行偵察任務的最遠距離，指無人機到目標的距離。

(3)

總收益適應度函數：

(4)

(5)

2.3 約束條件

(6)

(7)

式(6)表示為所有任務目標都完成；式(7)表示為每一架無人機執行的任務數目不得超過無人機本身的任務載荷數目約束。

3 改進布谷鳥算法

3.1 經典布谷鳥搜索算法

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

布谷鳥既不會做巢也不會育雛，它在產卵前會在其他鳥類(宿主鳥)離開鳥巢時，把宿主鳥的卵推出宿主鳥巢，將自己的蛋產在宿主的鳥巢里，讓宿主鳥喂養布谷鳥幼崽。而靠宿主鳥養大的幼年布谷鳥，也存在將宿主鳥幼鳥推出鳥巢的習慣，并且會模仿行為來降低被宿主鳥發現的概率。

假設布谷鳥搜索算法滿足下列3項理想化的條件：

① 布谷鳥每次隨機性的選擇合適的鳥巢產下一枚卵；

② 在隨機選擇的一組鳥窩中，最好的鳥窩將會被保留到下一代；

③ 能使用的鳥窩數目是固定的，鳥窩的主人能發現外來鳥蛋的概率，也稱為∈[0,1]；

算法位置更新公式如下：

(8)

()～=-, 1<≤3

(9)

采用下列公式生成隨機數：

(10)

更新鳥巢位置后，計算后比較鳥巢的適應度值，選擇適應度更優的解。之后按照概率拋棄一部分差解后采用偏好隨機游走生成同等數量的新解。

(11)

3.2 布谷鳥算法的改進

經典布谷鳥算法在運算中收斂速度較慢，影響運算速度，而且在運算中容易陷入局部最優從而影響求解結果的精度。

321 自適應步長因子

在標準布谷鳥算法中，步長控制因子是固定值，如果選取的步長控制因子較大，算法搜索速度變快，但是相應的求解精度降低；如果步長控制因子較小，算法精度變高但是搜索速度變慢。所以本文中在算法搜索的時候采用自適應步長調節的方法，在運算前期解的質量不好的時候，采用較大的步長控制因子進行快速搜索，提高搜索速度；在算法搜索后期，算法求得的解比較接近最優解，采用較小的步長控制因子進行精確搜索，提高搜索精度。為增加算法運算時的動態調節能力，這里引入一個自適應步長控制因子，隨著算法搜索過程的適應度值自動調整步長的大小，從而更快速的獲得更精確的優解。

(12)

3.2.2 模擬退火機制

模擬退火算法(simulated annealing，SA)是根據固體降溫現象提出的一種優化算法，先加熱固體讓它的溫度達到較高水平，加熱期間固體粒子隨著溫度升高而逐漸混亂，能量逐漸變大。再讓它緩慢降溫，因為溫度下降的足夠緩慢，整個降溫過程一直維持在平衡態，在降至室溫后，能量達到最小。SA先選擇一個隨機的初始高溫開始，隨著溫度參數下降，算法不斷搜索從而得到全局最優解。因為模擬退火機制具有使用靈活、運行效率高且受初始條件限制較小的原因，在布谷鳥算法中引入模擬退火機制，來加強算法的全局尋優能力，防止陷入局部最優。

(13)

=-1

(14)

3.2.3 編碼方式

實驗采用實數編碼如表1所示，實數的整數部分表示與任務對應的無人機編號,整數部分相同的目標任務分配在同一架無人機的任務序列中；實數的小數部分表示執行任務目標中序列的優先程度。編碼與無人機任務序列的關系如表2所示。

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

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

3.2.4 算法流程

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

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

1) 設置算法的溫度、種群數、發現概率、衰退因子、種群最大迭代次數等參數；

2) 初始化鳥巢并計算各個鳥巢的適應度值，留下適應度值最小的鳥巢；

3) 用改進后的Levy飛行更新鳥窩位置，計算當代鳥窩的適應度值并與前一代對比，保留當前最優的鳥窩；

5) 保留當前最優解，判斷是否滿足最大迭代次數的條件，如果達到最大迭代次數則輸出最優解；否則返回到第3步繼續計算。

4 仿真實驗

4.1 仿真實驗參數設置

假設現有3架偵察無人機對9個目標進行偵察任務，無人機參數和目標參數分別如表3、表4所示。

表3 無人機參數Table 3 UAVs parameters

表4 目標參數Table 4 Target parameters

為了不影響多無人機任務分配結果，這里引入熵權法，對威脅代價函數、航程代價函數和任務目標收益函數中的信息量進行對比，經過多次實驗取適應度函數中=03，=04，=03。改進布谷鳥算法、布谷鳥算法、蟻群算法和蜂群算法的仿真結果如圖2所示。

圖2 算法適應度曲線Fig.2 Comparison curve of algorithm fitness

改進布谷鳥算法、布谷鳥算法、蟻群算法和蜂群算法的仿真結果分配表如表5—表8所示。

表5 改進布谷鳥算法的任務分配表Table 5 Task allocation table of improved cuckoo algorithm

表6 布谷鳥算法的任務分配表Table 6 Task allocation table of cuckoo algorithm

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

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

改進布谷鳥算法、布谷鳥算法、蟻群算法和蜂群算法的仿真結果示意圖如圖3—圖6。

圖3 改進布谷鳥算法的任務分配示意圖Fig.3 Task allocation schematic diagram of improved cuckoo algorithm

圖4 布谷鳥算法的任務分配示意圖Fig.4 Task allocation schematic diagram of cuckoo algorithm

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

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

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

根據表9可知，經過多次的仿真實驗結果顯示改進布谷鳥算法比布谷鳥算法的求解精度提高了16.41%、速度提高了15.01%；和蟻群算法相比精度提高了39.66%、速度提高了30.55%；和蜂群算法相比精度提高了32.54%、速度提高了13.32%。

表9 算法結果Table 9 Comparison table of algorithm results

由此可知改進布谷鳥算法與其他3種算法相比擁有更好的全局尋優能力和更快的收斂速度，改進布谷鳥算法能放棄局部最優解，搜索全局最優解，使得搜索出來的解更符合多無人機任務分配的要求。

5 結論

改進布谷鳥算法應用于多無人機任務分配問題，比原布谷鳥算法、蟻群算法和蜂群算法具有更快的收斂速度；在任務分配過程中也不易陷入局部最優。