常天慶， 陳軍偉， 張 雷， 楊國(guó)振

(裝甲兵工程學(xué)院控制工程系， 北京 100072)

坦克分隊(duì)WTA問(wèn)題的改進(jìn)人工蜂群算法

常天慶， 陳軍偉， 張 雷， 楊國(guó)振

(裝甲兵工程學(xué)院控制工程系， 北京 100072)

針對(duì)目前智能算法初期收斂速度難以滿足坦克分隊(duì)武器-目標(biāo)分配(Weapon-Target Assignment, WTA)要求的問(wèn)題，提出了一種改進(jìn)人工蜂群算法。該算法結(jié)合NEH啟發(fā)式算法和隨機(jī)方法對(duì)種群進(jìn)行初始化，利用變鄰域搜索和模擬退火方法改進(jìn)了采蜜蜂算法，并簡(jiǎn)化了跟隨蜂算法，提出了一種全局最優(yōu)限制算法。最后，結(jié)合不同規(guī)模的WTA問(wèn)題，給出了該算法參數(shù)的確定方法。仿真結(jié)果表明：改進(jìn)人工蜂群算法相比于其他算法在初始種群質(zhì)量和算法初期收斂速度方面具有明顯優(yōu)勢(shì)，特別適合求解坦克分隊(duì)WTA問(wèn)題。

人工蜂群算法；NEH啟發(fā)式算法；模擬退火算法；WTA；坦克分隊(duì)

武器-目標(biāo)分配(Weapon-Target Assignment, WTA)問(wèn)題在軍事上又稱作火力分配問(wèn)題，研究的是在作戰(zhàn)過(guò)程中明確指出由我方哪些武器對(duì)敵方哪些目標(biāo)采取何種方案進(jìn)行射擊，從而實(shí)現(xiàn)作戰(zhàn)目的[1]。WTA問(wèn)題屬于典型的NP-hard問(wèn)題[2]，解空間為(n+1)m(n、m分別為參與戰(zhàn)斗的武器、目標(biāo)數(shù)量)。采用枚舉法、分支定界法、割平面法、動(dòng)態(tài)規(guī)劃法等傳統(tǒng)算法求解WTA問(wèn)題，雖然可以得到最優(yōu)解，但當(dāng)武器-目標(biāo)規(guī)模較大時(shí)，其解算代價(jià)是不能接受的。近年來(lái)的研究[3-5]已經(jīng)證明：智能算法可以更快求解NP-hard問(wèn)題，并得到滿意解。其中，粒子群算法(Particle Swarm Optimization, PSO)[6]、遺傳算法(Genetic Algorithm, GA)[7]、蟻群算法(Ant Colony Optimization, ACO)[8]均在解WTA問(wèn)題上取得了一定效果。但由于智能算法在運(yùn)行初期正反饋信息缺乏，其普遍存在初期收斂速度慢、易陷入局部最優(yōu)解的問(wèn)題[9]。

射擊反應(yīng)時(shí)間是坦克射擊的重要指標(biāo)，一般的要求是炮手從發(fā)現(xiàn)目標(biāo)到擊發(fā)的反應(yīng)時(shí)間不超過(guò)10 s[10]，如果將WTA加入坦克射擊過(guò)程中，其求解WTA時(shí)間增加1 s，射擊反應(yīng)時(shí)間至少增加10%。另外，地面戰(zhàn)場(chǎng)作戰(zhàn)態(tài)勢(shì)瞬息萬(wàn)變，及時(shí)輸出一個(gè)可行的次優(yōu)解要比花費(fèi)長(zhǎng)時(shí)間尋找滿意解更符合坦克分隊(duì)作戰(zhàn)需求。因此，坦克分隊(duì)WTA問(wèn)題的求解算法首先需要提高的性能就是算法運(yùn)行初期收斂速度，同時(shí)還要避免陷入局部最優(yōu)解。

