趙 儼,樂 俊,劉 丹

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

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

雙交叉算子遺傳算法在終端區(qū)飛機(jī)排序中的應(yīng)用①

趙 儼1,樂 俊2,劉 丹1

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

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

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

空中交通管制; 終端區(qū); 飛機(jī)排序; 遺傳算法; 交叉算子

隨著國際民航運(yùn)輸?shù)母咚侔l(fā)展,我國對(duì)民航運(yùn)輸?shù)男枨笕找嫣岣?飛行器的數(shù)量也隨之增加. 伴隨空中交通流量的快速增長,機(jī)場、空域和航線普遍出現(xiàn)了擁堵現(xiàn)象. 2016年我國民航平均航班正常率為76.76%,較前兩年雖有回升,但與美、日等國比較,仍有較大差距. 終端區(qū)擁堵不僅造成航班延誤,還會(huì)存在安全隱患,引發(fā)安全事故. 通過對(duì)終端區(qū)飛機(jī)隊(duì)列的合理排序,可有效的提高跑道容量,緩和擁堵,進(jìn)而減少飛機(jī)延誤[1].

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

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

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

1 建立算法模型

1.1 終端區(qū)環(huán)境

由于機(jī)場附近的航線非常復(fù)雜,飛機(jī)在此空域活動(dòng)頻繁,因此需要設(shè)立終端管制區(qū)進(jìn)行合理管制. 飛機(jī)的起飛和降落都將在該區(qū)域接受管制員的調(diào)度,安全、有序的完成離場和進(jìn)場. 終端區(qū)結(jié)構(gòu)如圖1所示.

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

本文將針對(duì)飛機(jī)進(jìn)場排序問題,并基于已有的算法,提出一些改進(jìn)和創(chuàng)新,力求得到一個(gè)更加高效的問題解決方案.

圖1 終端區(qū)結(jié)構(gòu)示意圖

1.2 算法模型

由國際民航組織規(guī)定的不同機(jī)型之間的最小尾流時(shí)間間隔標(biāo)準(zhǔn)(單位: 秒)如表1所示.

表1 尾流間隔標(biāo)準(zhǔn)

模型約束條件:

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

第i架飛機(jī)的延誤時(shí)長為:

對(duì)于單架飛機(jī)來說,延誤代價(jià)主要是由飛機(jī)類型、等待時(shí)長和航班優(yōu)先級(jí)這些因素決定. 參考文獻(xiàn)[8,9]并加以改進(jìn)得代價(jià)系數(shù)公式:

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

根據(jù)上述條件,每架飛機(jī)的延誤代價(jià)可如下計(jì)算:

為避免出現(xiàn)延誤代價(jià)集中在個(gè)別飛機(jī)上,采用各架飛機(jī)延誤代價(jià)平方和建立模型:

那么,問題轉(zhuǎn)化為求得飛機(jī)使Dtarget的值最小的飛機(jī)隊(duì)列. 個(gè)體適應(yīng)度函數(shù):

2 改進(jìn)的遺傳算法

2.1 改進(jìn)遺傳算法概述

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

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

2.2 編碼

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

2.3 自適應(yīng)算法

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

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

2.4 雙交叉算子

2.4.1 交叉掩碼

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

具體的,在本算法中計(jì)算示例如下.

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

在染色體使用交叉掩碼進(jìn)行交叉操作時(shí),交叉掩碼基因?yàn)?的基因座直接沿用父代基因,剩余基因按照另一條父代染色體中相應(yīng)基因的順序進(jìn)行排序. 在本算法中示例如下:

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

使用交叉掩碼進(jìn)行交叉操作的優(yōu)勢在于父代的優(yōu)質(zhì)基因完全得以保留,使高適應(yīng)度個(gè)體平穩(wěn)進(jìn)化,避免發(fā)散.

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

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

交叉雙親初始狀態(tài):

交換中間部分得:

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

該算子的優(yōu)勢是交叉過后,后代的染色體仍具有每個(gè)基因不會(huì)重復(fù)的特點(diǎn),符合飛機(jī)隊(duì)列的實(shí)際意義.并且,后代將部分保留父代的飛機(jī)序列,也達(dá)到了進(jìn)化的目的.

