基于改進(jìn)遺傳算法的艦載機(jī)出庫(kù)調(diào)度優(yōu)化方法*

劉亞杰，李忠猛，謝 君

（海軍工程大學(xué)，武漢 430033）

基于改進(jìn)遺傳算法的艦載機(jī)出庫(kù)調(diào)度優(yōu)化方法*

劉亞杰，李忠猛，謝 君

（海軍工程大學(xué)，武漢 430033）

艦載機(jī)出庫(kù)最優(yōu)調(diào)度方案是合理編排一批次艦載機(jī)出庫(kù)順序，使目標(biāo)艦載機(jī)在最短的時(shí)間內(nèi)調(diào)出機(jī)庫(kù)。提出艦載機(jī)出庫(kù)調(diào)度方案4步單目標(biāo)優(yōu)化方法。第1步實(shí)現(xiàn)艦載機(jī)數(shù)量分配功能；第2步依靠遺傳算法，實(shí)現(xiàn)艦載機(jī)選擇功能，尋找最優(yōu)出庫(kù)組合方案；第3步根據(jù)優(yōu)先級(jí)規(guī)則對(duì)艦載機(jī)出庫(kù)作業(yè)進(jìn)行排序，從而得到最優(yōu)出庫(kù)方案的艦載機(jī)調(diào)度序列；第4步找出需要倒機(jī)的艦載機(jī)并根據(jù)一定規(guī)則進(jìn)行整理后，得到出庫(kù)作業(yè)序列。最后，建立模擬機(jī)庫(kù)驗(yàn)證調(diào)度方案的優(yōu)化方法可行、高效。

艦載機(jī)，調(diào)度方案，遺傳算法

0 引言

艦載機(jī)的出庫(kù)調(diào)度效率，對(duì)于提高航母的作戰(zhàn)效能具有極其重要作用。調(diào)度效率的高低與調(diào)度方案的制定有著密切關(guān)系。事實(shí)上，由于機(jī)庫(kù)布滿艦載機(jī)，安全路徑可能并不存在。在安全路徑不存在的情況下，需要不斷將該批次目標(biāo)飛機(jī)附近的艦載機(jī)移出機(jī)庫(kù)（為了描述方便，本文將這種現(xiàn)象稱之為倒機(jī)），這將觸發(fā)了一個(gè)新的調(diào)運(yùn)問(wèn)題，直到機(jī)庫(kù)有足夠的空間使目標(biāo)飛機(jī)能安全通行為止。因此，艦載機(jī)出庫(kù)調(diào)度方案是一批次艦載機(jī)出庫(kù)順序的編排，最優(yōu)調(diào)度方案則是合理的編排飛機(jī)出庫(kù)順序，使目標(biāo)艦載機(jī)在最短的時(shí)間內(nèi)調(diào)出機(jī)庫(kù)。

國(guó)外過(guò)去對(duì)于艦載機(jī)調(diào)度的做法一般是通過(guò)擺放模型，以指導(dǎo)艦載機(jī)的調(diào)度活動(dòng)，如在美軍航母上使用的“占卜板”［1］。近年來(lái)，隨著計(jì)算機(jī)技術(shù)的發(fā)展，國(guó)外開始將計(jì)算機(jī)應(yīng)用于艦載機(jī)調(diào)度方面。為解決甲板操作人員視線阻擋等問(wèn)題，造成飛機(jī)刮擦碰撞甚至人員的傷亡事故發(fā)生，通過(guò)設(shè)計(jì)航母艦載機(jī)甲板持續(xù)監(jiān)控系統(tǒng)，結(jié)合艦載機(jī)GPS定位，碰撞事故檢測(cè)等功能，為提高艦載機(jī)甲板作業(yè)效率和減少事故起到了一定的積極作用［2］。無(wú)論是模型擺放還是電子顯示的方式，其優(yōu)點(diǎn)是操作簡(jiǎn)單靈活，考慮人的經(jīng)驗(yàn)因素比較多，適用于少數(shù)艦載機(jī)的調(diào)度；缺點(diǎn)是缺乏足夠科學(xué)依據(jù)，在需要調(diào)度艦載機(jī)數(shù)量較多時(shí)，無(wú)法考慮到各種因素，從而可能得出的調(diào)度結(jié)果并不是最優(yōu)［3］。近年來(lái)，國(guó)內(nèi)學(xué)者也開始注重艦載機(jī)調(diào)度方面的研究［3-6］，但關(guān)于機(jī)庫(kù)艦載機(jī)調(diào)度方案的文獻(xiàn)資料仍較少。

