基于魚群算法的電梯群控調(diào)度算法*

王瀚韜，李 強*，鄭永康

(1.杭州電子科技大學(xué)智能與軟件技術(shù)研究所，浙江杭州310037;2.杭州優(yōu)邁科技有限公司，浙江杭州310052)

0 引 言

電梯群控是指將3臺或3臺以上的電梯作為一個群體進行系統(tǒng)管理的控制系統(tǒng)［1］，目的是更加有效地調(diào)度電梯來滿足交通要求，是目前電梯節(jié)能的主要手段。對電梯群控系統(tǒng)性能評價的主要指標(biāo)包括乘客的平均等待時間、長時間候梯率、能源消耗、乘客乘梯時間和輸送能力等。這是一個多目標(biāo)優(yōu)化問題，有多目標(biāo)優(yōu)化固有的困難，即各目標(biāo)間可能相互矛盾。

近年來，國內(nèi)外提出了不少用于解決電梯群的調(diào)度算法，一般考慮電梯所在樓層、運行方向、內(nèi)外召信號作為調(diào)度的因素，很少考慮電梯轎廂內(nèi)人數(shù)的因素，文獻［2］提到了這一因素，但未提及如何運用到電梯群控算法中。考慮電梯轎廂內(nèi)人數(shù)的群控算法，可以縮小解的空間，從而在有限的時間內(nèi)，找到更優(yōu)解，讓電梯調(diào)度更加合理。

基于神經(jīng)網(wǎng)絡(luò)［3］、遺傳算法［4］、模糊控制［5］等智能調(diào)度算法，比傳統(tǒng)的調(diào)度算法更具有效性，但它們本身具有局限性，神經(jīng)網(wǎng)絡(luò)需要大量輸入-輸出數(shù)據(jù)，訓(xùn)練時間長，易陷入局部極小;遺傳算法對新空間的探索能力有限，容易收斂到局部最優(yōu)解;模糊規(guī)則比較難于建立。文獻［6］表明，魚群算法用于組合優(yōu)化問題具有較快的收斂速度，可以用于解決由實時性要求的問題，對于一些精度要求不高的場合，可以用它快速地得到一個可行解。

目前，魚群算法尚未在電梯群控這一領(lǐng)域中運用。因此，本研究對考慮轎廂內(nèi)人數(shù)因素的魚群算法進行探索性的研究。

1 魚群算法

人工魚群算法模擬自然界中魚的集群游弋覓食行為，通過魚之間的集體協(xié)作使群體達到最優(yōu)選擇的目的［7］。它采用自下而上的設(shè)計方法，對尋優(yōu)空間的形式和性質(zhì)沒有特殊要求。這種方法原則上是一種基于比較目標(biāo)函數(shù)值的搜索方法，不需要利用導(dǎo)數(shù)信息，因而具有較好的全局尋優(yōu)能力，且尋優(yōu)速度較快。魚的經(jīng)典行為如下［8］:

(1)魚的覓食行為:平時人們會看到魚兒在水中自由地游來游去，這一般可視為一種隨機移動，當(dāng)發(fā)現(xiàn)食物時，會向著食物逐漸增多的方向快速游去。

(2)魚的聚群行為:魚在游動過程中會自然的聚集成群，這也是為了保證群體的生存和躲避危害而形成的一種生活習(xí)性。

(3)魚的追尾行為:在魚群的游動過程中，當(dāng)其中一條或幾條發(fā)現(xiàn)食物時，其臨近的伙伴會尾隨其快速到達食物點。

魚群算法原理如下［9］:

2 基于魚群算法的群控算法

群控系統(tǒng)管理N部電梯，有p個呼梯信號，則有NP種派梯方案。魚群算法的功能就是在有限的時間內(nèi)，找出相對最優(yōu)的一種派梯方案。在建立人工魚群算法模型時，需要充分考慮該電梯運行的實際情況，采用合適的人工魚設(shè)計方法。包括如何描述人工魚的狀態(tài)，即對該問題變量的設(shè)計，以及如何修復(fù)魚的狀態(tài)使之符合問題的約束條件和人工魚的尋優(yōu)策略，即對覓食行為、聚群行為、追尾行為、隨機行為這4種基本行為的設(shè)計以及人工魚之間距離的計算方法參數(shù)的取值等問題進行討論。

2.1 人工魚狀態(tài)AF_init