2.4.3 雙交叉算子

如上所述,交叉掩碼具有保護(hù)優(yōu)質(zhì)染色體的能力,但也有阻礙劣質(zhì)染色體進(jìn)化的弊端. 因此,考慮使用雙交叉算子來針對(duì)不同適應(yīng)度染色體進(jìn)行不同的交叉操作.

當(dāng)選取的兩條父染色體,一條為優(yōu)質(zhì)染色體,另一條為劣質(zhì)染色體時(shí),優(yōu)質(zhì)染色體使用交叉掩碼進(jìn)行交叉操作; 同時(shí)對(duì)兩條父染色體進(jìn)行部分映射雜交操作,產(chǎn)生的兩個(gè)后代染色體選取適應(yīng)度較高者保留.

2.5 變異算子

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

變異操作示例如下:

隨機(jī)選取產(chǎn)生變異基因?yàn)?S1,L1. 則變異操作后結(jié)果如下:

2.6 重排算子

重排算子參考了文獻(xiàn)[14]中命題1提出的一條理論: 同類型的飛機(jī),應(yīng)按其預(yù)計(jì)到達(dá)跑道的時(shí)間先后依次著陸. 但該理論沒有考慮航班優(yōu)先級(jí)對(duì)降落次序產(chǎn)生的影響,需要在使用時(shí)做相應(yīng)處理. 重排操作是在變異操作之后,其目的是使新生的飛機(jī)排序結(jié)果的適應(yīng)度更高.

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

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

對(duì)C進(jìn)行重排操作后得:

2.7 改進(jìn)遺傳算法流程

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

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

第三步. 計(jì)算個(gè)體適應(yīng)度值,判斷是否符合要求.符合要求,則輸出結(jié)果; 否則進(jìn)入下一步;

第四步. 根據(jù)前兩代最優(yōu)適應(yīng)度染色體計(jì)算交叉掩碼(從第三代開始);

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

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

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

第八步. 對(duì)染色體進(jìn)行重排操作,產(chǎn)生新個(gè)體;

第九步. 新生代是否達(dá)到種群數(shù)量要求,未達(dá)要求返回第五步繼續(xù)產(chǎn)生后代; 否則,返回第三步循環(huán)尋優(yōu).

3 實(shí)驗(yàn)仿真及分析

本實(shí)驗(yàn)采用C++編寫算法仿真程序,對(duì)10架次飛機(jī)在單跑道降落的情況進(jìn)行模擬,分別使用先到先服務(wù)算法和雙交叉算子遺傳算法對(duì)飛機(jī)待降隊(duì)列進(jìn)行排序,計(jì)算兩種排序結(jié)果的總延誤代價(jià)及個(gè)飛機(jī)延誤代價(jià)平方和用作排序結(jié)果對(duì)比; 記錄遺傳算法種群適應(yīng)度變化情況,檢驗(yàn)收斂速度是否達(dá)到預(yù)期目標(biāo).

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

表2 FCFS 排序結(jié)果

表3 改進(jìn)遺傳算法排序結(jié)果

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

圖2 延誤代價(jià)平方和曲線圖

4 結(jié)束語

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

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王莉莉,史忠科,張兆寧. 機(jī)場著陸排序的一種滑動(dòng)窗優(yōu)化算法. 中國民航學(xué)院學(xué)報(bào),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常會(huì)賢,曲仕茹. 終端區(qū)航班排序的遺傳算法. 測控技術(shù),2010,29(7): 91–93,101.

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

9陳亮,鄒赟波,吳值民. 改進(jìn)遺傳算法在終端區(qū)飛機(jī)排序中的應(yīng)用. 軍事交通學(xué)院學(xué)報(bào),2013,15(1): 29–33.

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

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

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

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

14孟祥偉,張平,李春錦. 到場飛機(jī)排序及調(diào)度問題的Memetic 算法. 西南交通大學(xué)學(xué)報(bào),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

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

2017-03-06; 修改時(shí)間: 2017-03-23; 采用時(shí)間: 2017-03-27