劉生學(xué) 王公寶 胡 忠

(1.海軍工程大學(xué)理學(xué)院 武漢 430033)(2.海軍工程大學(xué)兵器工程系 武漢 430033)

?

基于遺傳算法的軍用飛機(jī)智能起降調(diào)度方法研究*

劉生學(xué)1王公寶1胡 忠2

(1.海軍工程大學(xué)理學(xué)院 武漢 430033)(2.海軍工程大學(xué)兵器工程系 武漢 430033)

計(jì)及軍用飛機(jī)起降過(guò)程中的時(shí)間窗口約束和尾流間隔約束條件,基于遺傳算法建立了軍用飛機(jī)智能起降調(diào)度的數(shù)學(xué)模型。飛機(jī)隊(duì)列順序采用整數(shù)染色體編碼方案,依據(jù)初始化種群、求解適應(yīng)度函數(shù)和輪盤賭方式的選擇操作,并配合相應(yīng)的交叉、變異算子,對(duì)軍用飛機(jī)航班規(guī)劃問(wèn)題進(jìn)行了求解和優(yōu)化。通過(guò)仿真計(jì)算,并與其他調(diào)度方法進(jìn)行對(duì)比分析,驗(yàn)證和說(shuō)明了所采用的模型和算法的有效性。

遺傳算法; Matlab; 優(yōu)化

Class Number TP301

1 引言

軍用飛機(jī)起降頻率及其時(shí)刻的確定是軍用航班規(guī)劃的重要內(nèi)容之一[1]。軍用飛機(jī)在某一時(shí)段內(nèi)進(jìn)駐同一機(jī)場(chǎng),其起飛和著陸是一個(gè)循環(huán)使用機(jī)場(chǎng)的過(guò)程,此時(shí)軍用飛機(jī)的出動(dòng)強(qiáng)度較大,而且對(duì)起降時(shí)刻和操作安全的要求較高。因此,采用一定的優(yōu)化策略對(duì)軍用機(jī)場(chǎng)的有限資源進(jìn)行科學(xué)合理的配置,不僅可以顯著提高人員的工作效率,而且可以有效加速空中戰(zhàn)斗力的生成?，F(xiàn)實(shí)軍用空管中的輔助工具一般由人工調(diào)度和智能調(diào)度兩種模式組成[2],其中人工調(diào)度完全基于管制員的個(gè)人經(jīng)驗(yàn),在交通繁忙的情形下往往調(diào)度效率低下,夜間疲勞時(shí)易危及飛行安全。近年來(lái),隨著航班規(guī)劃問(wèn)題規(guī)模的增大及目標(biāo)函數(shù)的復(fù)雜化,文獻(xiàn)[3～6]嘗試采用數(shù)學(xué)規(guī)劃方法研究機(jī)場(chǎng)飛機(jī)的智能起降調(diào)度問(wèn)題。作為一類智能優(yōu)化,遺傳算法具有很強(qiáng)的全局優(yōu)化能力,適合于求解眾多的最優(yōu)化問(wèn)題[7]。本文基于整數(shù)編碼方案和相應(yīng)的交叉、變異算子,將遺傳算法應(yīng)用于軍用飛機(jī)的智能起降調(diào)度問(wèn)題之中,對(duì)軍用飛機(jī)航班規(guī)劃問(wèn)題進(jìn)行了求解和優(yōu)化。通過(guò)仿真計(jì)算,并與其他調(diào)度方法進(jìn)行對(duì)比分析,驗(yàn)證和說(shuō)明了所采用的模型和算法的有效性。

2 軍用飛機(jī)起降調(diào)度的約束條件

針對(duì)軍用飛機(jī)的起降調(diào)度問(wèn)題,本文主要從作戰(zhàn)效能和飛行安全的角度出發(fā),構(gòu)建了起降調(diào)度的數(shù)學(xué)模型,該模型的約束條件主要包括時(shí)間窗口約束和尾流間隔約束。

