混合遺傳算法在艦空導彈武器系統火力分配中的應用＊

朱傳偉 童幼堂 董受全

（海軍大連艦艇學院 大連 116018）

1 引言

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

2 火力分配模型

艦空導彈武器系統火力分配模型是依據各空襲目標的威脅程度及其飛行參數，確定應由哪部照射雷達對其實施照射，保證最大數量的目標滿足射擊條件，使總體作戰效能最大［2］。

設有N個來襲目標，所有照射雷達都分配目標。則火力分配問題就是使下面的期望函數值最大化。

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

式（2）表示一次分配給目標j的照射雷達數量不超過bj個，式（3）表示每部照射雷達最多能照射一個目標。

在現代海戰場上，只有當目標進入到艦空導彈武器系統發射區，同時目標處于照射雷達作用范圍以內時，照射雷達才能照射目標［3］。因此，當照射雷達照射目標時，通常要受到艦指揮員決策、殺傷區大小、照射雷達實際作用范圍、照射雷達的轉移時間等因素制約。

2.1 艦指揮員決策約束條件

由于作戰情況的復雜多變，獲得的數據信息不可能非常完全、確定和可靠，艦指揮員的判斷、決策、選擇仍然是十分必要的，即艦指揮員應對火力分配方案有一定的干預能力［4］。通過賦予各目標對應的威脅系數Rj值，在火力分配中加權，體現出艦指揮員決策對火力分配結果的影響。

2.2 照射雷達有效作用范圍約束條件

對于照射雷達Zr來說，其有效作用范圍是艦空導彈武器系統殺傷區與照射雷達Zr的實際作用范圍的共同區域。設第一個目標到達照射器雷達Zr的有效作用范圍遠界的時間為TY（Zr，1），到達其有效作用范圍近界的時間為TY（Zr，1）＋TD（Zr，1），TD（Zr，1）為第一個目標在其有效作用范圍內停留的時間。該照射雷達對第一個目標的開始照射時刻為TL（Zr，1），只有滿足約束式（4）時，該照射雷達才能有效照射第一個目標。

照射雷達Zr執行完前一個目標的照射任務后，在向后一個目標開始執行照射任務之前需要有一段轉移的時間。設該照射雷達的最小轉移時間為TZ。

同理可以得出，只有同時滿足約束式（5）和式（6）時，該照射雷達才能有效照射第二個目標。

式中：TY（Zr，2）為第二個目標到達該照射雷達有效作用范圍遠界的時間；TD（Zr，2）為第二個目標在該照射雷達有效作用范圍內停留的時間；TL（Zr，2）為該照射雷達對第二個目標的開始照射時刻。

3 基于自適應懲罰函數法的混合遺傳算法

3.1 適應度評價函數設計

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

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

則適應度評價函數為

式中：pq為懲罰函數；Cq為懲罰函數的系數。其具有“多級懲罰”的功能，并且在算法的迭代過程中起到了“自適應”調節的作用。

3.2 混合遺傳算法設計

艦空導彈武器系統的混合遺傳算法的結構構成見圖1，其主要操作流程是首先使用遺傳算法，當滿足終止條件時，完成全局搜索，輸出群體適應度最優個體。然后通過使用爬山法，繼續完成局部搜索過程，最終得出適應度最優個體。

3.2.1 遺傳算法設計

1）編碼體制的選擇

染色體采用二進制編碼方式，設個體的串長為M×N，為第h（h≥1）代染色體kh串，表示第i部照射雷達對第j個目標的火力分配情況，則染色體表示為…＝（…）。

2）初始群體設定

傳統遺傳算法是按隨機方法產生一組初始解群體，但其中的每個染色體不一定滿足約束條件式（2）和式（3），以下方法可使初始解群體自動滿足這兩個式子，其步驟為

圖1 混合遺傳算法構成示意圖

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

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

3）個體適應度評價

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

照射雷達有效作用范圍約束條件的檢驗方法為：仍以照射雷達Zr為例進行說明。根據照射雷達Zr的有效作用范圍，將先進入有效作用范圍的目標作為該照射雷達第一次照射的目標，將稍后進入有效作用范圍的目標作為該照射雷達第二次照射的目標，即依據進入有效作用范圍的先后順序來確定該照射雷達的照射目標次序。當目標同時進入有效作用范圍時，優先照射目標威脅系數值大的目標。

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

4）選擇操作

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

5）交叉操作

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

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

6）變異操作

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

7）自適應交叉率和變異率

交叉概率pc和變異概率pm對遺傳算法性能具有重要影響，不少文獻對此進行了系統研究。其中，相關文獻［8］將pc、pm與群體的收斂性、個體的適應值相聯系，自適應地改變交叉概率pc和變異概率pm值的大小，將進化過程分為漸進和突變兩個不同階段：漸進階段強交叉，弱變異，強化優勢型選擇算子；突變階段弱交叉，強變異，弱化優勢型選擇算子。具體公式為

式中：evalgu為第g（g＝1，2，…，H）個個體的適應度值；evalbig為兩個交叉個體的適應度最大值；evalmax為當前群體的適應度最大值；evalavg為當前群體的適應度均值。

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

8）算法終止條件

判斷是否達到了所設定的世代數，或者兩世代的平均適應度評價函數值之差的絕對值是否小于給定的閾值εh。εh為一個小的正數，但也不能太小，否則爬山法局部尋優發揮的作用不大。如果不滿足終止條件，則進化代數h＝h＋1；否則，則輸出當前群體適應度最優個體，遺傳算法部分結束。

3.2.2 爬山法設計

爬山法是一種簡單的啟發式搜索算法［9］。它將最陡上升方向作為搜索方向，能夠以最快的速度爬到山頂。其搜索過程概況是：擴展當前節點。并估價它的子節點，將最優子節點作為下一步擴展節點，依此類推，直到爬到“山頂”為止。爬山法搜索速度快，容易達到局部最優［10］。

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

步驟1：取序號dp＝1；

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

步驟3：按照以上的“個體適應度評價”方法，計算新個體kx的適應度evalx和最優個體ky的適應度evaly；

步驟4：比較新個體的適應度。當evalx＞evaly時，新個體kx取代最優個體ky；否則，不變。同時dp＝dp＋1，返回到步驟2。如此不斷循環，直到當dp＝M×N時，循環結束，得出適應度最優個體。

4 結語

基于混合遺傳算法求解的艦空導彈武器系統火力分配問題能夠為解決防空作戰運籌領域類似的問題提供了一種新的思路。由于傳統遺傳算法在實踐應用中，會出現早熟現象、局部尋優能力較差等不足，而爬山法具有較強的局部尋優能力［11］。因此，可以將遺傳算法的把握總體能力和爬山法的局部搜索能力相互結合，取長補短，構建混合遺傳算法，從而可有效避免陷入局部極值并最終趨向全局優化。

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

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

［3］陶英歌，郭乃林，羅紅英.基于遺傳算法的目標分配優化模型研究［J］.系統工程與電子技術，2003，25（7）：817－819.

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

［5］劉瓊蓀，周聲華.基于自適應懲罰函數法的混合遺傳算法［J］.重慶大學學報，2006，29（6）：78－81.

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

［7］程杰，任偉，徐軍凱.遺傳算法在導彈火力分配中的應用［J］.現代防御技術，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］隋樹元，王樹山.終點效應學［M］.北京：國防工業出版社，2007：53－65.

［10］錢進，葉寒竹.基于作戰過程的機動導彈武器系統生存能力評估建模［J］.裝備指揮技術學院學報，2007，18（4）：116－123.

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