艦載機(jī)出庫(kù)調(diào)度方案制定的先決條件是機(jī)庫(kù)艦載機(jī)調(diào)運(yùn)作業(yè)環(huán)境建模［7］以及對(duì)艦載機(jī)在機(jī)庫(kù)內(nèi)的調(diào)運(yùn)作業(yè)進(jìn)行路徑規(guī)劃［8］。文獻(xiàn)［7-8］中已對(duì)調(diào)運(yùn)問(wèn)題環(huán)境建模和路徑規(guī)劃問(wèn)題進(jìn)行了詳述，本文不再贅述。

在環(huán)境建模和路徑規(guī)劃的基礎(chǔ)上，本文從實(shí)際應(yīng)用的角度出發(fā)，將艦載機(jī)出庫(kù)方案制定分解為4個(gè)優(yōu)化決策問(wèn)題——數(shù)量分配優(yōu)化、選機(jī)優(yōu)化、排序優(yōu)化和倒機(jī)優(yōu)化，通過(guò)4個(gè)算法的順序協(xié)作來(lái)完成出庫(kù)作業(yè)調(diào)度方案的制定。

1 批次艦載機(jī)出庫(kù)調(diào)度方案優(yōu)化方法設(shè)計(jì)

艦載機(jī)出庫(kù)作業(yè)調(diào)度方案制定問(wèn)題是4步組合優(yōu)化問(wèn)題。艦載機(jī)出庫(kù)調(diào)度方案優(yōu)化問(wèn)題與機(jī)場(chǎng)飛機(jī)調(diào)度優(yōu)化問(wèn)題和物流倉(cāng)儲(chǔ)系統(tǒng)的貨物出入庫(kù)問(wèn)題都是典型的NP組合優(yōu)化問(wèn)題［9-11］，艦載機(jī)出庫(kù)問(wèn)題的解空間非常龐大，問(wèn)題解空間隨機(jī)庫(kù)內(nèi)艦載機(jī)規(guī)模和需求艦載機(jī)數(shù)量的增大呈指數(shù)級(jí)增長(zhǎng)。由于機(jī)庫(kù)中艦載機(jī)數(shù)量眾多，即使現(xiàn)代智能計(jì)算方法，遍歷問(wèn)題解空間的時(shí)間開銷也難以承受。依靠單一的算法難以實(shí)現(xiàn)全局尋優(yōu)。對(duì)應(yīng)于實(shí)際問(wèn)題，艦載機(jī)出庫(kù)優(yōu)化算法設(shè)計(jì)分4步進(jìn)行優(yōu)化。第1步利用相關(guān)決策知識(shí)理論實(shí)現(xiàn)艦載機(jī)數(shù)量分配功能。第2步實(shí)現(xiàn)艦載機(jī)選擇功能，本文采用遺傳算法作為該優(yōu)化問(wèn)題的核心算法。依靠遺傳算法對(duì)機(jī)庫(kù)中出庫(kù)艦載機(jī)可行解空間的遍歷，尋找最優(yōu)出庫(kù)組合方案V。第3步實(shí)現(xiàn)排序決策功能，根據(jù)優(yōu)先級(jí)規(guī)則對(duì)V中艦載機(jī)出庫(kù)作業(yè)進(jìn)行排序，從而得到最優(yōu)出庫(kù)方案艦載機(jī)調(diào)度序列Y。第4步實(shí)現(xiàn)艦載機(jī)倒機(jī)決策功能，根據(jù)艦載機(jī)之間的邏輯關(guān)系及其機(jī)庫(kù)基本作業(yè)規(guī)則，基于Petri網(wǎng)的可達(dá)性，找出需要倒機(jī)的艦載機(jī)并根據(jù)一定規(guī)則進(jìn)行整理后，得到出庫(kù)作業(yè)序列Z。批次艦載機(jī)出庫(kù)作業(yè)計(jì)劃優(yōu)化算法流程圖如圖1所示。

