Developing Combined Genetic Algorithm – Hill Climbing Optimization Method for Area Traffic Control
Halim Ceylan
Abstract
This study develops a Genetic Algorithm with TRANSYT Hill-Climbing optimization routine, referred to as GATHIC, and proposes a method for decreasing the search space, referred to as ADESS, to find optimal or near optimal signal timings for area traffic control (ATC). The ADESS with GATHIC model is an algorithm, which solves the ATC problem to optimize signal timings for all signal controlled junctions by taking into account co-ordination effects. The flowchart of the proposed model with ADESS algorithm is correspondingly given. The GATHIC is applied to a well-known road network in literature for fix sets of demand. Results showed that the GATHIC is better in signal timing optimization in terms of optimal values of timings and performance index when it is compared with TRANSYT, but it is computationally demanding due to the inclusion of the Hill-Climbing method into the model. This deficiency may be removed by introducing the ADESS algorithm. The GATHIC model is also tested for 10% increased and decreased values of demand from a base demand.
CE Database Subject headings: Traffic control, Traffic delay, Optimization models, Genetic Algorithms
1. Introduction
Traffic signal control is a multi-objective optimization encompassing delay, queuing, pollution, fuel consumption and traffic throughput, combined into a network performance index (Akcelik, 1981). It can be either stage-based (e.g. TRANSYT) or group-based (e.g. SIGSIGN) (Silcock and Sang, 1990; Allsop, 1992). Signal optimization applies to several decision variables, such as green time, cycle length, stage sequence and offset. The optimization of signal timing for an isolated junction is relatively straight forward, but
optimizing the timing in dense networks where the distances between the intersections are too small to dissipate the platoons of traffic is a difficult task. The difficulty comes from the complexity of the signal co-ordination. Optimization of signal timings is well established at individual junctions (Heydecker and Dudgeon, 1987; Gallivan and Heydecker, 1988; Allsop, 1992; Heydecker, 1992), but optimization of timings in coordinated signalized networks requires further research due to the offsets and the common network cycle time. The reason for further research to optimize the offset and network cycle time in coordinated signalized networks is at least two fold: One is the non-convexity of the problem when it is formulated as a mathematical program, and the second is that there is no feasible constraint for the start of the green (i.e. signal offsets), thus it is an unconstraint optimization problem.
Among the current optimization models for area traffic control, TRANSYT is one of the most useful network study software tools for optimizing splits, offsets and stage ordering and also the most widely used program of its type. TRANSYT was developed by TRRL (Robertson, 1969) and is a stage-based optimization program. Main features of TRANSYT are: The cyclic flow profile and platoon dispersion models, and the hill-climbing algorithm. It consists of two main parts: A traffic flow model and a signal timing optimizer. The traffic model in TRANSYT (Vincent et al., 1980) is a deterministic, mesoscopic, time-scan simulation. It simulates traffic in a network of signalized intersections to produce a cyclic flow profile of arrivals at each intersection and to compute a performance index (PI) for a given signal timing and staging plan. The performance index is defined as the sum for all signal-controlled traffic streams of a weighted linear combination of estimated delay and number of stops per unit time. The PI is evaluated by the cyclic flow profile model of traffic movement and a simple analytical expression in all the links and is used to measure the overall cost of traffic congestion.
The optimization procedure in TRANSYT is based on an iterative search technique known as lsquo;Hill-Climbingrsquo; (HC), which basically searches for the best signal timings by a trial and error method. The HC consists of two kinds of signal setting variables; the offset, which affects the coordination between junctions, and the stage start and end times. It can be derscribed as follows:
First, TRANSYT calculates the performance index for an initial set of signal timings, in which all constraints are satisfied for considerations of safety. Next, one of the signal control variables is changed by a predetermined number of steps and the corresponding value of performance index is calculated. If the calculated value of performance index decreases, which means the system performance is improved as the signal setting variable changes in that direction by the predetermined number of steps, the signal setting variable is altered in the same direction by the same number of steps until a minimum value of the performance index is obtained. On the other hand, if the calculated value of performance index does not decrease, which shows that the system performance is not improved as the signal setting variable changes in that direction, the same variable is altered in the opposed direction by the same number of steps until a minimal value of the performance index is obtained. This process continues for each signal setting variable in the road network in turn. The steps by which the different variables are changed can be determined in advance (see for details, Vincent et al., 1980).
The HC uses the iterative improvement technique, which is applied to a single point in the search space. A new point is selected from the neighborhood of the current point. If the new point provides a better value of the objective function, the new point beco
全文共18212字，剩余内容已隐藏，支付完成后下载完整资料
发展结合遗传算法-针对区域交通控制的爬山优化方法
Halim Ceylan
摘要
本研究利用TRANSYT爬山优化程序（称为GATHIC）开发了一种遗传算法，并提出了一种减少搜索空间（称为ADESS）的方法，以找到区域流量控制（ATC）的最优或近似最优信号时序。具有GATHIC模型的ADESS是一种算法，其解决了ATC问题，通过考虑协调效应来优化所有信号控制路口的信号定时,相应地给出了使用ADESS算法提出的模型的流程图。 GATHIC应用于知名的文献路网，用于修复需求。结果表明，与TRANSYT相比，GATHIC在时序和性能指标的最优值方面优于信号时序优化，但由于将爬山算法纳入模型，计算量要求较高。可以通过引入ADESS算法来消除此缺陷。 GATHIC模型也从基础需求中测试了10％的需求增长和减少的值。
CE数据库关键词:交通控制、交通延迟、优化模型、遗传算法
命名系统：
Delta;psi;i =设计变量的精度
psi;min=信号定时的整个下限矢量
psi;max=信号定时的整个上限向量
phi;= [phi;m; forall;nisin;N]是绿色时间的向量，其中元素phi;是绿色的持续时间
对于我在交叉点n的阶段
theta;= [theta;1n; forall;nisin;N]是相对于a的每个连接点处的阶段1的绿色开始向量
网络作为一个整体的任意时间原点，即信号偏移psi;=（c，theta;，phi;）可行信号定时向量
phi;max=每级的最大允许绿色时间m（秒）
phi;min=每级最小允许绿色时间m（秒）
Omega;0=可行信号定时的整向量
Theta;i=由时序变量的二进制表示产生的整数
c =公共周期时间（秒）
ccrit =公共周期时间的临界值（秒）
cmax =最大可接受公共周期时间（秒）cmin =最小可接受公共周期时间（秒）
copt =最佳周期时间（秒）
Da = L中链路a上的车辆延迟 - 小时/小时
I = intergreen时间（秒）
2
K =每100个车辆的总成本
ka =在每单位时间链接a上停止加权因子
L = {1,2,3，...，NL}是一组NL链路，其中每个流量流接近任何连接点
由自己的链接代表
l =染色体长度
M =所有信号控制接点处的总级数
m =每个信号交界处的级数
N = {1,2,3，...，Nj}是一组Nj个节点，每个节点表示信号控制的连接点
PI =网络性能指数（pound;/ h或veh / h）
pz =人口的大小
q = L中的链路a的平均到达流量（以车辆/小时为单位）的向量
sa = L中链接a上的车辆停靠点数
T =进行估计的周期（小时）
W =延迟的平均车辆总成本
wa =每单位时间链接a上的延迟和停止加权因子
x =群体中染色体的载体
z =信号网络中控制变量的数量
- 介绍
交通信号控制是一个包含延迟，排队，污染，燃料消耗和流量吞吐量的多目标优化，并入网络性能指标（Akcelik，1981）。它可以是基于阶段的（例如TRANSYT）或基于组的（例如SIGSIGN）（Silcock和Sang，1990; Allsop，1992）。信号优化适用于多个决策变量，如绿色时间，周期长度，阶段序列和偏移量。隔离结的信号定时优化比较直观，但是优化密集网络中交叉点之间的距离太小而不能消除交通排的时间是一项艰巨的任务。困难来自于信号协调的复杂性。信号时序的优化在单个路口已经很好地建立（Heydecker和Dudgeon，1987; Gallivan和Heydecker，1988; Allsop，1992; Heydecker，1992），但协调信号网络中的时序优化需要进一步的研究，由于偏移和常见网络周期时间。进一步研究优化协调信号网络中的偏移和网络周期时间的原因至少有两个方面：一个是问题的非凸性，当它被制定为数学程序时，第二个是没有可行的绿色启动的约束（即信号偏移），因此是一个非约束优化问题。
在目前区域流量控制优化模型中，TRANSYT是最有用的网络研究软件工具之一，用于优化分割、偏移和阶段排序，也是最广泛使用的类型的程序。 TRANSYT由TRRL（Robertson，1969）开发，是基于阶段的优化程序。 TRANSYT的主要特点是：循环流动剖面和排排列模型，以及爬坡算法。它由两个主要部分组成：交通流模型和信号时序优化器。 TRANSYT中的流量模型（Vincent et al,，1980）是一个确定性的介观时间扫描模拟。它模拟信号交叉口网络中的流量，以产生每个交点处的到达的循环流程曲线，并计算给定信号时序和分段计划的性能指标（PI）。性能指标被定义为估计延迟和每单位时间停止次数的加权线性组合的所有信号控制业务流的和。 PI通过流量运动的循环流分布模型和所有链路中的简单解析表达式进行评估，并用于测量交通拥堵的总体成本。
TRANSYT中的优化过程基于称为“爬山算法”（HC）的迭代搜索技术，其基本上通过试错法搜索最佳信号时序。 HC由两种信号设置变量组成；偏移量，影响交汇点之间的协调，以及舞台开始和结束时间。可以描述如下：
首先，TRANSYT计算初始信号时序集的性能指标，其中满足安全考虑的所有约束条件。接下来，一个信号控制变量被改变预定的步数，并且计算相应的性能指标值。如果计算出的性能指标值降低，这意味着随着信号设定变量沿着该方向改变预定步数，系统性能得到改善，信号设定变量在相同方向上以相同的步数改变，直到获得性能指标的最小值。另一方面，如果计算出的性能指标值不降低，这表明随着信号设定变量在该方向上变化，系统性能没有改善，则相同的变量在相反方向上被改变相同的步数直到获得性能指标的最小值。这个过程将继续进行道路网络中的每个信号设置变量。可以提前确定不同变量的改变步骤（详见Vincent等，1980）。
HC使用迭代改进技术，其应用于搜索空间中的单个点。 从当前点的附近选择一个新点。 如果新点提供更好的目标函数值，则新点将成为当前点。如果不能进一步改进，则终止。另一方面，遗传算法（GA）通过维护潜在解决方案的总体来进行多方向搜索，并鼓励这些方向之间的信息交换。
GAs是一个由进化启发的计算工具系列。 这些算法对简单的染色体串如数据结构编码一个特定问题的潜在解决方案，并将重组算子应用于这些结构，以便保留关键信息，并产生一个新的群体，其目的是生成映射到高函数值的字符串。 GA利用衍生自生物学的概念。 利用GAs的关键点是基于达尔文的适者生存理论。 基于生物进化原理的分析和设计的范例一直在20世纪60年代以来，GAs领域的早期发展普遍得到肯定。
本研究包括二进制编码GA的实现。本地交互规则取代了传统的随机选择操作和交叉。演化过程是用概率转换规则在本地进行的。每个站点包含信号时序的二进制位描述。 GA的收敛特性通过使用洗牌机制得到改善，该随机机制在突变操作之后随机将人群中的成员重新定位到搜索空间内的新位置。这允许在当地社区引入新的信息。将GA的系数表示为二进制字符串需要确定位串长度。下限值对应于全零位（0000 ...），而上限值对应于所有一位数字（1111 ...）。
GA与基于健身评估进行的表达操作一起工作。适应度表示目标函数是健身度量的合理选择。 GA通过最小化TRANSYT流量模型获得的总网络PI来搜索最适合的成员。
GA和HC优化都有优缺点，在全局解决方案和CPU时间方面都有优化例程。 基于人口的搜索试图逃避堕入不良的局部最优。 因此，通过数学组合GA和HC技术可以获得良好的优化程序，以便去除被困的不良局部最优或定位良好的全局最优。 此外，还没有研究减少GA和HC的搜索空间，以便在CPU时间方面可以提高TRANSYT的性能。
TRANSYT-7F第10个版本具有循环长度、阶段序列、分割和偏移的单独遗传算法（GA）优化。 TRANSYT-7F的定相序列优化也可用于整个网络，也可用于每个单独的交点。 但是TRANSYT的任何版本都不能明确地组合GA和Hill Climbing（HC）方法来优化ATC问题的所有信号时序变量。
Heydecker（1996）提出了一种分解方法，以基于组为基础的变量优化个人和网络层面的信号时序。在这种方法中，交替地进行两个优化级别，直到满足某些收敛标准。获得了相当大的计算优势。然而，指出，每个优化水平只能产生次优结果，因此不能保证收敛。每个优化级别都是次优的，因为没有考虑到相邻路口之间协调的影响。
Wong（1996）提出了使用基于组的控制变量对区域交通控制的信号定时进行优化。 TRANSYT性能指标被认为是基于组的控制变量，周期时间，绿色时间的开始和持续时间的函数。在这种方法中，信号时序优化问题被形成为非线性数学程序，其中网络的性能指标在受到一定限制的情况下被最小化。使用整数编程方法解决问题。莱斯特郡的试验网络被用来证明提出的方法的有效性。获得了TRANSYT中基于阶段的方法优化性能指标的10％改进。但是据报道，获得每个控制变量的性能指标的推导在数学上是困难的。另外，提出了随机偏移计算来定位更好的局部最小值，但是它需要更长的计算时间。
关于网络公共周期时间，选择网络中每个节点的最佳周期时间是复杂的，而且仍然是未解决的优化问题。在TRANSYT中，它是根据孤立路口的性能指标进行选择，而不考虑协调的影响。 GA是GA的优点之一，可以将公共周期时间视为优化中的控制变量，从而可以确定与网络协调模式最和谐的方式工作的公共周期时间。
在传统方法中可能会出现困难，因为对于网络中的所有信号控制连接点使用公共周期时间。强制这个所有连接点可能导致生成的序列和级间的次最优性，它们各自分别具有循环时间的自由选择。序列和级间结构的优化通过将每个结点单独重新优化循环时间约束来控制，以等于公共循环时间。如果这导致选择新的序列或级间结构，则可以通过重复的新数据和过程来重新优化公共网络周期时间（Heydecker，1996）。然而，可能需要多次修改序列和级间结构增加了问题的复杂性。因此，为了优化网络级别的公共周期时间，然后调整各个连接点的定时，需要启发式搜索方法，例如组合的GA和HC。
公共周期时间变量只能增加，减少或保持不变。众所周知，循环时间越长，容量越多，延迟越多。此外，网络意味着选择在所有交叉点提供足够能力的周期，但可能在许多交叉点施加不适当的大延迟。因此，需要新的搜索方法将网络公共周期时间作为决策变量并且同时优化单个结点的信号定时（例如绿色时间）。为此，开发了将GA与HC相结合的一步优化启发式，其中公共循环时间减少，增加或保持不变。对于循环时间的每个变化，执行具有HC的GA，具有ADESS称为GATHIC，以找到信号控制网络中的最小PI。虽然TRANSYT-7F可以用GA执行公共循环长度评估，但是Hill-Climbing过程没有优化程序，也没有用于将GA的搜索空间减少为数学程序的算法。
作为上述问题的解决方案，引入了ADESS（用于增加搜索空间的算法）。它提供了一个共同的循环时间，减少，增加或修复，并与GATHIC报告最佳循环时间。利用这种方法，GA搜索空间的CPU时间的缺点也可能被放宽。本研究提出了一种具有HC方法的组合GA，称为GATHIC，并提出了一种减少GA的搜索空间的算法，称为ADESS。
- 遗传算法
遗传算法（GAs）是一个适应性搜索程序的家族，其松散地基于个体群体中遗传变化的模型。 戈德伯格（Goldberg，1989）阐述了GAs，而Gen和Cheng（1997）后来吸引了越来越多的优化问题。 GAs的主要优点是他们能够使用关于初始未知搜索空间的累积信息，以便将后续搜索偏移到有用的子空间中。 GAs与传统的非线性优化技术不同，它们通过维护解决方案群来搜索，从中创建更好的解决方案，而不是对问题的单一解决方案进行增量更改。
- 数值应用
测试网络根据Allsop和Charlesworth（1977）使用的网络进行选择。 图3和图4给出了网络和级配置的基本布局。表1给出了固定链路流的集合。该数值测试包括6个信号控制连接点处的21个信号设置变量。 还对GATHIC模型性能进行了测试，将表1的值降低了10％。
- 结论
本研究通过结合GA和HC方法解决了区域交通控制问题。开发了GATHIC模型，并且通过引入ADESS算法来减少搜索空间，可以消除其在CPU时间方面的缺点。使用GOTHIC的ADDRESS是一种优化启发式，通过同时考虑网络和单个连接级别的协调来优化网络公共周期长度。信号定时参数范围的其他下限和上限在GATHIC方法中也是可能的，但是将该信号定时参数设置为原始水平可以显着增加CPU时间约为13分钟至37分钟。使用ADESS算法，GATHIC的CPU时间改善约为60％。 GATHIC提供了在TRANSYT-HC方法中进一步使用的信号定时。由于用于信号定时优化的一步解算法，该示例的收敛可以被保证。虽然TRANSYT-7F引入了GA优化方法，GATHIC将GA与HC组合，并引入了一种算法来减少GA的搜索空间，以便在优化过程中应对CPU的不利影响。 GATHIC算法对TRANSYT的主要优点是它产生了HC算法的初始信号定时集，并且还优化了网络公共周期时间，其中循环时间的每个变化由ADIS算
全文共5986字，剩余内容已隐藏，支付完成后下载完整资料
资料编号：[144092]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
