陳　濤，王　棟

（1.海軍048工程綜合辦公室，北京100071；2.海軍航空工程學院飛行器工程系，山東煙臺264001）

基于遺傳算法的機載武器調度優(yōu)化

陳濤1，王棟2

（1.海軍048工程綜合辦公室，北京100071；2.海軍航空工程學院飛行器工程系，山東煙臺264001）

針對航母機載武器彈藥調度存在的過程復雜、不確定性強、涉及因素多等特點，建立了現階段機載武器彈藥調度模型。通過設計編碼方案，選擇適應度函數，設定交叉、變異操作建立了基于遺傳算法的調度優(yōu)化模型，并通過Matlab軟件進行了仿真驗證。結果表明，該優(yōu)化過程可在一定程度上縮短調度總時間，提高調度效率。

遺傳算法；機載武器；調度優(yōu)化

航母機載武器從彈庫到飛行甲板的調度過程，是通過武器升降機平臺和飛機升降機平臺，將所需的武器運至甲板不同戰(zhàn)位，之后加掛在飛機掛架上，涉及到多個升降機使用和掛彈位的選擇。對于不同的作戰(zhàn)任務，所需的武器類型及數量也有所區(qū)別。且出動飛機的停放位置、使用的升降機位置對于武器的調度也有影響，這一影響主要體現在調度時間的長短上。建立調度模型的目的也正是對某個調度計劃進行優(yōu)化，合理分配各升降機的使用，將任務耗時降至最低。

航母機載武器的彈藥調度屬于資源優(yōu)化調度問題，具有典型的復雜性、隨機性、多約束性和多目標性特點。解決此類問題的方法主要有啟發(fā)式方法、數學規(guī)劃方法、規(guī)則調度方法、基于人工智能和仿真的方法以及控制理論方法等[1-2]，通過計算機應用現代優(yōu)化算法解決此類問題已成主流趨勢。馬登武[3]等采用改進的蟻群算法對艦載機彈藥調度問題進行了研究，建立調度方案求解模型，克服了基本蟻群算法搜索時間長、易陷入局部最優(yōu)解等缺陷。

現代優(yōu)化算法中，基于人工智能的遺傳算法提供了一種求解復雜系統優(yōu)化問題的通用框架，它不依賴于問題的具體領域，對問題的種類有很強的魯棒性。遺傳算法在資源分配[4-7]、系統優(yōu)化[8-12]、生產調度[13-14]等領域的應用已日漸成熟，并與諸多算法混合應用，取得了很好的效果。本文通過分析各項約束條件，運用遺傳算法對機載武器的調度進行建模分析，力求通過設置合理的遺傳因子和算法，優(yōu)化調度過程。

1　遺傳算法介紹

遺傳算法（Genetic Algorithm，GA）是一種基于自然選擇原理和自然遺傳機制的并行全局搜索算法，能夠較快地對解空間進行搜索，尋找滿意解，并且通過采用實數編碼的方式對調度方案進行編碼迭代計算，能夠解決難以具體表達的變量。它是通過借鑒自然界中生命體的遺傳和進化機制，在人工系統中實現特定目標的優(yōu)化。其實質是采用群體搜索技術，按照適者生存的規(guī)則進行進化和演變，得到最終的最優(yōu)解或準最優(yōu)解。遺傳算法主要包括以下操作過程：產生初始群體、求出每個個體的適應度、根據適者生存的原則篩選出優(yōu)良個體、將選出的優(yōu)良個體進行兩兩配對、通過隨機交叉其染色體的基因并隨機變異某些染色體的基因來生成下一代群體，按此方法使群體逐代進化，直到滿足進化終止條件。

遺傳算法的基本操作是選擇、交叉和變異。選擇的作用是使父代的優(yōu)良特性得以保持并傳遞到下一代種群中。交叉使得種群中的個體以一定的概率隨機交換部分染色體，發(fā)生一定的性狀改變，從而產生新的特性。變異也是實現群體多樣性的一種手段，是某個個體自身一個或多個染色體以一定概率發(fā)生變化，從而產生新性狀。

使用遺傳算法進行優(yōu)化計算的步驟如下[15-16]。

1）根據優(yōu)化對象，確定一種編碼方法，并隨機生成個體數一定的初始種群。用一個編碼串來表示種群中的一個個體。

2）確定適應度函數。通過得到的種群中個體適應度值來判斷與優(yōu)化目標的相符性。若符合，則輸出結果，終止計算；否則進入下一步。

3）根據適應度值選擇需要進入下一代的個體。高適應度的個體有較大可能進入下一代，而低適應度的個體進入下一代的可能性較低甚至不會被選中進入下一代。

4）進行交叉和變異操作，得到新個體。

