電梯乘客交通分布的混合算法求解

金逸喬

(上海交通大學 電子信息學院，上海 200240)

0 引言

電梯作為垂直交通運輸?shù)闹匾ぞ?，隨著文明的不斷發(fā)展，早已成為了人類生活必不可少的部分。根據(jù)國家質(zhì)量監(jiān)督檢驗檢疫總局“關(guān)于2016年全國特種設(shè)備安全狀況情況的通報”顯示，截至2016 年底，全國在用電梯登記數(shù)量為493.69萬臺，我國電梯保有量、年產(chǎn)量、年增長量均為世界第一。面對如此龐大且復雜的輸送能力需求，如何通過改進電梯的配置方案以及服務(wù)性能來應(yīng)對這些需求，一直是電梯行業(yè)專家以及各國學者研究的課題。

電梯的交通客流情況，是各項研究的基礎(chǔ)數(shù)據(jù)。通過對客流情況的分析，可以調(diào)整和優(yōu)化電梯的群控系統(tǒng)，可以研究不同建筑的客流特性，可以檢驗和預(yù)測電梯的配置是否合理。電梯交通客流數(shù)據(jù)包含的內(nèi)容非常寬泛，理論上來說包含了乘客乘坐電梯發(fā)生的交通行為的所有數(shù)據(jù)。其中“每層進出電梯的乘客數(shù)”，能直接反映電梯乘客在建筑中交通狀況，同時獲取手段也比較多，因此在研究中較為常見。以往的研究中，側(cè)重點通常是電梯群控系統(tǒng)的優(yōu)化，因此每層進出電梯乘客數(shù)能夠符合要求。但如要進行電梯配置規(guī)劃及建筑客流分析，評價方式一般是一個絕對指標，此時就需要討論電梯及乘客在樓層間的交通情況，即電梯交通分布的信息。

隨著電梯遠程監(jiān)控與服務(wù)系統(tǒng)的大力發(fā)展[1]，每層進出電梯的乘客數(shù)已經(jīng)可以通過該系統(tǒng)記錄的電梯稱量裝置的相關(guān)數(shù)據(jù)來獲取，但是電梯交通分布信息難以通過簡單的方式大規(guī)模獲取。鑒于現(xiàn)狀，本文以每層進出電梯的乘客數(shù)為基礎(chǔ)，建立了乘客交通分布求解的模型，然后通過遺傳算法(Genetic Algorithm)與列文伯格-馬夸爾特算法(Levenberg-Marquardt Algorithm)結(jié)合的混合算法來求解模型，最終獲得電梯乘客交通分布信息。

1 電梯乘客起訖點矩陣

起訖點是一個在交通運輸規(guī)劃中被廣泛提及的概念，其描述的是交通網(wǎng)絡(luò)中從起點(origin)到終點(destination)的相關(guān)信息。而起訖點表，或稱OD表，就是一個交通網(wǎng)絡(luò)中所有起點與終點間產(chǎn)生的交通流量構(gòu)成的表格，是交通網(wǎng)絡(luò)的出行分布交通量的直觀表達，體現(xiàn)了用戶對于交通網(wǎng)絡(luò)的基本需求。根據(jù)起訖點數(shù)據(jù)表構(gòu)成的起訖點矩陣是進行進一步的交通規(guī)劃必不可少的基礎(chǔ)數(shù)據(jù)，是進行交通流量分配的前提，也是進行交通管理與控制優(yōu)化的重要基礎(chǔ)[2,3]。一個存在n個區(qū)域(即n個起點，n個終點)的交通網(wǎng)絡(luò)，其起訖點表如表1所示。

電梯作為垂直運輸工具，在許多地方與水平方向的交通運輸工具有著相似點。電梯運行產(chǎn)生的乘客交通量同樣存在起訖點的概念并形成一定的交通分布，在電梯的運行過程中，電梯運行的樓層是對交通區(qū)域的劃分，每個交通區(qū)域的發(fā)生量與吸引量相應(yīng)的是每一層進入電梯的乘客數(shù)與離開電梯的乘客數(shù)，乘客通過在起點樓層與終點樓層間的移動構(gòu)成了一張起訖點表，表的形式與表1一致，由ODij組成的n×n階的矩陣就是電梯乘客起訖點矩陣。

