基于博弈的差分進化和粒子群相結(jié)合的無人機任務(wù)分配

摘? 要：無人機具有成本低、靈活性高、部署方便等優(yōu)點，在軍事和民用領(lǐng)域得到了廣泛的應(yīng)用，然而，無人機的智能化水平難以應(yīng)對復(fù)雜不確定的任務(wù)環(huán)境。為了提高無人機的智能性與協(xié)同能力，文章提出基于博弈的差分進化算法（Differential Evolution， DE）和粒子群算法（Particle Swarm Optimization， PSO）相結(jié)合的無人機任務(wù)分配，采用博弈論中的聯(lián)盟博弈模型實現(xiàn)算法之間的相互協(xié)作。事實上，在每一輪迭代和特定迭代之后，DE和PSO算法進入博弈環(huán)境，基于納什議價理論共同進行博弈，以達到聯(lián)盟博弈中的納什均衡狀態(tài)。最后，通過仿真實驗驗證了所提算法的有效性。

關(guān)鍵詞：粒子群算法；差分進化算法；聯(lián)盟博弈；任務(wù)分配

中圖分類號：TP18? ? 文獻標識碼：A? 文章編號：2096-4706（2023）17-0055-06

UAV Task Allocation Based on Game Differential Evolution and

Particle Swarm Optimization

WANG Songbai

（School of Information， North China University of Technology， Beijing? 100144， China）

Abstract： UAVs have the advantages of low cost， high flexibility， and easy deployment， and have been widely used in military and civilian fields. However， the intelligence level of UAVs is difficult to cope with complex and uncertain task environment. In order to improve the intelligence and collaboration capability of UAVs， this paper proposes a UAV task allocation based on game Differential Evolution （DE） and Particle Swarm Optimization （PSO）， which uses the coalitional game model in Game theory to achieve mutual cooperation among algorithms. In fact， after each iteration and a specific iteration， the DE and PSO algorithms enter the game environment and jointly engage in the game based on Nash bargaining theory to achieve the Nash equilibrium state in alliance games. Finally， the effectiveness of the proposed algorithm is verified through simulation experiments.

Keywords： Particle Swarm Optimization; differential evolution algorithm; coalitional game; task allocation

0? 引? 言

無人機具有成本低、靈活性高、部署方便、隱蔽性好等優(yōu)點，在偵察打擊、信息收集、搜索救援等軍事和民用領(lǐng)域發(fā)揮著至關(guān)重要的作用[1，2]。根據(jù)分配主體的不同，任務(wù)分配可以分為集中式任務(wù)分配和分布式任務(wù)分配兩類，集中式任務(wù)分配由地面站作為單一分配主體，主要解決確定環(huán)境下的任務(wù)分配問題；分布式任務(wù)分配由每架無人機作為分配主體，可以用于動態(tài)不確定的環(huán)境。

目前，國內(nèi)外學者針對無人機任務(wù)分配問題進行了大量的研究工作，提出粒子群、整數(shù)規(guī)劃、拍賣、聯(lián)盟博弈等多種求解方法。2009年，Jing等人提出一種針對異構(gòu)多無人機的協(xié)同任務(wù)分配算法，該算法以微分進化算法為基礎(chǔ)，旨在解決異構(gòu)無人機協(xié)同執(zhí)行任務(wù)時的任務(wù)分配問題[3]。2017年，吳蔚楠提出了基于SEAD（Sensor， Energy， Action， Data）任務(wù)特性約束的任務(wù)分配方法，基于任務(wù)的空間位置、時間窗口、工作內(nèi)容等特性，將任務(wù)分配到不同的無人機上，從而高效完成任務(wù)[4]。2021年，Yan等人介紹一種基于改進粒子群優(yōu)化算法的多無人機海上任務(wù)分配和路徑規(guī)劃方法[5]。2022年，孫亞男等人從無人機之間負載均衡和算法的穩(wěn)定性出發(fā)，提出了具有高穩(wěn)定性和快速收斂的ISOM算法[6]。