1.1 艦載機(jī)數(shù)量分配方案擇優(yōu)算法

已知調(diào)運(yùn)需求信息Q，機(jī)庫(kù)每個(gè)部分的機(jī)型、數(shù)量及其之間的邏輯關(guān)系等信息，求艦載機(jī)機(jī)型及出庫(kù)數(shù)量在機(jī)庫(kù)I和機(jī)庫(kù)II的優(yōu)化分配方案（本文設(shè)定有兩部升降機(jī)，考慮升降機(jī)資源利用的均衡性，以防火分隔門為界，將機(jī)庫(kù)分為兩部分，分別記作機(jī)庫(kù)I部和機(jī)庫(kù)II部）。表1為各型艦載機(jī)需求及庫(kù)存信息。

圖1 艦載機(jī)出庫(kù)優(yōu)化算法流程圖

表1 艦載機(jī)需求及庫(kù)存信息表

滿足Q需求的機(jī)庫(kù)I部與機(jī)庫(kù)II部的艦載機(jī)機(jī)型及數(shù)量分配組合的集合元素?cái)?shù)量為，其中Mi指每種機(jī)型的組合數(shù)。由于分配組合數(shù)量大，因此，需要對(duì)數(shù)量分配方案進(jìn)行優(yōu)化。優(yōu)化方法為通過(guò)設(shè)定一些規(guī)則，去掉不合理的組合解，從而達(dá)到優(yōu)化目的。設(shè)定的數(shù)量分配方案規(guī)則如下：

（1）機(jī)庫(kù)兩部分分配的調(diào)運(yùn)數(shù)量不宜相差太大

為了保持升降機(jī)資源利用均衡，這里設(shè)定機(jī)庫(kù)兩部分艦載機(jī)分配的數(shù)量之差不大于2為宜。如以表1所示的信息為例，機(jī)庫(kù)I與機(jī)庫(kù)II艦載機(jī)的合理分配數(shù)量分別為6和5或者為5和6。

（2）根據(jù)優(yōu)先級(jí)的級(jí)別，設(shè)定優(yōu)先級(jí)的權(quán)重

設(shè)優(yōu)先級(jí)的級(jí)別為n級(jí)，則依優(yōu)先級(jí)級(jí)別的高低，設(shè)定該機(jī)型數(shù)量分配所占權(quán)重分別為n，n-1，…，1。即優(yōu)先級(jí)別越高，所占的權(quán)重越大。通過(guò)對(duì)每個(gè)級(jí)別的艦載機(jī)權(quán)重進(jìn)行求和，所求和的大小與該機(jī)型艦載機(jī)分配數(shù)量成正比。

（3）機(jī)庫(kù)內(nèi)該型艦載機(jī)的數(shù)量與艦載機(jī)分配數(shù)量成正比

艦載機(jī)的數(shù)量與分配數(shù)量成正比，符合實(shí)際情況。

根據(jù)上述規(guī)則，某機(jī)型在機(jī)庫(kù)I部、II部的數(shù)量分配公式：

1.2 艦載機(jī)出庫(kù)選擇算法

當(dāng)機(jī)庫(kù)內(nèi)兩個(gè)部分的艦載機(jī)數(shù)量分配方案確定后，接下來(lái)就要分別對(duì)機(jī)庫(kù)每部分具體調(diào)運(yùn)需求進(jìn)行調(diào)運(yùn)方案求解，采用改進(jìn)的遺傳算法對(duì)調(diào)運(yùn)方案進(jìn)行優(yōu)化。本文以機(jī)庫(kù)I部的艦載機(jī)選擇為例。

1.2.1 編碼策略

