免疫教與學(xué)算法在航空器優(yōu)化排序中的應(yīng)用

李 陽，聶黨民，溫祥西

（空軍工程大學(xué)空管領(lǐng)航學(xué)院，西安 710051）

0 引言

航空器進(jìn)場排序與調(diào)配是對將要進(jìn)場的航空器按照一定的規(guī)則和標(biāo)準(zhǔn)，使之形成一個(gè)有著一定先后順序的航空器進(jìn)場隊(duì)列，根據(jù)航空器的排序結(jié)果，為航空器分配合適的進(jìn)場時(shí)機(jī)、著陸時(shí)間等，實(shí)現(xiàn)進(jìn)場航空器的安全有序運(yùn)營。

目前管制指揮員對于進(jìn)場航空器的指揮調(diào)配主要是基于經(jīng)驗(yàn)，采用先到先服務(wù)（FCFS）策略，為進(jìn)場航空器確定著陸順序。該策略易于操作，且具有公平公正的特點(diǎn)。隨著近幾年經(jīng)濟(jì)的快速發(fā)展，空中交通流量持續(xù)增長，傳統(tǒng)調(diào)配手段低效的缺點(diǎn)越來越顯著，航空器延誤、空域擁堵的問題日益突出。進(jìn)場航空器優(yōu)化排序與調(diào)配成為當(dāng)前研究的熱點(diǎn)問題之一［1-2］。

進(jìn)場航空器優(yōu)化排序的要點(diǎn)在于保持航空器之間安全間隔，根據(jù)一定的約束條件，為進(jìn)場航空器進(jìn)行重新排序與調(diào)配，以期達(dá)到提升跑道容量、減少延誤、減輕管制員工作負(fù)荷的目的。智能算法作為一種啟發(fā)式算法，近年來得到迅猛的發(fā)展，被廣泛應(yīng)用于解決航空器優(yōu)化排序與調(diào)配的建模問題。2014 年，杜實(shí)［3］等人針對終端區(qū)航班延誤問題，建立以系統(tǒng)運(yùn)行時(shí)間最短目標(biāo)函數(shù)的元胞傳輸模型，給出合理的航空器進(jìn)場排序；同年，徐兆龍［4］等人采用蟻群算法對所建立多跑道航班協(xié)同調(diào)度多目標(biāo)動(dòng)態(tài)優(yōu)化模型進(jìn)行仿真，降低了航空器進(jìn)場的延誤損失；2016 年，馬衛(wèi)平［5］等人利用蟻群算法的全局搜索能力，結(jié)合CPS 確保調(diào)度的可操作性和公平性，在較短時(shí)間內(nèi)有效減少著陸航班的總延遲時(shí)間；2015 年，陳金良［6］等人運(yùn)用改進(jìn)人工魚群算法，建立了以總飛行成本最小為目標(biāo)函數(shù)的多跑道機(jī)場進(jìn)場航班排序模型，有效地緩解了航班延誤，降低了飛行成本；同年，馬英鈞［7］等人針對傳統(tǒng)粒子群算法缺點(diǎn)，提出改進(jìn)策略，解決了航班降落調(diào)度的問題；2016 年，張維杰［8］等人提出了一種改進(jìn)的遺傳算法，引入交叉掩碼，降低了飛機(jī)隊(duì)列總延誤代價(jià)；2016 年，陳文平［9］等人基于滾動(dòng)時(shí)域的遺傳-免疫算法（RHC-HGIA），解決了滾動(dòng)時(shí)域長度和航班排序優(yōu)化的問題。

