宗?群，秦新立，張博淵，田栢苓，王丹丹

?

基于DPSO-GT-SA算法的大規(guī)模UCAV協(xié)同任務分配

宗?群，秦新立，張博淵，田栢苓，王丹丹

(天津大學電氣自動化與信息工程學院，天津 300072)

無人作戰(zhàn)飛機(UCAV)編隊任務分配是研究UCAV編隊飛行作戰(zhàn)的關鍵．針對復雜約束環(huán)境下大規(guī)模UCAV協(xié)同任務分配問題，提出改進離散粒子群算法．根據(jù)現(xiàn)有UCAV編隊空對地飽和作戰(zhàn)模式，建立UCAV編隊作戰(zhàn)環(huán)境中任務分配模型，通過采用離散粒子群優(yōu)化-郭濤-模擬退火算法(DPSO-GT-SA)進行求解．根據(jù)粒子編碼方式建立粒子與UCAV及目標之間的映射，通過粒子交叉變異進行搜索與尋優(yōu)，并通過模擬退火Metropolis準則跳出局部最優(yōu)．在復雜約束條件下，為解決離散粒子群-郭濤算法(DPSO-GT)陷入局部極小問題，引入改進模擬退火算法．為解決模擬退火后期收斂速度慢問題，在DPSO-GT-SA算法中加入動態(tài)溫度衰減因子．仿真結(jié)果表明，改進離散粒子群算法可以更好地解決大規(guī)模UCAV協(xié)同任務分配問題．

大規(guī)模無人作戰(zhàn)飛機；協(xié)同任務分配；改進離散粒子群優(yōu)化；模擬退火

無人作戰(zhàn)飛機(unmanned combat aerial vehicles，UCAV)編隊任務分配是研究UCAV編隊控制的關鍵，被美國空軍科學研究局列為六大基礎研究課題之一．任務分配是指在UCAV執(zhí)行多個任務時，由于UCAV性質(zhì)、用途、作戰(zhàn)能力、載荷等各不相同，在滿足各種約束條件下，為UCAV找到最佳的任務分配方案，在保證UCAV飛行代價最小的情況下，能夠獲得最大收益．

任務分配的控制方式主要有集中式控制、分布式控制與分層次分布式控制3種[1]．目前，針對集中式的任務分配模型主要有多維旅行商模型[2]、車輛路徑模型[3]、多維多選擇背包問題模型[4]、動態(tài)網(wǎng)絡流優(yōu)化模型[5]、混合整數(shù)線性規(guī)劃模型[6]以及相關模型的改進．針對分布式的任務分配模型主要有基于合同網(wǎng)市場競拍模型[7]、拍賣算法模型[8]等．大規(guī)模UCAV任務分配是組合優(yōu)化中典型的NP-Hard問題．對于以上任務分配模型，優(yōu)化求解算法主要包括數(shù)學規(guī)劃算法和啟發(fā)式算法．數(shù)學規(guī)劃算法雖能求得最優(yōu)解，但具有較高的時間和空間復雜度，當問題規(guī)模增大時，求解難度也急劇增加，時間耗費呈指數(shù)增長[9]．啟發(fā)式算法雖然不一定得到最優(yōu)解，但計算復雜度低、性能優(yōu)越．在UCAV協(xié)同任務分配領域，現(xiàn)有的最新研究主要集中在復雜約束下的多UCAV任務分配問題上．

