基于改进遗传算法的动态路径规划研

董小帅 ，毛政元

1.福州大学 福建省空间信息工程研究中心，福州 350002

2.福州大学 空间数据挖掘与信息共享教育部重点实验室，福州 350002

3.福州大学 地理空间信息技术国家地方联合工程研究中心，福州 350002

1 引言

按照对时变性因素的不同处理，路径规划模型分为静态和动态两种类型[1]，前者指在静态路网模型上迭加各路段权重，再采用规划与优化算法求解最佳路径，同一问题只需求解一次；后者指综合考虑路网中各路段的通行能力和路网不断变化的路况信息采用优化算法求解最优路径[2-3]。动态路径规划相比静态路径规划更具实用价值[4]，同时，由于其采用的动态路网模型加入了实时、复杂、多变的路网信息，经典规划算法难以高效、鲁棒地完成路径规划与优化，目前相关研究中一般采用仿生智能算法实现动态路径规划[5-9]。

遗传算法是一种采用种群搜索机制的全局性寻优算法，该搜索策略使求得最优解的可能性和效率大大提高[10]，该算法因此被广泛应用于包括路径规划在内的众多问题的求解研究。但是传统的遗传算法存在“早熟收敛”、种群多样性逐渐降低和局部搜索能力差等缺陷[11-14]。对此，相关研究文献中提出了一系列的改进，比如，采用启发式算法生成初始种群[15-17]，提出以相同节点作为交叉点的交叉策略和变异策略等[18-19]，提高收敛速度，避免“早熟收敛”；采用多种群协同进化策略[20]，优良基因以一定概率在不同种群间横向传递，降低“早熟收敛”的可能性；自适应交叉概率和变异概率的提出，动态调整交叉，变异操作[21]，使得随着迭代次数增加，种群多样性不会大幅降低；引入模拟退火思想[22]以一定的概率接受比当前解更差的新解，混合禁忌搜索算法[23]、爬山算法[24]、融入复合型操作[25]等提高局部搜索能力。这些改进能够在一定程度上克服传统遗传算法的缺陷，但在处理大规模实时交通数据时，求解精度与效率仍不能满足实时路径规划的需求。

本文针对传统遗传算法应用于动态路径规划求解的局限性提出以下三方面的改进：（1）结合随机选择和趋于终点方向提出一种控制全局搜索方向的种群初始化策略，在保持初始种群多样性的同时提高初始种群个体质量，加快收敛。（2）提出一种根据空间距离的邻近大小选择交叉位置点的交叉策略，有效保留父代优良基因，同时避免“早熟收敛”。（3）提出一种基于节点适应度的局部搜索策略，通过建立节点选择概率与节点适应度的正相关关系，有效提高局部搜索能力，加快收敛。设计与实现了改进的遗传算法，并以福州市部分路网数据为样本，验证改进后的遗传算法在求解精度、效率与稳定性三方面的进步。

2 动态交通网络规划模型

2.1 动态路网模型

在城市交通网络中，同一路段的交通状况一般会随时间而改变，动态路网模型不仅是对现实世界中路网的简单抽象表达，同时还包含路况的实时变化信息[26-28]。比如，某些路段在上下班高峰时段更拥挤，采用传统的静态路阻函数进行时间最短的路径规划时，不能有效规避拥堵路段，时间成本较高。动态路网模型是静态路网模型添加各路段时态信息后的扩展，其数学表达式如下：

式中，G表示有向带权的动态城市交通路网；V表示路网中节点集合，V={vi|i=1,2,…,n}；E表示路网中各个节点连通的有向路段集合，vj∈V}，vi、vj分别是路段e的起点、终点；T表示时间闭区间[t0,tm]，t0是起点时刻，tm是到达终点时刻，在实际交通网络中，Δt为间隔时长，其值越小越能实时反应路况信息的变化，一般取5 min，并忽略在该间隔时长内的路况变化；表示节点v在时刻t的时延集合；W(e,t)表示路段e在时刻t的路阻系数集合。

图1为路网示意图，其中节点包括转向延误节点和分流节点两种类型，后者不产生转向延误（如V2）；路段具有方向性，在同一时间间隔内，同一路段可能由于方向不同而具有不同的路阻系数。

图1 交通路网示意图

2.2 路径规划模型

