劉生學 王公寶 胡 忠

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

?

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

劉生學1王公寶1胡 忠2

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

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

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

Class Number TP301

1 引言

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

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

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

2.1 時間窗口約束

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

2.2 尾流間隔約束

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

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

注:1,2,3分別代表進場著陸的重型機、中型機和輕型機;4,5,6分別代表離場起飛的重型機、中型機和輕型機。

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

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

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

ti:軍機i的計劃起飛/降落時刻;

ei:軍機i的最早起飛/降落時刻;

li:軍機i的最晚起飛/降落時刻;

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

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

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

xi:軍機i的實際起飛/降落時刻;

Ei:max{0,ti-xi};

Ti:max{0,xi-ti}。

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

(1)

4 算法的實現(xiàn)

4.1 染色體編碼方案

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

圖1 染色體編碼

4.2 解碼

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

(2)

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

4.3 種群的初始化

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

4.4 適應度函數(shù)

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

(3)

4.5 選擇運算

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

4.6 交叉運算

為使得后代交叉運算結(jié)果的合理性,交叉算子在隨機確定交叉的位置后,首先需對兩個父代個體的相應基因進行交換,然后從相應的父代個體中按照原來的基因順序?qū)⒉恢貜偷幕蚩截惖綄淖哟鷤€體中,如圖2所示。

圖2 交叉運算

4.7 變異運算

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

圖3 變異運算

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

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

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

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

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

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

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

圖4 各飛機的實際起降時刻

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

6 結(jié)語

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

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

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

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

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

[4] 楊秋輝,游至勝,馮子亮,等.自適應遺傳算法在飛機調(diào)度問題中的應用[J].四川大學學報,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] 胡毓達.實用多目標最優(yōu)化[M].上海:上?？茖W技術出版社,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] 余江,羅曉利.遺傳算法在飛機著陸調(diào)度問題上的應用[J].航空計算技術,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日

劉生學,男,碩士研究生,研究方向:軍事運籌學。

TP301

10.3969/j.issn1672-9730.2015.02.009