基于合作協(xié)同進(jìn)化算法的航跡沖突解脫研究

徐 滿,胡明華,周 逸,張 穎

(南京航空航天大學(xué) 民航學(xué)院,南京211106)

隨著經(jīng)濟(jì)的不斷發(fā)展,亞太地區(qū)將成為航空客運(yùn)量增長(zhǎng)的主要?jiǎng)恿?中國(guó)將在2022年成為全球第一大航空運(yùn)輸市場(chǎng)[1].根據(jù)國(guó)際航空運(yùn)輸協(xié)會(huì)的報(bào)告,到2034年,往返亞太地區(qū)和在亞太地區(qū)內(nèi)部的航線每年將增加18億人次,總體市場(chǎng)規(guī)模將達(dá)到29億.與其他地區(qū)相比,規(guī)模將增加到全球客運(yùn)量的42%,年平均增長(zhǎng)率為4.9%,與中東并列最高[2].隨著空中交通需求的不斷增長(zhǎng),空中交通的擁堵情況越來(lái)越嚴(yán)重,航空器之間的潛在沖突大大增加,導(dǎo)致空中交通管制員工作負(fù)荷的增加,危及空中交通安全[3].沖突解脫旨在根據(jù)航空器的飛行計(jì)劃解決航空器在運(yùn)行過(guò)程中的潛在沖突,是確保航空器安全運(yùn)行的一項(xiàng)關(guān)鍵技術(shù).

航空器的沖突解脫問(wèn)題是一個(gè)大規(guī)模組合優(yōu)化問(wèn)題,共同使用空域資源使得航空器之間相互耦合[4].已有大量文獻(xiàn)的研究航空器的沖突解脫方式,包括調(diào)整航空器起飛時(shí)刻[5]、調(diào)整航空器的飛行速度[6]、修改航空器的水平航跡[7]以及高度層分配[8]等方式及其組合[9].但是,目前傳統(tǒng)的基于扇區(qū)的空中交通系統(tǒng)已經(jīng)不能完全滿足交通量未來(lái)的增長(zhǎng)需求[10].大量的研究集中在戰(zhàn)術(shù)階段的沖突解脫問(wèn)題,戰(zhàn)術(shù)沖突解脫能在有限的范圍內(nèi)解決局部沖突,但是由于航空器之間的耦合關(guān)系,短期內(nèi)的沖突解脫可能會(huì)產(chǎn)生“多米諾骨牌”效應(yīng),使得沖突解脫一直處于被動(dòng)狀態(tài),危及空域安全.例如,采用地面等待策略時(shí),已經(jīng)延誤了的航空器仍然有可能繼續(xù)等待其他航空器以滿足空域的容量要求[5].而戰(zhàn)略階段的沖突解脫可以從全局角度解決航空器之間的潛在沖突,降低航空管制員的工作量,從而提高空域容量,緩解交通壓力.

4D航跡的運(yùn)用以及TBO的提出被認(rèn)為是未來(lái)空中交通管理的運(yùn)行基礎(chǔ).4D航跡將航空器航跡定義為三維空間加上時(shí)間,隨著運(yùn)行技術(shù)的不斷發(fā)展,4D航跡可以有效降低航空器運(yùn)行過(guò)程中的不確定性.這就為在一個(gè)較長(zhǎng)時(shí)間范圍內(nèi)解決航空器之間潛在沖突提供了技術(shù)支持,使得在戰(zhàn)略階段解決沖突成為可能.因此,基于4D航跡,綜合優(yōu)化給定空域范圍內(nèi)所有航空器的飛行計(jì)劃被認(rèn)為是未來(lái)應(yīng)對(duì)空中交通需求挑戰(zhàn)的關(guān)鍵技術(shù)[11].