粒子群優(yōu)化(particle swarm optimization，PSO)算法是一種高效的并行搜索啟發(fā)式算法，非常適于對復雜約束環(huán)境中優(yōu)化問題的求解，已經(jīng)得到廣泛應用和發(fā)展．但PSO算法主要用于求解連續(xù)空間中的優(yōu)化問題，所以對于離散或者組合優(yōu)化問題，需要做一些改進，便產(chǎn)生許多版本的離散粒子群優(yōu)化(discrete particle swarm optimization，DPSO)算法．1997年，美國普渡大學Kennedy等[10]針對PSO算法無法解決多個離散變量的缺點，提出一種二進制DPSO算法．2011年，山東商業(yè)職業(yè)技術(shù)學院Chen等[11]針對PSO算法處理離散問題效率低問題，提出一種改進DPSO算法，在粒子群優(yōu)化算法中引入蟻群算法中的女王信息素概念，有效提高了收斂速度．2013年，突尼斯斯法克斯大學Ktari等[12]提出了一種新的啟發(fā)式算法，禁忌搜索粒子群女王算法，將基本粒子群女王算法和禁忌搜索結(jié)合，能夠有效求解大規(guī)模0-1多維背包問題．2016年，印度尼赫魯大學Kumar等[13]針對任務調(diào)度問題，把PSO算法和遺傳算法(genetic algorithm，GA)相結(jié)合，提出了混合PSO-GA算法，該算法可以解決復雜組合優(yōu)化問題．2016年，斯法克斯大學Hadder等[14]提出了一種帶局部搜索的量子粒子群優(yōu)化算法，能夠有效解決廣義共享背包問題．2018年，馬德里大學的López等[15]把二進制粒子群優(yōu)化算法和GA結(jié)合，提出了混合粒子群遺傳算法，相比PSO算法，所提算法更能有效解決多旅行商問題．1998年武漢大學Guo等[16]針對TSP提出了基于Inver-over算子的郭濤(GT)算法．2010年，河海大學鄭東亮等[17]針對DPSO算法收斂速度慢、精度低等缺點，提出基于Inver-over算子的DPSO算法，與DPSO算法和GT算法相比，改進算法收斂速度和求解精度都有較大提高．2015年，海軍航空工程學院顏驥等[18]針對多無人機協(xié)同復雜任務分配問題，提出了DPSO-GT算法，有效解決復雜任務分配問題. 2010年，西北工業(yè)大學李儼等[19]針對DPSO易陷入局部最優(yōu)的缺點，把模擬退火(simulated annealing，SA)算法引入DPSO中，相比其他改進DPSO算法，所提算法更能有效求解火力分配問題．

DPSO算法對于大規(guī)模復雜約束優(yōu)化問題收斂速度慢，尋優(yōu)效果差．由于GT算法收斂速度快、精度高，可以彌補DPSO算法的缺點，但是現(xiàn)有的DPSO-GT算法對于解決大規(guī)模復雜約束問題易陷入局部極值．

本文在前人研究工作基礎上，采用基于啟發(fā)式算法的大規(guī)模任務分配方法，解決復雜約束戰(zhàn)場環(huán)境下的大規(guī)模UCAV任務分配問題．根據(jù)現(xiàn)有的大規(guī)模UCAV飽和作戰(zhàn)模式，建立大規(guī)模UCAV任務分配模型．針對大規(guī)模復雜約束問題，現(xiàn)有DPSO-GT算法易陷入局部極值的問題，引入了改進的SA算法，提出了DPSO-GT-SA算法，可以有效解決復雜約束下大規(guī)模UCAV任務分配問題．

1?大規(guī)模UCAV協(xié)同任務分配模型

根據(jù)UCAV的作戰(zhàn)場景構(gòu)建大規(guī)模UCAV協(xié)同作戰(zhàn)的任務分配模型．記UCAV數(shù)量為，任務數(shù)量為a，為了便于分析，變量定義如表1所示．

表1?變量定義

Tab.1?Definition of variables

1.1?約束指標

1.1.1?UCAV及任務類型約束

任務目標類型包括3類：偵查、電子干擾和攻擊．UCAV可執(zhí)行偵查、電子干擾和攻擊中的一種或幾種．UCAV能否執(zhí)行任務目標可表示為

???(1)

1.1.2?燃料約束

根據(jù)UCAV和任務目標的位置，計算UCAV各自的燃料消耗．第個UCAV所在基地和第個任務目標的距離可以表示為

?????(2)

第個UCAV執(zhí)行任務并返回基地的燃料消耗可以表示為

???(3)

在任務分配過程中假設UCAV都是恒高定速的，可以認為UCAV單位距離燃料消耗為定值．考慮攝動因素對UCAV飛行過程中燃料消耗影響，引入燃料冗余度，則燃料約束可以表示為

???(4)

1.1.3?作戰(zhàn)能力約束

根據(jù)各UCAV和任務目標的作戰(zhàn)和防御能力，第個UCAV執(zhí)行第個任務目標時自身損毀代價可以表示為

???(5)

根據(jù)各UCAV和任務目標的作戰(zhàn)和防御能力，第個UCAV執(zhí)行第個任務目標的收益，可以表示為

???(6)

1.1.4?UCAV數(shù)目約束

