基于改進(jìn)遺傳算法的聯(lián)合作戰(zhàn)火力打擊計(jì)劃優(yōu)化問題研究

劉 昊,張 策,孫 奇

(國防大學(xué)聯(lián)合作戰(zhàn)學(xué)院，河北 石家莊 050000)

在聯(lián)合作戰(zhàn)籌劃中,如何高效、科學(xué)地?cái)M制聯(lián)合作戰(zhàn)火力打擊計(jì)劃,是戰(zhàn)場(chǎng)上能否在有效時(shí)間內(nèi)發(fā)揮聯(lián)合作戰(zhàn)諸軍兵種部隊(duì)作戰(zhàn)效能的關(guān)鍵因素[1]。一份優(yōu)秀的聯(lián)合作戰(zhàn)火力打擊計(jì)劃,能夠使諸軍兵種部隊(duì)形成火力打擊合力,最大限度地破敵體系,同時(shí)均衡分擔(dān)各部隊(duì)任務(wù)壓力,適度留存機(jī)動(dòng)彈藥,對(duì)于提升部隊(duì)整體作戰(zhàn)能力至關(guān)重要,因此聯(lián)合作戰(zhàn)火力打擊計(jì)劃的優(yōu)化問題成為軍事研究的熱點(diǎn)。聯(lián)合作戰(zhàn)火力打擊計(jì)劃優(yōu)化問題的核心在于解決火力分配(Weapon-Target Assignment, WTA)問題,即根據(jù)戰(zhàn)場(chǎng)實(shí)時(shí)感知并動(dòng)態(tài)生成的兵力配置表、目標(biāo)打擊表、毀傷能力表,將特定種類和數(shù)目的火力打擊部隊(duì)和火力打擊目標(biāo)實(shí)施點(diǎn)對(duì)點(diǎn)分配,以實(shí)現(xiàn)火力打擊的過程[2]。聯(lián)合火力打擊計(jì)劃優(yōu)化的難點(diǎn)在于動(dòng)態(tài)火力分配[3]的可能性眾多,優(yōu)化計(jì)算復(fù)雜度高,這是一類典型的有約束組合優(yōu)化問題，即NP-hard問題[4],僅靠傳統(tǒng)的手工匹配方法無法在給定時(shí)間內(nèi)找到最優(yōu)計(jì)劃,必須構(gòu)造新型算法縮短尋優(yōu)時(shí)間,以便在有限時(shí)間內(nèi)找到相對(duì)最優(yōu)的火力打擊計(jì)劃。

動(dòng)態(tài)火力分配問題最早由Hosein等人提出[5],目前國內(nèi)外研究人員已經(jīng)探索了多種優(yōu)化方法,應(yīng)用較多的方法主要有:滾動(dòng)窗口規(guī)劃方法[6]、免疫算法[7]、神經(jīng)網(wǎng)絡(luò)法[8]、蟻群算法[9]、粒子群算法[10]、A*算法[11]、模擬退火算法[12]等。上述算法都有各自的理論脈絡(luò)和算法優(yōu)勢(shì),但從總體看,各算法都存在著某一或某些方面的不足,如算法計(jì)算量大、參數(shù)調(diào)節(jié)復(fù)雜困難、尋優(yōu)效率低下、易落入局部最優(yōu)解、收斂性不強(qiáng)、遷移能力差等問題。相比之下,遺傳算法在解決復(fù)雜系統(tǒng)尋優(yōu)問題具有魯棒、靈活、適應(yīng)能力強(qiáng)等優(yōu)點(diǎn),因此被廣泛應(yīng)用到動(dòng)態(tài)火力分配問題求解中,并取得了不錯(cuò)的效果。標(biāo)準(zhǔn)遺傳算法也存在著諸如種群規(guī)模大、收斂速度不可控、易于陷入局部最優(yōu)等問題,針對(duì)此類弊端,本文提出了使用基因群落預(yù)評(píng)分和多種群并行演化方法改進(jìn)的遺傳算法,以提升演化效率和最優(yōu)個(gè)體評(píng)估分值,最后通過仿真實(shí)驗(yàn)驗(yàn)證了改進(jìn)遺傳算法解決火力打擊計(jì)劃優(yōu)化問題的可行性和高效性。

