基于鱼群算法的电梯群控调度算法*

王瀚韬，李 强*，郑永康

(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.