微粒群算法(PSO)简要介绍.ppt

微粒群算法n微粒全算法英文缩写为PSO(particle Particle Swarm Optimization)是由Eberhart博士和kennedy博士于1995年提出。n所谓微粒群算法，实际上是一种模仿鸟类全体行为的进化算法。这种算法体现着一种简单朴实的智能思想：鸟类使用简单的规则来确定自己的飞行方向和速度，试图停落在鸟类中而不至于相互碰撞。n简单规则：n（1）飞离最近的个体，以避免碰撞。（2）飞向目标。(3)飞向群体的中心。一、微粒群算法介绍二、基本微粒群算法n每个个体被视为搜索空间中的一个没有重量和体积的微粒，并在搜索空间以一定的速度飞行，该飞行速度则由个体和群体的飞行经验进行动态调整，从而获得一个很好的寻优方案。n 为微粒i的当前位置。n 为微粒i的当前飞行速度。n 为微粒i所经历的最好位置，也就是微粒i所经历的具有最好适应值的位置，称为个体最好位置。对于最小化问题，目标函数值越小，对应的适应值越好。n为了讨论方便，设f(x)为最小化的目标函数，则微粒i的当前最好位置由下式确定 n设群体中的微粒为S，群体中所有微粒所经历过的最好位置为，称为全局最好位置。n则n有了以上定义，基本微粒全算法的进化方程可描述为n其中：下标“j”表示微粒的第j维，“i”表示微粒i,t 表示第t代，c1、c2为加速常数，通常在02之间rand()是（0,1）均匀分布相互独立的随机函数。从上述微粒进化方程可以看出，c1调节微粒飞向自身最好位置方向的步长，c2调节微粒向全局最好位置飞行的步长。为了减少在进化过程中，微粒离开搜索空间的可能性，飞行速度通常限定在一定的范围内即三、基本微粒群算法的初始化过程 n（a）设定群体规模N。n（b）对任意i,j在 内服从均匀分布产生 。n（c）对任意i,j在 内服从均匀分布产生 。n（d）对任意i，设 =。四、算法流程n（a）依照初始化过程，对微粒群得随机位置和速度进行初始设定。n（b）计算每个微粒的适应值。n（c）对于每个微粒，将其适应值与所经历过的最好位置的适应值进行比较，若较好，则将其作为当前的最好位置。n（d）对每个微粒，将其适应值与全局所经历的最好位置的适应值进行比较，若较好，则将其作为当前的全局最好位置。n（e）根据-方程（1）（2）对微粒的速度和位置进行进化。n（f）如未达到结束条件通常为足够好的适应值或达到一个预设最大代数，则返回步骤（b）。五、基本微粒群算法的社会行为分析n在上式（1）所描述的速度进化方程中，其第一部分为微粒先前的速度；其第二部分为“认知部分，因为它仅考虑了微粒自身的经验，表示微粒本身的思考。如果基本微粒群算法的速度进化方程仅包含认知部分，即 n则其性能变差。主要原因是不同的微粒间缺乏信息交流，即没有社会信息共享，微粒间没有交互，使得一个规模为N的群体等价于运行了N个单个微粒，因而得到最优解的概率非常小。式（1）中的第三部分为“社会”部分，表示微粒间的社会信息共享。若速度进化方程中仅包含社会部分，即 n则微粒没有认知能力。n若 则表示微粒速度的进化方程仅保留第一部分，此时，微粒将会保持速度不变，沿该方向一直“飞”下去直至到达边界。因而，在这种情况下，微粒很难搜索到较优解。n若n此时微粒的速度将取决与其历史最有位置与群体的历史最优位置，从而导致速度的无记忆性。假设在开始时，微粒i处于整体的最优位置，则按照式（3）它将停止进化知道群体发现更好的位置。这表明，整个微粒群得搜索区域将会收缩到当前最优位置附近，即如果没有第一项，则整个进化方程具有很强的局部搜索能力。综上可知：微粒速度的进化方程的第一项用于保证算法具有一定的全局搜索能n力。第二和第三项使微粒群算法具有局部收敛能力。六、带有惯性因子的改进微粒群算法n对于不同问题，如何确定局部搜索能力与全局搜索能力的比例关系，对于其求解的过程非常重要。因此，Yuhui Shi提出了带有惯性权重的改进微粒群算法，其进化方程为：n惯性权重w表明微粒原先的速度能在多大程度上得到保留。此外，惯性权重w类似模拟退火中的温度，较大的w有较好的全局收敛能力，而较小的w有较强的局部收敛能n-n力。因此，随着迭代次数的增加，惯性权重应不断减小，从而使得微粒群算法在初期具有较强的全局收敛能力，而晚期具有较强的局部收敛能力。七、带有收缩因子的微粒群算法n1999年，Clerc提出了带收缩因子的PSO算法。实验表明，这种方法可以保证PSO算法的收敛性。方程（6）和（7）描述了这种算法。n实验结果表明,与使用惯性权重的微粒群算法相比,使用收敛因子的微粒群算法有更快的收敛速度。其实只要恰当地选取w、c1 和c2 的值,两种算法是一样的,因此带收敛因子的微粒群算法可被看作带惯性权重的算法的一个特例。同时这也说明,恰当地选择算法的参数值可以改善算法的性能。在这种情况下同样不需要考虑V max 的设置的问题，这时只需要将其设为位置变量的最大变化范围即可。八、PSO算法的应用n（1）PSO 最直接的应用或许就是多元函数的优化问题,n 包括带约束的优化问题。如果所讨论的函数受到严重的n噪音干扰而呈现非常不规则的形状,同时所求的不一定是n精确的最优值,则PSO 算法能得到很好的应用。n（2）另外,还有一种应用更广泛的方法:简单而有效地n演化的人工神经网络,不仅用于演化网络的权重,而且包n括网络的结构。作为一个演化神经网络的例子,PSO 算法已应用于分析人的颤抖。对人颤抖的诊断,包括帕金森(Pa rk in son)病和原发性颤抖,是一个非常具有挑战性的领域。PSO 已成功地应用于演化一个用来快速和准确地辨别普通个体和有颤抖个体的神经网络,而网络的输入则为从一个活动变化记录系统中获得的归一化的移动振幅。n（3）另一个应用例子是使用PSO 对一个电气设备的功率反馈和电压进行控制。这里,采用一种二进制与实数混合的PSO 算法来决定对连续和离散的控制变量的控制策略,以得到稳定的电压。n（4）此外,PSO 还在动态问题中得到应用。一般而言,PSO 与其他演化算法一样,能用于求解大多数优化问题。在这些领域中,最具潜力的有系统设计、多目标优化、分类、模式识别、信号处理、机器人技术应用、决策制定、模拟和证明等。例子包括模糊控制器设计、工作调度、实时机器人路径设计和图像分割等。九、PSO算法的研究现状n（1）通过在基本的中引入繁殖和子种群的概念,增强其收敛性和寻求最优解的能力.在每轮迭代中随机选择一定的粒子作为父代,通过繁殖公式生成具有新的空间坐标和速度的子代粒子,并取代父代以保持种群规模.其实这是一种提高对解空间搜索能力和粒子多样性的数学交叉,可在一定程度上增强系统跳出局部极小的能力。n（2）将与模拟退火算法相结合的算法,解决了微粒群算法性能分析过程中发现的初始参数依赖性问题和算法搜索能力问题.通过模拟退火算法赋予搜索过程一种时变且最终趋于零的概率突跳性,有效地降低了陷入局部极小的概率,从而获取更佳的近似最优解.而且,模拟退火算法的串行优化结构和微粒群算法的群体并行搜索相结合,拓展了微粒群在解空间中的搜索范围,提高了其优化性能,促进了种群群体多样性的发展。