針對大規(guī)模UCAV飽和攻擊任務分配問題，考慮UCAV數(shù)目遠遠大于任務目標數(shù)目，要求每個任務目標需要由多個UCAV執(zhí)行，且每個UCAV當且僅當執(zhí)行一個任務，可以表示為

???(7)

1.2?性能指標

1.2.1?任務代價指標

任務代價指標主要包括兩個方面：①執(zhí)行任務所造成的UCAV的損傷代價，記為los；②執(zhí)行目標所需要的油耗，記為fuel．

損傷代價函數(shù)通過每個UCAV執(zhí)行任務目標時的被毀傷概率和UCAV的重要程度綜合得到，可以表示為

???(8)

執(zhí)行目標所需要的油耗可以表示為

???(9)

1.2.2?任務收益指標

任務收益函數(shù)通過每個UCAV對任務目標的毀傷概率、任務目標的重要程度綜合得到．

UCAV編隊執(zhí)行全部任務目標的任務收益函數(shù)可以表示為

???(10)

1.2.3?罰函數(shù)

罰函數(shù)構(gòu)造思想是把有約束問題轉(zhuǎn)化為無約束問題進行求解．對執(zhí)行任務目標所需UCAV數(shù)量約束轉(zhuǎn)化為性能指標處理，可以表示為

??????(11)

1.2.4?綜合性能指標

性能指標是由任務收益函數(shù)、任務代價函數(shù)和罰函數(shù)綜合得到的，即

????????????(12)

2?算法介紹

2.1?DPSO算法

PSO算法是基于群體的智能演化算法，群體按照一種合作的方式尋找食物，群體中的每個成員通過學習自身或其他成員的經(jīng)驗來不斷地改變搜索的方向，從而使整個群體的運動在問題求解空間中產(chǎn)生從無序到有序的演化過程，進而獲得問題的最優(yōu)解．

PSO算法采用速度-位置搜索模型，每個粒子代表解空間中的一個候選解，解的優(yōu)劣程度由適應度函數(shù)決定．速度決定粒子在搜索空間迭代時的位移．PSO算法局限于位置與速度更新公式，不能有效拓寬到離散和組合領域．通過對PSO算法機理的深入分析和研究，發(fā)現(xiàn)PSO算法的本質(zhì)是利用粒子自身信息、個體極值信息和全局極值信息來指導其下一步迭代．正如GA求解組合優(yōu)化問題時重新構(gòu)造變異與交叉算子一樣，對PSO算法求解組合優(yōu)化問題時，可重新構(gòu)造其更新公式．DPSO算法的速度-位置搜索模型可以表示為

???(13)

DPSO算法基本步驟如下：

步驟2?根據(jù)式(13)更新每個個體的速度和位置向量；

2.2?郭濤算法

GT算法是武漢大學Guo等[16]提出的一種結(jié)合子空間搜索和群體爬山法的隨機優(yōu)化算法．GT算法是一種基于序列倒置算子的優(yōu)化算法，其依概率進行相應倒置，倒置過程中淘汰較差的解，保留較優(yōu)的解．GT算法簡單，能夠充分利用群體信息，有利于全局尋優(yōu)．GT算法是隨機選擇種群中的粒子進行學習的，雖然保障了全局搜索，但其學習具有盲目性，影響 GT算法后期收斂速度．

GT算法基本步驟如下：

步驟1?初始化過程．初始種群、迭代次數(shù)和選擇概率；

步驟2?產(chǎn)生一個0～1之間的隨機數(shù)，當隨機數(shù)小于選擇概率時，在自身粒子中隨機選擇一段序列作為學習對象產(chǎn)生新的解，類似GA中的變異操作；

步驟3?如果隨機數(shù)大于選擇概率，當前個體向種群中其他個體學習產(chǎn)生新的解，類似GA中的交叉操作；

步驟4?計算新解的適應度值，若新解適應度值變好則接受新解，否則不接受；

步驟5?判斷是否滿足迭代終止條件，若滿足，則終止尋優(yōu)，輸出當前解為最優(yōu)解；否則轉(zhuǎn)步驟2．

2.3?SA算法

SA算法是Kirkpatrick等[20]發(fā)明的一種依概率搜索算法．SA基于冶金學中固體物質(zhì)退火過程和組合優(yōu)化問題的相似性．退火是將材料加熱后再經(jīng)特定速率冷卻．材料中的原子原來會停留在使內(nèi)能有局部最小值的位置，加熱使能量變大，原子會離開原來位置，而隨機在其他位置中移動．退火冷卻時速度較慢，使得原子有較多可能找到內(nèi)能比原先更低的位置．SA算法能夠以一定概率接受差的解，保證迭代過程中跳出局部最優(yōu)．理論證明，SA算法在一定條件下以概率1收斂于全局最優(yōu)解．

