基于免疫遗传算法的区域道路网智能路径诱导系统

董勇刚,谭 燕

(1.湖北省交通规划设计院股份有限公司，湖北 武汉 430064；2.湖北工业大学 土木建筑与环境学院 ，湖北 武汉 430072)

0 引 言

区域内汽车的保有量逐渐增长，使得区域道路交通状态日益恶化。交通运行状态如果较差，将会对社会发展和人们的工作、生活造成较大的影响，甚至造成巨大的经济损失[1-2]。因此，为了满足人民群众对美好生活的需求，设计有效的道路网规划和车辆诱导措施具有重要的现实意义。

为提升区域交通运输水平、缓解交通拥堵状态，文献[3]在道路运行监管系统中设置通信数据采集设备，应用ITS技术实现对区域交通中汽车数据的无缝采集与实时传输，建立24 h获取数据信息的区域交通路径规划网络。在这种系统的支持下，区域道路网规划系统主要研究道路的空间变化与交通流量的神经网络测试，能够有效协调区域道路中汽车流量，但是不能对汽车行驶方向和最优路径进行引导。文献[4]采用动态路径诱导系统技术，实现区域道路网红外信标通信，从而对拥堵路况展开调度。这种方式需要在汽车上安装与动态路径诱导系统技术相匹配的语音导航系统，并需要安装交通数据频道的广播设备，从而保障汽车导航数据的实时精准性。但这种系统对车辆最优路径的规划能力较差。

免疫遗传算法是基于生物免疫机制提出的一种改进遗传算法，可对应传统遗传算法中个体的多样性，有利于提高遗传算法的全局搜索能力，避免其陷入局部最优。因此，为进一步优化区域道路网路径诱导能力，本文基于免疫遗传算法设计了新的区域道路网智能路径规划系统，其创新之处在于运用该算法对最优路径不断的进行迭代，得出最优解，再通过层次搜索法和限制区域搜索法对得出的最优解，进行区域性的固定与限制，以增强智能路径诱导系统的稳定性。

1 系统设计

为了使区域道路网中智能路径诱导系统随时掌握区域道路交通状态，本文在免疫遗传算法的基础上进行硬件设备的开发与设计，从而完成对路径诱导系统中的交通数据收集、处理等功能的设计。基于免疫遗传算法的区域道路网智能路径诱导系统硬件结构如图1所示。

图 1 区域道路网智能路径诱导系统硬件结构Fig.1 Hardware architecture of intelligent path guidance system in regional road network

图1中的VICS、Euro-Scout型号路径诱导设备作为红外信标的标识设备，需要安装在区域道路网中，方便工作人员的及时管理，同时也能够精准地识别道路中的车辆信息。这2种类型的红外信标设备可以通过自身发射的红外信号与车辆接收设备之间的通信时长、数据类型等信息确定系统数据中心对车辆运行情况的计算[5-7]。系统硬件部分通过区域道路网诱导控制中心数据库的命令，向车载路径诱导系统发送实时交通状态，并结合区域道路的突发事件进行信息更改与处理，向硬件设备提供稳定、有效的基础信息。在区域交通路径中，比较重要的交通路口需要装配具有信息发送与信息采集功能的数据信息收集板，同时，还能够为车载单元提供相应的道路信息文本，最终呈现于车载屏幕上，并按照一定类型的模糊聚类原理划分不同道路的交通拥挤状态，能够提供给系统用户稳定且实时的道路拥挤状态[8-9]。

此外，本文应用北斗卫星雷达和民用交通型号卫星雷达作为全球道路网络的信息覆盖硬件设备，为用户提供精准三维数据模型与速度信息，通过差分方式将汽车的位置信息定位至1～2 m，满足大多数普通雷达的位置精准度。在卫星雷达中装置伪随机噪声码设备，能够为卫星雷达提供抗干扰信号与信息传播通道，保证在区域道路网络智能路径规划过程中不出现较大数据误差与干扰因子[10-11]。相对于军用雷达来讲，民用交通型号卫星雷达偏差较大，但应用于区域交通网智能路径规划完全能够满足汽车的路径行驶规范[12]。

