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

劉生學 王公寶 胡 忠

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

?

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

劉生學1王公寶1胡 忠2

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

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

遺傳算法; Matlab; 優化

Class Number TP301

1 引言

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

2 軍用飛機起降調度的約束條件

針對軍用飛機的起降調度問題,本文主要從作戰效能和飛行安全的角度出發,構建了起降調度的數學模型,該模型的約束條件主要包括時間窗口約束和尾流間隔約束。

2.1 時間窗口約束

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

2.2 尾流間隔約束

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

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

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

3 軍用飛機起降調度的數學模型

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

n:起降軍機的數量;

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

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

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

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

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

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

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

Ei:max{0,ti-xi};

Ti:max{0,xi-ti}。

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

(1)

4 算法的實現

4.1 染色體編碼方案

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

圖1 染色體編碼

4.2 解碼

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

(2)

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

4.3 種群的初始化

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

4.4 適應度函數

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

(3)

4.5 選擇運算

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

4.6 交叉運算

為使得后代交叉運算結果的合理性,交叉算子在隨機確定交叉的位置后,首先需對兩個父代個體的相應基因進行交換,然后從相應的父代個體中按照原來的基因順序將不重復的基因拷貝到對應的子代個體中,如圖2所示。

圖2 交叉運算

4.7 變異運算

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

圖3 變異運算

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

5 仿真結果與分析

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

表2 軍用飛機起降參數

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

表3 數值仿真結果

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

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

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

6 結語

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

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

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

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

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

[4] 楊秋輝,游至勝,馮子亮,等.自適應遺傳算法在飛機調度問題中的應用[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] 胡毓達.實用多目標最優化[M].上海:上海科學技術出版社,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].航空計算技術,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