董朝陽(yáng),路遙,王青

(1.北京航空航天大學(xué)航空科學(xué)與工程學(xué)院,北京100191;2.北京航空航天大學(xué)自動(dòng)化科學(xué)與電氣工程學(xué)院,北京100191)

改進(jìn)的遺傳算法求解火力分配優(yōu)化問(wèn)題

董朝陽(yáng)1,路遙1,王青2

(1.北京航空航天大學(xué)航空科學(xué)與工程學(xué)院,北京100191;2.北京航空航天大學(xué)自動(dòng)化科學(xué)與電氣工程學(xué)院,北京100191)

提出一種求解火力分配優(yōu)化問(wèn)題的改進(jìn)遺傳算法?；谀繕?biāo)函數(shù)的相對(duì)大小構(gòu)造適應(yīng)度函數(shù),較傳統(tǒng)的界限構(gòu)造法更加顯著地體現(xiàn)染色體之間的差異,使得優(yōu)良染色體更容易被選中,從而提高算法的收斂精度。采用基于父代染色體相似度的啟發(fā)式遺傳算子優(yōu)化遺傳運(yùn)算,靈活、有針對(duì)性地對(duì)父代染色體進(jìn)行交叉或變異操作,在防止算法陷入局部最優(yōu)的同時(shí)保證種群的更新速度。仿真實(shí)驗(yàn)對(duì)比結(jié)果分析表明所設(shè)計(jì)的改進(jìn)算法具有更高效的尋優(yōu)能力。

兵器科學(xué)與技術(shù);整數(shù)規(guī)劃;火力分配;遺傳算法;適應(yīng)度函數(shù)

DOI:10.3969/j.issn.1000-1093.2016.01.015

0 引言

火力分配(WTA)是指根據(jù)作戰(zhàn)目的、戰(zhàn)場(chǎng)態(tài)勢(shì)和武器性能等因素,將一定類(lèi)型和數(shù)量的火力單元以某種準(zhǔn)則進(jìn)行分配,攻擊一定數(shù)量敵方目標(biāo)的過(guò)程。WTA是戰(zhàn)場(chǎng)指揮當(dāng)中的重要環(huán)節(jié),是決定作戰(zhàn)效果的關(guān)鍵因素[1]。

WTA問(wèn)題屬于一類(lèi)NP-hard問(wèn)題。當(dāng)前國(guó)內(nèi)外研究成果多以對(duì)目標(biāo)的毀傷概率最大為目的,通過(guò)智能優(yōu)化算法,如啟發(fā)式遺傳算法[2]、蟻群遺傳算法[3]、模擬退火遺傳算法[4]、混合變鄰域搜索算法[5]、粒子群算法[6]等對(duì)模型進(jìn)行求解,其中以遺傳算法為基礎(chǔ)設(shè)計(jì)搜索算法居多。遺傳算法是應(yīng)用最為廣泛的智能優(yōu)化算法之一,具有很強(qiáng)的全局搜索能力;但其在實(shí)際應(yīng)用中也存在著進(jìn)化慢、易早熟收斂等問(wèn)題。實(shí)際研究表明,適應(yīng)度函數(shù)的選取和遺傳算子調(diào)節(jié)機(jī)制的設(shè)置是影響遺傳算法性能的關(guān)鍵。適應(yīng)度函數(shù)選取不當(dāng)將會(huì)嚴(yán)重影響算法的計(jì)算效率,而傳統(tǒng)的遺傳算法存在交叉變異概率在種群進(jìn)化過(guò)程中固定不變的不足。

