基于機器學(xué)習(xí)對串聯(lián)排隊系統(tǒng)等待時間的預(yù)測①

衛(wèi)安妮， 趙寧， 張志堅

昆明理工大學(xué) 理學(xué)院，昆明 650500

排隊網(wǎng)絡(luò)模型在流水生產(chǎn)線、 交通運輸、 計算機通信等領(lǐng)域應(yīng)用十分廣泛，吸引了眾多學(xué)者的關(guān)注． 串聯(lián)排隊系統(tǒng)是排隊網(wǎng)絡(luò)的基本結(jié)構(gòu)[1]，顧客在一個站接受服務(wù)后按照一定的規(guī)則接受下一個站的服務(wù)，研究該系統(tǒng)對深入分析復(fù)雜的排隊網(wǎng)絡(luò)具有重要意義．

串聯(lián)排隊系統(tǒng)的研究最早可追溯到20世紀50年代，文獻[2-5]研究了具有馬爾可夫性的串聯(lián)排隊系統(tǒng)的平均等待時間等性能指標． 隨后，關(guān)于滿足馬爾可夫性的串聯(lián)排隊系統(tǒng)得到了廣泛研究． 然而，實際生活中排隊系統(tǒng)一般不滿足馬爾可夫性，這導(dǎo)致串聯(lián)排隊系統(tǒng)的性能很難用解析的方法來求解，通常使用近似方法進行分析． 文獻[6]提出了排隊網(wǎng)絡(luò)分析方法(queueing network analysis，QNA)研究不滿足馬爾可夫性的串聯(lián)排隊系統(tǒng)． 文獻[7]利用到達過程和服務(wù)時間的一階矩和二階矩的近似提出了排隊網(wǎng)絡(luò)方法(queueing network，QNET)估計顧客的平均逗留時間． 文獻[8]基于分解的方法使用聯(lián)合矩對MAP/MAP/1排隊網(wǎng)絡(luò)進行了分析． 文獻[9]同樣基于分解算法提出魯棒排隊網(wǎng)絡(luò)分析器算法(robust queueing network analyzer，RQNA)近似開排隊網(wǎng)絡(luò)的穩(wěn)態(tài)性能． 文獻[10]使用固有比的方法近似串聯(lián)排隊系統(tǒng)的平均排隊時間． 文獻[11]采用指標比研究M/G/1-G/1串聯(lián)排隊系統(tǒng)的平均等待時間． 文獻[12]提出三階近似的方法分析GI/G/1-G/1串聯(lián)排隊系統(tǒng)的平均等待時間． 文獻[13]基于泛函重對數(shù)律和重對數(shù)律極限的方法，分析GI/G/1-G/1串聯(lián)排隊系統(tǒng)的性能指標的波動程度．

近年來，基于機器學(xué)習(xí)分析排隊系統(tǒng)引起一些學(xué)者的關(guān)注． 文獻[14]利用支持向量機(support vector machine，SVM)對排隊系統(tǒng)中到達和服務(wù)時間的概率密度函數(shù)進行分類和識別，并通過支持向量回歸(support vector regression，SVR)解決概率密度函數(shù)回歸的問題． 文獻[15]使用機器學(xué)習(xí)的方法對患者的治療數(shù)據(jù)進行預(yù)測，根據(jù)預(yù)測的治療時間推斷其等待時間，結(jié)果表明隨機森林模型為每日治療時間提供了最佳的預(yù)測． 文獻[16]使用分位數(shù)、 普通最小二乘(ordinary least square，OLS)回歸以及機器學(xué)習(xí)算法對某醫(yī)院患者的平均等待時間進行預(yù)測，結(jié)果表明套索回歸(lasso regression，Lasso)和分位數(shù)回歸方法的準確率更高． 文獻[17]使用交通模擬器對神經(jīng)網(wǎng)絡(luò)進行訓(xùn)練，得到一個自適應(yīng)交通系統(tǒng)． 文獻[18]使用神經(jīng)網(wǎng)絡(luò)方法對銀行排隊的等待時間進行預(yù)測，證明機器學(xué)習(xí)是預(yù)測排隊等待時間的一種可行方法． 文獻[19-20]使用高斯過程回歸預(yù)測單服務(wù)器和多服務(wù)器排隊網(wǎng)絡(luò)的平均逗留時間．

