第２７卷第６期　计算机仿真　２０１０年６月　文章编号：１００６—９３４８（２０１０）０６—０３０５—０４　

基于自适应遗传算法的交通信号配时优化　

田丰，边婷婷　（沈阳航空工业学院计算机学院，辽宁沈阳１１０１３６）　摘要：研究城市交通信号设置问题中对单交叉口多相位交通流建立了动态信号配时模型，以交叉口车辆平均延误最小为控　制目标，以相位绿灯时间和周期时长为控制变量，并运用自适应遗传算法对控制变量进行优化。根据实时交通流数据，通过　ＭＡＴＬＡＢ平台进行仿真。结果表明，自适应遗传算法能够有效降低车辆平均延误，在优化过程中比简单遗传算法具有更好　的搜索能力和解质量，其良好的优化性能有助于优良配时方案的产生，同时也提高了交通分配模型的实用价值。　关键词：交通控制；自适应遗传算法；信号配时优化　中图分类号：Ｕ４９１．５１　文献标识码：Ａ　

Ｔｒａｆｆｉｃ　Ｓｉｇｎａｌ　Ｔｉｍｉｎｇ　Ｏｐｔｉｍｉｚａｔｉｏｎ　Ｂａｓｅｄ　ｏｎ　Ａｄａｐｔｉｖｅ　Ｇｅｎｅｔｉｃ　Ａｌｇｏｒｉｔｈｍ　

ＴＩＡＮ　Ｆｅｎｇ，ＢＩＡＮ　Ｔｉｎｇ—ｔｉｎｇ　（Ｃｏｌｌｅｇｅ　ｏｆ　Ｃｏｍｐｕｔｅｒ　Ｓｃｉｅｎｃｅ，Ｓｈｅｎｙａｎｇ　Ｉｎｓｔｉｔｕｔｅ　ｏｆ　Ａｅｒｏｎａｕｔｉｃａｌ　Ｅｎ￣ｎｅｅｒｉｎｇ，Ｓｈｅｎｙａｎｇ　Ｌｉａｏｎｉｎｇ　１１０１３６，Ｃｈｉｎａ）　ＡＢＳＴＲＡＣＴ：Ａ　ｄｙｎａｍｉｃ　ｔｒａｆｆｉｃ　ｓｉｇｎａｌ　ｔｉｍｉｎｇ　ｍｏｄｅｌ　ｏｆ　ｍｕｈｉｐｈａｓｅ　ｔｒａｆｆｉｃ　ｆｌｏｗ　ｉｓ　ｅｓｔａｂｌｉｓｈｅｄ　ｆｏｒ　ｓｉｎｇｌｅ　ｉｎｔｅｒｓｅｃｔｉｏｎ，ｉｎ　ｗｈｉｃｈ　ｔｈｅ　ａｖｅｒａｇｅ　ｖｅｈｉｃｌｅ　ｄｅｌａｙ　ｉｓ　ａｄｏｐｔｅｄ　ａｓ　ｔｈｅ　ｃｏｎｔｒｏｌ　ｏｂｊｅｃｔｉｖｅ，ｔｈｅ　ｐｈａｓｅ　ｇｒｅｅｎ　ｔｉｍｅｓ　ａｎｄ　ｃｙｃｌｅ　ｔｉｍｅ　ａｓ　ｔｈｅ　ｃｏｎ—　ｔｒｏｌ　ｖａｒｉａｂｌｅｓ．Ａｄａｐｔｉｖｅ　ｇｅｎｅｔｉｃ　ａｌｇｏｒｉｔｈｍ　ｉｓ　ｕｓｅｄ　ｆｏｒ　ｏｐｔｉｍｉｚｉｎｇ　ｔｈｅ　ｃｏｎｔｒｏｌ　ｖａｒｉａｂｌｅｓ．Ｌａｒｇｅ　ａｍｏｕｎｔｓ　ｏｆ　ｓｉｍｕｌａｔｉｏｎ　ｗｉｔｈ　ＭＡＴＬＡＢ　ａｒｅ　ｅｘｅｃｕｔｅｄ　ｂａｓｅｄ　ｏｎ　ｔｈｅ　ｒｅａｌ—·ｔｉｍｅ　ｔｒａｆｆｉｃ　ｆｌｏｗ　ｄａｔａ　ｏｆ　ａ　ｐｒａｃｔｉｃａｌ　ｉｎｔｅｒｓｅｃｔｉｏｎ．Ｔｈｅ　ｒｅｓｕｌｔｓ　ｓｈｏｗ　ｔｈａｔ　ａｄａｐｔｉｖｅ　ｇｅｎｅｔｉｃ　ａｌｇｏｒｉｔｈｍ　ｃａｎ　ｅｆｆｅｃｔｉｖｅｌｙ　ｒｅｄｕｃｅ　ｔｈｅ　ａｖｅｒａｇｅ　ｖｅｈｉｃｌｅ　ｄｅｌａｙ，ａｎｄ　ｃｏｍｐａｒｅｄ　ｗｉｔｈ　ｓｉｍｐｌｅ　ｇｅｎｅｔｉｃ　ａｌｇｏ－　ｒｉｔｈｍ，ｉｔ　ｈａｓ　ｂｅｔｔｅｒ　ｓｅａｒｃｈ　ｃａｐａｂｉｌｉｔｙ　ａｎｄ　ｓｏｌｕｔｉｏｎ　ｑｕａｌｉｔｙ．Ｔｈｅ　ｇｏｏｄ　ｏｐｔｉｍｉｚｅｄ　ｐｅｒｆｏｒｍａｎｃｅ　ｉｓ　ｈｅｌｐｆｕｌ　ｔｏ　ｓｕｐｅｒｉｏｒ　ｔｉｍ—　ｉｎｇ　ｐｌａｎ　ｐｒｏｄｕｃｔｉｏｎ，ａｎｄ　ａｌｓｏ　ｉｍｐｒｏｖｅｓ　ｔｈｅ　ｖａｌｕｅ　ｏｆ　ｔｒａｆｆｉｃ　ｓｉｇｎａｌ　ｔｉｍｉｎｇ　ｍｏｄｅ１．　ＫＥＹＷＯＲＤＳ：Ｔｒａｆｆｉｃ　ｃｏｎｔｒｏｌ；Ａｄａｐｔｉｖｅ　ｇｅｎｅｔｉｃ　ａｌｇｏｒｉｔｈｍ；Ｓｉｇｎａｌ　ｔｉｍｉｎｇ　ｏｐｔｉｍｉｚａｔｉｏｎ　