表1 起訖點表

求電梯乘客交通分布的問題可以作如下描述：在一個服務(wù)n層樓的電梯群組中，設(shè)Bi表示第i層進入電梯(boarding)的乘客數(shù)，Ai表示第i層離開電梯(alighting)的乘客數(shù)，xij表示從第i層進入、第j層離開的電梯乘客數(shù)，其組成了n×n階的矩陣X。其簡單示意如圖1所示。

圖1 電梯運行起訖點描述示意

根據(jù)起訖點的概念，Bi、Ai與xij具有如下關(guān)系如式(1)。

(1)

上述問題中，Bi和Aj是我們通過電梯遠程監(jiān)控與服務(wù)系統(tǒng)得到的數(shù)據(jù)，共有2n個已知量，而xij為未知量，共n2個，式(1)可以組成2n個線性方程，一般情況下，電梯乘客基本不會發(fā)生同一樓層進出的情況，即當i=j時xij=0，因此實際問題中未知量的個數(shù)可以減小為n(n-1)個，即要求的乘客起訖點矩陣X是個對角矩陣。同時，實際問題中，電梯服務(wù)層數(shù)超過3(即n>3)時，n(n-1)>2n，因此僅上述條件，無法求得xij。

2 電梯乘客起訖點矩陣的最大熵模型

Willumsen提出了的一種在交通運輸領(lǐng)域推算起訖點矩陣的模型——最大熵模型。將每個起訖點對的一次出行看作一次隨機的事件，每種可能出現(xiàn)的起訖點狀態(tài)都相應(yīng)存在一個出現(xiàn)概率，出現(xiàn)概率最高的就是實際存在的起訖點狀態(tài)[4]。

根據(jù)最大熵理論，在一個有n個區(qū)域的交通網(wǎng)絡(luò)中，從起點i到終點j的交通流量Tij就表示第ij個事件的發(fā)生次數(shù)，而網(wǎng)絡(luò)的總流量T，即事件的總次數(shù)就是式(2)。

(2)

根據(jù)特定的排列形成Tij的概率就是式(3)。

(3)

按照最大熵原理的思想，實際存在的Tij是使W(Tij)熵值最大的矩陣。因此，將其存在概率設(shè)為目標函數(shù)，為方便求解，目標函數(shù)設(shè)為式(4)。

(4)

根據(jù)斯特林公式(Stirling approximation)lnx!≈xlnx-x，式(4)可以化簡得式(5)。

(5)

(6)

(7)

Tij≥0

(8)

α=1,2,…,m

(9)

i,j=1,2,…,n

(10)

(11)

(12)

(13)

i≠j

(14)

i,j=1,2,…,n

(15)

其中，Bi是第i層離開電梯人數(shù)，Aj是第j層離開電梯人數(shù)，在實際問題中，同一層上下電梯的情況可以忽略，因此令i≠j，由xij組成的對角矩陣X就是所要求得的起訖點矩陣。

針對上述基于最大熵模型表述的優(yōu)化問題，是一個帶約束的非線性優(yōu)化問題，無法直接求解。易知(11)為凸函數(shù)，因此利用拉格朗日乘數(shù)法(Lagrange Multiplier Method)，構(gòu)造拉格朗日函數(shù)：

(16)

根據(jù)庫恩-塔克條件(Kuhn-Tucker Condition)，最優(yōu)解通過計算L(xij,λ)對xij的偏導數(shù)，即式(17)。

(17)

可得式(18)。

xij=e-1-λi-λn+j

(18)

根據(jù)式(12)，(13)，(14)和(18)，可得式(19)。

(19)

上述方程組是以拉格朗日乘子λ=(λ1,λ2,…λ2n)T為變量，共有2n個未知數(shù)的非線性方程組。那么，原問題就可以通過求解拉格朗日乘子，再代入式(4-23)來求得xij和X即起訖點矩陣。