1 火力打擊計(jì)劃優(yōu)化問題描述

火力打擊計(jì)劃優(yōu)化問題可以分解為擬制、評(píng)估、優(yōu)選3個(gè)環(huán)節(jié),本文主要研究了如何使用改進(jìn)遺傳算法在眾多計(jì)劃中優(yōu)選出最優(yōu)計(jì)劃,為了進(jìn)行仿真實(shí)驗(yàn)實(shí)現(xiàn)優(yōu)選環(huán)節(jié),有必要構(gòu)建出科學(xué)的擬制和簡(jiǎn)要的評(píng)估模型。

1.1 火力打擊計(jì)劃擬制模型介紹

火力打擊計(jì)劃的擬制環(huán)節(jié)就是利用兵力配置表、目標(biāo)打擊表和毀傷能力表擬制聯(lián)合作戰(zhàn)火力打擊計(jì)劃的過程。為了描述貼合實(shí)際,設(shè)計(jì)作戰(zhàn)想定如下:我部擔(dān)負(fù)聯(lián)合火力打擊任務(wù),所屬部隊(duì)包括2個(gè)武裝直升機(jī)中隊(duì)、3個(gè)轟炸機(jī)中隊(duì)、2個(gè)常導(dǎo)發(fā)射架以及1個(gè)遠(yuǎn)火營(yíng)(含3個(gè)遠(yuǎn)火連),兵力配置如表1所示。

表1 兵力配置表

當(dāng)面之?dāng)碁樗{(lán)軍機(jī)步旅,正在組織陣地防御,企圖扼守主要防御地段,阻我向縱深發(fā)展進(jìn)攻,目標(biāo)打擊表如表2所示。

表2 目標(biāo)打擊表

要求綜合計(jì)劃席參謀根據(jù)各部隊(duì)毀傷能力(表3),擬制聯(lián)合作戰(zhàn)火力打擊計(jì)劃。

表3 毀傷能力表

綜合計(jì)劃席受領(lǐng)任務(wù)后,應(yīng)第一時(shí)間依據(jù)指揮員決心意圖為目標(biāo)清單實(shí)施打擊先后排序,而后分析我現(xiàn)有火力打擊力量的特點(diǎn),并根據(jù)火力打擊能力表為各參戰(zhàn)部隊(duì)賦予火力打擊任務(wù),最后匯總生成聯(lián)合作戰(zhàn)火力打擊計(jì)劃,見表4。

表4 初始火力打擊計(jì)劃

1.2 火力打擊計(jì)劃評(píng)估模型介紹

為了實(shí)現(xiàn)火力打擊計(jì)劃的優(yōu)選,本文構(gòu)建出簡(jiǎn)易的火力打擊計(jì)劃評(píng)估模型,主要設(shè)計(jì)了如下評(píng)估指標(biāo):

1)火力打擊執(zhí)行時(shí)長(zhǎng)指標(biāo)(T)；

2)各部隊(duì)出動(dòng)次數(shù)指標(biāo)(C)；

3)目標(biāo)重要程度指標(biāo)(Z)；

4)完成任務(wù)情況指標(biāo)(W)。

評(píng)估過程可描述為:

設(shè)共有m支參與火力打擊的部隊(duì),對(duì)n個(gè)目標(biāo)實(shí)施火力打擊;選取第i支部隊(duì)對(duì)各目標(biāo)實(shí)施火力打擊,共執(zhí)行ki次打擊任務(wù),當(dāng)前敵第j個(gè)目標(biāo)。設(shè)第i支部隊(duì)單次執(zhí)行任務(wù)時(shí)長(zhǎng)為ui,任務(wù)間隔時(shí)長(zhǎng)為vi;則火力打擊執(zhí)行時(shí)長(zhǎng)評(píng)估指標(biāo)T的計(jì)算公式為

(1)

設(shè)第i支部隊(duì)可執(zhí)行火力打擊任務(wù)的總次數(shù)為si次;則各部隊(duì)出動(dòng)次數(shù)評(píng)估指標(biāo)C的計(jì)算公式為

(2)

設(shè)目標(biāo)打擊清單中只包含一、二級(jí)目標(biāo),一級(jí)目標(biāo)數(shù)目為h,火力打擊計(jì)劃中對(duì)一級(jí)目標(biāo)實(shí)際打擊的數(shù)目為p;則對(duì)目標(biāo)打擊的重要程度評(píng)估指標(biāo)Z的算法描述如圖1所示。

