基于混合粒子群算法的列车停站方案优化
|
摘要
列车停站方案影响着旅客服务质量和运行效率,是列车开行方案的重要环节.本文建立了旅客列车停站方案的多目标规划模型以最大化区段可达性从而减少旅客旅行时间.针对传统的粒子群优化算法在处理复杂多维问题时,算法效率不高,易陷进局部最优,且无法有效处理离散问题等缺点,提出了一种将量子遗传算法引入到MPSO中的方法.算法整体采用粒子群算法,结合量子遗传算法的概率幅编码,并使用粒子群的速度更新公式来更新量子旋转门.算法引入量子遗传算法的全局探索和粒子群算法的种群智能体系,不仅提高了算法的收敛速度,同时增加了粒子多样性.最后,将改进的量子遗传粒子群算法(QGA_PSO)应用于ZDT函数优化和停站方案模型优化,证明了算法的有效性.
The stopping scheme for passenger trains is important to the operation planning of trains, and the scheme affects the quality of passenger service and the transportation efficiency. This study established a multi-target programming model, aiming to minimize the total travel time of passengers and maximize the zone accessibility. In view of the traditional Particle Swarm Optimization(PSO) algorithm, which is inefficient and easy to fall into local optimum and cannot effectively handle the discrete problems when dealing with complex high dimensional problems, a new hybrid particle swarm algorithm is proposed based on the Quantum Genetic Algorithm(QGA). First, the algorithm adopted the construction of particle swarm algorithm, employing the idea of quantum bit coding, and using PSO algorithm velocity update mechanism to update the quantum revolving door. Since the algorithm combined the global exploration of QGA and intelligent system PSO populations, which not only improves the convergence speed of algorithm, but also increases the diversity of particle. Finally, the experiment on the ZDT function optimum and stopping scheme optimum problem shows that the proposed algorithm consistently provides faster convergence and precision.
The stopping scheme for passenger trains is important to the operation planning of trains, and the scheme affects the quality of passenger service and the transportation efficiency. This study established a multi-target programming model, aiming to minimize the total travel time of passengers and maximize the zone accessibility. In view of the traditional Particle Swarm Optimization(PSO) algorithm, which is inefficient and easy to fall into local optimum and cannot effectively handle the discrete problems when dealing with complex high dimensional problems, a new hybrid particle swarm algorithm is proposed based on the Quantum Genetic Algorithm(QGA). First, the algorithm adopted the construction of particle swarm algorithm, employing the idea of quantum bit coding, and using PSO algorithm velocity update mechanism to update the quantum revolving door. Since the algorithm combined the global exploration of QGA and intelligent system PSO populations, which not only improves the convergence speed of algorithm, but also increases the diversity of particle. Finally, the experiment on the ZDT function optimum and stopping scheme optimum problem shows that the proposed algorithm consistently provides faster convergence and precision.
引文
1张小炳,倪少权,潘金山.基于均衡性和可达性的高速铁路列车停站方案优化.计算机应用研究,2017,34(7):1962–1965.
2 于剑,张星臣,许璐.轨道交通开行方案优化模型研究综述.武汉理工大学学报(交通科学与工程版),2016,40(1):195 –200.
3Wang S,Zhao P,Qiao K.Study on passenger train stopping scheme based on improved particle swarm optimization algorithm.Proceedings of 2009 IEEE International Conference on Intelligent Computing and Intelligent Systems.Shanghai,China.2009.821–826.
4陈世明,赖毅平,江冀海.面向列车运行调整问题的粒子群算法研究.计算机应用研究,2010,27(12):4460–4463.
5 严艺,叶玉玲.基于改进的遗传算法的城际铁路开行方案研究.2014第九届中国智能交通年会论文集.广州,中国智能交通协会.2014.29–37.
6Liu XY.Optimization design on fractional order PID controller based on adaptive particle swarm optimization algorithm.Nonlinear Dynamics,2016,84(1):379–386.[doi:10 .1007/s11071-015-2553-8]
7 Ali AF,Tawhid MA.A hybrid particle swarm optimization and genetic algorithm with population partitioning for large scale optimization problems.Ain Shams Engineering Journal,2016,8(2):191–206.
8Lin J,Zhao HY,Ma Y,et al.New hybrid genetic particle swarm optimization algorithm to design multi-zone binary filter.Optics Express,2016,24(10):10748–10758.[doi:10 .1364/OE.24.010748]
9 Wu SY,Zhang P,Li F,et al.A hybrid discrete particle swarm optimization-genetic algorithm for multi-task scheduling problem in service oriented manufacturing systems.Journal of Central South University,2016,23(2):421 –429.[doi:10.1007/s11771-016-3087-z]
10姜明媚.城际铁路列车停站方案优化研究[硕士学位论文].北京:北京交通大学,2015.
11Narayanan A,Moore M.Quantum-inspired genetic algorithms.Proceedings of IEEE International Conference on Evolutionary Computation.Nagoya,Japan.1999.61–66.
12许可,陈云飞.粒子群算法研究概述.福建电脑,2015,31 (9):83–84.
13蒋林利.量子遗传算法研究现状综述.广西科技师范学院学报,2016,31(2):130–134.
14Han KH,Kim JH.Genetic quantum algorithm and its application to combinatorial optimization problem.Proceedings of the 2000 Congress on Evolutionary Computation.La Jolla,CA,USA.2002.1354–1360.
15汪健雄.改进的多目标量子遗传算法及其在旅客列车开行方案中的应用[博士学位论文].北京:中国铁道科学研究院,2012.
16Shi YH,Eberhart RC.Parameter selection in particle swarm optimization.Proceedings of the 7th International Conference on Evolutionary Programming VII.San Diego,CA,USA.1998.591–600.
17徐斌.高速铁路列车停站方案研究[硕士学位论文].北京:北京交通大学,2012.
18江雨星.高速铁路旅客列车开行方案编制方法研究[硕士学位论文].兰州:兰州交通大学,2015.
19 李士勇,李盼池.求解连续空间优化问题的量子粒子群算法.量子电子学报,2007,24(5):569–574.
2 于剑,张星臣,许璐.轨道交通开行方案优化模型研究综述.武汉理工大学学报(交通科学与工程版),2016,40(1):195 –200.
3Wang S,Zhao P,Qiao K.Study on passenger train stopping scheme based on improved particle swarm optimization algorithm.Proceedings of 2009 IEEE International Conference on Intelligent Computing and Intelligent Systems.Shanghai,China.2009.821–826.
4陈世明,赖毅平,江冀海.面向列车运行调整问题的粒子群算法研究.计算机应用研究,2010,27(12):4460–4463.
5 严艺,叶玉玲.基于改进的遗传算法的城际铁路开行方案研究.2014第九届中国智能交通年会论文集.广州,中国智能交通协会.2014.29–37.
6Liu XY.Optimization design on fractional order PID controller based on adaptive particle swarm optimization algorithm.Nonlinear Dynamics,2016,84(1):379–386.[doi:10 .1007/s11071-015-2553-8]
7 Ali AF,Tawhid MA.A hybrid particle swarm optimization and genetic algorithm with population partitioning for large scale optimization problems.Ain Shams Engineering Journal,2016,8(2):191–206.
8Lin J,Zhao HY,Ma Y,et al.New hybrid genetic particle swarm optimization algorithm to design multi-zone binary filter.Optics Express,2016,24(10):10748–10758.[doi:10 .1364/OE.24.010748]
9 Wu SY,Zhang P,Li F,et al.A hybrid discrete particle swarm optimization-genetic algorithm for multi-task scheduling problem in service oriented manufacturing systems.Journal of Central South University,2016,23(2):421 –429.[doi:10.1007/s11771-016-3087-z]
10姜明媚.城际铁路列车停站方案优化研究[硕士学位论文].北京:北京交通大学,2015.
11Narayanan A,Moore M.Quantum-inspired genetic algorithms.Proceedings of IEEE International Conference on Evolutionary Computation.Nagoya,Japan.1999.61–66.
12许可,陈云飞.粒子群算法研究概述.福建电脑,2015,31 (9):83–84.
13蒋林利.量子遗传算法研究现状综述.广西科技师范学院学报,2016,31(2):130–134.
14Han KH,Kim JH.Genetic quantum algorithm and its application to combinatorial optimization problem.Proceedings of the 2000 Congress on Evolutionary Computation.La Jolla,CA,USA.2002.1354–1360.
15汪健雄.改进的多目标量子遗传算法及其在旅客列车开行方案中的应用[博士学位论文].北京:中国铁道科学研究院,2012.
16Shi YH,Eberhart RC.Parameter selection in particle swarm optimization.Proceedings of the 7th International Conference on Evolutionary Programming VII.San Diego,CA,USA.1998.591–600.
17徐斌.高速铁路列车停站方案研究[硕士学位论文].北京:北京交通大学,2012.
18江雨星.高速铁路旅客列车开行方案编制方法研究[硕士学位论文].兰州:兰州交通大学,2015.
19 李士勇,李盼池.求解连续空间优化问题的量子粒子群算法.量子电子学报,2007,24(5):569–574.