基于BP神經(jīng)網(wǎng)絡的排隊時間預測算法研究

潘櫻丹，錢佳麗，何妍蕾，唐震洲

(溫州大學數(shù)理與電子信息工程學院，浙江溫州 325035)

隨著現(xiàn)代生活節(jié)奏的加快，如何更高效地利用時間已然成為生活的重要需求．然而筆者觀察到，現(xiàn)有的許多排隊機制都在無形中浪費人們的時間，例如銀行取號排隊，人們常因為擔心過號而在大廳等候，雖然存在著一些能夠顯示預計排隊時間的APP，但其預測的排隊時間往往來自于大數(shù)據(jù)的平均值，一般和當天的實際情況不相符．因此研究排隊時間預測算法及其應用極具現(xiàn)實意義，將理論上的預測算法帶入現(xiàn)實生活，使人們避免為排隊浪費時間，從而獲得更高效便捷的生活方式．

在排隊時間預測領域的現(xiàn)有研究中，一般采用排隊論和傳感技術的結合，例如在機場利用WIFI 進行室內(nèi)定位得到排隊區(qū)域的客流量，然后再根據(jù)排隊論模型預測排隊時間[1]．但是排隊論在等待時間的計算上不夠動態(tài)，且傳感技術的部署成本較大，不能廣泛使用．因此需要更動態(tài)、成本更低的算法，比如決策樹算法，核心思想是選取具有最高信息增益的屬性，常用于預測數(shù)據(jù)的類別[2]；支持向量機，一種基于結構風險最小化原則的機器學習方法，適用于小樣本[3]．在多種預測算法中，BP 算法具有自學習、自組織、高容錯性的特點，預測較為精確，且在國內(nèi)外應用廣泛．例如，模糊優(yōu)選神經(jīng)網(wǎng)絡模型可以用來預測泥石流的平均流速，該模型在對云南蔣家溝黏性泥石流平均流速的預測中取得了很大成果[4]；BP 算法在股票預測中也有所應用，BP 神經(jīng)網(wǎng)絡的權值初始化在進行改進之后能夠較為準確的預測股價[5]；此外，BP 算法也應用于公交車到站時間的預測，通過公交車到站的歷史數(shù)據(jù)和實時數(shù)據(jù)對BP 算法的訓練，能夠得到相當準確的公交車到站預測時間[6]．因此，本文選擇了BP 算法來預測排隊等待時間．經(jīng)過實地考察測試以及誤差分析，結果表明，利用歷史排隊時間對BP 算法進行訓練能夠較為準確地預測當前用戶的排隊等待時間．

1 系統(tǒng)模型

本文采用的預測算法模型基于傳統(tǒng)BP 算法同時有所修改，具體模型如圖1．

圖1 BP 神經(jīng)網(wǎng)絡結構圖Fig 1 The Structure Chart for BP Neural Network

1.1 BP時間預測算法的正向傳輸

以當前用戶的前6 名的真實排隊時間或預測等待時間作為輸入層，如果此6 名用戶已結束排隊則具有實際等待時間，否則只有算法給予的預測等待時間．以6 名用戶的預測等待時間作為輸入層容易增大誤差，解決方式詳見后文．隱藏層有13 個單元（1.3.2 小節(jié)會詳細闡述如何確定隱藏層單元個數(shù)），輸出層為當前用戶的預測等待時間pw，以分鐘為單位．基礎算法如圖1 所示．

隱藏層單元hj的輸入加權和：

式（1）中，hwk，k=1,2,3,4,5,6，為輸入層單元，以分鐘為單位，另有閾值b1=1；Whwi,j，i=1,2,3,4,5,6，j=1,2,3,…,13，為輸入層到隱藏層權重，b1的權重為Wb1,j，j=1,2,3,…,13．

隱藏層單元hj的輸出Zhj：

式（2）中，Zhj，j=1,2,3,…,13，是隱藏層激活后的輸出，在隱藏層和輸出層，均采用sigmoid函數(shù)作為激活函數(shù)[7]．