圖1 重要程度評(píng)估指標(biāo)Z算法描述圖

設(shè)對(duì)第j個(gè)目標(biāo)實(shí)施火力打擊的總時(shí)長(zhǎng)為oj;則完成任務(wù)情況評(píng)估指標(biāo)W的算法描述如圖2所示。

圖2 完成任務(wù)評(píng)估指標(biāo)W計(jì)算流程圖

滿足約束條件:目標(biāo)坐標(biāo)必須在對(duì)該目標(biāo)執(zhí)行火力打擊任務(wù)的部隊(duì)射程內(nèi),如不在射程內(nèi)則去除該項(xiàng)打擊任務(wù)。設(shè)第i支部隊(duì)的打擊半徑為bi,坐標(biāo)為(xmi,ymi);準(zhǔn)備打擊第j個(gè)目標(biāo)的坐標(biāo)為(xnj,ynj)。約束公式如下:

(3)

綜合評(píng)估得分F為各指標(biāo)的經(jīng)驗(yàn)加權(quán)求和,計(jì)算公式為

(4)

以表X火力打擊計(jì)劃為例,計(jì)算評(píng)估過程如下:

1)計(jì)算火力打擊執(zhí)行時(shí)長(zhǎng)指標(biāo)T。根據(jù)表X計(jì)算出各部隊(duì)執(zhí)行時(shí)長(zhǎng)為{5,35,16,28,40,11,21,27,11,43},根據(jù)公式(1)可計(jì)算出T=46.51分。

2)計(jì)算各部隊(duì)出動(dòng)次數(shù)指標(biāo)C。根據(jù)表X計(jì)算出各部隊(duì)出動(dòng)次數(shù)ki為{1,3,2,3,4,2,3,4,2,6},查兵力配置表得到火力打擊總次數(shù)si為{2,3,2,3,2,2,4,3,4,3},m=10,根據(jù)公式(2)可計(jì)算出C=-15.83分。

3)計(jì)算目標(biāo)重要程度指標(biāo)Z。首先根據(jù)表X確定各目標(biāo)的打擊先后排名,第一名排名31,而后依次遞減,各目標(biāo)按打擊先后排序?yàn)閧6,2,12,3,14,5,9,0,0,8,15,11,4,10,0,17,13,20,0,19,1,0,0,0,0,0,7,21,22,18,16};各目標(biāo)實(shí)際排名分值=245分;最佳排名分值=231.4分;根據(jù)圖1可計(jì)算出Z=100分。

4)計(jì)算完成任務(wù)情況指標(biāo)W。根據(jù)火力計(jì)劃確定執(zhí)行該計(jì)劃后對(duì)各目標(biāo)完成任務(wù)情況為{100,100,100,100,100,100,100,0,0,50,50,50,50,100,0,50,100,100,0,100,100,0,0,0,0,0,50,100,100,100,100},各目標(biāo)實(shí)施火力打擊的時(shí)長(zhǎng)為{20,11,9,4,1,4,3,0,0,5,5,4,3,1,0,4,28,4,0,3,3,0,0,0,0,0,3,5,3,3,3},則根據(jù)圖2可計(jì)算出Z=51.61分。

5)計(jì)算綜合評(píng)估分值F。根據(jù)公式(4)可計(jì)算出F=48.27分。

2 改進(jìn)遺傳算法原理

2.1 標(biāo)準(zhǔn)遺傳算法介紹

遺傳算法是由美國Michigan大學(xué)的John Holland與其同事于1975年首先提出,該算法是一種借鑒生物演化規(guī)律而設(shè)計(jì)的隨機(jī)搜索方法,從自然生態(tài)系統(tǒng)中生物對(duì)外界環(huán)境的復(fù)雜適應(yīng)過程入手,模擬生物進(jìn)化機(jī)制創(chuàng)造人工的生物演化進(jìn)程,進(jìn)而構(gòu)造出人工的生物演化系統(tǒng)模型[13]。由于遺傳算法簡(jiǎn)單易用,魯棒性好,具有強(qiáng)有力的全局搜索能力,且算法簡(jiǎn)單、易于編程,目前已經(jīng)成為一種解決眾多實(shí)際優(yōu)化問題的有效工具[14]。