人工蜂群算法(Artificial Bee Colony, ABC)是由Ereiyes大學(xué)的Karaboga[11]提出的群智能優(yōu)化算法。與其他優(yōu)化算法相比，ABC算法具有多種群協(xié)同尋優(yōu)的特點(diǎn)，可以在更小的種群和時(shí)間成本內(nèi)得到優(yōu)秀的結(jié)果[12-13]。ABC算法獨(dú)有的“采蜜蜂、跟隨蜂”2層尋優(yōu)機(jī)制提高了算法運(yùn)行初期收斂速度，其“偵察蜂”機(jī)制減小了陷入局部最優(yōu)解的概率[14]。然而，由于ABC算法出現(xiàn)時(shí)間較短，其在應(yīng)用時(shí)還存在如下問(wèn)題[15-17]：1) ABC算法最早提出是用于求解連續(xù)多峰函數(shù)最值的問(wèn)題，其位置更新公式不適用于WTA等離散問(wèn)題；2) 在鄰域搜索方面不具備區(qū)域搜索能力，僅根據(jù)位置更新公式產(chǎn)生單個(gè)新解；3) 在接近全局最優(yōu)解時(shí)，由于種群相似度大，搜索速度變慢，僅依靠“偵察蜂”機(jī)制難以保證搜索效率。

針對(duì)上述問(wèn)題，筆者提出一種改進(jìn)ABC算法，并通過(guò)與其他算法的仿真對(duì)比驗(yàn)證該算法在解決坦克分隊(duì)WTA問(wèn)題上的優(yōu)勢(shì)。

1 坦克分隊(duì)WTA問(wèn)題描述

紅藍(lán)雙方裝甲分隊(duì)處于會(huì)戰(zhàn)某時(shí)刻，此時(shí)紅方有m個(gè)戰(zhàn)術(shù)單位，稱為武器集W={Wi}，i=1,2,…,m。藍(lán)方裝甲分隊(duì)有n個(gè)戰(zhàn)術(shù)單位，稱為目標(biāo)集T={Tj}，j=1,2,…,n。紅方目標(biāo)是使打擊效果最大化，建立坦克分隊(duì)WTA模型如下[18]：

(1)

(2)

(3)

式中：tj∈[0,1]，為目標(biāo)j對(duì)武器集W的威脅程度；pij∈[0,1]，為武器i對(duì)目標(biāo)j的命中概率；xij={0,1}，xij=1表示W(wǎng)i對(duì)Tj進(jìn)行打擊，否則xij=0。由于一個(gè)武器同一時(shí)刻只能打擊一個(gè)目標(biāo)，因此設(shè)置約束條件(2)；由于射擊武器數(shù)量不能超過(guò)武器總數(shù)m，因此設(shè)置約束條件(3)。

2 改進(jìn)ABC算法

2.1 基本ABC算法

ABC算法是模擬自然蜂群采蜜行為的一種群智能算法。該算法定義了食物源、采蜜蜂、跟隨蜂、偵察蜂4個(gè)組件，以及搜索、招募、放棄蜜源3個(gè)行為。每一個(gè)食物源有且只有一個(gè)采蜜蜂，食物源的位置代表優(yōu)化問(wèn)題的一個(gè)可行解，每個(gè)食物源的蜂蜜量代表相關(guān)解的質(zhì)量，稱為收益度。算法開(kāi)始時(shí)，所有蜜蜂均為偵察蜂，采用完全隨機(jī)的方式尋找食物源，即問(wèn)題的解；尋找到食物源后，所有偵察蜂返回蜂巢，根據(jù)所持有食物源的收益度遵循一定概率成為采蜜蜂或跟隨蜂；采蜜蜂回到原食物源附近繼續(xù)尋找新食物源，跟隨蜂選擇在蜂巢等待；當(dāng)采蜜蜂完成新食物源的尋找后回到蜂巢，跟隨蜂根據(jù)采蜜蜂所持新食物源的收益度遵循一定概率接受招募，在新食物源附近進(jìn)一步尋找食物源；如果采蜜蜂和跟隨蜂經(jīng)過(guò)一定次數(shù)尋找后未能找到收益度更高的食物源，則放棄當(dāng)前食物源并成為偵察蜂，依然采用完全隨機(jī)的方式搜索食物源。

2.2 改進(jìn)ABC算法流程

改進(jìn)ABC算法沿用了標(biāo)準(zhǔn)ABC算法主流程，對(duì)其中的子算法進(jìn)行了改進(jìn)，其流程如圖1所示。改進(jìn)ABC算法具體步驟如下：

圖1 改進(jìn)ABC算法總體流程

1) 進(jìn)行參數(shù)初始化，包括設(shè)定種群規(guī)模N，最大迭代次數(shù)M，蜂群控制參數(shù)L、L2,全局閾值Lmax，最優(yōu)解閾值Bmax和初始搜索范圍S；

