基于NGA算法的艦載機(jī)機(jī)庫出庫調(diào)度優(yōu)化*

司維超，齊玉東，韓 維

（海軍航空工程學(xué)院，山東 煙臺 264001）

基于NGA算法的艦載機(jī)機(jī)庫出庫調(diào)度優(yōu)化*

司維超，齊玉東，韓 維

（海軍航空工程學(xué)院，山東 煙臺 264001）

為了在復(fù)雜的機(jī)庫環(huán)境中，盡可能縮短艦載機(jī)出庫時間，優(yōu)化其出庫順序，對艦載機(jī)多機(jī)出庫調(diào)度優(yōu)化問題進(jìn)行了研究。首先，對該問題進(jìn)行分析，建立了適合優(yōu)化的數(shù)學(xué)模型。其次，設(shè)計了一種適合優(yōu)化艦載機(jī)多機(jī)出庫調(diào)度問題的算法—NGA算法，該算法是在遺傳算法（GA）的基礎(chǔ)上，對原有交叉和變異策略進(jìn)行改變以適應(yīng)所求解問題，并融入執(zhí)行路徑探測和規(guī)劃的通視圖算法后形成的。最后，分別將該方法和枚舉法應(yīng)用于求解尼米茲級航母艦載機(jī)多機(jī)出庫調(diào)度優(yōu)化問題T4。仿真結(jié)果為基于NGA算法所得的最短出庫時間為801 s，最短移動距離為1 098.3m;基于枚舉法結(jié)果為800.4 s和1 097.6m。由結(jié)果可知，NGA算法計算結(jié)果與枚舉法相差較小，可以應(yīng)用于求解艦載機(jī)多機(jī)出庫調(diào)度問題。

艦載機(jī)，出庫調(diào)度優(yōu)化，改進(jìn)遺傳算法，枚舉法，尼米茲航母

航母在目前乃至將來都是各軍事強(qiáng)國海軍的重要力量，對其搭載的艦載機(jī)進(jìn)行合理保障具有重要的意義［1］。為了完成特定任務(wù)，需要從機(jī)庫往艦面調(diào)運(yùn)多架飛機(jī)，其中涉及飛機(jī)出庫問題［2-3］。不同飛機(jī)所要調(diào)往艦面目的停機(jī)位各不同；飛機(jī)不同出庫順序，對應(yīng)的出庫時間和總的移動距離是不同的。為了盡量縮短出庫時間和移動距離，這需在綜合考慮飛機(jī)調(diào)往艦面目的停機(jī)位等基礎(chǔ)上，對飛機(jī)的出庫順序進(jìn)行優(yōu)化。

當(dāng)需要出庫的飛機(jī)數(shù)量較多時，出庫問題的解空間將會很大，使該問題成為一個NP完全問題［4］。例如，在不考慮相關(guān)約束前提下，出庫12架飛機(jī)，其總共的出庫順序方案有479 001 600種。如何從眾多的出庫方案中，排除不可行方案，并尋找最優(yōu)方案則需要進(jìn)一步研究。

國外以往對于飛機(jī)的出庫調(diào)度一般是通過人為進(jìn)行的［5］，即調(diào)度人員根據(jù)當(dāng)前機(jī)庫飛機(jī)的布放情況，在滿足安全的前提下，對需要出庫的飛機(jī)進(jìn)行排序，排序的原則一般是離升降機(jī)近的優(yōu)先出庫［6］。其優(yōu)點是操作比較簡單，適用于出庫少數(shù)飛機(jī)；缺點是沒有綜合考慮各架飛機(jī)所要調(diào)往的艦面停機(jī)位距離遠(yuǎn)近，以及本次出庫調(diào)度任務(wù)整體出動時間和移動距離優(yōu)化問題，在出庫飛機(jī)數(shù)量較多時，可能得出的調(diào)度結(jié)果并不是最優(yōu)。國內(nèi)對艦載機(jī)出庫調(diào)度問題研究相對較少，主要集中在艦載機(jī)的保障方面，如文獻(xiàn)［7］側(cè)重于艦載機(jī)綜合保障建模方法研究。

為此本文通過對飛機(jī)多機(jī)出庫調(diào)度問題進(jìn)行建模，并利用融合通視圖算法［8］的改進(jìn)遺傳算法NGA對該問題進(jìn)行解決，從數(shù)學(xué)方面給以依據(jù)，一定程度上解決了人工排序的缺陷。

