基于遗传算法的交通网络的研究 杨长安

1、基于遗传算法的交通网络的研究杨长安，周新志(四川大学 智能控制研究所,四川 成都 610064)摘要：目前城市中的道路错综复杂，如何控制交通网络中的流量使得交通系统中的通行力最大，是交通信息化控制的关键部分。在本文研究中，加入了赌轮选择和小生境混合的自适应遗传算法来研究智能交通问题。本文拥有多个优化目标，利用赌轮选择，增加了全局寻优能力；而利用小生境则是解决我们求多目标优化时，尽可能将整个Pareto最优解分散在集合内；使用自适应适应度函数是为了在计算的过程中避免局部收敛。因此，本遗传算法较传统遗传算法1-2在解决交通网络的问题时，完全避免了标准化误差、统计不完善、局部收敛等问题。关键词：车流

2、量；自适应；遗传算法；局部收敛中图法分类号：U 491.5 文献标识码：A 0引言社会的进步和经济的发展，使现代交通成为了人们生活中必不可少的部分。但随着人们对交通工具需求量增大，城市道路面临着日益拥挤的巨大问题。交通拥挤导致时间延误，交通事故增多，环境污染加剧等问题，严重影响城市的发展和建设。因此，各国迫切希望对城市交通控制系统进行改善，并展开了积极研究。目前解决智能交通问题的方法主要有：专家控制系统、模糊数学控制系统6、基于元胞自动机的城市交通信号自组织控制方法4、遗传算法1-2等。本研究正是使用遗传算法解决交通问题，在本遗传算法中，加入了赌轮选择、小生境及自适应函数等方法，使得交通网络中

3、道路的通行力尽可能最大。1遗传算法运用的设计1.1模型的建立首先我们把要研究的m+n条交错道路所组成的交通系统抽象成一个m+n网络。即横向有m条道路，纵向有n条，每一条直线是一条道路，每一个交叉点就是一个交叉路口。我们对模型进行简化，把东西向道路通过的车辆流看成一个横向的流量，南北向道路通过的车辆流看成一个纵向的流量，即东西横向流量与南北纵向流量。同时在每个交叉口与交叉口之间设立观测点，用于测量它们之间路段的流量设为。由于一条道路上各个路段的流量不一定相同，这里我们把道路各个路段的流量相加求平均，作为整条道路的平均流量：设东西向道路的平均流量为。南北向道路的平均流量为。对任意一个交叉路口横向放

4、行车辆的平均时间设为（），纵向放行车辆的平均时间设为（，）。则单个十字交叉路口一个周期内的横向平均滞留量为:纵向平均滞留量为：所以交叉路口总的滞留量为:其中为该交叉路口的周期，分别为该交叉口的车辆可以离开的最大横纵向流量，即它的通行力。由于研究的需要，我们希望在这个交通系统中总的平均流量尽量大，即:理想情况下，我们已知每个交叉路口的最小滞留量为0，因此把所有的交叉口滞留量加起来求它的最小值：相邻交叉口之间的路段都有最大容量，于是有：,交叉路口横纵向放行的平均时间也应该在一个范围内：然而，针对本研究的交通模型，采用求解多目标优化的方法5-6找出这个模型的最优解，所以综上所述，总的模型应为：1.2

5、赌轮选择 选择将遗传搜索引导到搜索空间中更有前途的区域，是模型的驱动力。针对于多目标优化模型有多个目标函数，搜索空间复杂等特点，利用赌轮选择，增强了空间寻优能力，也避免了标准化误差等选择问题。其基本思想是每个种群的选择概率（即生存概率）正比于它的适应值。计算种群中所有方案适应值的和：根据种群的适应度值，计算相应的选择概率：(k=1,2,pop_size)计算累计概率值： (k=1,2,pop_size)1.3小生境 求解多目标最优化问题时，一般希望所得到的解能尽可能地分散在整个Pareto最优解集合内，而不是集中在其Pareto最优解集合内的某一个较小的区域上。为达到这个要求，可以利用小生境遗

6、传算法。这种方法称为共享函数法，将共享函数的概念引入到求解多目标最优化问题的遗传算法中。算法对相同个体或类似个体的数量加以限制，以便能够产生较多不同的最优解。具体为: 其中为不同个体的共享度；为不同个体的欧式距离；为距离参数,可根据最优解分布情况设定。通过共享函数，可以对种群中聚集在一小块的个体加以惩罚,使其适应度减少。 其中、为共享函数前后个体的适应度值。n为群体规模，是不同于的个体。在计算出各个体的小生境数之后，可以使小生境数较小（相似程度较小）的个体能够有更多的机会遗传到下一代群体中，这样就增加了群体和解的多样性。1.4自动适应的适应度函数在利用遗传算法求解优化模型时，能否收敛到最优解取

