基于ABC-SA混合算法的群控电梯优化调度

闫秀英，郭普静，范凯兴

(1.西安建筑科技大学 建筑设备科学与工程学院，西安 710055;2.西安建筑科技大学 建筑学院，西安 710055)

0 引言

随着城镇化进程的加快，电梯和电梯组的发展伴随高层智能建筑的不断发展而逐渐增加。电梯群控系统(elevator elevator group control system，EGCS)是根据建筑物内的交通流状况，合理地分配多部电梯，根据管理目标、服务质量、服务数量及能量消耗的要求，电梯群控制器能合理、优化调度多部电梯以满足服务目标要求[1]。建筑物中一组电梯的调度本质上是资源合理分配的组合优化。对于EGCS而言，寻找一种高效的调度优化算法能够根据当前状态决定调度某台电梯响应某层呼梯信号至关重要。

以往群控电梯调度的研究主要集中在遗传算法、模糊控制、神经网络、最小等待时间法和专家系统等方法上。Beamurgia等人将遗传算法应用于电梯调度问题，分析乘客的等待时间，电梯性能得到了改善但遗传算法在搜索函数最优解时会花费较长时间[2]，王志华设计了基于模糊控制的群控电梯系统，但模糊控制缺少学习能力，难以实时调整模糊隶属度函数[3]，神经网络应用于电梯群控系统时训练时间过长并且参数不易选择[4]，专家系统不适合复杂多变的电梯系统，控制规则有限，适用于楼层较低的建筑物，最小等待时间法仅考虑了电梯的时间性能而忽略了现如今比较关注的其他能耗性能[5]。在节能时代，较好的EGCS应能满足不同交通模式下的乘客需求，尤其是高峰交通模式。电梯群调度最大化节省时间的同时也应更加关注电梯节能调度，最大化地减少电梯群控系统的能耗并使时间性能保持在可接受范围内。本文提出综合考虑乘客乘梯及侯梯时间、减少系统能耗的优化思想进行群控电梯多目标优化。

在求解优化问题上，人工蜂群(artificial bee colony，ABC)算法具有参数设置简单、易于实现的特点[6-7]。李彦苍等人设计了引用信息熵的改进人工蜂群算法求解组合优化问题[8]，郎曼等人提出了采用人工蜂群算法对电梯群控进行节能优化[9]，王志刚等人应用ABC算法求解车辆路径规划问题[10]。人工蜂群算法尽管具有鲁棒性强、计算简单等优点，但仍存在收敛速度慢、易早熟等缺陷。

基于此，研究电梯群控优化调度时在基本人工蜂群的基础上引入模拟退火(simulated annealing，SA)机制，以改善蜂群算法在迭代后期易于陷入局部最优而得到假象最优解的缺点，从而改善求解质量。并充分考虑影响电梯群控质量的关键因素，结合多目标优化思想建立多目标评价函数，利用ABC-SA混合算法对该目标函数进行求解，以得到更好的求解质量响应派梯策略，在节省乘客使用时间的同时节约系统能耗。

1 群控电梯多目标数学模型

1.1 优化目标

根据EGCS的随机性，非线性特征以及乘客心理和生理上的需求，本文综合考虑动态性能指标平均乘梯时间ART，平均侯梯时间AWT和系统运行能耗ANT，以实现电梯群调度的多目标优化。

1.1.1 乘梯时间评价函数

乘梯时间为tr电梯输送乘客运行时间 和电梯在此过程中停靠时间ts之和，电梯停靠时间由乘客进出门时间tpa和电梯开关门时间toc组成。N为电梯内乘客总人数，RT(i,j) 为第i部电梯运行到第j层时电梯内乘客的乘梯时间，st为电梯群总台数，sc为楼层数。平均乘梯时间ART如式(3)所示：

RT(i,j)=tr+ts

(1)

ts=toc+tpa

(2)

(3)

当正在输送乘客时，期待随着乘梯时间的增多，评价函数可信度降低，也就是评价值越高时，说明某一时刻电梯组时间性能良好，建立乘梯时间评价函数如式(4)所示。调度优化时希望所用时间越少越好，即随着乘客乘梯时间的增长，乘梯时间评价函数逐渐减少并接近于0。

(4)

