劉夏婷，傅 強(qiáng)

（中國民用航空飛行學(xué)院飛行技術(shù)學(xué)院，廣漢 618307）

0 引言

無人機(jī)（unmanned aerial vehicle，UAV）擁有成本低、自主程度高、機(jī)動靈活等優(yōu)點(diǎn)，被廣泛應(yīng)用于服務(wù)、農(nóng)業(yè)、軍事等領(lǐng)域［1-3］。在復(fù)雜環(huán)境下為了完成多樣變化的無人機(jī)任務(wù)，使用攜帶不同功能的集群無人機(jī)執(zhí)行任務(wù)已成為重要方式。對于多無人機(jī)任務(wù)分配問題，構(gòu)建的問題模型和使用的智能算法是至關(guān)重要的。

文獻(xiàn)［4］提出一種混合粒子群算法，創(chuàng)新性地提出對多攻擊任務(wù)死鎖檢測和修復(fù)算法，對任務(wù)重分配使用匹配策略思想，可有效解決協(xié)同攻擊任務(wù)重分配問題。文獻(xiàn)［5］對多無人機(jī)的偵察任務(wù)分配問題進(jìn)行研究，使用蟻群算法模擬多種不同載荷情況，其求解的分配方案更加貼合實(shí)際情況。文獻(xiàn)［6］使用量子遺傳算法進(jìn)行全局任務(wù)分配，同時加入混合蛙跳優(yōu)化策略，跳出局部極值并減少了算法的整體迭代次數(shù)。文獻(xiàn)［7］使用改進(jìn)蟻群算法對任務(wù)分配和路徑規(guī)劃聯(lián)合優(yōu)化，新增加無人機(jī)編隊(duì)數(shù)量約束，并引入信息素更新以保證資源的充分利用。文獻(xiàn)［8］提出基于并行機(jī)制的多目標(biāo)灰狼算法，在算法中引入分層編碼和檔案室共享策略，可有效提高求解速度和收斂能力。文獻(xiàn)［9］在基礎(chǔ)的布谷鳥算法中通過調(diào)整自適應(yīng)步長以及加入模擬退火算法，使算法不容易陷入局部最優(yōu)。

針對多無人機(jī)任務(wù)分配問題，本文提出基于Logistics混沌的多目標(biāo)麻雀搜索算法，構(gòu)建任務(wù)分配目標(biāo)函數(shù)，對麻雀搜索算法進(jìn)行改進(jìn)并優(yōu)化，可高效快速地求解任務(wù)分配目標(biāo)函數(shù)。

1 模型建立

1.1 問題描述

本文主要研究在模擬的二維戰(zhàn)場空間內(nèi)，我方多無人機(jī)對地面目標(biāo)完成評估、偵察、攻擊三項(xiàng)任務(wù)。無人機(jī)均從同一確定基地起飛。假設(shè)無人機(jī)數(shù)量NV，其集合為V={V1,V2,V3,…,VNV}，移動的空中目標(biāo)數(shù)量為NT， 集合為T={T1,T1,T3,…,TNT}，每個目標(biāo)需完成三項(xiàng)任務(wù)，即評估、偵察和攻擊，其任務(wù)數(shù)量為NU，任務(wù)集合為U={reconnoitre,attack,estimate} ，NU=3。在模擬的二維平面內(nèi)，無人機(jī)i對應(yīng)的位置為（xi,y）i，目標(biāo)j對應(yīng)的位置為（xj,y）j。其相對距離可表示為分別考慮無人機(jī)執(zhí)行任務(wù)時的威脅代價，執(zhí)行偵察、評估、攻擊任務(wù)帶來的收益，完成任務(wù)的航行距離，以這三個評價指標(biāo)為基礎(chǔ)綜合建立多無人機(jī)任務(wù)分配目標(biāo)函數(shù)。

1.2 評價指標(biāo)

1.2.1 威脅代價

威脅代價是指無人機(jī)在執(zhí)行任務(wù)時，任務(wù)目標(biāo)對無人機(jī)造成無人機(jī)損毀付出的代價。假設(shè)無人機(jī)i的價值為valuei，目標(biāo)j對無人機(jī)i的威脅概率為Sij，即無人機(jī)執(zhí)行任務(wù)后的生存概率為(1 -Sij)。經(jīng)過所有目標(biāo)后，無人機(jī)產(chǎn)生的執(zhí)行代價計算如下：

1.2.2 任務(wù)收益

當(dāng)無人機(jī)依次完成偵察、攻擊、評估三項(xiàng)任務(wù)時，根據(jù)無人機(jī)的偵察能力指數(shù)、對目標(biāo)的毀傷概率、評估能力分別得到收益P1ij、P2ij、P3ij。