在對(duì)航空器進(jìn)行沖突解脫時(shí),可以分為經(jīng)典沖突解脫方法和機(jī)器學(xué)習(xí)沖突解脫方法.經(jīng)典沖突解脫方法由于問(wèn)題模型的復(fù)雜程度,常采用啟發(fā)式算法求解.模擬退火算法及其改進(jìn)[9,12-14]獲得了廣泛的應(yīng)用.Dai[9]等人結(jié)合模擬退火算法,設(shè)計(jì)了一個(gè)均勻高度層策略,將航空器均勻分布至各個(gè)可用的高度層.但是該方法復(fù)雜度較高且需要較大的計(jì)算量.為了降低問(wèn)題的復(fù)雜度,引入滑動(dòng)時(shí)間窗來(lái)降低問(wèn)題的維數(shù),從而獲得可行解[5].降低問(wèn)題的維數(shù)可以降低問(wèn)題的復(fù)雜度,提高算法的效率.Guan[4]等人首次將合作協(xié)同進(jìn)化算法(Cooperative Coevolution Evolutionary Algorithm,CCEA)應(yīng)用到航班沖突解脫問(wèn)題中.CCEA采用分而治之的思想,將一個(gè)大規(guī)模組合優(yōu)化問(wèn)題分解成若干個(gè)子問(wèn)題,從而降低問(wèn)題的維數(shù),各個(gè)子問(wèn)題采用特定的進(jìn)化算法優(yōu)化得到部分可行解,通過(guò)各個(gè)小組之間的合作進(jìn)化獲取全局可行解.在CCEA的框架下,分組策略對(duì)算法效率具有重大影響.常見(jiàn)的分組策略有固定分組、均勻分組、隨機(jī)分組[15]、基于先驗(yàn)知識(shí)分組[4]等,各種分組策略有各自的適應(yīng)場(chǎng)景[16].其中,基于先驗(yàn)知識(shí)的分組策略,充分考慮航空器之間的沖突關(guān)系,將相互影響的航班分入同一小組內(nèi)進(jìn)化,充分發(fā)揮了先驗(yàn)知識(shí)的優(yōu)勢(shì),算法具備良好的效果.采用機(jī)器學(xué)習(xí)[17]進(jìn)行沖突解脫近幾年得到了迅速地發(fā)展,但是其多適應(yīng)于戰(zhàn)術(shù)階段的沖突解脫,在戰(zhàn)略階段的大規(guī)模場(chǎng)景下的應(yīng)用需要進(jìn)一步的研究.

在實(shí)際運(yùn)行過(guò)程中,空中交通管制員往往會(huì)在沖突數(shù)量和航空器航跡調(diào)整量之間尋求一個(gè)很好的平衡.針對(duì)這一目的,Yan Su等人[18]以最小化沖突數(shù)量和最小化航跡調(diào)整量為目標(biāo),在TBO概念下采用多目標(biāo)文化基因算法求解多目標(biāo)模型.在求解全國(guó)范圍內(nèi)的無(wú)沖突航跡時(shí),問(wèn)題的復(fù)雜度較高,算法求解效率下降明顯.沖突解脫模型中目標(biāo)具有多樣性,Mateos等人分析了六種不同的目標(biāo)函數(shù),包括最小化航空器機(jī)動(dòng)次數(shù)和幅度、最小化沖突風(fēng)險(xiǎn)、最小化航班延誤、最小化分離點(diǎn)偏差和最小化航空器機(jī)動(dòng)頻率[8].CCMOEA[10]同樣被應(yīng)用于沖突解脫問(wèn)題,在協(xié)同進(jìn)化算法的框架下,采用MOEA/D[19]進(jìn)行各個(gè)小組的內(nèi)部?jī)?yōu)化.但正如作者在文中指出一樣,算法的求解效率可以進(jìn)一步提高.

本文從空中交通管理的角度出發(fā),綜合考慮最小化沖突以及解沖突所導(dǎo)致的航跡調(diào)整量,建立起飛前戰(zhàn)略航跡沖突解脫多目標(biāo)優(yōu)化模型.為快速求解模型,設(shè)計(jì)IBCCMOEA進(jìn)行模型求解,在協(xié)同進(jìn)化算法的框架下采用動(dòng)態(tài)分組的方法降低問(wèn)題維度,利用NSGA-II[20]進(jìn)行組內(nèi)優(yōu)化.在組內(nèi)優(yōu)化時(shí)根據(jù)超體積(Hyper Volume,HV)指標(biāo)選擇協(xié)同解,從而進(jìn)一步提高算法的收斂速度.采用中國(guó)航路網(wǎng)繁忙時(shí)段真實(shí)數(shù)據(jù)進(jìn)行仿真驗(yàn)證,將所提算法與使用較多的多目標(biāo)優(yōu)化算法進(jìn)行對(duì)比,包括NSGA-II,MOEA/D以及CCMOEA,實(shí)驗(yàn)結(jié)果表明,所設(shè)計(jì)的算法在收斂速度以及求解結(jié)果上均具有良好的性能.

