火力分配多目標(biāo)優(yōu)化的IBACO算法

肖中暉，寇英信，李戰(zhàn)武，徐 安

（空軍工程大學(xué)航空航天工程學(xué)院，西安 710038）

火力分配多目標(biāo)優(yōu)化的IBACO算法

肖中暉，寇英信，李戰(zhàn)武，徐 安

（空軍工程大學(xué)航空航天工程學(xué)院，西安 710038）

應(yīng)用蟻群優(yōu)化算法（Ant Colony Optimization）求解多目標(biāo)優(yōu)化問題已經(jīng)引起廣泛關(guān)注，多目標(biāo)火力分配問題的目標(biāo)是求出一個合適的武器目標(biāo)分配方案，使?jié)M足決策需要。建立了多目標(biāo)火力分配的數(shù)學(xué)模型，提出一種基于指標(biāo)的蟻群優(yōu)化算法Indicator-Based Ant Colony Optimization），給出了算法的具體步驟。IBACO的核心思想是利用二元性能指標(biāo)來引導(dǎo)人工螞蟻進(jìn)行搜索，由于該算法中的信息素是根據(jù)指標(biāo)的值來更新的，通過獎勵信息素可以強(qiáng)化最優(yōu)解。仿真實驗證明了該算法的有效性，在解決火力分配問題上，所提算法和蟻群優(yōu)化算法相比具有較好的收斂性。

火力分配，二元指標(biāo)優(yōu)化，多目標(biāo)蟻群優(yōu)化

0 引言

火力分配問題，也稱武器目標(biāo)分配（Weapon Target Assignment，WTA）問題，是一個典型的優(yōu)化問題，需將武器根據(jù)目標(biāo)進(jìn)行合理分配，從而達(dá)到作戰(zhàn)意圖。應(yīng)用智能算法求解火力分配單目標(biāo)優(yōu)化問題目前有很多研究，如蟻群算法［2］、遺傳算法［3］、混合算法［4］等。

相對于單目標(biāo)優(yōu)化火力分配而言，多目標(biāo)優(yōu)化能夠同時綜合考慮并優(yōu)化多個目標(biāo)，使其同時達(dá)到綜合的最優(yōu)值，更符合決策者的需求。在實際問題中，由于多個目標(biāo)之間存在沖突，多目標(biāo)優(yōu)化問題往往不存在一個最優(yōu)解而應(yīng)存在一個解的集合，當(dāng)考慮所有目標(biāo)時，在這個集合中的解優(yōu)于其他解，這個解的集合稱為Pareto解集或者非支配解。

文獻(xiàn)［1］提出一種基于指標(biāo)的進(jìn)化算法，但指標(biāo)被用來排除最差解，而不是強(qiáng)化最優(yōu)解；文獻(xiàn)［2］對多個目標(biāo)定義信息素更新規(guī)則，并不能直接反映解的好壞；文獻(xiàn)［7］采用基于分解的多目標(biāo)進(jìn)化算法，并設(shè)計了不可行解修復(fù)方法，但該算法收斂速度低，只對小規(guī)模的火力分配案例進(jìn)行測試。

針對以上問題，提出一種采用二元性能指標(biāo)的蟻群優(yōu)化算法，利用這些指標(biāo)對每個Pareto近似解給出一個反映解的好壞的值，重新定義路徑上的信息素，從而引導(dǎo)螞蟻搜索。傳統(tǒng)的基于指標(biāo)的方法往往排除最差解，而在本文提出的方法中，指標(biāo)被用來強(qiáng)化最優(yōu)解。

1 多目標(biāo)火力分配優(yōu)化問題

1.1 火力分配問題描述

假設(shè)使用m個武器攻擊n個目標(biāo)，且m≥n，武器i攻擊j目標(biāo)的毀傷概率為表示武器的有效性，表示導(dǎo)彈命中概率；毀傷j目標(biāo)的收益為，設(shè)允許多個武器攻擊同一個目標(biāo)，使用武器i攻擊j目標(biāo)后目標(biāo)生存概率為，所有攻擊結(jié)束后，j目標(biāo)的毀傷概率為表示將武器i分配給目標(biāo)j的數(shù)目，如果導(dǎo)彈i打擊目標(biāo)j，那么xij=1；如果導(dǎo)彈i沒有打擊目標(biāo)j，那么xij=0。獲得的總收益為?；鹆Ψ峙涞膬?yōu)化問題的目標(biāo)函數(shù)通常是打擊敵方獲得的總收益最大。