傳統(tǒng)的求解方法是迭代法數(shù)值求解。以最典型的牛頓法為例，其求解方法如下。建立方程組F(λ)式(20)。

(20)

牛頓迭代格式為式(21)。

λk+1=λk-[J(λk)]-1F(λk)

(21)

其中，k為迭代次數(shù)，J(λ)為F(λ)的雅克比(Jacobi)矩陣。迭代的算法如下。

Step1：給定初始值λ0，和精度閾值ε>0，并令k=0；

Step2：計算F(λk)，J(λk)；

Step3：求解線性方程組J(λk)Δλk=-F(λk)，得Δλk;

Step5：計算新的迭代點λk+1,λk+1=λk+Δλk;

Step6：令k=k+1，轉(zhuǎn)至Step2。

3 混合算法求解最大熵模型

求解最大熵模型的傳統(tǒng)牛頓法在求解中有著不足：迭代過程中計算矩陣必須是非奇異矩陣。而在實際問題中，其最大的限制是必須給出初值。但考慮到實際的電梯乘客分布問題中，針對每一次采集到的電梯進出人數(shù)信息，是無法給出初始分布的，這也就意味著沒有辦法給出符合實際情況的初值，因此牛頓法包括其他一些改進的牛頓法難以適用。針對這個問題，本文提出一種遺傳算法(Genetic Algorithm)與列文伯格-馬夸爾特算法(Levenberg-Marquardt Algorithm)結(jié)合的混合算法來求解。遺傳算法的全局尋優(yōu)能力強，能夠在缺少初值信息的情況下，獲得一個較優(yōu)的數(shù)值解[6]。以此較優(yōu)解為初值，利用列文伯格-馬夸爾特算法開始迭代，能夠以良好的速度和精度獲得最優(yōu)解。這樣混合算法可以避免遺傳算法收斂慢的問題，同時能夠在實際問題中產(chǎn)生合適的初始值并快速求得模型的解。

遺傳算法的各項操作如下：

(1) 目標函數(shù)和適應(yīng)度函數(shù)

首先要確定遺傳算法的目標函數(shù)。本文基于式(19)和式(20)構(gòu)造目標函數(shù)如下式(22)。

(22)

式中，λ=(λ1,λ2,…λ2n)T，且i≠j。

適應(yīng)度函數(shù)為式(23)。

N(λ)=Cmax-M(λ)

(23)

式中，Cmax取一個M(λ)最大估計值，根據(jù)實際問題的情況而定。

(2) 編碼方式及種群初始化

本文采用浮點數(shù)編碼?？紤]到二進制編碼或格雷碼編碼的長度較大，計算量會增大，而對于本問題，變量的取值有負數(shù)存在，需要搜索的范圍較大，因此綜合相應(yīng)的選擇、交叉與變異方式，確定采用浮點數(shù)編碼。初始種群通過隨機的方式產(chǎn)生，種群規(guī)模需要根據(jù)不同情況進行設(shè)計，會由于實際問題中電梯的樓層數(shù)而改變，但是原則上，考慮到混合算法的目的是通過遺傳算法輸出一個供LM算法使用的初始值，因此種群規(guī)模不宜過小，否則會對全局搜索產(chǎn)生影響。

(3) 適應(yīng)度計算

算法需要通過個體適應(yīng)度來判斷個體的優(yōu)劣程度，來決定優(yōu)秀個體的遺傳。適應(yīng)度比例參數(shù)是把適應(yīng)度函數(shù)所返回的適應(yīng)度值轉(zhuǎn)換為適合于選擇函數(shù)使用范圍的值。本文通過個體適應(yīng)度值的排列順序而不是個體適應(yīng)度值的大小來衡量個體的優(yōu)劣，最適合個體的排序為1，次最適合個體的排序為2，依此類推，這樣可以消除原始適應(yīng)度值的影響。

(4) 選擇