在日常生活中，串聯(lián)排隊系統(tǒng)廣泛存在于生產(chǎn)系統(tǒng)等領(lǐng)域． 串聯(lián)排隊系統(tǒng)中站與站之間存在關(guān)聯(lián)性，上游站的輸出過程是下游站的輸入過程，對于不滿足馬爾可夫性的排隊系統(tǒng)，下游站的到達過程很難用解析的方法分析． 本文考慮具有兩個站的串聯(lián)排隊系統(tǒng)，其到達過程和服務(wù)時間均服從一般分布，通過模擬串聯(lián)排隊系統(tǒng)的平均等待時間生成訓(xùn)練集，使用機器學(xué)習(xí)預(yù)測一般串聯(lián)排隊系統(tǒng)的平均等待時間，并與近似方法進行比較．

本文結(jié)構(gòu)如下： 第1節(jié)描述了兩個站的串聯(lián)排隊模型；第2節(jié)介紹了常見的線性和非線性機器學(xué)習(xí)回歸算法；第3節(jié)利用機器學(xué)習(xí)的方法預(yù)測串聯(lián)排隊系統(tǒng)的平均等待時間；第4節(jié)將機器學(xué)習(xí)中的XGBoost算法與其他近似方法進行比較；第5節(jié)為結(jié)論．

1 模型描述

本文研究圖1所示的串聯(lián)排隊系統(tǒng)，該系統(tǒng)由兩個站串聯(lián)而成，每個站有一個服務(wù)器，并且服務(wù)器前的緩沖區(qū)無限大． 顧客的到達過程為更新過程，顧客到達系統(tǒng)后依次在每個站接受服務(wù)，服務(wù)完成后離開系統(tǒng)． 系統(tǒng)的服務(wù)規(guī)則為先到先服務(wù)(first come first served，F(xiàn)CFS)，每個服務(wù)器的服務(wù)時間服從一般分布．

圖1 兩個站的串聯(lián)排隊系統(tǒng)

其中E(X)和D(X)分別表示到達時間間隔的期望和方差，E(Si)和D(Si)，i=1，2分別表示第1個站和第2個站的服務(wù)器的服務(wù)時間的期望和方差． 串聯(lián)排隊系統(tǒng)中第1個站和第2個站的服務(wù)強度分別記為ρ1和ρ2，且

ρ1=λaE(S1)

ρ2=λaE(S2)

令ρ=max{ρ1，ρ2}． 串聯(lián)排隊系統(tǒng)中第1個站和第2個站的平均排隊時間分別記為W1和W2．

2 機器學(xué)習(xí)回歸算法

近年來，機器學(xué)習(xí)快速發(fā)展，廣泛應(yīng)用于數(shù)據(jù)挖掘、 人工智能、 醫(yī)療保健、 排隊等領(lǐng)域． 與傳統(tǒng)回歸方法相比，機器學(xué)習(xí)能夠分析和挖掘數(shù)據(jù)中的規(guī)律，并對新的樣本進行預(yù)測，適合處理復(fù)雜的回歸問題． 下面介紹機器學(xué)習(xí)中常見的回歸算法．

2.1 線性回歸模型

機器學(xué)習(xí)中常見的線性回歸模型為多元線性回歸(multiple linear regression，MLR)、 嶺回歸(ridge regression，Ridge)以及套索回歸(lasso regression，Lasso)． 線性回歸模型屬于一種監(jiān)督學(xué)習(xí)算法，研究兩個隨機變量之間的線性關(guān)系． 該模型可表示為

Y=Xβ+ε

其中：X表示線性回歸模型的自變量集合，Y表示線性回歸模型的因變量，β表示偏回歸系數(shù)，ε表示模型擬合后每一個樣本的誤差項．

為了求解線性回歸模型的參數(shù)，將該模型的目標函數(shù)表示為[16]

2.2 非線性回歸模型

對于比較復(fù)雜的非線性回歸模型，需要在因變量和多個自變量之間構(gòu)建復(fù)雜的非線性關(guān)系． 機器學(xué)習(xí)的非線性回歸算法主要包括K近鄰(k-nearest neighbor，KNN)、 支持向量機(support vector machine，SVM)、 決策樹(decision tree，DT)、 隨機森林(random forest，RF)、 梯度提升樹(gradient boosting decision tree，GBDT)以及極端梯度提升(extreme gradient boosting，XGBoost)算法． 本文將以上非線性回歸算法分為3類： 遞歸劃分方法、 黑箱方法和集成學(xué)習(xí)方法[22]．