1 問(wèn)題模型

本文研究巡航狀態(tài)下的沖突解脫問(wèn)題,因此航跡起終點(diǎn)為爬升和下降頂點(diǎn).假設(shè)空域中有n架航空器,F=(f1,f2,f3,…,fn),按照航班計(jì)劃沿著特定的航路飛行,航空器處于巡航狀態(tài),以恒定的巡航速度飛行.

基于四維航跡的沖突解脫可以被定義為:給定航班飛行計(jì)劃及航路網(wǎng)絡(luò),盡可能減少航空器之間的飛行沖突并產(chǎn)生較少的調(diào)整量.在進(jìn)行航空器的沖突解脫的過(guò)程中,應(yīng)滿足空域容量及航空器性能等因素的限制.在4D航跡條件下,航空器f的航跡由一組4D航跡采樣點(diǎn)組成:

1.1 多目標(biāo)航跡規(guī)劃決策變量及約束條件

本文采用調(diào)整航空器起飛時(shí)刻以及高度層兩種方式解決航空器之間的潛在沖突.在時(shí)間維度,沖突解脫表現(xiàn)為與航班fi相對(duì)應(yīng)的起飛時(shí)刻δi的調(diào)整;而在空間維度,表現(xiàn)為與航班fi相對(duì)應(yīng)的飛行高度層li的調(diào)整.決策變量表示為u:=(δ,l),其中δ為n個(gè)航班的起飛時(shí)間調(diào)整矢量,l為n個(gè)航班的高度層調(diào)整矢量,分別表示如下:

δ:=(δ1,δ2,δ3,…,δn)

l:=(l1,l2,l3,…,ln)

決策變量必須滿足以下約束:

1)地面延誤約束:由于不能將航空器的起飛時(shí)間推遲的太久,?fi∈F,i=1,2,…,n,其對(duì)應(yīng)的地面延誤ΔGHi必須保持在離散化的區(qū)間[0,ΔTGH]中,所有可能的延誤集合ΔGHi定義如下:

(1)

2)高度層分配約束:巡航狀態(tài)下的高度層分配受到航空器性能的限制,也應(yīng)受到約束.?fi∈F,i=1,2,…,n,所有可能的高度層偏移量集合ΔFLi定義如下:

(2)

1.2 目標(biāo)函數(shù)

沖突解脫的首要目標(biāo)是解決航空器之間的潛在沖突,實(shí)現(xiàn)沖突最小化.目標(biāo)一為最小化航班之間的沖突數(shù)量,表示如下:

(3)

其中:C(w(δi),w(δj),li,lj)為布爾變量,表示航跡采樣點(diǎn)之間的沖突關(guān)系.

在沖突解脫的過(guò)程中,航空器需要做出相應(yīng)的機(jī)動(dòng)來(lái)規(guī)避沖突.為了盡可能減少與其他航空器之間的沖突,可以對(duì)航空器的初始航跡做出大幅度調(diào)整,但是會(huì)產(chǎn)生額外的飛行成本.因此,目標(biāo)二為最小化航跡調(diào)整成本(Total Trajectory Amendment Cost,TTAC),TTAC由地面延誤成本(CostGH)、高度層分配成本(CostFL)構(gòu)成,表示如下:

minObj2=TTAC=λGH×CostGH+λFL×CostFL

(4)

其中:λGH與λFL分別表示地面延誤與高度層分配成本系數(shù).由于地面延誤成本與高度層分配成本量綱不同,因此先進(jìn)行歸一化再相加.地面延誤成本與高度層分配成本定義如下:

(5)

(6)

其中:F為航班集合,l為可用飛行高度層集合,δ為起飛時(shí)刻集合.

2 基于超體積的多目標(biāo)合作協(xié)同進(jìn)化算法