針對大規(guī)模組合優(yōu)化問題，SA算法是一種通用而有效的近似算法．SA算法具有初值魯棒性強、不受初始條件約束，算法描述簡單、通用易實現(xiàn)，適應于并行處理的優(yōu)點，但收斂速度較慢、執(zhí)行時間長等缺點．

SA算法基本步驟如下：

步驟1?初始化過程．初始溫度(充分大)，溫度衰減因子，總的迭代次數(shù)，初始解(算法迭代的起點)，每個值的迭代次數(shù)；

步驟2?對＝1，2，…，執(zhí)行步驟3至步驟5；

步驟3?產(chǎn)生新解，新解通常通過結(jié)合GA中交叉變異產(chǎn)生[21]；

步驟6?執(zhí)行＝，逐漸減少，判斷是否滿足迭代終止條件，若滿足，則終止尋優(yōu)，輸出當前解為最優(yōu)解；否則轉(zhuǎn)步驟2．

3?任務分配求解

3.1?粒子編碼方式

3.2?退火機制的改進

SA算法雖然適合求解復雜約束的組合優(yōu)化問題，但算法收斂速度慢．在退火迭代過程中，溫度是關于溫度衰減因子線性衰減的，若溫度衰減因子設置過小，算法迭代后期收斂速度變快，但是迭代前期尋優(yōu)性能變差；若溫度衰減因子設置過大，算法迭代前期尋優(yōu)效果好，但是迭代后期收斂速度變慢．

在退火過程中，為使算法收斂速度更快，采用動態(tài)溫度衰減因子．溫度衰減因子與迭代次數(shù)的函數(shù)關系表示為

?????(14)

式中為總迭代次數(shù)，其關系曲線如圖1所示．

圖1?溫度衰減因子r與迭代次數(shù)k關系曲線

3.3?DPSO-GT-SA算法

對于大規(guī)模UCAV協(xié)同任務分配問題，將DPSO算法、GT算法和SA算法相結(jié)合，提出DPSO-GT-SA算法．通過向具有全局極值和局部極值的粒子學習，提高了DPSO算法的尋優(yōu)效率；通過向隨機粒子學習，粒子能夠在更大的解空間中尋優(yōu)．為了克服算法直接向個體最優(yōu)值學習易引起早熟收斂的缺點，采用局部最優(yōu)子群的概念，使得粒子向局部最優(yōu)子群中的粒子學習而不是向個體最優(yōu)學習[17]．因此，學習粒子對象的選擇包括3個部分：全局最優(yōu)粒子、局部最優(yōu)子群粒子和隨機選擇粒子．為了完成上述學習進化過程，引入學習因子，用于確定學習選擇概率；引入局部最優(yōu)子群比，用于確定局部最優(yōu)子群的規(guī)模；引入迭代次數(shù)閾值，用于確定當前粒子何時向全局最優(yōu)粒子學習．

在每個粒子的速度和位置更新后加入SA算法，對進化后的粒子按Metropolis準則接受優(yōu)化解，同時以一定概率接受差的解，使粒子能夠跳出局部極值.

DPSO-GT-SA算法基本流程如圖2所示，具體步驟如下。

步驟2?適應度值計算．根據(jù)粒子計算適應度值并完成更新．

步驟3?對種群中粒子的最優(yōu)解排序，確定局部最優(yōu)子群．并確定每次迭代的相關參數(shù)．

步驟4?對每個粒子進行SA鄰域搜索，并產(chǎn)生新的粒子．

(3) 變異操作．執(zhí)行變異操作時，從當前粒子中隨機選擇兩個基因，將基因間的子序列進行倒置．

步驟5?計算新粒子的適應度值，如果優(yōu)于學習前的適應度值，則更新該粒子；否則按Metropolis準則判斷是否接受當前粒子．

步驟6?判斷是否達到SA過程迭代次數(shù)：如未到達，則跳轉(zhuǎn)到步驟4，循環(huán)執(zhí)行；否則重新排序確定局部最優(yōu)子群，并更新各個粒子的局部最優(yōu)值和種群的全局最優(yōu)值．