5）由上一步得到新的種群，返回步驟2）?；具z傳算法的求解過程如圖1所示。

圖1　基本遺傳法的求解過程Fig.1 Solving process of Basic GA

2　航空彈藥貯運系統工作流程

航母航空彈藥貯運系統與機載武器調度直接相關，下有航空彈藥綜合調度設施、航空彈藥貯存裝置和航空彈藥轉運裝置3個子系統。航空彈藥綜合調度設施負責對航空彈藥貯運系統的機載武器、設備、人員、任務等進行智能化管理調度；航空彈藥貯存裝置負責為機載武器在航母上安全、可靠、合理的貯存提供保障；航空彈藥轉運裝置主要用于轉運所裝載的各種機載武器，并具有部分對機頂升能力[17-19]。

綜合調度設施包括指揮管理設備、調度監(jiān)控設備和信息采集處理設備。

航空彈藥貯存裝置可分為航空彈藥貯存設備、可拆軍械貯存設備、保障器材貯存設備。按照結構，航空彈藥貯存裝置可分為存放架、存放籠、存放柜、通用基座等結構形式。

航空彈藥轉運裝置主要由垂直轉運設備、庫內轉運設備和甲板轉運設備等組成。其中，垂直轉運設備包括武器升降機，庫內轉運設備包括庫內轉運機、軌道轉運車和庫內轉運吊車等，甲板轉運設備包括甲板轉運車、頂升裝置和轉運設備等。

在接到調度任務后，由綜合調度設施制定并下發(fā)調度計劃。相應的艙室根據調度計劃，從貯存裝置上取出并轉運彈藥、附屬設備至指定位置，組裝檢測完成后最終運至甲板，加掛至作戰(zhàn)飛機上。綜合調度設施在調度的同時對人員設備進行監(jiān)控，根據反饋和現場狀況調整調度計劃，完成后，修改數據庫中相應內容。

3　彈藥調度模型的建立

設在航母上，參與一次運輸彈藥任務的升降機共有m個，掛彈位共有n個。第i個升降機到第 j個掛彈位所需的時間為tij。則升降機到掛彈位調度時間矩陣為：

相應的，設有升降機調度任務矩陣S。其中，元素amn表示第m臺升降機向第n個掛彈位提供的彈藥數量，則供彈任務矩陣為

記第i個升降機完成自身任務的時間行向量為Fi，矩陣T中對應的第i個行向量為Ti，S中第i個行向量為Si。先對Si中的元素進行邏輯判斷，當Si中的某個元素Six不為0時，令其在新的對應行向量Ri中對應元素的值Rix為1，反之為0。那么有

而一次調度任務的完成時間Tf為所有升降機中最晚完成任務的時間，則有

對任務的評價標準即為完成時間的長短。當完成任務時間最短時，說明調度方案最優(yōu)，即要求Tf的最小值。所以目標函數應為[20-22]：

相應的約束條件為：

3.1編碼方案

由于在調度過程中，任務矩陣S中元素均為非負實數，且有具體含義，故采用實數編碼。一條染色體共有n段，每一段由m個基因值組成，基因值pji的數值表示第 j掛彈位由第i個升降機提供的彈藥數量，如圖2所示。

圖2　編碼方案Fig.2 Coding scheme

可以看出，該編碼能夠符合約束條件。優(yōu)化問題的實質就是從這一編碼構成的種群中選擇最合適的解作為調度方案。

3.2適應度函數

適應度函數是進行自然選擇的依據，常由目標函數變形而來。在該問題中，目標函數是求最小值，可將函數值取倒數作為適應度函數，那么當函數值變小時適應度變大，說明更優(yōu)。適應度函數為

3.3選擇操作

本模型中采用輪盤賭法進行選擇操作。該方法對染色體的選擇基于適應度函數值的大小，當適應程度越高，時被選擇進入下一代種群的概率越高。染色體i被選中概率為

式（8）中：fi為染色體i的適應值；Z表示種群中個體總數。

3.4交叉操作

由于交叉過程在算法的迭代過程中是隨機發(fā)生的，這樣可能會導致已經產生的優(yōu)良染色體又被破壞。因此，需要一種機制防止出現這種現象，使優(yōu)良個體能夠順利進入下一代種群中。在交叉過程中，采取精英選擇法對適應度高于某個值Em的染色體進行保留進行交叉，剩下的染色體進行兩點交叉操作。關于Em的取值可以根據如下方法：

式中，k、c均為系數且0＜k＜1。

3.5變異操作

同上，在變異操作過程中也采用精英選擇法保護適應度高的染色體。當適應值高于某個值Ea時，該染色體直接進入下一代種群，而當染色體的適應值低于某個值Si時，將其淘汰并在這一代種群中隨機生成一個染色體代替。中間值部分，根據變異概率Pm進行變異操作。其中：