遞歸劃分方法主要包括決策樹(DT)算法． 該算法按照一定的規(guī)則持續(xù)拆分數(shù)據(jù)，每次將數(shù)據(jù)劃分為兩個相對一致的子集，直到達到目標，從而形成樹狀結(jié)構(gòu)，直觀反映變量的重要性，但該算法結(jié)構(gòu)不穩(wěn)定，容易產(chǎn)生過擬合的現(xiàn)象．

黑箱方法包括K近鄰算法(KNN)以及支持向量機(SVM)算法． 這類算法的輸入到輸出過程是通過一個模糊的“箱子”進行處理． KNN通過比較已知樣本和預(yù)測樣本的相似度，尋找最相似的k個樣本作為未知樣本的預(yù)測． 采用多重交叉驗證法選取最佳k值． SVM利用某些支持向量構(gòu)成的“超平面”，將不同類別的樣本點進行劃分，SVM算法與其他單一的算法相比，能夠?qū)⒌途S不可分的空間轉(zhuǎn)化為高維的線性可分空間，具有較高的預(yù)測準確性，但其最大的缺點是容易受共線性影響，運算成本高． 這類方法對數(shù)據(jù)缺失較敏感，處理大規(guī)模數(shù)據(jù)的效率較低．

集成學(xué)習(xí)方法通過選擇某種結(jié)合策略將若干弱學(xué)習(xí)器集合起來，以得到一個預(yù)測效果較好的強學(xué)習(xí)器． 隨機森林(RF)、 梯度提升樹(GBDT)以及極端梯度提升(XGBoost)算法是一類以決策樹(DT)為基學(xué)習(xí)器的集成學(xué)習(xí)算法． RF采用多棵決策樹的投票機制，即將多棵樹的回歸結(jié)果進行平均，最終得到樣本的預(yù)測值． 類似的，GBDT也是通過對多棵樹的結(jié)果進行綜合，不同的是每棵樹是從之前所有樹的殘差中學(xué)習(xí)的，并以新樹每個葉子的信息增益來進行最后的全局預(yù)測． XGBoost采用了隨機森林的思想，作為升級版的GBDT算法，XGBoost使用損失函數(shù)的一階導(dǎo)和二階導(dǎo)作為殘差的近似值，而GBDT僅利用損失函數(shù)的一階導(dǎo)作為殘差的近似值． 集成學(xué)習(xí)方法通常優(yōu)于單一的回歸方法，但預(yù)測速度明顯下降，隨著學(xué)習(xí)器數(shù)目的增加，所需的存儲空間也急劇增加[23]．

通常采用線性回歸模型以及非線性回歸模型進行預(yù)測時，需要將不同模型的運行時間成本和準確率進行對比分析，從中選擇合理的模型進行預(yù)測． 本文將準確率作為衡量標準，選擇較優(yōu)的模型對串聯(lián)排隊系統(tǒng)的平均等待時間進行預(yù)測．

3 基于機器學(xué)習(xí)預(yù)測平均等待時間

3.1 訓(xùn)練集數(shù)據(jù)

為了生成機器學(xué)習(xí)所需的訓(xùn)練集數(shù)據(jù)，首先對串聯(lián)排隊系統(tǒng)進行模擬，得到不同參數(shù)下串聯(lián)排隊系統(tǒng)的平均等待時間．

表1 訓(xùn)練集的參數(shù)

對于每個串聯(lián)排隊系統(tǒng)，模擬運行30個樣本，每個樣本取第400 001個顧客到600 000個顧客在第1個站和第2個站的等待時間的平均值分別作為第1個站和第2個站的平均等待時間，其中平均等待時間的置信水平大于95%，保證了模擬數(shù)據(jù)的可靠性．

3.2 數(shù)據(jù)預(yù)處理