如图1所示，设vO、vD分别是始节点、终节点，ROD是vO到vD所有合格路径的集合，r=(vO,v2,v4,v5,vD)是其中一条路径，r∈ROD，时间最优路径规划是指根据时刻t所在时间段的路况信息，分别计算ROD中每个路径的行程时间Z(r)，从中选择一条时间最短的路径作为该时间段内的最优路径，目标函数如下：

3 改进遗传算法理论

3.1 编码和初始化

遗传算法包括三种常用的编码实现方式，即二进制编码、符号编码与实数编码。在动态路径规划问题中，一条路径相当于一个染色体，路网节点相当于染色体中的基因，由于这些节点的排列顺序正好就是所要求的路径，所以采用实数编码方式更能直接表达路径的实际意义，同时也有利于适应值函数的选取和适应值的计算。由于城市交通路网中的节点数较大，满足相同起点和终点之间的不同连通路径一般具有不同的节点数，因此采用变长度染色体编码策略比定长度策略更适合求解动态路径规划这一问题。

遗传算法与其他搜索算法最大的区别之一就是其面向种群进行搜索的并行性，初始种群的设定对整个遗传算法的运行性能具有决定作用。传统的遗传算法采用随机的方式生成初始种群，这样虽能提高种群的多样性，但整个搜索过程缺乏方向性的引导，同时会出现断路或环路现象，使得遗传的进化操作复杂化甚至无意义。为了保证种群的多样性、避免出现断路与环路现象，同时又提高初始种群个体的质量，本文采用半随机方式生成初始种群，即引入控制全局搜索方向的启发式搜索策略。具体操作步骤如下：（1）以起节点O作为染色体的第一个基因，以终节点D作为染色体的最后一个基因。（2）为了规避断路或环路现象，当一个节点被选中后，就标记该节点，若当前节点无未标记的邻接节点可用于选择时，退回当前节点的上一节点重新进行选择并标记当前节点禁止下一次被搜索到。（3）以当前节点C的所有未被标记的邻接节点作为下一个节点N的候选节点，从中按照一定的选择概率使用随机方式或最优夹角方式确定下一个节点，若选择最优夹角方式，计算有向路段的夹角，选择夹角最小的节点作为下一个节点。（4）重复步骤（2）和（3）直到当前节点C 为终节点D，即为一个初始染色体。（5）按照此方式求解下一个染色体，直至达到初始种群规模的要求。（6）为了进一步提高初始种群个体的平均质量，本文确定初始种群规模为设定种群规模数的1.2倍，最后按表现排名依次舍去最差的多余个体。

3.2 选择操作

定义适应度函数的值为每个个体所包含路段和中间节点的交通时间阻抗之和，根据第二章得出的动态路网模型和动态最优路径模型可知，个体适应度函数为：

式中，Z(r)越小，染色体的适应值越小，所对应的路径所花费的行程时间越少，越接近于路径最优解。

选择操作是指从当代种群中选择优秀个体以生成交配池遗传给下一代的过程，联赛选择、最佳个体保留、适应值比例选择是目前最常用的三种选择策略。本文选择联赛选择与最佳个体保留相结合的策略，前者的基本思想为：从当代群体中随机选择一定规模的个体，比较后选择适应值小的个体放入交配池；可通过调整联赛规模动态控制群体选择压力，一般联赛规模取2。同时采用最佳个体保留策略将当代种群中最优的个体直接复制进入子代，使得子代种群中的最优个体不会出现比父代种群中的最优个体差的可能，从而保证进化方向，加快收敛速度。

3.3 交叉操作

交叉算子是模仿自然界染色体基因交叉重组将父代的优良基因遗传给下一代个体的操作。采用随机确定交叉点对或选择相同节点作为交叉点对的传统方式进行交叉操作存在明显的局限性，前者需对子代个体进行连通化处理，从而使父代的优良基因发生剧变；后者会因为两父代个体在此节点的前后基因片段相同而产生等同于父代的个体，使得交叉操作无效。因此本文采用启发式邻近交叉算子操作，主要步骤如下：（1）从其中一个双亲中随机选择待交叉点（除去O、D点）。（2）计算另一双亲中的节点与该节点的空间距离，选取距离最小的节点作为交叉点。（3）在交叉点连通生成子代个体，使子代表示的路径合格化。此策略把需要连通处理的路段降到最小，同时保留了父代双亲的优良基因。

3.4 变异操作