2) 采用NEH啟發(fā)式算法[19]進(jìn)行采蜜蜂的種群初始化，運(yùn)用隨機(jī)方法進(jìn)行跟隨蜂的種群初始化，采蜜蜂與跟隨蜂的數(shù)量相等；

3) 采蜜蜂采用基于變鄰域與模擬退火(Simulated Annealing, SA)[20]的算法進(jìn)行鄰域搜索；

4) 采用簡(jiǎn)化的跟隨蜂算法保持種群中的最優(yōu)個(gè)體；

5) 采用基于遺傳算子的全局最優(yōu)限制算法協(xié)調(diào)2種蜂群中最優(yōu)個(gè)體的數(shù)量，防止因種群相似度過(guò)大而陷入早熟；

6) 判斷是否滿足算法終止條件，若滿足，則輸出最優(yōu)解，否則返回步驟3)。

與標(biāo)準(zhǔn)ABC算法相同，偵察蜂算法嵌入采蜜蜂算法和跟隨蜂算法中。當(dāng)采蜜蜂或跟隨蜂的控制參數(shù)L、L2達(dá)到閾值Lmax時(shí)，則采蜜蜂或跟隨蜂放棄食物源并轉(zhuǎn)變?yōu)閭刹旆?，以全隨機(jī)的方式尋找新的食物源。

2.3 種群編碼方法

食物源(分配方案)可編碼為N個(gè)m維向量所組成的矩陣形式：X=(xuv)N×m。其中：u=1,2,…,N，N為食物源數(shù)量，也是采蜜蜂數(shù)量；v為武器的編號(hào)；xuv是區(qū)間[0,n]內(nèi)的整數(shù)，xuv=j(j≠0)表示在分配方案u中，編號(hào)為v的武器射擊編號(hào)為j的目標(biāo)，xuv=0表示武器v沒(méi)有射擊目標(biāo)。

2.4 NEH啟發(fā)式算法和隨機(jī)方法相結(jié)合的種群初始化

初始種群的多樣性特征和個(gè)體解的質(zhì)量對(duì)后期算法尋優(yōu)效果具有重要影響。標(biāo)準(zhǔn)ABC算法采用全隨機(jī)的方法生成初始化種群，這種方法簡(jiǎn)單易行、離散度高，有利于全局尋優(yōu)，但初始種群質(zhì)量較差，限制了算法初期的收斂速度。為此，本文采用NEH啟發(fā)式算法和隨機(jī)方法相結(jié)合(簡(jiǎn)稱“混合法”)進(jìn)行種群初始化。

NEH啟發(fā)式算法是為解決流水線車間調(diào)度問(wèn)題所提出的一種啟發(fā)式算法[21]，本文基于NEH基本方法并加以改進(jìn)，對(duì)采蜜蜂進(jìn)行種群初始化，具體步驟如下：

1) 將所有n個(gè)目標(biāo)按照威脅程度遞減的順序進(jìn)行排列；

2) 選擇威脅程度最大的目標(biāo)jtmax，并計(jì)算武器單獨(dú)打擊目標(biāo)產(chǎn)生的收益Qi=tj·pij,i=1,2,…,m，選擇其中收益最大的武器和目標(biāo)進(jìn)行匹配；

3) 更新武器集、目標(biāo)集，將步驟2)中選擇的武器、目標(biāo)從集合中去除，令m=m-1,n=n-1；

4) 判斷m·n是否為0，若否，返回步驟2)，否則初始化結(jié)束，輸出WTA分配結(jié)果。

通過(guò)這種方法可以得到一個(gè)可行解，將其插入采蜜蜂群中，其他采蜜蜂和跟隨蜂采用全隨機(jī)的方該進(jìn)行種群初始化。

這樣的種群初始化方法可以有效提高初始種群質(zhì)量和算法運(yùn)行初期的收斂速度，但由于初始化后某一個(gè)體收益度遠(yuǎn)超種群平均收益度，該個(gè)體很快占據(jù)優(yōu)勢(shì)比例，降低了全局最優(yōu)解的搜索能力，導(dǎo)致算法陷入早熟。為此，筆者將通過(guò)改進(jìn)的采蜜蜂算法和全局最優(yōu)限制算法予以解決。

2.5 基于變鄰域與模擬退火的采蜜蜂算法

