基于分布式混合灰狼蝗蟲優(yōu)化算法航班延誤預(yù)測

涂勝紅， 陳宏偉， 楊威威， 楊智慧

(湖北工業(yè)大學(xué)計算機(jī)學(xué)院， 湖北 武漢 430068)

世界航空貨運(yùn)預(yù)測：航空市場將保持4.7%的增速[1]。隨著航班數(shù)量增加，航班延誤和取消的現(xiàn)象變得越來越普遍。航班延誤和取消不僅影響個人出行，也嚴(yán)重?fù)p害航空公司的聲譽(yù)和利益[2]，對我國民航業(yè)的發(fā)展造成阻礙。近年來國內(nèi)外研究者對航班延誤預(yù)測進(jìn)行了一些研究，Khanmohammadi采用多層級ANN挖掘航班數(shù)據(jù)集輸入變量與輸出變量關(guān)系[3]；Farshchian等人提出了一種基于深度學(xué)習(xí)的航班延誤預(yù)測模型，結(jié)合堆棧的自動去噪編碼技術(shù)提高模型預(yù)測準(zhǔn)確率[4]；Yu等采用深度信念網(wǎng)絡(luò)與支持向量機(jī)融合方法在大型數(shù)據(jù)集捕獲特征方面具有很好的效果[5]；李華峰采用貝葉斯網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)相結(jié)合的方法建立預(yù)測模型，另外加入影響航班延誤因素，進(jìn)一步建立航班延誤波及傳遞的貝葉斯網(wǎng)絡(luò)模型[6]；張兆寧等人基于SEIR思想將航班分為正常、延誤、延誤傳播及恢復(fù)四種狀態(tài)，通過計算基本再生的值來預(yù)測下一時段的航班延誤發(fā)生[7]；王語桐等人采用支持向量機(jī)和多元線性回歸方法建立組合預(yù)測模型，對航班延誤進(jìn)行預(yù)測[8]。

本文使用基于機(jī)器學(xué)習(xí)的分類方法，通過對航班延誤數(shù)據(jù)集的各個特征分析，確定與航班延誤相關(guān)的特征因素，運(yùn)用隨機(jī)森林分類算法，得到航班延誤預(yù)測等級。為確定最優(yōu)的隨機(jī)森林分類模型，使用分布式灰狼蝗蟲優(yōu)化算法對隨機(jī)森林的參數(shù)進(jìn)行調(diào)優(yōu)。數(shù)據(jù)集實驗結(jié)果顯示，優(yōu)化后的航班延誤預(yù)測的準(zhǔn)確率更高，運(yùn)行時間更少。

1 航班延誤預(yù)測