2.1 時(shí)間窗口約束

為了最大限度地發(fā)揮軍用飛機(jī)的作戰(zhàn)效能,軍機(jī)起降時(shí)間必須限制在一定的時(shí)間窗口內(nèi)。對(duì)于起飛軍機(jī),過(guò)早起飛則可能導(dǎo)致浪費(fèi)作戰(zhàn)資源;過(guò)晚起飛,則可能導(dǎo)致無(wú)法完成任務(wù)。對(duì)于降落軍機(jī),最早降落時(shí)刻為軍機(jī)保持最大飛行速度返航降落的時(shí)刻,最晚降落時(shí)刻為確保燃油能夠使得軍機(jī)安全降落的最大時(shí)刻。

2.2 尾流間隔約束

依據(jù)空氣動(dòng)力學(xué)原理,飛機(jī)在飛行過(guò)程中會(huì)產(chǎn)生“尾流”,如果它后面的飛機(jī)距離太近則會(huì)失去飛行平衡,從而造成飛行事故。國(guó)際民航組織(ICAO)將最大起飛重量在136噸以上的飛機(jī)定義為重型機(jī),7～136噸之間的飛機(jī)定義為中型機(jī),7噸以下的飛機(jī)定義為輕型機(jī),并規(guī)定了無(wú)風(fēng)條件下不同類型飛機(jī)之間尾流間隔的最低標(biāo)準(zhǔn)[8],如表1所示(單位:s)。例如,對(duì)于需進(jìn)場(chǎng)著陸的兩重型機(jī)(機(jī)型均為1),前機(jī)和后機(jī)之間的尾流間隔至少應(yīng)大于60s,這樣才能有效避免起飛飛機(jī)遭遇尾流影響。

表1 飛機(jī)之間的尾流間隔(s)

注:1,2,3分別代表進(jìn)場(chǎng)著陸的重型機(jī)、中型機(jī)和輕型機(jī);4,5,6分別代表離場(chǎng)起飛的重型機(jī)、中型機(jī)和輕型機(jī)。

3 軍用飛機(jī)起降調(diào)度的數(shù)學(xué)模型

在軍用飛機(jī)起降調(diào)度模型中,主要涉及如下的參數(shù)或變量,其符號(hào)及物理含義表述如下。

n:起降軍機(jī)的數(shù)量;

ti:軍機(jī)i的計(jì)劃起飛/降落時(shí)刻;

ei:軍機(jī)i的最早起飛/降落時(shí)刻;

li:軍機(jī)i的最晚起飛/降落時(shí)刻;

Sji:軍機(jī)j和i之間的最小尾流間隔;

gi:軍機(jī)i早于ti起飛/降落造成不利影響的單位系數(shù);

hi:軍機(jī)i晚于ti起飛/降落造成不利影響的單位系數(shù);

xi:軍機(jī)i的實(shí)際起飛/降落時(shí)刻;

Ei:max{0,ti-xi};

Ti:max{0,xi-ti}。

n架軍機(jī)的起降,會(huì)形成一個(gè)起降隊(duì)列p。所謂軍機(jī)起降調(diào)度問(wèn)題,就是在滿足時(shí)間窗口約束和尾流間隔約束的前提下,尋找一個(gè)最優(yōu)的起降隊(duì)列p,使得軍機(jī)的實(shí)際起降時(shí)刻與計(jì)劃起降時(shí)刻之間的誤差對(duì)作戰(zhàn)造成的不利影響最小。定義軍用飛機(jī)起降時(shí)刻的誤差對(duì)作戰(zhàn)造成的不利影響函數(shù)為f(p),則軍用飛機(jī)起降調(diào)度的數(shù)學(xué)模型可描述如下:

(1)

4 算法的實(shí)現(xiàn)

4.1 染色體編碼方案