選擇運算，又稱為復制運算。是在當前群體中選擇適應(yīng)度較高的個體按某種規(guī)則或模型遺傳到下一代群體中。在本文中采用輪盤賭規(guī)則，即與適應(yīng)度成正比的概率來確定各個體復制到下一代群體中的數(shù)量。具體的操作過程是：首先，計算出群體中所有個體的適應(yīng)度值的總和；其次，計算出每個個體的相對適應(yīng)度大小，每個個體都會在某個概率區(qū)間內(nèi)，該區(qū)間表示個體會被遺傳下去的概率大小，所有區(qū)間的概率值總和為1；最后，產(chǎn)生一個0～1之間的隨機數(shù)，通過判斷該隨機數(shù)落在上述哪一片概率區(qū)間來確定該各個體所對應(yīng)的被選中的機率。

(5) 交叉

交叉運算是遺傳算法中產(chǎn)生新個體的主要操作過程，它以某一概率相互交換某兩個個體之間的部分染色體。本文采用如下交叉的方式：在1到變量個數(shù)之間選擇兩個隨機數(shù)m和n，在第一個父輩中選擇序號小于或等于m的向量項，在第二個父輩中選擇序號在m+1到n的向量項，序號大于n的向量項也來自于第一個父輩。這樣可以有效提高遺傳算法的搜索速度，為盡快得到初始值，轉(zhuǎn)到LM算法做準備。

(6) 變異

變異運算對個體的某一些基因編碼串中的基因按某一概率進行改變以產(chǎn)生新的種群，指明了個體在子種群間的遺傳。本文采用基本位的方式進行變異。

(7) 算法終止

本文考慮的是通過遺傳算法得到LM算法的初始解，避免遺傳算法陷入局部過慢的收斂中，因此需要根據(jù)實際問題中不同的情況設(shè)置算法終止條件，一般通過設(shè)置進化代數(shù)限制來實現(xiàn)。

綜合上述分析，結(jié)合LM算法后，整個混合算法的步驟是：

Step1：遺傳算法初始化種群；

Step2：遺傳算法求解，得到局部最優(yōu)解及變量值；

Step3：變量作為初始值輸入LM算法作為初始迭代點λ0；

Step4：設(shè)置LM算法初始步長因子μ0，步長調(diào)整因子v>1，精度閾值ε>0，并令k=0；

Step5：計算F(λk)，J(λk)；

Step7：求解方程組(J(λk)TJ(λk)+μkI)Δλk=-J(λk)TF(λk)，得Δλk

Step8：計算F(λk+Δλk)，如果F(λk+Δλk)>F(λk)，則轉(zhuǎn)至Step9，否則轉(zhuǎn)至Step10；

Step9：令μk=vμk，轉(zhuǎn)至Step7；

4 實例分析

通過前文提及的電梯遠程監(jiān)控與服務(wù)系統(tǒng)采集了某醫(yī)院病房大樓電梯的每層進出電梯乘客數(shù)，采集時段是一個工作日，從電梯啟動到電梯停運為止，如表2所示。

表2 某大樓一天年內(nèi)進出電梯的乘客數(shù)據(jù)

使用混合算法求解最大熵模型，遺傳算法的相關(guān)參數(shù)為：種群規(guī)模POPSIZE=160，交叉概率PCROSS=0.8，變異概率PMUT=0.15，終止代數(shù)MAXGENS=400。400代進化結(jié)束后，算法結(jié)果如圖2所示。

圖2 遺傳算法結(jié)果

以遺傳算法的結(jié)果作為初始值，開始LM算法。結(jié)果如圖3所示。

圖3 LM算法結(jié)果

將LM算法得到的變量值代入，最終求得，大樓的乘客交通分布如表3所示。

表3 電梯乘客交通分布表

5 總結(jié)

作為電梯群控系統(tǒng)優(yōu)化、電梯配置規(guī)劃和建筑客流分析的基礎(chǔ)，電梯乘客交通分布的情況是一個重要的信息。本文在最大熵模型的基礎(chǔ)上提出了遺傳算法和LM結(jié)合的混合算法，求得電梯乘客交通分布，可以作為群控仿真、電梯配置規(guī)劃的輸入數(shù)據(jù)，無需進行費時費力的人工調(diào)查，有著很強的實用性。