步驟7?判斷當前迭代次數(shù)是否達到總迭代次數(shù)：如未達到，跳轉(zhuǎn)到步驟2，循環(huán)執(zhí)行；否則終止尋優(yōu)，輸出全局最優(yōu)粒子．

圖2?DPSO-GT-SA算法流程

(15)

4?仿真與分析

為驗證設計優(yōu)化算法的性能，在Windows10操作系統(tǒng)上，基于Matlab2014a環(huán)境實現(xiàn)算法的仿真實驗．PC機配置為Intel(R)Core i5-6500 @3.2,GHz處理器，4,G內(nèi)存．

4.1?仿真實驗數(shù)據(jù)

圖4?戰(zhàn)場環(huán)境分布

表2?UCAV性能參數(shù)

Tab.2?UCAV performance parameters

表3?任務性能參數(shù)

Tab.3?Task performance parameters

為簡化類型約束，表2中，設置類型1為可執(zhí)行電子干擾和攻擊任務的UCAV，類型2為可執(zhí)行偵查和電子干擾任務的UCAV，類型3為可執(zhí)行偵查和攻擊任務的UCAV，類型0為可執(zhí)行這3種任務的UCAV．UCAV作戰(zhàn)防御能力等相關性能參考表3設置，由于100個UCAV性能數(shù)據(jù)過大，這里不再贅述．表3中，任務類型1為偵查任務，類型2為攻擊任務，類型3為電子干擾任務．

4.2?不同算法仿真比較分析

為驗證改進SA算法中動態(tài)溫度衰減因子對求解過程影響，分別在DPSO-GT-SA算法中加入動態(tài)與靜態(tài)溫度衰減因子，其迭代過程如圖5所示．從圖5可以看出，加入動態(tài)溫度衰減因子的DPSO-GT-SA算法在迭代中期就已經(jīng)收斂，相比加入靜態(tài)溫度衰減因子的DPSO-GT-SA算法的收斂效果更好，具體細節(jié)可以參考圖5(b)．

圖5?動態(tài)和靜態(tài)溫度衰減因子迭代過程

圖6分別給出模擬退火-遺傳(SA-GA)算法[22]、DPSO-GT算法和DPSO-GT-SA算法求解任務分配的適應度值變化曲線．由于SA算法自身機制影響，SA-GA算法后期收斂速度慢．相比SA-GA算法和DPSO-GT算法，DPSO-GT-SA算法收斂速度更快，尋優(yōu)效果更好．

圖7和圖8分別給出DPSO-GT算法和DPSO-GT-SA算法進行100次蒙特卡洛仿真過程中適應度最佳值、適應度最差值以及適應度平均值的情況，其仿真結(jié)果如表4所示．

圖6?3種算法迭代過程對比

圖7?DPSO-GT蒙特卡洛仿真結(jié)果

圖8?DPSO-GT-SA蒙特卡洛仿真結(jié)果

表4?兩種算法性能比較

Tab.4?Performance comparison between two algorithms

由表4可以看出，相比DPSO-GT算法，DPSO-GT-SA算法3種適應度值都要好，平均運行時間更快.其中，DPSO-GT-SA算法適應度平均值要比DPSO-GT算法高8.59%，表明改進算法在迭代過程中有利于粒子跳出局部最優(yōu)值，驗證了算法的有效性.

采用DPSO-GT-SA算法，大規(guī)模UCAV任務分配優(yōu)化結(jié)果如表5所示．

表5?任務分配優(yōu)化結(jié)果

Tab.5?Optimization results of task allocation

4.3?參數(shù)對算法影響仿真分析

為驗證所設計算法中粒子數(shù)、迭代次數(shù)的選取對于算法性能的影響．分別針對不同粒子數(shù)和不同迭代次數(shù)進行仿真，仿真結(jié)果如表6和表7所示，表6中除粒子數(shù)其他參數(shù)同第4.1節(jié)所述，表7同理．將表6和表7中數(shù)據(jù)進行擬合，繪制適應度平均值和運行時間隨粒子數(shù)以及迭代次數(shù)變化曲線，如圖9所示．由圖9(a)和(c)可知，設計算法的平均適應度值隨粒子數(shù)以及迭代次數(shù)先快速變化后緩慢變化至一個定值；由圖9(b)和(d)可知，設計算法的運行時間隨粒子數(shù)以及迭代次數(shù)都近似線性變化．