每架艦載機(jī)都擁有相應(yīng)的編號(hào)，每個(gè)編號(hào)對(duì)應(yīng)著艦載機(jī)的位置。首先對(duì)機(jī)庫(kù)中艦載機(jī)進(jìn)行編號(hào)，選機(jī)算法編碼對(duì)象為相應(yīng)的艦載機(jī)編號(hào)。這里為了簡(jiǎn)化起見，艦載機(jī)的編號(hào)用英文大寫字母表示。這樣每個(gè)大寫英文字母便與艦載機(jī)編號(hào)一一對(duì)應(yīng)，即每個(gè)大寫字母對(duì)應(yīng)著不同架次的艦載機(jī)。

1.2.2 適應(yīng)度函數(shù)設(shè)計(jì)

本文所求的目標(biāo)函數(shù)值為調(diào)運(yùn)所用時(shí)間最短，采用設(shè)定最大值Cmax的方法計(jì)算適應(yīng)度值。遺傳算法適應(yīng)度函數(shù)值Fit（Zi）可通過(guò)式（2）計(jì)算求出。

其中，Cmax指進(jìn)化到當(dāng)前代為止的最大目標(biāo)函數(shù)值。

1.2.3 選擇算子設(shè)計(jì)

本文采用改進(jìn)的排序法（又稱賭盤選擇）選擇下一代個(gè)體。排序選擇方法的主要思想是：對(duì)群體中的所有個(gè)體按其適應(yīng)度大小進(jìn)行排序，基于這個(gè)排序來(lái)分配各個(gè)體被選中的概率。概率計(jì)算如式（3）所示。

為保持種群多樣性，避免過(guò)早收斂，本文借鑒期望值選擇策略的應(yīng)用經(jīng)驗(yàn)，對(duì)染色體適應(yīng)度值Fit（Z）進(jìn)行調(diào)整，如式（4），式（5）所示，以替代值Fit'（X）參與輪盤賭選擇。

排序后的種群中的第i個(gè)個(gè)體被選中概率由式（6）求得。

1.2.4 交叉算子設(shè)計(jì)

考慮到染色體個(gè)體中每個(gè)基因組編碼值域不同，本文采用單點(diǎn)同位交叉的方式，在保證個(gè)體差異化的基礎(chǔ)上，降低無(wú)效子個(gè)體產(chǎn)生幾率。對(duì)于交叉操作之后仍然不滿足編碼約束的個(gè)體，采用隨機(jī)數(shù)校正地方式，對(duì)無(wú)效個(gè)體進(jìn)行修正。隨機(jī)數(shù)生成域?yàn)樵撐换虻木幋a值域。

1.2.5 變異算子設(shè)計(jì)

遺傳算法中的所謂變異運(yùn)算，是指將個(gè)體染色體編碼串中某些基因座上基因值用該基因座其他等位基因來(lái)替換，從而形成一個(gè)新的個(gè)體。對(duì)于符號(hào)編碼個(gè)體，變異操作就是用這個(gè)字符集中一個(gè)隨機(jī)指定且與原基因值不相同的字符去替換變異點(diǎn)上的原有符號(hào)。

1.3 艦載機(jī)出庫(kù)排序及倒機(jī)決策算法

第3層排序優(yōu)化算法對(duì)上一層傳入的出庫(kù)集合X中的艦載機(jī)，根據(jù)解碼后艦載機(jī)的具體屬性信息，按照優(yōu)先級(jí)從高到低進(jìn)行排序，同級(jí)者隨機(jī)排列，得到出庫(kù)作業(yè)次序Y。

對(duì)于排序后的艦載機(jī)，根據(jù)構(gòu)造關(guān)聯(lián)矩陣，可以計(jì)算每架艦載機(jī)的出庫(kù)序列。艦載機(jī)倒機(jī)具體算法流程如圖2所示。

圖2 艦載機(jī)倒機(jī)決策算法流程圖

2 應(yīng)用案例

設(shè)定艦載機(jī)在機(jī)庫(kù)中的一種布列方式，對(duì)艦載機(jī)出庫(kù)方案優(yōu)化算法進(jìn)行驗(yàn)證。