在飛機(jī)編號(hào)中為充分體現(xiàn)軍用飛機(jī)的航班號(hào)或呼叫號(hào)[9],本文對(duì)染色體采用整數(shù)編碼的思想。此處一個(gè)飛機(jī)的起降隊(duì)列定義為一個(gè)染色體,每個(gè)染色體由n個(gè)整數(shù)組成,每個(gè)基因值代表一架飛機(jī),一個(gè)染色體代表一種調(diào)度方案,表示安排軍機(jī)的一種順序。在一條染色體中,每個(gè)基因值均會(huì)出現(xiàn),且出現(xiàn)次數(shù)僅有一次。比如某一染色體為124356,則表示首先為1號(hào)軍機(jī)安排降落時(shí)間,然后依次安排2、4、3、5、6軍機(jī),如圖1所示。這種編碼方案的優(yōu)點(diǎn)在于其簡(jiǎn)練而直觀,便于數(shù)值實(shí)現(xiàn)。

圖1 染色體編碼

4.2 解碼

具體的解碼過(guò)程是:按照染色體中第i架軍機(jī)的次序,安排實(shí)際的調(diào)度時(shí)間xi,首先令xi等于最早起降時(shí)刻ei,這樣可以盡可能早地為軍機(jī)安排調(diào)度時(shí)刻,避免因延誤而對(duì)戰(zhàn)機(jī)造成不利影響。如果最早時(shí)刻不能滿足尾流約束,這樣就會(huì)對(duì)作戰(zhàn)造成一定的不利影響;同時(shí),飛機(jī)的實(shí)際調(diào)度時(shí)刻會(huì)在滿足尾流約束的基礎(chǔ)上產(chǎn)生一定的延誤。這里定義一個(gè)延誤系數(shù),表示由于延誤對(duì)人的判斷有一定的影響,從而對(duì)戰(zhàn)機(jī)造成影響的一個(gè)隨機(jī)因子,本文的延誤系數(shù)隨機(jī)取為0～0.05。故軍機(jī)的起飛時(shí)刻模型可采用下式描述

(2)

式中:rand是擾動(dòng)因子,為處于[0,1]之間服從均勻分布的隨機(jī)數(shù),該參數(shù)的引入可有效避免算法陷入局部最優(yōu)。依據(jù)上述解碼方法,則可確定每條染色體中全部軍機(jī)的實(shí)際起飛時(shí)刻。

4.3 種群的初始化

在遺傳算法中,種群規(guī)模和初始種群的質(zhì)量對(duì)運(yùn)算過(guò)程及數(shù)值結(jié)果有較大的影響。為確保初始種群的多樣性和數(shù)值解的可行性,在種群初始化中采用FCFS(First Come First Serve)策略,令其中一條染色體按照軍機(jī)的先后起降順序排列;其余1/3的染色體為1～20的序列,由每?jī)蓚€(gè)數(shù)隨機(jī)產(chǎn)生;還有1/3的染色體為1～20的序列中每三個(gè)數(shù)隨機(jī)產(chǎn)生;最后剩下的染色體為隨機(jī)產(chǎn)生的序列。

4.4 適應(yīng)度函數(shù)

適應(yīng)度函數(shù)的設(shè)計(jì)通常要與問(wèn)題的求解目標(biāo)相關(guān)。由于飛機(jī)調(diào)度問(wèn)題的目標(biāo)函數(shù)值越小越好,而通常遺傳算法中認(rèn)為適應(yīng)度大的個(gè)體其適應(yīng)性較好,本文設(shè)計(jì)的適應(yīng)度函數(shù)如下:

(3)

4.5 選擇運(yùn)算

采用輪盤賭方式,可依據(jù)適應(yīng)度函數(shù)的大小決定群體中個(gè)體被選中的概率,這體現(xiàn)了自然界中的適者生存原則。

4.6 交叉運(yùn)算