因此，無人機(jī)完成任務(wù)的總收益為

1.2.3 航行代價

航程代價是指無人機(jī)到達(dá)執(zhí)行任務(wù)位置時所需的距離代價，本文采用直線度量。

Dis（Tij）指無人機(jī)i到目標(biāo)j的距離，dmax指無人機(jī)執(zhí)行偵察任務(wù)的最遠(yuǎn)距離。

1.3 總收益適應(yīng)度目標(biāo)函數(shù)

式（8）中Wi為權(quán)重系數(shù)，且W1+W2+W3= 1。

1.4 約束條件

1.4.1 任務(wù)時序約束

1.4.2 無人機(jī)執(zhí)行任務(wù)約束

（1）目標(biāo)的三種任務(wù)可被不同無人機(jī)執(zhí)行，且一架無人機(jī)只能執(zhí)行該點(diǎn)的一種任務(wù)。

（2）所有任務(wù)均被完成。

2 改進(jìn)多目標(biāo)麻雀搜索算法

2.1 經(jīng)典麻雀搜索算法

在麻雀搜索算法中，有發(fā)現(xiàn)者、跟隨者和警戒者三類。警戒者所占種群比例10%～20%，發(fā)現(xiàn)者和跟隨者所占比例是不確定的。其中發(fā)現(xiàn)者的主要職責(zé)是尋找食物所在的方向和位置，跟隨者是跟隨發(fā)現(xiàn)者進(jìn)行覓食，警戒者負(fù)責(zé)對覓食區(qū)域的監(jiān)視。為獲得生存的資源，該算法通過在尋找食物過程中不斷更新三者的位置完成。發(fā)現(xiàn)者的位置更新方式如下：

其中，表示在第t代中第i只麻雀在第j維的位置，R2表示報警值。

跟隨者的位置更新：

其中，表示第t代適應(yīng)度最差的個體位置，表示第t+1 代中適應(yīng)度最佳的個體位置。A+=AT(AAT)-1。

警戒者位置更新方式如下：

其中，表示第t代中全局最優(yōu)位置，β為控制步長。fi表示當(dāng)前個體的適應(yīng)度值，fg和fw表示目前全局最優(yōu)和最差個體的適應(yīng)度值。

2.2 改進(jìn)多目標(biāo)麻雀搜索算法

2.2.1 利用Logistic映射初始化種群

麻雀搜索算法尋優(yōu)能力較好，但其結(jié)果具有較大的隨機(jī)性，且初始化種群麻雀個體的位置會影響算法結(jié)果的穩(wěn)定性，因此在初始化種群階段利用Logistic 映射，在初期階段進(jìn)行個體分類，隨著迭代次數(shù)變化提高了種群的多樣性，在一定程度上減小了算法陷入局部最優(yōu)的概率。其數(shù)學(xué)表達(dá)公式如下：

其中，μ為Logistic 參數(shù)。為了保證映射得到的Xn始終位于［0,1］內(nèi)，則μ∈［0,4］。x（t）為在t時刻種群占最大可能種群規(guī)模的比例。

2.2.2 利用Pareto最優(yōu)解求解多目標(biāo)優(yōu)化問題

利用Pareto 多目標(biāo)優(yōu)化問題的主要思想是首先對不同目標(biāo)優(yōu)先級或權(quán)重進(jìn)行明確，然后試圖找到優(yōu)化條件在不同權(quán)重下各為最優(yōu)解的一組解，然后根據(jù)決策者的偏好或應(yīng)用場景決定選擇哪個解。

多目標(biāo)優(yōu)化定義如下：

其中，u∈Ω 為決策向量，Ω 為決策空間；y∈Y，為目標(biāo)向量，Y為目標(biāo)函數(shù)空間。

3 算法流程

具體算法流程如下：

步驟一：利用Logistic映射策略初始化種群、迭代次數(shù)，以及初始化捕食者和加入者比例；

步驟二：計算適應(yīng)度值，并對結(jié)果排序；

步驟三：麻雀更新捕食者位置；

步驟四：麻雀更新加入者位置；

步驟五：麻雀更新警戒者位置；

步驟六：計算適應(yīng)度值并更新麻雀位置；

步驟七：是否滿足停止條件，若滿足條件則結(jié)束，輸出結(jié)果；否則，重復(fù)執(zhí)行步驟二至步驟六。

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

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

