改進的遺傳算法求解火力分配優化問題

董朝陽,路遙,王青

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

改進的遺傳算法求解火力分配優化問題

董朝陽1,路遙1,王青2

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

提出一種求解火力分配優化問題的改進遺傳算法。基于目標函數的相對大小構造適應度函數,較傳統的界限構造法更加顯著地體現染色體之間的差異,使得優良染色體更容易被選中,從而提高算法的收斂精度。采用基于父代染色體相似度的啟發式遺傳算子優化遺傳運算,靈活、有針對性地對父代染色體進行交叉或變異操作,在防止算法陷入局部最優的同時保證種群的更新速度。仿真實驗對比結果分析表明所設計的改進算法具有更高效的尋優能力。

兵器科學與技術;整數規劃;火力分配;遺傳算法;適應度函數

DOI:10.3969/j.issn.1000-1093.2016.01.015

0 引言

火力分配(WTA)是指根據作戰目的、戰場態勢和武器性能等因素,將一定類型和數量的火力單元以某種準則進行分配,攻擊一定數量敵方目標的過程。WTA是戰場指揮當中的重要環節,是決定作戰效果的關鍵因素[1]。

WTA問題屬于一類NP-hard問題。當前國內外研究成果多以對目標的毀傷概率最大為目的,通過智能優化算法,如啟發式遺傳算法[2]、蟻群遺傳算法[3]、模擬退火遺傳算法[4]、混合變鄰域搜索算法[5]、粒子群算法[6]等對模型進行求解,其中以遺傳算法為基礎設計搜索算法居多。遺傳算法是應用最為廣泛的智能優化算法之一,具有很強的全局搜索能力;但其在實際應用中也存在著進化慢、易早熟收斂等問題。實際研究表明,適應度函數的選取和遺傳算子調節機制的設置是影響遺傳算法性能的關鍵。適應度函數選取不當將會嚴重影響算法的計算效率,而傳統的遺傳算法存在交叉變異概率在種群進化過程中固定不變的不足。

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

本文針對一類以對目標的毀傷概率最大為目的的WTA問題,采用改進的遺傳算法進行求解。通過設計合適的適應度函數以及自適應的變異概率調節機制,提高了算法的尋優能力,避免算法過早地陷入局部極值。

1 WTA問題的數學描述

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

WTA的目的為根據作戰要求,通過攻擊最大化地對目標造成毀傷,可描述為

式中:V表示目標函數。此外,模型還應滿足毀傷下界約束:

式中:βj表示第j個目標的毀傷下界。

2 基于模擬退火遺傳算法的WTA實現

2.1 編碼

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

式中:yk為0～n之間的整數,稱為元素。yk=j表示將第k個火力單元分配給第j個目標;yk=0表示第k個火力單元沒有分配給任一目標。這種編碼方式能夠描述以上3類情況WTA問題的同時不會產生“不合法"的染色體。

2.2 適應度函數

輪盤賭是最常見的從種群中選擇父代染色體的策略,它能夠定量地表示染色體之間適應度的差異[13]。在輪盤賭選擇方式下,染色體被選中的概率與其適應度值大小緊密相關。本文采用界限構造法[7]設計適應度函數,可表示為

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

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

2.3 遺傳算子

交叉算子采用多點交叉的方式。對于兩個選定的父代染色體y1和y2:

隨機選取3個切點,交換切點間的子串,得到新的子代個體y＇1和y＇2:

變異采用簡單的替換方式實現。當一個染色體進行變異操作時,隨機選取染色體編碼中的3個元素,在合理的范圍內進行替換:

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

本文根據父代染色體之間的相似度來決定是否進行交叉和變異操作。從算法進行交叉和變異操作的目的來看,交叉是為了產生和父代染色體不同的子代染色體,通過比較保留適應度好的個體從而使種群不斷進化。但是,當父代染色體之間編碼差異很小或沒有差異,屬于“近親"時,進行交叉操作產生的子代染色體與父代染色體之間的差異也會很小甚至沒有差異;此時,應通過變異操作使得子代染色體與父代染色體之間產生差異,從而增加種群的多樣性,擴大對解空間的搜索范圍,這也是算法中變異操作行為的目的。總的來說,當父代染色體之間差異度較小時,算法應進行交叉操作;當父代染色體之間差異度較大時,應進行變異操作。用D(y1、y2)表示y1、y2之間的相似度,其值為向量(y1-y2)中0元素的個數。D(y1,y2)越小表示y1、y2之間差異越大,進行交叉操作后得到新的子代染色體幾率越高; D(y1,y2)越大表示y1、y2之間差異越小,進行交叉操作越不容易得到新的子代染色體,應進行變異操作增加種群的多樣性。基于上述原因,用變異操作閥值φ代替傳統的變異概率pa,判斷是否進行變異操作;當D(y1,y2)≥φ時,認為選取的父代染色體的相似度足夠高,算法進行變異操作。

2.4 最優個體保持策略

本文采用最優個體保持策略對每一代種群中的最優個體進行保護,避免其在之后進行的選擇、交叉或變異過程中被破壞。具體方式為:用前一代種群中適應度值最大的染色體代替新一代種群中目標函數值最小的染色體。

2.5 算法描述

采用改進的遺傳算法求解WTA問題的具體步驟如下:

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

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

步驟3 計算種群中染色體的適應度值,采用輪盤賭方式選擇待交叉的父代染色體。

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

步驟5 保留最優個體。計算子代種群的適應度值,用父代種群中的最優個體替換子代種群中適應度值最差的個體。

步驟6 迭代次數加一,判斷算法終止條件。若迭代次數達到最大迭代次數Tmax,則輸出最優解,結束算法;否則轉步驟3.

3 算例仿真和結果分析

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

表1 毀傷概率及目標威脅度參數Tab.1 Damage probability and target threat parameters

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

3.1 不同適應度函數比較

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

表2 不同適應度值計算方式下的優化結果Tab.2 Optimization results in different fitness value calculation modes

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

圖1 第一組仿真算例結果對比Fig.1 Comparison of simulation results in Group 1

3.2 不同變異算子比較

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

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

圖2 第二組仿真算例結果對比Fig.2 Comparison of simulation results in Group 2

圖3 仿真耗時比較Fig.3 Comparison of simulation times

圖4 本文算法總變異次數統計Fig.4 Total mutation times statistics of the proposed algorithm

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

表3 不同變異算子下的優化結果Tab.3 Optimization results in different variation operators

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

4 結論

本文針對一類以對目標的毀傷概率最大為目的的WTA問題,提出了一種改進的遺傳算法,并通過仿真實驗得到了以下結論:

1)適應度函數的選擇影響算法的尋優精度。本文構造的適應度函數較傳統的界限構造法能夠提高優秀染色體被選中的概率,從而提高了種群的質量,對算法尋優能力產生積極影響。

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

References)

[1]張蛟,王中許,陳黎,等.具有多次攔截時機的防空火力分配建模及其優化方法研究[J].兵工學報,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]賀小亮,畢義明.基于模擬退火遺傳算法的編隊對地攻擊WTA建模與優化[J].系統工程與電子技術,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]燕樂緯,陳洋洋,周云.基于數字序列編碼遺傳算法的高層結構黏滯阻尼器優化布置[J].振動與沖擊,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].控制與決策,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]汪定偉,王俊偉,王洪峰,等.智能優化算法[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

國家自然科學基金項目(61273083、61374012)

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