標(biāo)準(zhǔn)遺傳算法是將優(yōu)化問題同生物個(gè)體建立對(duì)應(yīng)關(guān)系,將問題中的優(yōu)化參數(shù)用基因編碼替代,進(jìn)而將優(yōu)化問題映射為生物群體中找最優(yōu)個(gè)體的過程。而后利用基因突變、有性繁殖、適應(yīng)評(píng)估、優(yōu)選下一個(gè)個(gè)體等過程建立生物演化循環(huán),使種群不斷演化,種群內(nèi)的最優(yōu)個(gè)體評(píng)分分值逐漸趨向于最優(yōu)解[15]。具體算法描述如下:

1)設(shè)置初始個(gè)體。隨機(jī)生成一個(gè)初始個(gè)體,本文中可表示為一套具體的聯(lián)合作戰(zhàn)火力打擊計(jì)劃(如表4)。將火力計(jì)劃的每行子任務(wù)描述為一個(gè)基因,則多個(gè)基因共同組成了初始個(gè)體。圖3表示初始個(gè)體結(jié)構(gòu),個(gè)體由基因、壽命、評(píng)估分值組成。

圖3 初始個(gè)體結(jié)構(gòu)圖

2)繁殖為新種群。通過基因突變、兩性基因交換和兩性基因拆補(bǔ)使最初個(gè)體自我繁殖,擴(kuò)充為1000個(gè)個(gè)體。設(shè)個(gè)體Am和個(gè)體An在第k位上對(duì)應(yīng)的基因分別為amk和ank,b取[0,1]之間的隨機(jī)整數(shù),b=0表示基因不交換,b=1表示基因交換;則交換的具體方法為:

(5)

設(shè)基因拆補(bǔ)為將amk拆下,插補(bǔ)到ank后,b=0表示基因不拆補(bǔ),b=1表示基因拆補(bǔ);則拆補(bǔ)的具體方法為:

(6)

3)計(jì)算種群中個(gè)體的評(píng)估分值。按照火力打擊計(jì)劃評(píng)估模型對(duì)每個(gè)個(gè)體計(jì)算評(píng)估分值,分值越高表示該個(gè)體在群體中的適應(yīng)性越強(qiáng)。

4)優(yōu)選個(gè)體。使用輪盤法在種群中優(yōu)選出100個(gè)個(gè)體,使高評(píng)分個(gè)體有較大概率留存,低評(píng)分個(gè)體也有小概率的留存機(jī)會(huì)。同時(shí)刪除壽命達(dá)到上限的個(gè)體(留存超過5代個(gè)體),防止超級(jí)個(gè)體破壞種群基因多樣性。設(shè)第i個(gè)體評(píng)分分值為Fi,pi表示個(gè)體被選中的概率;輪盤法的算法描述:

(7)

5)演化終止條件判斷。如滿足“種群優(yōu)選個(gè)體高低分差為<0.5”條件,則退出循環(huán),輸出最佳結(jié)果;否則執(zhí)行2)。

圖4 遺傳算法基本流程圖

2.2 改進(jìn)遺傳算法介紹

雖然標(biāo)準(zhǔn)遺傳算法為解決火力打擊計(jì)劃優(yōu)化問題提供了可行性解決方案,但它還存在兩個(gè)不容忽視的缺陷:未成熟收斂和遺傳后期的收斂遲滯,前者影響算法精確度,后者影響算法執(zhí)行效率。為此,本文采用基因群落預(yù)評(píng)分和多種群并行演化的方法改進(jìn)標(biāo)準(zhǔn)遺傳算法,具體改進(jìn)說明如下。

1)基因群落預(yù)評(píng)分