4　模型驗證

設在一次調度過程中，有5臺升降機和4個掛彈位參與，對應的調度時間矩陣和各掛彈位彈藥需求分別為：

設置算法相關初始參數為：初始種群個體數70，交叉概率0.25，變異概率0.01，迭代代數200。通過Matlab軟件進行仿真，得到結果見表1。

表1　仿真結果Tab.1 Simulation results

仿真結果圖如圖3所示。通過優(yōu)化，可以得到改進后的調度方案為333352213255211411444，任務總時間為31min。新方案的甘特圖如圖4所示。

圖3　仿真結果圖Fig.3 Simulation results

圖4　調度方案甘特圖Fig.4 Gantt chart of dispatching scheme

5　結論

相較傳統的數學和運籌方法既耗時又不便計算機實現，本文通過遺傳算法對航母機載武器從彈庫到飛行甲板的過程進行建模，方便計算機程序處理且步驟相對簡單，容易理解。采用實數編碼對調度過程進行描述，分段表示各掛彈位的補給方案，減少了迭代計算的次數，耗時較少，效率較高。在交叉變異操作中，使用精英保留策略對適應度值高的函數進行保護，能夠有效避免優(yōu)良個體被淘汰，并自動調整選取保留的范圍，防止出現算法陷入局部最優(yōu)的狀況。仿真結果可以看出，該算法在機載武器彈藥調度保障中具有一定的適用性和實用價值。

[1]王萬良，吳啟迪.生產調度智能算法及其應用[M].北京：科學出版社，2007：43-44. WANG WANLIANG，WU QIDI.Intelligent algorithm and its application in production scheduling[M].Beijing：Science Press，2007：43-44.（in Chenese）

[2]李敏強，寇紀淞，林丹，等.遺傳算法的基本理論與應用[M].北京：科學出版社，2003：56-58. LI MINQIANG，KOU JISONG，LIN DAN，et al.Basic theory and application of genetic algorithm[M].Beijing：Science Press，2003：56-58.（in Chenese）

[3]馬登武，郭小威，鄧力.基于改進蟻群算法的艦載機彈藥調度[J].系統仿真學報，2012，24（6）：1207-1211. MA DENGWU，GUO XIAOWEI，DENG LI.Ammunition scheduling of carrier-based aircraft based on improved ant colony algorithm[J].Journal of System Simulation，2012，24（6）：1207-1211.（in Chenese）

[4]王為新，李原，張開富.基于遺傳算法的多模式資源約束項目調度問題研究[J].計算機應用研究，2007，24（1）：72-74. WANG WEIXIN，LI YUAN，ZHANG KAIFU.Research of multi-Model resource constrained project scheduling problem based on genetic algorithm[J].Application Research of Computers，2007，24（1）：72-74.（in Chenese）

[5]熊輝.基于遺傳算法的公路養(yǎng)護資源最優(yōu)分配[J].北京理工大學學報，2007，27（1）：21-24. XIONG HUI.Optimal allocation of highway maintenance resources based on genetic algorithms[J].Beijing Institute of Technology，2007，27（1）：21-24.（in Chenese）

[6]王波，劉小利，胡亮，等.基于改進遺傳算法的反艦導彈火力分配研究[J].火力與指揮控制，2015，40（8）：90-93．WANG BO，LIU XIAOLI，HU LIANG，et al.Antiship missile fire distribution based on improved genetic algorithm[J].Fire Control&Command Control，2015，40（8）：90-93.（in Chenese）

[7]楊童.基于遺傳算法的SOFDM信道資源動態(tài)分配策略[J].中國空間科學技術，2010，30（4）：23-30．YANG TONG.Genetic arithmetic based dynamic channel allocation algorithm for SOFDM system in satellite multimedia broadcastings[J].Chinese Space Science and Technology，2010，30（4）：23-30.（in Chenese）

[8]張宗華，張偉，趙霖.利用遺傳算法實現交通控制系統優(yōu)化的方法[J].計算機工程，2003，29（12）：53-54，155. ZHANG ZONGHUA，ZHANG WEI，ZHAO LIN.Method of optimizing the traffic control system using genetic algorithm[J].Computer Engineering，2003，29（12）：53-54，155.（in Chenese）

[9]童樹鴻，沈毅，劉志言.遺傳算法在模糊系統優(yōu)化設計中的應用研究[J].系統工程與電子技術，2001，23（1）：73-76. TONG SHUHONG，SHEN YI，LIU ZHIYAN.Simultaneous optimal design of membership functions and rule sets for fuzzy systems using genetic algorithm[J].Systems Engineering and Electronics，2001，23（1）：73-76.（in Chenese）