針對(duì)具體的工程優(yōu)化問(wèn)題,許多學(xué)者對(duì)算法適應(yīng)度函數(shù)的構(gòu)建和遺傳算子的改進(jìn)方案進(jìn)行了研究。文獻(xiàn)[7]設(shè)計(jì)了相對(duì)適應(yīng)度函數(shù)和離散重組交叉算子,解決了一類(lèi)高層結(jié)構(gòu)黏滯阻尼器優(yōu)化布置問(wèn)題;文獻(xiàn)[8]提出了一種新的適應(yīng)度函數(shù)以解決一類(lèi)最小屬性約簡(jiǎn)問(wèn)題;文獻(xiàn)[9]將Petri網(wǎng)分析應(yīng)用于遺傳算法的適應(yīng)度函數(shù)設(shè)計(jì),用以解決城市交通流優(yōu)化問(wèn)題;文獻(xiàn)[10]研究了遺傳算法的交叉操作,設(shè)計(jì)了順序構(gòu)造交叉算子,提高了生成解的質(zhì)量;文獻(xiàn)[11]設(shè)計(jì)了一種啟發(fā)式交叉算子以改善種群質(zhì)量,加快算法的尋優(yōu)速度。文獻(xiàn)[12]在研究遺傳算法求解虛擬機(jī)資源調(diào)度問(wèn)題時(shí),設(shè)計(jì)了新的變異算子,取得了更好地求解結(jié)果。

本文針對(duì)一類(lèi)以對(duì)目標(biāo)的毀傷概率最大為目的的WTA問(wèn)題,采用改進(jìn)的遺傳算法進(jìn)行求解。通過(guò)設(shè)計(jì)合適的適應(yīng)度函數(shù)以及自適應(yīng)的變異概率調(diào)節(jié)機(jī)制,提高了算法的尋優(yōu)能力,避免算法過(guò)早地陷入局部極值。

1 WTA問(wèn)題的數(shù)學(xué)描述

假設(shè)有b種火力單元,分別用Mi(i=1,2,…,b)表示,每種火力單元的數(shù)量為mi,且預(yù)打擊目標(biāo)共有n個(gè),分別用Tj(j=1,2,…,n)表示;ωj表示第j個(gè)預(yù)打擊目標(biāo)的威脅度系數(shù);pij表示第i種作戰(zhàn)單位對(duì)Tj的毀傷概率;令χkj(k=1,2,…,m)為決策變量,表示是否分配第k個(gè)火力單元打擊第j個(gè)目標(biāo),若分配則χkj=1,否則χkj=0.所有火力單元必須分配給預(yù)打擊目標(biāo),且每個(gè)火力單元只能分配給單個(gè)目標(biāo)。

WTA的目的為根據(jù)作戰(zhàn)要求,通過(guò)攻擊最大化地對(duì)目標(biāo)造成毀傷,可描述為

式中:V表示目標(biāo)函數(shù)。此外,模型還應(yīng)滿足毀傷下界約束:

式中:βj表示第j個(gè)目標(biāo)的毀傷下界。

2 基于模擬退火遺傳算法的WTA實(shí)現(xiàn)

2.1 編碼

用智能算法求解WTA問(wèn)題時(shí),首先要考慮的是所采用的編碼方式能不能恰當(dāng)?shù)乇硎締?wèn)題的求解空間以及能否使得算法具有較高的搜索效率。由于火力單元的數(shù)目或類(lèi)型以及目標(biāo)數(shù)均為整數(shù),用整數(shù)序列編碼表示火力單元與目標(biāo)的對(duì)應(yīng)狀態(tài)是自然、合理的方式;而對(duì)于不同的WTA問(wèn)題,根據(jù)火力單元總數(shù)m與預(yù)打擊目標(biāo)總數(shù)n的不同,可劃分為m＞n,m＜n以及m=n三類(lèi)情況。因此,所選擇的編碼方式應(yīng)在能夠描述以上所有3類(lèi)情況的基礎(chǔ)上,盡可能地不產(chǎn)生或較少產(chǎn)生“不合法"的染色體。基于此,搜索解的編碼可表示為

式中:yk為0～n之間的整數(shù),稱(chēng)為元素。yk=j表示將第k個(gè)火力單元分配給第j個(gè)目標(biāo);yk=0表示第k個(gè)火力單元沒(méi)有分配給任一目標(biāo)。這種編碼方式能夠描述以上3類(lèi)情況WTA問(wèn)題的同時(shí)不會(huì)產(chǎn)生“不合法"的染色體。