传统的单点、多点变异等策略在路径规划问题中不能有效地维持种群的多样性，容易导致个体向更坏的方向变异，本文采用多向变异策略，主要步骤如下：（1）按照变异概率选择变异个体，随机选择变异个体的变异点（除去O、D点）。（2）以该点为起点，O点为终点，逆向搜索获得变异个体。（3）以D节点为起点，该变异点为终点，逆向搜索求得变异个体。（4）对两个变异个体进行去环路处理。（5）比较两种方式下变异个体的适应度，选择适应度大的个体作为子代个体。（6）为保证种群多样性，每隔五代重新生成一个新的个体取代其中一个待变异个体。

3.5 局部搜索策略

前人引入模拟退火、爬山与禁忌搜索等思想设计的混合遗传算法虽在一定程度上能提高遗传算法的局部搜索能力，但由于局部搜索过程中多次随机生成若干路段，然后比较择优替代旧局部路段，而没有考虑或者利用局部路段中邻接节点的路况、转向等已知信息的综合影响，从而导致经过大量时间解算得到的最优路径中的部分路段为次优而非最优，因此本文引入节点适应度这一新的局部搜索策略对各代种群个体的随机部分基因片段进行自学习，以替代适应度差的旧基因片段，且每次自学习只需搜索一次。根据路段的实时路况Traffic、路段的道路等级类型Type、转弯类型Turn，以及与基因片段终点的夹角Angle四个影响因子对当前节点的邻接节点进行适应度评价，定义为节点适应度，按照适应度所占比例选取下一节点。节点适应度与节点选择概率定义为：

式中，f(xj)为当前节点的邻接节点xj的适应度；根据路段的路阻系数，分为通畅、较通畅、拥挤和拥堵四种类型，分别对应的 Traffic值为1、0.75、0.5、0；根据城市交通道路的等级类型，分为主干路和支路两种类型，分别对应的Type值为1和0.5；通过判断通往下一节点的行驶转向，分为直行、右转、左转和掉头四种类型，对应的Turn值分别为1、0.75、0.5和0.25；Angle为有向路段----CN与------

ND的夹角所对应弧度值（C为当前节点，N为待选邻接节点，D为所选基因片段的终点），由于其与适应度呈为负相关，需要进行倒数处理。P(xj)为邻接节点xj的选择概率，节点适应度越大，选择概率就越大。

3.6 算法步骤

改进的动态路径规划算法的主要步骤如下：（1）设定遗传参数以及动态路阻系数。（2）采用启发式策略获得初始种群。（3）计算个体适应度，判断是否满足算法终止条件，满足则算法终止输出实时路径转步骤（6），不满足转步骤（4）。（4）进行选择算子、交叉算子、变异算子操作，对遗传算子操作生成的子代个体进行局部搜索，并通过筛选生成子代种群。（5）转步骤（3）。（6）按照最优路径行驶，每隔5 min更新动态路阻系数，并判断当前最优行车路线上是否出现某一个或几个路段发生拥堵等严重影响正常通行的现象，若不发生继续原定路线行驶，若发生转步骤（7）。（7）定位当前位置的下一节点，若其为终点，结束行程，若不为终点则以该节点为起点重新进行路径规划。如图2为算法流程。

4 实验与分析

4.1 数据处理

图2 改进后的算法流程

有向交通路网向量数据主要包括节点图层和路段图层，依据时间最短的路径规划需求，先设计节点与路段的字段属性表：前者包括RoadID、FromNodeID、ToNodeID、Road_Type、Speed、Length与Real_Traffic字段，分别表示路段编号、路段起节点编号、路段终节点编号、路段等级、通畅时速度、长度、拥堵系数；后者包括NodeID、X、Y与Node_Type字段，分别表示节点编号、X坐标值、Y坐标值、节点是否为转向节点；二者通过路段属性表中的FromNodeID、ToNodeID字段与节点属性表中的NodeID字段关联。为了模拟路网的动态性，采用时间离散化方法对路段拥堵系数进行每隔5 min的变化处理，结合路段长度以及通畅时路段速度求解路段行驶时间。本文采用的福州市部分路网数据共包含3 757个节点（包括转向时延节点和转向非时延节点），5 981个路段（包括单向路段和双向路段），228个时段的拥堵系数。

邻接矩阵和邻接链表是路网资料常用的两种存储结构，由于城市有向路网的大规模性和稀疏性，采用邻接矩阵表达路网数据需要消耗大量存储空间与搜索时间，而邻接链表充分利用了路网中路段的邻接特性进行存储，存储空间和搜索时间的消耗均远远小于邻接矩阵。因此，本文选用邻接链表数据结构，在.NET平台下，利用ArcEngine组件库进行仿真实验。

