基于混合算法的智能立体停车库研究

2018-05-03张小龙杨国太

铜仁学院学报 2018年3期

张小龙，杨国太

（安徽工程大学机械与汽车工程学院，安徽芜湖 241000）

0．引言

现在生活中汽车随处可见，汽车总量也在不断的增加。据权威部门统计，截止到2016年我国小型载客汽车已经接近1.5亿辆，与上一年相比，其中私家车的增幅达到15.08%，增加近2000万辆[1]。按照停车位需求：每辆汽车平均有1.2个停车位（一个基本停车位加0.2个公共停车位），可见停车位缺口非常之大。从目前数据[1]来看，我国汽车保有量与停车位之比约为4:1，停车位的满足率不足30%。传统地面停车位因受土地限制已不能满足当下需求，立体停车库逐渐兴起。它在节约土地的同时还能有效地避免车辆意外受损以及被盗事件的发生，且它体积小，容量大，现在已经较广泛应用在大型医院，大型超市等车辆密集的公共场所。但是目前应用较为广泛的立体车库控制系统主要由PLC控制，受到其本身性能限制，具有响应速度慢，只能进行简单的逻辑运算和顺序控制的缺点，使它无法在大型停车库上实现智能优化存取路径，实现高效便捷的存取[1]。

考虑到遗传算法和蚁群算法对于优化复杂大型立体停车库运行轨迹有很大的优势，可经过多次迭代寻找最优路径，实现智能选择。文中提出了结合二者优势的混合算法，对立体停车库存取过程的停车库载车板运行路线进行优化，使得存取车更加高效、智能。

1．立体车库车位调度模型

升降横移式立体车库是一种常见的立体停车库。它主要是以框架为结构支撑，利用停车托盘为运动工具，利用升降横移电机提供动力，实现停车库各层车辆的存取。载车板的运行特点是：底层只能横向移动；最高层的只能上升下降；中间不仅可以平移还可升降，且在每层都设置一个空位（不放载车板）作为通道供载车板升降时使用[6]。位于底层位置的车辆，无需移动其他托盘即可完成存取；底层以上各位置载车板存取车时首先对下方位置进行判断：当下方位置不为空位时先对下方载车板进行左右平移，然后向下移动，也可自行移动至空位上方然后进行下移[3]。载车板运动的基本方式是：升降回到原位，平移不回到原位。立体车位模型如图1所示。

从上面的车库排列方式可以看出每次的存取方式有很多种，每种的动作方式也不相同，所以满足条件的存取路线有很多。从这些路线中选择用最短时间走完最少的路线是我们研究的要点。与此同时，为使立体停车库安全工作，有许多限制条件：（1）底层车位上下受限，仅能左右运动；（2）顶层车位左右受限，仅能上下运动；（3）上升下降后的运动一定是左右移动；（4）车库的最后一步是下降至一层位置[9]。

图1 立体车库模型图Fig 1 Three-dimensional garagemodel diagram

2．混合算法设计

2．1．遗传算法和蚁群算法简介

遗传算法（Genetic Algorithm）是一种概率搜索算法。其原理为利用编码方式将解空间映射到相应的编码空间，编码与问题解一一对应，称为染色体，再随机确定一个起始种群（染色体数串）进行后续迭代[5]。对比生存理论，依据适应度的不同来挑选对应的染色体，然后根据不同的遗传算子对确定的种群进行交叉异化，得到新的种群[2]。重新生成种群的环境适应性将比迭代以前的种群更好，最后进行重复进化，直到最后得到优化解。这时最后经过迭代生成的末代个体可以看作是所求最优解。

遗传算法具有优异的整体搜索性能，较强的自适应性使它在工程实际问题中得到较为广泛的应用。但它有一些缺点：局部寻优能力不足，收敛速度慢，容易早熟，尤其需要优化的参数较多时，遗传算法的缺点更加明显[5]。