2.2 適應(yīng)度函數(shù)

輪盤(pán)賭是最常見(jiàn)的從種群中選擇父代染色體的策略,它能夠定量地表示染色體之間適應(yīng)度的差異[13]。在輪盤(pán)賭選擇方式下,染色體被選中的概率與其適應(yīng)度值大小緊密相關(guān)。本文采用界限構(gòu)造法[7]設(shè)計(jì)適應(yīng)度函數(shù),可表示為

式中:Cmin為V(ys)的最小估計(jì)值,需取一個(gè)較小的數(shù)以保證適應(yīng)度值非負(fù),例如,對(duì)于 (1)式表示的WTA問(wèn)題來(lái)說(shuō)可選擇Cmin=0.同時(shí),Cmin的取值還應(yīng)盡量使優(yōu)良染色體能夠以較大的概率被選中,從而提高算法優(yōu)化的計(jì)算效率。采用 (3)式計(jì)算染色體適應(yīng)度大小時(shí),一個(gè)染色體被選中的幾率Pys計(jì)算方法如下:

式中:N表示種群大小。Pys對(duì)Cmin求導(dǎo),可得由(5)式可知,當(dāng)ys為群體中在平均水平之上的優(yōu)良染色體時(shí),Cmin取值越大,P＇ys(Cmin)越大,即ys被選擇的幾率就越大。為保證優(yōu)良染色體在輪盤(pán)賭策略下具有最大的選擇幾率,本文中取,適應(yīng)度函數(shù)可表示為

2.3 遺傳算子

交叉算子采用多點(diǎn)交叉的方式。對(duì)于兩個(gè)選定的父代染色體y1和y2:

隨機(jī)選取3個(gè)切點(diǎn),交換切點(diǎn)間的子串,得到新的子代個(gè)體y＇1和y＇2:

變異采用簡(jiǎn)單的替換方式實(shí)現(xiàn)。當(dāng)一個(gè)染色體進(jìn)行變異操作時(shí),隨機(jī)選取染色體編碼中的3個(gè)元素,在合理的范圍內(nèi)進(jìn)行替換:

交叉概率pc和變異概率pa的大小是影響算法性能的關(guān)鍵。pc的大小決定種群個(gè)體的更新速率,較大的pc能夠提高解空間的探索能力,但pc過(guò)大時(shí)容易導(dǎo)致早熟收斂;pc取值保守會(huì)導(dǎo)致算法搜索過(guò)程緩慢,不利于種群的進(jìn)化。pa取值過(guò)大會(huì)使算法近似于隨機(jī)搜索,失去遺傳算法本身的一些優(yōu)良特性;pa取值過(guò)小容易使種群丟失一些優(yōu)良的基因。針對(duì)這一問(wèn)題,許多學(xué)者研究了自適應(yīng)調(diào)整參數(shù)的方法[10-12],取得了一定的成果;但設(shè)計(jì)的調(diào)節(jié)機(jī)制大都比較復(fù)雜,從而耗費(fèi)大量的計(jì)算時(shí)間。

本文根據(jù)父代染色體之間的相似度來(lái)決定是否進(jìn)行交叉和變異操作。從算法進(jìn)行交叉和變異操作的目的來(lái)看,交叉是為了產(chǎn)生和父代染色體不同的子代染色體,通過(guò)比較保留適應(yīng)度好的個(gè)體從而使種群不斷進(jìn)化。但是,當(dāng)父代染色體之間編碼差異很小或沒(méi)有差異,屬于“近親"時(shí),進(jìn)行交叉操作產(chǎn)生的子代染色體與父代染色體之間的差異也會(huì)很小甚至沒(méi)有差異;此時(shí),應(yīng)通過(guò)變異操作使得子代染色體與父代染色體之間產(chǎn)生差異,從而增加種群的多樣性,擴(kuò)大對(duì)解空間的搜索范圍,這也是算法中變異操作行為的目的?？偟膩?lái)說(shuō),當(dāng)父代染色體之間差異度較小時(shí),算法應(yīng)進(jìn)行交叉操作;當(dāng)父代染色體之間差異度較大時(shí),應(yīng)進(jìn)行變異操作。用D(y1、y2)表示y1、y2之間的相似度,其值為向量(y1-y2)中0元素的個(gè)數(shù)。D(y1,y2)越小表示y1、y2之間差異越大,進(jìn)行交叉操作后得到新的子代染色體幾率越高; D(y1,y2)越大表示y1、y2之間差異越小,進(jìn)行交叉操作越不容易得到新的子代染色體,應(yīng)進(jìn)行變異操作增加種群的多樣性?；谏鲜鲈?用變異操作閥值φ代替?zhèn)鹘y(tǒng)的變異概率pa,判斷是否進(jìn)行變異操作;當(dāng)D(y1,y2)≥φ時(shí),認(rèn)為選取的父代染色體的相似度足夠高,算法進(jìn)行變異操作。