4.2 结果分析

种群规模是遗传算法的一个重要参数，对求解精度和求解效率都存在较大影响，如图3显示了种群规模与收敛适应值、收敛代数的关系：当种群规模较小时，需要较多收敛代数，同时求解的收敛适应值较大不能满足路径规划的精度要求；随着种群规模增大，收敛次数减少，同时求解的收敛适应值逐渐减低，最终收敛次数和收敛适应值趋于平稳；当种群规模为20～60时，收敛适应值和收敛代数皆满足最优路径规划的精度要求，但随着种群规模的增加，同样的收敛代数，种群规模越小，收敛计算时间越少。通过多次模拟分析，综合考虑求解精度和效率，本文设定种群规模为30，交叉率为0.9，变异率为0.05，迭代终止条件为最优适应值连续5代保持不变或达到最大迭代次数100。

图3 种群规模对收敛适应值和收敛代数影响

为便于比较分析算法的性能，选取传统遗传算法（GA）、文献[22]中基于模拟退火的混合遗传算法（SAGA），以及本文改进的遗传算法（IGA）进行实验对比，随机选取一对OD点对，同时进行100代进化操作实验，分析对比进化过程中每代种群中最优适应值的变化情况。如图4所示，IGA在进化至13代时已达到收敛适应值，求解收敛速度快于GA和SAGA，同时IGA所求得的收敛适应值明显优于GA和SAGA。分析可知，本文所采用的局部搜索策略通过利用邻接节点自身的先验知识，构建节点适应度，然后根据各节点选择概率进行搜索，强化了局部搜索的目的性，进化过程中每一代种群最优值都有所提高，直至达到收敛适应值，从而提高了算法的局部搜索能力，使其具有更好的收敛性。

图4 进化过程中最优适应值变化

进一步对该OD点对进行20次实验，并利用第100代最优适应值的均值对之前每一代种群中最优适应值的均值做标准化处理，其值越趋近于1对应路径越优，结果如图5。IGA在前20代中具有很快的收敛速度，在进化至20代左右时的标准化适应值已达到0.9，即20次实验中有若干次已十分逼近收敛结果，而GA和SAGA进化缓慢，直到40代之后才达到0.9，说明本文提出的改进算法IGA的收敛性和稳定性均优于GA和SAGA。

图5 进化过程中标准化适应值变化

为避免偶然性，选取10对OD点对分别进行20次实验，实验结果如表1。精度上：IGA搜索到的最优个体所对应路径的行程时间更少，相较于GA缩短约38%，相较于SAGA缩短约6%；效率上：IGA收敛时所需计算时间平均值为1.232 s，相较于GA降低约30%，比SAGA降低约20%。本文提出的算法IGA具有更好的局部搜索能力，求解精度和求解效率均有明显提升，能更好地满足动态路径规划需求。

表1 不同OD点对实验结果

为检验本文提出的算法的动态性与优越性，选择锦绣大厦为起点，光明港公园为终点，采用三种算法分别进行动态路径规划诱导，结果如图6、7、8所示，其中红色代表拥堵路段，黄色代表拥挤路段，淡绿色代表较通畅路段，绿色代表通畅路段。初始时刻IGA所规划的最优路径避免不必要的转向等次优行驶决策，具有更好的局部搜索效果，行程时间为19.69 min，优于GA的34.68 min，和SAGA的22.56 min；5 min后规划路径中剩余部分未出现拥堵路段，不需要重新进行路径规划；10 min后规划路径中剩余部分出现拥堵路段，重新规划后得到规避了拥堵路段的新路径。对比可知，本文提出的算法IGA能更好地处理动态路径规划问题。

图6 GA动态路径规划

图7 SAGA动态路径规划

图8 IGA动态路径规划

5 结论

本文针对城市路网中动态路径规划问题，提出一种改进的遗传算法，该算法采用启发式策略控制全局搜索方向确定初始种群；采用空间邻近交叉策略完成交叉操作；使用前向、逆向的多向变异和重新生成新个体变异相结合的变异策略实施变异操作；引入节点选择概率的局部搜索策略进行局部搜索，能有效克服传统遗传算法存在的“早熟收敛”，局部搜索能力差等问题，同时有着更高的收敛效率与更稳定的收敛性。实验结果表明，提出的算法在搜索最优路径的过程中具有更优的局部搜索能力，能有效地规避交通拥堵路段，满足行进中的动态最优路径规划对求解精度和效率的要求。