1
摘要
粒子群优化算法(Particle Swarm Optimization,PSO)是由美国的
Eberhart和Kennedy在1995年提出的一种高效的并行优化算法。由于该算法
具有深刻的智能背景,且简单、易实现,因此,一经提出便引起了许多学者
的广泛关注,并在短短的几年里出现了大量的研究成果,现已成为研究的热
点。目前,已提出了多种PSO的改进算法,被广泛应用于函数优化、神经网
络训练、模式分类、模糊系统控制等领域。但其应用大多是连续优化问题,
很少被用来解决离散问题,而现实生活中的许多工程实例只能抽象出离散模
型,如典型的旅行商问题(Traveling Salesman Problem,TSP)、加工调度
(Job-slmp)问题、最短路径问题等。
最短路径问题是图论中的一个典范问题。从网络模型的角度看最短路径
分析就是在指定网络的两节点间找一条阻碍强度最小的路径。最短路径问题
的研究在汽车实时导航、应急救援等领域有广泛的应用。经典的 Dijkstra
算法是应用最短路径解决实际问题的理论基础。但是算法在具体的城市道路
网络中执行的效率比较低,无法满足实时高效的应用需求,因此国内外很多
学者开始了最短路径问题的粒子群优化算法研究。
本文主要是研究在最短路径问题中的粒子群算法。文中给出了基于交换
序的基本的粒子群算法,并在此基础上提出了一种改进的粒子群算法。基本
的粒子群算法是在计算完粒子速度之后再更新粒子的位置,改进算法则是计
算粒子速度的同时更新粒子的位置。文中还引入自适应惯性权重的改进策略,
使粒子在开始时惯性速度大,能快速的向最优值点运动,而在粒子迭代过程
中惯性速度越来越小,从而使粒子能更好的接近最优值点。引入罚函数,把
约束优化问题转化为无约束优化问题来解,从而减化求解过程。本文用实例
对基本的粒子群算法和改进粒子群算法进行了对比分析,并得出了改进算法
确实存在优势的结论。文中还对算法的主要参数如何取值进行了分析,并结
合经验给出了总结。本文最后用实例验证了算法确实在执行了若干次迭代后
收敛。程序的编程环境为Microsoft Visual Studio 2008,编程语言为C#。
关键词: 粒子群算法 最短路径 约束优化 惯性权重