綜上所述，無人機任務(wù)分配已經(jīng)成為無人機應(yīng)用領(lǐng)域的重要研究課題之一。在不同的時間點，研究者們利用不同的算法和方法來解決無人機任務(wù)分配問題。其中，基于聯(lián)盟博弈的算法性能優(yōu)良并具有較好的可擴展性。未來，隨著技術(shù)的不斷發(fā)展和應(yīng)用場景的日益擴大，智能體聯(lián)盟博弈中的任務(wù)分配問題將再次成為研究熱點。

1? 算法概述

1.1? PSO算法基本原理和特點

PSO算法最初應(yīng)用于計算智能領(lǐng)域，由于其具有程序簡單，設(shè)置參數(shù)少，求解速度快，能夠優(yōu)化各種函數(shù)等優(yōu)勢，被廣泛應(yīng)用于工業(yè)、醫(yī)學、農(nóng)業(yè)、軍事等領(lǐng)域[7]。

PSO算法的步驟可以描述如下：

1）初始化迭代次數(shù)t，并對群體中各個粒子的位置與速度進行初始化。

2）通過對目標函數(shù)的分析得到群體的相應(yīng)適配度fitnessi（t）。

3）求出相應(yīng)的個體最佳位置Pi（t）和全體最佳位置Pg（t）。

4）在此基礎(chǔ)上，利用個體最佳位置Pi（t）和全體最佳位置Pg（t）對各粒子的位置和速度進行更新。

5）求出此時粒子Xi（t）的適應(yīng)度值并將其與個體最優(yōu)位置pi（t）的適應(yīng)度值進行對比，若此時粒子的適應(yīng)度值更好，則有Pi（t） = Xi（t）。

6）求出此時粒子Pi（t）的適應(yīng)度值并將其與全局最優(yōu)位置Pg（t）的適應(yīng)度值進行對比，若此時粒子的適應(yīng)度值更好，則更新此時的全局最優(yōu)位置。

7）判斷是否達到結(jié)束條件，若還未達到結(jié)束條件，則返回步驟4），同時令t = t + 1；否則結(jié)束進程。

PSO算法流程圖如圖1所示。

1.2? DE算法基本原理和特點

DE算法是一種基于種群的優(yōu)化方法，它通過種群的其他成員來選擇當前種群的方向和距離。最初，DE允許使用突變操作符生成突變向量，允許使用交叉算子生成試驗向量。

對于每個主解（目標向量），由突變算子生成一個突變向量。在此過程中，基向量和加權(quán)差值在其他隨機選擇的親本之間發(fā)生突變。

用下面的關(guān)系式表示第i代元素的突變向量ui的生成：

其中，CR ∈ [0，1]表示給定常數(shù)的交叉速率，rj表示[0，1]范圍內(nèi)的均勻隨機數(shù)，jrand表示[1，D]范圍內(nèi)隨機選取的整數(shù)。

這保證了試驗向量? 可從突變向量ui中獲得至少一個元素，從而避免了進化停滯。二項式交叉和指數(shù)交叉是交叉的兩種類型。不同之處在于，在指數(shù)交叉中，選擇交叉的放在一起的元素是循環(huán)選擇的。

總之，DE算法是一種出色的全局優(yōu)化算法，具有全局尋優(yōu)能力強、適用范圍廣、參數(shù)設(shè)置簡單、并行處理能力強、魯棒性強等特點，為此得到了廣泛的應(yīng)用。

1.3? 納什議價理論基本原理和特點

在聯(lián)盟博弈中，玩家們可能不是為了共同利益或多邊利益，而是為了獲得更多的利益而在某些策略的選擇上達成一致。單個或多個玩家集合稱為聯(lián)盟，在這種情況下，只有當協(xié)議和合作的結(jié)果至少等于在游戲中獨立行動和競爭的結(jié)果時，玩家才會有動力合作并加入聯(lián)盟。

納什議價理論被認為是聯(lián)盟博弈論中最重要、最具開拓性的理論之一。當就一個問題討價還價時，雙方或多方通過談判達成協(xié)議，并采取相應(yīng)的行動。達到納什均衡的兩名參與者的納什議價理論可以很容易地推廣到n名參與者的方案之中。該理論的二人一般模式如下：

