一種基于混合算法的火力規(guī)劃方法

沈 馳，浦方韜

（中國(guó)電子科技集團(tuán)第二十八研究所，南京 210007）

0 引言

火力規(guī)劃是根據(jù)作戰(zhàn)任務(wù)，戰(zhàn)場(chǎng)態(tài)勢(shì)以及武器裝備毀傷能力，按照一定的分配規(guī)則，將敵方目標(biāo)分配給我方火力單元的過(guò)程。戰(zhàn)前與戰(zhàn)時(shí)的火力規(guī)劃可以有效提高我方火力單元的打擊效率，節(jié)約火力資源，對(duì)作戰(zhàn)效果有重要影響。

火力規(guī)劃問題已被證明是NP-hard 問題，其求解難度隨著問題復(fù)雜程度的增大呈指數(shù)上升。目前，國(guó)內(nèi)外對(duì)于這類問題的求解主要采用云遺傳算法［1］、蟻群算法［2］、多樣性粒子群算法［3］、離散粒子群算法［4］、量子免疫克隆算法［5］以及禁忌搜索算法［6］等。遺傳算法是由美國(guó)Michigan 大學(xué)的John Holland 教授根據(jù)生物進(jìn)化中的信息遺傳與自然選擇機(jī)制提出的一種優(yōu)化算法。遺傳算法具有較好的全局搜索能力，但存在進(jìn)化較慢，易早熟收斂的問題。并且，隨著約束條件的加入和問題復(fù)雜程度的增大，遺傳算法的搜索效率不斷降低。

采用遺傳算法進(jìn)行火力規(guī)劃存在兩個(gè)主要問題，一是火力規(guī)劃問題具有多個(gè)約束條件，對(duì)于約束條件的處理，文獻(xiàn)［7］提出了采用懲罰函數(shù)的方法，文獻(xiàn)［8］提出了對(duì)子代個(gè)體進(jìn)行合法性判斷的方法。二是當(dāng)火力規(guī)劃問題涉及的火力單元與目標(biāo)數(shù)量較多，問題較為復(fù)雜時(shí)，遺傳算法搜索效率較低，文獻(xiàn)［9-10］提出了加快收斂的方式，但在火力規(guī)劃問題中適用性不強(qiáng)。因此，需探尋一種改進(jìn)算法以解決上述問題。

本文提出了一種基于貪心策略和改進(jìn)遺傳算法的混合算法，通過(guò)編碼方式和自體雜交算子處理約束條件，將貪心策略應(yīng)用于種群的初始化過(guò)程和一定復(fù)雜程度以上問題的求解。本文提出的混合算法針對(duì)不同復(fù)雜程度的火力規(guī)劃問題均有較好的尋優(yōu)能力，并大大減少了算法的運(yùn)行時(shí)間。

1 火力規(guī)劃問題描述

現(xiàn)代戰(zhàn)爭(zhēng)中，戰(zhàn)前規(guī)劃在大規(guī)模戰(zhàn)斗中扮演了重要角色，根據(jù)戰(zhàn)前的情報(bào)信息，我方對(duì)敵方各目標(biāo)進(jìn)行毀傷分析，獲得我方各火力單元摧毀該目標(biāo)所需要的彈藥種類與數(shù)量。通過(guò)戰(zhàn)前火力規(guī)劃形成打擊方案，將敵方各目標(biāo)分配給我方火力單元實(shí)施打擊任務(wù)，明確我方火力單元達(dá)成預(yù)期毀傷任務(wù)所需的彈藥種類與數(shù)量，為我方彈藥保障提供支持。

本文討論的火力規(guī)劃問題，是大規(guī)模作戰(zhàn)的戰(zhàn)前火力規(guī)劃過(guò)程，對(duì)于作戰(zhàn)進(jìn)程中因我方火力單元被摧毀而產(chǎn)生的重新規(guī)劃及火力轉(zhuǎn)移等問題可通過(guò)分（群）隊(duì)級(jí)的臨機(jī)規(guī)劃解決，因此，在文中不作具體討論。

