朱傳偉 童幼堂 董受全

（海軍大連艦艇學(xué)院 大連 116018）

1 引言

遺傳算法是一種借鑒生物界的進(jìn)化規(guī)律演化而來的隨機(jī)化搜索方法，其從試圖解釋自然系統(tǒng)中生物的復(fù)雜適應(yīng)過程入手，模擬生物進(jìn)化的機(jī)制來構(gòu)造人工系統(tǒng)的模型［1］。由于遺傳算法具有高度的并行處理能力、強(qiáng)魯棒性和全局搜索能力，被廣泛應(yīng)用于諸多領(lǐng)域，包括可以用于艦空導(dǎo)彈武器系統(tǒng)火力分配。由于傳統(tǒng)遺傳算法在實(shí)踐應(yīng)用中存在著一定的局限性。因此，采用混合遺傳算法對(duì)艦空導(dǎo)彈武器系統(tǒng)的火力分配問題進(jìn)行研究，既能克服傳統(tǒng)遺傳算法的不足，又能保證傳統(tǒng)遺傳算法的效率。

2 火力分配模型

艦空導(dǎo)彈武器系統(tǒng)火力分配模型是依據(jù)各空襲目標(biāo)的威脅程度及其飛行參數(shù)，確定應(yīng)由哪部照射雷達(dá)對(duì)其實(shí)施照射，保證最大數(shù)量的目標(biāo)滿足射擊條件，使總體作戰(zhàn)效能最大［2］。

設(shè)有N個(gè)來襲目標(biāo)，所有照射雷達(dá)都分配目標(biāo)。則火力分配問題就是使下面的期望函數(shù)值最大化。

式中：Rj為目標(biāo)j的威脅系數(shù)；Xij為布爾值，用來判斷目標(biāo)j是不是分配給了照射雷達(dá)i。如果目標(biāo)j分配給了照射雷達(dá)i，則Xij＝1，否則Xij＝0。

式（2）表示一次分配給目標(biāo)j的照射雷達(dá)數(shù)量不超過bj個(gè)，式（3）表示每部照射雷達(dá)最多能照射一個(gè)目標(biāo)。

在現(xiàn)代海戰(zhàn)場(chǎng)上，只有當(dāng)目標(biāo)進(jìn)入到艦空導(dǎo)彈武器系統(tǒng)發(fā)射區(qū)，同時(shí)目標(biāo)處于照射雷達(dá)作用范圍以內(nèi)時(shí)，照射雷達(dá)才能照射目標(biāo)［3］。因此，當(dāng)照射雷達(dá)照射目標(biāo)時(shí)，通常要受到艦指揮員決策、殺傷區(qū)大小、照射雷達(dá)實(shí)際作用范圍、照射雷達(dá)的轉(zhuǎn)移時(shí)間等因素制約。

2.1 艦指揮員決策約束條件

由于作戰(zhàn)情況的復(fù)雜多變，獲得的數(shù)據(jù)信息不可能非常完全、確定和可靠，艦指揮員的判斷、決策、選擇仍然是十分必要的，即艦指揮員應(yīng)對(duì)火力分配方案有一定的干預(yù)能力［4］。通過賦予各目標(biāo)對(duì)應(yīng)的威脅系數(shù)Rj值，在火力分配中加權(quán)，體現(xiàn)出艦指揮員決策對(duì)火力分配結(jié)果的影響。

2.2 照射雷達(dá)有效作用范圍約束條件

對(duì)于照射雷達(dá)Zr來說，其有效作用范圍是艦空導(dǎo)彈武器系統(tǒng)殺傷區(qū)與照射雷達(dá)Zr的實(shí)際作用范圍的共同區(qū)域。設(shè)第一個(gè)目標(biāo)到達(dá)照射器雷達(dá)Zr的有效作用范圍遠(yuǎn)界的時(shí)間為TY（Zr，1），到達(dá)其有效作用范圍近界的時(shí)間為TY（Zr，1）＋TD（Zr，1），TD（Zr，1）為第一個(gè)目標(biāo)在其有效作用范圍內(nèi)停留的時(shí)間。該照射雷達(dá)對(duì)第一個(gè)目標(biāo)的開始照射時(shí)刻為TL（Zr，1），只有滿足約束式（4）時(shí)，該照射雷達(dá)才能有效照射第一個(gè)目標(biāo)。

