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

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

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

中圖分類號(hào)：TP18? ? 文獻(xiàn)標(biāo)識(shí)碼：A? 文章編號(hào)：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? 引? 言

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

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

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

1? 算法概述

1.1? PSO算法基本原理和特點(diǎn)

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

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

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

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

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

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

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

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

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

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

1.2? DE算法基本原理和特點(diǎn)

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

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

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

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

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

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

1.3? 納什議價(jià)理論基本原理和特點(diǎn)

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

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

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

納什提出的議價(jià)理論，遵循以下5個(gè)原則：

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

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

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

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

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

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

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

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

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

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

在該方法中，PSO算法被認(rèn)為是第一架無人機(jī)，DE算法被認(rèn)為是第二架無人機(jī)。每架無人機(jī)的初始狀態(tài)都是使用目標(biāo)函數(shù)獨(dú)立評(píng)估的。在對(duì)第一架無人機(jī)和第二架無人機(jī)的所有解進(jìn)行評(píng)估后，選擇第一架無人機(jī)和第二架無人機(jī)中的最佳解。

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

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

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

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

其中，根據(jù)議價(jià)理論的條件，如果從可行集F中選擇的（x1，x2）優(yōu)于分歧點(diǎn)（v1，v2），則認(rèn)為它是唯一答案 ，否則分歧點(diǎn)被選為唯一答案 。基于帕累托最優(yōu)性，唯一答案? 是雙方的最佳答案。

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

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

作為第二架無人機(jī)的分歧點(diǎn)被更新。實(shí)際上，這一輪納什議價(jià)的值? 作為下一輪納什議價(jià)的分歧點(diǎn)（v1，v2）。

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

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

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

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

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

在進(jìn)行仿真實(shí)驗(yàn)時(shí)，隨機(jī)生成任務(wù)目標(biāo)點(diǎn)的坐標(biāo)、獎(jiǎng)勵(lì)和任務(wù)所需時(shí)間，當(dāng)環(huán)境中分布30個(gè)任務(wù)目標(biāo)點(diǎn)時(shí)，任務(wù)目標(biāo)點(diǎn)的坐標(biāo)、獎(jiǎng)勵(lì)和任務(wù)所需時(shí)間如表2所示。

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

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

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

3.1? PSO粒子群算法

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

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

3.2? DE差分進(jìn)化算法

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

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

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

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

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

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

4? 結(jié)? 論

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

參考文獻(xiàn)：

[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] 宗群，王丹丹，邵士凱，等.多無人機(jī)協(xié)同編隊(duì)飛行控制研究現(xiàn)狀及發(fā)展 [J].哈爾濱工業(yè)大學(xué)學(xué)報(bào)，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] 孫亞男，吳杰宏，石峻嶺，等.改進(jìn)自組織映射的多無人機(jī)協(xié)同任務(wù)分配方法 [J].計(jì)算機(jī)應(yīng)用，2023，43（5）：1551-1556.

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

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