由于航空系統(tǒng)的復(fù)雜性，航班延誤的成因也具有復(fù)雜性和隨機(jī)性，其影響因素包括人為因素如旅客影響、空管影響、機(jī)場管理影響等，還有不可控的因素如天氣、軍事原因?qū)е碌暮桨嘌诱`或取消。研究使用的航班延誤數(shù)據(jù)來自Kaggle網(wǎng)站上美國交通運(yùn)輸部的(BTS)2009-2018年全美航空公司航班運(yùn)行信息數(shù)據(jù)，該數(shù)據(jù)集包含超過五千萬條航班運(yùn)行信息，采集航班運(yùn)行過程中多種特征數(shù)據(jù)，同時航空系統(tǒng)的運(yùn)行具有相似性，其數(shù)據(jù)特征的研究具有相通性，因此采用BTS的信息數(shù)據(jù)研究對我國航空發(fā)展仍然具有意義。

2009-2018年航班延誤數(shù)據(jù)集包含28個特征，分別是航班日期、航空公司識別碼、航班號等等。將上述數(shù)據(jù)進(jìn)行特征分析保留對航班延誤具有相關(guān)性的特征，一方面能夠提高預(yù)測準(zhǔn)確率，另一方面減少無關(guān)特性對預(yù)測結(jié)果帶來干擾，缺失值采用隨機(jī)取值然后計算均值的方法插入。字符屬性數(shù)值化處理包括航空公司識別碼、機(jī)場代碼都是字符類型數(shù)據(jù)，按照在數(shù)據(jù)集中出現(xiàn)順序，依次使用不同的數(shù)值代替。在構(gòu)建航班延誤預(yù)測模型時，按照航班到達(dá)時間將航班延誤進(jìn)行分級預(yù)測，在延誤分級之后將標(biāo)簽數(shù)值化，分為五個類別。在下面的實驗部分將對數(shù)據(jù)集標(biāo)簽進(jìn)行訓(xùn)練和預(yù)測。分級范圍和標(biāo)簽設(shè)置見表1。

表1 延誤分級

在數(shù)據(jù)集的設(shè)計中考慮到后續(xù)研究實驗將在Spark大數(shù)據(jù)平臺對模型進(jìn)行訓(xùn)練，為了后續(xù)對比算法運(yùn)行效率，將航班延誤數(shù)據(jù)集按照數(shù)據(jù)條數(shù)分別劃分為不同的數(shù)據(jù)集，分別包含的數(shù)據(jù)條數(shù)為500萬條、1000萬條、2000萬條和5000萬條數(shù)據(jù)。

2 混合灰狼蝗蟲優(yōu)化算法

灰狼優(yōu)化算法(Grey Wolf Optimizer，GWO)是一種進(jìn)化元啟發(fā)式算法，其仿真行為是灰狼的領(lǐng)導(dǎo)等級和狩獵食物的行為，蝗蟲優(yōu)化算法(Grasshopper Optimization Algorithm，GOA)是2017年提出的模仿蝗蟲運(yùn)動行為的群智能優(yōu)化算法，與大多數(shù)算法相比，GWO算法的主要優(yōu)勢是：元啟發(fā)式算法不需要特定的輸入?yún)?shù)，同時具有較強(qiáng)的局部尋優(yōu)能力。GOA的優(yōu)勢在于處理復(fù)雜、高維數(shù)據(jù)時全局尋優(yōu)能力強(qiáng)?？紤]到GWO和GOA各自的優(yōu)勢，這兩種算法非常適合雜交混合，混合算法由GWO和GOA組成，稱為混合灰狼蝗蟲優(yōu)化算法(Hybrid Gray Wolf Optimizer Grasshopper Optimization Algorithm，GWOGOA)，將GWO等級機(jī)制引入到GOA中，每一次迭代過程中，種群按照適應(yīng)度大小依次選出α狼、β狼和δ狼，根據(jù)它們的位置共同指導(dǎo)種群的進(jìn)化方法，而不是僅僅根據(jù)單一的最優(yōu)個體進(jìn)行更新，避免了單一個體對種群進(jìn)化的絕對控制，有效避免算法陷入局部最優(yōu)，GWOGOA算法的蝗蟲種群位置更新依據(jù)公式(1)進(jìn)行。

(1)

其中:f表示吸引力的強(qiáng)度，l是吸引力的大小范圍,在文獻(xiàn)中取值f=0.5，l=1.5。

啟發(fā)式算法還使用交叉和變異操作增強(qiáng)智能優(yōu)化算法的勘探和開發(fā)能力，它有助于GWOGOA避免過早的收斂影響算法性能。交叉策略將種群個體根據(jù)適應(yīng)度大小分為兩部分，對于優(yōu)秀種群部分予以保留，對于非優(yōu)種群使用公式(2)交叉策略。變異策略是為了增強(qiáng)種群的隨機(jī)性，以保留算法跳出局部收斂點的可能性，保持種群多樣性以避免算法陷入局部最優(yōu)，變異率是變異個體占種群總數(shù)量的比例，過大的變異率使種群波動過大難以收斂，變異率太小起不到保持種群多樣性，跳出局部最優(yōu)的目的，對所有個體按照公式(3)進(jìn)行變異。

xi(t)=xm(1)+…,xm(k)+xn(k+1),…+xn(d), [k]=rand*dim

(2)

(3)

公式(2)中k為隨機(jī)選擇的交叉位置，m、n表示選中的兩個蝗蟲;公式(3)中rand()為[0,1]之間的隨機(jī)數(shù)，k表示變異的位置，變異概率p為0.2，交叉變異之后的種群繼續(xù)計算適應(yīng)度迭代更新α狼、β狼和δ狼的位置。具體算法實現(xiàn)步驟如下：

算法1 GWOGOA算法偽代碼

Input：蝗蟲搜索個數(shù)N，搜索空間范圍up、down，個體維度dim，迭代次數(shù)Max_iter

Output：α狼個體

1: 初始化蝗蟲群position←InitPosition(N,up,down,dim)

2:forallgrasshopper in position

3:dogetFitness(grasshopper, trainRDD)

4:endfor

5:α、β、δ wolf ← getWolfs(grasshoper)

6:whileiter < Max_iter

7:forallgrasshopper in position

8: c←公式3

9: x(t+1) ←公式1、2

10: newPosition ←position.cross(),變異交叉策略

11:endfor

12: α、β、δ wolf←getWolfs(grasshoper) ∥更新α、β、δ狼的位置

13: iter += 1

14:endwhile

3 分布式混合灰狼蝗蟲優(yōu)化算法

Apache Spark是一種基于內(nèi)存計算的大數(shù)據(jù)計算框架，能將數(shù)據(jù)加載至內(nèi)存后重復(fù)使用，減少數(shù)據(jù)寫磁盤，有效提高大數(shù)據(jù)迭代計算運(yùn)行效率。傳統(tǒng)優(yōu)化算法只能單機(jī)串行計算，面對計算復(fù)雜度高和數(shù)據(jù)量大的場景，算法運(yùn)算速度受限于單機(jī)配置，運(yùn)行效率低。因此基于Spark大數(shù)據(jù)平臺，使用Spark提供的算子將混合灰狼蝗蟲優(yōu)化算法做分布式改進(jìn)。算法初始化在driver進(jìn)行，進(jìn)一步抽象為RDD分布到不同的計算節(jié)點并行計算，算法具體步驟描述如下：

Step1 算法初始化，在搜索空間范圍內(nèi)隨機(jī)生成蝗蟲群；

Step2 根據(jù)目標(biāo)函數(shù)計算蝗蟲個體適應(yīng)度，生成α、β和δ狼并使用Spark廣播變量；

Step 3 使用parallelize()函數(shù)將種群轉(zhuǎn)為positionRDD；

Step4 將positionRDD使用mapToPair()算子將種群映射為(個體,種群)的格式生成pairRDD；

Step5 使用公式3更新參數(shù)c、使用公式1對pairRDD使用map算子轉(zhuǎn)換計算，使用公式5、6使用交叉和變異策略得到newPairRDD；

Step6 使用collect()算子將種群更新后的個體回收得到更新后的蝗蟲種群；

Step7 根據(jù)目標(biāo)函數(shù)計算蝗蟲適應(yīng)度，更新α、β和δ狼并使用Spark廣播變量；

Step8 迭代次數(shù)加1，如果達(dá)到停止條件則輸出當(dāng)前α狼的位置，否則返回Step4。

隨機(jī)森林(Random Forest，RF)是一種基于Bagging的集成機(jī)器學(xué)習(xí)方法，具有準(zhǔn)確率高、抗噪能力強(qiáng)的優(yōu)點，因此使用隨機(jī)森林對航班延誤做分類預(yù)測。隨機(jī)森林的性能受不同參數(shù)影響較大，為了找到性能最優(yōu)的隨機(jī)森林模型，將分布式混合灰狼蝗蟲算法用于隨機(jī)森林參數(shù)的調(diào)優(yōu)。選擇隨機(jī)森林主要的參數(shù)n_estimators、max_features、max_depth作為蝗蟲個體的編碼，進(jìn)行迭代計算尋優(yōu)。蝗蟲個體解碼出參數(shù)建立隨機(jī)森林，輸入航班延誤數(shù)據(jù)集做分類預(yù)測，最后分類預(yù)測的準(zhǔn)確率作為該個體的適應(yīng)度。分布式GWOGOA預(yù)測模型的偽代碼如下：

算法2 基于Spark的分布式GWOGOA預(yù)測模型偽代碼

Input：蝗蟲搜索個數(shù)N，搜索空間范圍up、down，個體維度dim，迭代次數(shù)Max_iter

Output：α狼個體

1: spark←SparkSession.builder().appName(“SparkGOA”).getOrCreate() ∥ Spark集群入口

2: trainRDD←spark.read().format("libsvm").load(datapath)

3: positions←InitPosition(N,up,down,dim)

4:forallposition in positions

5: α、β、δ←getWolfs(grasshopper, trainRDD)

6: positionRDD←spark.parallelize(position)

7: pairRDD←positionRDD.mapToPair( _ , position) ∥ 映射為(個體，種群)

8:endfor

9:whileiter < Max_iter

10: c←公式3

11:forallgrasshopper in position

12: newPositionRDD←pairRDD.map()∥公式1、2計算位置

13: newPosition←newPositionRDD.cross().collect() ∥個體回收到driver

14: α、β、δ← getWolfs(newTargetPosition) ∥更新α、β、δ狼的位置

15:endfor

16: iter +=1

17:endwhile

4 實驗分析

為評估分布式GWOGOA算法的性能，使用四種測試函數(shù)來判斷算法的收斂性，為體現(xiàn)分布式GWOGOA算法的尋優(yōu)能力，采用海鷗優(yōu)化算法(Seagull Optimization Algorithm，SOA)和混合灰狼蝗蟲優(yōu)化算法作為對比，海鷗優(yōu)化算法是2018年提出的新型智能優(yōu)化算法，具有收斂快、精度高、算法新的特點，因此使用SOA作為智能優(yōu)化算法的代表進(jìn)行對比實驗。測試函數(shù)分別為Sphere、Schwefel2.22、Schwefel1.2、Schwefel2.21實驗結(jié)果如圖1所示，可以看出分布式GWOGOA算法具有較好的尋優(yōu)能力。

圖 1 不同算法迭代曲線

集群實驗環(huán)境由四臺虛擬機(jī)組成，虛擬機(jī)搭建在Win10系統(tǒng)上，處理器為9400，內(nèi)存為24G，使用Hadoop3.2.1，Spark3.0搭建4節(jié)點的分布式集群。航班延誤預(yù)測模型的參數(shù)設(shè)置種群個體N=10、迭代次數(shù)為20次、分布式GWOGOA與GOA的準(zhǔn)確率迭代結(jié)果如圖2所示，可以看到基于Spark的分布式GWOGOA算法有效提高航班延誤預(yù)測準(zhǔn)確率。在Spark集群上使用Yarn作為集群資源管理器，將GOA算法模型作為對比，算法的運(yùn)行效率對比見圖3，分布式GWOGOA算法解決了模型運(yùn)行效率低的問題，顯著減少了模型訓(xùn)練運(yùn)行時間。

圖 2 分布式GWOGOA對比GOA預(yù)測準(zhǔn)確率

圖 3 對比單機(jī)和Spark平臺運(yùn)行時間

5 結(jié)論

將混合算法思想與分布式思想結(jié)合提出分布式混合灰狼蝗蟲優(yōu)化算法，具有更強(qiáng)的尋優(yōu)性能，將分布式混合灰狼蝗蟲優(yōu)化算法用于隨機(jī)森林參數(shù)的調(diào)優(yōu)，選擇更合適的參數(shù)，構(gòu)建性能更優(yōu)的隨機(jī)森林分類模型，提高了航班延誤預(yù)測準(zhǔn)確率，且模型運(yùn)行時間縮短了42%。