輸出層單元pw的輸入加權和輸出為：

式（3）中，hk，k=1,2,3,…,13，是13 個隱藏層單元，另有閾值b2=1；隱藏層到輸出層權重為Whk，k=1,2,3,…,13，b2的權重為Wb2，權重矩陣的初始值皆隨機產(chǎn)生．

式（4）中，Zpw為輸出層激活后的輸出，也是算法最終輸出的預測結果，同時顯示給用戶．

1.2 BP神經(jīng)算法的反饋機制

由于BP 神經(jīng)網(wǎng)絡最初的權重為隨機產(chǎn)生，如果不根據(jù)實際值和預測值的誤差調(diào)整權重，BP神經(jīng)網(wǎng)絡將無法準確地適應具體情景．因此，必須使用歷史數(shù)據(jù)對BP 算法加以訓練[8]．本文的預測算法模型的反饋機制分為兩部分：①輸入層--＞隱藏層、隱藏層--＞輸出層的權重更新；②某用戶結束等待后，其后用戶的輸入層更新．

1.2.1 層與層之間的權重更新

首先，根據(jù)用戶的實際等待時間和預測等待時間得到總體誤差；其次，對輸入層--＞隱藏層、隱藏層--＞輸出層的權重進行一一更新．下面以隱藏層--＞輸出層的權重更新為例進行闡述，如圖2所示．

圖2 BP 神經(jīng)網(wǎng)絡的反饋機制（隱藏層--＞輸出層的權重更新）Fig 2 The Feedback Mechanism for BP Neural Network(hidden layer --＞output layer weight updating)

總誤差的計算：

式中，target 為用戶的實際等待時間，output 為預測等待時間．

根據(jù)梯度下降法，隱藏層到輸出層的權重更新為：

隱藏層的閾值權重更新：

（8）式中，η為學習率，本文取0.3．下文會講到如何確定學習率．

輸入層--＞隱藏層的權重更新與隱藏層--＞輸出層同理，只是計算對象變化．

1.2.2 用戶的輸入層更新

該機制的主要目的是解決預測等待時間作為輸入層帶來的誤差問題．在一個用戶結束等待時將產(chǎn)生實際等待時間，算法利用其實際等待時間與預測等待時間的誤差進行權重更新，更新完畢后迭代更新其后所有用戶的輸入層和預測等待時間，具體過程可見圖3．

1.3 BP時間預測算法的關鍵參數(shù)處理與確定

1.3.1 學習率的確定

學習率是權重更新算法的重要參數(shù)，在BP 算法中學習率的確定很重要．因為BP 算法學習率一經(jīng)確定就不再改變，并且決定后期權重更新的收斂速度[9]．本文通過多次數(shù)據(jù)測試確定如下學習率：

在選定0.2 的學習率時：MSE=70.0；

在選定0.3 的學習率時：MSE=60.2；

在選定0.4 的學習率時：MSE=63.5；

在選定0.5 的學習率時：MSE=68.6；

在選定0.6 的學習率時：MSE=71.3．

通過多次比較均方差，確定0.3 為最適合本模型的學習率．

1.3.2 隱藏層節(jié)點數(shù)的確定

根據(jù)Komogorov 定律，一個具有m個輸入層節(jié)點、2m+1個隱藏層節(jié)點、n個輸出層節(jié)點的三層網(wǎng)絡，可以精確實現(xiàn)任意連續(xù)函數(shù)[10]．在本文的BP 算法模型中，以當前用戶的前6 名用戶的等待時間作為輸入層節(jié)點，因此選擇隱藏層節(jié)點數(shù)為13 個．

1.3.3 輸入層輸出層的數(shù)據(jù)處理

