一种基于蚁群遗传算法的电梯群控算法设计

谢轶俍 李昂

（1.同济大学 上海 2.三菱电梯）

一种基于蚁群遗传算法的电梯群控算法设计

谢轶俍1李昂2

（1.同济大学 上海 2.三菱电梯）

随着社会的不断深入，以及高层楼宇的不断涌现，多台电梯单独服务的电梯系统已经无法满足人们对于电梯的需要了。多台电梯如果需要更好地提高效率，那就需要一种好的群控方法，来对电梯群进行控制。本文算法的主要目标是在于将蚁群算法与遗传算法进行融合，然后再将电梯调度的基本模型引入蚁群遗传算法中，通过遗传算法中概率选择、交叉、变异等一系列操作手段，提高电梯调度系统的全局搜索能力以及蚁群算法快速的求解能力，优势互补，在算法收敛以后，得到较好的电梯群控调度方案。

蚁群算法；遗传算法；电梯群控

1 两种算法的性能分析

蚁群算法及遗传算法在计算的过程中，本质上可以并行计算、即其具有并行性。它们之间的信息是可以相互交流，协同处理。同时，遗传算法不受条件的约束，在对电梯群控参数进行一一编码形成2进制编码的染色体后，通过交叉和变异操作，使其具有了全局搜索解的能力的，这样一来在面对多个召唤同时出现的复杂调度及非线性问题，它具有很好的解决能力。当然遗传算法同样有其缺点，根据遗传算法在求解到一定范围时往往会出现冗余的迭代，使得反馈信息无法完全被利用，导致求解效率不高。蚁群算法因为其正反馈机制所以其求解的效率相对较好，但是蚁群算法的缺点是其在初始化阶段由于信息素较少，如果问题规模很大那么其相对来说效率将会变慢。

2 两种算法混合的可行性分析

我们可以设想一下，如果我们能将这两种算法优势互补，从而能克服两者可能存在的缺点，那求解的效率一定会有所提高产生一种在时间和求解上效率都比较高的蚁群遗传算法，相关研究表明蚁群和遗传算法的速度与时间曲线如图1所示。

图1 蚁群和遗传算法的速度与时间曲线图

我们可以从图上得知，遗传算法在t0～t1时间具有很快的速度，在t2这个点有了下降的趋势，在过了tc时刻之后求解的效率就降低了。蚁群算法在t0～t1时间速率并不是很高，缺乏信息素致使其搜索缓慢，随着信息素积累，过了tc它的求解收敛速度开始提高。那我们的初步思想是在前期在某些系统问题不复杂的情况下，利用蚁群算法处理问题，后期当系统复杂度提升时利用有全面搜索能力的遗传算法进行求解，再利用蚁群的特性进行最优解的求解，并作为遗传算法的种群的一个补充。

3 混合算法框架设计

作为电梯群控系统来说，其非常大的特点是实时性，这个特性大大影响了算法的搜索以及算法对于最优值计算的能力。由实时性伴随而来的其实就是系统的随机性，随机性则导致了单纯地求出最优解实际意义并不大，因为某个特定情况的最优解，不一定始终就是最优解。结合实际来分析就是当召唤信号由乘客发出后，即便系统通过本身的算法计算出最优化的分配方案，但是由于随机性的存在，电梯的环境条件其实随时都在发生改变。那么当时的最优分配方案在电梯被分配到用户呼叫楼层后就已经不是最优的分配方案了。因此本算法中在选择电梯的分配方式时是具有选择性地在每隔一段时间后就会重新启动遗传算法进行最优方案的搜索及电梯分派工作。对电梯轿厢的分派系统进行及时修正，简单地说就是在多个用户先后发出多个召唤信号时根据情况选择最优的电梯调度多目标优化方案。上述过程的具体流程图如图2所示。

4 电梯群控混合算法步骤设计

首先我们先确定了引入蚁群算法和遗传算法的条件：

图2 电梯群控混合算法的流程图

在确定之后开始算法流程的描述。

（1）扫描外部召唤信号。

（2）当有电梯系统有一个外召信号时候。

（3）分析各轿厢目前的状态。

（4）引入蚁群算法，并有多目标函数作为蚁群算法信息素浓度。

（5）求该调度方案的目标函数值与暂优方案进行比较。

（6）若该方案暂优，将其道路上整体信息素更新。然后信息素挥发。

（7）若不是则信息素直接挥发。

（8）算法是否收敛，不收敛则继续进行搜索。

（9）算法若收敛，将若个优秀调度方案作为遗传算法的补充放入数据库。

（10）继续扫描外召信号，若一段时间继续没有外召信号，则以蚁群算法的最优解作为最佳调度。

（11）若在一段时间内出现多个外召信号。

（12）则开始遗传部分的的计算

（13）将N个召唤对应的N太电梯作为染色体进行编码。

（14）种群初始化，先随机选出种群进行编码，同时蚁群算法的几个较有效解也可以作为种群的一个补充。

（15）先计算每个个体适应度。

（16）保留最优个体的策略选出N个个体。即选择操作。

（17）随机重新排列群中的个体序列。

（18）计算两两相邻个体交叉概率Pc按照此概率随机单点交叉两个体。即交叉操作。

（19）计算每个个体的变异概率Pm按照此概率随机变异得到下一代种群。即变异操作。

（20）计算新一代种群中个体适应度的值。

（21）是否满足终止条件，不满足则继续进行，满足则求得电梯调度最优解。

5 结语

本文在求解电梯群控系统中首先提出了将蚁群算法及遗传算法结合运用于电梯群控之中的思想。既加大了电梯的行驶效率、减少了消耗，在减轻轿厢拥挤度等方面，做出了多目标优化的尝试.而且还以模拟研究确认了此公式的可行性。截止到目前为止，这两种算法同时应用在电梯群控系统中的探讨还相当少。并对针对蚁群遗传算法的基础条件、数字建构、做出了重点探讨。有效设计了这两个算法的融合步骤及应用条件。

[1]刘立东，蔡淮.融入遗传算法的混合蚁群算法[J].计算机工程与设计，2014，05：1248～1249+1252.

[2]黄立君，许永花.遗传算法和蚁群算法融合求解电梯群控[J].东北农业大学学报，2014，04：109～113.

[3]肖宏峰，谭冠政.基于遗传算法的混合蚁群算法[J].计算机工程与应用，2014，16：42～45+134.

TP18

A

1004-7344（2016）08-0329-02

2016-3-1

谢轶俍（1985-），男，浙江绍兴人，工程师，本科，从事控制工程工作。