張凱，周德云，潘潛

西北工業(yè)大學(xué)電子信息學(xué)院，西安 710129

基于混合蛙跳算法的協(xié)同空戰(zhàn)火力分配

張凱，周德云，潘潛

西北工業(yè)大學(xué)電子信息學(xué)院，西安 710129

針對(duì)超視距多機(jī)協(xié)同空戰(zhàn)中的火力分配（WTA）問(wèn)題，建立了協(xié)同空戰(zhàn)火力分配的數(shù)學(xué)模型，提出了采用混合蛙跳算法（SFLA）來(lái)求解協(xié)同空戰(zhàn)火力分配問(wèn)題，根據(jù)無(wú)約束化的編碼方式，結(jié)合交叉、變異的遺傳操作，提高了算法的收斂速度以及全局搜索能力，能有效避免陷入局部最優(yōu)。仿真結(jié)果表明，所提出的混合蛙跳算法在解決協(xié)同空戰(zhàn)火力分配問(wèn)題中具有高效可行性。

協(xié)同空戰(zhàn)；火力分配；混合蛙跳算法；遺傳算子

1 引言

隨著機(jī)載火控系統(tǒng)的快速發(fā)展，超視距協(xié)同空戰(zhàn)已成為現(xiàn)代空戰(zhàn)的主要形式，火力分配作為必不可少的決策支持，一直是研究的熱點(diǎn)[1]。Lloyd和W itsenhausen已證明了WTA問(wèn)題是NP完全問(wèn)題[2]，針對(duì)該問(wèn)題，目前已有多種算法，如拍賣(mài)算法[3]、混合粒子群算法[4-6]、蟻群算法[7-8]、遺傳算法[9]等，以上算法均已應(yīng)用于火力分配并取得顯著的成果。

在以上研究的基礎(chǔ)上，本文提出了一種混合蛙跳算法求解協(xié)同多目標(biāo)空戰(zhàn)決策問(wèn)題。作為一種新的仿生學(xué)智能優(yōu)化算法，蛙跳算法結(jié)合了基于模因進(jìn)化的模因演算法（M emetic A lgorithm，MA）和基于群體行為的粒子群算法（Particle Swam optimization，PSO）的優(yōu)點(diǎn)，調(diào)整參數(shù)少，收斂速度快，全局尋優(yōu)能力強(qiáng)[10]。仿真結(jié)果表明了該算法在解決協(xié)同多目標(biāo)空戰(zhàn)決策問(wèn)題中的有效性。

2 協(xié)同空戰(zhàn)火力分配數(shù)學(xué)模型

設(shè)在多機(jī)系統(tǒng)攻擊多目標(biāo)的超視距空戰(zhàn)中，我方的空戰(zhàn)編隊(duì)有n架飛機(jī)，每架飛機(jī)載有ki枚導(dǎo)彈，共有k1+k2+…+kn=k枚導(dǎo)彈；所要攻擊的敵機(jī)數(shù)目為m架，每架敵機(jī)的威脅系數(shù)為ωh，h=1，2，…，m。其中第i枚導(dǎo)彈對(duì)第j架敵機(jī)的毀傷概率為pij，i=1，2，…，k，j=1，2，…，m。

引入火力分配的決策矩陣[11]：

xij為決策變量，xij=1表示分配了第i枚導(dǎo)彈攻擊第j架敵機(jī)，否則xij=0。

則協(xié)同空戰(zhàn)火力分配數(shù)學(xué)模型可描述為：尋求一組解X，滿足以下目標(biāo)函數(shù)和約束條件：

目標(biāo)函數(shù)：

其中，第一個(gè)約束條件表示一枚導(dǎo)彈只能用于打擊一個(gè)目標(biāo)，第二個(gè)約束條件表示所能使用的導(dǎo)彈數(shù)量不超過(guò)k個(gè)。

3 蛙跳算法

蛙跳算法（Shuffled Frog Leaping A lgorithm，SFLA）由Eusuff和Lansey為解決組合優(yōu)化問(wèn)題于2003年提出[12]，作為一種新的仿生學(xué)智能優(yōu)化算法，該算法具有調(diào)整參數(shù)少、收斂速度快、有效避免局部最優(yōu)解的特點(diǎn)。目前混合蛙跳算法主要應(yīng)用于解決多目標(biāo)優(yōu)化問(wèn)題，如資源分配、作業(yè)調(diào)度、流程安排等工程實(shí)際應(yīng)用問(wèn)題[13-14]。

