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

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

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

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

1 系統(tǒng)模型

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

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

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

以當(dāng)前用戶的前6 名的真實(shí)排隊(duì)時(shí)間或預(yù)測(cè)等待時(shí)間作為輸入層，如果此6 名用戶已結(jié)束排隊(duì)則具有實(shí)際等待時(shí)間，否則只有算法給予的預(yù)測(cè)等待時(shí)間．以6 名用戶的預(yù)測(cè)等待時(shí)間作為輸入層容易增大誤差，解決方式詳見后文．隱藏層有13 個(gè)單元（1.3.2 小節(jié)會(huì)詳細(xì)闡述如何確定隱藏層單元個(gè)數(shù)），輸出層為當(dāng)前用戶的預(yù)測(cè)等待時(shí)間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 個(gè)隱藏層單元，另有閾值b2=1；隱藏層到輸出層權(quán)重為Whk，k=1,2,3,…,13，b2的權(quán)重為Wb2，權(quán)重矩陣的初始值皆隨機(jī)產(chǎn)生．

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

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

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

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

首先，根據(jù)用戶的實(shí)際等待時(shí)間和預(yù)測(cè)等待時(shí)間得到總體誤差；其次，對(duì)輸入層--＞隱藏層、隱藏層--＞輸出層的權(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)

總誤差的計(jì)算：

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

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

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

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

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

1.2.2 用戶的輸入層更新

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

輸入：前6 名用戶的排隊(duì)時(shí)間

輸出：預(yù)測(cè)排隊(duì)時(shí)間

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

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

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

3 結(jié) 語(yǔ)

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