1.2 多目標(biāo)優(yōu)化數(shù)學(xué)模型

提出讓所使用武器成本最小作為第2個目標(biāo)函數(shù)。假設(shè)i型武器的成本為ci，則攻擊總成本為。因此，多目標(biāo)火力分配優(yōu)化問題可定義為：

2 二元性能指標(biāo)

定義1 二元性能指標(biāo)

表示該二元指標(biāo)服從Pareto規(guī)則。

文獻(xiàn)［1］提出基于指標(biāo)的進(jìn)化算法（Indicator-Based Evolutionary Algorithm，IBEA），利用性能指標(biāo)將適應(yīng)度值最差的個體刪除，剩余個體的適應(yīng)度值更新。在IBEA中，測試了兩種指標(biāo)：epsilon指標(biāo)Iε和hypervolume指標(biāo)IHD，本文只測試指標(biāo) Iε。表示使x1支配x2所需移動的最小值。當(dāng)x1支配x2時，Iε為負(fù)值。

3 IBACO算法描述

IBACO算法的基本思想是利用基于指標(biāo)的方法引導(dǎo)螞蟻進(jìn)行搜索找到Pareto近似解，在該算法中只有Pareto解能夠釋放信息素。在算法的每個循環(huán)中，每個螞蟻構(gòu)建一個解，一旦構(gòu)建過程結(jié)束，進(jìn)行適應(yīng)度分配并采用二元指標(biāo)更新Pareto解集，信息素根據(jù)適應(yīng)度值更新。當(dāng)達(dá)到最大循環(huán)數(shù)時，算法終止。

3.1 解的構(gòu)建

為了用蟻群優(yōu)化算法求解火力分配問題，火力分配問題可以表示為二分圖G=（V，U，E）。V表示n個目標(biāo)，U表示m個武器，E是連接目標(biāo)節(jié)點和武器節(jié)點的邊。二分圖的多個邊組成的一條路徑，表示火力分配的一種分配方案，構(gòu)建火力分配問題的解就是求二分圖的路徑。

圖1 WTA問題二分圖

在構(gòu)建解的過程中，每個螞蟻從可分配的武器目標(biāo)集合Cand中構(gòu)建各自的武器目標(biāo)分配方案Sant，一旦選擇了一個武器或者目標(biāo)，集合Cand必須更新。

構(gòu)建解的步驟如下：

步驟1：初始化，螞蟻隨機(jī)選擇初始點。

步驟2：下一節(jié)點的選擇。螞蟻由武器i以概率Pij轉(zhuǎn)移到目標(biāo)j，在火力分配問題中，存在每個目標(biāo)允許分配的武器限制的問題，所以螞蟻在由武器i轉(zhuǎn)移到目標(biāo)j時需要檢查目標(biāo)j已分配武器數(shù)目是否已達(dá)到限制。若已達(dá)到限制，螞蟻在該目標(biāo)點不能移向武器點，只能移向目標(biāo)點，否則隨機(jī)移向另一個點。此外，螞蟻位于一個已被分配的武器點上時，只能移向未被分配的武器點。這兩條規(guī)則分別對應(yīng)于模型的兩個約束。

概率Pij定義為：

其中：α、β是決定信息素因子ij與啟發(fā)信息因子ηij相對重要程度的參數(shù)。與真實螞蟻不同，人造螞蟻在分配武器給不同目標(biāo)時，納入啟發(fā)信息。

步驟3：更新Cand，根據(jù)約束條件刪除已被分配的武器和已到達(dá)分配武器數(shù)目限制的目標(biāo)，回到步驟2，當(dāng)Cand=0時終止。

3.2 啟發(fā)信息