表6?不同粒子數(shù)目實驗結(jié)果

Tab.6 Experimental results with different particles

粒子數(shù)目運行時間/s適應度值 40134-36 80266-28 120405-25 160562-24 200723-23 250865-23 3001,0331,-23

表7?不同迭代次數(shù)實驗結(jié)果

Tab.7 Experimental resultswith different iterations

迭代次數(shù)運行時間/s適應度值 100064-34 200132-30 300197-28 400272-27 500319-26 600407-26 700478-26

圖9?粒子數(shù)與迭代次數(shù)對算法的影響

5?結(jié)?語

本文首先建立大規(guī)模UCAV任務分配模型，采用DPSO-GT-SA算法進行求解．對于求解復雜約束大規(guī)模UCAV任務分配問題，DPSO-GT算法易陷入局部最優(yōu)，引入SA算法，利用SA算法中Metropolis準則依概率接受差的解，使算法能夠跳出局部極值．對于加入SA算法后期收斂速度慢的問題，提出帶動態(tài)溫度衰減因子DPSO-GT-SA算法．仿真結(jié)果表明，對于大規(guī)模任務分配問題，相比SA-GA算法以及原DPSO-GT算法，加入帶有動態(tài)溫度衰減因子DPSO-GT-SA算法收斂速度更快，尋優(yōu)效果更好．

［1］ 尹高揚，周紹磊，賀鵬程，等. 國外多無人機協(xié)同任務分配研究現(xiàn)狀及發(fā)展趨勢[J]. 飛航導彈，2016(5)：54-58.

Yin Gaoyang，Zhou Shaolei，He Pengcheng，et al. Research status and development trend of cooperative task allocation for multiple UAVs in foreign countries[J].，2016(5)：54-58(in Chinese).

［2］ Tsiogkas N，Saigol Z，Lane D. Distributed multi-AUV cooperation methods for underwater archaeology[C]//Genova，Italy，2015：1-5.

［3］ Li J T，Zhang S，Zheng Z，et al. Research on multi-UAV loading multi-type sensors cooperative reconnaissance task planning based on genetic algorithm[C]//Liverpool，UK，2017：485-500.

［4］ Hojda M. Comparison of algorithms for constrained multi-robot task allocation[J].，2017，539：255-264.

［5］ 萬路軍，姚佩陽，稅冬東，等. 多編組任務分配動態(tài)優(yōu)化模型及IVFSA算法求解[J]. 電光與控制，2014，21(5)：43-49.

Wan Lujun，Yao Peiyang，Shui Dongdong，et al. Dynamic task allocation methods in multiple groups using IVFSA[J].，2014，21(5)：43-49(in Chinese).

［6］ 顏?驥，李相民，劉?波，等. 基于MILP的多無人機對敵防空火力壓制[J]. 海軍航空工程學院學報，2014，29(4)：369-373.

Yan Ji，Li Xiangmin，Liu Bo，et al. Multi UAV suppression of on enemy air defense based on MILP[J].，2014，29(4)：369-373(in Chinese).

［7］ Zhu X，Sim K M，Jiang J，et al. Agent-based dynamic scheduling for earth-observing tasks on multiple airships in emergency[J].，2017，10(2)：661-672.

［8］ Lee D H，Zaheer S A，Kim J H. A resource-oriented，decentralized auction algorithm for multi-robot task allocation[J].，2015，12(4)：1469-1481.

［9］ 毛紅保，田?松，晁愛農(nóng)，等. 無人機任務規(guī)劃[M]. 北京：國防工業(yè)出版社，2015.

Mao Hongbao，Tian Song，Chao Ainong，et al.[M]. Beijing：National Defense Industry Press，2015(in Chinese).

［10］ Kennedy J，Eberhart R C. A discrete binary version of the particle swarm algorithm[C]//，，. Orlando，USA，1997，5(5)：4104-4108.

［11］ Chen E，Li J，Liu X. In search of the essential binary discrete particle swarm[J].，2011，11(3)：3260-3269.

［12］ Ktari R，Chabchoub H. Essential particle swarm optimization queen with Tabu search for MKP resolution[J].，2013，95(9)：897-921.

［13］ Kumar N，Vidyarthi D P. A novel hybrid PSO-GA meta-heuristic for scheduling of DAG with communication on multiprocessor systems[J].，2016，32(1)：35-47.