CCEA最初由Potter[22]提出,其主要思想是采用特定的分組策略將一個(gè)大規(guī)模優(yōu)化問(wèn)題分解成多個(gè)小規(guī)模優(yōu)化問(wèn)題,從而降低問(wèn)題的復(fù)雜度.在協(xié)同進(jìn)化算法中,各個(gè)子問(wèn)題采用相應(yīng)的進(jìn)化算法分別進(jìn)行組內(nèi)優(yōu)化,通過(guò)個(gè)體與其他子種群代表個(gè)體的協(xié)同評(píng)價(jià)獲得子種群的適應(yīng)度值,最優(yōu)解通過(guò)子種群之間的協(xié)同進(jìn)化得到.CCEA及其改進(jìn)在航空規(guī)劃領(lǐng)域已有過(guò)大量成功的應(yīng)用[4,10,23].

當(dāng)將該框架應(yīng)用于多目標(biāo)優(yōu)化時(shí),影響算法效率的一個(gè)關(guān)鍵因素為選擇子種群代表性個(gè)體的方法.常用的一種選擇方式為從各個(gè)子種群的Pareto解集中隨機(jī)選擇一個(gè)非支配解,但是與其他子種群代表個(gè)體相結(jié)合形成完備解時(shí)卻有可能產(chǎn)生較差的解[24].本文采用一種基于超體積指標(biāo)的選擇策略,根據(jù)個(gè)體貢獻(xiàn)度選擇代表性個(gè)體.

在分組時(shí),采用動(dòng)態(tài)分組策略將相互關(guān)聯(lián)的航空器放入同一小組;組內(nèi)優(yōu)化時(shí),采用NSGA-II結(jié)合自適應(yīng)遺傳算子進(jìn)行優(yōu)化,選擇子種群代表性個(gè)體時(shí)采用基于超體積指標(biāo)的選擇方法,算法框架如下:

Algorithm1:IBCCMOEA

-------------------------------------------

Input:Initial solution,MAXgenerations,maxgenerations

Output: IBCCMOEA solution

// Main procedure

1:Initialize the initial solution to generate the initial population;

2:fori=1:MAX generationsdo

3:Evaluate all the individuals in the population and compute the non-dominated solution;

4:Select an objective vector based on the HV indicator;

// Cooperative co-evolution

5:Decompose the objective vector intomilow subcomponents based on the dynamic grouping

6: strategy;

7:Set;j=1;

8:whilej≤mido

9:forK=1:maxgenerationsdo

10: Initialize thejthsubcomponent;

11: Select theoffspringkbased on the HV indicator;

12: Use the adaptive crossover and mutation strategy to obtain theoffspringk+1;

13:endfor

14:j=j+1;

15:endwhile

16:endfor

2.1 動(dòng)態(tài)分組策略

分組策略是影響IBCCMOEA效率的關(guān)鍵因素之一,本文采用動(dòng)態(tài)分組策略,根據(jù)航空器之間的沖突關(guān)系進(jìn)行分組.為了表示航空器之間的沖突關(guān)系,定義一個(gè)矩陣C來(lái)表示航空器之間是否存在沖突:

(7)

矩陣C是一個(gè)n×n矩陣,第i行,第j列表示航空器fi,fj之間的沖突關(guān)系,即:

(8)

當(dāng)任意兩架航空器之間沒(méi)有沖突時(shí),采用均勻分組策略將航空器分成數(shù)量相等的m組.

當(dāng)存在相互沖突的兩架航空器時(shí),即:?i≠j,Cij=1,此時(shí)根據(jù)航空器之間的沖突關(guān)系將相互影響的航班放入同一小組之內(nèi):

(9)

其中:nk表示第k組的航班數(shù)量.在此種分組策略下,同一小組內(nèi)的航班之間一定是相互影響的,不同小組之間的航班不存在相互影響,即:

?fi,fj∈groupk,Cij=1.
?fi∈groupk,fj∈groupl,Cij=0.

(10)

2.2 子種群優(yōu)化

2.2.1 染色體結(jié)構(gòu)

在用IBCCMOEA求解模型時(shí),采用整數(shù)編碼的方式,將航班起飛時(shí)刻及高度層按照航班序號(hào)進(jìn)行排序并編碼.染色體結(jié)構(gòu)如圖1所示.

圖1 染色體結(jié)構(gòu)Figure 1 Chromosome structure