多目標(biāo)優(yōu)化的啟發(fā)信息是單目標(biāo)優(yōu)化啟發(fā)信息的聚合，考慮打擊敵方獲得的總收益最大和使用武器的成本最小為目標(biāo)函數(shù)，那么啟發(fā)信息可定義為打擊敵方收益與成本的比：

3.3 適應(yīng)度分配

適應(yīng)度分配是指利用二元性能指標(biāo)將得到的解根據(jù)各自的性能進(jìn)行排序，也就是說，最優(yōu)解的適應(yīng)度值越大。在IBACO中，適應(yīng)度分配只在Pareto中進(jìn)行，表明其關(guān)于其他解的關(guān)系。為評價解x1在整個種群的性能，學(xué)者們提出不同的適應(yīng)度分配方法。其中一個方法就是將剩余種群的性能指標(biāo)求和。

為了強(qiáng)調(diào)支配解對非支配解的影響，采用另一種適應(yīng)度分配方法：

其中：κ是比例縮放因子。

3.4 信息素更新規(guī)則

當(dāng)Pareto解集中的螞蟻選擇一個武器或目標(biāo)點以后，通過信息素更新規(guī)則來更新武器i到目標(biāo)j路徑上的信息素。

其中ρ為信息素?fù)]發(fā)系數(shù)，且0＜ρ＜1。

如果解Sant支配解Sant，指標(biāo)的值為負(fù)，當(dāng)給指標(biāo)分配負(fù)值時，適應(yīng)度值越大。因此，支配解的適應(yīng)度值比被支配解的適應(yīng)度值大。為了引導(dǎo)螞蟻搜尋，IBACO算法中，信息素只獎勵Pareto解集中的解。在信息素更新過程中，根據(jù)分配的適應(yīng)度值，最優(yōu)解的信息素最高，被螞蟻選擇的概率將會更大。

算法流程如下：

步驟1 初始化信息素init；

步驟2 對每個螞蟻從ant=1到NbAnts構(gòu)建一個解Sant；

步驟3 計算解的適應(yīng)度值；

步驟4 更新Pareto解集P，篩選非支配解；

步驟5 更新信息素；

步驟6 當(dāng)最大循環(huán)數(shù)達(dá)到時終止，否則回到步驟2。

4 仿真分析

假設(shè)有12個武器和10個目標(biāo)，對每個目標(biāo)分配的最大武器數(shù)a取3。模型的參數(shù)設(shè)定為如下：

表1 目標(biāo)價值uj取值

表2 武器的有效性qij取值

表3 武器命中概率ρk取值

表4 武器成本ci取值

4.1 Pareto前沿

圖2 Pareto前沿

圖2所示用改進(jìn)的IBACO算法求解多目標(biāo)火力分配模型得到的解集和真實的Pareto解，該算法求得的解包含了Pareto解，表明了算法求解Pareto解的有效性。每個Pareto解對應(yīng)的函數(shù)值以及分配方案如表5所示。

4.2 算法收斂性分析

求解多目標(biāo)火力分配問題就是找到近似最優(yōu)解，在實際應(yīng)用中，根據(jù)作戰(zhàn)指揮以及作戰(zhàn)需求從中選出實時的方案，因此，算法的收斂性應(yīng)滿足實際需求。圖3和圖4分別為兩種算法單獨求解f1和f2的收斂情況。本文提出的算法與ACO相比，指標(biāo)改進(jìn)了適應(yīng)度分配規(guī)則，提高了支配解路徑上的信息素濃度，最優(yōu)解的信息素濃度最高，螞蟻選擇最優(yōu)解的概率越大，從而提高了搜索的效率，因此，能更快得到單個目標(biāo)函數(shù)的最優(yōu)解。

圖3 第1目標(biāo)函數(shù)與迭代次數(shù)的關(guān)系

圖4 第2目標(biāo)函數(shù)與迭代次數(shù)的關(guān)系

5 結(jié)論

首先，綜合考慮攻擊的收益和消耗，建立了火力分配的數(shù)學(xué)模型；其次，提出了一種求解火力分配問題的基于指標(biāo)的蟻群優(yōu)化算法——IBACO，該算法利用IBEA算法提出的二元性能指標(biāo)進(jìn)行優(yōu)化，通過指標(biāo)和適應(yīng)度分配函數(shù)改變路徑上信息素的濃度，從而引導(dǎo)螞蟻搜索；最后，通過火力分配的仿真表明了IBACO求解該問題的有效性以及收斂速度明顯優(yōu)于蟻群優(yōu)化算法。