［14］ Haddar B，Khemakhem M，Rhimi H，et al. A quantum particle swarm optimization for the 0-1 generalized knapsack sharing problem[J].，2016，15(1)：153-164.

［15］ López L F M，Blas N G，Albert A A. Multidimensional knapsack problem optimization using a binary particle swarm model with genetic operations[J].，2018，22(8)：2567-2582.

［16］ Guo T，Michalewicz Z. Inver-over operator for the TSP[C]//Heidelberg，Germany，1998：803-812.

［17］ 鄭東亮，薛云燦，楊啟文，等. 基于Inver-over算子的改進離散粒子群優(yōu)化算法[J]. 模式識別與人工智能，2010，23(1)：97-102.

Zheng Dongliang，Xue Yuncan，Yang Qiwen，et al. Modified discrete particle swarm optimization algorithm based on inver-over operator[J].，2010，23(1)：97-102(in Chinese).

［18］ 顏?驥，李相民，劉?波. 應用離散粒子群-郭濤算法分配多無人機協(xié)同任務[J]. 國防科技大學學報，2015，37(4)：165-171.

Yan Ji，Li Xiangmin，Liu Bo. Cooperative task allocation of multi-UAVs with mixed DPSO-GT algorithm[J].，2015，37(4)：165-171(in Chinese).

［19］ 李?儼，董玉娜. 基于SA-DPSO混合優(yōu)化算法的協(xié)同空戰(zhàn)火力分配[J]. 航空學報，2010，31(3)：626-631.

Li Yan，Dong Yuna. Weapon-target assignment based on simulated annealing and discrete particle swarm optimization in cooperative air combat[J].，2010，31(3)：626-631(in Chinese).

［20］ Kirkpatrick S，Gelatt C D，Vecchi M P. Optimization by simulated annealing[J].，1983，220(4598)：671-680.

［21］ Jiang J，Liu H，F(xiàn)eng H，et al. Embedded static task allocation and scheduling based on simulated annealing and genetic algorithm[J].，2014，10(4)：1465-1472.

［22］ 羅德林，吳順祥，段海濱，等. 無人機協(xié)同多目標攻擊空戰(zhàn)決策研究[J]. 系統(tǒng)仿真學報，2008，20(24)：6778-6782.

Luo Delin，Wu Shunxiang，Duan Haibin，et al. Air-combat decision-making for UAVs cooperatively attacking multiple targets[J].，2008，20(24)：6778-6782(in Chinese).

(責任編輯：孫立華)

Cooperative Task Allocation of Large-Scale UCAV Based on DPSO-GT-SA Algorithm

Zong Qun，Qin Xinli，Zhang Boyuan，Tian Bailing，Wang Dandan

(School of Electrical and Information Engineering，Tianjin University，Tianjin 300072，China)

Task allocation of unmanned combat aircraft vehicle(UCAV)is the key to UCAV formation flying campaign．An improved discrete particle swarm optimization(IDPSO)algorithm is proposed for large-scale UCAV cooperative task allocation in complex constraint environment．According to the existing multi-UCAV formation saturation combat mode of air to ground，the multiple UCAV formation task allocation model in combat environment is established．Discrete particle-GuoTao-simulated annealing(DPSO-GT-SA)algorithm is used to solve the problem. According to the particle coding method，the mapping between the UCAV，the target and the particle is established．The exploitation and exploration are based on crossover and mutation of particles，and the local optimum is jumped out by Metropolis criterion of simulated annealing．In order to solve the problem that the DPSO-GT algorithm falls into local minimum，the improved simulated annealing is introduced．As to the problem of slow convergence at the later stage of simulated annealing，a dynamic temperature attenuation factor in DPSO-GT-SA algorithm is proposed．The simulation results show that the improved discrete particle swarm optimization algorithm can better solve the large-scale UCAV cooperative task allocation problem.

large-scale UCAV；cooperative task allocation；improved discrete particle swarm optimization(IDPSO)；simulated annealing

the National Natural Science Foundation of China(No.,6167020850 and No.,61573060)．

TP242

A

0493-2137(2018)10-1005-10

10.11784/tdxbz201711069

2017-11-19；

2018-03-30.

宗?群（1961—??），男，教授，zongqun@tju.edu.cn.

秦新立，xlqin@tju.edu.cn.

國家自然科學基金資助項目(6167020850，61573060).