2.2.2 子種群初始化

在初始化種群時(shí),根據(jù)航空器當(dāng)前的沖突數(shù)量,采用輪盤賭選擇,優(yōu)先選擇沖突數(shù)量較多的航空器,調(diào)整起飛時(shí)刻的概率為PGH,調(diào)整高度層的概率為PFL,PGH+PFL=1.

生成隨機(jī)數(shù)r,當(dāng)時(shí)0

圖2 子種群初始化Figure 2 Sub-population initializing

2.2.3 基于超體積的選擇機(jī)制

HV[25]是一個(gè)由維數(shù)為n的點(diǎn)集合所包含的n維空間,應(yīng)用于多目標(biāo)優(yōu)化時(shí),將解的n維目標(biāo)值作為該空間的點(diǎn)來(lái)計(jì)算,即通過(guò)非支配解P在目標(biāo)函數(shù)空間中的體積求得超體積.?pi∈P,根據(jù)參照點(diǎn)R生成一個(gè)超立方體vi,pi為超立方體vi的另一個(gè)對(duì)角,計(jì)算方式如下:

(11)

在MOEAs中,使用HV作為選擇策略是根據(jù)個(gè)體對(duì)總體的HV貢獻(xiàn)度,優(yōu)先選擇對(duì)前沿解的HV貢獻(xiàn)度較大的個(gè)體,屬于總體P的個(gè)體pi的HV貢獻(xiàn)值計(jì)算方式如下:

Δspi=S(P,R)-S(P{pi},R)

(12)

在雙目標(biāo)優(yōu)化時(shí),該計(jì)算過(guò)程如圖3所示.本文在選擇各個(gè)子種群代表性個(gè)體時(shí),首先計(jì)算種群中個(gè)體的適應(yīng)度,對(duì)其進(jìn)行非支配排序,其次計(jì)算個(gè)體對(duì)前沿解的HV貢獻(xiàn)度,選擇對(duì)前沿解的HV貢獻(xiàn)度較大的個(gè)體.

圖3 超體積貢獻(xiàn)值Figure 3 Hyper volume contribution

2.2.4 自適應(yīng)交叉算子

自適應(yīng)交叉算子根據(jù)航班的局部適應(yīng)度確定,本文采用的局部適應(yīng)度算子綜合考慮了目標(biāo)一與目標(biāo)二,局部適應(yīng)度計(jì)算方式如下:

(13)

caj=floor(εaj+(1-ε)bj)
cbj=floor(εbj+(1-ε)aj)

(14)

其中:floor為向下取整,ε為線性重組系數(shù).自適應(yīng)交叉算子原理圖如圖4所示,交叉概率為Pc.

圖4 自適應(yīng)交叉算子Figure 4 Adaptive crossover operator

2.2.5 自適應(yīng)變異算子

當(dāng)航空器的局部適應(yīng)度值越高時(shí),表明該航空器按當(dāng)前飛行計(jì)劃會(huì)產(chǎn)生更少的沖突數(shù)量和航跡調(diào)整量.在本文采用的自適應(yīng)變異算子中,當(dāng)子種群k中的第j架航空器的局部適應(yīng)度值小于σ時(shí),發(fā)生變異的概率為Pm,自適應(yīng)變異算子如圖5所示.

圖5 自適應(yīng)變異算子Figure 5 Adaptive mutation operator

3 仿真驗(yàn)證

3.1 小規(guī)模算例

首先采用中國(guó)航路網(wǎng)絡(luò)2019年6月8日9點(diǎn)至11點(diǎn)442架航班的小規(guī)模算例對(duì)模型參數(shù)進(jìn)行分析,在Matlab R2019a平臺(tái)上運(yùn)行.所用數(shù)據(jù)包含7 684個(gè)航路點(diǎn),93個(gè)起降機(jī)場(chǎng).航空器的初始飛行計(jì)劃有237個(gè)潛在飛行沖突.巡航階段航空器的飛行速度v設(shè)置為980 km/h,允許的最大延誤ΔTGH為30 min,調(diào)整航空器起飛時(shí)刻的時(shí)隙設(shè)置為2 min;遵循“東單西雙”的原則,垂直方向上每300 m劃分為一個(gè)高度層,高度范圍為8 900～11 600 m,允許的最大高度調(diào)整量ΔLFL為1 200 m;采用等時(shí)間間隔對(duì)航跡點(diǎn)進(jìn)行采樣,航跡采樣點(diǎn)時(shí)間間隔τ為20 s.