這些算法都可以應(yīng)用于解決進(jìn)場航空器優(yōu)化排序問題，取得了較好的結(jié)果，但算法本身擁有一定的局限性，如都需要設(shè)置一定的控制參數(shù)，參數(shù)的選取對于算法的搜索能力會產(chǎn)生較大的影響。教與學(xué)優(yōu)化算法（Teaching-Learning Based Optimization，TLBO）是Rao［10-11］等人于2010 年提出的一種新的種群智能優(yōu)化算法。該算法通過模擬教師的教學(xué)過程和學(xué)員的學(xué)習(xí)過程來實(shí)現(xiàn)，因其簡單、具有更快的收斂速度，收斂能力強(qiáng)，取消了其他智能算法需特定的控制參數(shù)值而受到廣泛關(guān)注。本文通過對該算法進(jìn)行改進(jìn)，增加離散化［12］過程，并結(jié)合免疫算法的“抗體注入”與“免疫修正”，提出免疫教與學(xué)算法（ITLBO），使其可以應(yīng)用于進(jìn)場航空器的離散化排序問題，并進(jìn)行仿真實(shí)驗(yàn)分析，來驗(yàn)證該方案的有效性。

1 問題描述

假設(shè)機(jī)場只有一條跑道，只考慮著陸隊(duì)列，進(jìn)場航空器可以從幾條不同的航路進(jìn)入機(jī)場著陸，所有的航空器都可以按照進(jìn)場時(shí)間排成一個(gè)隊(duì)列，在航空器終止調(diào)配前進(jìn)行重新排序。

假設(shè)該進(jìn)近段待排序航空器有n 架，集合為F={F1，F(xiàn)2，…，F(xiàn)n}。定義航空器i 的預(yù)計(jì)到達(dá)時(shí)間為ETAi，實(shí)際到達(dá)時(shí)間為STAi。

航空器類型可分為3 種，分別為重型（H）、中型（M）、輕型（L），進(jìn)場航空器通常以時(shí)間為基準(zhǔn)，以航空器的尾流間隔作為重要參考因素。定義第i 架航空器類型表示為p（i），當(dāng)i，j 分別為此航路上的前后兩架航空器時(shí)，兩架航空器間的尾流時(shí)間間隔為d［p（i），p（j）］，如表1，選用修正后的基于時(shí)間量綱的ICAO 雷達(dá)尾流間隔標(biāo)準(zhǔn)，其中列表示前機(jī)，行表示后機(jī)。

表1 基于時(shí)間量綱的ICAO 雷達(dá)尾流間隔標(biāo)準(zhǔn)（單位：s）

根據(jù)航空器進(jìn)場序列和雷達(dá)尾流間隔標(biāo)準(zhǔn)，可求得航空器的實(shí)際到達(dá)時(shí)間，滿足

1）目標(biāo)函數(shù)

航空器i 的延誤時(shí)間表示為D（i），滿足

優(yōu)化目標(biāo)為最小化航空器平均延誤：

2）約束條件

①間隔要求

航空器在進(jìn)近著陸階段，需保持最小安全間隔，該間隔的標(biāo)準(zhǔn)主要取決于航空器的著陸次序以及前后機(jī)的尾流標(biāo)準(zhǔn)。滿足

②最大位置約束轉(zhuǎn)換（CPS）

航空器在排序過程中，若重新排成的序列嚴(yán)重偏離FCFS 序列，將增加管制員的管制負(fù)荷，同時(shí)也不利于航空器的安全運(yùn)行。因此，需要設(shè)置航空器的最大位置偏量。設(shè)當(dāng)前共有5 架航空器，最大位置約束為1 時(shí)，航空器位于FCFS 排序的第2 架，則其可能變動(dòng)的位置有1、2、3。考慮管制員工作負(fù)荷及操作限制，一般定義最大位置約束值為1 或2。

2 ITLBO 算法

2.1 基本TLBO 算法

基于教與學(xué)的優(yōu)化算法是模擬以班為單位的學(xué)習(xí)方式，班級中學(xué)員水平的提高需要教師的“教”來引導(dǎo)，同時(shí)，學(xué)員之間需要相互“學(xué)習(xí)”來促進(jìn)知識的吸收。其中，教師和學(xué)員相當(dāng)于進(jìn)化算法中的個(gè)體，而教師是適應(yīng)值最好的個(gè)體之一。每個(gè)學(xué)員所學(xué)的某一科相當(dāng)于一個(gè)決策變量。學(xué)員的成績即函數(shù)適應(yīng)值，教室就是適應(yīng)值最好的個(gè)體。具體定義如下：