采蜜蜂負(fù)責(zé)在食物源附近搜索優(yōu)秀解，傳統(tǒng)的搜索方法是在m維的編碼中隨機(jī)選擇一個(gè)位置，在可行域內(nèi)隨機(jī)生成新的編碼值。這種固定域的搜索方法忽視了算法在不同迭代次數(shù)時(shí)對(duì)搜索寬度的不同需求。本文采用一種搜索范圍隨迭代過(guò)程變化的變鄰域搜索算法，參數(shù)初始化時(shí)給定了一個(gè)搜索范圍S，則更新搜索鄰域的公式為

s.t.S≥Slimit。

式中：C為算法迭代次數(shù)；Cmax為設(shè)定的算法最大迭代次數(shù)；ceil表示對(duì)括號(hào)內(nèi)的內(nèi)容向上取整。為確保算法運(yùn)行后期變鄰域依然可以起到搜索新食物源的作用，設(shè)置約束條件S≥Slimit，Slimit的數(shù)值需要根據(jù)求解問(wèn)題中目標(biāo)的數(shù)量n來(lái)確定，一般取Slimit=n/4。與固定鄰域的食物源搜索方法相比，變鄰域的搜索范圍在初始值S的基礎(chǔ)上隨迭代次數(shù)的增加而不斷變小。這種方法既提高了算法運(yùn)行初期的搜索寬度，又加快了算法運(yùn)行后期的尋優(yōu)速度。

在采蜜蜂搜索過(guò)程中，將蜂群分為2部分：1) 采用SA算法對(duì)蜂群中具有最優(yōu)收益度的解進(jìn)行深度搜索，SA算法的搜索鄰域依然采用變鄰域的方法；2) 對(duì)其他采蜜蜂所擁有的解僅采用變鄰域的方法進(jìn)行搜索。新編碼搜索更新方法如下：

模擬退火算法的引入不但提高了優(yōu)秀解的局部搜索能力，而且其概率突跳特性可以有效降低算法早熟的概率，突跳概率為

P=exp[-(fit(E2)-fit(E1))]，

式中：fit(E1)、fit(E2)分別為采蜜蜂E1和E2的收益度。

基于變鄰域與模擬退火的采蜜蜂算法流程如圖2所示，采用數(shù)組L作為蜂群控制參數(shù)，記錄各個(gè)采蜜蜂連續(xù)未更新的代數(shù)。個(gè)體更新后，L中的對(duì)應(yīng)值歸0；否則，對(duì)應(yīng)值加1。當(dāng)采蜜蜂在L中的對(duì)應(yīng)值達(dá)到全局閾值Lmax時(shí)，采蜜蜂轉(zhuǎn)變?yōu)閭刹旆?，偵察蜂隨機(jī)尋找新的食物源替換當(dāng)前個(gè)體。SA算法中：Tstart為初始溫度；Tend為終止溫度；T為溫度；K為退火系數(shù)。

圖2 基于變鄰域與模擬退火的采蜜蜂算法流程

2.6 簡(jiǎn)化的跟隨蜂算法

在標(biāo)準(zhǔn)ABC算法中，跟隨蜂會(huì)根據(jù)采蜜蜂所持信息采用輪盤賭的方法進(jìn)行選擇，持有高收益度食物源的采蜜蜂被選中的概率較大；反之，被選中的概率較小。跟隨蜂在選中采蜜蜂后，會(huì)在采蜜蜂持有解的基礎(chǔ)上進(jìn)行搜索，產(chǎn)生一個(gè)新解，分別與采蜜蜂持有解和自身解進(jìn)行比較，保留較優(yōu)秀的解。與其他群智能優(yōu)化算法相比，這種二次搜索的方法相當(dāng)于在總體上提高了蜂群1倍的搜索量，跟隨蜂可以在采蜜蜂的基礎(chǔ)上更深度地搜索優(yōu)秀解。

在基于變鄰域與SA的采蜜蜂算法中，變鄰域搜索增加了采蜜蜂群優(yōu)秀解的搜索廣度，SA算法增加了采蜜蜂群優(yōu)秀解的搜索深度。此時(shí)，由于跟隨蜂在采蜜蜂基礎(chǔ)上進(jìn)行深度搜索時(shí)只產(chǎn)生一個(gè)新解，因此對(duì)最優(yōu)解收益度的提高效果有限。如果仍然在跟隨蜂中采用基于變鄰域和SA的搜索方法，不僅增加了算法復(fù)雜度，還會(huì)使算法陷入早熟。