2.1 問(wèn)題描述

該機(jī)庫(kù)配備兩部升降機(jī)，一道防火分隔門將機(jī)庫(kù)分為兩部分，記作機(jī)庫(kù)I部，機(jī)庫(kù)II部，機(jī)庫(kù)I部、機(jī)庫(kù)II部分別與升降機(jī)1，升降機(jī)2對(duì)應(yīng)，即機(jī)庫(kù)I部的艦載機(jī)通過(guò)升降機(jī)1調(diào)運(yùn)至甲板，機(jī)庫(kù)II部的艦載機(jī)通過(guò)升降機(jī)II調(diào)運(yùn)至甲板。機(jī)庫(kù)內(nèi)擁有艦載機(jī)的機(jī)型為4種，共計(jì)26架。

試驗(yàn)過(guò)程中設(shè)計(jì)4張不同的艦載機(jī)需求批量表Q1，Q2，Q3，Q4，每張批量表中包含4種機(jī)型的需求艦載機(jī)，艦載機(jī)數(shù)量分別為6，8，11，12。批量表中艦載機(jī)需求情況和各機(jī)型艦載機(jī)的在庫(kù)數(shù)量如表2所示。

表2 艦載機(jī)庫(kù)存及批量需求表

2.2 遺傳算法參數(shù)設(shè)定

算法中設(shè)最大遺傳代數(shù)Genmax=200，種群空間Popmax=50，變異率pm=0.02，交叉率pc=0.6。算法執(zhí)行過(guò)程中，往往會(huì)在沒(méi)有達(dá)到最大遺傳代數(shù)情況下得到最優(yōu)解。為降低算法執(zhí)行時(shí)間，GA算法中設(shè)置一個(gè)閾值flag，flag表示每代種群個(gè)體平均適應(yīng)度值與當(dāng)前最優(yōu)適應(yīng)度值比值，如式（7）所示。

設(shè)定flag=0.9，如果flag值超過(guò)0.9，就可以認(rèn)為截止到當(dāng)前己經(jīng)取得問(wèn)題的全局最優(yōu)解。

2.3 試驗(yàn)結(jié)果及分析

在算法運(yùn)行過(guò)程中，優(yōu)化算法表現(xiàn)出較好的收斂性，需求Q1，Q2，Q3，Q4的求解時(shí)間分別為12 s，13 s，15 s和16 s，滿足實(shí)時(shí)性要求。圖3為需求Q1的求解結(jié)果。

下面將本文提出的改進(jìn)遺傳算法和標(biāo)準(zhǔn)遺傳算法執(zhí)行過(guò)程中的收斂情況進(jìn)行比較。以需求Q4的求解為例，GA在每一代取得的最優(yōu)目標(biāo)函數(shù)值F（Z）隨遺傳代數(shù)的變化曲線如圖4所示。由圖中可以看出，與采用標(biāo)準(zhǔn)輪盤賭選擇算子的優(yōu)化算法相比，采用改進(jìn)輪盤賭選擇算子的優(yōu)化算法運(yùn)行得到最優(yōu)目標(biāo)函數(shù)值在整體上具有更好的收斂性。在算法運(yùn)行前期，采用標(biāo)準(zhǔn)輪盤賭選擇算子的優(yōu)化算法具有更快的收斂速度。但是隨著算法運(yùn)行，采用改進(jìn)輪盤賭選擇算子的優(yōu)化算法搜索效率更高，最終得到的優(yōu)化結(jié)果也明顯優(yōu)于前者。

圖3 艦載機(jī)出庫(kù)優(yōu)化方案結(jié)果區(qū)界面

圖4 GA最優(yōu)目標(biāo)函數(shù)值變化曲線

3 小結(jié)