議價問題由（F，v）構(gòu)成，其中F是一組可行的分配集，v = （v1，v2）是在議價失敗的情況下決定雙方結(jié)果的分歧點。其中，可行集F包含分歧點。

納什提出的議價理論，遵循以下5個原則：

1）Pareto最優(yōu)性。對于一個固定的可行集F，賦值x = （x1，x2）是Pareto的最優(yōu)解，且沒有其他點y = （ y1，y2）中y2≥x2，y1≥x1。

2）個人理性。要求在談判解決方案中分配任何參與者的結(jié)果不應(yīng)低于它在分歧中所能實現(xiàn)的結(jié)果。

3）線性不變性。如果可行分配集的規(guī)模發(fā)生變化，則博弈解將具有相同的變換。

4）無關(guān)備選方案的獨立性。假設(shè)一個閉凸集F，該原則要求去除不被視為解的可行備選方案（除了不一致的點）不影響該解。

5）對稱性。這一原則要求，如果1號和2號在博弈問題中的狀態(tài)是完全相同的，那么議價問題的解決方案也應(yīng)該相同。

對于（F，v）的議價理論，存在唯一解函數(shù)f（0，0）滿足上述原則1）～5）。

下式展示了該解決方案適用于任何兩人談判問題（F，v）。

總之，納什議價理論是一種基于協(xié)商的博弈理論，通過討價還價的方式使得雙方都能夠得到最大化的收益。它具有理論簡單、適用范圍廣、兼顧雙方利益平衡以及可以處理多個問題等特點。

2? 基于DE和PSO算法博弈結(jié)合算法

盡管DE和PSO算法已被卓有成效地應(yīng)用于無人機任務(wù)分配領(lǐng)域，但卻忽略了執(zhí)行任務(wù)中的各種因素（包括無人機的收益回報、任務(wù)的優(yōu)先級、無人機的能力、任務(wù)的限制條件等），這些因素都會在一定程度上阻礙無人機性能的發(fā)揮。因此，本文提出一種結(jié)合DE和PSO算法的博弈算法——GBDEPSO算法來改進搜索，采用博弈論中的聯(lián)盟博弈模型來實現(xiàn)算法之間的相互協(xié)作，在每一輪迭代和特定迭代之后，DE和PSO算法進入博弈環(huán)境，并基于納什議價理論共同進行博弈，以此達到聯(lián)盟博弈中的納什均衡狀態(tài)。

在該方法中，PSO算法被認為是第一架無人機，DE算法被認為是第二架無人機。每架無人機的初始狀態(tài)都是使用目標函數(shù)獨立評估的。在對第一架無人機和第二架無人機的所有解進行評估后，選擇第一架無人機和第二架無人機中的最佳解。

將這兩個較好的解決方案相互比較，從而在第一輪博弈中選擇最佳解決方案作為分歧點（v1，v2）。由于博弈時兩架無人機都有相同的條件并且是對稱的，所以在第一輪中v1 = v2的值在第一輪是相等的。

在每一輪迭代中，第一架無人機和第二架無人機各自獨立運行N次，在每次迭代中，集合M1存儲第一架無人機的最優(yōu)解，集合M2存儲第二架無人機的最優(yōu)解。這意味著在每次的迭代中，N個最優(yōu)解存儲在集合M1和M2中。

下面的關(guān)系展現(xiàn)了可行集合F，它等于兩架無人機在N次迭代中最佳解評估值的笛卡爾乘積。

經(jīng)過N次迭代，雙方進入博弈環(huán)境，根據(jù)式（5）對可行集F和分歧點（v1，v2）應(yīng)用納什議價定理。最終， 被選為最優(yōu)選擇，即兩架無人機合作的結(jié)果。

其中，根據(jù)議價理論的條件，如果從可行集F中選擇的（x1，x2）優(yōu)于分歧點（v1，v2），則認為它是唯一答案 ，否則分歧點被選為唯一答案 ?；谂晾弁凶顑?yōu)性，唯一答案? 是雙方的最佳答案。