因此，本文對(duì)標(biāo)準(zhǔn)ABC算法中的跟隨蜂算法進(jìn)行了簡(jiǎn)化：首先跟隨蜂采用輪盤賭的方法進(jìn)行選擇；而后僅根據(jù)貪婪法進(jìn)行更新，不再進(jìn)行二次搜索。比較跟隨蜂與采蜜蜂所擁有可行解的收益度，保留其中收益度大的解。另外，在跟隨蜂群中采用數(shù)組L2記錄各跟隨蜂連續(xù)未更新的代數(shù)，跟隨蜂更新后，L2中的對(duì)應(yīng)值歸0；否則，對(duì)應(yīng)值加1。當(dāng)跟隨蜂在L2中的對(duì)應(yīng)值達(dá)到全局閾值Lmax時(shí)，跟隨蜂轉(zhuǎn)變?yōu)閭刹旆?，偵察蜂隨機(jī)尋找新的食物源替換當(dāng)前個(gè)體。

2.7 基于遺傳算子的全局最優(yōu)限制算法

種群相似度過(guò)大容易造成算法陷入局部最優(yōu)解，雖然算法已經(jīng)引入了全局閾值Lmax對(duì)種群個(gè)體進(jìn)行控制，但由于本文改進(jìn)了種群初始化方法以及采蜜蜂搜索方法，算法運(yùn)行初期最優(yōu)解收益度大大超過(guò)種群平均個(gè)體收益度，最優(yōu)解會(huì)迅速占據(jù)優(yōu)勢(shì)比例，限制算法的全局搜索能力。為解決這一問(wèn)題，筆者提出了一種基于遺傳算子的全局最優(yōu)限制算法，用于減少2種群中最優(yōu)解的重復(fù)度。以采蜜蜂為例，其全局最優(yōu)限制算法流程如圖3所示。

圖3 采蜜蜂全局最優(yōu)限制算法流程

算法設(shè)計(jì)了控制閾值Bmax，目的是限制蜂群中最優(yōu)解的數(shù)量。當(dāng)蜂群中的最優(yōu)解數(shù)量Bnum超過(guò)閾值Bmax時(shí)，從種群中任選2個(gè)最優(yōu)解，如果2個(gè)最優(yōu)解的收益度相等，任意選擇其中一個(gè)變成偵察蜂隨機(jī)搜索食物源并替代原有解；否則，借用遺傳算子中的交叉操作(cross)，通過(guò)最優(yōu)解的交叉合并產(chǎn)生2個(gè)子代解。如果2個(gè)子代解的收益度值較當(dāng)前群體最優(yōu)值發(fā)生改變，則保留2個(gè)子代解；否則，任意選擇一個(gè)變成偵察蜂隨機(jī)搜索食物源并替代原有解。交叉算子(cross)的具體流程如圖4所示。

圖4 交叉算子(cross)流程

在交叉算子中，隨機(jī)生成指示參數(shù)I1、I2、I3、I4,E1與E2交換指示參數(shù)所截取出的序列，并去掉重復(fù)部分，可以獲得新解Elfinal與E2final。經(jīng)過(guò)cross操作后，蜂群中的最優(yōu)解數(shù)量可以限制在閾值Bmax之內(nèi)。為提高優(yōu)秀蜂群的搜索能力，采用SA算法對(duì)其他未進(jìn)行交叉算子操作的解進(jìn)行優(yōu)化。為兼顧搜索效率，SA算法中鄰域產(chǎn)生法采用單次交叉法[22]。

3 仿真分析

3.1 仿真環(huán)境

改進(jìn)ABC算法運(yùn)行環(huán)境如表1所示。

表1 改進(jìn)ABC算法運(yùn)行環(huán)境

3.2 種群初始化方法驗(yàn)證

WTA問(wèn)題還沒(méi)有公認(rèn)的標(biāo)準(zhǔn)算例，但文獻(xiàn)[23]中所使用的算例最具代表性，也是被比較最多的算例。因此，為驗(yàn)證采用混合法進(jìn)行種群初始化的優(yōu)勢(shì)，分別采用混合法和全隨機(jī)法對(duì)文獻(xiàn)[23]中的算例進(jìn)行100次仿真計(jì)算，對(duì)每次迭代后的平均最優(yōu)解進(jìn)行比較，結(jié)果如圖5所示。

