论文部分内容阅读
摘要：在城市交通路网中诱导车辆规划较优出行路线，来提高人们的出行质量。本文分别研究了蚁群算法和粒子群算法，并根据其优缺点进行了算法融合。同时学习和分析了Transmodeler4.0软件，建立城市路网，加入仿真数据，并模拟了融合算法下的路径优化模型。结合实例，通过路径对比，提出优化方案。
关键词：蚁群算法；粒子群算法；Transmodeler；路径仿真
中图分类号：TP18 文献标识码：A 文章编号：1009-3044（2016）36-0166-02
针对目前智慧城市的要求，出行者迫切需要一个避免拥堵，安全方便，高效率的出行服务，交通管理者也需要合理的分配城市路网的交通流，使出行者的行驶路径达到最大优化[1， 2]。那么，路径优化的研究具有很大的意义。
算法的选择，直接影响了优化结果的精度。目前，广泛应用于路径选择和网络路由策略等领域的算法，常见的有群智能优化算法的粒子群算法（Particle Swarm Optimization，PSO）和模拟进化算法的蚁群算法（Ant Colony Optimization，ACO）。而交通仿真是再现复杂的真实交通现象，并对其进行问题解释、环境分析、现象预测，最终找出问题所在并解决优化，并对所研究的系统进行改进、比选和评价。Transmodeler4.0软件以地理信息系统 （ GIS ）为基础，采用较为实用的仿真模型，能够体现优化方案的科学性和可行性是仿真软件参数设定的最终目标，同时具有结果评价和分析等功能。
本文根据PSO和ACO两算法的优缺点进行算法的融合使用，加入实例，选出最优路径，并利用Transmodeler4.0软件对所选路径进行了仿真模拟，实验结果较好。
1 蚁群算法与粒子群算法
1.1 ACO的基本原理
ACO是应用最广的一种算法，其思想源于蚂蚁觅食行为，尽管蚂蚁个体非常简单，但能表现出强大的社会群体行为。
若m只蚂蚁被随机分配到m个地点。设各个路径上初始信息浓度值为[τ0]，可定为[τ0=m/cmn]，m为蚂蚁数量。变化后的信息浓度为[τijn]。设定过小的初始信息浓度[τ0]，容易使搜索陷入局部空间；[τ0]过大时，只有信息素挥发一部分之后，蚂蚁释放的信息素才能发挥指引作用。位于地点i的蚂蚁选择地点j依据如下概率公式[3]：
[pkij（t）=ταij（t）ηβij（t）s∈allowkταis（t）ηβis（t），j∈allowk0，j?allowk]
式中：
[τ0]——路径（i， j）的信息素浓度；
[nij]——地点间距离的启发式信息，[nij=1/dij]；
α，β——两个启发式信息的参数，决定启发式信息对蚂蚁选择地点影响的程度；
allow——蚂蚁未访问的地点的集合。
以上是个体蚂蚁的行为特征，要想得到局部最优解，需要多只蚂蚁多此寻找路径，一旦发现新的最短路径，就将此路径记录下来。
1.2 PSO的基本原理
在[D]维的搜索空间内，一个由[M]个粒子组成的群体按照一定的速度进行不断运动[7]。粒子[pi]在[t]时刻[D]维空间里的状态如下：
位置记为：[Xti=xti1，xti2，xti3，???，xtid]，i=1，2，3，…，[M]。[xtid∈xmind，xmaxd]，[xmind]，[xmaxd]分别代表搜索空间[D]的下限和上限；
飞行速度为：[Vti=vti1，vti2，vti3，???，vtid]，i=1，2，3，…，[M]。[vtid∈vmind，vmaxd]，
[vmind]，[vmaxd]分别为粒子飞行的最小和最大速度；
个体最优位置：[Pti=pti1，pti2，pti3，???，ptid]，整体最优：[Ptg=ptg1，ptg2，ptg3，???，ptgd]；
其中[1≤d≤D]，[1≤i≤M]，粒子群算法进行优化迭代中，则粒子[pi]在[t 1]时刻按照以下公式进行速度的不断更新和位置的不断更新：
PSO的基本算法步骤大概描述如下：
（1）初始化。设PSO中各类参数：搜索空间[D]的下限[xmind]和上限[xmaxd]；学习因子[c1]，[c2]；算法最高迭代次数[Tmax]和寻优误差系数[θ]；粒子的速度上限和下限为[vmind]，[vmaxd]。随机初始化各个粒子的速度[vi]和位置[xi]。
（2）计算和评价每一个粒子的适应值，并记录粒子的个体极值[Pti]和全局极值[Ptg]。
（3）将粒子个体历史的最好位置[Pti]的适应值于当前粒子位置适应值进行比较，[Pti]取优。
（4）将每个粒子的位置的适应值和全体粒子最佳位置[Ptg]的适应值做比较，[Ptg]取优。
（5）根据以上公式更新粒子的速度和位置。
（6）检验是否满足结束条件。如果当前的迭代次数达到了最高迭代次数[Tmax]或结果误差小于寻优误差系数[θ]，那么停止迭代，输出最优解。否则转到步骤（2）。
1.3 算法融合
PSO收敛速度较慢，易陷入局部优先，而ACO的搜索具有很大的盲目性。本文針对两算法的缺点和实际交通路径规划在计算时间和精度上的高要求，分别对ACO和PSO做出改进，建立混合型算法，模糊缺点，发挥各自在路径搜索上的优势。
利用粒子群算法得到一组优化路径，然后在整体的环境已经加入相同信息素，再从这组路径中选取部分路径，加大信息素浓度作为蚁群算法新的初始化信息素，从起点和终点一起进行精搜索，从而形成双向搜索模式，选出最优路径。所谓最优，并不是指路程最短，而是时间与路程的结合分析。从[O]点到[D]点的所有路径中，经过粒子群的筛选，以下三条路径可以作为蚁群算法的初始路径。 2 仿真实例
2.1 仿真环境
Transmodeler软件是目前应用比较广泛的仿真软件之一。本文使用的是Transmodeler4.0版本，此可以详细仿真从高速公路到城市道路各种道路网以及公交站点等设施[8]。二次开发是Transmodeler软件最大的特性，可以使此软件按照开发者需求或者城市道路变化需求完成有针对性的系统重构，建立一个针对城市道路智能控制算法验证的仿真软件平台。
2.2 实例模拟
选取2016年5月15上午9点到10点为仿真时间段，从内蒙古工业大学新城校区出发，目的地为呼和浩特市植物园。通过PSO-ACO融合算法，选出最优路径。
拟定工大新城校区到呼市植物园路线为仿真背景，在实际地图上设置城市路网（如图2），加入仿真流量，模拟区域简单仿真环境。步骤如下：
Transmodeler4.0软件打开地图“全景1.jpeg” →建立Simulation Project，并使用Road Editor工具箱，根据实况建立城市主干道、快速路、十字路口等仿真环境→加入仿真流量，以蓝色路径为仿真背景，通过设置车型、车速，以及各个路口的转向流量等，真实的模拟车辆行驶路径。
在9：01时，从工大南门出发自驾沿着爱民街直行，到达呼伦贝尔北路，向南经历第三个十字路口时，向西进入新华大街，通过两个路口进入新华西街，在9：15时到达呼和浩特市植物园。总历程将近14分钟，其中车辆速度根据实际情况不断变化，最高达到72.4km/h。
3 结论
本文将粒子群和蚁群算法相结合，从始发到终点的路径中，有效的选出相对最优的路径，并通过运用Transmodeler4.0软件加入实例，对两节点间的多条路径的距离和时间进行对比分析，为城市道路优化和出行提供了可靠的依据，并为智慧城市的研究提供很大帮助。
参考文献：
[1] 刁阳， 隽志才. 基于仿真的城市路网动态分配矩阵估计方法[J]. 系统管理学报， 2011， 20（3）：376-383..
[2] 赵明翠， 成卫， 戢晓峰，等. 基于TransCAD与TransModeler的交通影响分析方法[J].科学技术与工程， 2010， 10（27）：6689-6694.
[3] 吴义虎， 李宁，王正武. 蚁群算法在车辆路径诱导系统中的应用[J].系统工程， 2007， 25（2）：27-31.
[4] 宋世杰， 刘高峰，周忠友，等. 基于改进蚁群算法求解最短路径和TSP问题[J].计算机技术与发展， 2010， 20（4）：144-147.
[5] 李晓东， 王东， 曾凡智，等. 城市交通时間最短路径计算模型及应用仿真[J].计算机仿真， 2014， 31（1）：172-175.
[6] 杨慧， 成卫， 肖海承，等. 基于TransModeler的拥堵区域交通流量调控方法研究[J].科学技术与工程， 2011， 11（8）：1746-1750.
关键词：蚁群算法；粒子群算法；Transmodeler；路径仿真
中图分类号：TP18 文献标识码：A 文章编号：1009-3044（2016）36-0166-02
针对目前智慧城市的要求，出行者迫切需要一个避免拥堵，安全方便，高效率的出行服务，交通管理者也需要合理的分配城市路网的交通流，使出行者的行驶路径达到最大优化[1， 2]。那么，路径优化的研究具有很大的意义。
算法的选择，直接影响了优化结果的精度。目前，广泛应用于路径选择和网络路由策略等领域的算法，常见的有群智能优化算法的粒子群算法（Particle Swarm Optimization，PSO）和模拟进化算法的蚁群算法（Ant Colony Optimization，ACO）。而交通仿真是再现复杂的真实交通现象，并对其进行问题解释、环境分析、现象预测，最终找出问题所在并解决优化，并对所研究的系统进行改进、比选和评价。Transmodeler4.0软件以地理信息系统 （ GIS ）为基础，采用较为实用的仿真模型，能够体现优化方案的科学性和可行性是仿真软件参数设定的最终目标，同时具有结果评价和分析等功能。
本文根据PSO和ACO两算法的优缺点进行算法的融合使用，加入实例，选出最优路径，并利用Transmodeler4.0软件对所选路径进行了仿真模拟，实验结果较好。
1 蚁群算法与粒子群算法
1.1 ACO的基本原理
ACO是应用最广的一种算法，其思想源于蚂蚁觅食行为，尽管蚂蚁个体非常简单，但能表现出强大的社会群体行为。
若m只蚂蚁被随机分配到m个地点。设各个路径上初始信息浓度值为[τ0]，可定为[τ0=m/cmn]，m为蚂蚁数量。变化后的信息浓度为[τijn]。设定过小的初始信息浓度[τ0]，容易使搜索陷入局部空间；[τ0]过大时，只有信息素挥发一部分之后，蚂蚁释放的信息素才能发挥指引作用。位于地点i的蚂蚁选择地点j依据如下概率公式[3]：
[pkij（t）=ταij（t）ηβij（t）s∈allowkταis（t）ηβis（t），j∈allowk0，j?allowk]
式中：
[τ0]——路径（i， j）的信息素浓度；
[nij]——地点间距离的启发式信息，[nij=1/dij]；
α，β——两个启发式信息的参数，决定启发式信息对蚂蚁选择地点影响的程度；
allow——蚂蚁未访问的地点的集合。
以上是个体蚂蚁的行为特征，要想得到局部最优解，需要多只蚂蚁多此寻找路径，一旦发现新的最短路径，就将此路径记录下来。
1.2 PSO的基本原理
在[D]维的搜索空间内，一个由[M]个粒子组成的群体按照一定的速度进行不断运动[7]。粒子[pi]在[t]时刻[D]维空间里的状态如下：
位置记为：[Xti=xti1，xti2，xti3，???，xtid]，i=1，2，3，…，[M]。[xtid∈xmind，xmaxd]，[xmind]，[xmaxd]分别代表搜索空间[D]的下限和上限；
飞行速度为：[Vti=vti1，vti2，vti3，???，vtid]，i=1，2，3，…，[M]。[vtid∈vmind，vmaxd]，
[vmind]，[vmaxd]分别为粒子飞行的最小和最大速度；
个体最优位置：[Pti=pti1，pti2，pti3，???，ptid]，整体最优：[Ptg=ptg1，ptg2，ptg3，???，ptgd]；
其中[1≤d≤D]，[1≤i≤M]，粒子群算法进行优化迭代中，则粒子[pi]在[t 1]时刻按照以下公式进行速度的不断更新和位置的不断更新：
PSO的基本算法步骤大概描述如下：
（1）初始化。设PSO中各类参数：搜索空间[D]的下限[xmind]和上限[xmaxd]；学习因子[c1]，[c2]；算法最高迭代次数[Tmax]和寻优误差系数[θ]；粒子的速度上限和下限为[vmind]，[vmaxd]。随机初始化各个粒子的速度[vi]和位置[xi]。
（2）计算和评价每一个粒子的适应值，并记录粒子的个体极值[Pti]和全局极值[Ptg]。
（3）将粒子个体历史的最好位置[Pti]的适应值于当前粒子位置适应值进行比较，[Pti]取优。
（4）将每个粒子的位置的适应值和全体粒子最佳位置[Ptg]的适应值做比较，[Ptg]取优。
（5）根据以上公式更新粒子的速度和位置。
（6）检验是否满足结束条件。如果当前的迭代次数达到了最高迭代次数[Tmax]或结果误差小于寻优误差系数[θ]，那么停止迭代，输出最优解。否则转到步骤（2）。
1.3 算法融合
PSO收敛速度较慢，易陷入局部优先，而ACO的搜索具有很大的盲目性。本文針对两算法的缺点和实际交通路径规划在计算时间和精度上的高要求，分别对ACO和PSO做出改进，建立混合型算法，模糊缺点，发挥各自在路径搜索上的优势。
利用粒子群算法得到一组优化路径，然后在整体的环境已经加入相同信息素，再从这组路径中选取部分路径，加大信息素浓度作为蚁群算法新的初始化信息素，从起点和终点一起进行精搜索，从而形成双向搜索模式，选出最优路径。所谓最优，并不是指路程最短，而是时间与路程的结合分析。从[O]点到[D]点的所有路径中，经过粒子群的筛选，以下三条路径可以作为蚁群算法的初始路径。 2 仿真实例
2.1 仿真环境
Transmodeler软件是目前应用比较广泛的仿真软件之一。本文使用的是Transmodeler4.0版本，此可以详细仿真从高速公路到城市道路各种道路网以及公交站点等设施[8]。二次开发是Transmodeler软件最大的特性，可以使此软件按照开发者需求或者城市道路变化需求完成有针对性的系统重构，建立一个针对城市道路智能控制算法验证的仿真软件平台。
2.2 实例模拟
选取2016年5月15上午9点到10点为仿真时间段，从内蒙古工业大学新城校区出发，目的地为呼和浩特市植物园。通过PSO-ACO融合算法，选出最优路径。
拟定工大新城校区到呼市植物园路线为仿真背景，在实际地图上设置城市路网（如图2），加入仿真流量，模拟区域简单仿真环境。步骤如下：
Transmodeler4.0软件打开地图“全景1.jpeg” →建立Simulation Project，并使用Road Editor工具箱，根据实况建立城市主干道、快速路、十字路口等仿真环境→加入仿真流量，以蓝色路径为仿真背景，通过设置车型、车速，以及各个路口的转向流量等，真实的模拟车辆行驶路径。
在9：01时，从工大南门出发自驾沿着爱民街直行，到达呼伦贝尔北路，向南经历第三个十字路口时，向西进入新华大街，通过两个路口进入新华西街，在9：15时到达呼和浩特市植物园。总历程将近14分钟，其中车辆速度根据实际情况不断变化，最高达到72.4km/h。
3 结论
本文将粒子群和蚁群算法相结合，从始发到终点的路径中，有效的选出相对最优的路径，并通过运用Transmodeler4.0软件加入实例，对两节点间的多条路径的距离和时间进行对比分析，为城市道路优化和出行提供了可靠的依据，并为智慧城市的研究提供很大帮助。
参考文献：
[1] 刁阳， 隽志才. 基于仿真的城市路网动态分配矩阵估计方法[J]. 系统管理学报， 2011， 20（3）：376-383..
[2] 赵明翠， 成卫， 戢晓峰，等. 基于TransCAD与TransModeler的交通影响分析方法[J].科学技术与工程， 2010， 10（27）：6689-6694.
[3] 吴义虎， 李宁，王正武. 蚁群算法在车辆路径诱导系统中的应用[J].系统工程， 2007， 25（2）：27-31.
[4] 宋世杰， 刘高峰，周忠友，等. 基于改进蚁群算法求解最短路径和TSP问题[J].计算机技术与发展， 2010， 20（4）：144-147.
[5] 李晓东， 王东， 曾凡智，等. 城市交通时間最短路径计算模型及应用仿真[J].计算机仿真， 2014， 31（1）：172-175.
[6] 杨慧， 成卫， 肖海承，等. 基于TransModeler的拥堵区域交通流量调控方法研究[J].科学技术与工程， 2011， 11（8）：1746-1750.