針對(duì)艦載機(jī)出庫(kù)調(diào)度方案優(yōu)化問(wèn)題，提出了4步單目標(biāo)優(yōu)化算法設(shè)計(jì)方案并實(shí)現(xiàn)優(yōu)化算法的開發(fā)。第1步利用相關(guān)決策知識(shí)理論，確定艦載機(jī)數(shù)量分配方案；第2步，以遺傳算法作為優(yōu)化核心算法，進(jìn)行選機(jī)操作；第3步，利用優(yōu)先級(jí)關(guān)系，對(duì)艦載機(jī)出庫(kù)順序進(jìn)行排序。第4步，利用構(gòu)造關(guān)聯(lián)矩陣算法，構(gòu)建倒機(jī)決策優(yōu)化算法。最后通過(guò)模擬機(jī)庫(kù)驗(yàn)證了優(yōu)化算法的可行性和高效性。

［1］漁翁.美國(guó)航母航空部門的組織管理［J］.艦船知識(shí)，2006（9）:36-37.

［2］Jerrrey S.Feasibility Study of Global-positioning-System-Based Aircraft-Carrier Flight-Deck Persistent Moni-toring System［C］//Journal of Aircraft，2010.

［3］司維超，韓維，史瑋韋.基于PSO算法的艦載機(jī)艦面布放調(diào)度方法研究［J］.航空學(xué)報(bào)，2012，33（11）:2048-2056.

［4］楊炳恒，畢玉泉，徐偉勤.一種艦載機(jī)調(diào)運(yùn)作業(yè)流程優(yōu)化模型［J］.艦船科學(xué)技術(shù)，2011，33（1）:118-121.

［5］馮強(qiáng)，曾聲奎，康銳.基于MAS的艦載機(jī)動(dòng)態(tài)調(diào)度模型［J］.航空學(xué)報(bào)，2009，30（11）:2109-2125.

［6］劉欽輝，邱長(zhǎng)華，王能健.考慮空間約束的艦載機(jī)作業(yè)調(diào)度模型研究［J］.哈爾濱工程大學(xué)學(xué)報(bào)，2012，33（11）: 1435-1439.

［7］劉亞杰，翁輝，陳曉山.一種基于“矢柵結(jié)合”的機(jī)庫(kù)艦載機(jī)調(diào)運(yùn)作業(yè)環(huán)境建模方法［J］.裝甲兵工程學(xué)院學(xué)報(bào)，2014，28（2）:75-78.

［8］劉亞杰，李忠猛，陳曉山.考慮空間約束的機(jī)庫(kù)艦載機(jī)調(diào)運(yùn)路徑規(guī)劃方法［J］.海軍工程大學(xué)學(xué)報(bào)，2014，26（3）: 100-103.

［9］Abela J，Abranmson D.Computing Optional Scheduling for Landing Aircraft［C］//Proceedings 12th National ASOR Conference，Adelaide Australia，2006.

［10］馮心玲，龔月姣，林映霞.用遺傳算法優(yōu)化航班規(guī)劃問(wèn)題［J］.計(jì)算機(jī)工程與設(shè)計(jì)，2009，30（19）:468-471.

［11］王廣民.造船廠鋼板堆場(chǎng)出庫(kù)作業(yè)計(jì)劃建模及優(yōu)化研究［D］.大連:大連理工大學(xué)，2009.

Optimized Method of Carrier-borne Aircrafts Exporting Scheduling Based on Improved Genetic Algorithm

LIU Ya-jie LI Zhong-meng XIE Jun
（Naval University of Engineering，Wuhan 430033，China）

The optimized exporting scheduling programme of carrier-borne aircrafts is to arrange exporting order of aircrafts，which makes the total time shortest.Four-stage decision-making course of exporting operation is put forward.The first step is to realize the amount allocation of the aircrafts.The second step is aircrafts chosen based on genetic algorithm.The third step is to sort order based on the rule of priority.The last step is to find out the aircrafts which need be rehandled.Finally，a simulated hangar is built to test the optimized algorithm reasonable and efficient.

carrier-borne aircraft，operation scheduling programme，genetic algorithm

TP208

A

1002-0640（2015）06-0057-04

2014-05-08

2014-06-19

軍隊(duì)科研計(jì)劃基金資助項(xiàng)目

劉亞杰（1975- ），女，遼寧朝陽(yáng)人，博士。研究方向：復(fù)雜系統(tǒng)建模與仿真。