1 多機(jī)出庫調(diào)度問題數(shù)學(xué)建模

問題描述如下：

①約束條件：飛機(jī)在機(jī)庫內(nèi)按照一定方式進(jìn)行排列，且不同飛機(jī)所要調(diào)往的艦面停機(jī)位互不相同，在進(jìn)行出庫方案優(yōu)化時必須進(jìn)行考慮；飛機(jī)在出庫過程中，必須保證有可行路徑，即避免與其他飛機(jī)或機(jī)庫本身發(fā)生碰撞沖突，確保安全；機(jī)庫空間相對有限，對使用同一升降機(jī)出庫的飛機(jī)而言，每次允許1架飛機(jī)執(zhí)行機(jī)庫內(nèi)部移動，且后移動的飛機(jī)必須等緊前飛機(jī)移動到升降機(jī)后才開始移動；升降機(jī)需根據(jù)承載能力規(guī)定一次可以升降的飛機(jī)數(shù)量；各個升降機(jī)的使用原則上是互不沖突，可獨立進(jìn)行，為此本章重點考慮使用一個升降機(jī)時的多機(jī)出庫優(yōu)化問題。

②多目標(biāo)：已知待出庫多架飛機(jī)所處機(jī)庫停機(jī)位及其所要調(diào)往的艦面目的停機(jī)位，則不同的出庫順序所對應(yīng)的出庫任務(wù)總的出庫時間和總的移動距離互有差異，為此可以選擇在優(yōu)先保證出庫時間最短基礎(chǔ)上，盡量保證移動距離也最短作為待優(yōu)化的目標(biāo)。

③優(yōu)化內(nèi)容：在滿足上述約束條件的前提下，對使用同一個升降機(jī)執(zhí)行出庫操作的多架飛機(jī)進(jìn)行合理的排序，給出最優(yōu)出庫方案，使得在優(yōu)先保證飛機(jī)總的出庫時間最短的基礎(chǔ)上，也盡可能縮短其總的移動距離。

針對某一具體的出動任務(wù)，令需要出庫飛機(jī)數(shù)量為n；所使用的升降機(jī)序號為μ。則建立數(shù)學(xué)模型如下所示。

目標(biāo)函數(shù):

其中，F(xiàn)為所要達(dá)到的目標(biāo)函數(shù)，即在優(yōu)先保證n架飛機(jī)總的出庫時間最短的基礎(chǔ)上，也盡可能縮短其總的移動距離。Xi為第i種飛機(jī)出庫方案，主要由n架飛機(jī)按照出庫順序?qū)ζ渌帣C(jī)庫停機(jī)位編號進(jìn)行排序組成，用作目標(biāo)函數(shù)F的輸入?yún)?shù)。S代表總的移動距離計算函數(shù)，參數(shù)為n架飛機(jī)所處機(jī)庫停機(jī)位的某種排序方案Xi。S需要在滿足約束條件下，根據(jù)不同航母的不同出庫方案動態(tài)給出。T代表總的出動時間計算函數(shù)，參數(shù)為n架飛機(jī)所處機(jī)庫停機(jī)位的某種排序方案Xi。T需要在滿足約束條件下，根據(jù)不同航母的不同出庫任務(wù)動態(tài)給出。

約束條件

其中，aij為第i種出庫方案中的第j架順序出庫的飛機(jī)所處停機(jī)位編號。式（2）表示各架飛機(jī)必須按照順序無重復(fù)出動。

2 基于NGA算法的多機(jī)出庫優(yōu)化

2.1 NGA算法設(shè)計

常規(guī)單一的遺傳算法對飛機(jī)出庫方案優(yōu)化問題，并不能完全適應(yīng)，必須對其進(jìn)行相應(yīng)的轉(zhuǎn)變，為此本節(jié)通過對交叉和變異策略進(jìn)行改變，并融入執(zhí)行路徑探測和規(guī)劃的通視圖算法，形成了適用于優(yōu)化飛機(jī)出庫問題的NGA算法。

①融合通視圖法的NGA算法操作流程如圖1所示。

圖1 MGA算法基本流程圖

②基于NGA算法優(yōu)化的基本思路

