基于蚁群算法的进路搜索算法研究及应用

2018-12-21吴相飞敖银辉

机械工程与自动化 2018年6期

吴相飞，敖银辉

(广东工业大学机电工程学院，广东广州 510006)

0 引言

地铁信号联锁系统是提高地铁运输效率、确保车站运行安全的必要技术装备。联锁一般来说是指在进路、信号机、道岔和区段之间建立的一种相互制约关系[1-2]。在地铁车站连锁系统作业中，进路的选排对接发车工作的效率和车站是否能通过有着直接的影响，如何合理有效地选排接发列车和调车工作进路是确保行车安全和提升行车效率的重要研究内容。

计算机联锁的进路选排有很多种进路搜索的方法，其中经常使用的算法有A*进路搜索算法和二叉树遍历搜索[3-6]。近年来很多的研究学者大量使用了智能优化算法来求解路径优化方面的问题。例如文献[7]将高度搜索算法用于搜索基本进路和变更进路的过程，该算法弥补了深度优先算法和广度优先算法的缺陷，使得搜索目标更加明确、搜索过程更加高效准确；文献[8]通过对地铁车站站场图和有向图的结合，研究出了一种适用于地铁车站站场实际状况的进路搜索算法，并给出了具体的描述内容。本文结合以上文献提出了一种基于蚁群算法的进路搜索算法，其以蚁群算法为核心，具有精确、快速有效、占用空间小的特点，能高效地搜索出一条所需基本进路。

1 地铁站场数据结构分析及建模

站场型数据结构指的是依据地铁车站站场信号布置地铁车站平面图，由地铁车站各个信号点依据其在车站平面图的位置链接组成，本质就是节点的链接表[9-10]。广州市地铁三号线站场平面布置如图1所示。为了简化对车站站场的建模过程，只研究了列车进路的选排，暂时没有研究调车进路的选排。

图1 广州市地铁三号线站场平面布置

首先我们要简化站场图，站场下行接车口由两个方向组成，分别是岗顶方向和广州东方向。设上行信号机用S表示，下行信号机用X表示；用W开头的一段数字代表道岔，如W0001号道岔；用T开头的一段数字表示轨道区段，如T0001。如图1所示，地铁车站站场是由各个信号设备按一定的连接方式组成的设备网络。地铁车站信号设备主要包括信号机、道岔、轨道区段等，且这三者信号设备之间存在物理连接关系。将信号机、道岔、轨道区段都作为站场图节点并进行统一定义，按照由左向右、由下向上的顺序对节点依次进行编号。把两节点间的长度和所用通行时间等属性表示为该边的权值(例如编号2节点和编号3节点之间的权值为6)，就可以把地铁车站站场抽象为一个带权有向图，如图2所示。

2 基于蚁群算法的进路搜索

2.1 蚁群算法进路搜索的描述

地铁车站站场由各个信号设备按一定的连接方式组成一个设备网络。将各信号设备抽象为节点集合N={n1,n2,n3,…,ni}，各信号设备之间的距离长度抽象为对应的逻辑边集合dij(i,j=1，2，…，N)，例如d23表示编号节点2和节点3之间的距离长度。用τij(t)表示t时刻在节点i和节点j之间路径上的信息素强度，用于模拟蚂蚁在地铁道路上的分泌信息。在改进蚁群算法中[11-12]，初始信息素强度设为：

τij(0)=W/(dij+dje).

(1)

其中:dje为节点j与终点e的直线距离；W为给定常数。蚂蚁k(1,2，…，M)识别各条路径上的信息素强度来决定转移方向，禁忌表tabuk用来记录蚂蚁k经过的路径。设q0为特定参数，0

当q≤q0时：

(2)

(3)

其中:allowedk={0,1,…,n-1}-tabuk，为蚂蚁k下一步允许选择的节点；α为信息启发式因子，代表轨迹信息的相对重要性；β为期望启发式因子，代表能见度的重要性；τij为边(i,j)上的信息浓度;ηij为启发函数，ηij=1/dij,反映了蚂蚁由节点i运动到节点j的启发程度。在蚂蚁k完成了一次路径搜索后，将其经过路径上的信息素浓度按照局部更新原则进行更新。其局部信息浓度更新规则为：

τij(t+n)=(1-ρ)τij(t)+ρΔτij(t).

(4)

其中:ρ为信息素蒸发系数;τij(t+n)为t+n时刻边(i,j)上的信息素浓度；Δτij(t)为经过n时刻边(i，j)上的信息素变化量。如果蚂蚁k经过路径(i,j),则：

(5)

其中:Q为给定的参数;Lk为第k只蚂蚁在本次循环搜索所走的路径长度。当实验中所有的蚂蚁都完成一次循环搜索之后，则对这一次迭代最好进路(最小值为Llocalmin)上的信息素进行调整更新：

τij(t+n)=(1-μ)τij(t)+μΔτij.

(6)

其中:μ为给定参数，且：

(7)

记录全局最优解：通过MATLAB进行实验仿真，当到达设定的迭代次数或有停滞情况出现时，则实验结束。记录迭代位置中显示的局部最优解中值最小的解，就是本次实验的全局最优解。

图2 31个节点的加权有向图

2.2 具体算法步骤和算法流程

2.2.1 进路搜索算法步骤

(1) 初始化参数α、β、W、μ、Q、nmax(最大迭代次数)，令nc=0(nc为当前迭代次数)。

(2) 计算所有节点的长度矩阵，按照公式(1)初始化信息素浓度矩阵，并将结果存放在τij(0)中。

(4)n小时以后，蚂蚁从初始节点到达终点，按照公式(4)进行实时更新。

(5) 重复(3)～(4)步骤，直到M只蚂蚁都完成路径的遍历。

(6) 计算各边的信息素增量Δτij和信息素量τij(t+n)，并记录当前迭代路径，更新最优路径。

(7) 判断有没有到达提前设置的迭代次数，如果有就结束实验，输出本次最优进路和长度值。

2.2.2 进路搜索算法流程图

进路搜索算法流程如图3所示。

3 实例仿真分析

以图1地铁站场平面图为实例，可以任意选择一条列车进路进行路径的选排。下面以广州东方向上行至珠江新城接车进路的选排作为实例进行仿真分析。

首先选中起始信号灯S0201和终点信号灯S0403，则相应的进路搜索起始节点和终止节点被确定，分别是节点2和节点18，参见图2。之后利用蚁群算法搜索列车排路，求解从起始节点2到终止节点18的最短距离。主要实验参数如表1所示。

仿真实验结果如图4所示。显然利用蚁群算法对路径的排路经过约55次迭代以后，便快速到达局部最优解，其适应度F不再发生变化，此时F=1.560 2×104，得到的最优个体是{2,3,10,11,12,25,26,17,18}，即为对应的最优进路节点。经过多次仿真实验表明，蚁群算法的初始种群都是随机产生的，收敛速度也在不断发生变化，却总会在一定的迭代次数后收敛。虽然本文在经典蚁群算法中对初始信息素浓度进行了改进，防止了蚂蚁初始搜索进路时的盲目搜索，但依然会陷入局部最优。针对以上问题，可以采用对局部更新规则的改进和全局更新规则的改进，在一定程度上避免了搜索陷入局部最优解，同时也增加了收敛到全局最优解的速度。