照射雷達(dá)Zr執(zhí)行完前一個(gè)目標(biāo)的照射任務(wù)后，在向后一個(gè)目標(biāo)開始執(zhí)行照射任務(wù)之前需要有一段轉(zhuǎn)移的時(shí)間。設(shè)該照射雷達(dá)的最小轉(zhuǎn)移時(shí)間為TZ。

同理可以得出，只有同時(shí)滿足約束式（5）和式（6）時(shí)，該照射雷達(dá)才能有效照射第二個(gè)目標(biāo)。

式中：TY（Zr，2）為第二個(gè)目標(biāo)到達(dá)該照射雷達(dá)有效作用范圍遠(yuǎn)界的時(shí)間；TD（Zr，2）為第二個(gè)目標(biāo)在該照射雷達(dá)有效作用范圍內(nèi)停留的時(shí)間；TL（Zr，2）為該照射雷達(dá)對(duì)第二個(gè)目標(biāo)的開始照射時(shí)刻。

3 基于自適應(yīng)懲罰函數(shù)法的混合遺傳算法

3.1 適應(yīng)度評(píng)價(jià)函數(shù)設(shè)計(jì)

以上的火力分配模型屬于約束優(yōu)化問題，而用遺傳算法不能直接去求解約束優(yōu)化問題，需要做一些處理。通常是通過引入懲罰函數(shù)，將有約束優(yōu)化問題轉(zhuǎn)換為無約束優(yōu)化問題，再使用遺傳算法求解。但在實(shí)際計(jì)算中，懲罰函數(shù)法中的懲罰因子通常難以合理選取，如果懲罰因子過小，懲罰項(xiàng)得不到足夠的懲罰，滿足約束條件的精度就會(huì)降低；反之，懲罰函數(shù)會(huì)增大，造成對(duì)期望函數(shù)分配的權(quán)重過小，忽略了對(duì)期望函數(shù)的影響，得到的往往是局部最優(yōu)解，同時(shí)也給計(jì)算增加困難。

為了較好地解決懲罰因子的確定問題，采用了文獻(xiàn)［5］中的自適應(yīng)懲罰函數(shù)方法，將懲罰因子選取為關(guān)于自變量Xij的函數(shù)。同時(shí)，為了加快收斂速度，借鑒了“多級(jí)懲罰”的思想，即對(duì)違反約束大的段給予較大懲罰，而違反約束小的段給予較小的懲罰。

則適應(yīng)度評(píng)價(jià)函數(shù)為

式中：pq為懲罰函數(shù)；Cq為懲罰函數(shù)的系數(shù)。其具有“多級(jí)懲罰”的功能，并且在算法的迭代過程中起到了“自適應(yīng)”調(diào)節(jié)的作用。

3.2 混合遺傳算法設(shè)計(jì)

艦空導(dǎo)彈武器系統(tǒng)的混合遺傳算法的結(jié)構(gòu)構(gòu)成見圖1，其主要操作流程是首先使用遺傳算法，當(dāng)滿足終止條件時(shí)，完成全局搜索，輸出群體適應(yīng)度最優(yōu)個(gè)體。然后通過使用爬山法，繼續(xù)完成局部搜索過程，最終得出適應(yīng)度最優(yōu)個(gè)體。

3.2.1 遺傳算法設(shè)計(jì)

1）編碼體制的選擇

染色體采用二進(jìn)制編碼方式，設(shè)個(gè)體的串長(zhǎng)為M×N，為第h（h≥1）代染色體kh串，表示第i部照射雷達(dá)對(duì)第j個(gè)目標(biāo)的火力分配情況，則染色體表示為…＝（…）。

2）初始群體設(shè)定

傳統(tǒng)遺傳算法是按隨機(jī)方法產(chǎn)生一組初始解群體，但其中的每個(gè)染色體不一定滿足約束條件式（2）和式（3），以下方法可使初始解群體自動(dòng)滿足這兩個(gè)式子，其步驟為

圖1 混合遺傳算法構(gòu)成示意圖

第一步：將所有染色體中每個(gè)基因座均賦值為0；

第二步：對(duì)于每一個(gè)染色體，將其變換為M×N階矩陣。隨機(jī)選擇其中的一個(gè)或兩個(gè)基因座，根據(jù)式（3）在每一行中置一個(gè)1。然后隨機(jī)選擇其中的幾個(gè)基因座，使第j列中最多置bj個(gè)1，以滿足式（2）。

