基于遺傳算法的艦艇編隊(duì)任務(wù)分配問題研究＊

佘 博 葛富斌

（海軍大連艦艇學(xué)院研究生管理大隊(duì) 大連 116018）

1 引言

艦艇編隊(duì)對(duì)地攻擊是支援對(duì)岸作戰(zhàn)、打擊敵縱深戰(zhàn)略目標(biāo)的一個(gè)重要手段。編隊(duì)任務(wù)分配問題一直是海軍指揮員關(guān)注的重點(diǎn)，也是我軍軍事斗爭(zhēng)中重要決策問題。指揮員如何根據(jù)目標(biāo)威脅程度和我編隊(duì)武器性能，將各類武器分配給目標(biāo)，實(shí)施艦艇編隊(duì)協(xié)同作戰(zhàn)，使得毀傷目標(biāo)效能最大、兵力消耗最少，充分發(fā)揮出各武器的整體優(yōu)勢(shì)。針對(duì)艦艇編隊(duì)的編成兵力多、武器裝備復(fù)雜、信息量大、作戰(zhàn)節(jié)奏快的特點(diǎn)，在對(duì)戰(zhàn)場(chǎng)態(tài)勢(shì)估計(jì)、威脅程度、目標(biāo)任務(wù)價(jià)值判斷的基礎(chǔ)上，需要利用計(jì)算機(jī)科學(xué)合理的設(shè)計(jì)編隊(duì)任務(wù)分配方案，輔助指揮員決策，發(fā)揮出編隊(duì)的最大作戰(zhàn)效能。

艦艇編隊(duì)的任務(wù)分配不僅要確定每種型號(hào)武器單元攻擊的目標(biāo)，還要確定攻擊目標(biāo)的彈藥數(shù)量，屬于典型的非線性整數(shù)規(guī)劃問題。解這類問題已有很多優(yōu)化算法：模擬退火算法、禁忌搜索法、枚舉法和蘭徹斯特方程等。當(dāng)模型規(guī)模較大時(shí)，這些優(yōu)化算法存在計(jì)算量大、耗時(shí)長(zhǎng)，不能保證具體問題的收斂性等不足。而遺傳算法能夠?qū)崿F(xiàn)在復(fù)雜空間中進(jìn)行魯棒搜索，具有全局搜索性強(qiáng)、運(yùn)算收斂速度快、結(jié)果精度高等優(yōu)點(diǎn)，能夠很好解決其他算法存在的不足［1］。

2 任務(wù)分配模型

艦艇編隊(duì)對(duì)地任務(wù)分配是一個(gè)NP問題，導(dǎo)彈對(duì)目標(biāo)的毀傷效能指標(biāo)以毀傷目標(biāo)數(shù)的數(shù)學(xué)期望為基礎(chǔ)，優(yōu)化的目的是使數(shù)學(xué)期望最大［2］。

艦艇編隊(duì)對(duì)地攻擊對(duì)目標(biāo)武器的選擇以目標(biāo)的威脅程度、目標(biāo)價(jià)值、易攻性及編隊(duì)武器裝備數(shù)量為基礎(chǔ)，尋找最優(yōu)方法使目標(biāo)與武器的配對(duì)對(duì)戰(zhàn)場(chǎng)綜合價(jià)值貢獻(xiàn)率最高，并且考慮導(dǎo)彈的價(jià)值，使導(dǎo)彈消耗少，留有一定的余量［3～5］。設(shè)wj表示目標(biāo)j的重要程度，ci表示編隊(duì)第i種類型導(dǎo)彈的價(jià)值，其中wj的取值比較復(fù)雜，根據(jù)戰(zhàn)場(chǎng)態(tài)勢(shì)，可由專家評(píng)價(jià)、模糊理論評(píng)估、層次分析法等確定。將目標(biāo)函數(shù)（1）轉(zhuǎn)換為一個(gè)新的最優(yōu)化目標(biāo)函數(shù)：

其中，參數(shù)a表示導(dǎo)彈消耗總價(jià)值相對(duì)于導(dǎo)彈對(duì)目標(biāo)毀傷效能的權(quán)重，不同的任務(wù)需求程度使得a的取值不同。本文要求編隊(duì)盡可能的摧毀岸上目標(biāo)，導(dǎo)彈少量余留，此處a取值0.0125。

3 任務(wù)分配問題遺傳算法實(shí)現(xiàn)

遺傳算法是一種基于達(dá)爾文的“進(jìn)化論”而產(chǎn)生的優(yōu)勝劣汰、自然選擇、適者生存和基因遺傳思想的優(yōu)化算法。遺傳算法將問題的求解表示成“染色體”（用編碼表示字符串），根據(jù)適者生存的原則，選擇出適應(yīng)環(huán)境（約束條件）的染色體，進(jìn)行復(fù)制、交叉、變異操作，產(chǎn)生總體性能上勝于舊的新個(gè)體，淘汰不適合環(huán)境的舊的個(gè)體，經(jīng)過多代的進(jìn)化選擇，最終產(chǎn)生滿足需求的最佳染色體。對(duì)于遺傳算法，也就是不斷接近最優(yōu)解。遺傳算法操作的流程圖［6］如圖1所示。

