基于分布式混合灰狼蝗蟲優化算法航班延誤預測

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

(湖北工業大學計算機學院， 湖北 武漢 430068)

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

本文使用基于機器學習的分類方法，通過對航班延誤數據集的各個特征分析，確定與航班延誤相關的特征因素，運用隨機森林分類算法，得到航班延誤預測等級。為確定最優的隨機森林分類模型，使用分布式灰狼蝗蟲優化算法對隨機森林的參數進行調優。數據集實驗結果顯示，優化后的航班延誤預測的準確率更高，運行時間更少。

1 航班延誤預測

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

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

表1 延誤分級

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

2 混合灰狼蝗蟲優化算法

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

(1)

其中:f表示吸引力的強度，l是吸引力的大小范圍,在文獻中取值f=0.5，l=1.5。

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

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

(2)

(3)

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

算法1 GWOGOA算法偽代碼

Input：蝗蟲搜索個數N，搜索空間范圍up、down，個體維度dim，迭代次數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 分布式混合灰狼蝗蟲優化算法

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

Step1 算法初始化，在搜索空間范圍內隨機生成蝗蟲群；

Step2 根據目標函數計算蝗蟲個體適應度，生成α、β和δ狼并使用Spark廣播變量；

Step 3 使用parallelize()函數將種群轉為positionRDD；

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

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

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

Step7 根據目標函數計算蝗蟲適應度，更新α、β和δ狼并使用Spark廣播變量；

Step8 迭代次數加1，如果達到停止條件則輸出當前α狼的位置，否則返回Step4。

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

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

Input：蝗蟲搜索個數N，搜索空間范圍up、down，個體維度dim，迭代次數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算法的性能，使用四種測試函數來判斷算法的收斂性，為體現分布式GWOGOA算法的尋優能力，采用海鷗優化算法(Seagull Optimization Algorithm，SOA)和混合灰狼蝗蟲優化算法作為對比，海鷗優化算法是2018年提出的新型智能優化算法，具有收斂快、精度高、算法新的特點，因此使用SOA作為智能優化算法的代表進行對比實驗。測試函數分別為Sphere、Schwefel2.22、Schwefel1.2、Schwefel2.21實驗結果如圖1所示，可以看出分布式GWOGOA算法具有較好的尋優能力。

圖 1 不同算法迭代曲線

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

圖 2 分布式GWOGOA對比GOA預測準確率

圖 3 對比單機和Spark平臺運行時間

5 結論

將混合算法思想與分布式思想結合提出分布式混合灰狼蝗蟲優化算法，具有更強的尋優性能，將分布式混合灰狼蝗蟲優化算法用于隨機森林參數的調優，選擇更合適的參數，構建性能更優的隨機森林分類模型，提高了航班延誤預測準確率，且模型運行時間縮短了42%。