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

佘 博 葛富斌

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

1 引言

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

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

2 任務(wù)分配模型

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

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

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

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

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

圖1 遺傳算法流程

3.1 問題編碼

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

3.2 初始種群生成

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

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

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

3.4 選擇

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

3.5 交叉

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

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

3.6 變異

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

3.7 終止

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

4 算例仿真與分析

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

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

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

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

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

本程序比較穩(wěn)定，經(jīng)過多次運行，通過對程序結(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；護衛(wèi)艦B用7枚導(dǎo)彈攻擊目標(biāo)3；護衛(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é)語

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

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

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

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

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

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

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

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

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

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

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

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