在對訓(xùn)練集數(shù)據(jù)進行建模分析之前，需要對數(shù)據(jù)進行預(yù)處理以滿足模型的要求． 對于等待時間非常小的數(shù)據(jù)，即使預(yù)測值只有微小的偏差，其相對誤差也會非常大，造成整體的平均誤差偏大，影響預(yù)測效果． 因此，本文選取第1個站和第2個站的平均等待時間均大于0.1的數(shù)據(jù)進行分析． 從圖2和圖3的分布來看，模擬得到的串聯(lián)排隊系統(tǒng)的第1個站和第2個站的平均等待時間均呈現(xiàn)嚴重的右偏現(xiàn)象，為了滿足機器學(xué)習(xí)模型的數(shù)據(jù)要求，提高模型精度和訓(xùn)練效率，本文對第1個站的平均等待時間W1和第2個站的平均等待時間W2分別進行對數(shù)處理，令

圖2 第1個站的平均等待時間W1及其對數(shù)變換W′1

圖3 第2個站的平均等待時間W2及其對數(shù)變換W′2

W′i=log(Wi+1)，i=1，2

計算模擬得到的數(shù)值Wi和W′i(i=1，2)的核密度如圖2，3所示． 從圖中可知經(jīng)過對數(shù)處理后，W′1的分布近似服從正態(tài)分布，W′2的右偏現(xiàn)象明顯有所緩解，W′i，i=1，2的值域均縮小到[-2，8]之間，采用W′i加快了梯度下降求最優(yōu)解的速度，即機器學(xué)習(xí)訓(xùn)練的速度．

3.3 基于線性回歸模型預(yù)測平均等待時間

表2 線性回歸模型的最佳λ值

圖4 基于線性回歸模型對第1個站平均等待時間的預(yù)測

圖5 基于線性回歸模型對第2個站平均等待時間的預(yù)測

3.4 基于非線性回歸模型預(yù)測平均等待時間

下面使用非線性回歸模型對串聯(lián)排隊系統(tǒng)的平均等待時間進行預(yù)測，其中包括K近鄰(KNN)、 支持向量機(SVM)、 決策樹(DT)、 隨機森林(RF)、 梯度提升樹(GBDT)以及極端梯度提升(XGBoost)算法． 大多數(shù)機器學(xué)習(xí)算法都需要對參數(shù)進行設(shè)置，參數(shù)設(shè)置不同，學(xué)習(xí)得到的模型性能往往有顯著的差異． 因此，使用非線性回歸模型對平均等待時間進行預(yù)測時，需要對參數(shù)調(diào)優(yōu)． 為了提高參數(shù)優(yōu)化的效率，使用10重交叉驗證的方法調(diào)整參數(shù)，并通過網(wǎng)格搜索找到最佳的參數(shù)組合． 各模型參數(shù)的范圍和最優(yōu)值如表3所示，其中參數(shù)最優(yōu)值(x1，x2)中x1和x2分別表示預(yù)測W1和W2所設(shè)定的模型參數(shù)．

表3 模型的參數(shù)范圍和最優(yōu)值

對于上述非線性回歸模型，使用最優(yōu)的參數(shù)組合對訓(xùn)練集數(shù)據(jù)進行學(xué)習(xí)，并對測試集進行預(yù)測． 非線性回歸模型預(yù)測的第1個站和第2個站的平均等待時間及其模擬值如圖6，7所示． DT，RF，GBDT以及XGBoost算法的預(yù)測效果明顯優(yōu)于KNN和SVM算法，這是由于RF，GBDT和XGBoost是基于DT的集成學(xué)習(xí)算法，結(jié)合了對所有弱學(xué)習(xí)器的預(yù)測，優(yōu)于單一的學(xué)習(xí)器．

圖6 基于非線性回歸模型對第1個站平均等待時間的預(yù)測

圖7 基于非線性回歸模型對第2個站平均等待時間的預(yù)測

為了比較DT，RF，GBDT以及XGBoost算法的預(yù)測效果，將平均相對誤差r作為模型的評價標準，4種模型的第1個站的平均等待時間的平均相對誤差分別為3.42%，2.33%，2.79%，1.60%，第2個站的平均等待時間的平均相對誤差分別為8.34%，4.13%，3.34%，1.86%． 實驗結(jié)果表明，DT算法對于第2個站的平均等待時間的預(yù)測效果較差，XGBoost算法對第1個站和第2個站的平均等待時間的預(yù)測準確率分別為98.40%和98.14%，對串聯(lián)排隊系統(tǒng)的平均等待時間的預(yù)測較優(yōu)．