為使得后代交叉運(yùn)算結(jié)果的合理性,交叉算子在隨機(jī)確定交叉的位置后,首先需對(duì)兩個(gè)父代個(gè)體的相應(yīng)基因進(jìn)行交換,然后從相應(yīng)的父代個(gè)體中按照原來(lái)的基因順序?qū)⒉恢貜?fù)的基因拷貝到對(duì)應(yīng)的子代個(gè)體中,如圖2所示。

圖2 交叉運(yùn)算

4.7 變異運(yùn)算

由于染色體中飛機(jī)編號(hào)必須且只能出現(xiàn)一次,為了保證后代變異運(yùn)算后的合理性,本文采用染色體中相鄰基因進(jìn)行位置交換的方式處理變異運(yùn)算。首先隨機(jī)確定變異位置,再將該位置上的基因與該位置之后的基因進(jìn)行交換,如圖3所示,這種概率較大的變異算子將有助于優(yōu)化結(jié)果的快速獲得。

圖3 變異運(yùn)算

在種群規(guī)模的控制上,本文采用保持固定種群規(guī)模的策略,在每一代的進(jìn)化過(guò)程中,保留最佳個(gè)體,去掉最差個(gè)體,而個(gè)體的總數(shù)在進(jìn)化過(guò)程中保持不變。在這種情況下,算法將快速收斂并得到最優(yōu)解。同時(shí),這也便于計(jì)算機(jī)使用固定的內(nèi)存需求以確保算法的快速實(shí)現(xiàn)。

5 仿真結(jié)果與分析

本文選擇某單跑道機(jī)場(chǎng)內(nèi)20架軍機(jī)進(jìn)行仿真驗(yàn)證,表2羅列了各軍機(jī)的起降機(jī)型、起降時(shí)刻、最早起降時(shí)刻、最晚起降時(shí)刻及其對(duì)飛機(jī)起降造成不利影響的單位系數(shù),各參數(shù)的物理含義詳見(jiàn)文中第3節(jié)相關(guān)內(nèi)容。

表2 軍用飛機(jī)起降參數(shù)

根據(jù)該算法的實(shí)現(xiàn)理論,在Matlab中編制了仿真程序。經(jīng)過(guò)進(jìn)化計(jì)算,同時(shí)保留每一代中的最優(yōu)個(gè)體,最后再?gòu)乃械淖顑?yōu)個(gè)體中選擇出最佳的調(diào)度序列和起降時(shí)刻,并與文獻(xiàn)[2]提出的粒子群和FCFS策略的結(jié)果進(jìn)行比較,表3給出了仿真計(jì)算的結(jié)果。

表3 數(shù)值仿真結(jié)果

由表3可知,運(yùn)用遺傳算法計(jì)算得出的結(jié)果相比粒子群算法和FCFS策略所得結(jié)果更優(yōu),其中遺傳算法與粒子群算法得到的目標(biāo)函數(shù)值相近,比FCFS策略的結(jié)果要低48%,這表明了遺傳算法在優(yōu)化軍用飛機(jī)起降調(diào)度問(wèn)題中的優(yōu)勢(shì)。

圖4 各飛機(jī)的實(shí)際起降時(shí)刻

為進(jìn)一步驗(yàn)證結(jié)果的正確性,將軍機(jī)的最早、最晚、計(jì)劃、實(shí)際起降時(shí)刻進(jìn)行比較(見(jiàn)圖4)。由圖4可知,飛機(jī)的實(shí)際起降時(shí)刻均在其最早和最晚起降時(shí)刻之間,這樣可保證結(jié)果滿足時(shí)間窗口約束;另外,實(shí)際起降時(shí)刻都在計(jì)劃起降時(shí)刻附近,這表明該算法所求得結(jié)果的正確性。

6 結(jié)語(yǔ)