步行訓(xùn)練過程中每條人工魚的狀態(tài)描述運用一個二維數(shù)組x［2］［2M －1］表示，其中 M 為樓層數(shù)。x［0］［1，2..i..M －1］，i表示第 i層的上行召喚。x［0］［M，M+1，..i..2M －2］，i表示第 i－ M+2 層的下行召喚。x［0］［i］的取值范圍為1或0，1表示該樓層有外部召喚，0 表示無召喚，x［1］［i］的取值范圍［0，N］，0 表示不派梯，N 表示參與群控電梯數(shù)，x［1］［i］=j表示第i個外部召喚由j號電梯響應(yīng)(注:樓層數(shù)為16，第1層無下行召喚，第16層無上行召喚，x［0］［0］，x［1］［0］舍棄不用)。

例如，數(shù)組 x［2］［2M －1］(設(shè) M=16，N=4，當(dāng)前外部上行召喚有 5、8、9 層，外部下行召喚有 2、6、8、15、16 層)為:

該數(shù)組表示的含義為:

(1)1號電梯響應(yīng)第5、8、9層的上行召喚，同時響應(yīng)第6、8層的下行召喚;

(2)2號電梯響應(yīng)第2層的下行召喚;

(3)3號電梯響應(yīng)第15、16層的下行召喚;

(4)4號電梯空閑。

本研究對每條魚的初始化采用如下策略:依次給x［0］［i］=1 的 x［1］［i］賦值，其值為在［1，N］之間隨機產(chǎn)生一個整數(shù)j。

2.2 食物濃度的計算AF_foodconsistence

該算法以平均候梯時間、平均乘梯時間以及平均能耗作為電梯調(diào)度的主控指標(biāo)。目標(biāo)函數(shù)［10］為:

式中:AWT—平均等待時間;AJT—平均乘梯時間;EW—電梯能耗;ω1，ω2，ω3—AWT，AJT，EW 的加權(quán)系數(shù)。

ω1+ω2+ω3=1，該系數(shù)由不同的交通模式確定。

例如，在隨機層間在隨機層間交通模式下，希望顧客的候梯時間和乘梯時間小一些，則ω1，ω2應(yīng)該偏大一些。問題到此就由求解min(AWT，AJT，EW)轉(zhuǎn)化為求解min(Fk)。

2.3 人工魚的行為設(shè)計

2.3.1 感知能力設(shè)計AF_visual

對于距離計算問題，本研究采取計算2個變量數(shù)組取值的相似度的策略。對于任意的2個變量數(shù)組，將數(shù)組中每個x［1］［i］存儲的值進行比較，如果兩者不相等，則取值為2，否則為0，將所有位置比較后的值相加就是2條魚之間的距離d的取值。從變量意義的描述中可以看出，變量中存儲的每個數(shù)值都不具有數(shù)值的真正涵義，它們都只是一個符號，因此，如果采用通常的加減方法或是求解空間距離長度的方法都不太合適，因為這樣得出的距離值對問題的解決無實際意義，而且會干擾和扭曲人工魚的視覺判斷。采用上述的距離計算方法簡單易行，它是以方案的總體視角來考慮問題的，即比較2個方案，計算它們的相似程度，取值越大就表明兩種方案相似程度越小，當(dāng)它大于所給的閾值visual時，就認(rèn)為這2條魚對對方都是不可見的。對于有9個外部召喚的2條人工魚的距離運算中，最壞的情況是配送方案完全的不相似，這時它們之間的距離就為18。

2.3.2 覓食行為AF_prey

從電梯群控調(diào)度問題可以看出，每組x［1］［2M－1］都是一種可行的方案，它的解集空間不是連續(xù)的，而是很多離散的點，而且變量中每個分量的取值都不具有數(shù)值含義，因此，步長的設(shè)計對于該問題的意義就不大。如果強硬地設(shè)置出步長并讓人工魚按照步長行動，會造成取值的混亂。

基于上述問題的考慮，本研究對于每條魚的行動采取讓魚直接跳向更優(yōu)狀態(tài)的策略，這樣不僅簡單易行，而且收斂效果也很好。

設(shè)人工魚當(dāng)前狀態(tài)為Xi，在其視野范圍內(nèi)隨機選擇一個狀態(tài) Xj，如果 Yi＞Yj，則令 Xi=Xj;反之，再重新隨機選擇狀態(tài)Xj，判斷是否滿足前進條件;試探trynumber次后，如果仍不滿足前進條件，則執(zhí)行隨機移動行為［11］。

