基于蟻群算法的電梯群控系統(tǒng)節(jié)能策略的優(yōu)化研究

周衛(wèi)紅，裴 箏，和曉萍，李 晨，陸偉春

(1.云南民族大學(xué)數(shù)學(xué)與計算機科學(xué)學(xué)院，云南昆明650500;2.鄭州大學(xué)西亞斯國際學(xué)院，河南新鄭451150)

電梯群控系統(tǒng)指安裝在建筑物內(nèi)的3臺或者3臺以上的一組電梯作為一個有機整體，使用一個自動控制系統(tǒng)調(diào)度每一臺電梯的運行.當(dāng)前大部分電梯調(diào)度算法，如靜態(tài)或動態(tài)分區(qū)的最小等待時間、目標(biāo)層登記算法等，集中在減少乘客的等待與運行時間上，忽略了系統(tǒng)的耗能［1－2］.節(jié)能方面［3］，當(dāng)前的研究集中于單通道優(yōu)化來減少不必要的能耗，如無傳動牽引和能量反饋技術(shù)，沒有注意減少群控調(diào)度的能耗，實際上，在電梯群系統(tǒng)中，單通道節(jié)能模型中由于對乘客呼叫不合理的調(diào)度降低了節(jié)能的效能，因此研究電梯群控節(jié)能調(diào)度算法是有必要的.

電梯群控是調(diào)度一組多臺電梯服務(wù)于用戶的呼叫，屬于典型的組合優(yōu)化問題.我們采用仿生學(xué)的優(yōu)化算法——蟻群算法來解決這個離散組合優(yōu)化問題，蟻群算法適于解決離散組合優(yōu)化問題［4－5］，其良好的全局優(yōu)化能力與快速收斂能力適于電梯群控調(diào)度，蟻群算法已經(jīng)解決了許多調(diào)度問題，如TSP，車間調(diào)度，無線傳感器網(wǎng)絡(luò)的路由問題［6－8］等.

本文提出一種基于蟻群算法的電梯群調(diào)度算法，首先，以建立能耗目標(biāo)函數(shù)作為優(yōu)化目標(biāo)，建立一個基于圖的搜索機制的蟻群算法控制模型.模型中，每一只螞蟻代表每一臺電梯，每一蟻群代表代表一組電梯，圖中的不同結(jié)點代表從不同樓層乘客的呼叫服務(wù).每一個結(jié)點都會被蟻群遍歷，其次，把最少能耗的調(diào)度策略問題轉(zhuǎn)化為尋找最短路徑動態(tài)的TSP問題，模型約束條件來自于結(jié)點之間能量分配、電梯運行邏輯、電梯選擇概率等，并對算法的收斂性進行了研究，最后的仿真結(jié)果表明了調(diào)度算法的有效性.

1 能量目標(biāo)函數(shù)

以節(jié)能為導(dǎo)向的調(diào)度算法目標(biāo)是盡量減少耗能，首先，以電梯群的能耗為蟻群算法的優(yōu)化目標(biāo)函數(shù).電梯群的能耗由2個部分組成:啟動與停止耗能;勻速運行的耗能.即E=Ea+Ev，這里，E代表整體的能耗，Ea代表加速與減速的能耗，Ev代表勻速的能耗［9］.

其中n代表電梯群的電梯數(shù)量，Ea、Ev是第r臺電梯的啟停和運行的耗能.Ea、Ev按公式(2)、(3)計算.

其中p(r，s)表示第r臺電梯收到的啟停于第s層的請求的數(shù)量，q(r)表示第r臺電梯響應(yīng)呼叫的總數(shù)，并假設(shè)每臺電梯啟停耗能是個常量Ec.

其中nl(r，s，t)表示第r部電梯響應(yīng)從t層到s層請求的乘客總?cè)藬?shù)為乘客的平均質(zhì)量.h(r，s，t)是該電梯從t層到s層的位移.

綜合式(2)、(3)，模型中電梯群控總的能耗目標(biāo)函數(shù)由(4)式計算:

2 蟻群算法調(diào)度策略

蟻群算法能有效解決多節(jié)點(TSP)問題中的最短路徑優(yōu)化難題，電梯群控調(diào)度系統(tǒng)和這些問題很相似，所以非常適合采用蟻群算法來解決.當(dāng)然這里結(jié)點與路徑的涵義被延伸并增加了一些特殊的約束條件.

2.1 蟻群算法模型