作為一種后啟發(fā)式群體進(jìn)化算法，蛙跳算法的思想是：濕地中的一群青蛙通過(guò)尋找不同的石頭進(jìn)行跳躍去找到食物較多的地方。青蛙具有自己的文化，每只青蛙的文化被定義為問(wèn)題的一個(gè)解，個(gè)體之間通過(guò)文化的交流實(shí)現(xiàn)信息的交換。濕地的整個(gè)青蛙群體被分為不同的子群體，在子群體中的每個(gè)個(gè)體通過(guò)自己的文化影響著其他個(gè)體，也受其他個(gè)體的影響，并隨著子群體的進(jìn)化而進(jìn)化，執(zhí)行局部搜索策略。當(dāng)子群體進(jìn)化到一定階段以后，各子群體之間再進(jìn)行文化的交流實(shí)現(xiàn)子群體間的混合運(yùn)算。重復(fù)上述過(guò)程，直到滿足設(shè)置的截止條件為止。

SFLA算法的數(shù)學(xué)模型可以表示為：首先，隨機(jī)初始化生成解空間為S維、規(guī)模為N的初始種群P= {X1，X2，…，XN}，第i只蛙表示問(wèn)題的一個(gè)解Xi=[xi1，xi2，…，xiS]。將初始種群中蛙的個(gè)體按適應(yīng)值降序排列，并將種群中具有最優(yōu)適應(yīng)值的個(gè)體記為Xg。然后將整個(gè)種群分為m個(gè)模因組，每個(gè)模因組含有n只蛙，即N=n×m，分配方法為：第1只蛙分入第1模因組，第2只蛙分入第2模因組，…，第m只蛙分入第m模因組，第m+1只蛙分入第1模因組，…，依次類推。第k個(gè)模因組的蛙的集合Ak可表示為[15]：

將每個(gè)模因組中的最優(yōu)適應(yīng)值個(gè)體和最劣適應(yīng)值個(gè)體記為Xb、Xw，然后在每個(gè)模因組中根據(jù)蛙跳規(guī)則執(zhí)行局部搜索策略：

式中，rand()表示（0，1）之間的隨機(jī)數(shù)，Dmax表示蛙每次跳躍步長(zhǎng)的最大值。在經(jīng)過(guò)更新后，如果得到的優(yōu)于原來(lái)的Xw，則取代原模因組中的Xw；如果沒(méi)有改進(jìn)，則用Xg取代Xb，再按式（5）與式（6）執(zhí)行局部搜索過(guò)程，如果仍沒(méi)有改進(jìn)，則隨機(jī)產(chǎn)生一個(gè)新蛙直接取代原Xw。重復(fù)上述局部搜索過(guò)程iN次，然后將整個(gè)蛙群重新混合并排序和劃分基因組，再進(jìn)行局部搜索，如此反復(fù)，直到滿足設(shè)定的截止條件為止，如適應(yīng)度達(dá)到期望值或達(dá)到混合迭代次數(shù)im。

4 求解火力分配問(wèn)題的混合SFLA算法

協(xié)同多目標(biāo)空戰(zhàn)火力分配的數(shù)學(xué)模型作為帶有一定約束條件的非線性0-1整數(shù)規(guī)劃問(wèn)題，若按基本SFLA算法來(lái)求解，其步長(zhǎng)的速度向量難以表達(dá)。故本文在一種無(wú)約束化的編碼方式上，借鑒遺傳算法的交叉、變異思想，采用遺傳-蛙跳混合算法來(lái)解決空戰(zhàn)火力分配問(wèn)題。

4.1 解的編碼

在混合SFLA算法中，對(duì)解的位置需要結(jié)合實(shí)際問(wèn)題進(jìn)行編碼。本文采用了一種基于實(shí)數(shù)的編碼方式，此編碼方式不僅用粒子位置代表一種導(dǎo)彈-目標(biāo)分配的決策方案，而且還滿足模型中所有約束條件的要求，從而實(shí)現(xiàn)了原規(guī)劃問(wèn)題的無(wú)約束轉(zhuǎn)化。

由上述設(shè)計(jì)第i個(gè)載機(jī)平臺(tái)的火力策略空間：

其中，xir∈0，1，…，m;r∈1，2，…，ni。當(dāng)xir=h時(shí)，表示第i個(gè)載機(jī)平臺(tái)的第r枚導(dǎo)彈用于摧毀第h個(gè)目標(biāo)，當(dāng)xir=0時(shí)，表示第i個(gè)載機(jī)的第r個(gè)武器單元沒(méi)有使用。以上是第i個(gè)載機(jī)平臺(tái)決策序列的編碼，編碼長(zhǎng)度為ni，其他平臺(tái)以此類推。

4.2 個(gè)體更新策略