本研究还在卫星雷达中安装了基点信息接收器，能够反馈区域道路智能路径诱导过程中的测量距离与现实距离之间的误差，接收器中的终端接口再向系统用户传达经过接收器修正过的定位系统动态值。卫星雷达的接收机作为信息误差的修正设备，结合卫星雷达中的数据惯性以及定位观测量完成数据的实时修正，提升原始雷达数据的稳定性与精准性[13-15]。为对车辆的导航信息确定方式进行优化与改善，本文采用ADVANCE型号设备，通过自主通信的方式诱导数据定位算法与车辆流量的关联。

2 免疫遗传算法

路径诱导的作用是指应用连接法确定出发点和终点之间的距离、道路状态等信息，然后在区域道路网中确定两点之间的最优行驶路线[16-17]。

本文应用免疫遗传算法设计智能路径诱导系统，确定区域道路网中智能路径与遗传算法中染色体等串位结构之间的关联，应用编码对排列运算路径诱导信息，同时，需要结合实时的道路运行状态信息与免疫遗传算法中染色体等因素的算法功能，设定免疫遗传算法中染色体的长度代表路径规划的初始点与结束点。染色体内包含的子染色体是未知因素，其具有一定的延展性。因此，在设计编码的过程中，需要将区域道路网中所有的路径信息全部涵盖。

遗传免疫算法中的染色体具有不可重复的特点[18-19]。因此，当区域道路中具有环路、立交桥等路状时，不考虑将其道路信息添加至免疫遗传算法中，从而减少编码储存空间。在区域道路网中设置n个节点。则道路网中共有n个道路的初始点或终点，计算不同点之间的最佳路径时，可以对点与点之间进行路径个体编码，编码中的终点为基因结束位置，路径经过点位为基因串。免疫遗传算法在系统中的路径规划步骤如下：

1) 获取区域内的路径数据信息并生成基因种群结构；

2) 模拟路径的相关参数并设定路径规划中所应用的初始值；

3) 在种群数据中寻找具有代表性的路径运算参数，将其作为抗原，并判断最佳的适度计算条件；

4) 判断适度计算条件在一定时间内是否存在，并应用2种搜索方法扩大范围搜索备用适度计算条件，通过计算抗体确定路径最优解的存在；

5) 通过遍历所有的数据节点，将数据节点的重组操作，并将新产生的节点基因个体不断代入免疫遗传算法中循环迭代计算，并将计算结果持续性地检索与验证，保障最佳路径的有效性。

免疫遗传算法具有变量数量大的特点，因此，在复杂交错的道路网中可以设定大量的数据节点。然而随着区域道路网规模的不断扩大，数据节点的规模也不断增大，当基因中重复性地出现相同染色体时，将不能满足免疫遗传算法的基本适应函数，导致免疫遗传算法在路径规划的过程中出现基因种群库超载现象，不能够及时对种群基因库限制[20-21]，进而降低了系统对路径规划的搜索效率。为此，本文在免疫遗传算法的基础上建立种群的层次搜索方法与限制区域搜索方法，通过上述方法提升基因搜索效率。其中，层次搜索法用于实现图像分层处理、道路等级划分搜索以及关联子图搜索；限制区域搜索法用于实现限制距离与构建模型以及提取道路子网数据。

应用基因搜索方法选择区域道路中的任意两点作为种群基因的初始路径规划范围，两点之间进行连接可以得到相应的椭圆形搜索范围，椭圆限制区域搜索范围如图2所示。

图 2 椭圆限制区域搜索范围Fig.2 Ellipse area to limited search range

图2中，a为出发点，b为到达点，(A,B)为椭圆圆心坐标，(xa,ya)为a点坐标，(xb,yb)为b点坐标。由于每一个区域的道路网都具有不同的特点，导致椭圆形的搜索范围不同，应用几何学方法计算椭圆范围内的道路网匹配基因系数为椭圆长轴与椭圆焦距之比，进而能够确定椭圆的基本模型，可表示为