現(xiàn)假設(shè)我方火力單元數(shù)量為M，已探測(cè)到敵方目標(biāo)數(shù)量為N，敵方目標(biāo)數(shù)量大于我方火力單元數(shù)量（N＞M），定義此火力規(guī)劃問題的復(fù)雜程度為M*N。要求將敵方目標(biāo)合理分配給我方火力單元，每個(gè)火力單元對(duì)各目標(biāo)完成預(yù)定打擊任務(wù)所需消耗的彈藥數(shù)量為Ci，要求完成打擊任務(wù)所需火力資源最少，即

式中，T 為目標(biāo)函數(shù)。此外，火力規(guī)劃問題還需滿足以下3 個(gè)約束條件：

1）每個(gè)目標(biāo)僅由一個(gè)火力單元實(shí)施打擊任務(wù)；

3）火力單元完成打擊任務(wù)所需的彈藥數(shù)量不能超過(guò)該火力單元可攜行彈藥總量。

2 基于貪心策略和改進(jìn)遺傳算法的混合算法的實(shí)現(xiàn)

2.1 貪心策略

通過(guò)某種算法可以求出火力單元對(duì)各目標(biāo)完成既定打擊任務(wù)所需消耗的彈藥數(shù)量，這些數(shù)據(jù)可以組成一個(gè)M*N 的矩陣P，矩陣元素Pij表示第i個(gè)火力單元對(duì)第j 個(gè)目標(biāo)實(shí)施打擊所消耗的彈藥數(shù)量。

在最優(yōu)分配方案中，矩陣P 的每一列有且僅有一個(gè)Pij被選中，且被選中的Pij為該列最小或較小值，因此，引入貪心策略來(lái)進(jìn)行快速選擇。具體步驟為：

1）隨機(jī)選取第j（j∈［1，N］）列為起始列，選取第j 列的最小值；

2）從第j 列向后，逐列選取符合約束條件的該列最小值；

3）從第j 列向前，逐列選取符合約束條件的該列最小值。

2.2 編碼

在相似問題的求解中，文獻(xiàn)［11］提出二進(jìn)制編碼方式，文獻(xiàn)［12-13］提出整數(shù)編碼方式，但在雜交與變異過(guò)程中，這兩種編碼方式均會(huì)破壞所有3 個(gè)約束條件。因此，為解決破壞約束條件的問題，提出一種編碼方式：染色體表示為與矩陣P 大小一致的分配矩陣Q，其中Qij表示第i 個(gè)火力單元對(duì)第j 個(gè)目標(biāo)的打擊狀態(tài)，采用二進(jìn)制編碼，1 為打擊，0 為不打擊。矩陣中每個(gè)元素為一個(gè)基因，每一行為一個(gè)基因組。

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

要求以最少火力資源消耗完成既定打擊任務(wù)。因此，選擇式（1）中目標(biāo)函數(shù)作為適應(yīng)度函數(shù)，即

2.4 種群初始化

遺傳算法中常隨機(jī)生成一定數(shù)量的合法染色體作為初始種群。當(dāng)問題復(fù)雜程度增大時(shí)，采用隨機(jī)初始化的遺傳算法收斂速度減緩，無(wú)法保證在一定代數(shù)內(nèi)收斂。由2.1 中分析可知，采用貪心策略產(chǎn)生的個(gè)體均為適應(yīng)度較為優(yōu)秀的個(gè)體，因此，初始種群的部分染色體采用貪心策略產(chǎn)生以加快算法收斂速度，剩余染色體隨機(jī)生成來(lái)維持初始種群的多樣性。

2.5 自體雜交算子

采用2.2 中定義的染色體，當(dāng)兩個(gè)染色體隨機(jī)交換某個(gè)基因或基因組時(shí)，都可能破壞所有約束條件。因此，本文提出自體雜交算子以減少破壞約束的數(shù)量。

自體雜交算子在進(jìn)行雜交操作時(shí)，隨機(jī)交換染色體的任意兩個(gè)基因組。因父代染色體為合法染色體，所以交換之后的染色體不會(huì)破壞約束1）與約束2），僅可能破壞約束3），即攜行彈藥總量不足以完成交換之后的打擊任務(wù)，大大提高了子代中合法染色體的比例。