首先，選出整個(gè)種群中最優(yōu)適應(yīng)值個(gè)體Pg，每個(gè)模因組中的最優(yōu)適應(yīng)值個(gè)體Pb、最劣適應(yīng)值個(gè)體Pw。然后將Pb和Pw進(jìn)行交叉操作，比較新產(chǎn)生的兩個(gè)個(gè)體與Pw的適應(yīng)值，如有比Pw適應(yīng)度高的個(gè)體，就用較優(yōu)適應(yīng)值的個(gè)體替代Pw。否則用Pg代替Pb與Pw進(jìn)行交叉操作，如果產(chǎn)生的個(gè)體仍不優(yōu)于Pw，則對(duì)Pw進(jìn)行變異操作，并用產(chǎn)生的新個(gè)體直接替代Pw。具體的交叉、變異操作策略如下：

交叉操作：由解的編碼方式可知，編碼長(zhǎng)度等于我機(jī)編隊(duì)的火力單元總數(shù)k，所以粒子X(jué)與粒子Y均是長(zhǎng)度為k的實(shí)數(shù)序列。生成一個(gè)長(zhǎng)為k的0-1隨機(jī)序列，在“1”對(duì)應(yīng)的位置上將粒子X(jué)與粒子Y進(jìn)行交換，“0”所在的位置則不進(jìn)行操作，從而產(chǎn)生新粒子X(jué)'、Y'。

變異操作：變異操作與交叉操作類似，首先生成一個(gè)長(zhǎng)為k的0-1隨機(jī)序列，在“1”所在的位置上對(duì)粒子X(jué)進(jìn)行變異操作，“0”所在的位置上則不進(jìn)行操作。

4.3 混合SFLA算法流程

圖1 蛙跳算法總流程

5 仿真分析

為了測(cè)試混合SFLA算法處理協(xié)同多目標(biāo)攻擊空戰(zhàn)決策問(wèn)題的性能，引入文獻(xiàn)[4]中所用的作戰(zhàn)想定，設(shè)我方戰(zhàn)機(jī)編隊(duì)與敵機(jī)編隊(duì)在超視距條件下進(jìn)行空戰(zhàn)，我方戰(zhàn)機(jī)數(shù)量為4架，每架飛機(jī)上均掛載4枚導(dǎo)彈，共探測(cè)到聯(lián)合攻擊區(qū)內(nèi)的10架敵機(jī)，我方戰(zhàn)機(jī)編隊(duì)采用協(xié)同空戰(zhàn)戰(zhàn)術(shù)。

各導(dǎo)彈對(duì)各目標(biāo)的毀傷概率矩陣為：

圖2 模因組進(jìn)化流程

各目標(biāo)的威脅權(quán)重矩陣為：

在本文所采用的GA-SFLA算法中，種群規(guī)模取為100個(gè)，模因組數(shù)目為5個(gè)，每個(gè)模因組規(guī)模為20個(gè)。在這樣的情況下，使用GA-SFLA算法和SA-DPSO算法分別對(duì)該火力分配問(wèn)題進(jìn)行優(yōu)化求解。所得的最優(yōu)適應(yīng)值變化情況見(jiàn)圖3。

圖3 最佳適應(yīng)值的變化曲線

最優(yōu)分配情況如下：

通過(guò)比較可知，混合SFLA算法不但可以在設(shè)定的代數(shù)中找到最優(yōu)解，而且能夠有效地避免局部最優(yōu)。而SA-DPSO算法不僅收斂速度慢于混合SFLA算法，且在迭代過(guò)程中會(huì)陷入局部最優(yōu)解。此外，考慮到火力分配的實(shí)時(shí)性問(wèn)題，從算法的效率上來(lái)看，GA-SFLA的粒子更新只需對(duì)每個(gè)模因組的最后一個(gè)粒子進(jìn)行操作，將更新后的該粒子根據(jù)適應(yīng)值排序重新插入到模因組中，整個(gè)算法具有并行性且設(shè)置參數(shù)少。而SA-DPSO算法是一種兩層的串行結(jié)構(gòu)，DPSO的一次優(yōu)化結(jié)果作為SA的初始種群，SA經(jīng)M etropolis抽樣過(guò)程得到的解又成為下一次進(jìn)化的初始種群，過(guò)程復(fù)雜且涉及的動(dòng)態(tài)參數(shù)較多，不利于大規(guī)模問(wèn)題的快速求解。這說(shuō)明本文提出的混合SFLA算法在解決協(xié)同空戰(zhàn)火力分配問(wèn)題上是快速有效的。

6 結(jié)論

本文建立了協(xié)同空戰(zhàn)火力分配數(shù)學(xué)模型，引入的編碼方式將原模型轉(zhuǎn)化成為無(wú)約束優(yōu)化問(wèn)題，且不增加問(wèn)題的復(fù)雜性。提出了一種混合SFLA算法對(duì)模型進(jìn)行求解，在求解過(guò)程中，充分利用了群智能的信息（種群最優(yōu)、模因組最優(yōu)和模因組最劣）和智能算法的個(gè)體智能（交叉、變異），且各模因組進(jìn)化具有高度的并行性，體現(xiàn)了分布式計(jì)算的高效率。仿真結(jié)果表明，提出的混合SFLA算法是快速有效的。