在利用NGA算法求解多機(jī)出庫調(diào)度方案過程中，飛機(jī)總的出庫時間以及總的移動距離可以作為算法的適應(yīng)度函數(shù)；某種出庫方案可以作為NGA算法的某條染色體。通過不斷進(jìn)化染色體，并進(jìn)行通視圖法可行路徑探測及規(guī)劃，也即更新了飛機(jī)出庫方案，最終可以得出使得總的出動時間以及總的移動距離綜合最優(yōu)的某種出庫方案。

2.2 基于NGA算法搜索最優(yōu)出庫方案的方法

①建立機(jī)庫環(huán)境模型，明確多機(jī)出庫環(huán)境，包括待出庫飛機(jī)在機(jī)庫中的布放及編號等。

②明確出庫任務(wù)，確定需要出庫的飛機(jī)范圍。

③執(zhí)行基于NGA算法的最優(yōu)出庫方案搜索。具體如下：

a.NGA算法基本參數(shù)的選取

采用如下參數(shù)設(shè)置：種群大小設(shè)置為300；交叉率設(shè)置為0.8［9］；最大進(jìn)化代數(shù)設(shè)置為200次。

b.染色體編碼動態(tài)設(shè)置

此處采用實值編碼方式，即每條染色體代表一種多機(jī)的出庫方案，其中的第i個基因表示該出庫方案中第i順序出庫的飛機(jī)，用其所占用的機(jī)庫停機(jī)位編號表示。而對于染色體的長度也必須能夠根據(jù)不同任務(wù)所需出庫飛機(jī)數(shù)量的不同而動態(tài)變化。

c.適應(yīng)度函數(shù)的動態(tài)設(shè)置

在進(jìn)化過程中，需要評價每條染色體，而評價的標(biāo)準(zhǔn)為該染色體所對應(yīng)出庫方案是否令目標(biāo)更優(yōu)，為此可選用式（1）作為適應(yīng)度函數(shù)。其中總的出庫時間包括所有待出庫飛機(jī)機(jī)庫操作時間和艦面操作（移至目的停機(jī)位等）時間之和；總的移動距離函數(shù)包括所有待出庫飛機(jī)機(jī)庫移動距離和艦面移動距離之和。其中所涉及到的待出庫飛機(jī)的機(jī)庫移動路徑和時間由通視圖法法計算給出；而艦面移動距離和時間可由路徑規(guī)劃方法計算給出［10-11］。

d.種群初始化

為縮短計算時間，此處將種群中每一條染色體均初始化為可行染色體，即均滿足飛機(jī)出庫相關(guān)約束條件?？尚行耘卸椋捍_保該出庫方案中，在除去前面已出庫的（i-1）架飛機(jī)后新的機(jī)庫環(huán)境中，第i架待出庫飛機(jī)與升降機(jī)之間均存在可行路徑。

e.執(zhí)行選擇算子運(yùn)算

選擇算子用來對群體中的個體進(jìn)行優(yōu)勝劣汰操作。此處采用輪盤賭選擇法對種群進(jìn)行選擇。具體步驟如下：首先，生成選擇概率CP。設(shè)群體中共有n個染色體，第i個染色體的適應(yīng)度值（優(yōu)先考慮總的出庫時間）為fi，則該染色體的選擇概率為：

其中，CPi為第i個染色體的選擇概率為種群中的最大適應(yīng)度值；fi為第i個染色體的適應(yīng)度值表示第i個染色體參與選擇的并被選中的機(jī)會值，由于此處是以總的出庫時間越短越好，所以fi越小，對應(yīng)越大，則其被選中的機(jī)會就越大。

其次，根據(jù)選擇概率，用輪盤賭選擇方法決定被選擇保留到下一代的染色體。

f.執(zhí)行改進(jìn)交叉算子運(yùn)算

此處隨機(jī)取新生代中兩組染色體配成一對，執(zhí)行兩點交叉操作。但是對配對染色體（即兩種飛機(jī)出庫方案）執(zhí)行簡單的兩點交叉可能會使所生成的子個體出現(xiàn)元素重復(fù)的現(xiàn)象，而這與實際出庫要求（同一機(jī)庫停機(jī)位的飛機(jī)只能出庫一次）相矛盾，為此需要采用某種新的交叉策略。本節(jié)采用如下策略來克服元素重復(fù)的問題，如圖2所示。

圖2 兩點交叉更新操作示意圖

●確定任意兩個交叉位置a和b。

