王瀚韜，李 強(qiáng)*，鄭永康

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

0 引 言

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

近年來，國內(nèi)外提出了不少用于解決電梯群的調(diào)度算法，一般考慮電梯所在樓層、運(yùn)行方向、內(nèi)外召信號(hào)作為調(diào)度的因素，很少考慮電梯轎廂內(nèi)人數(shù)的因素，文獻(xiàn)［2］提到了這一因素，但未提及如何運(yùn)用到電梯群控算法中。考慮電梯轎廂內(nèi)人數(shù)的群控算法，可以縮小解的空間，從而在有限的時(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)練時(shí)間長，易陷入局部極小;遺傳算法對(duì)新空間的探索能力有限，容易收斂到局部最優(yōu)解;模糊規(guī)則比較難于建立。文獻(xiàn)［6］表明，魚群算法用于組合優(yōu)化問題具有較快的收斂速度，可以用于解決由實(shí)時(shí)性要求的問題，對(duì)于一些精度要求不高的場(chǎng)合，可以用它快速地得到一個(gè)可行解。

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

1 魚群算法

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

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

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

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

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

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

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

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

步行訓(xùn)練過程中每條人工魚的狀態(tài)描述運(yùn)用一個(gè)二維數(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個(gè)外部召喚由j號(hào)電梯響應(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號(hào)電梯響應(yīng)第5、8、9層的上行召喚，同時(shí)響應(yīng)第6、8層的下行召喚;

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

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

(4)4號(hào)電梯空閑。

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

2.2 食物濃度的計(jì)算AF_foodconsistence

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

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

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

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

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

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

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

2.3.2 覓食行為AF_prey

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

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

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

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

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

2.3.3 聚群行為AF_swarm

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

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

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

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的位置前進(jìn)一步;否則執(zhí)行覓食行為。

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

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

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

2.5 參數(shù)分析

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

表1 參數(shù)取值

3 仿真測(cè)試

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

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

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

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

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

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

算法1:魚群算法;

算法2:最小等待時(shí)間算法。

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

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

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

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

4 結(jié)束語

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

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

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

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

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

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

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

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

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

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

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