Xj=Random(N(Xi，Visual))表示在［Btnum －Visual/2，Btnum］(Btnum表示當(dāng)前需響應(yīng)的外部召喚個數(shù))之間隨機產(chǎn)生一個整數(shù) j，在 x［0］［i］=1 的 x［1］［i］中，選取 j個點插入與 Xi相同的位置，其余 x［0］［i］=1，x［1］［i］的位置隨機選擇分配。

覓食行為偽代碼描述如下:

2.3.3 聚群行為AF_swarm

設(shè)人工魚當(dāng)前狀態(tài)為Xi，探索其鄰域的伙伴數(shù)目nf，如果 nf/N ＜ δ，(0 ＜ δ＜1)，則表明伙伴中心有較多的食物并且不太擁擠，如果此時Yi＞Yc，則人工魚向中心位置前進一步;否則執(zhí)行其覓食行為。

聚群行為偽代碼描述如下:

Center(N(Xi，Visual))表示中心位置，首先，統(tǒng)計每個 x［1］［i］位置上0～4出現(xiàn)的次數(shù)，其次，將出現(xiàn)次數(shù)最多的數(shù)字填入Xj，這樣，賦值就盡量的找到了伙伴的共同點。

2.3.4 追尾行為AF_follow

設(shè)人工魚當(dāng)前狀態(tài)為Xi，探索其鄰域內(nèi)狀態(tài)最優(yōu)的鄰居Xmin，如果Yi＞Ymin，并且Xmin的鄰域內(nèi)伙伴的數(shù)目滿足nf/N＜δ，(0＜δ＜1)，表明Xmin附近有較多的食物并且不太擁擠，則向Xmin的位置前進一步;否則執(zhí)行覓食行為。

追尾行為偽代碼描述如下:

2.4 電梯轎廂內(nèi)人數(shù)

人工魚根據(jù)以上的覓食行為、聚群行為和追尾行為進行全局尋優(yōu)，當(dāng)人工魚向某一方向游動時，考慮各臺電梯轎廂的人數(shù)和已有的內(nèi)部召喚，可以使算法跳過一些不合理的解，從而搜索到更優(yōu)的解。例如，第7層有外部上行召喚，1號電梯所在樓層為第5層，方向為上行，最近的內(nèi)部召喚為第9層，當(dāng)前轎廂內(nèi)人數(shù)已到達額定人數(shù)18;2號電梯所在樓層為第3層，方向為上行，最近的內(nèi)部召喚為第10層，當(dāng)前轎廂內(nèi)人數(shù)為7，未達到額定人數(shù)18;3、4號電梯都停在第1層。根據(jù)最小等待時間，就近原則，如不考慮電梯轎廂人數(shù)，將派1號電梯響應(yīng)第7樓的外部上行召喚，但考慮轎廂人數(shù)之后，則派2號電梯響應(yīng)該樓層外部上行召喚。

2.5 參數(shù)分析

離散魚群算法的參數(shù)設(shè)定尚無嚴(yán)格的理論依據(jù)，還沒有確定最優(yōu)參數(shù)的一般方法。對于離散魚群算法的參數(shù) trynumber、visual、number、maxgen 等重要參數(shù)，解析法難以確定其最佳選擇。擬先使用“保持其他參數(shù)不變而改變其中某一個參數(shù)”的辦法來考察每一個參數(shù)對于算法性能的影響。對于樓層數(shù)為16，有4臺電梯的大樓，8個及以下外部召喚，可采用窮舉法處理，即可在600 ms內(nèi)找到最優(yōu)解，當(dāng)大于8個外部召喚時，窮舉法計算的時間成指數(shù)增加，這時調(diào)用魚群算法處理。由于電梯外部召喚的多態(tài)性、實時性，9個外部召喚與16個外部召喚的復(fù)雜度不同，相應(yīng)離散魚群算法的參數(shù) trynumber、visual、number、maxgen 也會不同，本研究給出針對9～30個不同外部召喚調(diào)整好后的參數(shù)，參數(shù)取值如表1所示。

表1 參數(shù)取值

3 仿真測試

本研究借助于Visual C++強大的運算處理能力進行最優(yōu)解的搜索，實現(xiàn)了電梯群控調(diào)度的魚群算法，并在電梯群控虛擬仿真環(huán)境下，按如下參數(shù)設(shè)計進行仿真比較:

(1)建筑物及電梯配置參數(shù)。

建筑物層數(shù)為16層，樓層高度為4 m，電梯數(shù)為4臺，電梯額定載客量為18人。額定速度為3 m/s，加速度為1 m/s2，加加速度率為2 m/s3，開門時間為2 s，關(guān)門時間為1 s，保持時間2 s。

(2)交通流數(shù)據(jù)。

上行高峰(8:30～9:30，總1 000人/次)。

(3)選取的調(diào)度算法:

算法1:魚群算法;

算法2:最小等待時間算法。

圖1 平均候梯時間的仿真結(jié)果

圖2 平均乘梯時間的仿真結(jié)果

仿真結(jié)果如圖1～3所示，2種算法性能對比結(jié)果如表2所示。分析得，魚群算法相比最小等待時間的平均候梯、平均乘梯時間、長候梯率分別減少7.35%、16.71%、30%，但電梯能耗增加4.7%。可見魚群算法的有效性。

表2 2種算法調(diào)度性能指標(biāo)比較

4 結(jié)束語

筆者研究了魚群算法在電梯群控調(diào)度中的應(yīng)用。魚群算法理論從仿生學(xué)的角度來解決電梯群控調(diào)度問題，通過對電梯群控調(diào)度系統(tǒng)的深入分析，結(jié)合人工魚群算法模型的核心思想，建立了電梯群控調(diào)度的人工魚群算法模型，然后利用電梯群控虛擬仿真環(huán)境實現(xiàn)了魚群算法，進行了仿真驗證。仿真過程中，通過與其他調(diào)度算法的比較，證明了魚群算法的優(yōu)良性能和較強的適應(yīng)能力。

人工魚群算法的思想簡單，易于實現(xiàn)，但是應(yīng)用于實際問題中時，有很多與算法相關(guān)的要素要結(jié)合問題的實際情況進行靈活地修改。如，離召喚樓層近的電梯應(yīng)優(yōu)先考慮;客流高峰期間，電梯轎廂內(nèi)的人數(shù)常常會滿員，因此，針對這些特殊問題進行優(yōu)化，從而達到縮小解空間的目的。今后會在目前的算法基礎(chǔ)上，根據(jù)這些實際條件對算法設(shè)計進行補充和調(diào)整，使人工魚群算法在求解電梯調(diào)度算法上既實用又能豐富電梯群控求解算法。

［1］李向莉.基于模糊神經(jīng)網(wǎng)絡(luò)的電梯群控系統(tǒng)調(diào)度方法研究［D］.蘇州:蘇州大學(xué)計算機學(xué)院，2006:1-2.

［2］楊廣全.電梯交通流分析及電梯群控策略研究［D］.上海:上海交通大學(xué)機械與動力工程學(xué)院，2008:15-16.

［3］ERDEM I C.Artificial neural networks application in duplex/triplex elevator group control system［J］.Journal of Mechanical Engineering，2008，54(2):103-114.

［4］鄭延軍，張惠僑.電梯動態(tài)分區(qū)算法及遺傳進化研究［J］.計算工程與應(yīng)用，2001，22(3):142-148.

［5］張 昆，段其昌，張從力.基于模糊控制的多目標(biāo)電梯群控技術(shù)［J］.儀器儀表學(xué)報，2004，25(4):248-251.

［6］李曉磊，路 飛，田國會，等.組合優(yōu)化問題的人工魚群算法應(yīng)用［J］.山東大學(xué)學(xué)報:工學(xué)版，2004，34(5):64-67.

［7］黃光球，劉嘉飛.人工魚群算法的全局收斂性證明［J］.計算機工程，2012，38(2):204-206.

［8］李曉磊，錢積新.人工魚群算法:自下而上的尋優(yōu)模式［C］.過程系統(tǒng)工程年會論文，2001:76-82.

［9］李曉磊.一種新型的智能優(yōu)化方法-人工魚群算法［D］.杭州:浙江大學(xué)控制科學(xué)與工程學(xué)學(xué)院，2003:23-51.

［10］秦 臻.基于SVM的電梯群控系統(tǒng)(EGCS)算法的研究［D］.杭州:杭州電子科技大學(xué)計算機學(xué)院，2011:34-35.

［11］劉彥君.魚群算法及在無線傳感器網(wǎng)絡(luò)覆蓋優(yōu)化中的應(yīng)用［D］.濟南:山東大學(xué)通信學(xué)院，2009:11-16.