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

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

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

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

1 系統(tǒng)模型

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

圖1 BP 神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)圖Fig 1 The Structure Chart for BP Neural Network

1.1 BP時間預(yù)測算法的正向傳輸

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

隱藏層單元hj的輸入加權(quán)和：

式（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，為輸入層到隱藏層權(quán)重，b1的權(quán)重為Wb1,j，j=1,2,3,…,13．

隱藏層單元hj的輸出Zhj：

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

輸出層單元pw的輸入加權(quán)和輸出為：

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

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

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

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

1.2.1 層與層之間的權(quán)重更新

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

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

總誤差的計算：

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

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

隱藏層的閾值權(quán)重更新：

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

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

1.2.2 用戶的輸入層更新

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

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

1.3.1 學(xué)習(xí)率的確定

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

在選定0.2 的學(xué)習(xí)率時：MSE=70.0；

在選定0.3 的學(xué)習(xí)率時：MSE=60.2；

在選定0.4 的學(xué)習(xí)率時：MSE=63.5；

在選定0.5 的學(xué)習(xí)率時：MSE=68.6；

在選定0.6 的學(xué)習(xí)率時：MSE=71.3．

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

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

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

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

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

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

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

1.4 BP時間預(yù)測算法模型的具體流程

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

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

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

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

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

4）當(dāng)一個用戶結(jié)束等待時，將其實際等待時間和預(yù)測等待時間置入算法中進(jìn)行權(quán)重更新，更新完畢的權(quán)重和該用戶的實際等待時間立刻用于其后用戶的等待時間預(yù)測．

BP 時間預(yù)測算法偽代碼如下．

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

輸出：預(yù)測排隊時間

2 預(yù)測結(jié)果分析

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

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

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

3 結(jié) 語

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