2.4 最優(yōu)個(gè)體保持策略

本文采用最優(yōu)個(gè)體保持策略對(duì)每一代種群中的最優(yōu)個(gè)體進(jìn)行保護(hù),避免其在之后進(jìn)行的選擇、交叉或變異過(guò)程中被破壞。具體方式為:用前一代種群中適應(yīng)度值最大的染色體代替新一代種群中目標(biāo)函數(shù)值最小的染色體。

2.5 算法描述

采用改進(jìn)的遺傳算法求解WTA問(wèn)題的具體步驟如下:

步驟1 參數(shù)設(shè)置。需要設(shè)置的參數(shù)包括:種群數(shù)量N,交叉概率pc,毀傷下界βj,變異操作閥值φ,最大迭代次數(shù)Tmax.

步驟2 種群編碼及初始化。種群編碼采用(3)式表述的方式。通過(guò)函數(shù)y=ceil(n·rand(m,1))產(chǎn)生初始解,其中ceil和rand分別是Matlab中的取整數(shù)和隨機(jī)數(shù)生成命令。

步驟3 計(jì)算種群中染色體的適應(yīng)度值,采用輪盤(pán)賭方式選擇待交叉的父代染色體。

步驟4 更新種群。從父代染色體中隨機(jī)選擇兩個(gè)個(gè)體y1,y2,計(jì)算它們的相似度;若D(y1,y2)≥φ,則進(jìn)行變異操作;否則,依交叉概率pc進(jìn)行3切點(diǎn)交叉操作。

步驟5 保留最優(yōu)個(gè)體。計(jì)算子代種群的適應(yīng)度值,用父代種群中的最優(yōu)個(gè)體替換子代種群中適應(yīng)度值最差的個(gè)體。

步驟6 迭代次數(shù)加一,判斷算法終止條件。若迭代次數(shù)達(dá)到最大迭代次數(shù)Tmax,則輸出最優(yōu)解,結(jié)束算法;否則轉(zhuǎn)步驟3.

3 算例仿真和結(jié)果分析

為驗(yàn)證改進(jìn)的遺傳算法在求解(1)式類(lèi)型WTA問(wèn)題時(shí)的優(yōu)點(diǎn),采用文獻(xiàn)[4]給出的航空兵編隊(duì)對(duì)地攻擊WTA模型進(jìn)行仿真驗(yàn)證,并與該文獻(xiàn)中采用的模擬退火遺傳算法進(jìn)行比較。設(shè)有3種類(lèi)型的戰(zhàn)機(jī),共m=10架:M1、M2類(lèi)型戰(zhàn)機(jī)各有4架,即m1=m2=4;M3類(lèi)型戰(zhàn)機(jī)有2架,即m3=2.預(yù)打擊目標(biāo)數(shù)n=12,目標(biāo)威脅度以及每種類(lèi)型戰(zhàn)機(jī)對(duì)各個(gè)目標(biāo)的毀傷概率如表1所示。

表1 毀傷概率及目標(biāo)威脅度參數(shù)Tab.1 Damage probability and target threat parameters

