雙交叉算子遺傳算法在終端區飛機排序中的應用①

趙 儼,樂 俊,劉 丹

1(電子科技大學 電子科學技術研究院,成都 611731)

2(西南電子電信技術研究所,成都 610041)

雙交叉算子遺傳算法在終端區飛機排序中的應用①

趙 儼1,樂 俊2,劉 丹1

1(電子科技大學 電子科學技術研究院,成都 611731)

2(西南電子電信技術研究所,成都 610041)

當今,普遍的航班延誤現象不僅增加了巨額飛行成本,還影響乘客體驗. 對終端區待降飛機隊列進行合理調整,可以提高跑道利用率,減少航班延誤,達到降低延誤代價的效果. 針對終端區飛機排序問題,提出一種包含雙交叉算子的遺傳算法,針對不同適應度染色體采取不同的交叉操作,使得在交叉過程中既能保護優質染色體,也能使其它染色體繼續進化. 同時引入重排算子對變異后的子代進行優化,共同加快遺傳算法收斂速度,使其更加符合實際使用需求. 實驗結果表明,算法收斂速度得到改進,能在可接受時間內得到可行解.

空中交通管制; 終端區; 飛機排序; 遺傳算法; 交叉算子

隨著國際民航運輸的高速發展,我國對民航運輸的需求日益提高,飛行器的數量也隨之增加. 伴隨空中交通流量的快速增長,機場、空域和航線普遍出現了擁堵現象. 2016年我國民航平均航班正常率為76.76%,較前兩年雖有回升,但與美、日等國比較,仍有較大差距. 終端區擁堵不僅造成航班延誤,還會存在安全隱患,引發安全事故. 通過對終端區飛機隊列的合理排序,可有效的提高跑道容量,緩和擁堵,進而減少飛機延誤[1].

目前,國內常用的飛機排序方式是先到先服務算法,即僅根據飛機的預計到場時間進行排序. 該算法的優勢在于實現簡便、易操作,但會產生較大的延誤代價. 此外,較常見的排序算法還有滑動窗優化算法[2]、約束位置交換算法[3]、時間提前量算法[4]和模糊模式識別算法[5]等確定性優化算法. 但隨著飛機數量的增加,確定性優化算法難以在可接受的時間內得出高復雜度排序問題的結果. 終端區飛機排序問題已被歸為NP難問題,使用常規算法求最優解已不切實際.

1975年由Michigan大學的John Holand教授與其同事提出的遺傳算法 (Genetic algorithm,GA)[6]具有良好的全局搜索能力、潛在并行性、可擴展性等優點,適合用于解決此類問題. 許多科研人員通過對傳統遺傳算法進行改進并融入其他算法或約束條件,提出了許多針對飛機排序的算法. 常會賢、曲世茹利用矩陣編碼為飛機隊列在多跑道降落的問題提出解決方案[7];白重陽等人利用遺傳算法對飛機的速度進行調整,使得飛機在終端區航路沖突極小,從而減少飛機延誤[8].陳亮等人對飛機延誤代價系數的計算進行了討論,指出代價系數會根據飛機類型和等待時間等因素的影響而動態改變. 根據該系數得出的飛機延誤總代價模型更具有實際意義,而不再是片面的考慮如何將總延誤時間降至最低[9].

在飛機排序的實際應用場景中,要求在可接受的時間范圍內得到可以減少飛機延誤的飛機排序隊列.這不僅對排序質量有要求,排序的效率也不可忽視. 本文主要受文獻[10]中提出的“交叉掩碼”的概念和使用方式的啟發,采取針對不同適應度的染色體采用雙交叉算子分別處理的方式,達到既能保證優質染色體平穩進化,又不會影響其他染色體的進化速度的目的,使種群進化方向更加明確,從而加快算法收斂速度.

1 建立算法模型

1.1 終端區環境

由于機場附近的航線非常復雜,飛機在此空域活動頻繁,因此需要設立終端管制區進行合理管制. 飛機的起飛和降落都將在該區域接受管制員的調度,安全、有序的完成離場和進場. 終端區結構如圖1所示.

終端區的定義和作用使其成為了極其復雜的區域,也是造成空中交通擁堵的關鍵因素. 僅僅依靠新建跑道或擴大終端區等改善硬件條件的方法已經不足以解決終端區空中交通壓力過載的問題. 采取更有效的利用已有的資源、選擇合理的飛機降落次序、提高跑道容量等策略,可以大大緩解終端區和機場擁堵帶來的交通壓力.

