基于强化蚁群算法的高层住宅电梯群调度研究

顾玲丽，董佳琦，许洪华

(苏州科技大学电子与信息工程学院，江苏 苏州 215009)

1 引言

电梯群控制系统(EGCS)是在一幢建筑物内能够对多部电梯进行统一管理调度的系统[1]。电梯群控研究早期，分区调度方法[2，3]、基于搜索的算法[4]和基于规则的算法[5，6]都是很传统的调度方法。

而蚁群算法作为智能算法，对于求解复杂的组合优化问题非常适用；如文献[7]采用蚁群算法解决了传统调度方法不能满足全局收敛性的问题，但同时也存在算法计算量大、收敛较慢等问题。通过大量的文献及研究可以发现，算法的收敛性与信息素控制策略息息相关，缺乏有效的初始信息素，算法在探索初期就不能对蚂蚁进行有效引导。为了克服以上不足，文献[8]提出Max-Min蚂蚁系统，主要原理是对路径上的信息素的允许值设限同时只有最好的ant更新轨迹；文献[9]算法中的信息素先用先验知识初始化，然后再用群知识引导信息素的更新，有效引导蚂蚁搜索；文献[10]根据蚂蚁进化规则，提出新的的算法；吴庆洪等人还引入变异机制，加快蚁群算法收敛[11]；但这些改进应用于实际的优化问题种效果并不明显，迭代次数多，计算量大仍然是蚁群算法应用于大规模优化问题的制约因素。同时在一般的住宅建筑中，目前电梯基本都是最为简单的单梯独立运行方式，也鲜有优化的运行调度，随着住宅建筑越来越高，类似的问题更为突显。

为了解决上述问题，文章针对性地以业主的乘梯体验与电梯群系统的运行能耗为优化目标，同时通过改进单蚁群算法，即先用Q-learning对信息素进行初始化设置，在概率路径选择中也引入Q值，对蚂蚁的搜索起到引导作用，再利用蚁群算法最终寻优获得最终的电梯调度方案，减少算法迭代次数，加快收敛。

2 电梯群组调度模型

2.1 系统模型

电梯群控技术图如图1所示，交通数据模块主要采集厅外厅内的乘客呼梯信号，根据识别的交通流模式，电梯的运行状态等信息进行统计分析，同时群控制器根据不同的优化目标，应用相应的调度优化算法，产生合理的控制策略，调度电梯群组合理运行，提高运行效率。

图1 电梯群控技术图

2.2 指标模型

在电梯群控系统当中，采用的调度算法主要还是解决提升乘客的乘梯体验问题，往往忽略电梯能耗问题，基于此，建立多目标优化模型，主要从业主平均待梯时间、乘梯时间以及系统平均能耗这三个目标来进行优化，具体如下：

1)业主平均待梯时间

(1)

其中fn表示示响应该业主楼层请求信号的电梯所处的位置，fc表示业主候梯位置，t1表示电梯行驶一层的大概时间，Ni表示电梯第i次停靠，ti表示电梯第i次停靠时间

2)业主平均乘梯时间

(2)

其中ft表示该业主所需要到达的目标楼层，Nj表示电梯第j次停靠，tj表示电梯第j次停靠时间；

3)平均运行能耗

(3)

电梯轿厢的启停会消耗大量能耗，暂不考虑其它能耗因素，电梯的运行能耗就用启停次数来表示，Hu1表示一台电梯所有的外呼信号的个数，Hu2表示一台电梯所有的内呼信号的个数。

2.3 算法模型

2.3.1 信息素初始状态模型

为了清晰的说明MDP过程的派梯问题，需要对状态，动作，成本奖励以及值函数等要素进行定义说明。

电梯群调度系统的状态集为S={st}，这个集合中有每个电梯的运行方向及当前位置、外呼信号、内呼信号；用A={ai}表示行为集，ai表示将当前新呼梯信息分配至电梯轿厢i；

式(4)Vπ(s) Bellman方程，式(5)是最优状态-行为值函数

V*(s)=maxVπ(s)

