粒子群优化算法.ppt

粒子群优化算法 1. 引言 1. 引言 2.PSO产生背景 3.基本原理 3.基本原理 3.基本原理 3.基本原理 4.PSO应用领域 4.PSO应用领域 5.PSO研究方向 5.PSO研究方向 * 粒子群优化算法(Particle Swarm Optimization，PSO)由Kennedy博士和Eberhart教授在1995年提出，该算法模拟鸟群、鱼群、蜂群等动物群体觅食的行为，通过个体之间的相互协作使群体达到最优目的，是一种基于群智能(Swarm Intelligence，SI)的优化方法。 PSO算法也是一种启发式的优化计算方法，其最大的优点在于： ⑴易于描述，易于理解； ⑵对优化问题定义的连续性无特殊要求； ⑶只有非常少的参数需要调整； ⑷算法实现简单，速度快； ⑸相对其它演化算法而言，只需要较小的演化群体； ⑹算法易于收敛，相比其他演化算法，只需要较少的评价函数计算次数就可达到收敛； ⑺无集中控制约束，不会因个体的故障影响整个问题的求解，确保了系统具有很强的鲁棒性。 粒子群优化算法源于1987年Reynolds对鸟群社会系统boids的仿真研究，boids是一个复杂适应系统 (Complex Adaptive System，CAS)，在boids中，一群鸟在空中飞行，每个鸟遵守以下三条规则： ⑴避免与相邻的鸟发生碰撞冲突； ⑵尽量与自己周围的鸟在速度上保持协调和一致； ⑶尽量试图向自己所认为的群体中靠近。 ⑴基本粒子群优化算法 一个由m个粒子（Particle）组成的群体（Swarm）在D维有哪些信誉好的足球投注网站空间中以一定的速度飞行，每个粒子在有哪些信誉好的足球投注网站时，考虑了自己有哪些信誉好的足球投注网站到的历史最好点和群体内（或邻域内）其他粒子的历史最好点，在此基础上进行位置（状态，也就是解）的变化。 第i个粒子的位置表示为： 第i个粒子的速度表示为：，， 第i个粒子经历过的历史最好点表示为： 群体内（或邻域内）所有粒子所经过的最好的点表示为： 粒子的位置和速度根据如下方程进行变化： （2-1） （2-2） 这里，c1和c2称为学习因子，为正常数。学习因子使粒子具有自我总结和向群体中优秀个体学习的能力，从而向自己的历史最优点以及群体内或领域内的历史最优点靠近。c1和c2通常等于2。，是在[0,1]区间内均匀分布的伪随机数。粒子的速度被限定在一个最大速度的范围内。 基本粒子群优化算法的流程如下： ⑴在初始化范围内，对粒子群进行随机初始化，包括随机位置和速度。 ⑵计算每个粒子的适应值。 ⑶对于每个粒子，将其适应值与所经历过的最好位置的适应值进行比较，如果更好，则将其作为粒子的个体历史最优值，用当前位置更新个体历史最好位置。 ⑷对每个粒子，将其历史最优适应值与群体内或邻域内所经历的最好位置的适应值进行比较，若更好，则将其作为当前的全局最好位置。 ⑸根据式(2-1)和(2-2)对粒子的速度和位置进行更新。 ⑹若未达到终止条件，则转步骤⑵。 一般讲终止条件设定为一个足够好的适应值或达到一个预设的最大迭代代数。 ⑵标准粒子群优化算法 为改善算法收敛性能，Shi和Eberhart在1998年的论文中引入了惯性权重的概念，将速度更新方程修改为式(2-3)所示 （7.3） 这里，称为惯性权重，其大小决定了对粒子当前速度继承的多少，合适的选择可以是粒子具有均衡的探索和开发能力。可见，基本PSO算法是惯性权重=1的特殊情况。 PSO算法的优势在于算法的简洁性，易于实现，没有很多参数需要调整，且不需要梯度信息。PSO算法是非线性连续优化问题、组合优化问题和混合整数费线性优化问题的有效优化工具。 ⑴函数优化 大量的问题最终可归结为函数的优化问题，通常这些函数是非常复杂的，PSO算法通过改进或结合其它算法，对高维复杂函数可以实现高效优化。 ⑵神经网络的训练 与BP算法相比，使用PSO算法训练神经网络的优点在于不使用梯度信息，可使用一些不可微的传递函数。多数情况下其训练结果优于BP算法，而且训练速度非常快。 ⑶参数优化 PSO算法已广泛应用于各类连续问题和离散问题的参数优化。例如，在模糊控制器的设计、机器人路径规划、信号处理和模式识别等问题上均取得了不错的效果。 ⑷组合优化 研究者根据问题的不同，提出了相应问题的粒子表达方式。目前已提出了多种解决TSP、VRP以及车间调度等问题的方案。 除了以上领域外，PSO算法的应用包括系统设计、多目标优化、分类、模式识别、调度、信号处理、决策、机器人应用等。其中具体的应用实例有：模糊控制器设计、车间作业调度、机器人实时路径规划、自动目标检测等。 目前若干研究PSO算法的方向如下： ⑴PSO方法的数学基础显得相当薄弱，缺乏深刻其具有普遍意义的理论分析，因为清楚的理论分析可