3）個(gè)體適應(yīng)度評(píng)價(jià)

由于單個(gè)個(gè)體代表一種火力分配方案，必須將火力分配方案通過照射雷達(dá)有效作用范圍約束條件的檢驗(yàn)，形成可行的火力分配方案，然后根據(jù)式（7）計(jì)算個(gè)體適應(yīng)度值。

照射雷達(dá)有效作用范圍約束條件的檢驗(yàn)方法為：仍以照射雷達(dá)Zr為例進(jìn)行說明。根據(jù)照射雷達(dá)Zr的有效作用范圍，將先進(jìn)入有效作用范圍的目標(biāo)作為該照射雷達(dá)第一次照射的目標(biāo)，將稍后進(jìn)入有效作用范圍的目標(biāo)作為該照射雷達(dá)第二次照射的目標(biāo)，即依據(jù)進(jìn)入有效作用范圍的先后順序來確定該照射雷達(dá)的照射目標(biāo)次序。當(dāng)目標(biāo)同時(shí)進(jìn)入有效作用范圍時(shí)，優(yōu)先照射目標(biāo)威脅系數(shù)值大的目標(biāo)。

對(duì)于照射雷達(dá)Zr的第一次照射，依據(jù)式（4）判斷該照射雷達(dá)是否可有效照射第一個(gè)目標(biāo)，如果不能有效照射第一個(gè)目標(biāo)，則染色體中該照射雷達(dá)照射第一個(gè)目標(biāo)對(duì)應(yīng)的布爾值賦值為0。同時(shí)，當(dāng)該照射雷達(dá)還有照射其它目標(biāo)的性質(zhì)時(shí)，依據(jù)上述方法選擇另外一個(gè)目標(biāo)作為第一個(gè)目標(biāo)，依上述程序進(jìn)行判斷。如能有效照射第一個(gè)目標(biāo)，則需判斷該照射雷達(dá)是否還要照射第二個(gè)目標(biāo)。如還要照射第二個(gè)目標(biāo)，則依據(jù)式（5）和式（6）進(jìn)行判斷，經(jīng)過判斷后，如不能有效照射第二個(gè)目標(biāo)，則染色體中該照射雷達(dá)照射第二個(gè)目標(biāo)對(duì)應(yīng)的布爾值賦值為0。同時(shí)，當(dāng)該照射雷達(dá)還要照射其它目標(biāo)時(shí)，依據(jù)上述方法選擇另外一個(gè)目標(biāo)作為第二個(gè)目標(biāo)，依上述程序進(jìn)行判斷。如能有效照射第二個(gè)目標(biāo)，則需判斷該照射雷達(dá)是否還要照射第三個(gè)目標(biāo)。如此反復(fù)，直到火力分配方案滿足該照射雷達(dá)有效作用范圍約束條件時(shí)為止。

4）選擇操作

選擇時(shí)在群體中選擇生命力強(qiáng)的個(gè)體產(chǎn)生新的群體的過程。在傳統(tǒng)遺傳算法中，常根據(jù)個(gè)體的適應(yīng)度大小采用“賭輪選擇”策略。該策略雖然簡(jiǎn)單，但容易引起“早熟收斂”和“搜索遲鈍”問題。為了避免這一問題，采用比例選擇和精華模型相結(jié)合的選擇策略，將每個(gè)代群種He個(gè)個(gè)體中適應(yīng)值最大的一個(gè)直接進(jìn)入下一代。下一代種群中其它個(gè)體將由上一代種群中剩余的He－1個(gè)個(gè)體，用輪盤賭法產(chǎn)生。這樣一方面可以保證種群中最優(yōu)個(gè)體可以生存到下一代；另一方面，又避免了個(gè)體間因適應(yīng)值不同而被選入下一代的機(jī)會(huì)太懸殊，從一定程度上保證了種群的多樣性。

5）交叉操作

交叉是指對(duì)相互配對(duì)的染色體按某種方式相互交換其部分基因，從而形成兩個(gè)新的個(gè)體［6］。傳統(tǒng)遺傳算法對(duì)父染色體之間進(jìn)行交叉操作時(shí)，是隨機(jī)選取的，未考慮它們各自適應(yīng)度的大小。因此，交叉操作存在著很大的盲目性，影響了算法的性能。