设乘梯时间为110 s时，此时乘梯时间评价函数值为0.000 1，则可根据乘梯时间函数求解评价函数的相关参数，即乘梯时间评价函数fr如下所示：

fr=e-0.00076RT2(i,j)

(5)

将公式(5)每20 s记录一次fr评价函数值，由表1得出随着乘梯时间RT(i,j)的增加乘梯时间评价函数fr逐渐减小。

表1 乘梯时间函数评价表

1.1.2 侯梯时间评价函数

侯梯时间定义为呼梯信号响应开始到电梯到达召唤层所用时间。侯梯时间评价函数与乘梯时间评价函数类似，不做具体说明。WT(i,j)为第i部电梯运行到第j层响应外呼信号所用的时间，候梯时间评价函数fw表达式如式(6)：

fw=e-0.0025WT2(i,j)

(6)

1.1.3 系统能耗评价函数

电梯系统的能耗包括启停能耗和运行时的能耗。一般来说启停能耗都要大于运行能耗，因此可通过减少电梯停靠次数来降低能耗。第i部电梯停靠次数记作n(i) ，系统能耗评价函数fn表达式为：

fn=e0.016n2(i)

(7)

1.2 建立多目标数学模型

电梯群控系统的优化属于柔性多目标优化问题，能够协调目标以使所有目标功能尽可能最佳地解决此类问题的关键。电梯群调度采用群智能多目标优化算法，综合3个评价标准，采用加权组合法对3个指标进行加权求和，数学表达式如下：

F(x)=W1fw+W2fr+W3fn

(8)

式中,F(x)为多目标评价函数，评价函数值越大，评价派梯的可信度越高。fw、fr、fn分别为候梯时间评价函数、乘梯时间评价函数、系统能耗评价函数；W1、W2、W3为评价函数fw、fr、fn对应的系数权重，其中：

(9)

Wi体现了在不同交通模式下各评价指标的侧重。当前电梯为上行或下行客流高峰时以减少乘客候梯时间和乘梯时间为主要目标，因此考虑适当增大fw、fr的权重系数W1、W2；同理电梯运行在层间或空闲交通模式下时以减少系统能耗为主，因此可增大fn的权重系数W3。

2 基于ABC-SA算法的电梯群控系统

2.1 ABC算法及SA算法的思想

人工蜂群(ABC)算法是一种模拟群体蜜蜂觅食特性的智能优化算法，该算法是土耳其学者Karaboga于2005年提出，通过模拟蜜蜂采蜜觅食的行为而寻找优化问题的解[11-13]。算法包括食物源(蜜源)、雇佣蜂(引领蜂)、跟随蜂和侦查蜂4种基本要素。使用ABC算法进行电梯优化调度时，蜜源对应于群控电梯优化问题的一个可行解，其收益率即适应度值代表解的质量。每个雇佣蜂对应一个确定的蜜源也就是解向量，在不断迭代过程中对蜜源的邻域进行搜索。

基本ABC算法在搜索开始阶段，引领蜂根据式(10)搜索新蜜源：

vij=xij+φij(xij-xkj)

(10)

式中，j∈{1,2,…，D}，D为待优化问题参数维度，i∈{1,2，…，SN}，k∈{1,2，…，SN}，SN为种群规模，φij为[-1,1]之间的随机数。

引领蜂在完成搜索后，会回到蜂巢进行资源分享，采用摇摆舞的方式将信息传递给跟随蜂，跟随蜂对蜜源的选择概率根据式(11)使用轮盘赌的方式进行，其中fit1为第i个蜜源的收益率，蜜源越丰富，被跟随蜂选择的概率越大。

(11)

(12)

模拟退火(SA)算法不仅是一种启发式随机搜索方法，而且还是一种有效的全局优化算法，它的凝结源于固态物理退火过程，是由Kirknatrick于1983年提出并首次应用于组合优化问题[14-15]。SA算法采用Metropolis验收准则，该算法在搜索策略过程中可以避免陷入局部最优，其原因是在模拟退火的优化过程中，较好地解决方案被完全接受，较差的解决方案也以一定的接受概率被接受，增加了算法的多样性。

SA算法中退火温度T决定蜜蜂接受低收益率食物源的概率，温度T越高则蜜蜂接受低收益率食物源的概率越大，温度T越低则蜜蜂接受低收益率食物源的概率越小，因此算法初期温度T应该较大使得算法趋于全局搜索，迭代后期温度T越小使算法越趋于局部重点搜索，加快算法收敛速度。因此，温度下降函数 选取如式(13)所示：