１　引言　随着经济的发展和城市化水平的提高，城市交通问题日　益突出。对城市交叉路口交通实施合理优化控制，有利于缓　解日趋紧张的交通拥挤问题，提高交通效益。城市交通信号　控制的核心在于各相位绿信比的分配，而信号设置合理与否　直接影响运行效率，乃至整个路网功能的发挥。对于如何快　速、合理地获得最优控制方案，众多学者对此进行了广泛研　究，如黄金分割法、爬山法、网格搜索法等，同时也有不少学　者将人工智能理论用于配时优化研究中，如蚁群算法、遗传　算法、免疫算法…等。　遗传算法是一种基于自然选择和进化的搜索技术，广泛　应用于优化领域　。诸多实例证明遗传算法是一种高效的　全局寻优算法，但同时也暴露出一些不足，容易造成未成熟　收稿日期：２００９—０４—２０修回日期：２００９—０５—０４　收敛，且收敛速度易受参数的影响　。因此，为了提高遗传　算法在交通配时优化中的搜索能力，实现信号配时优化更加　合理化，本文将自适应遗传算法应用于交叉１３信号配时优化　中进行研究。　

２动态交通信号配时模型　交通信号控制的目的在于最大限度地提高交叉１３的使　用效率，满足路１３的交通需求。由于路况延误时问越长，路　段运行时间也越长，如需缩短路段运行时间，就必须缩短路　口的延误时间　］。因此本文以实时采集的路上交通流数据　为基础，以交叉１３各相位各进１３道上的车辆平均延误最小为　优化目标，优化参数为信号周期时长及各个相位绿灯的时　间，通过确定信号周期最优化相位绿灯时间，使得控制周期　内路口的车辆平均延误最小。　每辆车在交叉口的平均延误ｄ，根据Ｗｅｂｓｔｅｒ延误公　式　为：　３０５．．．——　ｄ＝特　＋　㈩　。一　一至　ｃ　（１－Ａ　ｉ）　２：　％２　——　—一　