標(biāo)準(zhǔn)遺傳算法的基因變異的隨機(jī)發(fā)生的,不存在方向可控性,而實(shí)際經(jīng)驗(yàn)告訴我們,絕大多數(shù)的基因變異對(duì)種群演化是無意義的,因此在基因概念基礎(chǔ)上,引入基因群落概念?；蛉郝溆蓭讉€(gè)基因聚集組成,可完成一項(xiàng)獨(dú)立功能,如在聯(lián)合作戰(zhàn)火力打擊計(jì)劃的優(yōu)化問題中,基因代表了“某一時(shí)刻由某一部隊(duì)打擊某一目標(biāo)”,基因群落則由多個(gè)相同部隊(duì)基因組成,代表了“整個(gè)火力打擊過程中某一部隊(duì)打擊了哪些目標(biāo)”,簡(jiǎn)而言之,基因群落是由一支部隊(duì)能夠執(zhí)行的火力打擊任務(wù)序列構(gòu)成，如圖5所示。則對(duì)火力打擊計(jì)劃的總體評(píng)分,可拆解為對(duì)各基因群落的單獨(dú)評(píng)分之和,而對(duì)基因群落的預(yù)先評(píng)分可以有效剔除標(biāo)準(zhǔn)遺傳算法隨機(jī)產(chǎn)生的低評(píng)分基因群落。

圖5 基因群落示意圖

2)多種群并行演化

標(biāo)準(zhǔn)遺傳算法由于演化效果的不確定性,導(dǎo)致每次演化產(chǎn)生的最優(yōu)個(gè)體評(píng)估分值都不相同,因此考慮在單種群演化基礎(chǔ)上,引入多種群并行演化概念。設(shè)有多個(gè)種群互不干擾的獨(dú)立演化,則會(huì)產(chǎn)生多個(gè)互相獨(dú)立的最優(yōu)個(gè)體,在時(shí)間條件允許情況下,取各種群產(chǎn)生的最優(yōu)個(gè)體中的最高評(píng)估分值個(gè)體為最終輸出結(jié)果。多種群并行演化體現(xiàn)了以降低算法效率提升算法精確度的思想,即“多次重復(fù)演化,取最優(yōu)結(jié)果”。

改進(jìn)的遺傳算法執(zhí)行步驟(見圖6)如下:

1)設(shè)置最初個(gè)體。

2)設(shè)置基因群落集合。對(duì)每支部隊(duì)能夠打擊到的目標(biāo)產(chǎn)生對(duì)應(yīng)的基因群落,并對(duì)每個(gè)群落計(jì)算群落評(píng)分,優(yōu)選高評(píng)分的基因群落組成基因群落集合。

3)繁殖為新種群。將變異對(duì)象從基因變異改為從基因群落集合中隨機(jī)選取一支部隊(duì)的基因群落,其他同標(biāo)準(zhǔn)遺傳算法。

4)計(jì)算種群中個(gè)體的評(píng)估分值。

5)優(yōu)選個(gè)體。

6)演化終止條件判斷。

7)重復(fù)演化。將最優(yōu)個(gè)體存入最優(yōu)個(gè)體集合,判斷時(shí)間是否允許,如允許則返回1)重復(fù)演化;否則退出循環(huán),輸出最優(yōu)個(gè)體集合中的最高分個(gè)體。

圖6 改進(jìn)遺傳算法基本流程圖

3 仿真實(shí)驗(yàn)結(jié)果分析

仿真實(shí)驗(yàn)環(huán)境設(shè)置如下:設(shè)定每代種群上限1000個(gè),優(yōu)選種群為100個(gè);變異發(fā)生概率為每個(gè)新個(gè)體可隨機(jī)產(chǎn)生1次基因突變;遺傳終止條件為優(yōu)選個(gè)體總最高低分差值小于0.5(意味著種群中所有個(gè)體分值都演化為最高分值)。本文實(shí)驗(yàn)計(jì)算機(jī)配置:聯(lián)想筆記本電腦運(yùn)行程序,配置:Intel酷睿雙核CPU T7300 2.0 GHz;3G內(nèi)存;32位Win7操作系統(tǒng);vc6.0編程環(huán)境。為驗(yàn)證改進(jìn)遺傳算法的有效性,選取標(biāo)準(zhǔn)遺傳算法作為參考對(duì)象,在實(shí)驗(yàn)過程中,兩種算法的控制參數(shù)相同,包括種群規(guī)模、變異概率、遺傳終止條件等。