●建立兩個中間個體temp1和temp2。其組成方式為：將父個體由交叉位置b至其結(jié)束的部分提前至該父個體的前端。

●分別針對兩個父個體進(jìn)行交叉操作。例如針對父個體1來說，首先保留交叉位置a和b之間的部分；其次，從交叉位置b開始依次順序選擇temp2的每一個基因執(zhí)行插入（注意若temp2當(dāng)前基因與父個體1保留部分中的基因有重復(fù)，則拋棄temp2當(dāng)前基因，選擇其下一個基因），直至到達(dá)父個體1染色體末端；最后，返回父個體1最前端，繼續(xù)選擇temp2中基因執(zhí)行插入，直至到達(dá)交叉位置a為止。

g.依次遍歷交叉形成的新染色體，并執(zhí)行以下操作：

●對當(dāng)前染色體的各個基因執(zhí)行基于通視圖法的可行路徑探測及規(guī)劃。依次遍歷交叉后染色體的各個基因，判斷按照當(dāng)前順序出庫該基因所代表的飛機(jī)是否存在可行路徑：若存在，則進(jìn)一步規(guī)劃路徑；若不存在，則執(zhí)行變異策略。

其中，通視圖法的基本思路為：首先，建立障礙物凸殼環(huán)境模型，即將需要移動的飛機(jī)簡化為一點，而將其他障礙物的凸多邊形進(jìn)行擴(kuò)充，建立障礙物多邊形的緩沖區(qū)［12］（障礙物多邊形緩沖區(qū)是沿該多邊形邊界線外側(cè)距離不超過緩沖距的點組成的區(qū)域）；其次，利用兩點法建立起點和終點的連線，如果該連線不與任何障礙物凸殼模型相交，則其即為待規(guī)劃的最優(yōu)路徑；否則，連線直接或間接穿過某障礙物凸殼模型集合，則該連線將集合中各障礙物凸殼模型分為上下兩部分，此時可以將路徑規(guī)劃問題轉(zhuǎn)換為利用凸包法求解障礙物上下兩部分頂點集的凸包問題，然后通過對凸包所形成的初始路徑進(jìn)行優(yōu)化便可以得到上下兩條可行路徑。其次，對當(dāng)前規(guī)劃出路徑上相鄰兩個節(jié)點間的路徑段重復(fù)執(zhí)行以上操作，直至所有路徑段均不與障礙物發(fā)生碰撞。最后，按照所記錄的無碰撞路徑節(jié)點建立可行路徑有向圖，并給出最優(yōu)路徑。

●根據(jù)當(dāng)前基因可行性，選擇性執(zhí)行改進(jìn)變異算子運(yùn)算。

經(jīng)過交叉后形成的新染色體，雖然避免了基因重復(fù)，但并不一定是可行的，為此需要對每條染色體中不可行基因執(zhí)行某種變異策略。

原始變異算子在需要執(zhí)行變異操作染色體中隨機(jī)取該個體的某兩個基因進(jìn)行互換，以完成變異操作。而本節(jié)對于代表飛機(jī)出庫順序的特殊染色體，并不能隨機(jī)進(jìn)行基因互換，因為這樣可能導(dǎo)致可行基因變?yōu)椴豢尚校徊豢尚谢蛉匀徊豢尚星闆r的出現(xiàn)。為此，此處采用了一種新的變異策略，具體為：記錄當(dāng)前不可行基因，并判定當(dāng)前所有可用基因的集合，將該不可行基因與當(dāng)前可用基因集合中隨機(jī)一個執(zhí)行互換，并再次利用通視圖法規(guī)劃可行出庫路徑。

●根據(jù)該基因所代表飛機(jī)所要調(diào)往的艦面停機(jī)位，對其艦面移動路徑進(jìn)行規(guī)劃，詳見文獻(xiàn)［13］。

h.在所有染色體均執(zhí)行完第g.步操作之后，則計算各條新染色體的適應(yīng)度值，然后返回第d.步操作，進(jìn)行新一輪迭代。

i.確定算法終止條件。

通過設(shè)定進(jìn)化迭代次數(shù)來終止算法。

步驟d.在步驟c.經(jīng)過一定迭代次數(shù)后，染色體逐漸趨于穩(wěn)定，而對應(yīng)基因序列便為所要求解的最優(yōu)飛機(jī)出庫方案。

3 實例仿真

本節(jié)以尼米茲級航母為初始環(huán)境，對本文方法進(jìn)行了仿真應(yīng)用。