1）班級。在TLBO 算法中，將搜索空間中所有點(diǎn)的集合成為班級；

2）學(xué)員。班級中某一個(gè)點(diǎn)Xj=（，，…，）稱之為一個(gè)學(xué)員；

3）教師。班級中學(xué)習(xí)成績最好的學(xué)員Xbest稱之為教師，用Xteacher表示。

TLBO 算法步驟如下：

1）初始化班級

班級中每個(gè)學(xué)員

在搜索空間隨機(jī)生成。

2）“教學(xué)”階段

在TLBO“教學(xué)”階段，班級中每個(gè)學(xué)員Xj（j=1，2，…，NP）根據(jù)Xteacher和學(xué)員平均值Xmean之間的差異性進(jìn)行學(xué)習(xí)。

采取如下公式進(jìn)行教學(xué)工作：

教學(xué)完成后，更新學(xué)員。對每個(gè)學(xué)員求取對應(yīng)的函數(shù)適應(yīng)值，把學(xué)習(xí)后的成績和學(xué)習(xí)之前的成績進(jìn)行比較，表達(dá)式如下：

3）相互學(xué)習(xí)階段

通過學(xué)員之間的相互學(xué)習(xí)提高，來優(yōu)化解集?！皩W(xué)”階段是學(xué)員在小范圍搜索空間內(nèi)互相學(xué)習(xí)，不過會過早向全局最優(yōu)點(diǎn)靠攏，增強(qiáng)了算法的全局搜索能力，有效保持了種群的多樣性。每一個(gè)學(xué)員在班級隨機(jī)選取另一個(gè)不同學(xué)員作為學(xué)習(xí)對象，相互分析比較來進(jìn)行更新，采用公式：

4）如果滿足結(jié)束條件，則輸出結(jié)果，否則返回教學(xué)階段繼續(xù)優(yōu)化。

2.2 算法改進(jìn)

傳統(tǒng)的TLBO 算法不能直接應(yīng)用于航空器優(yōu)化排序問題，需要對算法進(jìn)行如下改進(jìn)：

1）離散化

基本的TLBO 主要是針對解決連續(xù)問題提出的，航空器排序優(yōu)化問題屬于離散復(fù)雜性問題，因此，需要對TLBO 算法進(jìn)行改進(jìn)，以解決此類離散優(yōu)化問題。因此，本文采取的方法是對學(xué)員的離散化，即對Xj進(jìn)行再編譯，從而生成新的學(xué)員，對新學(xué)員進(jìn)行成績評定；

假設(shè)第一位學(xué)員隨機(jī)生成6.96，6.21），將該學(xué)員生成的隨機(jī)數(shù)按照從小到大升序排列，將排列后的下標(biāo)作為新的隨機(jī)數(shù)生成新學(xué)員。如X1生成新學(xué)員。

2）免疫教與學(xué)算法

免疫算法［13］模擬了生物免疫的過程，是一種確定性和隨機(jī)性選擇相結(jié)合并具有“勘探”與“開采”能力的啟發(fā)式隨機(jī)搜索算法。航空器排序過程中，存在最大位置約束轉(zhuǎn)換問題（CPS），需要設(shè)定航空器的最大位置偏移量。本文擬引入免疫算法的抗體注入、免疫修正思想，對“教與學(xué)”算法進(jìn)行改進(jìn)［14-15］，提高其收斂速度及魯棒性。

在初始化班級過程中，隨機(jī)產(chǎn)生的序列存在太多不滿足約束的可能解，從而影響整個(gè)班級的收斂速度，導(dǎo)致算法效率不高。因此，引入免疫算法抗體注入策略，在初始化班級階段，為隨機(jī)生成學(xué)員提前注入抗體，加入最大位置約束轉(zhuǎn)換（CPS），使得隨機(jī)生成序列更接近于最佳序列，從而增強(qiáng)算法的收斂能力。

可隨機(jī)生成n 個(gè)包含于搜索空間的數(shù)。

3 基于ITLBO 算法的航空器優(yōu)化排序

1）初始化學(xué)員