采用自體雜交算子，無(wú)法通過(guò)不同染色體之間基因交換獲得其他染色體中的優(yōu)良基因，使得基因多樣性減少。本算法通過(guò)提高變異幾率來(lái)豐富基因的多樣性。

2.6 選擇算子

選擇算子分為兩步，首先從目標(biāo)種群中選擇適應(yīng)度最優(yōu)的個(gè)體，再采用輪盤賭的方式，在除去最優(yōu)適應(yīng)度個(gè)體的種群中選擇若干個(gè)體，與最優(yōu)適應(yīng)度個(gè)體一起構(gòu)成選擇結(jié)果。

2.7 變異算子

變異算子采用兩點(diǎn)變異，首先隨機(jī)選擇一個(gè)基因，若此基因的值為1，則重新選擇；若此基因的值為0，且該火力單元被分配的目標(biāo)數(shù)量未達(dá)上限，則將此基因的值置為1，并且假設(shè)這個(gè)基因位于第j列，將第j 列另一個(gè)值為1 的基因置為0，完成變異操作。

2.8 合法性校驗(yàn)

自體雜交算子和變異算子經(jīng)過(guò)改進(jìn)，在執(zhí)行的過(guò)程中，對(duì)于雜交或變異后的個(gè)體，檢查發(fā)生變化的兩個(gè)基因組是否滿足約束3）的條件，若滿足，子代個(gè)體合法，通過(guò)校驗(yàn)；若不滿足，對(duì)父代個(gè)體重新執(zhí)行相應(yīng)算子，直至通過(guò)校驗(yàn)。

2.9 算法描述及復(fù)雜度

混合算法求解火力規(guī)劃問題可分為兩個(gè)主要步驟：計(jì)算問題復(fù)雜程度；根據(jù)復(fù)雜程度的大小選擇采用貪心算法或改進(jìn)遺傳算法進(jìn)行求解。

步驟0 根據(jù)我方火力單元數(shù)量M 和敵方目標(biāo)數(shù)量N 計(jì)算火力規(guī)劃問題復(fù)雜程度，當(dāng)復(fù)雜程度大于閾值Th 時(shí)，采用貪心算法求解，否則采用改進(jìn)遺傳算法求解。

2.9.1 貪心算法

步驟1 將矩陣P 中的隨機(jī)k 列作為起始列采用貪心策略得到k 個(gè)分配方案。步驟1 的復(fù)雜度為O（kMN）。

步驟2 取k 個(gè)分配方案中適應(yīng)度值最優(yōu)的為火力規(guī)劃的結(jié)果。步驟2 的復(fù)雜度為O（kMN）。

貪心算法考慮參數(shù)的復(fù)雜度為O（kMN）。

2.9.2 改進(jìn)遺傳算法

步驟1 設(shè)置參數(shù)。設(shè)置以下參數(shù)：種群數(shù)量p，子種群大小c，變異概率m 和最大進(jìn)化代數(shù)max_iter。

步驟2 編碼及種群初始化。采用2.2 中的編碼方式。初始種群的產(chǎn)生分為以下兩種情況：當(dāng)敵方目標(biāo)數(shù)量少于p/2 時(shí)，以每一列為起始列采用貪心策略得到N 個(gè)染色體，剩余染色體通過(guò)隨機(jī)的方式產(chǎn)生。當(dāng)敵方目標(biāo)數(shù)量大于p/2 時(shí)，以隨機(jī)選取的p/2 列作為起始列采用貪心策略得到p/2 個(gè)染色體，剩余p/2 個(gè)染色體通過(guò)隨機(jī)的方式產(chǎn)生。步驟2 的復(fù)雜度為O（pMN）。

步驟3 選擇。從父代種群中選擇包括最優(yōu)適應(yīng)度個(gè)體在內(nèi)的共p/5 個(gè)個(gè)體。步驟3 的復(fù)雜度為O（pMN+p）。