(4)

(5)

使用Q值函数作为强化学习模型中函数的值，电梯初始电梯分配方案是通过强化学习算法求解式(5)，逼近最优Q值函数，从而得到各分配任务的Q值。

2.3.2 蚁群算法数学模型

利用Q-learning获得初始分配方案的Q值后，初始化信息素矩阵，再利用并行蚁群算法进行最终派梯调度的过程中，同样需要建立合适的目标评价函数，同样考虑平均候梯、乘梯时间、系统运行能耗三个优化指标，公式如式(6)所示

fi=w1μTwi+w2μTki+w3μEeni

(6)

fi为第i部电梯的适合度，μTwi为候梯时间归一化隶属度，隶属度的值越小即业主等待时间越短，以此类推。

3 派梯算法设计

为了解决高层住宅建筑电梯群控调度问题，本文将强化学习中的Q-learning算法和并行蚁群算法相结合：将Q-learning算法获得的初始分配方案的Q值去初始化蚁群算法的信息素，同时再把Q值引入概率路径选择中，然后再用多个蚂蚁并行运行的蚁群算法来找到电梯的最优调度方案。

3.1 Q-learning算法的电梯任务分配

本文以MDP为框架模型，整个系统的目标是使累计奖赏R最小化，R的定义如式(7)所示。把Q-Learning视为求解最优状态动作值函数的值迭代方法实现电梯派梯的初始分配，Q值更新公式如式(8)所示

(7)

累积奖R即电梯平均运行成本主要包括平均待梯时间Tw、平均乘梯时间Tk、电梯的运行能耗Een这三个优化指标。

Qt+1(st，at)=Qt(st，at)+

α[Rt+1+γmina∈AQt(st+1，at)-Qt(st，at)]

(8)

用Q-learning来实现电梯派梯分配方案的初始化，其主要思想就是将S={st}为电梯群控系统的离散状态集，这个集合包含每个电梯的运行方向及当前位置、每个轿厢已有的内呼信息、外呼信息和尚未分配的新呼梯信息，将蚂蚁完成一次迭代得到电梯的分配方案作为可执行的动作a，从而通过(9)式奖赏R不断的迭代更新得到最优的Q值目标，同时也能获得初始相对较优的调度策略π*。基于Q-learning的电梯群控调度派梯算法步骤总结如下：

1)初始化st，at，rt，πt和Q值函数，最大迭代次数T，最大情节数ET，每个情节中最大步数ETP，探索因子ε，折扣因子γ，学习率β；

2)当前状态为s，即当前4部电梯的当前位置及运行方向，各楼层的用户请求；

3)当前情节数et=1；

4)当前步数P=0；

5)根据贪心策略，利用当前ε-greedy策略所得到的Q(s，a)值，选取相应的动作a；

6)获得下一时刻电梯以及各楼层用户请求状态st+1和系统成本rt+1，根据式(8)计算更新后的Q值；

7)对探索因子ε和学习率进行衰减，并将下一状态赋值给当前状态；

8)判断当前步数p，当前情节数et是否结束，结束则到步骤9，否则重新从步骤2开始；

9)根据迭代多次得到的较优的Q值。

3.2 并行蚁群算法的电梯群调度

将上一步骤算法所得的Q值对信息素进行初始化，再通过并行的蚁群算法寻优，形成最终的电梯派梯策略，其中评价指标式如式(6)所示。

其中w1+w2+w3=1，权重因子的选取根据实时的交通流模式随时改变，例如在早上下行高峰模式下，应该尽可能的使业主的待梯时间和乘梯时间尽量缩短，而较少考虑能耗部分，所以此时应使w1，w2权重大一点，w3权重小一点，在随机模式下，人流较为随机，此时应该多考虑能耗部分，因此适当增加能耗部分的权重，权重因子在不同模式下的数值选取参见表1。

表1 不同模式下权重系数

具体优化算法如下：

1)首先定义上述候梯、乘梯时间以及系统能耗矩阵

(9)