由于在生物界中，很多生物種群是以一個(gè)個(gè)小群體生活于自然界的。這些生物種群的下一代均依靠最優(yōu)秀的個(gè)體和其它母體產(chǎn)生，如蜜蜂、狼群等。根據(jù)這些生物現(xiàn)象，采取的交叉過程如下：一是選擇適應(yīng)度最大的個(gè)體為最優(yōu)個(gè)體，其直接進(jìn)入到下一代，設(shè)為第h代染色體kh1（其表示為…）；二是隨機(jī)選擇與最優(yōu)個(gè)體kh1配對(duì)的一個(gè)個(gè)體，設(shè)為染色體kh2（其表示為…）；三是將與互換與互換，與互換，依此形成兩個(gè)新的個(gè)體。當(dāng)這兩個(gè)新個(gè)體的適應(yīng)度不相同時(shí)，去掉其中適應(yīng)度最小的個(gè)體，保留另外一個(gè)個(gè)體。否則，任意保留其中一個(gè)。

6）變異操作

變異運(yùn)算是指將個(gè)體染色體編碼串中某些基因座上的基因值用該基因座的其它等位基因來替換，從而形成一個(gè)新的個(gè)體［7］。對(duì)于第h代染色體kh，隨機(jī)選擇其中的與，將兩者互換，形成新的染色體與。d1，d2，e1，e2＝1，2，…，M。然后評(píng)價(jià)新產(chǎn)生個(gè)體的適應(yīng)度值，將其與父代個(gè)體進(jìn)行比較，若適應(yīng)度值相同，則視為無效變異操作，去除這個(gè)新產(chǎn)生的個(gè)體，重新按以上方法實(shí)施變異操作；否則，則視為有效變異操作，新產(chǎn)生的個(gè)體取代父代個(gè)體。

7）自適應(yīng)交叉率和變異率

交叉概率pc和變異概率pm對(duì)遺傳算法性能具有重要影響，不少文獻(xiàn)對(duì)此進(jìn)行了系統(tǒng)研究。其中，相關(guān)文獻(xiàn)［8］將pc、pm與群體的收斂性、個(gè)體的適應(yīng)值相聯(lián)系，自適應(yīng)地改變交叉概率pc和變異概率pm值的大小，將進(jìn)化過程分為漸進(jìn)和突變兩個(gè)不同階段：漸進(jìn)階段強(qiáng)交叉，弱變異，強(qiáng)化優(yōu)勢(shì)型選擇算子；突變階段弱交叉，強(qiáng)變異，弱化優(yōu)勢(shì)型選擇算子。具體公式為

式中：evalgu為第g（g＝1，2，…，H）個(gè)個(gè)體的適應(yīng)度值；evalbig為兩個(gè)交叉?zhèn)€體的適應(yīng)度最大值；evalmax為當(dāng)前群體的適應(yīng)度最大值；evalavg為當(dāng)前群體的適應(yīng)度均值。

通常取b1＝b3＝1.0，b2＝b4＝0.5。

8）算法終止條件

判斷是否達(dá)到了所設(shè)定的世代數(shù)，或者兩世代的平均適應(yīng)度評(píng)價(jià)函數(shù)值之差的絕對(duì)值是否小于給定的閾值εh。εh為一個(gè)小的正數(shù)，但也不能太小，否則爬山法局部尋優(yōu)發(fā)揮的作用不大。如果不滿足終止條件，則進(jìn)化代數(shù)h＝h＋1；否則，則輸出當(dāng)前群體適應(yīng)度最優(yōu)個(gè)體，遺傳算法部分結(jié)束。

3.2.2 爬山法設(shè)計(jì)

爬山法是一種簡(jiǎn)單的啟發(fā)式搜索算法［9］。它將最陡上升方向作為搜索方向，能夠以最快的速度爬到山頂。其搜索過程概況是：擴(kuò)展當(dāng)前節(jié)點(diǎn)。并估價(jià)它的子節(jié)點(diǎn)，將最優(yōu)子節(jié)點(diǎn)作為下一步擴(kuò)展節(jié)點(diǎn)，依此類推，直到爬到“山頂”為止。爬山法搜索速度快，容易達(dá)到局部最優(yōu)［10］。