本文將針對飛機進場排序問題,并基于已有的算法,提出一些改進和創新,力求得到一個更加高效的問題解決方案.

圖1 終端區結構示意圖

1.2 算法模型

由國際民航組織規定的不同機型之間的最小尾流時間間隔標準(單位: 秒)如表1所示.

表1 尾流間隔標準

模型約束條件:

前者表示每架飛機實際降落時間不得早于預計降落時間; 后者表示相鄰飛機實際降落時間間隔不得小于尾流時間間隔要求. 根據上述約束條件,第i架飛機的實際降落時間應為:

第i架飛機的延誤時長為:

對于單架飛機來說,延誤代價主要是由飛機類型、等待時長和航班優先級這些因素決定. 參考文獻[8,9]并加以改進得代價系數公式:

公式 (3)參數說明: Pi表示飛機 i的優先級,用于調整特定航班降落優先級或應對緊急處理.α,β,γ均為正整數,其中,α 為與機型相關的線性參數,β 為與機型相關的指數底數,γ為時間延誤基數. 代價系數的含義:即飛機在延誤時長di達到γ后,該飛機的延誤代價系數會根據不同機型決定的α、β以及di的大小呈指數增長,若 di=0,則 Ki=0,延誤代價也等于 0.

根據上述條件,每架飛機的延誤代價可如下計算:

為避免出現延誤代價集中在個別飛機上,采用各架飛機延誤代價平方和建立模型:

那么,問題轉化為求得飛機使Dtarget的值最小的飛機隊列. 個體適應度函數:

2 改進的遺傳算法

2.1 改進遺傳算法概述

為加快遺傳算法的收斂速度,文獻[10]中提出了交叉掩碼的概念和使用,以此來保證交叉、變異得到的后代染色體會繼承父代的優質基因,提高個體適應度,從而加快收斂. 然而,交叉掩碼的使用可以保護高適應度染色體,但也會阻礙低適應度染色體的進化,延緩整個種群的進化速度. 尤其是在搜索初期,如果較優質染色體僅占很小的比例,那么搜索周期可能會被大幅延長.

為了既能利用交叉掩碼帶來的優勢,又不阻礙低適應度染色體的進化,可以嘗試針對不同適應度的染色體采用不同的交叉算子和變異算子做區別處理. 對高適應度的染色體,通過使用交叉掩碼提供保護; 對低適應度染色體,采用部分映射雜交算子(Partially mapped crossover,PMX)完成交叉操作. 通過這種雙交叉算子的遺傳算法來提高種群收斂速度,從而更快的得出可行解.

2.2 編碼

為方便后文中將介紹的重排算子的使用,飛機i的編碼采用“飛機型號”+“該飛機在同類型飛機中預計到達跑道先后的序號”,不同類型飛機編碼互不影響. 編碼結果舉例: S1、L1、S2、H1、S3、S4、H2、S5、L2、S6. 該編碼方式可以保證在交叉、變異或重排后,每架飛機編號依然唯一,符合實際意義.

2.3 自適應算法

自適應遺傳算法是針對每個染色體的適應度來計算適合該染色體的Pc和Pm. 對高適應度的染色體降低Pc和Pm,使其得到保護; 反之,對適應度較低的染色體提高Pc和Pm,使其在下一代中被淘汰. 目的是避免發散和陷入局部最小[11]. 自適應遺傳算法的作用與本文的目的一致. 因此,算法將采用以下公式計算Pc和Pm[12]:

式中,f為適應度值,f’取雙親染色體的適應度中的較大值,fmax表示當代種群中的適應度最大值,favg表示當代適應度平均值. 一般Pc1和Pc2分別取0.9和0.6,Pm1和Pm2分別取0.1和0.001.

2.4 雙交叉算子

2.4.1 交叉掩碼

交叉掩碼的計算[10]: 交叉掩碼是根據近兩代的適應度最高的個體的相似基因來確定的. 取近兩代適應度最高個體的染色體進行比較,對應基因座的基因相同,則交叉掩碼對應位置記為1,否則記為0,如此就產生了交叉掩碼,并可以利用它將優質基因傳遞下去.

具體的,在本算法中計算示例如下.

已知i-2、i-1代種群中適應度最高的染色體Ci-2、Ci-1,則第i代交叉掩碼的計算如下:

在染色體使用交叉掩碼進行交叉操作時,交叉掩碼基因為1的基因座直接沿用父代基因,剩余基因按照另一條父代染色體中相應基因的順序進行排序. 在本算法中示例如下:

那么得到的孩子染色體如下(假設兩條染色體適應度均符合用交叉掩碼進行交叉操作):

使用交叉掩碼進行交叉操作的優勢在于父代的優質基因完全得以保留,使高適應度個體平穩進化,避免發散.

2.4.2 部分映射雜交算子[13]

第一步. 在范圍[1,n)(n為飛機數量)隨機產生兩個整數r1、r2,將待交叉染色體均分為3段,并交換中間部分. 例如:r1=2,r2=5.

交叉雙親初始狀態:

交換中間部分得:

第二步. 染色體兩端部分有與中間部分重復的基因用*代替,表示沖突基因. 即:

該算子的優勢是交叉過后,后代的染色體仍具有每個基因不會重復的特點,符合飛機隊列的實際意義.并且,后代將部分保留父代的飛機序列,也達到了進化的目的.

2.4.3 雙交叉算子

如上所述,交叉掩碼具有保護優質染色體的能力,但也有阻礙劣質染色體進化的弊端. 因此,考慮使用雙交叉算子來針對不同適應度染色體進行不同的交叉操作.

當選取的兩條父染色體,一條為優質染色體,另一條為劣質染色體時,優質染色體使用交叉掩碼進行交叉操作; 同時對兩條父染色體進行部分映射雜交操作,產生的兩個后代染色體選取適應度較高者保留.

2.5 變異算子

根據排序的實際意義,要求排序結果中包含所有飛機編碼且每架飛機編碼僅出現一次. 因此,變異算子采用染色體內部變異的方式,以滿足上述要求. 并且考慮到重排算子的存在,則應隨機選擇型號不同(即編號字母不同)的兩個基因進行交換.

變異操作示例如下:

隨機選取產生變異基因為:S1,L1. 則變異操作后結果如下:

2.6 重排算子

重排算子參考了文獻[14]中命題1提出的一條理論: 同類型的飛機,應按其預計到達跑道的時間先后依次著陸. 但該理論沒有考慮航班優先級對降落次序產生的影響,需要在使用時做相應處理. 重排操作是在變異操作之后,其目的是使新生的飛機排序結果的適應度更高.

本文中的重排操作是指將變異操作后得到的飛機序列中的各類型(H,L,S)飛機分別按飛機的預計到達時間分別排序. 具有高優先級的飛機不參與這次排序,防止高優先級飛機被延后.

具體的在本算法中使用重排算子的示例如下:

對C進行重排操作后得:

2.7 改進遺傳算法流程

第一步. 獲取待排序航班信息,為飛機編碼;

第二步. 隨機產生初始種群(染色體數量根據飛機數量決定,可取與飛機數量相等的值);

第三步. 計算個體適應度值,判斷是否符合要求.符合要求,則輸出結果; 否則進入下一步;

第四步. 根據前兩代最優適應度染色體計算交叉掩碼(從第三代開始);

第五步. 采用賭輪盤選擇法從當代種群中選出雙親;

第六步. 采用自適應算法公式(7)計算Pc,根據雙親的適應度選擇對應交叉方式進行交叉操作;

第七步. 采用自適應算法公式(8)計算Pm,進行變異操作;

第八步. 對染色體進行重排操作,產生新個體;

第九步. 新生代是否達到種群數量要求,未達要求返回第五步繼續產生后代; 否則,返回第三步循環尋優.

3 實驗仿真及分析

本實驗采用C++編寫算法仿真程序,對10架次飛機在單跑道降落的情況進行模擬,分別使用先到先服務算法和雙交叉算子遺傳算法對飛機待降隊列進行排序,計算兩種排序結果的總延誤代價及個飛機延誤代價平方和用作排序結果對比; 記錄遺傳算法種群適應度變化情況,檢驗收斂速度是否達到預期目標.

算法參數說明: 已知飛機的預計到達時間、飛機類型; 飛機類型為H、S、L的飛機,α分別取 20、15、10,β=2,γ=600,即飛機在延誤 10 分鐘以上,延誤代價將呈指數增長,且重型飛機延誤代價系數底數是輕型飛機的2倍,中型飛機延誤代價系數底數是輕型飛機的1.5倍; 種群初始數量取20,最大遺傳代數取100,初始兩代交叉掩碼無法計算,均取1; 自適應算法中Pc1、Pc2分別取 0.9和 0.6,Pm1、Pm2分別取 0.1和0.001. 使用以上參數進行仿真,得到的結果如表2、表3所示.

表2 FCFS 排序結果