在數(shù)據(jù)處理方面，由于輸入層和輸出層的實際值單位為分鐘數(shù)值過大而權重過小，會導致權重無法影響數(shù)據(jù)變化和權重無法進行更新而預測失敗，因此在產(chǎn)生輸入層和輸出層實際值時先進行歸一化處理．我們采用的歸一化處理方式為最大值歸一化[11]：在輸入的所有歷史數(shù)據(jù)中選出最大的等待時間，輸入層即為實際等待時間/最大等待時間．輸入層歸一化處理的公式為：

其中，hwmax為所有輸入層歷史數(shù)據(jù)中的最大等待時間．而輸出層歸一化處理的公式為：

其中，pwmax為所有輸出層歷史數(shù)據(jù)中的最大等待時間．

1.4 BP時間預測算法模型的具體流程

該算法對排隊等待時間預測的具體實施流程如圖3 所示：

圖3 BP 時間預測算法的具體流程Fig 3 The Detailed Flow for BP Time Prediction Algorithm

1）建立一個輸入層為6、隱藏層為13、輸出層為1、學習率為0.3 的BP 算法模型；

2）使用來自合作商家的歷史數(shù)據(jù)對權重隨機的BP 算法進行訓練，以適應當前的情形；

3）用戶進行取號操作，調(diào)用歷史數(shù)據(jù)庫查看其前6 個用戶是否有實際等待時間，如果有則采用，否則使用預測等待時間作為該用戶的輸入層．調(diào)用BP 算法，顯示預測結果；

4）當一個用戶結束等待時，將其實際等待時間和預測等待時間置入算法中進行權重更新，更新完畢的權重和該用戶的實際等待時間立刻用于其后用戶的等待時間預測．

BP 時間預測算法偽代碼如下．

輸入：前6 名用戶的排隊時間

輸出：預測排隊時間

2 預測結果分析

將上文所述模型應用于實際排隊時間預測．在某餐廳，晚餐時間段（16: 00- 20: 00）實地考察了67 組數(shù)據(jù)，預測誤差基本在8 分鐘以內(nèi)，其中60組數(shù)據(jù)的實際值和預測值的對比圖如圖4所示：

圖4 60組數(shù)據(jù)的實際值和預測值的對比圖Fig 4 The Area Chart for Actual Value and Predicted Value from 60Sets of Data

60組數(shù)據(jù)的分析結果：MSE=60.2；RMSE=7.75．在圖4 中可以觀察到幾組等待時間異常的數(shù)據(jù)，例如某組數(shù)據(jù)的等待時間近100分鐘，但其后幾組數(shù)據(jù)的等待時間驟降至70分鐘左右，這幾組異常數(shù)據(jù)是由人們行為的不穩(wěn)定性導致的．當天用餐的時間、天氣、心情都可能影響用餐人的用餐速度，進而影響預測結果的準確性．在剔除這幾組數(shù)據(jù)的影響后，可以明顯發(fā)現(xiàn)均方差的降低．剔除幾組異常數(shù)據(jù)后的均方差為：MSE=5.31．從均方差的大幅度降低可以見得，在大部分時候，算法預測的準確率是比較高的，在偶然的不穩(wěn)定因素出現(xiàn)時，算法才出現(xiàn)局部的偏差．但我們不能因此而忽略了這種不穩(wěn)定因素的存在，因此我們后續(xù)的研究方向是，在考慮前6人的等待時間外，把當天的其它因素也轉(zhuǎn)化成算法的一個特征值以減少這些特殊行為帶來的誤差，提高算法的容錯能力．

3 結 語

日常生活中經(jīng)常會出現(xiàn)長時間的排隊等待現(xiàn)象，為了減少枯燥的等待行為和避免過號現(xiàn)象，本文提出了一種基于BP 算法的排隊時間預測算法．經(jīng)過實地考察、數(shù)據(jù)測試分析，證明該BP算法模型可以較好地為人們預測較為準確的排隊時間．后續(xù)研究中我們會繼續(xù)深入，希望能夠進一步減少誤差，為人們提供更高精度的預測．