本文只研究了靜態(tài)目標(biāo)分配問題，下一步將考慮作戰(zhàn)時間對模型的影響，研究動態(tài)目標(biāo)分配的模型和求解方法。

表5 Pareto前沿函數(shù)值及對應(yīng)分配方案

［1］ZITZLER E，KVNZLI S.Indicator-based selection in multi-objective search［C］//8th International Conference on Parallel Problem Solving from Nature，2004:832-842.

［2］MCMULLEN M P R.An ant colony optimization approach to addressing a JIT sequencing problem with multiple objectives［J］.Artificial Intelligence in Engineering，2001，15（3）:309-317.

［3］BOGDANOWICZ Z R.Advanced input generating algorithm for effect-based weapon-target pairing optimization［J］.IEEE Transaction on System，Man，and Cybernetics-Part B:Cybernetics，2012，42（1）:276-280.

［4］ LEE Z J，SU S F，LEE C Y.Efficiently solving general weapon-target assignment problem by genetic algorithms with greedy eugenics［J］.IEEE Transaction on System，Man，and Cybernetics-Part B:Cybernetics，2003，33（1）:113-121.

［5］CHAHARSOOGHI S K，AMIR H.KERMANI M.An effective ant colony optimization algorithm（ACO）for multi-objective resource allocation problem （MORAP）［J］.Applied Mathematics and Computation，2008（200）:167-177.

［6］WANG J，GAO X G，ZHU Y W.Solving algorithm for TA optimization model based on ACO-SA ［J］.Journal of Systems Engineering and Electronics，2011，22（4）:628-639.

［7］LI J，CHEN J，XIN B.Solving multi-objective multi-stage weapon target assignment problem via adaptive NSGAII and adaptive MOEA/D:a comparison study［C］//Congress on Evolutionary Computation，IEEE，2015:3132-3139.

［8］張瀅，楊任農(nóng)，左家亮，等.基于分解進(jìn)化多目標(biāo)優(yōu)化算法的火力分配問題［J］.系統(tǒng)工程與電子技術(shù)，2014，36（12）:2435-2441.

［9］劉曉，劉忠，侯文姝，等.火力分配多目標(biāo)規(guī)劃模型的改進(jìn)MOPSO 算法 ［J］. 系統(tǒng)工程與電子技術(shù)，2013，35（2）:326-330.

［10］王喆.蟻群算法及其在火力分配問題中的應(yīng)用［J］.火力與指揮控制，2009，34（11）:92-94.

Indicator Based Ant Colony Optimization for Multi-objective WTA Problem

XIAO Zhong-hui,KOU Ying-xin,LI Zhan-wu,XU An
（Engineering College of Aeronautics and Astronautics,Air Force Engineering University,Xi’an 710038，China）

The use of Ant Colony Optimization to solve multi-objective problems is a very active research topic.The Weapon-Target Assignment （WTA） problem aims at seeking for a proper assignment of weapons to targets to meet the decision-making requirements.A mathematic model on weapon-target assignment is formulated at first.Then,an indicator-based ant colony Optimization algorithm called IBACO for the multi-objective weapon-target assignment problem is proposed.The description and the process of IBACO proposed are given.The IBACO algorithm proposes a new idea that uses binary quality indicators to guide the search of artificial ants for that the pheromone information is defined relatively to the indicator values.In this paper,we use the indicator optimization to reinforce the best solutions by rewarding pheromone trails.Simulation results show the effectiveness of the algorithm proposed in the paper as well as better convergence performance compared with ACO.

weapon-target assignment，binary-indicator optimization，multi-objective ant colony optimization

E844；TJ760

A

10.3969/j.issn.1002-0640.2017.07.036

1002-0640（2017）07-0165-05

2016-05-08

2016-06-17

肖中暉（1994- ），男，江蘇鹽城人，碩士研究生。研究方向：航空武器火力控制原理與技術(shù)。