由于染色體采用二進(jìn)制編碼方式，那么采用位爬山法時(shí)要根據(jù)位變異的方式和概率等不同，具有多種具體樣式。對(duì)于位變異方式，要采用從左向右的順序一次變異。對(duì)于以上遺傳算法實(shí)施全局搜索后得出的單一最優(yōu)個(gè)體ky來說，其串長(zhǎng)為M×N，則位爬山法的搜索過程如下：

步驟1：取序號(hào)dp＝1；

步驟2：以一定的概率pdj變異最優(yōu)個(gè)體ky的第dp位基因值，即將基因值取反，由0變到1，或由1變到0，得出新個(gè)體kx；

步驟3：按照以上的“個(gè)體適應(yīng)度評(píng)價(jià)”方法，計(jì)算新個(gè)體kx的適應(yīng)度evalx和最優(yōu)個(gè)體ky的適應(yīng)度evaly；

步驟4：比較新個(gè)體的適應(yīng)度。當(dāng)evalx＞evaly時(shí)，新個(gè)體kx取代最優(yōu)個(gè)體ky；否則，不變。同時(shí)dp＝dp＋1，返回到步驟2。如此不斷循環(huán)，直到當(dāng)dp＝M×N時(shí)，循環(huán)結(jié)束，得出適應(yīng)度最優(yōu)個(gè)體。

4 結(jié)語

基于混合遺傳算法求解的艦空導(dǎo)彈武器系統(tǒng)火力分配問題能夠?yàn)榻鉀Q防空作戰(zhàn)運(yùn)籌領(lǐng)域類似的問題提供了一種新的思路。由于傳統(tǒng)遺傳算法在實(shí)踐應(yīng)用中，會(huì)出現(xiàn)早熟現(xiàn)象、局部尋優(yōu)能力較差等不足，而爬山法具有較強(qiáng)的局部尋優(yōu)能力［11］。因此，可以將遺傳算法的把握總體能力和爬山法的局部搜索能力相互結(jié)合，取長(zhǎng)補(bǔ)短，構(gòu)建混合遺傳算法，從而可有效避免陷入局部極值并最終趨向全局優(yōu)化。

［1］馬亞龍，邵秋峰，孫明.評(píng)估理論和方法及其軍事應(yīng)用［M］.北京：國(guó)防工業(yè)出版社，2013：164－174.

［2］任少偉，賀正洪，劉進(jìn)忙.基于改進(jìn)遺傳算法的防空火力優(yōu)化分配方法［J］.火力與指揮控制，2004，29（3）：82－84.

［3］陶英歌，郭乃林，羅紅英.基于遺傳算法的目標(biāo)分配優(yōu)化模型研究［J］.系統(tǒng)工程與電子技術(shù)，2003，25（7）：817－819.

［4］張海峰，吳富初，王光源.防空系統(tǒng)目標(biāo)威脅評(píng)估與火力分配模型［J］.火力與指揮控制，2004，29（6）：29－31.

［5］劉瓊蓀，周聲華.基于自適應(yīng)懲罰函數(shù)法的混合遺傳算法［J］.重慶大學(xué)學(xué)報(bào)，2006，29（6）：78－81.

［6］曳永芳，杜永清，行小帥.一種抑制早熟收斂的改進(jìn)遺傳算法［J］.山西師范大學(xué)學(xué)報(bào)，2010，24（2）：24－28.

［7］程杰，任偉，徐軍凱.遺傳算法在導(dǎo)彈火力分配中的應(yīng)用［J］.現(xiàn)代防御技術(shù)，2008，36（4）：93－96.

［8］M.Srinivas，L.M.Patnaik.Adaptive probabilities of crossover of crossover and mutation in genetic algorithms［J］.IEEE Trans.Systems，Man Cybernet，1994，24（4）：656－667.

［9］隋樹元，王樹山.終點(diǎn)效應(yīng)學(xué)［M］.北京：國(guó)防工業(yè)出版社，2007：53－65.

［10］錢進(jìn)，葉寒竹.基于作戰(zhàn)過程的機(jī)動(dòng)導(dǎo)彈武器系統(tǒng)生存能力評(píng)估建模［J］.裝備指揮技術(shù)學(xué)院學(xué)報(bào)，2007，18（4）：116－123.

［11］王書齊，沈治河.基于可變模糊集決策理論的航空母艦編隊(duì)防空決策方法研究［M］.北京：海潮出版社，2013：130－134.