圖7中為兩種算法對(duì)比的實(shí)驗(yàn)結(jié)果,其中橫坐標(biāo)表示演化代數(shù),縱坐標(biāo)表示各代最優(yōu)個(gè)體分值。從圖中可以看出,隨著演化代數(shù)的增多,兩種算法都收斂到最高分值,但改進(jìn)遺傳算法的收斂分值略高于標(biāo)準(zhǔn)遺傳算法的收斂分值,并且收斂曲線更加平滑,不存在明顯波動(dòng),證明改進(jìn)遺傳算法能突破局部最優(yōu)解限制,在多次重復(fù)演化中逼近全局最優(yōu)解。

圖7 各代演化中最優(yōu)個(gè)體分值比較

圖8中為兩種算法各代高低分差對(duì)比結(jié)果,其中橫坐標(biāo)表示演化代數(shù),縱坐標(biāo)表示各代最高分值個(gè)體和最低分值個(gè)體的高低分差。從圖中可以看出,隨著演化代數(shù)的增多,標(biāo)準(zhǔn)遺傳算法的高低分差逐漸歸于0,在各代演化中并無明顯波動(dòng),演化計(jì)算逐漸趨向于無意義的時(shí)間消耗;而改進(jìn)遺傳算法采用了多種群并行演化策略,各代高低分差具有周期性歸于0的波動(dòng)特點(diǎn),算法通過一次次的演化尋找全局最優(yōu)解。從實(shí)驗(yàn)結(jié)果可以得出結(jié)論:在時(shí)間允許的情況下,改進(jìn)遺傳算法具備無限逼近全局最優(yōu)解的能力,而標(biāo)準(zhǔn)遺傳算法可能陷入局部最優(yōu)解。

圖8 各代高低分差比較

表5中為兩種算法各代時(shí)間消耗對(duì)比結(jié)果,在演化代數(shù)相同的前提下,標(biāo)準(zhǔn)遺傳算法平均每代演化用時(shí)0.98 s,改進(jìn)遺傳算法平均每代演化用時(shí)0.76 s,改進(jìn)遺傳算法每代演化的平均用時(shí)明顯低于標(biāo)準(zhǔn)遺傳算法。從實(shí)驗(yàn)結(jié)果可以得出結(jié)論:基因群落預(yù)評(píng)分能夠有效縮短演化時(shí)長(zhǎng),提升遺傳算法的演化效率,提速比例可達(dá)28.9%。

表5 時(shí)間消耗比較/s

表6 改進(jìn)遺傳算法生成最優(yōu)火力打擊計(jì)劃

表6為以表4為初始火力打擊計(jì)劃,經(jīng)過改進(jìn)遺傳算法演化產(chǎn)生的最優(yōu)火力打擊計(jì)劃?？梢钥闯?相比于傳統(tǒng)手工制作的火力打擊計(jì)劃而言,改進(jìn)遺傳算法生成的火力打擊計(jì)劃任務(wù)執(zhí)行時(shí)長(zhǎng)更短、各部隊(duì)任務(wù)分配更均勻、對(duì)目標(biāo)體系破壞性更強(qiáng)、預(yù)留彈藥更合理、綜合評(píng)估分值更高。對(duì)比結(jié)果如表7所示。

表7 初始計(jì)劃和最優(yōu)計(jì)劃對(duì)比

4 結(jié)束語

本文針對(duì)聯(lián)合作戰(zhàn)火力打擊計(jì)劃優(yōu)化中的動(dòng)態(tài)火力分配問題,提出使用改進(jìn)遺傳算法自主生成最優(yōu)火力打擊計(jì)劃的方法。該方法創(chuàng)新點(diǎn)主要有:提出用遺傳算法的思路解決聯(lián)合作戰(zhàn)火力打擊計(jì)劃的優(yōu)化問題,并設(shè)計(jì)簡(jiǎn)易的火力打擊計(jì)劃評(píng)估模型驗(yàn)證方法可行性;通過設(shè)計(jì)基因群落預(yù)評(píng)分機(jī)制,實(shí)現(xiàn)對(duì)無意義的基因突變的過濾,提升了遺傳算法的執(zhí)行效率;通過設(shè)計(jì)多種群并行演化機(jī)制,有效地克服了遺傳算法早熟缺陷。實(shí)驗(yàn)表明,將該方法應(yīng)用到聯(lián)合作戰(zhàn)火力打擊計(jì)劃優(yōu)化操作中,能有效提高火力打擊計(jì)劃擬制的針對(duì)性和時(shí)效性。