T(t+1)=λT(t)

(13)

式中,λ为退火系数，一般取值范围为[0.9，1)。

2.2 基于ABC-SA算法的电梯群控系统派梯策略

基本ABC算法中侦察蜂的功能是保证算法跳出局部最优，收敛到全局最优，但对复杂的优化问题进行求解时算法往往很难收敛到全局最优。引领蜂和侦查蜂在进行邻域搜索后利用贪婪选择策略进行蜜源选择，对初期适应度值较差的蜜源缺乏关注，提前将有潜力的蜜源淘汰，寻优过度依赖算法优化前后蜜源好坏，忽略拥有巨大潜力的蜜源。为进一步挖掘潜力蜜源，避免ABC算法求解多目标问题时陷入局部最优解，从算法选择机制角度出发，引入模拟退火扩大选择机制，提出一种混合ABC-SA算法来解决EGCS优化调度问题。所提ABC-SA混合算法是一种结合人工蜂群算法的快速计算优势以及模拟退火利用高温状态下粒子的高速无序性，有效避免陷入局部最优解的方法以提高全局搜索能力。混合算法可以拓宽解的搜索方向，加强算法的全局搜索能力，并且根据模拟退火的特性，初始温度在较高的情况下，算法容易接受恶化解，从而能够跳出局部最优解，减少算法对初始解的依赖。而通过缓慢地降低温度T，当T趋于零时不再接受恶化解，逼近全局最优解，此过程对整体算法后期求解更加有益。

模拟退火的选择策略如式(14)所示，fit(xi)、fit(xj)为原始蜜源的适应度和邻域搜索后新蜜源的适应度。若fit(xj)>fit(xi)，则接受新蜜源；若fit(xj)⦤fit(xi)，则以概率计算公式接受新蜜源。模拟退火的选择策略在一定程度上保留了原有算法贪婪选择策略的择优选择思想，同时也以一定的概率接受有潜力的蜜源，在一定程度上增强了基本ABC算法跳出局部最优的能力。

(14)

在群控电梯优化调度中，根据某一时刻每台电梯当前所在状态楼层、电梯内信息、呼梯信号信息、侯梯人数等数据对1.2节所建目标函数进行优化，优化过程是寻找评估函数极值的过程。基于ABC-SA混合算法的EGCS调度流程如图1所示。

图1 基于ABC-SA算法的EGCS调度流程图

Step1：初始化算法参数，如种群规模SN、蜜源限制开采次数limit、最大迭代次数Maxcycle、模拟退火的初始温度T等；

Step2：蜜源初始化并计算其适应度值；

Step3：雇佣蜂(引领蜂)阶段。按照式(10)进行邻域搜索寻找新食物源并计算适应度值；

Step4：进行模拟退火操作。当引领蜂进行邻域搜索后，利用贪婪选择策略进行蜜源选择，尽管可以较快地找到局部最优的蜜源，但会失去当前适应度不高且更接近于全局最优的蜜源。利用模拟退火的选择概率，比较原始食物源和新食物源的适应度，若新食物源适应度大于原始蜜源的适应度，则接受该食物源，否则以式(14)求出的概率接受新食物源。

Step5：跟随蜂阶段。根据式(11)计算食物源的概率，依照概率选择食物源；

Step6：判断是否有要放弃的蜜源，若有侦查蜂产生，则放弃原蜜源按照式(12)寻找新蜜源并标记；若没有侦查蜂，更新最优蜜源，记录当目前为止最优解；

Step7：判断是否达到循环终止条件，若满足循环结束，输出最优蜜源，否则返回Step3继续搜索。

2.3 模型约束

利用混合模拟退火改进人工蜂群算法解决电梯群控调度问题时，应充分考虑电梯当前运行状态和运行逻辑，即模型约束条件：

1)当电梯产生m个向上的呼梯信号时，此时电梯首先响应较低楼层的乘客，然后再响应较高楼层的乘客。

2)当电梯计划服务于n个下行信号的乘客时，电梯首先承载较高楼层的乘客，然后再承载较低楼层的乘客。

3)电梯实际载重量超过额定载重量时，不响应任何呼梯信号。