為了驗(yàn)證IBCCMOEA算法在沖突解脫中的高效性,對(duì)于模型中的各項(xiàng)參數(shù)進(jìn)行靈敏度分析,選定最優(yōu)參數(shù)組合;分別采用NSGA-II,MOEA/D,CCMOEA三種算法進(jìn)行求解及比較.

3.1.1 參數(shù)靈敏度分析

本文采用地面延誤及高度層分配兩種方式進(jìn)行沖突解脫,在1.2節(jié)中兩種沖突解脫方式所產(chǎn)生的成本通過(guò)式(4)進(jìn)行加權(quán)作為本文的目標(biāo)函數(shù)之一,同時(shí)依概率選擇沖突解脫方式.令λGH+λFL=1,PGH+PFL=1.在對(duì)λGH和λFL進(jìn)行靈敏度分析時(shí),PGH與PFL采用默認(rèn)值0.5;在確定了最優(yōu)的λGH和λFL后,將其應(yīng)用到PGH與PFL的分析中.獨(dú)立重復(fù)試驗(yàn)10次,給出在不同系數(shù)下Pareto前沿的HV作為依據(jù),如圖6所示.

圖6 λGH,λFL,PGH,PFL靈敏度分析Figure 6 λGH,λFL,PGH,PFL sensitivity analysis

表1 模型參數(shù)設(shè)置Table 1 Parameter settings of model

除了對(duì)模型中的參數(shù)進(jìn)行靈敏度分析,算法中的四個(gè)參數(shù):交叉概率(Crossover rate,Pc),變異概率(Mutation rate,Pm),最大進(jìn)化代數(shù)(Generations)和種群規(guī)模(Population size)同樣需進(jìn)行靈敏度分析.在分析當(dāng)前參數(shù)時(shí),其他參數(shù)設(shè)置為默認(rèn)值0.9,0.05,80,150,獲取的最佳參數(shù)用于后續(xù)算法比較[26].

在靈敏度分析過(guò)程中,HV,反轉(zhuǎn)世代距離(Inverted Generational Distance,IGD)和散度(Spread,SP)[27]用于衡量該參數(shù)條件下算法性能.圖7為IBCCMOEA基于10次重復(fù)獨(dú)立運(yùn)行所得到的結(jié)果.HV,SP值越大且IGD值越小,說(shuō)明在該參數(shù)條件下算法性能越優(yōu)異.其余三種算法靈敏度分析方法相同,最優(yōu)參數(shù)組合如表2所示.

表2 算法參數(shù)設(shè)置Table 2 Parameter settings of algorithms

圖7 參數(shù)靈敏度分析(顯著性水平5%)Figure 7 Parameters sensitivity analysis(significant level at 5%)

3.1.2 算法高效性與收斂性

圖8給出了四種算法對(duì)應(yīng)的Pareto前沿,可以看出,IBCCMOEA優(yōu)化后得到的Pareto前沿優(yōu)于其他三種算法,在沖突解脫以及航跡調(diào)整成本方面表現(xiàn)出優(yōu)越的性能.

圖8 小規(guī)模算例Pareto前沿Figure 8 Small-scale case pareto front

為了證明算法沖突解脫的高效性,給出NSGA-II,MOEA/D,CCMOEA,IBCCMOEA在442架航班沖突解脫過(guò)程中每一代的Pareto前沿平均沖突數(shù)量變化趨勢(shì)圖,如圖9所示.表3為四種算法的運(yùn)行時(shí)間、沖突數(shù)量及對(duì)應(yīng)的航跡調(diào)整成本.

表3 運(yùn)行時(shí)間、CS及TTAC對(duì)比Table 3 Running time, CS and TTAC

圖9 平均最小沖突數(shù)量Figure 9 Average minimun total conflict