圖1 遺傳算法流程

3.1 問題編碼

遺傳算法不能直接處理問題空間的參數(shù)，而只能處理以基因碼串形式表示的個(gè)體，因此，使用遺傳算法前，需要把優(yōu)化問題的解的參數(shù)形式轉(zhuǎn)換成基因碼串表示的形式，即完成問題解空間到GA空間的映射，這一轉(zhuǎn)換操作就叫編碼。為保證基因碼串可行，問題的編碼需要滿足一定要求，如：編碼的完備性、健全性、非冗余性。編碼的形式有二進(jìn)制編碼、格雷碼編碼、實(shí)數(shù)編碼、序列編碼等。本文采用實(shí)數(shù)編碼形式［7］，艦艇數(shù)量為m，目標(biāo)數(shù)為n，編碼長(zhǎng)度Lc＝m·n，編碼形式為X＝（x11，x12，…，x1n，…，xm1，…，xmn）。

3.2 初始種群生成

遺傳算法是群體型并行操作，使得搜索解的效率高，這樣也就必須為遺傳算法操作準(zhǔn)備一個(gè)若干初始解組成的初始群體。本文假定每艘艦艇對(duì)任一目標(biāo)攻擊不超過7發(fā)導(dǎo)彈，即xij∈［0，7］，在隨機(jī)產(chǎn)生初始群體時(shí)要滿足xij的取值要求，以此產(chǎn)生的群體為第一代種群X［8］。

3.3 計(jì)算適應(yīng)度值

個(gè)體適應(yīng)度函數(shù)采用目標(biāo)函數(shù)形式，其值可由式（2）計(jì)算得到。

3.4 選擇

選擇是從種群中淘汰劣質(zhì)個(gè)體，選擇生命力強(qiáng)的染色體產(chǎn)生新種群的過程。本文采用適應(yīng)度比例法，在該方法中，各個(gè)個(gè)體的選擇概率和其適應(yīng)度成比例。個(gè)體適應(yīng)度值越大，被選中進(jìn)行遺傳操作的概率就越大，其子孫在下一代產(chǎn)生的個(gè)體就越多。并采取精英保留策略［9］，即各代中的最佳個(gè)體不參與交叉、變異，直接進(jìn)入下一代，這能有效減少較好個(gè)體結(jié)構(gòu)被破壞，提高程序運(yùn)算速度。

3.5 交叉

交叉算子是模仿自然界有性繁殖的基因重組過程，其作用在于將原有的優(yōu)良基因遺傳到下一代種群中，生成新個(gè)體，保證種群的多樣性。交叉操作一般分為以下幾個(gè)步驟：1）從交配池中隨機(jī)的取出要交配的一對(duì)染色體；2）對(duì)要配對(duì)的一對(duì)染色體，隨機(jī)選?。?，Lc－1］中一個(gè)或多個(gè)基因位作為交叉位置；3）由交叉概率Pc實(shí)施交叉操作，配對(duì)的染色體相互交換在交叉位置之后的基因內(nèi)容，形成一對(duì)新的個(gè)體。

如雙親A、B經(jīng)過兩點(diǎn)交叉操作后生成后代染色體A′、B′。

3.6 變異

變異算子模擬生物進(jìn)化過程中個(gè)體的基因突變現(xiàn)象，從而改變?nèi)旧w的結(jié)構(gòu)和物理性狀，在一定程度上可改善遺傳算法的局部搜索能力，增加種群的多樣性。根據(jù)變異概率Pm實(shí)施變異操作。

3.7 終止

遺傳算法的終止，一般采用設(shè)定最大遺傳代數(shù)T的方法［10］，種群代數(shù)達(dá)到T，則終止迭代，輸出計(jì)算結(jié)果。

4 算例仿真與分析

設(shè)艦艇編隊(duì)由三艘艦艇組成，包括：一艘驅(qū)逐艦、兩艘護(hù)衛(wèi)艦，分別編號(hào)A、B、C。其中驅(qū)逐艦裝備Ⅰ型導(dǎo)彈，護(hù)衛(wèi)艦都裝備Ⅱ型導(dǎo)彈。目標(biāo)有四個(gè)，分別編號(hào)1、2、3、4。