蚁群算法（Ant Colony System）一种新型仿生类进化算法。它是通过模拟工蚁出巢觅食时寻找最短路径的情形提出的。蚁群算法的基本原理是：大量工蚁向未知食物区域寻找食物，当其中一只工蚁找到后会向所在区域分泌一种传递信息的激素，通过这种信息素的扩散吸引其他工蚁到来，这样找到食物的蚂蚁就会越来越多[4]。在其它工蚁来此的路上，一些会沿着之前蚂蚁走过的路，但有些蚂蚁会重新寻找路线。如果新出现的路线比原来路线更短，那么越来越多的蚂蚁会逐渐被引导至新开辟的短路线上。

蚁群算法采用正反馈机制，不断收缩搜寻范围，最后得到最优解。它的搜索过程通过分布式计算方式实现，多个个体同时进行并行计算，不仅提高了算法的计算能力和运行效率，而且容易找到整体最优解[3]。但是在运行初期信息素缺乏，无法在运行之前找到一个使它在面对各种情况时都能获得最优性能的参数，导致时间效率低下。

2．2．混合算法的基本流程

基于遗传算法与蚁群算法的混合算法可以使二者优势互补，弥补两者的短处。首先依靠遗传算法的全面择优能力、自适应性、快速性等来产生应用于蚁群算法的原始信息素分布。然后由蚁群算法的并行性和正反馈方式及求解效率高的特征，来求最优解[3]。这样融合后的混合算法在时间效率上和求解效率上均优于单独的遗传算法和蚁群算法。混合算法的过程如图2所示。

3．遗传算法

3．1．编码与解码

立体停车库的研究目标是在运动方向受限的前提下，行走最优路径。分析车位的动作有五种状态，分别是：静止不动，向上移动，向下移动，向左移动，向右移动，然后进行参数编码，具体方式是：个体的奇数位和偶数位分别代表车位号和运动方向，并且用数字0，1，2，3，4来表示车位的静止不动，向上移动，向下移动，向左移动，向右移动。此处将解码定义为编码的逆过程。根据运动限制条件制定不同的惩罚函数，根据实际情况设计惩罚函数的情况有下面几种：

（1）确定目标车位所在位置，一层停车板上下移动的与顶层停车板左右移动的；

（2）两个相邻车位运动并且朝一个方向的；

（3）最后一步的动作不是下降的；

（4）最后一步的车位不是目标车位的；

（5）停车板已经位于车库的边缘且在边缘方向上继续有动作的；

（6）在停车板下一步移动的方向位置上有其它停车板的；

（7）然后采用最佳保留选择的方式将适应度值优的子代直接遗传下去，或者通过交叉产生新子代再遗传下去，将适应度不好的个体进行淘汰，这种优胜劣汰的选择能够使得迭代终止结果一定是历代适应度最高的个体。

图2 混合算法流程图Fig.2 hybrid algorithm flow chart

3．2．交叉操作

对于一般遗传算法中的交叉算子很难适应立体停车库的调度特征，快速的将巡回路径上优异性能传给后代。为更好的解决这个问题，本文使用一种改进型的交叉算子，其具体如下：

（1）在每队父辈个体（A1、A2）中随机选择两个交叉点，两交叉点中间编码B1，B2；

（2）将父辈个体中A1与B2间的相同编码去除，剩下的记为C1，相同可以得到C2；

（3）在C1的任意两个基因间顺序插入B2的整个基因片段，插入一次则会产生一个后代，然后再将B2的编码倒置，进行相同操作。将D1记为两次操作产生的子代。相同地，B1与C2也产生后代D2；

（4）选择D1、D2中一个最优的个体遗传下来。特别注意的是，由于调度解编码的奇数位和偶数位分别代表立体停车库的车位号以及他的运动方向，如果在交叉和变异操作时不将车位号与动作方向同时看做一个基因来进行操作，那么将会出现车位号与动作方向混乱的情况。

3．3．变异操作

