基于魚群算法的電梯群控調度算法*

王瀚韜，李 強*，鄭永康

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

0 引 言

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

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

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

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

1 魚群算法

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

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

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

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

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

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

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

2.1 人工魚狀態AF_init

步行訓練過程中每條人工魚的狀態描述運用一個二維數組x［2］［2M －1］表示，其中 M 為樓層數。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 表示參與群控電梯數，x［1］［i］=j表示第i個外部召喚由j號電梯響應(注:樓層數為16，第1層無下行召喚，第16層無上行召喚，x［0］［0］，x［1］［0］舍棄不用)。

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

該數組表示的含義為:

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

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

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

(4)4號電梯空閑。

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

2.2 食物濃度的計算AF_foodconsistence

該算法以平均候梯時間、平均乘梯時間以及平均能耗作為電梯調度的主控指標。目標函數［10］為:

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

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

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

2.3 人工魚的行為設計

2.3.1 感知能力設計AF_visual

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

2.3.2 覓食行為AF_prey

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

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

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

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

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

2.3.3 聚群行為AF_swarm

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

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

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

2.3.4 追尾行為AF_follow

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

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

2.4 電梯轎廂內人數

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

2.5 參數分析

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

表1 參數取值

3 仿真測試

本研究借助于Visual C++強大的運算處理能力進行最優解的搜索，實現了電梯群控調度的魚群算法，并在電梯群控虛擬仿真環境下，按如下參數設計進行仿真比較:

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

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

(2)交通流數據。

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

(3)選取的調度算法:

算法1:魚群算法;

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

圖1 平均候梯時間的仿真結果

圖2 平均乘梯時間的仿真結果

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

表2 2種算法調度性能指標比較

4 結束語

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

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

［1］李向莉.基于模糊神經網絡的電梯群控系統調度方法研究［D］.蘇州:蘇州大學計算機學院，2006:1-2.

［2］楊廣全.電梯交通流分析及電梯群控策略研究［D］.上海:上海交通大學機械與動力工程學院，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］鄭延軍，張惠僑.電梯動態分區算法及遺傳進化研究［J］.計算工程與應用，2001，22(3):142-148.

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

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

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

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

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

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

［11］劉彥君.魚群算法及在無線傳感器網絡覆蓋優化中的應用［D］.濟南:山東大學通信學院，2009:11-16.