由圖9可知,IBCCMOEA對(duì)于無(wú)沖突解的搜索效率最高,在進(jìn)化過(guò)程中其沖突解脫的速度最快.對(duì)比NSGA-II與CCMOEA,采用了合作協(xié)同進(jìn)化算法框架的CCMOEA具有更高的效率,同時(shí)還可以得到無(wú)沖突的可行解,這是因?yàn)樵谝肓撕献鲄f(xié)同進(jìn)化的框架之后,將相互影響的航空器放入同一小組進(jìn)行分別優(yōu)化,避免在沖突解脫時(shí)對(duì)兩個(gè)相互沒(méi)有影響的航空器進(jìn)行調(diào)整,浪費(fèi)計(jì)算資源.通過(guò)表3中的對(duì)比可知,在收斂速度上,IBCCMOEA比CCMOEA快了約7.54%,同時(shí)IBCCMOEA產(chǎn)生的航跡調(diào)整成本減少了約9.62%.

因此,在引入了HV進(jìn)行選擇時(shí),算法的性能可以進(jìn)一步提高.這是因?yàn)镃CMOEA在選擇代表子種群時(shí),從子種群中的Pareto集合中隨機(jī)選擇一個(gè)解作為代表,與其他代表形成完備解時(shí)會(huì)產(chǎn)生較差的解;而在引入了超體積指標(biāo)作為選擇依據(jù)時(shí),在子種群的Pareto解集中,根據(jù)各個(gè)非支配解的HV貢獻(xiàn)度選擇代表,更好的考慮了綜合性,因此提高了沖突解脫的效率.

分別計(jì)算Pareto前沿的SP,HV和IGD,如表4所示,為各個(gè)算法10次獨(dú)立重復(fù)試驗(yàn)中各項(xiàng)指標(biāo)的平均值及標(biāo)準(zhǔn)差.

表 4 小規(guī)模算例算法性能對(duì)比Table 4 Performance comparision between algorithms in small-scale case

由表4可知,IBCCMOEA在各項(xiàng)指標(biāo)上均優(yōu)于其他各種算法.其中,SP的值最大,表明算法的分布更均勻;HV值最大,表明算法的綜合性較好;IGD值最小,表明距離參考集越近,因此算法的收斂性要優(yōu)于其他三種算法.其IGD隨進(jìn)化代數(shù)的變化趨勢(shì)如圖10所示.由圖可知,算法最終收斂.

圖10 IGD趨勢(shì)圖Figure 10 IGD trend

3.2 大規(guī)模算例

為了驗(yàn)證所提算法在大規(guī)模場(chǎng)景下的適應(yīng)性,對(duì)于1 014架航班真實(shí)飛行數(shù)據(jù)進(jìn)行仿真驗(yàn)證.所用數(shù)據(jù)航空器經(jīng)過(guò)的航路及沖突位置如圖11所示,其中包含150個(gè)起降機(jī)場(chǎng),19 624個(gè)航路點(diǎn).航空器初始航跡中的沖突數(shù)量為747個(gè).在大規(guī)模算例中采用允許的航班最大延誤ΔTGH為60 min,允許的最大高度調(diào)整量ΔLFL為1 200 m.

圖11 大規(guī)模算例Pareto前沿Figure 11 Large-scale case pareto front

在大規(guī)模沖突解脫場(chǎng)景下得到的Pareto前沿的SP,HV及IGD平均值及其標(biāo)準(zhǔn)差,如表5所示.

表5 大規(guī)模算例算法性能對(duì)比Table 5 Performance comparision between algorithmsin large-scale case

由表5可知,在大規(guī)模場(chǎng)景下,IBCCMOEA的優(yōu)化結(jié)果仍然具有優(yōu)勢(shì),在大規(guī)模場(chǎng)景下具有實(shí)用價(jià)值.

圖11為所采用的四種算法分別優(yōu)化得到的Pareto前沿,均基于10次獨(dú)立重復(fù)實(shí)驗(yàn).由圖11可知,IBCCMOEA的優(yōu)化效果更好,其優(yōu)化得到的Pareto前沿完全支配其他三種算法.兩種經(jīng)典的多目標(biāo)優(yōu)化算法NSGA-II與MOEA/D,優(yōu)化速度較慢且優(yōu)化出的結(jié)果不理想.在引入了合作協(xié)同進(jìn)化框架后,CCMOEA在降低沖突數(shù)量上更高效,但提高了算法的復(fù)雜度.在此基礎(chǔ)上,為了克服CCMOEA隨機(jī)選擇代表個(gè)體可能產(chǎn)生較低質(zhì)量的解的缺點(diǎn),引入了超體積指標(biāo)作為選擇機(jī)制,優(yōu)化結(jié)果表明能有效提高算法效率.因此,所采用的算法優(yōu)點(diǎn)為:采用了協(xié)同進(jìn)化策略提高了算法的搜索能力;采用了基于超體積指標(biāo)的選擇策略及自適應(yīng)遺傳算子,提高了算法的搜索效率.