ｅ≤ｔ　≤ｃ—ｌ一１０×。　４　∑ｔ　＝ｃ—ｌ　

ｌ＝ｌ　ｃ　ｉ　≤ｃ≤ｃ　

（４）　

ｅ为每相位的最小绿灯时间（这里取最小绿时为１０ｓ），１　为交叉口总损失时间／ｓ；ｃ　；　和ｃ一分别为最小周期和最大　周期。　

３遗传算法的交通配时优化　采用自适应的遗传算法，对信号配时参数进行优化。在　遗传操作中的采用（　＋Ａ）选择算子，增加种群的多样性；同　时引入自适应的交叉和变异概率。克服了传统遗传算法早　熟收敛的弊端，并提高了全局寻优能力。具体操作步骤　如下。　３．１染色体编码　为了提高算法的运行速度，本文算法采用实数的表示方　式。以每个相位绿灯时间为决策变量，染色体形式为ｔ：＜　ｔｌ，ｔ２ｔ３，ｔ　＞，其中，ｔ‘（ｉ＝１，２，３，４）表示相位ｉ的绿灯时间，　范围在［ｔ　，　～］。染色体采用实数编码，由于路口周期一　般不超过１５０ｓ，因此每个基因座设定为３位，基因长度为３×　４＝１２位。如：ｔ：＜０３００２８０２２０２０＞，则第１—４相位的绿灯　时间依次为：３０ｓ，２８ｓ，２２ｓ，２０ｓ。为了避免产生无效基因，本　文在交叉和变异中，以基因座为单位进行操作。　３．２适应度函数　三为目标函数，选择适应度函数为：　，＇：』ｍ—Ｌ　ｍ≥Ｌ　（５）　ｔＯ　ｍ＜Ｌ　ｍ为一个足够大的正整数。　３．３遗传算子　选择算子，交叉算子和变异算子是遗传算法的三大基本　３０６．．．——　遗传算子，这些参数的选择将直接影响算法的性能和搜索速　度，所以选择合适的遗传算子是算法能高效收敛到全局最优　解的关键所在。　３．３．１选择策略　针对传统简单遗传算法中使用赌轮选择容易造成超级　个体的影响，产生非成熟收敛　，在自适应遗传算法中选择　了（　＋Ａ）选择算子进行运算，增强种群的多样性。先复制　父代，将父代备份进行交叉和变异，然后在父代和得到的新　种群中选择适应度最好的个体组成新的父代。　３．３．２自适应交叉算子　交叉算子采用单点交叉。在遗传算法中，交叉概率过　大，新个体产生的速度就越快，然而遗传模式被破坏的可能　性越大，使得具有高适应度的个体结构很快就会被破坏；如　果过小，会使搜索过程缓慢，以至停滞不前。为此，交叉概率　选用自适应交叉概率　，在保持群体多样性的同时，保证了　遗传算法的收敛能力，有效提高遗传算法的优化能力。　交叉概率公式如下：　一　：ｊｐｒｌ一——７＝＝　一　（６）　【Ｐ。。　≥丘　Ｐ。　＝０．９，Ｐ　：０．６。ｆ　是交叉的两个个体中适应度较大的　值．√ｎ删　分别为当前种群的平均适应度和个体的最大适应　度。由公式可以看出，当，　较大时，Ｐ　较小，当，　较小时，Ｐ　较大，有利于保留种群中较好的个体。　３．３．３自适应变异算子　为防止非成熟收敛，在变异概率上选用自适应变异　概率　Ｊ：　ｒ　（ｐ　ｌ　一　二　！：　二　ｌ一一ｌ　ｇ　≥　（７）　＜ｌ　ｇ　Ｐ　ｌ＝０．１，ｐｍ２：０．００１。　变异算子采用非均匀变异，假设有一个体为Ｘ＝　。，　：…　若钆为变异点，取其值范围为［ｆ　，￡　］，在该点对　个体　进行均匀变异操作后，可得到一个新的个体Ｘ＝　。，　其中变异点的新基因座的值是：　△（ｇ，　一ｋ　）ｉｆｒａｎｄｏｍ（０，１）～（８）　Ｌ＝《　６　Ｊ　