設(shè)n臺電梯服務(wù)于m層的建筑物，根據(jù)調(diào)度電梯為各層服務(wù)的原則，蟻群模型將服務(wù)分為2層，向上服務(wù)層和向下服務(wù)層，ant1～antn代表n部電梯，u1～up代表向上服務(wù)的層，而點d1～dq代表向下服務(wù)的層，每一調(diào)度方案就是一個拓?fù)鋱D，螞蟻訪問所有呼叫點，也就是調(diào)度群中的電梯服務(wù)于每個呼叫層，例如，螞蟻1→u1→u2→dq，，就是表示螞蟻 1 按順序完成向上請求u1，u2，再完成向下請求dq，優(yōu)化就是從中找出一條最短路徑，對比用蟻群算法解決的TSP問題，在這個模型中每條路徑的長度的含義已改變了.路徑長度被定義為每種調(diào)度方案的能耗，因此最短路徑代表耗能最少，即最優(yōu)解.

2.2 約束條件

當(dāng)用蟻群算法解決電梯群控問題時，有必要討論模型的約束條件，其主要取決于電梯當(dāng)前的運行狀態(tài)與運行邏輯.將所有的呼叫層分為2個部分:上層呼叫與下層呼叫，節(jié)點的設(shè)置遵循“向上呼叫升序，向下呼叫降序”的原則并依據(jù)呼叫交通流的信號采樣設(shè)置時間間隔.與圖1相對應(yīng)，有u1＜u2＜…＜up，d1＜ d2… ＜ dq.在蟻群優(yōu)化的過程中，蟻群將按 u1，u2，…，uq、dq，…，d2，d1的順序設(shè)置路徑.為簡化算法，采用禁忌表避免多部電梯被調(diào)到同一呼叫層.

2.3 群控調(diào)度優(yōu)化

2.3.1 信息素更新

τij代表信息素，i代表電梯序列號，j代表呼叫節(jié)點的數(shù)目.路徑ij表示第i臺電梯將服務(wù)于第j個節(jié)點，信息素初始值設(shè)置為相同的最小值常量A，設(shè)置最小值的目的是為避免在迭代中丟失優(yōu)化結(jié)果，當(dāng)某些蟻群(電梯群)(ant1～antn)成功找到一條可行性調(diào)度方案，每條經(jīng)過路徑的信息素將按(5)式信息素更新.

其中C是一個常量，ΓK是第K組電梯群的調(diào)度方案總的能耗.

2.3.2 電梯選擇概率

其中allowedk是第k群電梯的可選呼叫節(jié)點集是第i臺電梯服務(wù)于第j層起停呼叫層服務(wù)的能耗，α，β是系數(shù).

2.4 算法流程圖

算法流程如圖1所示.

2.5優(yōu)化機制

蟻群算法是通過迭代尋求優(yōu)化結(jié)果，對于每一組電梯，每一呼叫層由哪臺電梯服務(wù)的機會是由決定，而由 τij和 1/決定.τij不斷更新其值，低能耗可行性路徑上的信息素越來越大.而1/確保對每呼叫層響應(yīng)的電梯最小的能耗，在迭代后，根據(jù)蟻群算法的正反饋機制，就能找到優(yōu)化的低能耗調(diào)度方案.圖1是蟻群控制策略節(jié)能的流程圖，在左邊的圖，算法加載了每個電梯的當(dāng)前情況和呼叫層、結(jié)點集、初始化的信息素，在每次迭代中，將產(chǎn)生一個調(diào)度方案，由公式(5)計算總的Γk，更新信息素.每一個調(diào)度方案的產(chǎn)生都需要右邊的步驟.

在文獻［9］的基礎(chǔ)上，我們對蟻群模型進行了改進，建立了新的上行高峰流和下行高峰流的更為精細(xì)的調(diào)度策略，因為上行高峰流中存在乘客逐漸減少而在下行高峰流乘客逐漸增加的規(guī)律，本文改進的蟻群算法考慮到這個因素，進行了相關(guān)的優(yōu)化設(shè)置.

3 算法的收斂性

蟻群算法的收斂證明［10］如下:

引理 信息素τij有上界τmax=C/(Γmin·ρ).

證明 假設(shè)信息素的初始值為τ0，一次迭代后，其最大的增量是c/Γmin，因此最大的信息素是(1－ρ)τ0+c/Γmin，第2次迭代后，信息素的值為(1 －ρ)2τ0+(1 － ρ)τ0+c/Γmin，按此計算，由于信息素的揮發(fā)，經(jīng)過θ次迭代，信息素將會變小或者等于:

因為0 ＜ρ≤1，τmax收斂于 C/(Γmin·ρ).

定理 p*(θ)表示經(jīng)過θ次迭代至少找到一條優(yōu)化方案的概率，當(dāng)給一個足夠大的θ，有公式