4 機器學(xué)習(xí)與近似方法的比較

目前，對于到達過程為更新過程，服務(wù)時間服從一般分布的排隊系統(tǒng)的平均等待時間的研究均采用近似方法． 文獻[24]研究了GI/G/1排隊系統(tǒng)的平均等待時間． 文獻[6]基于文獻[24]的方法使用排隊網(wǎng)絡(luò)分析方法(QNA)研究了具有非馬爾可夫性的串聯(lián)排隊系統(tǒng)的平均等待時間． 基于布朗運動，文獻[7]利用一階矩和二階矩的近似方法提出了使用QNET方法估計串聯(lián)排隊系統(tǒng)中顧客的平均逗留時間．

為了驗證本文方法的有效性，下面分別對GI/G/1-G/1系統(tǒng)以及M/G/1-G/1系統(tǒng)的平均等待時間的誤差進行比較．

對于上述串聯(lián)排隊系統(tǒng)，分別采用Kingman方法以及本文提出的XGBoost方法對第1個站的平均等待時間進行預(yù)測；使用QNA，QNET以及本文提出的XGBoost方法對第2個站的平均等待時間進行預(yù)測，各種方法預(yù)測的相對誤差如表4，5所示．

表4 系統(tǒng)1中兩個站的平均等待時間的相對誤差比較

由表4可知，在不同的繁忙程度下，對于第1個站的平均等待時間，XGBoost方法、 Kingman方法的平均相對誤差分別為0.43%，28.02%． Kingman方法是對平均等待時間上限的近似分析，其預(yù)測效果比XGBoost方法差．

對于第2個站的平均排隊時間，XGBoost方法、 QNA方法以及QNET方法的平均相對誤差分別為0.56%，30.49%以及19.42%． 相比于其他方法，XGBoost方法的相對誤差最小且平均誤差均小于1%． 在繁忙程度ρ較小時，顧客的平均等待時間較短，相對誤差較大． 由此可知，本文提出的XGBoost方法明顯優(yōu)于其他方法，并且在繁忙程度ρ較大時，預(yù)測效果最佳．

在M/G/1-G/1排隊系統(tǒng)中，第1個站的平均等待時間存在精確解析表達式，因此，僅對第2個站的平均等待時間的相對誤差進行比較． QNA方法、 QNET方法均通過考慮離去過程的一階矩和二階矩來刻畫串聯(lián)排隊系統(tǒng)中第1個站對第2個站的影響． 雖然這些方法很容易計算平均等待時間的近似值，但是其計算的精確度不高． 由表5可知，當(dāng)ρ={0.1，0.2，0.3，0.5，0.6，0.8，0.9}時，本文提出的XGBoost方法相對誤差最小，XGBoost方法、 QNA以及QNET方法的平均相對誤差分別為0.83%，4.58%以及3.55%． XGBoost方法的平均相對誤差最小，QNET方法優(yōu)于QNA方法，這是由于QNA方法在平方變異系數(shù)較大的情況下，參數(shù)分解方法的性能下降導(dǎo)致預(yù)測效果不佳[7]． 綜上所述，XGBoost方法優(yōu)于其他方法，近似效果較好，能夠比較準確地計算串聯(lián)排隊系統(tǒng)的平均等待時間．

表5 系統(tǒng)2中第2個站的平均等待時間的相對誤差比較

5 結(jié)論

本文采用機器學(xué)習(xí)中的線性回歸算法和非線性回歸算法預(yù)測串聯(lián)排隊系統(tǒng)的平均等待時間． 將仿真的通用性與機器學(xué)習(xí)的計算效率相結(jié)合，提高了平均等待時間預(yù)測的準確性． 大量的數(shù)值實驗表明，XGBoost方法對平均等待時間的預(yù)測效果較好．

本文主要研究了兩個站的串聯(lián)排隊系統(tǒng)，未來可以使用該方法對其他排隊系統(tǒng)進行深入研究，例如具有多個服務(wù)站的串聯(lián)排隊系統(tǒng)、 具有有限緩沖區(qū)的串聯(lián)排隊系統(tǒng)、 具有批量服務(wù)的串聯(lián)排隊系統(tǒng)以及復(fù)雜的排隊網(wǎng)絡(luò)等．