圖5 混合法和全隨機(jī)法種群初始化的各代平均最優(yōu)解

通過(guò)圖5可以看出：采用混合法進(jìn)行種群初始化可以有效提高初始種群的質(zhì)量和算法運(yùn)行初期的收斂速度，但降低了全局最優(yōu)解的搜索能力，致使算法陷入早熟。

3.3 全局最優(yōu)限制算法驗(yàn)證

全局最優(yōu)限制算法可以在保留最優(yōu)解的情況下限制蜂群中最優(yōu)解的數(shù)量，增加了種群多樣性，提高了算法的全局搜索能力。采用該算法對(duì)文獻(xiàn)[23]中的算例進(jìn)行100次仿真計(jì)算，圖6為采用全局最優(yōu)限制算法前后各代平均最優(yōu)解對(duì)比?？梢钥闯觯翰捎昧嘶谶z傳算子的全局最優(yōu)限制算法后，平均最優(yōu)解的質(zhì)量得到了提高。

3.4 參數(shù)確定

為充分驗(yàn)證改進(jìn)ABC算法在WTA問(wèn)題上的有效性，選取了3個(gè)不同規(guī)模的WTA算例，分別為5打3(算例1)、11打7(算例2)、17打10(算例3)。3個(gè)算例的武器-目標(biāo)命中概率如表2所示，目標(biāo)威脅程度如表3所示。

圖6 采用全局最優(yōu)限制算法前后各代平均最優(yōu)解對(duì)比

表2 武器-目標(biāo)命中概率

表3 目標(biāo)威脅程度

改進(jìn)ABC算法的控制參數(shù)為：種群規(guī)模N、各蜂群規(guī)模Ns、最大迭代次數(shù)M、全局閾值Lmax、最優(yōu)解閾值Bmax、初始搜索范圍S。首先綜合考慮算法優(yōu)化效果和收斂時(shí)間可以確定各參數(shù)的取值范圍，具體如表4所示。

而后通過(guò)算例具體確定全局閾值Lmax與最優(yōu)解閾值Bmax的取值。由于2種參數(shù)獨(dú)立，可先在不加入全局最優(yōu)限制算法的條件下確定Lmax的取值。利用3種不同規(guī)模的WTA算例，分別對(duì)Lmax取[5,10]內(nèi)的整數(shù)值各進(jìn)行100次仿真運(yùn)算，比較平均最優(yōu)解(Average Optimal, AO)、平均均值(Average Mean, AM)、平均最差解(Average Worst, AW)，結(jié)果如表5所示?？梢钥闯觯簩?duì)于算例1，Lmax=6時(shí)結(jié)果最優(yōu)；對(duì)于算例2，Lmax=7時(shí)結(jié)果最優(yōu)；對(duì)于算例3，Lmax=8時(shí)結(jié)果最優(yōu)。

表4 改進(jìn)ABC算法參數(shù)取值范圍

在確定參數(shù)Lmax后，采用同樣的驗(yàn)證方法確定Bmax的取值，結(jié)果如表6所示。可以看出：當(dāng)Bmax=Ns/6時(shí)，解算性能最優(yōu)。

表5 不同Lmax取值下的結(jié)果對(duì)比

表6 不同Bmax取值下的結(jié)果對(duì)比

3.5 算法比較

分別采用GA、PSO、ACO、標(biāo)準(zhǔn)ABC以及本文的改進(jìn)ABC (IABC)算法對(duì)算例2進(jìn)行100次仿真計(jì)算，對(duì)比5種算法各代的平均最優(yōu)解，具體結(jié)果如圖7所示。

圖7 5種算法各代平均最優(yōu)解對(duì)比

通過(guò)圖7可以看出：混合種群初始化方法和SA算法的引入對(duì)標(biāo)準(zhǔn)ABC算法初始種群質(zhì)量和初期收斂速度改善明顯；與單獨(dú)引入混合種群初始化方法(如圖5所示)的收斂效果相比，變鄰域搜索方法和全局最優(yōu)限制算法的引入改善了標(biāo)準(zhǔn)ABC算法運(yùn)行后期的尋優(yōu)能力。總體來(lái)說(shuō)，雖然改進(jìn)ABC算法的最優(yōu)解稍遜于標(biāo)準(zhǔn)ABC算法，但由于該算法在運(yùn)行初期具有明顯優(yōu)勢(shì)，因此特別適用于求解坦克分隊(duì)WTA問(wèn)題。