仿真過(guò)程中,遺傳算法參數(shù)參考文獻(xiàn)[4]中給出的數(shù)據(jù),設(shè)置為:種群數(shù)量N=100,交叉概率pc= 0.8,毀傷下界βj=0.8,變異操作閥值φ=7.

3.1 不同適應(yīng)度函數(shù)比較

對(duì)算法選擇不同適應(yīng)度函數(shù)時(shí)的仿真效果進(jìn)行對(duì)比。用仿真實(shí)驗(yàn)1表示本文所設(shè)計(jì)算法,即以(6)式計(jì)算適應(yīng)度值;用仿真實(shí)驗(yàn)2表示對(duì)比算法,以(3)式計(jì)算適應(yīng)度值。取Cmin=0,最大迭代次數(shù)Tmax=30,其它參數(shù)設(shè)置不變,進(jìn)行100次仿真計(jì)算,結(jié)果如圖1和表2所示。圖1中為直觀表現(xiàn)兩種算法仿真結(jié)果間的差異,分別按從小到大的順序?qū)⑦m應(yīng)度值結(jié)果重新進(jìn)行了排列。

表2 不同適應(yīng)度值計(jì)算方式下的優(yōu)化結(jié)果Tab.2 Optimization results in different fitness value calculation modes

由表2可以看出,本文所提算法的種群適應(yīng)度值較對(duì)比算法具有優(yōu)勢(shì),其中算法初期優(yōu)勢(shì)較大,而隨著進(jìn)化次數(shù)的增加,優(yōu)勢(shì)變得越來(lái)越小。這是由于在輪盤(pán)賭選擇階段,與對(duì)比算法采用的適應(yīng)度函數(shù)相比,(6)式表示的適應(yīng)度函數(shù)能夠以更大的概率將種群中的優(yōu)良染色體選進(jìn)交配池中,即交配池中父代染色體整體質(zhì)量較高;在算法初期,種群適應(yīng)度值增長(zhǎng)空間較大,本文算法能夠更高效地改善種群質(zhì)量;而隨著進(jìn)化過(guò)程的進(jìn)行,本文算法逐漸趨于穩(wěn)定,種群適應(yīng)度值增長(zhǎng)空間逐漸減小,而對(duì)比算法種群適應(yīng)度值仍有一定的增長(zhǎng)空間,因此本文算法優(yōu)勢(shì)較搜索初期有所縮小。

圖1 第一組仿真算例結(jié)果對(duì)比Fig.1 Comparison of simulation results in Group 1

3.2 不同變異算子比較

本節(jié)中,采用參考文獻(xiàn)[4]中設(shè)計(jì)的模擬退火遺傳算法作為對(duì)比算法,用仿真實(shí)驗(yàn)3表示,取恒定的變異概率pa=0.1,且采用模擬退火策略避免算法陷入局部極值,退火參數(shù)設(shè)置為初始溫度T0=100,降溫系數(shù)α=0.99.取最大迭代次數(shù)Tmax=50,進(jìn)行100次仿真計(jì)算,結(jié)果如圖2～圖5及表3、表4所示。