3.1 基礎(chǔ)模型的建立

3.1.1 機(jī)庫出庫環(huán)境模型的建立

利用矩形區(qū)域表示尼米茲航母機(jī)庫，如圖3所示。

圖3 任務(wù)T4局部機(jī)庫模型

其中，坐標(biāo)原點設(shè)在矩形區(qū)域的左上角，向右為X軸正方向，向下為Y軸正方向。按照比例進(jìn)行縮放，設(shè)定機(jī)庫大小為1 000×158 pix（pix為像素）。不同類型的飛機(jī)用不同的實體模型進(jìn)行表示。各飛機(jī)布放參數(shù)如表1所示。

表1 T4飛機(jī)機(jī)庫布放參數(shù)

另外，各架飛機(jī)所要調(diào)往艦面（1 597×369 pix）的停機(jī)位也互不相同，如圖4所示。

圖4 機(jī)庫各飛機(jī)調(diào)往目的地分布圖

其中，機(jī)庫中1號飛機(jī)調(diào)往艦面1號位置；2號飛機(jī)調(diào)往艦面2號位置；依此類推。各艦面目的停機(jī)位坐標(biāo)如表2所示。

表2 各飛機(jī)調(diào)運(yùn)目的地參數(shù)

3.1.2 出庫任務(wù)T4的建立

任務(wù)T4要求如圖所示局部機(jī)庫環(huán)境中的12架飛機(jī)，使用1號升降機(jī)執(zhí)行出庫操作（一次出庫2架），并分別調(diào)往各自預(yù)定艦面停機(jī)位。目標(biāo)是給出某種最優(yōu)出庫方案，使得在優(yōu)先保證12架飛機(jī)出庫時間最短的基礎(chǔ)上，也盡可能縮短其總的移動距離。

3.2 NGA算法相關(guān)具體設(shè)置

3.2.1 染色體長度設(shè)置

染色體的長度應(yīng)該與需要出庫的飛機(jī)數(shù)量相等。任務(wù)T4需要出庫12架飛機(jī)，所以染色體長度應(yīng)為12。即

其中，Xi代表第i條染色體，也即為第i種飛機(jī)出庫方案。每一維aij代表第條i染色體的第j個基因，用第j架順序出庫的飛機(jī)所處的機(jī)庫停機(jī)位編號予以表示。

3.2.2 適應(yīng)度函數(shù)的動態(tài)設(shè)置

3.2.2.1 飛機(jī)總的出庫時間計算公式

此處飛機(jī)總的出庫時間指從第1架飛機(jī)開始執(zhí)行出庫操作，直到最后一架飛機(jī)移動到艦面指定位置為止的整個時間。

尼米茲航母飛機(jī)出庫一般流程為（以兩架飛機(jī)A和B出庫過程為例）：

①飛機(jī)A由機(jī)庫停機(jī)位移至升降機(jī)入口位置；

②飛機(jī)A進(jìn)一步移至升降機(jī)，并進(jìn)行系留等操作；

③飛機(jī)B由機(jī)庫停機(jī)位移至升降機(jī)入口位置；

④飛機(jī)B進(jìn)一步移至升降機(jī)，并進(jìn)行系留等操作；

⑤升降機(jī)將A和B升至艦面；與此同時，下一架飛機(jī)開始執(zhí)行①操作；

⑥飛機(jī)A和B執(zhí)行解除系留等操作，由升降機(jī)移至各自艦面目的停機(jī)位；

⑦升降機(jī)降回機(jī)庫，準(zhǔn)備接收下兩架飛機(jī)。

為此，以出庫1架飛機(jī)時的出庫時間為基礎(chǔ)，即

則可以給出當(dāng)出庫不同情況時的出庫時間計算公式如下：

●當(dāng)出庫奇數(shù)k（k≥3）架飛機(jī)的出庫時間計算公式：

●當(dāng)出庫偶數(shù)l（l≥2）架飛機(jī)的出庫時間計算公式：

其中，各參數(shù)定義如表3所示。

表3 符號定義

3.2.2.2 飛機(jī)總的移動距離計算公式

每一架飛機(jī)的移動距離包括兩部分：一是飛機(jī)在機(jī)庫中的移動距離；二是飛機(jī)由升降機(jī)移至目的地的距離。而總的移動距離為所有飛機(jī)移動距離之和。