7、决于适应度函数的取法。本文针对这类有等式约束的特殊模型提出了相应的自适应适应度函数。设式的适应度函数为，式的适应度函数为。其中为各个群体的值，与是种群排队后的编号。则这个多目标优化模型总的适应度函数为：其中t为函数的权重。t在算法迭代过程中根据实际情况而变化。因为我们要让式等于0或者很接近于0，所以要统计式的最小个体值，即是否为0，或者给一个范围，让群体的最小值小于一个常数，超过这个范围立刻增加权重，从而迫使达到满足等式约束的条件。1.5算法流程图图2 流程图1.6 具体算法步骤第一步 ：先随机生成N组初始群体。 第二步 ：计算适应度值，判断是否满足终止条件，是则退出，否则向下进行。 第三步：

8、把群体先带入式，计算它们的函数值，利用函数值的大小编序号。最小的值编为1，次之编为2，直到n；然后把群体带入，计算它们的函数值，相对于前面式的编号不同。这里最大的值编为1，次之编为2，直到n。然后把它们代入1.4，求种群的整合适应度值。第四步：根据式计算出不同个体的共享度，利用式更新适应度值，再通过1.2计算相应的选择概率。第五步: 采用赌轮选择算法的算子，根据各个种群的适应度选择。第六步 ：使用交叉和变异，并对种群进行重组。为了更好地避免过早收敛，可以当迭代到某一代时，使用一、两次迁徙算子。 第七步：检查看是否满足终止条件。是则退出程序，否则跳转至第三步。2实验仿真设有三纵三横的城市网络，横

9、向的平均流量设为，纵向平均流量设为。设每个交叉口的横纵通行能力相同分别为3.0、3.1、2.9、3.1、3.6、3.1、2.7、3.1、2.5，单位是辆/s。每个十字一个周期的通行时间取120s。便于实验仿真，随机取60个种群（每个种群由9个交叉口流量观测数据构成），迭代200次，代沟取0.9，选择概率取0.85，变异概率取0.04。距离参数，根据最优解分布情况设定。适应度函数取 ，其中是种群在流量适应度值的顺序，是种群在滞留适应度值的顺序，t为权重。根据这个模型要求，我们设定当，t =3；当，t =6；其它t =12。分别用传统GA7和改进GA做实验仿真，图3为传统GA7得出的流量/滞留量仿

10、真图，图4为本文改进的GA得出的流量/滞留量仿真图。图3 传统GA7仿真图图4 改进GA仿真图图中每个点表示一个种群搜索到的值。纵坐标表示滞留车辆，单位辆；横坐标表示流量大小，单位辆/s。从图中可以看出滞留量随着流量的逐渐增大而增多。根据分析需要，我们要统计的是平均流量最大，而总的滞留量又恰好为0 或很接近0 时的值。于是，从图3中可以看出整个交通网络最优流量为3.5823 辆/s,滞留量为6.4625辆。从图4 中可以看出整个交通网络最优流量为4.1248辆/s，滞留量为0.1880辆。针对通过遗传算法得到的最优解，我们求出各条道路的流量与滞留量，进行深入的对比。下面为传统GA7和改进GA分

11、析对比表：表1 最优流量/滞留量关系对比道路传统GA7 改进GA 流量滞留量流量滞留量道路10.51160.92120.58820.0273道路20.63281.14240.72910.0329道路30.59851.07970.68960.0314道路40.65471.18100.75380.0343道路50.45600.82250.65250.0239道路60.61831.11540.71190.0324 表1中各条道路最优流量的单位为辆，滞留量的单位为辆/s。显然，从表1中各条道路流量/滞留量的数据可以对比出，在各条道路中，改进遗传算法得出的流量较大，而滞留量更接近于0。充分说明改进遗传算

12、法得出的效果更好。于是通过实验仿真，我们就得出了一个城市交通网络各条道路的最优平均流量，即交通网络的最大通行能力。因此，只要控制住流入每条路的平均流量，就可以让一个交通系统处于最优效率中。3结论本文主要讨论遗传算法在交通网络控制中的运用。通过对各个交叉路口设置观测点，监测出各个交叉路口的流量，计算各条道路的平均流量，通过遗传算法的模型计算，得出整个交通网络系统中的最优流量。如果处理的交通网络较大，会有多个等式约束条件。本文采用解多目标优化模型的方法5-6，先通过计算适应度值将多目标转换成单一优化模型，利用小生境将整个Pareto最优解分散在集合内，再通过赌轮选择算子，得到选择概率，通过反复迭代

13、遗传种群，得出多个Pareto解。最后选择流量最大而滞留接近为0的那个解，即整个交通系统的最优流量。参 考 文 献 1陈国良. 遗传算法及其应用M. 北京: 人民邮电出版社. 2001:69-478.2王小平, 曹立明. 遗传算法M. 西安: 西安交通大学出版社. 20023Langton. C G Studying Artificial Life With Cellular Automata. Physica 22D,1986:120-149.4姚亚夫, 曹锋. 多路口模糊控制及其仿真研究J.机械工程与自化. 2006(3):108-112. 5Deb K, Pratap A, Agarwal S, Meyarivn T1.A Fast and Elitist Multi-objectiv