为了得到最优解，本文引入变换变异算子来维护种群的多样性，且可以防止遗传算法的过早收敛。例如，对于路径(1 2 3/4 5 6/7 8 9)，假设第一个切入点在3、4之间，第二个切入点在6、7之间，则得到的变换变异为(1 2 3/6 5 4/7 8 9)，它不仅保留了遗传给下一代的优良基因片断，而且又产生了新个体。新个体的复杂程度能够有效地扩大搜索范围。

利用遗传算法经过以上步骤，进行n次迭代后将会生成几组优化解作为车库的动作，由此得到的优化解交于蚁群算法进行下一步的优化。

3．4．适应度计算与选择复制

要获取最优运动方案，首先选择对应的评价函数，并设计相应的惩罚函数。研究的目标是在存取车过程中停车板运动路线最短，即车库停车板运动次数最少。为了对比评价函数并计算选择概率，评价函数的值要取正。

评价函数应尽量保证通用性，使其不用改变其中的参数，一个好的评价函数能在运行过程中自动修正其参数值，得到最优解。对于停车库载车板的运行优化问题选用的评价函数如（1）式所示：

4．蚁群算法

由于蚁群算法的计算开销大，从时效性和有效性等因素的考量，为避免混合算法在优化过程中过早停止，以及更好的与遗传算法相衔接，本文采用一种改进的蚁群算法并使用精英保留策略[8]。改进的算法包含几种蚁群，每种蚁群含有独自的信息素。

4．1．初始状态下信息素释放

将遗传算法得到的优化解作为蚁群算法的信息素，将组优化解分别作为几个蚁群的独立信息素，并且这几种信息素的更新相互独立，相互之间不受影响。设有n个节点，蚁群在(m，n)之间转移：

则初始时刻各路径上的信息素如式2所示：

4．2．接受信息素后的转移概率

在蚂蚁种群中，共在节点上随机释放m只蚂蚁，初始时刻蚂蚁在路径选择上的概率如（4）式所示：

4．3．信息素更新

当出现最优路线时，那只蚂蚁要进行信息素的全局更新（6）、（7）、（8）式所示：

随着循环的持续进行，经过最短路径的蚂蚁信息素不断加强，当达到设定的循环周期后，可以得到整个循环最短路径的信息素之和，如（9）式所示：

4．4．混合算法的复杂度分析

在程序的执行过程中，算法的时间复杂度定量的表达该算法的运行时间，空间复杂度是指计算所需的存储单元数量，算法复杂性和空间复杂度都是指算法运行时所需的计算机资源的量。

对于混合算法中的遗传算法由于其本质为二重迭代，时间复杂度小于n2，迭代次数一般不多，时间和空间复杂度主要体现在其中的蚁群算法中，设n是停车板数量，m是蚂蚁数量，T是迭代次数，则时间复杂度如（10）式所示：

一般情况下，m=n 2/3，T=k n，当n趋近无穷大时(此时k会远小于n)，time约等于n4；由space=3 n n+n m可得其空间复杂度如（11）式所示：

当n趋于无穷大时，space约等于n2。

5．实验模拟与仿真

在MATLAB环境下，以本文的立体车库为例，目标车位位于30号载车板的条件下，确定各遗传算子参数，得到了部分实验结果。按照本文的遗传算子设计，种群规模为20，迭代次数为30代，交叉概率Pc=0.8，变异概率Pm=0.2。

经过遗传算法的迭代并将最优解作为蚁群算法的信息素，继续寻找最优路径。经过实验对比遗传算法和混合算法的最优解的迭代曲线图（图3），可以看出遗传算法局部寻优能力不足，具有收敛速度慢的特点，而混合算法的收敛速度明显高于遗传算法。通过蚁群算法和遗传算法的时间响应速度对比（图4），可以看出遗传算法在响应速度上的不足：响应速度慢，时间效率低。结合遗传算法和蚁群算法的混合算法（图5），从图5中可看出它可将两者优点结合，响应时间短，收敛速度快，能够较快的寻找到最优路径。