DTw表示候梯时间矩阵，其中TW11表示电梯1号到达一楼的等待时间，以此类推；

(10)

DTk表示候梯时间矩阵，其中Tk11表示电梯1号运送乘客到达一楼的乘梯时间，以此类推；

(11)

DTen表示系统运行能耗，Ten11表示电梯4号运行到20楼所经过的启停次数；

2)对DTw，DTk，DTen进行归一化处理，蚁群算法的输入可以通过式(6)求得的评价矩阵得来；

3)初始化，蚁群算法中的蚂蚁数量m，信息素重要程度因子α′，启发函数重要程度因子β，信息素挥发率η，调节因子μ，算法最大化迭代次数T；

4)根据算法获得的Q值对蚁群算法的信息素进行初始化设置；

5)t时刻蚂蚁K从电梯楼层i响应用户请求到选择下一楼层j的用户请求的概率

(12)

其中Tij(t)为t刻用户请求楼层i到j连接路径上的信息素浓度；此时的Q值就可以通过Q-Learning算法获得；

6)修改禁忌表指针，蚂蚁移动到一个新的楼层，再将该楼层放入禁忌表当中，随着时间的推移，表中将放满所有请求信号的楼层；

7)本次迭代结束后，计算所有蚂蚁走过路径上的楼层总数以及最佳派梯路径并保存；

8)将各个电梯连接路径上的信息素进行更新

(13)

9)当前迭代次数t=t+1，如达到最大迭代次数，算法结束，输出所有任务对应的电梯派梯方案；否则转入4)继续运行。

4 实验分析

4.1 实验参数设置

本文所进行的超高层住宅电梯群控调度算法设计均在python下进行验证。算法就以20层，4部电梯的高层住宅电梯为基础，基本的电梯参数设置见表2。

表2 电梯参数设置

派梯算法参数设置：强化学习算法中Q值为0，最大迭代次数T=100，最大情节数ET=200，最大步数ETS=100，α=0.5，衰减因子β=0.8，折扣因子γ=0.8；蚁群算法中重要程度因子α′=1，启发函数重要程度因子β=3，信息强度Q=100，信息素挥发率η=Q/F(i，j)，期望值的重要程度ρ=0.3，算法最大化迭代次数T=200，蚂蚁个数m=40。

4.2 仿真运行与分析

业主是高层住宅电梯群控系统的服务对象，需要根据业主的生活方式及规律来调整相应的调度策略，然而仿真难以获得真实的乘客流动情况，所以通过模拟每一层楼的请求信号来进行试验。随机设定的每一层请求信号的个数见表3。

表3 每一层请求信号个数

文章首先对层间常规交通时段进行仿真。具体过程如下：首先利用q-learning对初始的电梯分配方案寻优，得到各分配任务的Q值，利用迭代寻优得到的各任务的Q值去初始化蚁群算法的信息素矩阵；而后设置蚁群算法中的蚂蚁数为40只，将这40只蚂蚁分成10组，每组4只，将这四只蚂蚁随机的放置于4部电梯所对应的任一楼层，然后根据式(11)以一定的概率选择下一楼层的用户请求，当遍历完一次之后，将最短路径存储到表中，同时根据公式(12)更新信息素矩阵，开启下一组蚂蚁去遍历呼梯信号，直到10组蚂蚁都遍历完，到达迭代次数上限，终止算法，然后计算出最短路径和平均路径长度，如图2。

图2 随机模式下电梯群仿真图

通过上图可以看出，在随机人流模式下，大致在迭代到40代时电梯运行的最短路径趋于稳定值，收敛较快，而平均路径长度的曲线图波度较大，考虑是因为随机模式下呼梯信号具有随机性与动态性，但其值也最终较趋于稳定；通过此实验图可以知道强化蚁群算法在超高层住宅电梯群控系统的可行性与有效性。

为了验证文章中提出的算法的优越性，将强化蚁群算法去与单蚁群算法在典型的下行高峰模式下和随机层间交通模式下相比较。

4.2.1 下行高峰模式下两种算法仿真结果