表3 改進遺傳算法排序結果

各飛機延誤代價平方和變化曲線如圖2所示. 種群在前10代收斂速度很快,在第10-50代進化更加平穩,在第50代左右達到穩定,與文獻[10]中的收斂曲線對比,收斂曲線相似,但平均提前 5 代達到穩定,基本達到算法改進預期目的.

圖2 延誤代價平方和曲線圖

4 結束語

本文針對終端區飛機排序問題,結合文獻[10]提到的交叉掩碼的使用方式,再融入使用雙交叉算子針對不同適應度染色體進行不同交叉操作的思想,提出了一種改進的遺傳算法. 根據實驗數據,證明該算法的收斂速度相比文獻[10]中的算法有進一步的改進,得到的排序結果也達到了降低航班延誤總代價的效果,且延誤代價分配更加均勻.

1Venkatakrishnan CS,Barnett A,Odoni AR. Landings at Logan airport: Describing and increasing airport capacity.Transportation Science,1993,27(3): 211–227. [doi: 10.1287/trsc.27.3.211]

2王莉莉,史忠科,張兆寧. 機場著陸排序的一種滑動窗優化算法. 中國民航學院學報,2004,22(6): 18–21.

3Neuman F,Erzberger H. Analysis of sequencing and scheduling methods for arrival traffic. NASA-TM-102795,1990.

4Erzberger H,Nedell W. Design of automated system for management of arrival traffic. NASA TM 102201,1989.

5Neuman F,Erzberger H. Analysis of delay reducing and fuel saving sequencing and spacing algorithms for arrival traffic.NASA TM 103880,1991.

6Holland JH. Adaptation in Natural and Artificial Systems.Ann ArborMI: The University of Michigan Press,1975.

7常會賢,曲仕茹. 終端區航班排序的遺傳算法. 測控技術,2010,29(7): 91–93,101.

8白重陽,張學軍,管祥民. 基于改進遺傳算法的終端區排序研究. 航空計算技術,2011,41(5): 42–44,48.

9陳亮,鄒赟波,吳值民. 改進遺傳算法在終端區飛機排序中的應用. 軍事交通學院學報,2013,15(1): 29–33.

10張維杰,龍華,胡婷,等. 改進的遺傳算法在延誤飛機進場排序中的應用. 信息技術,2016,(7): 78–83.

11陳長征,王楠. 遺傳算法中交叉和變異概率選擇的自適應方法及作用機理. 控制理論與應用,2002,19(1): 41–43.

12焦瀟冰,費向東,謝澤輝. 基于改進的遺傳算法航班進港排序模型研究. 計算機技術與發展,2014,24(2): 246–249.

13張泳,趙建民,朱信忠,等. 基于 SLP 方法的遺傳算法在多目標布置設計中的應用. 計算機時代,2010,(5): 1–3,7.

14孟祥偉,張平,李春錦. 到場飛機排序及調度問題的Memetic 算法. 西南交通大學學報,2011,46(3): 488–493.

Application of Double Crossover Operator Genetic Algorithm to Aircraft Sequencing in Terminal Area

ZHAO Yan1,YUE Jun2,LIU Dan1

1(Research Institute of Electronic Science and Technology,University of Electronic Science and Technology of China,Chengdu 611731,China)
2(Research Institute of Southwest Electronic Telecommunication Technology,Chengdu 610041,China)

Nowadays,the widespread phenomenon of flight delays does not only increase massive flight costs,but also impacts the experience of passengers. Reasonably adjusting the aircraft queue in terminal areas can raise the utilization ratio of the runway and reduce flight delays. Finally,the cost of delay can be cut down. To resolve the problem of aircraft scheduling in terminal areas,this article puts forward an genetic algorithm including double crossing operator. Different crossover operations are carried out for chromosomes with different fitness so that the quality of chromosomes can be protected and the others continue to evolve. At the same time,reordering operator is introduced to optimize the descendants after mutation to improve convergence rate of genetic algorithm and makes it more suitable for practical use.The experimental results show that the convergence rate of algorithm is improved and the feasible solution can be obtained within acceptable time.

air traffic control; terminal area; aircraft sequencing; genetic algorithm; crossover operator

趙儼,樂俊,劉丹.雙交叉算子遺傳算法在終端區飛機排序中的應用.計算機系統應用,2017,26(12):110–115. http://www.c-sa.org.cn/1003-3254/6070.html

2017-03-06; 修改時間: 2017-03-23; 采用時間: 2017-03-27