遗传算法的改进及其在城市交通信号优化控制中的应用研究
|
摘要
遗传算法是模拟自然界遗传机制和生物进化论而成的一种随机搜索优化方法,由于其隐含并行性和较强的全局搜索特性,使其具有其他常规优化算法无法拥有的优点。然而,与经典的方法比较,遗传算法还是一门新兴的学科,无论是在其理论上还是实现方法上都有待进一步完善,只有对其不断的改进,才能更好地发挥遗传算法的性能和特点,使其更广泛的应用于工程实践。
在对遗传算法的基本原理、基本要素以及理论基础等进行详细分析后,本文针对基本遗传算法在应用中存在的局限性,提出了相应的改进措施:(1)从遗传算法自身的角度出发,采用了小生境技术的遗传算法,结合精英保留策略、种群多样性保持方案、新的适应度值标定方式、改进的自适应交叉和变异率对基本遗传算法进行改进;(2)在遗传算法的搜索过程中融合局部搜索能力强的梯度法,构成混合遗传算法来提高运行效率和求解的质量。
随着国民经济的不断增长,人民生活水平的不断提高,汽车进入寻常百姓家中业已成为现实,随之而来的城市交通问题则日益突现出来。因此,采用现代科学手段,研究一些智能化的方法来解决城市交通管理问题,就成为当务之急。为了缓解城市交通拥挤,本文在分析了城市道路单交叉路口交通流特性的基础上,首先建立了以车辆平均延误时间最短,以相位有效绿灯时间和饱和度为约束条件的非线性函数模型,利用混合遗传算法对模型进行求解,得到在固定周期下的最优配时方案。仿真结果表明获得了理想的效果,表现了混合遗传算法的优越性。其次,针对交叉路口的拥挤状况,建立了以控制周期内路口的总的排队长度最小为目标,以相位有效绿灯时间和周期时长为控制变量的交通信号优化控制模型,利用改进的遗传算法对模型进行多次仿真计算,结果表明本文的优化控制方法能够使控制周期内路口的总延误排队车辆数明显减少,同时也体现了改进的遗传算法在解的稳定性、最优性和收敛速度等方面都优于基本遗传算法。
Genetic algorithm is a random searching and optimizing method which simulates natural descendiblity mechanism and biology evolution theory. This method has some advantages that other usual methods don't have because of its twocharacters——implicit parallelism and global searching. But after all, geneticalgorithm is a newborn optimizing method and both its theory and its realization need to be improved. Only in this way, can genetic algorithm apply to the practice more effectively and widely.
After basic theory , basic factors and theory base of genetic algorithm being introduced detailedly, aiming at limitations on application of the simple genetic algorithm, this thesis bring forwards some improving measures: (1) From genetic algorithm itself, the niche technique is adopted and it combines elitists reservation model, scheme of keeping population diversiform, mode of demarcating fitness, improved adaptive crossover and mutation rate to improve basic genetic algorithm. (2) During the period of searching of genetic algorithm, blending steepest descent method whose ability of local searching is strong, forming hybrid genetic algorithm to enhance efficiency of circulating and quality of computing.
With the development of our national economy and the improving of the civilian living standard level, the car has been popular for every one. The problem of urban traffic is increasingly serious. So it is urgent for all of us to solve this problem by adopting modern scientific technology and intelligent method. In order to mitigate city traffic jam, the traffic flow characteristics of urban intersections were analyzed. firstly, a nonlinear function model of urban single—point intersections was established, in which shortest average delay of vehicles were taken as objectives, and phase effective green time, saturation degree were taken as restrictions, the objective function of the model was solved by hybrid genetic algorithm. Solved result indicates that obtaining perfect effect, which manifests the advantage of hybrid genetic algorithm. Secondly, aiming at crowd status of intersection, an urban intersection controlling model was established, in which shortest total queue length of vehicles were taken as objectives, phase effective green time and cycle time length were taken as controlling variables, the objective function of the model was solved by improved genetic algorithm. The result indicates that controlling methods of the paper can make delayed vehicles of intersection fewer than before. At the same time, it incarnates that improved genetic algorithm is more excellent than basic genetic algorithm on stability, optimization and convergence speed of results.
在对遗传算法的基本原理、基本要素以及理论基础等进行详细分析后,本文针对基本遗传算法在应用中存在的局限性,提出了相应的改进措施:(1)从遗传算法自身的角度出发,采用了小生境技术的遗传算法,结合精英保留策略、种群多样性保持方案、新的适应度值标定方式、改进的自适应交叉和变异率对基本遗传算法进行改进;(2)在遗传算法的搜索过程中融合局部搜索能力强的梯度法,构成混合遗传算法来提高运行效率和求解的质量。
随着国民经济的不断增长,人民生活水平的不断提高,汽车进入寻常百姓家中业已成为现实,随之而来的城市交通问题则日益突现出来。因此,采用现代科学手段,研究一些智能化的方法来解决城市交通管理问题,就成为当务之急。为了缓解城市交通拥挤,本文在分析了城市道路单交叉路口交通流特性的基础上,首先建立了以车辆平均延误时间最短,以相位有效绿灯时间和饱和度为约束条件的非线性函数模型,利用混合遗传算法对模型进行求解,得到在固定周期下的最优配时方案。仿真结果表明获得了理想的效果,表现了混合遗传算法的优越性。其次,针对交叉路口的拥挤状况,建立了以控制周期内路口的总的排队长度最小为目标,以相位有效绿灯时间和周期时长为控制变量的交通信号优化控制模型,利用改进的遗传算法对模型进行多次仿真计算,结果表明本文的优化控制方法能够使控制周期内路口的总延误排队车辆数明显减少,同时也体现了改进的遗传算法在解的稳定性、最优性和收敛速度等方面都优于基本遗传算法。
Genetic algorithm is a random searching and optimizing method which simulates natural descendiblity mechanism and biology evolution theory. This method has some advantages that other usual methods don't have because of its twocharacters——implicit parallelism and global searching. But after all, geneticalgorithm is a newborn optimizing method and both its theory and its realization need to be improved. Only in this way, can genetic algorithm apply to the practice more effectively and widely.
After basic theory , basic factors and theory base of genetic algorithm being introduced detailedly, aiming at limitations on application of the simple genetic algorithm, this thesis bring forwards some improving measures: (1) From genetic algorithm itself, the niche technique is adopted and it combines elitists reservation model, scheme of keeping population diversiform, mode of demarcating fitness, improved adaptive crossover and mutation rate to improve basic genetic algorithm. (2) During the period of searching of genetic algorithm, blending steepest descent method whose ability of local searching is strong, forming hybrid genetic algorithm to enhance efficiency of circulating and quality of computing.
With the development of our national economy and the improving of the civilian living standard level, the car has been popular for every one. The problem of urban traffic is increasingly serious. So it is urgent for all of us to solve this problem by adopting modern scientific technology and intelligent method. In order to mitigate city traffic jam, the traffic flow characteristics of urban intersections were analyzed. firstly, a nonlinear function model of urban single—point intersections was established, in which shortest average delay of vehicles were taken as objectives, and phase effective green time, saturation degree were taken as restrictions, the objective function of the model was solved by hybrid genetic algorithm. Solved result indicates that obtaining perfect effect, which manifests the advantage of hybrid genetic algorithm. Secondly, aiming at crowd status of intersection, an urban intersection controlling model was established, in which shortest total queue length of vehicles were taken as objectives, phase effective green time and cycle time length were taken as controlling variables, the objective function of the model was solved by improved genetic algorithm. The result indicates that controlling methods of the paper can make delayed vehicles of intersection fewer than before. At the same time, it incarnates that improved genetic algorithm is more excellent than basic genetic algorithm on stability, optimization and convergence speed of results.
引文
[1]Bin Han.Optimizing Traffc Signal Setting for Periods of Time-Varying Demand [J].Transpn.Res.-A,1996,V30(3):207-230
[2]陈国良,王煦法,庄镇泉,王东生.遗传算法及其应用[M].北京:人民邮电出版社,1996
[3]陈得宝,赵春霞.一种改进遗传算法性能的方法研究[J].南开大学学报,2005,V38(6):84-88
[4]陈群,晏克非.基于遗传算法的城市交叉口实时信号控制研究[J].交通与计算机,2005,V23(1):15一18
[5]陈小峰.城市交通信号动态优化控制技术研究[D].西安:西北工业大学,2003[6]陈小峰,史忠科.基于遗传算法的交通信号动态优化方法[J].系统仿真学报,2004,V16(6):1155-1161
[7]Davis L.Handbook of genetic algorithms[M].New York:Van Noestrand Reinhold,1991
[8]董超俊,刘智勇,邱祖廉.灾变粒子群优化算法及其在交通控制中的应用[J].计算机工程与应用,2005,29:19-23
[9]付绍昌.城市智能交通信号控制方法及其仿真研究[D].湘潭:湘潭大学,2006
[10]Goldberg D E.Genetic algorithms in search,optimization and machine leaming [M].Reading:Addison-Wesley,1989
[11]Garter N.H,el al.Combined control and route assignment in traffic signal network.Proceedings of 8th IFAC symposium on transportation systems,1997,125-139
[12]Gtover F,et al.Genetic algorithms and tabu search:hybrids for optimization[J].Computer and Operation Research(UK),1995,V122(1):111-134
[13]顾榕,曹立明,王小平.基于改进免疫遗传算法的交通信号优化控制[J].模式识别与人工智能,2006,V19(3):331-337
[14]Hai Yang,Sam Yagar.Traffic assignment and signal control in saturated road networks[J].Transportation Research A,1995,V 29(2):125-139
[15]贺国光.ITS系统工程导论[M].北京:中国铁道出版社,2004
[16]黄辉先.城市交通信号优化控制方法的研究[D].西安:西北工业大学,2000
[17]江金龙.改进遗传算法及其在波束形成中的应用[D].南京:河海大学,2005
[18]焦敏朵,马良,范炳全.交叉口信号配时的人工蚂蚁优化[J].上海理工大学学报,2003,v25(2):143-145
[19]Kuncheva L I,Fitness Functions in Editing K-NN Reference Set by Genetic Algorithms [J].Pattern Recognition,1997,V30(6):1041-1049
[20]邝航宇,金晶,苏勇.自适应遗传算法交叉变异算子的改进[J].计算机工程与应用,2006,12:93-97
[21]Lin C Y,Hajela P.Genetic algorithms in optimization problems with discrete and integer design variables[J].Eng.Opt.,1992,19:309-327
[22]Leninger,M.G,Drew,A.W.A New Traffic Control Design Method for Large Networks with Signalized Intersections[J].IFAC-A Link Between Science and Application of Automatic Control,1975,11:331-350
[23]吕金华,江汉红.用混合遗传算法实现对PNN网络的快速训练[J].船海工程,2006,5:92-95
[24]刘金琨.智能控制[M].北京:电子工业出版社,2005
[25]黎钧琪.改进的遗传算法及其在物流配送中心选址优化的应用[D].武汉:武汉理工大学,2003
[26]李明.遗传算法的改进及其在优化问题中的应用研究[D].长春:吉林大学,2003
[27]李威武.城域智能交通系统中的控制与优化问题研究[D].杭州:浙江大学,2003
[28]李士勇.模糊控制·神经控制和智能控制论[M].哈尔滨:哈尔滨工业大学出版社,2002
[29]李艳,樊晓平.基于遗传算法的城市单交叉路口信号动态控制[J].交通运输系统工程与信息,2002,V2(1):49-53
[30]雷英杰,张善文,李续武,周创明.MATLAB遗传算法工具箱及应用[M].西安:西安电子科技大学出版社,2005
[31]刘喜敏.面向智能化与集成化的交通信号控制研究[D].长春:吉林大学,2005
[32]李秀平,刘智勇,吴今培.平面交叉路口的神经网络自学习控制方案[J].信息与控制,2001,V 30(1):76-79
[33]刘智勇.智能交通控制理论及其应用[M].北京:科学出版社,2003
[34]Mirchandani P B,Head K L.A real-time traffic signal control system:architecture,algorithms,and analysis[J].Transportation Research Part C:Emerging Technologies, 2001,V9(6):415-432
[35]R.Yang,I.Douglas.Simple Genetic Algorithm with Local Tuning:Efficient Global Optimizing Technique[J].Journal of Optimization Theory and Applications,1998,V99(2):1125-1134
[36]Singh M.G.,Tatnura H,Modeling and Hierarchical Optimization For Oversaturated Urban Road Traffic Network[J].Int.J.Control,1974,V 20(6):913-934
[37]宋晓霞,李勇.混合遗传算法在圆形件优化排样中的应用研究[J].微计算机信息,2006,V22(10):170-172
[38]史忠科,黄辉先,曲仕茹,陈小峰.交通控制系统导轮[M].北京:科学出版社,2003
[39]田方.遗传算法的改进研究及其在压缩机性能分析与优化中的应用[D].沈阳:东北大学,2006
[40]王秋平,谭学龙,张生瑞.城市单点交叉口信号配时优化[J].交通运输学报,2006,V6(2):60-64
[41]王小平,曹立明.遗传算法—理论、应用与软件实现[M].西安:西安交通大学出版社,2005:5-15
[42]万绪军,陆化普.实时自适应交通信号控制优化理论模型[J].交通运输工程学报,2001,V1(4):60-66
[43]万绪军,陆化普.线控系统中相位差优化模型的研究[J].中国公路学报,2001,V14(2):99-103
[44]徐冬玲,方建安,邵世煌.交通系统的模糊控制及其神经网络实现.信息与控制,1992,V 21(2):74-75
[45]许义海,李晓东.一种快速寻优的新型改进遗传算法[J].中山大学学报,2006,V45(2):36-40
[46]徐勋倩,黄卫.单路口交通信号多相位实时控制模型及其算法[J].控制理论与应用,2005,V22(3):413-416
[47]杨锦冬,杨东援.城市信号控制交叉口信号周期时长优化模型[J].同济大学学报,2001,V29(7):789-794
[48]杨煜普,欧海涛.基于再励学习与遗传算法的交通信号自组织控制[J].自动化学报,2002,V28(4):564-568
[49]袁琴.基于改进遗传算法的电力系统无功优化研究[D].成都:电子科技大学,2006
[50]杨丽娜,刘刚,王秋生.一种改进的遗传算法及其应用[J].郑州大学学报(工学版),2005,V26(3):98-101
[51]周明、孙树栋.遗传算法原理及应用[M].北京:国防工业出版,1999
[52]朱文兴.城市交通系统智能优化控制技术研究[D].济南:山东大学,2006
[53]朱文兴,贾磊,杜晓通.单路口信号灯模糊一遗传算法优化配时研究[J].系统仿真学报,2004,V16(6):1193-1197
[54]朱筱蓉,张兴华.基于小生境遗传算法的多峰函数全局优化研究[J].南京工业大学学报,2006,V28(3):39-43
[55]周商吾等.交通工程[M].上海:同济大学出版社,2004
[2]陈国良,王煦法,庄镇泉,王东生.遗传算法及其应用[M].北京:人民邮电出版社,1996
[3]陈得宝,赵春霞.一种改进遗传算法性能的方法研究[J].南开大学学报,2005,V38(6):84-88
[4]陈群,晏克非.基于遗传算法的城市交叉口实时信号控制研究[J].交通与计算机,2005,V23(1):15一18
[5]陈小峰.城市交通信号动态优化控制技术研究[D].西安:西北工业大学,2003[6]陈小峰,史忠科.基于遗传算法的交通信号动态优化方法[J].系统仿真学报,2004,V16(6):1155-1161
[7]Davis L.Handbook of genetic algorithms[M].New York:Van Noestrand Reinhold,1991
[8]董超俊,刘智勇,邱祖廉.灾变粒子群优化算法及其在交通控制中的应用[J].计算机工程与应用,2005,29:19-23
[9]付绍昌.城市智能交通信号控制方法及其仿真研究[D].湘潭:湘潭大学,2006
[10]Goldberg D E.Genetic algorithms in search,optimization and machine leaming [M].Reading:Addison-Wesley,1989
[11]Garter N.H,el al.Combined control and route assignment in traffic signal network.Proceedings of 8th IFAC symposium on transportation systems,1997,125-139
[12]Gtover F,et al.Genetic algorithms and tabu search:hybrids for optimization[J].Computer and Operation Research(UK),1995,V122(1):111-134
[13]顾榕,曹立明,王小平.基于改进免疫遗传算法的交通信号优化控制[J].模式识别与人工智能,2006,V19(3):331-337
[14]Hai Yang,Sam Yagar.Traffic assignment and signal control in saturated road networks[J].Transportation Research A,1995,V 29(2):125-139
[15]贺国光.ITS系统工程导论[M].北京:中国铁道出版社,2004
[16]黄辉先.城市交通信号优化控制方法的研究[D].西安:西北工业大学,2000
[17]江金龙.改进遗传算法及其在波束形成中的应用[D].南京:河海大学,2005
[18]焦敏朵,马良,范炳全.交叉口信号配时的人工蚂蚁优化[J].上海理工大学学报,2003,v25(2):143-145
[19]Kuncheva L I,Fitness Functions in Editing K-NN Reference Set by Genetic Algorithms [J].Pattern Recognition,1997,V30(6):1041-1049
[20]邝航宇,金晶,苏勇.自适应遗传算法交叉变异算子的改进[J].计算机工程与应用,2006,12:93-97
[21]Lin C Y,Hajela P.Genetic algorithms in optimization problems with discrete and integer design variables[J].Eng.Opt.,1992,19:309-327
[22]Leninger,M.G,Drew,A.W.A New Traffic Control Design Method for Large Networks with Signalized Intersections[J].IFAC-A Link Between Science and Application of Automatic Control,1975,11:331-350
[23]吕金华,江汉红.用混合遗传算法实现对PNN网络的快速训练[J].船海工程,2006,5:92-95
[24]刘金琨.智能控制[M].北京:电子工业出版社,2005
[25]黎钧琪.改进的遗传算法及其在物流配送中心选址优化的应用[D].武汉:武汉理工大学,2003
[26]李明.遗传算法的改进及其在优化问题中的应用研究[D].长春:吉林大学,2003
[27]李威武.城域智能交通系统中的控制与优化问题研究[D].杭州:浙江大学,2003
[28]李士勇.模糊控制·神经控制和智能控制论[M].哈尔滨:哈尔滨工业大学出版社,2002
[29]李艳,樊晓平.基于遗传算法的城市单交叉路口信号动态控制[J].交通运输系统工程与信息,2002,V2(1):49-53
[30]雷英杰,张善文,李续武,周创明.MATLAB遗传算法工具箱及应用[M].西安:西安电子科技大学出版社,2005
[31]刘喜敏.面向智能化与集成化的交通信号控制研究[D].长春:吉林大学,2005
[32]李秀平,刘智勇,吴今培.平面交叉路口的神经网络自学习控制方案[J].信息与控制,2001,V 30(1):76-79
[33]刘智勇.智能交通控制理论及其应用[M].北京:科学出版社,2003
[34]Mirchandani P B,Head K L.A real-time traffic signal control system:architecture,algorithms,and analysis[J].Transportation Research Part C:Emerging Technologies, 2001,V9(6):415-432
[35]R.Yang,I.Douglas.Simple Genetic Algorithm with Local Tuning:Efficient Global Optimizing Technique[J].Journal of Optimization Theory and Applications,1998,V99(2):1125-1134
[36]Singh M.G.,Tatnura H,Modeling and Hierarchical Optimization For Oversaturated Urban Road Traffic Network[J].Int.J.Control,1974,V 20(6):913-934
[37]宋晓霞,李勇.混合遗传算法在圆形件优化排样中的应用研究[J].微计算机信息,2006,V22(10):170-172
[38]史忠科,黄辉先,曲仕茹,陈小峰.交通控制系统导轮[M].北京:科学出版社,2003
[39]田方.遗传算法的改进研究及其在压缩机性能分析与优化中的应用[D].沈阳:东北大学,2006
[40]王秋平,谭学龙,张生瑞.城市单点交叉口信号配时优化[J].交通运输学报,2006,V6(2):60-64
[41]王小平,曹立明.遗传算法—理论、应用与软件实现[M].西安:西安交通大学出版社,2005:5-15
[42]万绪军,陆化普.实时自适应交通信号控制优化理论模型[J].交通运输工程学报,2001,V1(4):60-66
[43]万绪军,陆化普.线控系统中相位差优化模型的研究[J].中国公路学报,2001,V14(2):99-103
[44]徐冬玲,方建安,邵世煌.交通系统的模糊控制及其神经网络实现.信息与控制,1992,V 21(2):74-75
[45]许义海,李晓东.一种快速寻优的新型改进遗传算法[J].中山大学学报,2006,V45(2):36-40
[46]徐勋倩,黄卫.单路口交通信号多相位实时控制模型及其算法[J].控制理论与应用,2005,V22(3):413-416
[47]杨锦冬,杨东援.城市信号控制交叉口信号周期时长优化模型[J].同济大学学报,2001,V29(7):789-794
[48]杨煜普,欧海涛.基于再励学习与遗传算法的交通信号自组织控制[J].自动化学报,2002,V28(4):564-568
[49]袁琴.基于改进遗传算法的电力系统无功优化研究[D].成都:电子科技大学,2006
[50]杨丽娜,刘刚,王秋生.一种改进的遗传算法及其应用[J].郑州大学学报(工学版),2005,V26(3):98-101
[51]周明、孙树栋.遗传算法原理及应用[M].北京:国防工业出版,1999
[52]朱文兴.城市交通系统智能优化控制技术研究[D].济南:山东大学,2006
[53]朱文兴,贾磊,杜晓通.单路口信号灯模糊一遗传算法优化配时研究[J].系统仿真学报,2004,V16(6):1193-1197
[54]朱筱蓉,张兴华.基于小生境遗传算法的多峰函数全局优化研究[J].南京工业大学学报,2006,V28(3):39-43
[55]周商吾等.交通工程[M].上海:同济大学出版社,2004
© 2004-2018 中国地质图书馆版权所有 京ICP备05064691号 京公网安备11010802017129号 地址：北京市海淀区学院路29号 邮编：100083 电话：办公室：(+86 10)66554848；文献借阅、咨询服务、科技查新：66554700 |