[10]段芳，余培兵，朱衛(wèi)鋒.艦船補給物料搬運順序優(yōu)化問題的改進遺傳算法[J].計算機系統應用，2015，24（9）：105-111．DUAN FANG，YU PEIBING，ZHU WEIFENG.Improved genetic algorithm of material handling sequence optimization problem for ship material supply[J].Computer Systems&Applications，2015，24（9）：105-111.（in Chenese）

[11]劉洋.基于遺傳算法的水下無人潛器結構特性優(yōu)化分析[J].艦船科學技術，2015，37（9）：145-148．LIU YANG.Optimization analysis of structure of UUV based on genetic algorithm[J].Ship Science and Technology，2015，37（9）：145-148.（in Chenese）

[12]徐昕，耿清華.基于實數型遺傳算法的水輪機調節(jié)系統設計優(yōu)化[J].人民長江，2015，46（17）：83-86．XU XIN，GENG QINGHUA.Design optimization of turbine regulating system based on real coded genetic algorithm[J].Yangtze River，2015，46（17）：83-86.（in Chenese）

[13]KIM M，JUNG J H，LEE I B.Intelligent scheduling and moni-toring for multi-product networked bath processes [J].Computers and Chemical Engineering，1996（20）：1149-1154.

[14]KIM M，JUNG J H，LEE I B.Optimal scheduling of multi-product batch processes for various intermediate storagepolicies[J].Industrial and Engineering Chemistry Re-search，1996，35（11）：4058-4066.

[15]曲曉燕，溫德宏，謝勇.遺傳算法在艦載機彈藥轉運任務優(yōu)化配置中的應用[J].計算機與現代化，2012（3）：23-26. QU XIAOYAN，WEN DEHONG，XIE YONG.Genetic algorithm for ammunition transfer assignment optimization collocation of carrier-based aircraft[J].Computer and Modernization，2012（3）：23-26.（in Chenese）

[16]夏惠誠，申戰(zhàn)勝，伊柏棟.基于遺傳算法的艦載機對海導彈攻擊任務分配模型研究[J].艦船科學技術，2012，34（5）：117-121. XIA HUICHENG，SHEN ZHANSHENG，YI BAIDONG. Research on the mission assignment model of missile attacking on the sea by carrier aircraft on genetic algorithms[J].Ship Science and Technology，2012，34（5）：117-121.（in Chenese）

[17]史文強，李彥慶，陳練.航母的航空彈藥貯運作業(yè)解析[J].艦船科學技術，2013，35（6）：136-141. SHI WENQIANG，LI YANQING，CHEN LIAN.Analysis for the ordnance handling process aboard aircraft carrier [J].Ship Science and Technology，2013，35（6）：136-141.（in Chenese）

[18]XIAO HE，LIU YUNHUI，YU ZHENRONG.Combination of eco-profile and least-cost model for eco-network planning[J].China Geography Science，2014，24（1）：113-125.

[19]玄光男，程潤偉.遺傳算法與工程優(yōu)化[M].北京：清華大學出版社，2012：1-3. XUAN GUANGNAN，CHENG RUNWEI.Genetic algorithm and engineering scheduling[M].Beijing：Tsinghua University Press，2012：1-3.（in Chenese）

[20]BU QUANMIN，WANG ZHANJUN，TONG XING.An improved genetic algorithm for searching for pollution sources[J].Water Science and Engineering，2013，6（4）：392-401.

[21]JIANG RUI，LUO YUPIN，HU DONGCHENG.Coordinating exploration and exploitation to construct genetic algorithms[J].Tsinghua Science and Technology，2002，7（6）：608-618.

[22]BU QUANMIN，WANG ZHANJUN，TONG XING.An improved genetic algorithm for searching for pollution sources[J].Water Science and Engineering，2013，6（4）：392-401.

Scheduling Optimization of Aircraft Weapons Based on Genetic Algorithm

CHEN Tao1,WANG Dong2
（1.Naval General Office of 048 Project,Beijing 100071,China; 2.Department of Airborne Vehicle Engineering,NAAU,Yantai Shandong 264001,China）

Aiming at the characteristics of complex course,strong uncertainty and many involved factors in scheduling of aircraft weapons,the scheduling optimization model based on genetic algorithm was built through coding scheme design?ing,adaption function selecting,across and aberrance sizing.The simulation validating was also carried through Matlab. The result showed that the optimization was effective to shorten scheduling time and to elevate scheduling efficiency in a certain extent.

genetic algorithm;aircraft weapons;scheduling optimization

V271.4；E926.392

A

1673-1522（2016）01-0058-05

10.7682/j.issn.1673-1522.2016.01.011

2015-11-21；

2015-12-25

陳濤（1964-），男，高工，大學。