從軍用飛機(jī)的作戰(zhàn)效能和起降安全的角度出發(fā),基于遺傳算法建立了軍用飛機(jī)智能起降調(diào)度的數(shù)學(xué)模型。通過(guò)引入時(shí)間窗口約束和尾流間隔約束,該模型可適當(dāng)?shù)卣{(diào)整部分軍機(jī)的起降序列,有效提高戰(zhàn)機(jī)進(jìn)場(chǎng)著陸和離場(chǎng)起飛的效率,進(jìn)而獲得較優(yōu)的作戰(zhàn)效果。針對(duì)軍用飛機(jī)起降調(diào)度的特點(diǎn),分別設(shè)計(jì)了遺傳算法的編碼方法、適應(yīng)度函數(shù)、遺傳算子(選擇、交叉、變異運(yùn)算)等,并通過(guò)計(jì)算機(jī)仿真驗(yàn)證了其優(yōu)良性能。

在結(jié)果分析方面,將本文所提出的算法與粒子群算法和FCFS策略進(jìn)行比較,發(fā)現(xiàn)本文算法優(yōu)化所得的結(jié)果明顯比粒子群算法和FCFS策略得到的結(jié)果優(yōu)異,這說(shuō)明了該算法具有良好的優(yōu)化性能。

[1] 馮心玲,龔月嬌,林映霞,等.用遺傳算法優(yōu)化航班規(guī)劃問(wèn)題[J].計(jì)算機(jī)工程與設(shè)計(jì),2009,30(19):4468-4471.

[2] 胡訓(xùn)強(qiáng),謝曉方,李德棟.軍用飛機(jī)智能起降調(diào)度技術(shù)研究[J].系統(tǒng)工程與電子技術(shù),2012,34(11):2280-2284.

[3] 孫宏,張翔,徐杰.應(yīng)用模擬退火算法求解飛機(jī)調(diào)度問(wèn)題[J].飛行力學(xué),2006,24(2):84-87.

[4] 楊秋輝,游至勝,馮子亮,等.自適應(yīng)遺傳算法在飛機(jī)調(diào)度問(wèn)題中的應(yīng)用[J].四川大學(xué)學(xué)報(bào),2004,41(6):1158-1162.

[5] Hu X B,Paolo E D.Binary-representation-based genetic algorithm for aircraft arrival sequencing and scheduling[J].IEEE Trans on Intelligent Transportation System,2008,9(2):301-310.

[6] Chou T Y,Liu T K,Lee C N,et al.Method of inequality-based multiobjective genetic algorithm for domestic daily aircraft routing[J].IEEE Trans on Systems,2008,38(2):299-308.

[7] 胡毓達(dá).實(shí)用多目標(biāo)最優(yōu)化[M].上海:上海科學(xué)技術(shù)出版社,1990.

[8] Beasley J E,Krishnamoorthy M,Sharaiha Y M,et al.Scheduling aircraft landings-the static case[J].Transportation Science,2000,34(2):180-197.

[9] 余江,羅曉利.遺傳算法在飛機(jī)著陸調(diào)度問(wèn)題上的應(yīng)用[J].航空計(jì)算技術(shù),2007,37(3):1-4.

An Intelligent Method for the Depart-and-Land Scheduling of Military Aircraft Based on Genetic Algorithm

LIU Shengxue1WANG Gongbao1HU Zhong2

(1.College of Science,Naval University of Engineering,Wuhan 430033)(2.Department of Weaponry Engineering,Naval University of Engineering,Wuhan 430033)

Based on the genetic algorithm,an intelligent method is proposed for the depart-and-land scheduling of military aircraft,where the time window and vortex separation constraints are taken into account in the course of departure and landing processes.For the sequencing problem,the aircraft are numbered by the integer chromosome codes.According to the population initialization,fitness-function implementation and selecting operation in the roulette form,the military aircraft planning problem is resolved and optimized with the corresponding crossover and mutation operators.Through the comparison of other two scheduling methods,the effectiveness of the model and algorithm presented is validated in the simulation process.

genetic algorithm,Matlab,optimization

2014年8月6日,

2014年9月21日

劉生學(xué),男,碩士研究生,研究方向:軍事運(yùn)籌學(xué)。

TP301

10.3969/j.issn1672-9730.2015.02.009