Ｌ　＾一△（ｇ，　一＃　ｉ　）ｉｆ　ｒａｎｄｏｍ（０，１）＝１　

／ｔ（ｇ，Ｙ）中Ｙ代表　一　和机一￡：　ａ（ｇ，Ｙ）定义为：　△（ｇ，Ｙ）＝Ｙ·（１一ｒ‘　。　）　（９）　式中，ｒ为Ｅｏ，１］范围内符合均匀概率分布的一个随机数，Ｇ　是最大进化代数。　非均匀变异实现了在其初始运行阶段（最初ｇ较小时）　进行均匀搜索，而在其后期运行阶段（ｇ较接近于Ｇ时）搜索　范围逐渐减小，满足了初期大范围、后期小范围搜索的要求，　有利于收敛于全局最优值和提高搜索精度。　３．４停止条件　以ｓｔｏｐ＝Ｅ（ｆ）为终止条件，Ｅ（ｆ）为种群的平均适应度，　即如果ｓｔｏｐ的值连续超过阀值次数不发生变化，则停止进　化。阀值一般为种群大小的１／３。为了防止迭代永无休止，　规定最大迭代次数。　３．５算法实现　１）在可行域内随机产生初始父代种群Ｐ（ｔ），并将种群　中的个体采用实数编码。　２）计算个体的适应度，并判断是否符合终止条件，若符　合，输出最佳个体及其代表的最优解，用作实际路口绿灯控　制，并结束计算；否则转向第３）步。　３）复制父代。　４）以自适应交叉率进行单点交叉，生成新种群ＰＣ（ｔ）　种群。　５）对ＰＣ（ｔ）种群进行非均匀变异，采用自适应变异率，　生成种群ＰＭ（ｔ）。　６）运用选择运算从Ｐ（ｔ）、ＰＭ（ｔ）中选择出新种群作为下　次遗传的父代Ｐ（ｔ＋１）。　４仿真实验　本文以４相位为例，各相位车流如图１。　第一相位　第二相位　ｊｉ　Ｌ　Ｉ　Ｌ　］ｆ　］１厂　第三相位　第四相位　图１相位车流图　实测了沈阳市某繁华交叉路口晚高峰时段各进Ｅｌ道的　车辆相关数据。见表１。　表１车辆相关数据　采用Ｍａｔｌａｂ平台中的语言分别对自适应遗传算法和简　单遗传算法编写程序，对目标函数进行仿真计算。仿真过程　中的一些具体参数设置为：最大进化代数和初始种群大小为　分别为１００和５０，简单遗传算法的交叉率和变异率分别取为　０．９和０．Ｏ１，最大周期设为１５０ｓ，周期损失时间为ｌＯｓ。分别　利用简单遗传算法和自适应遗传算法对目标函数进行１００　次优化计算，取１００次优化计算中的最优解进行比较，优化　结果见表２。　表２算法优化结果对比　

定时控制　遗传算法　自适应遗传算法　各相位绿时／ｓ　５Ｏ，２０，４５，２Ｏ　３Ｏ，２２，３Ｏ，３Ｏ　进化代数——　６９　平均延误／（ｓ·ｖｅｈ　）４９．５４８９　１８．７９１５　由表２可知，就控制效果而言，简单遗传算法和自适应　遗传算法在交叉路口信号配时优化控制效果明显优于传统　的定时控制效果。而基于自适应遗传算法优化效果又优于　简单遗传算法。简单遗传算法最优解为１８．７９１５，需进化代　数为６９，而自适应遗传算法最优解为１７．６４５１，进化代数为　４７。进化过程如图２。