计算机工程与应用 ›› 2008, Vol. 44 ›› Issue (34): 234-238.DOI: 10.3778/j.issn.1002-8331.2008.34.071

• 工程与应用 • 上一篇    下一篇

改进的粒子群算法在动态OD矩阵反推中的应用

杜长海,黄席樾,杨祖元,唐明霞,杨芳勋   

  1. 重庆大学 自动化学院,重庆 400044
  • 收稿日期:2007-11-26 修回日期:2008-03-03 出版日期:2008-12-01 发布日期:2008-12-01
  • 通讯作者: 杜长海

Application of improved particle swarm algorithm in dynamic OD matrix estimation

DU Chang-hai,HUANG Xi-yue,YANG Zu-yuan,TANG Ming-xia,YANG Fang-xun   

  1. College of Automation,Chongqing University,Chongqing 400044,China
  • Received:2007-11-26 Revised:2008-03-03 Online:2008-12-01 Published:2008-12-01
  • Contact: DU Chang-hai

摘要: 针对粒子群算法存在收敛速度慢和局部最优的问题,引入粒子间相对位置改进基于抗体浓度的概率选择公式,提出了一种带免疫机理的改进粒子群算法。粒子不仅根据个体极值和全局极值更新速度和位置,而且按一定概率以轮盘赌法选择某个粒子进行学习,以保持种群多样性,防止出现早熟停滞现象。并将其用于由路段流量反推OD矩阵的极大熵模型求解研究中,以重庆市某交叉路口为实例进行实验,结果表明:粒子群算法推算OD矩阵是有效、可行的,可以克服牛顿法严格依赖初始值的缺点;改进的粒子群算法比基本粒子群算法和基本遗传算法具有更好的全局寻优能力。

关键词: 智能交通系统, OD矩阵, 极大熵模型, 粒子群优化, 免疫算法

Abstract: Due to the disadvantage of slow convergence and local optimum of particle swarm algorithm,introducing relative distances among particles to improve probability selection formula,an improved particle swarm optimization with immune mechanism is proposed.Particles update their velocity and position not only by individual and global optima,but also by individual optima of a specific particle selected by roulette method according to certain probability,to keep the variety of the population and avoid precocity and stagnation.This algorithm is applied to solve the maximum entropy model,estimating OD matrix from traffic link flows.Through a test on a specific crossroad in Chongqing City,the experimental results show that particle swarm algorithm is feasible and effective for OD matrix estimation,overcomes the shortcoming of Newton’s method that strictly depends on initial values,and the particle swarm algorithm has much higher capacity of optimization than basic particle swarm algorithm and basic genetic algorithm.

Key words: intelligent transportation system, Origin-Destination(OD) matrix, maximum-entropy model, particle swarm optimization, immune algorithm