金逸喬

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

0 引言

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

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

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

1 電梯乘客起訖點(diǎn)矩陣

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

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

表1 起訖點(diǎn)表

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

圖1 電梯運(yùn)行起訖點(diǎn)描述示意

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

(1)

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

2 電梯乘客起訖點(diǎn)矩陣的最大熵模型

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

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

(2)

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

(3)

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

(4)

根據(jù)斯特林公式(Stirling approximation)lnx!≈xlnx-x，式(4)可以化簡(jiǎn)得式(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層離開(kāi)電梯人數(shù)，Aj是第j層離開(kāi)電梯人數(shù)，在實(shí)際問(wèn)題中，同一層上下電梯的情況可以忽略，因此令i≠j，由xij組成的對(duì)角矩陣X就是所要求得的起訖點(diǎn)矩陣。

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

(16)

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

(17)

可得式(18)。

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

(18)

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

(19)

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

傳統(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：計(jì)算F(λk)，J(λk)；

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

Step5：計(jì)算新的迭代點(diǎn)λk+1,λk+1=λk+Δλk;

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

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

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

遺傳算法的各項(xiàng)操作如下：

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

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

(22)

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

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

N(λ)=Cmax-M(λ)

(23)

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

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

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

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

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

(4) 選擇

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

(5) 交叉

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

(6) 變異

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

(7) 算法終止

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

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

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

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

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

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

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

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

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

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

4 實(shí)例分析

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

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

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

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

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

圖3 LM算法結(jié)果

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

表3 電梯乘客交通分布表

5 總結(jié)

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