步驟4 自體雜交。對(duì)步驟3 中選出的每一個(gè)個(gè)體執(zhí)行c 次自體雜交操作形成一個(gè)子種群，共形成p/5 個(gè)子種群。最優(yōu)適應(yīng)度個(gè)體的子種群中包含最優(yōu)適應(yīng)度個(gè)體本身。步驟4 的復(fù)雜度為O（2pc/5）。

步驟5 選擇。從步驟4 產(chǎn)生的每個(gè)子種群中選擇5 個(gè)個(gè)體進(jìn)入下一代種群，共選出p 個(gè)個(gè)體。步驟5 的復(fù)雜度為O（pcMN/5+pc/5）。

步驟6 變異。對(duì)步驟5 產(chǎn)生的下一代種群中除最優(yōu)適應(yīng)度個(gè)體之外的所有個(gè)體按照變異概率m執(zhí)行變異操作。經(jīng)過(guò)變異后種群完成一次進(jìn)化，進(jìn)化次數(shù)加一。步驟6 的復(fù)雜度為O（3p）。

步驟7 判斷算法終止條件。若種群達(dá)到最大進(jìn)化代數(shù)，算法終止，輸出末代種群最優(yōu)適應(yīng)度個(gè)體為最優(yōu)解，否則轉(zhuǎn)步驟3。步驟7 的復(fù)雜度為O（1）。

改進(jìn)遺傳算法考慮參數(shù)的復(fù)雜度為O（pMN+max_iter*（p*（MN+4）+pc*（MN+3）/5）。

2.10 誤差時(shí)間系數(shù)

為確定閾值Th 的取值，定義誤差時(shí)間系數(shù)et來(lái)比較貪心算法與改進(jìn)遺傳算法的綜合效能，誤差時(shí)間系數(shù)定義為

et=err×comp

其中，err 為相對(duì)誤差，定義為貪心算法相對(duì)改進(jìn)遺傳算法的誤差，具體為

式中，errg為貪心算法最優(yōu)個(gè)體適應(yīng)度，erri為改進(jìn)遺傳算法最優(yōu)個(gè)體適應(yīng)度。

comp 為相對(duì)算法復(fù)雜度，定義為貪心算法復(fù)雜度與改進(jìn)遺傳算法復(fù)雜度之比，具體為

算法復(fù)雜度越低，其運(yùn)行時(shí)間越短，因此，et 的值綜合反映了算法誤差與運(yùn)行時(shí)間的效能，et 的值越小，則貪心算法綜合效能越好。

3 仿真與分析

混合算法主要用于求解復(fù)雜程度較大的火力規(guī)劃問題，為驗(yàn)證混合算法的有效性，通過(guò)實(shí)驗(yàn)獲得了誤差時(shí)間系數(shù)隨問題復(fù)雜程度變化的圖像，以此進(jìn)行閾值Th 的選?。煌ㄟ^(guò)兩個(gè)不同復(fù)雜程度的火力規(guī)劃問題的仿真，對(duì)比了采用不同的種群初始化方法的改進(jìn)遺傳算法以及貪心算法的結(jié)果。

火力規(guī)劃問題仿真所需彈藥消耗矩陣P，暫無(wú)數(shù)據(jù)可以參考，因此，根據(jù)火力單元與目標(biāo)所固有的殺傷能力與防護(hù)能力精心設(shè)計(jì)了彈藥消耗矩陣P，其每行元素由隨機(jī)數(shù)發(fā)生器產(chǎn)生，隨機(jī)數(shù)的范圍由該行的索引確定。

混合算法的參數(shù)設(shè)置如下：貪心算法k=100，種群數(shù)量p=50，子種群大小c=20，變異概率m=0.2，最大進(jìn)化代數(shù)max_iter=100。

3.1 誤差時(shí)間系數(shù)分析

為獲得誤差時(shí)間系數(shù)隨問題復(fù)雜程度變化的圖像，對(duì)25 個(gè)復(fù)雜程度介于50 和60 000 之間的火力規(guī)劃問題進(jìn)行了仿真，對(duì)每一個(gè)問題，取10 次仿真的相對(duì)誤差平均值作為該復(fù)雜程度的相對(duì)誤差，再通過(guò)相對(duì)誤差求得該復(fù)雜程度下的誤差時(shí)間系數(shù)。因復(fù)雜程度區(qū)間較大，圖像的x 軸為復(fù)雜程度的自然對(duì)數(shù)。