(1)

式中：θ为长轴与坐标系X轴的角度。

随着道路网的拓展，在椭圆形区域搜索免疫遗传基因的算法与搜索的功能特性也随之提升[22-23]。在应用免疫遗传算法规划最佳路径的同时，也需要考虑到用户的实用信息，例如路径长度、路况、道路等级、心理期待预期等，因此需要在免疫遗传算法的基础上建立函数策略，满足算法中染色体与基因构造过程中的环境稳定性。

假设路径权值为ω，通行率为g，路径基础长度为l，路径染色体参与数为r，路况染色体比重参数为r1，道路等级为C，道路等级染色体比重为r2，可得路径权值ω表达式为

(2)

权值ω越小，则证明通过此路径的时间越少，时间消耗损耗越小。

综合上述分析，设计基于免疫遗传的区域道路网智能路径诱导流程如图3所示。

图 3 区域道路网智能路径诱导流程Fig.3 Intelligent route guidance process of regional road network

3 实验研究

本文在免疫遗传算法的基础上，应用2种数据搜索方法在限制区域内寻找路径的最优解，使遗传算法与2种搜索方法形成数据平衡状态，更有利于免疫遗传算法信息的深度积累与最优路径空间的解锁。

将免疫遗传算法应用到实际系统中，通过节点与节点之间的路径规划验证本文系统的有效性。设定在实验道路区域内具有11个路径出发点与终点(a—b点，将a设为起点，将b设为终点)。在考虑用户心理变化的情况下要保障权重值不能大于高峰值，根据生活常识需要在早晚高峰时期进行目标的最快路径搜索，此时的路径规划过程需要具有更短的路径规划时间，为用户行驶方向的改变争取时间。

为突出说明本文系统在最优路径诱导方面的作用，实验环境不便的前提下，进行对比实验，设置对照组，对比系统分别为文献[3]和文献[4]，实验结果的评价以路径作为评价指标，路径越短，说明系统的路径规划性能越好。实验结果如图4所示。

(a) 本文系统

(b) 文献[3]系统

(c) 文献[4]系统图 4 最佳路径对比实验结果Fig.4 Experiment results of the best path comparison

从图4可以看出，本研究通过免疫遗传算法对区域道路节点的不断操作与数据适应搜索，最终规划的路径为a—c—b，文献[3]系统规划的路径为a—g—d—e—b，文献[4]系统规划的路径为a—h—i—k—b，其中本文系统规划的路径除起点和终点外，只经过1个节点c，文献的系统除起点和终点外，均经过3个节点，与本文系统相比，路径的节点数量超出本文2个，路径的长度超过本文系统规划的路径。因此，本文系统规划的路径更合理，有效提高了路径的规划能力，实现车辆路径最优诱导。测试不同系统进行网智能路径诱导系统的稳定性，得到对比结果见表1。

表 1 路径诱导系统稳定性测试Tab.1 Stability test of path induction system

从表1可以看出，当迭代次数达到400次时，本文系统的稳定性达到0.997，近乎为1，文献[3]系统的稳定性为0.913，文献[4]系统的稳定性为0.901，分别低于本文0.084和0.096，其他迭代次数时的稳定性也均低于本文系统。由此可见，本文系统的路径诱导系统的稳定性效果得到了提升。

4 结 语

本文根据区域交通的特点对基于免疫遗传算法的区域道路网智能路径诱导系统展开研究与设计，采用经典的免疫遗传算法获取区域道路网中可能存在的路径最优解，再应用层次搜索法和限制区域搜索法对免疫遗传算法的最优解进行区域性的限制与稳固，从而增强了路径诱导的智能程度与高效性。

然而由于研究时间的限制，本文系统还存在一定的不足，如路径规划过程耗时偏多。因此，在接下来的研究中，将考虑从提高诱导路径规划时效性的角度进一步提高本文系统的应用优势。