表示第一架無人機的博弈收益，作為下一輪迭代DE變異算子中的基向量，引起DE變異算子的變化。計算式如下：

表示第二架無人機的博弈收益，作為PSO中的領(lǐng)先粒子，用于更新下一輪迭代中的粒子速度向量，改變粒子運動方向。計算式如下：

作為第二架無人機的分歧點被更新。實際上，這一輪納什議價的值? 作為下一輪納什議價的分歧點（v1，v2）。

如果滿足協(xié)議的條件，則從兩個值中選擇最佳值? 作為最后的解決方案，否則重復(fù)進行下一輪博弈。

還需要注意的是，在博弈環(huán)境中，為了獲得納什議價理論的解，使用可行集F和分歧點中解的評價值。

總之，納什議價定理的條件有助于在所提出的算法中保持探索能力和利用能力之間的平衡。事實上，從可行集F中選擇（x1，x2）會導(dǎo)致對問題空間進行徹底的探索和搜索，以找到最優(yōu)解。此外，選擇分歧點（v1，v2）的好處是提取更好的解決方案。從算法之間的博弈中獲得收益的交換使得在搜索環(huán)境中探索新的領(lǐng)域，增加多樣性，避免局部最優(yōu)。

3? 仿真結(jié)果與分析

在研究無人機任務(wù)分配中，本實驗設(shè)置了二維的實驗場景地圖，同時為了對算法的魯棒性進行分析，分別設(shè)置三種不同場景下的實驗，如表1所示。其中，小范圍任務(wù)包含5架無人機、30個目標，以及5 km×5 km的任務(wù)區(qū)域，中范圍任務(wù)包含10架無人機、60個目標，以及10 km×10 km的任務(wù)區(qū)域，大范圍任務(wù)包含15架無人機、90個目標，以及15 km×15 km的任務(wù)區(qū)域。

在進行仿真實驗時，隨機生成任務(wù)目標點的坐標、獎勵和任務(wù)所需時間，當環(huán)境中分布30個任務(wù)目標點時，任務(wù)目標點的坐標、獎勵和任務(wù)所需時間如表2所示。

在進行仿真訓練時，任務(wù)資源也是隨機產(chǎn)生的，所有無人機都是初始化于坐標（0，0）的倉庫中，并且每一次任務(wù)都有完成時間限制。

實驗主要分為三組：小規(guī)模、中規(guī)模和大規(guī)模，如圖2、圖3、圖4所示，不同規(guī)模具有不同的參數(shù)。除了無人機和目標的數(shù)量外，其他關(guān)鍵擴展參數(shù)則是隨機生成的，例如任務(wù)位置、任務(wù)獎勵、不同任務(wù)的時間消耗和飛行速度。在每個參數(shù)設(shè)置下，每個算法中求解10次。

解決多無人機多任務(wù)分配問題的結(jié)果如圖5至圖13所示，在所得到的分配結(jié)果和所有無人機得到的回報總和中，回報值越大說明任務(wù)完成程度越高。其中，被折線經(jīng)過的點表示已完成的目標，未被經(jīng)過的表示未完成的目標，中心大點表示無人機倉庫。任務(wù)點的大小與無人機完成此任務(wù)所得回報成正比，而不同折線代表的是不同UAV的行動路徑。

3.1? PSO粒子群算法

在權(quán)重系數(shù)相同，無人機與任務(wù)坐標不變的情況下，使用PSO算法進行三組對比實驗。

如圖5、圖6、圖7所示，在限定時間內(nèi)，PSO算法在小、中、大范圍任務(wù)中分別獲得了回報83、143和250點。

3.2? DE差分進化算法

在權(quán)重系數(shù)相同，無人機與任務(wù)坐標不變的情況下，使用DE算法進行三組對比實驗。

如圖8、圖9、圖10所示，在限定時間內(nèi)，DE算法在小、中、大范圍任務(wù)中分別獲得了回報80、154和239點。