4 結(jié)論

本文提出了一種改進(jìn)ABC算法，有效滿足了坦克分隊(duì)WTA對(duì)求解算法初期收斂速度的要求。但該算法依然采用有限迭代次數(shù)的停止方法，下一步將研究一種新型的算法停止控制方法，以滿足坦克分隊(duì)WTA可以隨時(shí)輸出有效解的要求。

[1] Cai H P, Liu J X, Chen Y W, et al. Survey of the Research on Dynamic Weapon-target Assignment Problem [J]. Journal of System Engineering and Electronics, 2006, 17(3): 559-565.

[2] Lloyd S P, Witsenhausen H S. Weapons Allocation is NP-complete[C]∥Metler W A. Proceedings of the 1986 Summer Computer Simulation Conference. Reno,USA: The Society for Modeling and Simulation International, 1986: 1054-1058.

[3] Athanasios C S, Stavros T P, Ilias P T, et al. A New Hybrid Parallel Genetic Algorithm for the Job-shop Scheduling Problem[J]. International Transactions in Operational Research, 2014, 21(3): 479-499.

[4] Zhu X, Li X P, Wang Q. Objective Increment Based Metaheuristic for Total Flow Time Minimization in No-wait Flow Shops [J]. Journal of Southeast University, 2008, 24(2): 168-173.

[5] 杜鵬禎, 唐振民, 孫研. 一種面向?qū)ο蟮亩嘟巧伻核惴捌銽SP問(wèn)題求解[J]. 控制與決策, 2014, 29(10): 1729-1736.

[6] 曲在濱, 劉彥君,徐曉飛. 用離散粒子群優(yōu)化算法求解WTA問(wèn)題[J]. 哈爾濱工業(yè)大學(xué)學(xué)報(bào), 2013, 43(3): 67-69.

[7] Changdar C, Rajat G S M. An Efficient Genetic Algorithm for Multi-objective Solid Travelling Salesman Problem under Fuzziness [J]. Swarm and Evolutionary Computation, 2014, 15: 27-37.

[8] Lee Z J, Lee W L. A Hybrid Search Algorithm of Ant Colony Optimization and Genetic Algorithm Applied to Weapon-Target Assignment Problems [J]. Lecture Notes in Computer Science, 2003, 2690 (1): 278-285.

[9] Zhang J. A Hybrid Lehmer Code Genetic Algorithm and Its Application on Traveling Salesman Problems [D]. Norfolk: Old Dominion University, Doctoral Dissertation, 2011.

[10] 王春忠, 榮明, 張成亮, 等. 坦克嵌入式車場(chǎng)射擊訓(xùn)練炮長(zhǎng)操縱控制模型[J]. 裝甲兵工程學(xué)院學(xué)報(bào), 2008, 22(6): 19-21.

[11] Karaboga D. An Idea Based on Honey Bee Swarm for Numerical Optimization [R]. Kayseri: Engineering Faculty Computer Engineering Department, Ereiyes University, 2005.

[12] Omkar S, Senthilnath J, Khandelwal R. Artificial Bee Colony (ABC) for Multi-objective Design Optimization of Composite Structures [J]. Applied Soft Computing, 2011, 11(1): 489-499.

[13] Mansouria P, Asadya B, Gupta N. An Approximation Algorithm for Fuzzy Polynomial Interpolation with Artificial Bee Colony Algorithm [J]. Applied Soft Computing, 2013, 13(4): 1997-2002.

[14] Gao W, Liu S. A Modified Artificial Bee Colony Algorithm [J]. Computers & Operations Research, 2012, 39(3): 687-697.

[15] Zhang W, Wang N, Yang S. Hybrid Artificial Bee Colony Algorithm for Parameter Estimation of Proton Exchange Membrane Fuel Cell [J]. International Journal of Hydrogen Energy, 2013, 38(14): 5796-5806.

[16] Bullinaria J, AlYahya K. Artificial Bee Colony Training of Neural Networks[EB/OL].(2013-12-06)[2015-05-20]. http://www.cs.bhan.ac.uk/～jxb/PUBS/NICOS13.pdf