其中，si表示某種出庫方案中第i架順序出庫的飛機(jī)總的移動距離，包括：由其所處的停機(jī)位移至1號升降機(jī)入口的距離si，1；由1號升降機(jī)移至艦面目的地的距離 si，2。

3.3 實例分析

3.3.1 基于NGA算法的問題求解

利用NGA算法對該問題進(jìn)行求解，結(jié)果如表4所示。

表4 基于NGA的最短出動時間和移動距離

3.3.2 基于枚舉法的問題求解

為了驗證本章方法的有效性，此處另外采用枚舉法對同一出庫任務(wù)T4進(jìn)行求解，給出全局最優(yōu)精確解。所得結(jié)果如表5所示。

表5 枚舉法計算結(jié)果

3.3.3 計算結(jié)果比較

3.3.3.1 所得出庫方案結(jié)果比較

由表4和表5可以看出，基于本章方法所得的出庫時間與基于枚舉法的全局精確出庫時間差為|801-800.4|=0.6 s；移動距離之差|1 098.3-1 097.6|=0.7m。另外，枚舉法單次計算的時間為約20 h，而NGA方法僅用約90 s。

由此可知，基于本文方法所得方案與全局精確值誤差較小，基本可以忽略不計，且計算時間較短，這表明本章方法在求解尼米茲級航母飛機(jī)機(jī)庫出庫調(diào)度問題時具有較好的有效性和快速性。

3.3.3.2 出庫示例分析

此處以NGA算法所得出的全局近似最優(yōu)出庫方案（1；2；5；4；10；12；9；3；8；7；11；6）為例進(jìn)行說明：

●優(yōu)先出庫阻礙其他飛機(jī)正常使用升降機(jī)的飛機(jī)，即1、2號飛機(jī)。

●出庫5號飛機(jī)。在1、2號飛機(jī)已經(jīng)出庫前提下，5號飛機(jī)與升降機(jī)之間存在可行路徑。

●出庫4號飛機(jī)。在1、2號飛機(jī)已經(jīng)出庫前提下，4號飛機(jī)與升降機(jī)之間存在可行路徑。

●出庫10號飛機(jī)。在1、2、5號飛機(jī)已經(jīng)出庫前提下，10號飛機(jī)與升降機(jī)之間存在可行路徑。

●出庫12號飛機(jī)。在2、4號飛機(jī)已經(jīng)出庫前提下，12號飛機(jī)與升降機(jī)之間存在可行路徑。

●出庫9號飛機(jī)。在1、2、5、10號飛機(jī)已經(jīng)出庫前提下，9號飛機(jī)與升降機(jī)之間存在可行路徑。

●出庫3號飛機(jī)。在2號飛機(jī)已經(jīng)出庫前提下，3號飛機(jī)與升降機(jī)之間存在可行路徑。

●出庫 8號飛機(jī)。在 1、2、5、9、10號飛機(jī)已經(jīng)出庫前提下，8號飛機(jī)與升降機(jī)之間存在可行路徑。

●出庫 7號飛機(jī)。在 1、2、5、8、9、10號飛機(jī)已經(jīng)出庫前提下，7號飛機(jī)與升降機(jī)之間存在可行路徑。

●出庫11號飛機(jī)。在1、2、4號飛機(jī)已經(jīng)出庫前提下，11號飛機(jī)與升降機(jī)之間存在可行路徑。

●最后出庫6號飛機(jī)。

該方案綜合考慮了各架飛機(jī)所處機(jī)庫停機(jī)位及其所要調(diào)往的艦面停機(jī)位，在確保了每架飛機(jī)出庫時具有可行路徑的基礎(chǔ)上，給出的飛機(jī)最優(yōu)出庫順序，與實際要求相符。這表明基于本文方法在求解尼米茲級航母飛機(jī)機(jī)庫出庫調(diào)度問題時具有較好可行性。

4 結(jié)論

本文針對艦載機(jī)多機(jī)出庫問題進(jìn)行了優(yōu)化研究。分析了艦載機(jī)出庫調(diào)度問題，并建立了需要優(yōu)化的數(shù)學(xué)模型；為了解決該問題，在分析GA算法的基礎(chǔ)上，通過對交叉和變異策略進(jìn)行改變，并融入執(zhí)行路徑探測和規(guī)劃的通視圖算法，形成了適用于優(yōu)化艦載機(jī)出庫問題的NGA算法；將NGA算法在尼米茲航母的艦載機(jī)多機(jī)出庫問題上進(jìn)行仿真應(yīng)用，結(jié)果表明該方法無論在結(jié)果的準(zhǔn)確性，還是在計算時間上的快速性等都滿足實際要求。