艦艇編隊(duì)各艦艇攜帶的導(dǎo)彈數(shù)量為ai＝（a1，a2，a3）＝（12，16，16）；艦艇編隊(duì)各艦艇攜帶的導(dǎo)彈價(jià)值系數(shù)為ci＝（c1，c2，c3）＝（0.4，0.3，0.3）；目標(biāo)的重要程度系數(shù) wj（j＝1，2，3，4）和各艦艇艦空導(dǎo)彈對(duì)目標(biāo)的毀傷概率eij（i＝1，2，…，m；j＝1，2，…，n）分別見表1、表2。

表1 目標(biāo)威脅系數(shù)

表2 各艦艇導(dǎo)彈對(duì)目標(biāo)的毀傷概率

本算例中，遺傳算法參數(shù)設(shè)置如下：群體規(guī)模M＝24；終止迭代次數(shù)T＝100；選擇概率方式：賭輪選擇；交叉概率：Pc＝0.8；變異概率：Pm＝0.02。由于B、C為同型護(hù)衛(wèi)艦，且裝備同型導(dǎo)彈，在作戰(zhàn)過程中，按均分原則，護(hù)衛(wèi)艦B、C發(fā)射導(dǎo)彈總數(shù)相差不超1枚。采用Matlab編程［11］，得到的運(yùn)行結(jié)果如表3和圖2。

本程序比較穩(wěn)定，經(jīng)過多次運(yùn)行，通過對(duì)程序結(jié)果分析可得到，最大染色體適應(yīng)度值為0.8449。導(dǎo)彈目標(biāo)的分配情況為：驅(qū)逐艦A用5枚導(dǎo)彈攻擊目標(biāo)1，2枚導(dǎo)彈攻擊目標(biāo)2，2枚導(dǎo)彈攻擊目標(biāo)3，1枚導(dǎo)彈攻擊目標(biāo)4；護(hù)衛(wèi)艦B用7枚導(dǎo)彈攻擊目標(biāo)3；護(hù)衛(wèi)艦C用3枚導(dǎo)彈攻擊目標(biāo)2，5枚導(dǎo)彈攻擊目標(biāo)4。結(jié)果符合導(dǎo)彈攻擊作戰(zhàn)使用要求。

表3 導(dǎo)彈目標(biāo)分配情況

圖2 最佳染色體適應(yīng)度和各代染色體平均適應(yīng)度值

5 結(jié)語

艦艇編隊(duì)武器目標(biāo)任務(wù)分配是提高編隊(duì)對(duì)地攻擊毀傷效能的關(guān)鍵因素，武器目標(biāo)的分配一直是個(gè)難題，有效解決這一問題對(duì)現(xiàn)代作戰(zhàn)具有重要意義。本文采用遺傳算法對(duì)模型仿真運(yùn)算，只需要目標(biāo)函數(shù)和編碼串，方法較簡(jiǎn)單，收斂速度快，該模型和方法可為編隊(duì)對(duì)地作戰(zhàn)武器的分配提供一定的參考。

［1］牛曉博，趙虎，周國祥.基于并列遺傳算法的艦艇編隊(duì)目標(biāo)分配問題［J］.現(xiàn)代防御技術(shù)，2010，38（6）：70－74.

［2］張最良.軍事運(yùn)籌學(xué)［M］.北京：軍事科學(xué)出版社，1993：403－410.

［3］張曉豐，程紅斌，張鳳鳴.改進(jìn)遺傳算法的導(dǎo)彈目標(biāo)分配方法［J］.火力控制與指揮，2007，32（4）：59－61.

［4］白軍，劉新學(xué)，郭峰，等.基于遺傳算法的導(dǎo)彈編隊(duì)攻擊任務(wù)優(yōu)化分配策略［J］.四川兵工學(xué)報(bào)，2011，32（10）：51－53.

［5］董樹軍，張羅政，趙瑾.一種武器－目標(biāo)分配模型及求解算法［J］.火力控制與指揮，2006，31（5）：41－44.

［6］韓力群.智能控制理論及應(yīng)用［M］.北京：機(jī)械工業(yè)出版社，2011：241－256.

［7］高桂清，向進(jìn)，董承博.基于遺傳算法的常規(guī)彈道導(dǎo)彈火力分配［J］.四川兵工學(xué)報(bào)，2009，30（11）：9－11.

［8］尹文彬，許騰，侯博，等.基于遺傳算法的艦艇編隊(duì)火力分配問題研究［J］.兵工自動(dòng)化，2010，29（5）：4－6.

［9］姚躍亭，趙建軍，尹波波，等.艦艇編隊(duì)防空目標(biāo)分配優(yōu)化算法研究［J］.計(jì)算機(jī)與數(shù)字工程，2011，39（1）：31－34.

［10］劉新發(fā).艦艇編隊(duì)火力分配決策模型研究［J］.艦船電子工程，2012，32（11）：18－20.

［11］李明.詳解MATLAB在最優(yōu)化計(jì)算中的應(yīng)用［M］.北京：電子工業(yè)出版社，2012：383－392.