證明 由于信息素是介于τmax和τmin之間，令η=1/，因此η有1個上界和下界.電梯選擇概率最小值為

其中D是某一時刻可供選擇的呼叫層的數(shù)量，任意的調(diào)度方案包括最優(yōu)方案，可以以一定的概率得到，這里n代表呼叫的數(shù)量，因此只要一個螞蟻找到優(yōu)化方案就得到最優(yōu)解.對于p*(θ)的下界是由公式(θ)=1－(1－)θ推導(dǎo)得到，只要θ充分大，概率值可能大于1－ε(ε＞0是個任意小的量)，所以有

以上的結(jié)果表明本文算法能以概率1得到低能耗的調(diào)度方案.

4 試驗仿真

為了驗證算法的有效性，仿真是在虛擬電梯的環(huán)境下完成的，表1給出了各參量的數(shù)值.能量目標(biāo)初始參量(由OTIS電梯提供):啟停耗能22.5 kJ，箱體800 kg，平衡錘900 kg，乘客平均65 kg.仿真對于3種60 min的上行高峰流，任意間層交通流，下行高峰流交通流，與靜態(tài)調(diào)度算法、最小等待時間調(diào)度算法以及文獻［9］的算法進行性能比較.本文改進算法中，蟻群算法的參數(shù)值是 α=1，β=5，ρ=0.99，迭代次數(shù)200，等待時間的極限值為60 s，模擬的結(jié)果如表2.

結(jié)果表明蟻群算法與其它3種算法相比，在3種交通流的情況下，本文提出的改進蟻群算法能有效地減少能耗，特別是在上行與下行的高峰期.然而在任意層間模式中，效果不明顯，另外算法為了追求低能耗犧牲了一些等待時間，例如在高峰期的等待時間有點長，但還是在可接受的范圍內(nèi)，這也是設(shè)置閾值的原因，目的是在沒有太多時間損耗的情況下盡可能減少能耗.

表1 仿真電梯參量值說明

表2 仿真試驗結(jié)果

5 結(jié)語

采用蟻群算法解決電梯群控制的節(jié)能問題，首先建立能量目標(biāo)函數(shù)，其次提出以節(jié)能為導(dǎo)向的蟻群算法，建立蟻群電梯模型，提出基于信息素和選擇概率函數(shù)的收斂優(yōu)化機制.仿真結(jié)果表明，和已有的電梯群控算法相比，基于蟻群的算法在電梯群控中能有效地減少能耗.

［1］TAI J Z，YANG S Y，TAN H.Dispatching approach optimization of elevator group control system with destination floor guidance usingfuzzy neural network［C］//Proceeding of 8th World Congress on Intelligent Control and Automation(WCICA 2008).IEEE，2008:7085－7088.

［2］BARNEY G，SANTOS S D.Elevator traffic analysis，design and control［M］.Stevenage，U.K:Peregrinus，1985.

［3］LEE S，BAHN H.An energy－aware elevator group control system［C］//Proceeding in 3rd IEEE International Conference on Industrial Informatics.IEEE，2005:639 －643.

［4］DORIGO M，CARO G D，GAMBARDELLA L M.Ant algorithms for discrete optimization［J］.Artificial Life，1999，5(2):137 －172.

［5］YAGMAHAN B，YENISEY M M.A multi－objective ant colony system algorithm for flow shop scheduling problem［J］.Expert Systems with Applications，2010，37(2):1361 －1368.

［6］PURIS A，BELLO R，HERRERA F.Analysis of the efficacy of a Two－Stage methodology for ant colony optimization:Case of study with TSP and QAP［J］.Expert Systems with Applications，2010，37(7):5443 －5453.

［7］DHURANDHER S K，MISRA S，OBAIDAT M S，et al.An ant colony optimization approach for reputation and quality－of－service－based security in wireless sensor networks［J］.Security and Communication Networks，2009，2(2):215 －224.

［8］KADONO D，IZUMI T，OSHITA F.An ant colony optimization routing based on robustness for ad hoc networks with GPSs［J］.AD HOC Networks，2010，8(1):63 －76.

［9］ZHANG J L，TANG J，ZONG Q，LI J F.Energy－ saving scheduling strategy for elevator group control system based on ant colony optimization［C］//Proceedings of 2nd IEEE Youth Conference on Information，Computer and Telecommunications.IEEE，2010:37 －40.

［10］STUTZLE T，DORIGO M.A short convergence proof for a class of ant colony optimization algorithm［J］.IEEE Transactions on Evolutionary Computation，2012，6(2):358 －365.