圖1 為誤差隨復(fù)雜程度變化的圖像，圖2 為誤差時(shí)間系數(shù)隨復(fù)雜程度變化的圖像。

圖1 相對(duì)誤差隨問題復(fù)雜程度變化曲線

圖2 誤差時(shí)間系數(shù)隨問題復(fù)雜程度變化曲線

通過(guò)仿真可知，相對(duì)誤差及誤差時(shí)間系數(shù)均隨著問題復(fù)雜程度的增大而減小，表明當(dāng)火力規(guī)劃問題越來(lái)越復(fù)雜時(shí)，貪心算法的綜合效能越來(lái)越好，在這種情況下，閾值Th 可綜合考慮實(shí)際應(yīng)用中的硬件條件以及對(duì)誤差的容忍度進(jìn)行選取，給予了作戰(zhàn)籌劃人員較大的自主選擇權(quán)。在本文的仿真中，取誤差為1%時(shí)的復(fù)雜程度作為閾值Th，取值約為2 300。

3.2 不同復(fù)雜程度問題的仿真與對(duì)比

3.2.1 復(fù)雜程度小于閾值Th

選取我方火力單元數(shù)量M=25，敵方目標(biāo)數(shù)量N=50，問題復(fù)雜程度為1 250，小于閾值Th。分別采用完全隨機(jī)初始化與貪心策略的初始化的混合算法的收斂曲線如圖3 所示。

圖3 復(fù)雜程度小于閾值的算法收斂曲線

由圖3 可知，采用貪心策略進(jìn)行初始化的種群的最優(yōu)個(gè)體適應(yīng)度較優(yōu)，可以加快算法收斂速度，并可以取得相對(duì)貪心算法更好的結(jié)果，采用完全隨機(jī)初始化的算法在此復(fù)雜程度下可在100 代內(nèi)收斂，但其最優(yōu)個(gè)體的適應(yīng)度較差，算法陷入局部最優(yōu)。

3.2.2 復(fù)雜程度大于閾值Th

選取我方火力單元數(shù)量M=40，敵方目標(biāo)數(shù)量N=80，問題復(fù)雜程度為3 200，大于閾值Th。初始化方式仍采用前述兩種方式，收斂曲線如圖4 所示。

由圖4 可知，當(dāng)復(fù)雜程度大于閾值時(shí)，采用完全隨機(jī)初始化的算法已無(wú)法在100 代內(nèi)收斂，采用貪心策略初始化的算法雖然可以收斂，但初始種群最優(yōu)適應(yīng)度與末代種群最優(yōu)適應(yīng)度相差較小，搜索效率較低，且貪心算法所得結(jié)果與末代種群最優(yōu)適應(yīng)度誤差極小。此時(shí)采用貪婪算法，可以大大提高求解速度，滿足實(shí)時(shí)性的要求，證明了混合算法可以有效平衡誤差與求解時(shí)間，是解決復(fù)雜火力規(guī)劃問題的有效途徑。

圖4 復(fù)雜程度大于閾值的算法收斂曲線

4 結(jié)論

本文針對(duì)火力規(guī)劃問題，提出了一種適用于不同復(fù)雜程度問題的采用貪心策略與改進(jìn)遺傳算法的混合算法，并通過(guò)仿真實(shí)驗(yàn)得到以下結(jié)論：

1）采用自體雜交算子和改進(jìn)的兩點(diǎn)變異算子可以大大提高雜交與變異操作產(chǎn)生的子代中合法染色體的比例，從而提高搜索效率，加快算法運(yùn)行時(shí)間。

2）采用貪心策略對(duì)種群進(jìn)行初始化可以大大加快種群的收斂速度并可在一定代數(shù)內(nèi)獲得更加優(yōu)秀的解。

3）混合算法可以有效平衡時(shí)間成本與解的質(zhì)量，通過(guò)結(jié)合實(shí)際需求合理選擇閾值的大小，使各種復(fù)雜程度的問題都可在一定時(shí)間內(nèi)獲得較為滿意的解。