在下行高峰模式下，蚁群算法的权重设置为W1=0.5，W2=0.4，W3=0.1，此时为业主上班下行高峰，主要以疏散乘客为主要目标。上行客流百分比设置为0.05；下行客流百分比设置为0.90，层间流动客流百分比设置为0.05；乘客到达率设置为50人/5min。仿真结果如图3～5所示。

图3 下行高峰模式下算法性能对比图

从图3到图5中可以看出，在下高峰模式下，两种算法都能有效地减少电梯的平均待梯时间，乘梯时间和运行能耗。在图3中，单蚁群算法大致在迭代到20代时电梯运行的最短路径逐渐趋于稳定值50左右，而文章提出的新算法在同等的迭代到20代时最短路径值为46；随着迭代次数的增多，单蚁群算法的最短路径值稳定在49左右，而新算法的值趋于40，明显优于单蚁群算法，这说明在用户体验以及系统能耗方面有很大改善。图4与图5为两种算法在乘客平均待梯时间与乘梯时间的仿真对比，可以看出，改进的蚁群算法的平均候梯时间、平均乘梯时间水平均位于单蚁群算法之下，分别平均减少了7.5s和8.2s，这对于在高峰模式下疏散乘客效果显著。

图4 下行高峰模式平均待梯时间对比

图5 下行高峰模式平均乘梯时间对比

4.2.2 随机层间模式下两种算法仿真结果

在随机层间模式下，蚁群算法的权重设置为W1=0.2，W2=0.3，W3=0.5，此时为住宅较为空闲的时间，主要以减少业主乘梯时间和降低系统运行能耗为主要目标。上行客流百分比设置为0.05，；下行客流百分比设置为0.45，层间流动客流百分比设置为0.10；乘客到达率设置为30人/5min。仿真结果如图6～8所示。

图6 随机层间模式下算法性能对比图

层间交通模式相比于客流高峰模式，乘客数量有一定幅度上的减少。从图4可以看出，在随机模式下，两种算法的收敛速度差不多，两者性能相差不大，本文方法稍稍优于单蚁群算法。从图7为业主乘梯时间的算法对比结果，图8为整个电梯群系统运行能耗对比图，可以发现，在随机层间模式下，由于客流量不大，两种算法下的平均乘梯时间相差不大，较为接近，但从图8可以看出，本文算法使系统能源消耗大大降低，优于蚁群算法下的能源消耗。

图7 随机层间模式下平均乘梯时间对比

图8 随机层间模式下运行能耗对比

本文通过强化学习初始化蚁群算法的信息素矩阵，从两个方面优化了原本单一的蚁群算法。首先，强化蚁群算法中，电梯组的最短路径从迭代一开始就优于单蚁群算法，并一直保持在一个比较小的值。虽然中间有一些波动，但总体上来看效果优于单蚁群算法。其次，强化蚁群算法能更快的收敛到一个最优值。相比之下，单蚁群算法收敛速度更慢，并且很难收敛到一个比较优的值。这一效果的原因存在于强化蚁群算法的预处理部分即通过强化学习的输出初始化蚁群算法的初始信息素，同时将Q值引入概率路径选择中。由于采用的最终结果由蚁群算法部分的输出决定，因此不需要强化学习的智能体收敛到最终趋于平稳。同这种条件下，强化蚁群算法即保证了时间消耗较小，也保证了最终效果优于单蚁群算法。

5 总结

本文针对高层建筑鲜有电梯群调度以及蚁群算法在电梯群控调度系统中存在的迭代次数多、收敛速度慢的不足，用Q-learning与蚁群算法有效结合解决高层筑住宅电梯调度问题，从业主待梯、乘梯时间和能耗这三个方面进行多目标优化建模，利用信息素对蚂蚁进行有效引导，而后再将其Q值引入概率计算公式，加速蚂蚁搜索。通过实验可知，与传统的蚁群算法相比，不仅计算量大大减少而且从更大程度上提升业主乘梯体验，降低系统能耗，效果显著。