[1]蔡懷平，陳英武.武器-目標(biāo)分配（WTA）問(wèn)題研究進(jìn)展[J].火力與指揮控制，2006，31（12）：11-15.

[2]Lloyd S P，H S W.Weapons allocations is NP-complete[C]// Proceedings of the 1986 Summer Conference on Simulation，Reno，Nevada，1986.

[3]費(fèi)愛(ài)國(guó)，張陸游，丁前軍.基于拍賣(mài)算法的多機(jī)協(xié)同火力分配[J].系統(tǒng)工程與電子技術(shù)，2012，34（9）：1828-1833.

[4]李儼，董玉娜.基于SA-DPSO混合優(yōu)化算法的系統(tǒng)空戰(zhàn)火力分配[J].航空學(xué)報(bào)，2010，31（3）：626-631.

[5]陳華東，王樹(shù)宗，王航宇.基于混合粒子群算法的多平臺(tái)多武器火力分配研究[J].系統(tǒng)工程與電子技術(shù)，2008，30（5）：880-883.

[6]高尚，楊靜宇.武器-目標(biāo)分配問(wèn)題的粒子群優(yōu)化算法[J].系統(tǒng)工程與電子技術(shù)，2005，27（7）：1250-1253.

[7]羅德林，段海濱，吳順詳.基于啟發(fā)式蟻群算法的協(xié)同多目標(biāo)空戰(zhàn)決策研究[J].航空學(xué)報(bào)，2006，27（6）：1166-1170.

[8]Gao S.Solving weapon-target assignment problem by a new ant colony algorithm[C]//Proceedings of the 6 World Congress on Intelligent Control and Automation，2008，1：221-224.

[9]楊山亮，黃健，劉洋，等.基于遺傳算法的聯(lián)合火力WTA問(wèn)題研究[J].計(jì)算機(jī)仿真，2012，29（3）：61-64.

[10]羅雪暉，楊燁，李霞.改進(jìn)混合蛙跳算法求解旅行商問(wèn)題[J].通信學(xué)報(bào)，2009，30（7）：130-135.

[11]裴蘭珍，甘傳付，邢波，等.采用改進(jìn)差分進(jìn)化算法的防空導(dǎo)彈火力分配[J].計(jì)算機(jī)工程與應(yīng)用，2012，48（22）：235-238.

[12]Eusuff M M，Lansey K E.optimization of water distribution network design using the shuffled frog leaping algorithm[J].J of Water Resources Planning and Management，2003，129（3）：210-225.

[13]張敬敏，馬麗，李媛媛.求解TSP問(wèn)題的改進(jìn)混合蛙跳算法[J].計(jì)算機(jī)工程與應(yīng)用，2012，48（11）：47-50.

[14]王亞敏，潘全科，冀俊忠.求解考試時(shí)間安排的離散蛙跳算法[J].計(jì)算機(jī)工程與應(yīng)用，2009，45（36）：40-44.

[15]崔文華，劉曉冰，王偉，等.混合蛙跳算法研究綜述[J].控制與決策，2012，27（4）：481-487.

ZHANG Kai, ZHOU Deyun, PAN Qian

School of Electronics and Information, Northwestern Polytechnical University, Xi’an 710129, China

In view of beyond-visual-range cooperative air combat, the model of Weapon-Target Assignment（WTA）is established,and a mixed Shuffled Frog Leaping Algorithm（SFLA）is proposed to solve the weapon-target assignment problem.Based on an unconstrained encoding, the algorithm combining the cross and mutation of genetic algorithm improves the convergence rate and the seeking ability for the global optimal result so that the local minimum is avoided. The simulation results show that the proposed algorithm is an effective algorithm to solve weapon-target assignment for cooperative air combat.

cooperative air combat; weapon-target assignment; shuffled frog leaping algorithm; genetic operator

ZHANG Kai, ZHOU Deyun, PAN Qian. Weapon-target assignment based on shuffled frog leaping algorithm in cooperative air combat. Computer Engineering and Applications, 2014, 50（17）：263-266.

A

V 247

10.3778/j.issn.1002-8331.1306-0116

航空科學(xué)基金（No.20115553021）。

張凱（1988—），男，碩士研究生，研究領(lǐng)域?yàn)榇笙到y(tǒng)理論及應(yīng)用、先進(jìn)控制理論；周德云（1964—），男，教授，博士生導(dǎo)師；潘潛（1989—），男，碩士研究生。E-mail：zhangkainw pu@mail.nw pu.edu.cn

2013-06-13

2013-10-21

1002-8331（2014）17-0263-04

CNKI網(wǎng)絡(luò)優(yōu)先出版：2013-11-27,http://www.cnki.net/kcm s/detail/11.2127.TP.20131127.1511.005.htm l