粒子群优化算法及其在圆度误差评定中的应用

    1 前 言

    粒子群优化算法(Particle Swarm Optimization,PSO)是由Kennedy和Eberhart于1995年提出的,是一种较为新颖的优化算法[1]。PSO优化算法与其它演化算法相似,也是一种基于群体的优化算法,即模拟鸟群觅食的过程,其功能与遗传算法(Genetic A-lgorithm,GA)非常相似,但是其实现技术却有显著的优点:(1)无交叉和变异运算,依靠粒子速度完成搜索;(2)有记忆性,粒子的历史最好位置和群体的历史最好位置可以记忆并传递给其它粒子;(3)需调整的参数较少,结构简单,易于实现;(4)采用实数编码,直接由问题的解决定,问题解的变量数直接作为粒子的维数;(5)收敛速度快,在迭代进化中只有最优的粒子把信息传递给其它粒子,属于单向信息流动。

    PSO优化算法虽然起源于对简单社会系统的模拟,但后来发现PSO是一种很好的优化工具,很多学者都进行了这方面的研究。目前,PSO已应用于函数优化、神经网络训练(主要是权重)、模式分类、模糊系统控制以及其它遗传算法的应用领域[2,3]。

    2 粒子群优化算法原理和基本实现步骤

    2.1 算法原理

    PSO的基本概念源于对鸟群觅食行为的研究,它属于/群智能0,类似于蚁群优化算法[1]。设想有这样一个场景:一群鸟在随机搜索食物,在这个区域里只有一块食物,所有的鸟都不知道食物在哪里,但是它们知道当前的位置离食物还有多远。那么找到食物的最优策略是什么呢?最简单有效的办法就是搜索目前离食物最近的鸟的周围区域。

    PSO从这种模型当中得到启示,并用于解决优化问题。PSO中,每个优化问题的解都是搜索空间中的一只鸟,称之为/粒子(Particle)0。所有的粒子都有一个由被优化的函数决定的适应度值(Fitnessvalue),每个粒子还有一个速度(Velocity)决定它们飞翔的方向和距离。然后粒子们就追随当前的最优粒子在解空间中搜索。粒子群在二维空间内的搜索飞跃过程如图1所示。其中,粒子在二维空间的位置用X(x1,x2)表示,速度用V(v1,v2)表示,下一时刻的位置和速度用Xc(x1c,x2c)和Vc(v1c,v2c)表示,可以用粒子与目标(如食物)之间的距离评价粒子的优劣。

    PSO运算时首先初始化为一群随机粒子(随机解),然后通过迭代找到最优解。在每一次迭代P飞跃中,粒子通过跟踪两个/极值0来更新自己。第一个就是粒子自己找到的最优解,这个解叫做个体极值pBest(personal Best);另一个极值是整个粒子群目前找到的最优解,这个极值是全局极值gBest(globalBest)。另外也可以不用整个粒子群而只是用其中一部分作为粒子的邻居,那么在所有的邻居中的极值就是局部极值。