4)行驶过程中，当同时有向上或向下的呼梯请求时，电梯顺应当前行驶路径预先响应相同方向的信号。

5)分散待机策略：无任何呼梯请求时，电梯均匀分布于各个楼层为自由梯状态；上高峰时间段内，电梯均处于基层呈基梯状态。

3 模拟仿真及结果分析

3.1 模拟仿真

为验证混合ABC-SA算法应用于电梯群控系统派梯调度策略的有效性，以常见办公大楼3部电梯24层建筑物群控电梯系统作为模拟对象，当前状态下设置楼层内电梯运行情况参数如表2，仿真代码在Matlab平台上编译。

表2 EGCS群控电梯参数

分别进行上高峰、下高峰、层间交通模式3种情况下的仿真实验，目标函数的权重系数取值如表3所示。上高峰模式下人群密集，乘梯需求多集中于基层并向上行驶，且上高峰多发生在早上上班期间，以输送人流为主要目的，因此乘梯时间、侯梯时间、系统能耗权重分别为0.4、0.65、0.1。下高峰多发生在下班期间，以输送乘客为主，乘梯时间、侯梯时间、系统能耗权重设置为0..4、0.4、0.2；同理层间交通模式下人流量少以能耗为主时间性能为辅，权重设置分别为0.2、0.2、0.6，在不同模式权重下对群控电梯进行多目标调度仿真研究。

表3 不同交通模式下的权重

3.2 结果分析

针对1.2节建立的多目标优化函数，在Matlab仿真软件中采用基本ABC算法和混合ABC-SA算法对3.1节所设置的三3种不同模式进行仿真研究，群控电梯多目标优化前后适应度曲线对比结果如图2～4所示。

由图2～4可以看出，基本ABC算法在3种模式下均容易陷入局部最优解，而改进的ABC-SA混合算法却能跳出局部最优最终达到全局最优解。且在基本ABC算法调度下上高峰、下高峰和层间模式的适应度分别为0.378、0.31和0.295，ABC-SA算法调度下适应度分别为0.395、0.357和0.314。可以看出无论处在哪种交通模式下，混合ABC-SA算法优化后的适应度值结果都优于基本ABC算法的求解结果，选择适应度大的结果进行派梯，验证了混合算法的有效性。

图2 上高峰模式两种算法的收敛对比图

图3 下高峰模式两种算法的收敛对比图

图4 层间模式两种算法的收敛对比图

为进一步说明结果的有效性，通过对平均侯梯时间、平均乘梯时间、停靠次数的多组数据进行优化，然后取各指标值的平均值。表4～6为上高峰模式下混合ABC-SA算法与基本ABC算法进行比较的仿真结果。仿真数据表明，与基本ABC算法相比，混合算法的平均候梯时间，平均乘梯时间以及停靠次数的平均值都有不同程度的提高，ABC-SA算法下的平均等待时间减少19.69 s，平均乘梯时间减少4.57 s，停靠次数减少4次，各项重要指标均比较理想，其衡量电梯群控系统的3大指标性在混合ABC-SA算法下均比基本ABC算法有所提高。

表4 平均侯梯时间比较 s

表5 平均乘梯时间比较 s

表6 停靠次数比较 n

表7为两种算法在3种模式下的各指标数据值，可以看出在不同的交通模式下，ABC-SA算法的求解质量相对于基本ABC算法的求解质量具有一定优势。尤其是在上高峰和下高峰模式，ABC-SA算法的优势比层间模式下的优势更为明显。其仿真结果表明了该算法具有一定的可行性和有效性，能有效地提高群控电梯系统的性能和服务质量。

表7 不同模式下调度算法对比

4 结束语

电梯群控系统具有庞大的状态空间和随机的乘客到达等特点，且需同时兼顾乘客的时间请求以及能耗请求，这使得调度问题变得复杂。文中提出一种混合改进的人工蜂群算法实现对群控电梯优化调度策略的研究，通过确定影响群控电梯性能的关键因素建立多目标数学模型，根据基本人工蜂群算法求解易陷入局部最优解进而引入模拟退火思想改善算法性能，经仿真研究ABC-SA混合算法求解结果相对于基本人工蜂群算法在乘梯时间、侯梯时间和停靠次数方面均有一定提高，对电梯群控系统多目标调度的优化有一定的应用参考价值。