3.3? GBDEPSO基于博弈的差分和粒子群聯(lián)合算法

在與PSO和GD算法相同的條件下，使用本文所提出的GBDEPSO基于博弈的差分和粒子群聯(lián)合算法進行三組實驗，可以看出無論是在小范圍、中范圍還是大范圍任務(wù)中，GBDEPSO在限定時間內(nèi)所得到的任務(wù)回報總數(shù)均高于其他兩種方法。

如圖11、圖12、圖13所示，在限定時間內(nèi)，PSO算法在小、中、大范圍任務(wù)中分別獲得了回報97、160和292點。

通過對實驗過程和結(jié)果的對比可知，GBDEPSO在限定時間內(nèi)能夠更加合理地對無人機集群進行任務(wù)分配。如圖14、圖15所示，分別展現(xiàn)了三種算法在不同類型任務(wù)下十次訓練的平均任務(wù)回報和平均訓練時間，雖然在訓練所用時間上GBDEPSO相較于其他兩種算法有明顯的不足，但是其平均回報數(shù)有較大的提升，驗證了GBDEPSO算法的有效性。

4? 結(jié)? 論

本文針對無人機任務(wù)分配問題進行分析、建模，提出一種混合DE算法和PSO算法來解決優(yōu)化問題。DE算法和PSO算法都有各自的缺點，PSO算法在解決復(fù)雜優(yōu)化問題時過早收斂，可能會陷入無法逃脫的局部最優(yōu)，DE算法嚴重依賴于試驗向量生成策略和所使用的參數(shù)值。為了解決這些問題，在所提出的GBDEPSO算法中實行了DE和PSO優(yōu)化算法的組合和協(xié)作，這種合作是基于納什議價理論而進行的。簡單地說，納什議價定理試圖使兩個參與者所獲得的利潤最大化，避免局部最優(yōu)。事實上，博弈在算法之間創(chuàng)造一種競爭環(huán)境，大大提高了算法的搜索能力。實驗結(jié)果表明，本文算法雖然在訓練時間方面稍有劣勢，但是算法所得回報總數(shù)相比PSO和DE有較大幅度的提升，實現(xiàn)了任務(wù)執(zhí)行過程中距離代價最小，無人機可用資源更均衡的優(yōu)化目標。

參考文獻：

[1] XING N，ZONG Q，TIAN B L，et al. Nash Network Formation among Unmanned Aerial Vehicles [J].Wireless Networks，2020，26（3）：1781-1793.

[2] 宗群，王丹丹，邵士凱，等.多無人機協(xié)同編隊飛行控制研究現(xiàn)狀及發(fā)展 [J].哈爾濱工業(yè)大學學報，2017，49（3）：1-14.

[3] JING D，JIAN C，MIN S. Cooperative task assignment for heterogeneous multi-UAVs based on differential evolution algorithm [C]//2009 IEEE International Conference on Intelligent Computing and Intelligent Systems.Shanghai：IEEE，2009，163-167.

[4] 吳蔚楠，關(guān)英姿，郭繼峰，等.基于SEAD任務(wù)特性約束的協(xié)同任務(wù)分配方法 [J].控制與決策，2017，32（9）：1574-1582.

[5] YAN M，YUAN H M，XU J，et al. Task allocation and route planning of multiple UAVs in a marine environment based on an improved particle swarm optimization algorithm [J/OL].EURASIP Journal on Advances in Signal Processing，2021：1-23[2023-01-05]. https：//link.springer.com/article/10.1186/s13634-021-00804-9.

[6] 孫亞男，吳杰宏，石峻嶺，等.改進自組織映射的多無人機協(xié)同任務(wù)分配方法 [J].計算機應(yīng)用，2023，43（5）：1551-1556.

[7] 吳歇爾.面向多無人機的協(xié)同任務(wù)預(yù)分配及重分配研究 [D].南昌：南昌航空大學，2018.

作者簡介：王松柏（1998—），男，漢族，江蘇泰州人，碩士研究生在讀，研究方向：智能體決策優(yōu)化。