由圖2和表3可以看出,本文算法的搜索結(jié)果更為精確。對(duì)比算法中采用固定變異率和模擬退火策略保證種群的多樣性,防止算法陷入局部極值,但這兩種措施并沒(méi)有與種群多樣性的變化和父代染色體的相似度聯(lián)系起來(lái)。本文算法不需事先確定固定變異率,而是根據(jù)具體尋優(yōu)過(guò)程中種群多樣性變化和選擇的父代染色體之間的相似度決定是否進(jìn)行變異操作。圖3給出了本文算法和對(duì)比算法仿真耗時(shí)的比較結(jié)果,與傳統(tǒng)算法相比,本文算法所設(shè)計(jì)的遺傳算子調(diào)節(jié)機(jī)制并不會(huì)耗費(fèi)更多的計(jì)算時(shí)間。圖4給出了每個(gè)采用本文算法的仿真實(shí)驗(yàn)中總變異次數(shù)的統(tǒng)計(jì)結(jié)果,表3給出了其中的最大值、最小值以及平均值。本文算法中,每次仿真實(shí)驗(yàn)會(huì)進(jìn)行2 450次進(jìn)化操作,由此可知本文算法的變異率大致在0.215～0.562之間,平均為0.317,這與尋優(yōu)過(guò)程中種群收斂至最優(yōu)值的速度有關(guān):種群越快地接近最優(yōu)值,每代更新時(shí)變異次數(shù)就越多。圖5給出了采用本文算法的一次仿真實(shí)驗(yàn)種群更新過(guò)程中進(jìn)化代數(shù)與變異次數(shù)的關(guān)系曲線?？梢钥闯?開(kāi)始階段變異次數(shù)較少,這是由于此時(shí)種群多樣性較高,選擇的父代染色體之間相似度較小的緣故;隨著種群的不斷更新,種群中的個(gè)體越來(lái)越接近最優(yōu)解,種群多樣性變得較差,選擇相似度較高的父代染色體進(jìn)行交配的概率越來(lái)越大,因此變異操作次數(shù)也越來(lái)越多。表4給出了本文算法得到的最優(yōu)攻擊分配方案,最優(yōu)值為0.906 0.通過(guò)以上實(shí)驗(yàn)數(shù)據(jù)可知,本文所設(shè)計(jì)的變異算子能夠在不影響計(jì)算耗時(shí)的情況下,取得更好的優(yōu)化結(jié)果。

圖2 第二組仿真算例結(jié)果對(duì)比Fig.2 Comparison of simulation results in Group 2

圖3 仿真耗時(shí)比較Fig.3 Comparison of simulation times

圖4 本文算法總變異次數(shù)統(tǒng)計(jì)Fig.4 Total mutation times statistics of the proposed algorithm

圖5 種群更新過(guò)程中變異操作次數(shù)Fig.5 Mutation operation times in population regeneration process

表3 不同變異算子下的優(yōu)化結(jié)果Tab.3 Optimization results in different variation operators

表4 本文算法得到的最優(yōu)攻擊分配Tab.4 Optimal attack distribution of the proposed algorithm

4 結(jié)論

本文針對(duì)一類(lèi)以對(duì)目標(biāo)的毀傷概率最大為目的的WTA問(wèn)題,提出了一種改進(jìn)的遺傳算法,并通過(guò)仿真實(shí)驗(yàn)得到了以下結(jié)論:

1)適應(yīng)度函數(shù)的選擇影響算法的尋優(yōu)精度。本文構(gòu)造的適應(yīng)度函數(shù)較傳統(tǒng)的界限構(gòu)造法能夠提高優(yōu)秀染色體被選中的概率,從而提高了種群的質(zhì)量,對(duì)算法尋優(yōu)能力產(chǎn)生積極影響。

2)根據(jù)尋優(yōu)過(guò)程中種群多樣性的變化,有針對(duì)性地選擇交叉或變異操作,仿真結(jié)果表明所設(shè)計(jì)的遺傳算子較固定不變的遺傳算子操作模式更為合理,效率更高。

References)

[1]張蛟,王中許,陳黎,等.具有多次攔截時(shí)機(jī)的防空火力分配建模及其優(yōu)化方法研究[J].兵工學(xué)報(bào),2014,35(10):1644-1650.ZHANG Jiao,WANG Zhong-xu,CHEN Li,et al.Modeling and optimization on antiaircraft weapon-target assignment at multiple interception opportunity[J].Acta Armamentarii,2014,35(10): 1644-1650.(in Chinese)

[2]Bayrak A E,Polat F.Employment of an evolutionary heuristic to solve the target allocation problem efficiently[J].Information Sciences,2013,222:675-695.

[3]Zhang J,Wang X,Xu C,et al.ACGA algorithm of solving weapon-target assignment problem[J].Open Journal of Applied Sciences,2013,2(4):74-77.