表6為四種優(yōu)化算法的Pareto前沿中最小沖突數(shù)量及最小航跡調(diào)整量對(duì)應(yīng)的解,同時(shí)給出了對(duì)應(yīng)的求解時(shí)間.IBCCMOEA的沖突解脫效果優(yōu)于其他算法,可以得到無(wú)沖突的解,航跡調(diào)整成本也低于其他算法,求解速度也在可以接受的時(shí)間范圍之內(nèi).

表6 1 014架航班Pareto前沿最小沖突和最小航跡調(diào)整成本對(duì)應(yīng)解Table 6 Non-dominated solutions with the least CS and the least TTAC for 1014 flights

圖12為四種算法優(yōu)化結(jié)果沖突數(shù)量最小的解,其對(duì)應(yīng)的航空器地面延誤及高度層分配的分布圖.其中,IBCCMOEA算法對(duì)應(yīng)的解,62%的航空器沒(méi)有產(chǎn)生延誤,68%的航空器遵循著初始飛行高度層;航空器的延誤主要分布在10 min之內(nèi),超過(guò)30 min的延誤只有0.4%的航班;航空器飛行高度的調(diào)整也主要分布在600 m之內(nèi).隨著調(diào)整量的增大,航空器所占比例逐漸減小,證明本文采用的算法不僅沖突解脫效率高,而且產(chǎn)生的航跡調(diào)整成本也較低.

圖12 地面延誤及飛行高度調(diào)整量分布圖Figure 12 Distribution of ground delay and flight level adjustment

4 結(jié) 語(yǔ)

本文研究了航空器運(yùn)行中的沖突解脫問(wèn)題.首先根據(jù)問(wèn)題特點(diǎn),建立了基于沖突數(shù)量和航空器航跡偏移成本的雙目標(biāo)優(yōu)化模型;其次采用一種基于指標(biāo)的多目標(biāo)合作協(xié)同進(jìn)化算法求解該問(wèn)題.沖突解脫問(wèn)題是一個(gè)大規(guī)模組合優(yōu)化問(wèn)題,為了提高求解效率,采用動(dòng)態(tài)分組方法將航空器按照沖突關(guān)系分組,將該大規(guī)模問(wèn)題分解為若干了子問(wèn)題,該協(xié)同策略提高了算法的搜索能力,針對(duì)協(xié)同進(jìn)化過(guò)程中,子種群代表性個(gè)體的選擇問(wèn)題,采用了基于超體積指標(biāo)的選擇策略,優(yōu)先選擇超體積更大的個(gè)體,該策略對(duì)提高算法搜索效率有效.為了驗(yàn)證算法的優(yōu)勢(shì),分別采用小規(guī)模和大規(guī)模算例,將IBCCMOEA算法與NSGA-II,MOEA/D,CCMOEA進(jìn)行對(duì)比,結(jié)果驗(yàn)證了本文算法的性能優(yōu)勢(shì).

下一步的工作主要集中在對(duì)更多樣化的沖突解脫方式以及如何進(jìn)一步結(jié)合解沖突方式的特點(diǎn)進(jìn)行算法設(shè)計(jì)從而提高算法求解效率上:沖突解脫方式除了本文采用的調(diào)整航空器起飛時(shí)刻以及高度層優(yōu)化分配,還可以考慮航跡的水平調(diào)整、高度層和速度在不同航段的分別優(yōu)化;同時(shí),加入對(duì)航跡預(yù)測(cè)不確定性的考慮,使得模型更符合實(shí)際運(yùn)行情況,所生成的解沖突方案在存在不確定性的運(yùn)行環(huán)境下具備較強(qiáng)的魯棒性.