［1］譚曉寅，徐忠平，鄭文祥.現(xiàn)代戰(zhàn)爭武器揭秘—航母［M］.上海：百家出版社，2008.

［2］韓維，王慶官.航母與飛機(jī)概論［M］.煙臺:海軍航空工程學(xué)院出版，2009：10-120.

［3］ Jeffrey S.Feasibility Study of Global-Positioning-System-Based Aircraft-Carrier Flight-Deck Persistent Monitoring System［C］//JOURNAL OF AIRCRAFT，2010，47（5）.

［4］孫詩南.現(xiàn)代航空母艦［M］.上海:科學(xué)普及出版社，2000:1-100.

［5］ Jeffrey S J.A Feasibility Study of a Persistent Monitoring System for the Flight Deck of U.S.Navy Aircraft Carriers［D］.DEPARTMENTOF THE AIR FORCE AIR UNIVERSITY，2009.

［6］ Authority of the Chief of Naval Operations.NAVAIR 00-80T-120.CV Flight/Hangar Deck NATOPS Manual［R］.WASHINGTON，D.C.，2001.

［7］馮強(qiáng)，曾生奎，康銳.基于多主體的艦載機(jī)綜合保障過程建模方法 ［J］.系統(tǒng)工程與電子技術(shù)，2010，32（1）：211-216.

［8］ Asano T，Guibas L，Hershberger J，et al.Visibility-polygon Search and Euclidean ShortestPath［C］//Berkeley，CA:The Proceedingsof26th Symposium on FoundationsofComputer Science，1989:155-164.

［9］王小平，曹立明.遺傳算法理論、應(yīng)用與軟件實現(xiàn)［M］.西安:西安交通大學(xué)出版社，2002:1-50，124-141.

［10］Dieguez A R，Sanz R，Lopez J.Deliberative on-line Local Path Planning for Autonomous Mobile Robots［J］.Journal of Intelligentand Robotic Systems，2003，37（1）：1219.

［11］鄭昌文，嚴(yán)平，丁明躍，等.飛行器航跡規(guī)劃［M］.北京：國防工業(yè)出版社，2008：70-79.

［12］楊毅，劉亞辰.一種基于凸殼的智能服務(wù)機(jī)器人路徑規(guī)劃算法［J］.北京理工大學(xué)學(xué)報，2011，31（1）：54-58.

［13］韓維，司維超，丁大春，等.基于聚類PSO算法的飛機(jī)艦面多路徑動態(tài)規(guī)劃［J］.北京航空航天大學(xué)學(xué)報，2013，39（5）：610-614.

Hangar-exporting Optim ization ScheduleofM ulti-carrier Plane Based on NGA

SIWei-chao，QIYu-dong，HANWei
（Naval Aeronautical and Astronautical university，Yantai264001，China）

In order to reduce carrier plane hangar-exporting time and optimize sequence in complicated hangar environment，it researched the carrier plane hangar-exporting optimization problem.Firstly，the mathematic model of carrier plane hangar-exporting optimization problem is established.Secondly，it designed NGA algorithm which is suitable for solving the problem.NGA changed original crossover and variation tactics of GA in order to suit hangar-exporting problem，and combined Visibility Graph Algorithm which is used to detect and plan route.Finally，it used NGA and enumeration to solve the carrier plane hangar-exporting optimization problem （T4） in hangar of Nimetz aircraft carrier separately.Results are that the shortest hangar-exporting time is 801 s and shortest distance is 1098.3m based on NGA;based on enumeration it is 800.4 s and 1 097.6 m.From the results，we can know that the difference of results based on NGA and enumeration is small，and it is suitable for using NGA to solve the carrier plane hangar-exporting optimization problem.

carrier plane，hangar-exporting optimization，NGA，enumeration method，nimetz aircraft carrier

TP202；E9

A

1002-0640（2015）11-0013-07

2014-10-25

2014-11-12

軍隊“十二五”預(yù)先研究基金資助項目

司維超（1984- ），男，山東淄博人，博士，講師。研究方向：指揮控制。