[4]賀小亮,畢義明.基于模擬退火遺傳算法的編隊(duì)對(duì)地攻擊WTA建模與優(yōu)化[J].系統(tǒng)工程與電子技術(shù),2014,36(5): 900-904.HE Xiao-liang,BI Yi-ming.Modeling and optimization of formation air-to-ground attack fire distribution based on simulated annealing genetic algorithm[J].Systems Engineering and Electronics,2014,36(5):900-904.(in Chinese)

[5]Tokg?z A,Bulkan S.Weapon target assignment with combinatorial optimization techniques[J].International Journal of Advanced Research in Artificial Intelligence,2013,2(7):39-50.

[6]Leboucher C,Shin H S,Le Mènec S,et al.Novel evolutionary game based multi-objective optimisation for dynamic weapon target assignment[C]//Preprints of the 19th World Congress:The International Federation of Automatic Control.Cape Town,South Africa:IFAC,2014:3936-3941.

[7]燕樂(lè)緯,陳洋洋,周云.基于數(shù)字序列編碼遺傳算法的高層結(jié)構(gòu)黏滯阻尼器優(yōu)化布置[J].振動(dòng)與沖擊,2015,34(3): 101-107.YAN Le-wei,CHEN Yang-yang,ZHOU Yun.Optimal positioning of viscous dampers in tall buildings based on digital sequence conding genetic algorithm[J].Journal of Vibration and Shock,2015,34(3):101-107.(in Chinese)

[8]Ye D Y,Chen Z J,Ma S L.A novel and better fitness evaluation for rough set based minimum attribute reduction problem[J].Information Sciences,2013,222:413-423.

[9]Henrique D,Regiane D S B,Norian M,et al.Optimizing urban traffic flow using genetic algorithm with Petri net analysis as fitness function[J].Neurocomputing,2014,124:162-167.

[10]Zakir H Ahmed.Genetic algorithm for the traveling salesman problem using sequential constructive crossover operator[J].International Journal of Biometrics and Bioinformatics,2010,3(6):96-105.

[11]于瑩瑩,陳燕,李桃迎.改進(jìn)的遺傳算法求解旅行商問(wèn)題[J].控制與決策,2014,29(8):1483-1488.YU Ying-ying,CHEN Yan,LI Tao-ying.Improved genetic algorithm for solving TSP[J].Control and Decision,2014,29(8): 1483-1488.(in Chinese)

[12]Gu J H,Hu J H,Zhao T H,et al.A new resource scheduling strategy based on genetic algorithm in cloud computing environment[J].Journal of Computers,2012,7(1):42-52.

[13]汪定偉,王俊偉,王洪峰,等.智能優(yōu)化算法[M].北京:高等教育出版社,2007.WANG Ding-wei,WANG Jun-wei,WANG Hong-feng,et al.Intelligent optimization methods[M].Beijing:Higher Education Press,2007.(in Chinese)

Improved Genetic Algorithm for Solving Firepower Distribution

DONG Chao-yang1,LU Yao1,WANG Qing2
(1.School of Aeronautic Science and Engineering,Beihang University,Beijing 100191,China; 2.School of Automation Science and Electrical Engineering,Beihang University,Beijing 100191,China)

An improved genetic algorithm for solving firepower distribution is proposed.The fitness function is constructed based on relative value of objective function.Compared with the conventional finitude construction method,this measure can incarnate the differences among the chromosomes more significantly and the fine chromosomes are selected more easily,thus improving the convergence precision of algorithm.The heuristic genetic operator based on the similarity of father chromosomes is used to optimize the genetic operation and do crossover or mutation to the father chromosomes with agility and pertinence.It can prevent the local optimization and guarantee the optimization speed of population.The contrast results of simulation examples show that the improved algorithm have more efficient search ability.

ordnance science and technology;integer programming;firepower distribution;genetic algorithm;fitness function

N945.25

A

1000-1093(2016)01-0097-06

2015-06-10

國(guó)家自然科學(xué)基金項(xiàng)目(61273083、61374012)

路遙(1987—),男,博士研究生。E-mail:luyaosacred@126.com;董朝陽(yáng)(1966—),男,教授,博士生導(dǎo)師。E-mail:dongchaoyang@buaa.edu.cn