本文對實(shí)驗(yàn)場景構(gòu)想如下：在多無人機(jī)任務(wù)分配過程中不考慮能源消耗、通信約束以及載荷約束。為方便計算，將無人機(jī)和目標(biāo)均視為具有速度、角度、價值、概率等屬性的質(zhì)點(diǎn)。仿真環(huán)境的區(qū)域設(shè)置為5 km×5 km的平面。無人機(jī)的初始位置從固定點(diǎn)（1.1）開始。

假設(shè)現(xiàn)有7 架無人機(jī)對4 個目標(biāo)進(jìn)行偵察、評估、攻擊任務(wù)，無人機(jī)的基本參數(shù)和目標(biāo)參數(shù)及毀傷概率分別見表1、表2和表3。

表1 無人機(jī)的基本參數(shù)

表2 目標(biāo)參數(shù)設(shè)置

經(jīng)多次實(shí)驗(yàn)數(shù)據(jù)對比，取適應(yīng)度函數(shù)W1= 0.3,W2= 0.3,W3= 0.4。

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

4.2.1 結(jié)果分析

無人機(jī)任務(wù)目標(biāo)分配結(jié)果見表4所示。

從任務(wù)分配結(jié)果可以看出，無人機(jī)V1完成了T4與T2的評估任務(wù)，無人機(jī)V2完成了T2的偵察任務(wù)與T4的攻擊任務(wù)，無人機(jī)V3完成了T1的偵察任務(wù)，無人機(jī)V4完成了T2的攻擊任務(wù)與T3的評估任務(wù)，無人機(jī)V5完成了T1與T3的偵察任務(wù)，無人機(jī)V6完成了T1的評估任務(wù)與T3的攻擊任務(wù)，無人機(jī)V7完成了T4的偵察任務(wù)。每個無人機(jī)的任務(wù)均為唯一，且每個目標(biāo)的偵察、攻擊、評估任務(wù)均被完成。

總收益適應(yīng)度目標(biāo)函數(shù)結(jié)果如圖1所示。

圖1 算法適應(yīng)度曲線

由圖1 可知，改進(jìn)麻雀搜索算法利用Pareto最優(yōu)解求解多目標(biāo)優(yōu)化問題，獲得了更快的收斂速度，利用Logistic 映射在初期階段進(jìn)行個體分類，隨著迭代次數(shù)變化的同時提高了種群的多樣性，一定程度上減小了算法陷入局部最優(yōu)的概率。

4.2.2 不同場景下實(shí)驗(yàn)結(jié)果及分析

為驗(yàn)證算法的有效性，使用ISSA、SSA 和GA 三種算法求解不同場景下的多無人機(jī)任務(wù)分配問題。三種算法的最大迭代次數(shù)均設(shè)置為100，其他參數(shù)的設(shè)置均一樣。其目標(biāo)迭代收斂曲線如圖2、圖3和圖4所示。

圖2 10無人機(jī)對5個目標(biāo)的收斂曲線

圖3 13無人機(jī)對6個目標(biāo)的收斂曲線

圖4 16無人機(jī)對7個目標(biāo)的收斂曲線

從總體上看，三種算法迭代收斂的目標(biāo)函數(shù)最終都會趨于一個穩(wěn)定值。ISSA 算法的收斂值均小于其他兩種算法。從圖2可以看出，在目標(biāo)數(shù)量較少的情況下，相比其他兩種算法，隨迭代次數(shù)增加，ISSA 算法可以在較短時間內(nèi)經(jīng)過較少的迭代次數(shù)達(dá)到穩(wěn)定的目標(biāo)函數(shù)值。在圖3 和圖4 中，當(dāng)目標(biāo)數(shù)量增加時，迭代初期三種算法目標(biāo)函數(shù)值較為不穩(wěn)定，上下波動，優(yōu)化算法的搜索操作呈現(xiàn)不穩(wěn)定的狀態(tài)；在迭代后期，各算法的搜索能力較為平穩(wěn)，目標(biāo)函數(shù)值也趨于穩(wěn)定。因此，與GA 與SSA 相比，ISSA具有良好的收斂性能。

5 結(jié)語

本文以麻雀搜索算法為基礎(chǔ)，加入了Logistic映射策略來建立無人機(jī)任務(wù)分配模型，利用Pareto 多目標(biāo)優(yōu)化問題的主要思想對目標(biāo)的威脅代價、航程代價、任務(wù)收益進(jìn)行權(quán)重分配，多次試驗(yàn)找到最優(yōu)解。仿真結(jié)果表明，本文研究的模型合理有效，且應(yīng)用在不同的場景下也有較大優(yōu)勢，通過算法的改進(jìn)不僅加強(qiáng)了種群多樣性，同時提高了算法的收斂精度以及搜索效率。