[17] Zhang D L, Tang Y G, Guan X P. Optimum Design of Fractional Order PID Controller for an AVR System Using an Improved Artificial Bee Colony Algorithm [J]. 自動(dòng)化學(xué)報(bào), 2014, 40(5): 973-980.

[18] 常天慶, 陳軍偉, 郝娜,等. 裝甲分隊(duì)動(dòng)態(tài)武器目標(biāo)分配中蟻群算法終止控制[J]. 系統(tǒng)工程與電子技術(shù), 2015, 37(2): 343-347.

[19] Nawaz M, Enscore E, Ham I. A Heuristic Algorithm for them-Machinen-job Flow-shop Sequencing Problem [J]. The International Journal of Management Sciences, 1983, 11(1): 91-95.

[20] Kirkpatrick S, Gelatt J C D, Vecchi M P. Optimization by Simulated Annealing [J]. Science, 1983, 4598 (220): 671-680.

[21] Kalczynski P J, Kamburowski J. On the NEH Heuristic for Minimizing the Makespan in Permutation Flowshops [J]. The International Journal of Management Sciences, 2007, 35(1): 53-60.

[22] 王凌, 劉波, 微粒群優(yōu)化與調(diào)度算法[M]. 北京: 清華大學(xué)出版社, 2008.

[23] 韓瑞新, 朱紅勝, 盧厚清, 等. 艦艇編隊(duì)防空火力基于改進(jìn)遺傳算法的分配方案[J]. 解放軍理工大學(xué)學(xué)報(bào)：自然科學(xué)版, 2006, 7(1): 46-50.

(責(zé)任編輯: 尚彩娟)

《裝甲兵工程學(xué)院學(xué)報(bào)》2016年征訂啟事

《裝甲兵工程學(xué)院學(xué)報(bào)》創(chuàng)刊于1987年，是以反映陸軍武器裝備工程技術(shù)與軍事理論為主的綜合性學(xué)術(shù)刊物，雙月刊，國(guó)內(nèi)外公開(kāi)發(fā)行，大16開(kāi)本，每期112頁(yè)，雙月25日出版。2016年定價(jià)為15.00元/期，全年90.00元(免郵寄費(fèi))。本刊自辦發(fā)行，無(wú)郵發(fā)代號(hào)，欲訂閱者可直接與本刊編輯部聯(lián)系，編輯部隨時(shí)辦理訂閱手續(xù)。

訂閱者請(qǐng)?zhí)顚?xiě)下面的回執(zhí)，并通過(guò)郵寄或E-mail的方式發(fā)回本刊編輯部。

《裝甲兵工程學(xué)院學(xué)報(bào)》2016年訂閱回執(zhí)

通信地址： 北京市豐臺(tái)區(qū)杜家坎21號(hào)《裝甲兵工程學(xué)院學(xué)報(bào)》編輯部 郵 編： 100072

聯(lián)系人： 王老師 聯(lián)系電話： 010-66719443 E-mail: xuebaozjb@163.com

An Improved Artificial Bee Colony Algorithm for Tank Unit WTA Problem

CHANG Tian-qing, CHEN Jun-wei, ZHANG Lei, YANG Guo-zhen

(Department of Control Engineering, Academy of Armored Force Engineering, Beijing 100072, China)

Aiming at the problem that it is difficult for the current intelligent algorithms to meet the requirement of tank unit Weapon-Target Assignment (WTA) for faster convergence speed on the early stage, an improved Artificial Bee Colony (ABC) algorithm is proposed. This algorithm adopts a combination method of NEH heuristic algorithm and random method for population initialization, uses variable neighborhood search and simulated annealing method for improving employed bees algorithm and simplifying unemployed bees algorithm, and introduces a global optimal limit algorithm. At last, combining different scale of WTA problem, the method used to determine algorithm parameters are given. The simulation results reveal that the improved ABC has a significant advantage on the quality of the initial population and the convergence speed on the early stage over other algorithms, and it is particularly suitable for tank unit WTA problem.

artificial bee colony; NEH heuristic optimization algorithm; simulated annealing algorithm; WTA; tank unit

1672-1497(2015)05-0069-08

2015-07-29

軍隊(duì)科研計(jì)劃項(xiàng)目

常天慶(1963-)，男，教授，博士。

TP301.6

A

10.3969/j.issn.1672-1497.2015.05.015