根據(jù)式（9）隨機(jī)生成初始班級學(xué)員Xj，數(shù)量為NP。依據(jù)離散規(guī)則，對初始化的班級學(xué)員進(jìn)行離散化，得到新學(xué)員Yj，即為航空器進(jìn)場排序問題可行解；

2）成績評定

依據(jù)新學(xué)員Yj對應(yīng)的航空器排序序列，參照航空器類型、航空器雷達(dá)間隔標(biāo)準(zhǔn)，根據(jù)式（1）可求得各架航空器對應(yīng)到達(dá)時(shí)間STAi，依據(jù)式（2）可求得各架航空器延誤時(shí)間D（i）。因?yàn)楹娇掌鲀?yōu)化排序模型優(yōu)化目標(biāo)為最小航空器平均延誤，算法尋優(yōu)搜索設(shè)置為空間內(nèi)最小解，因此，可成績評定f（Yj）=；

3）“教”階段。采用式（6）實(shí)現(xiàn)“教”階段，對學(xué)員進(jìn)行離散化，計(jì)算成績并進(jìn)行對比，依據(jù)規(guī)則式（10）對學(xué)員進(jìn)行更新；

4）“學(xué)”階段。采用式（8）實(shí)現(xiàn)班級中學(xué)員間的學(xué)習(xí)，對新舊學(xué)員進(jìn)行離散化，計(jì)算成績并進(jìn)行對比，依據(jù)規(guī)則式（10）對學(xué)員進(jìn)行更新，對新生成學(xué)員進(jìn)行免疫疫苗更新；

5）如果滿足結(jié)束條件，則優(yōu)化結(jié)束，否則轉(zhuǎn)至步驟2）繼續(xù)。

4 案例分析

以某機(jī)場一段時(shí)間內(nèi)的15 架航空器作為樣本進(jìn)行實(shí)驗(yàn)。航空器信息如表2 所示。為了檢驗(yàn)算法對該模型的可行性和有效性，使用先到先服務(wù)排序方法對到場航空器進(jìn)行仿真分析，結(jié)果如下。

圖1 基于ITLBO 算法的航空器排序流程圖

表2 基于FCFS 方法的航空器排序結(jié)果

使用ITLBO 算法，設(shè)置迭代次數(shù)為100 次，學(xué)員數(shù)為20，CPS=1，進(jìn)行仿真分析，算法的收斂特性曲線如圖2，所得排序結(jié)果如表3。

圖2 算法收斂特性曲線圖

表3 基于ITLBO 算法的航空器排序結(jié)果

由表2 與表3 可知，F(xiàn)CFS 方法的航空器優(yōu)化排序最終延誤時(shí)間為4 629 s，ITLBO 算法對于進(jìn)場航空器排序產(chǎn)生的延誤時(shí)間為3 797 s，ITLBO 算法可以實(shí)現(xiàn)對進(jìn)場航空器的有效排序，并將總延誤時(shí)間降低了650 s。由圖2 可知，ITLBO 算法離散化TLBO算法收斂速度更快，優(yōu)化效果更好。

仿真表明，經(jīng)過ITLBO 算法可以應(yīng)用于進(jìn)場航空器的優(yōu)化排序模型中，且求解速度較快，與傳統(tǒng)先到先服務(wù)調(diào)配方法相比延誤更小，可以加快航空器的降落時(shí)間，降低飛行成本。

5 結(jié)論

本文通過對基本TLBO 算法進(jìn)行離散化處理，結(jié)合免疫算法相關(guān)思想進(jìn)行算法改進(jìn)，并將其應(yīng)用于解決進(jìn)場航空器的優(yōu)化排序模型的離散問題，得出了經(jīng)過優(yōu)化后的航空器序列。與傳統(tǒng)調(diào)配方法相比，使用改進(jìn)算法進(jìn)行調(diào)配可以更好地解決航空器延誤問題，降低飛行成本，提高機(jī)場利用率，為航空管制自動(dòng)化提供一定的技術(shù)支持。未來的研究主要以提高算法在各個(gè)場景的實(shí)用性為主，并基于優(yōu)化后的調(diào)度策略提出相應(yīng)的調(diào)配策略以及輔助工具。