粒子群优化算法简介.docx

多目标粒子群算法粒子群算法，也粒子群优化算法（Particle Swarm Optimization），缩写为 PSO，是一种进化计算技术(evolutionary computation)，1995 年由Eberhart 博士和kennedy 博士提出，源于对鸟群捕食的行为研究 。PSO算法从随机解出发，通过迭代寻找最优解，通过适应度来评价解的品质。但是，PSO比遗传算法规则更为简单，它没有遗传算法的“交叉” 和“变异”操作，它通过追随当前搜索到的最优值来寻找全局最优。这种算法以其实现容易、精度高、收敛快等优点，并且在解决实际问题中展示了其优越性。1 引言优化问题是工业设计中经常遇到的问题,许多问题最后都可以归结为优化问题. 为了解决各种各样的优化问题,人们提出了许多优化算法,比较著名的有爬山法、遗传算法等. 优化问题有两个主要问题一是要求寻找全局最优点, 二是要求有较高的收敛速度. 遗传算法属于进化算法( Evolutionary Algorithms) 的一种,它通过模仿自然界的选择与遗传的机理来寻找最优解. 遗传算法有三个基本算子:选择、交叉和变异. 但是遗传算法的编程实现比较复杂,首先需要对问题进行编码,找到最优解之后还需要对问题进行解码,另外三个算子的实现也有许多参数,如交叉率和变异率,并且这些参数的选择严重影响解的品质,而目前这些参数的选择大部分是依靠经验。 PSO 算法PSO同遗传算法类似，是一种基于迭代的优化算法。系统初始化为一组随机解，通过迭代搜寻最优值。但是它没有遗传算法用的交叉(crossover)以及变异(mutation)，而是粒子在解空间追随最优的粒子进行搜索。同遗传算法比较，PSO的优势在于简单容易实现并且没有许多参数需要调整。目前已广泛应用于函数优化，神经网络训练，模糊系统控制以及其他遗传算法的应用领域。 2 算法介绍简介如前所述，PSO模拟鸟群的捕食行为。设想这样一个场景：一群鸟在随机搜索食物。在这个区域里只有一块食物。所有的鸟都不知道食物在那里。但是他们知道当前的位置离食物还有多远。那么找到食物的最优策略是什么呢。最简单有效的就是搜寻目前离食物最近的鸟的周围区域。 PSO从这种模型中得到启示并用于解决优化问题。PSO中，每个优化问题的解都是搜索空间中的一只鸟。我们称之为“粒子”。所有的粒子都有一个由被优化的函数决定的适应值(fitness value)，每个粒子还有一个速度决定他们飞翔的方向和距离。然后粒子们就追随当前的最优粒子在解空间中搜索。 PSO 初始化为一群随机粒子(随机解)。然后通过迭代找到最优解。在每一次迭代中，粒子通过跟踪两个极值来更新自己。第一个就是粒子本身所找到的最优解，这个解叫做个体极值pBest。另一个极值是整个种群目前找到的最优解，这个极值是全局极值gBest。另外也可以不用整个种群而只是用其中一部分作为粒子的邻居，那么在所有邻居中的极值就是局部极值。 描述在基本粒子群算法中, 粒子群由n个粒子组成, 每个粒子的位置xi代表优化问题在D维搜索空间中潜在的解。粒子在搜索空间中以一定的速度飞行, 这个速度根据它本身的飞行经验和同伴的飞行经验来动态调整下一步飞行方向和距离。所有的粒子都有一个被目标函数决定的适应值, 并且知道自己到目前为止发现的最好位置(个体极值pi)和当前的位置(xi)。除此之外, 每个粒子还知道到目前为止整个群体中所有粒子发现的最好位置(全局极值pg)。粒子群算法的数学描述如下: 每个粒子i包含为一个D维的位置向量xi=( xi1, xi2, , xiD ) 和速度向量vi = ( vi1, vi2, viD ), 粒子i搜索解空间时, 保存其搜索到的最优经历位置p i = ( pi1, pi2, , piD )。在每次迭代开始时, 粒子根据自身惯性和经验及群体最优经历位置pg = ( pg1, pg2, , pgD )来调整自己的速度向量以调整自身位置。c1、c2 是正常数,称之为加速因子; r1、r2为 0, 1中均匀分布的随机数, d为D维中的维数;是惯性权重因子。其中, 每个粒子的位置和速度更新按下式 vidt+1 =w*vidt+c1r1(pidt-xidt)+c2r2(pgdt-xidt) (1)xidt+1 =xidt+vidt+1 (2)式(1)由三部分组成, 第一部分是粒子原来的速度, 其值越大, 越利于全局搜索, 其值小则利于局部搜索能力, 具有平衡全局和局部搜索的能力; 第二部分是粒子本身的思考, 表明粒子自身经验对当前搜索倾向的吸引程度, 受到c1 r1的随机调整, 是对粒子所积累经验的利用, 使粒子有了足够强的全局搜索能力, 避免局部极小; 第三部分是粒子学习其他粒子经验的过程, 表明粒子间信息的共享和社会协作, 受到c2r2的随机调整, 并与pg 的位置和种群的领域拓扑结构直接相关。在这三部分的共同作用下, 粒子根据自己的经验并利用信息共享机制不断调整自己的速度与位置, 从而有效地到达最好位置。粒子位置在每一代的上述更新方式可用下图来描述由于粒子群算法具有高效的搜索能力, 有利于得到多目标意义下的最优解; 通过代表整个解集种群, 按并行方式同时搜索多个非劣解, 也即搜索到多个Pareto 最优解; 同时, 粒子群算法的通用性比较好, 适合处理多种类型的目标函数和约束,并且容易与传统的优化方法结合, 从而改进自身的局限性, 更高效地解决问题。因此, 将粒子群算法应用于解决多目标优化问题上具有很大的优势。粒子群算法思想描述如下: 初始化种群后,种群的大小记为N。基于适应度支配的思想,将种群划分成两个子群,一个称为非支配子集A, 另一个称为支配子集B, 两个子集的基数分别为n1、n2, 满足两个子群基数之和为N。外部精英集用来存放每代产生的非劣解子集A, 每次迭代过程只对B中的粒子进行速度和位置的更新, 并对更新后的B中的粒子基于适应度支配思想与A中的粒子进行比较, 若xiB，任意xjA, 使得xi 支配xj, 则删除xj，使xi加入A更新外部精英集; 且精英集的规模要利用一些技术维持在一个上限范围内, 如密度评估技术、分散度技术等。最后, 算法终止的准则可以是最大迭代次数Tmax、计算精度或最优解的最大凝滞步数t等。具体步骤如下图所示：图中，t是迭代的代数,xi是第i个粒子的位置坐标, vi是第i个粒子的速度,pi是粒子的个体极值,pg是粒子群的全局极值。粒子群算法是一种新兴起的优化算法, 其每个粒子根据自身的最优位置和群体全局的最优位置更新自己的速度和位置,各粒子由于群体全局的最优位置的影响, 很快收敛到全局最优位置附近, 这已显示出它的快速性、有效性和鲁棒性等多种优点。3 遗传算法和 PSO 的比较粒子群优化算法(PSO)是一种基于迭代的优化工具,系统初始化一组随机解, 通过迭代搜寻最优值, 不但具有全局寻优能力, 而且具有较强的局部寻优能力。粒子群算法（PSO）和遗传算法(GA)都是优化算法，都力图在自然特性的基础上模拟个体种群的适应性，它们都采用一定的变换规则通过搜索空间求解。 PSO和GA的相同点： (1) 都属于仿生算法。PSO主要模拟鸟类觅食、人类认知等社会行为而提出；GA主要借用生物进化中“适者生存”的规律。 (2) 都属于全局优化方法。两种算法都是在解空间随机产生初始种群，因而算法在全局的解空间进行搜索，且将搜索重点集中在性能高的部分。 (3) 都属于随机搜索算法。都是通过随机优化方法更新种群和搜索最优点。PSO中认知项和社会项前都加有随机数；而GA的遗传操作均属随机操作。 (4) 都隐含并行性。搜索过程是从问题解的一个集合开始的，而不是从单个个体开始，具有隐含并行搜索特性，从而减小了陷入局部极小的可能性。并且由于这种并行性，易在并行计算机上实现，以提高算法性能和效率。 (5) 根据个体的适配信息进行搜索，因此不受函数约束条件的限制，如连续性、可导性等。 (6) 对高维复杂问题，往往会遇到早熟收敛和收敛性能差的缺点，都无法保证收敛到最优点。 PSO和GA不同点 (1) PSO有记忆，好的解的知识所有粒子都保存，而GA没有记忆，以前的知识随着种群的改变被破坏。 (2) 在GA算法中，染色体之间相互共享信息，所以整个种群的移动是比较均匀地向最优区域移动。PSO中的粒子仅仅通过当前搜索到最优点进行共享信息，所以很大程度上这是一种单项信息共享机制，整个搜索更新过程是跟随当前最优解的过程。在大多数情况下，所有粒子可能比遗传算法中的进化个体以更快速度收敛于最优解。 (3) GA的编码技术和遗传操作比较简单，而PSO相对于GA，不需要编码，没有交叉和变异操作，粒子只是通过内部速度进行更新，因此原理更简单、参数更少、实现更容易。 (4) 在收敛性方面，GA己经有了较成熟的收敛性分析方法，并且可对收敛速度进行估计；而PSO这方面的研究还比较薄弱。尽管已经有简化确定性版本的收敛性分析，但将确定性向随机性的转化尚需进一步研究。 (5) 在应用方面，PSO算法主要应用于连续问题，包括神经网络训练和函数优化等，而GA除了连续问题之外，还可应用于离散问题，比如TSP问题、货郎担问题、工作车间调度等。4 演化计算技术过程大多数演化计算技术都是用同样的过程 ： 1. 种群随机初始化 2. 对种群内的每一个个体计算适应值(fitness value).适应值与最优解的距离直接有关 3. 种群根据适应值进行复制 4. 如果终止条件满足的话，就停止，否则转步骤2 从以上步骤，我们可以看到PSO和GA有很多共同之处。两者都随机初始化种群，而且都使用适应值来评价系统，而且都根据适应值来进行一定的随机搜索。两个系统都不是保证一定找到最优解 。 5 粒子群算法的记忆性PSO 没有遗传操作如交叉(crossover)和变异(mutation). 而是根据自己的速度来决定搜索。粒子还有一个重要的特点，就是有记忆。 与遗传算法比较, PSO 的信息共享机制是很不同的. 在遗传算法中，染色体(chromosomes) 互相共享信息，所以整个种群的移动是比较均匀的向最优区域移动. 在PSO中, 只有gBest (or lBest) 给出信息给其他的粒子，这是单向的信息流动. 整个搜索更新过程是跟随当前最优解的过程. 与遗传算法比较, 在大多数的情况下，所有的粒子可能更快的收敛于最优解 6 PSO的参数设置从上面的例子我们可以看到应用PSO解决优化问题的过程中有两个重要的步骤: 问题解的编码和适应度函数 PSO的一个优势就是采用实数编码不需要像遗传算法一样是二进制编码(或者采用针对实数的遗传操作.例如对于问题 f(x) = x12 + x22+x32 求解, 粒子可以直接编码为 (x1, x2, x3), 而适应度函数就是f(x). 接着我们就可以利用前面的过程去寻优.这个寻优过程是一个叠代过程, 中止条件一般为设置为达到最大循环数或者最小错误 PSO中并没有许多需要调节的参数,下面列出了这些参数以及经验设置。 粒子数: 一般取 20 40. 其实对于大部分的问题10个粒子已经足够可以取得好的结果, 不过对于比较难的问题或者特定类别的问题, 粒子数可以取到100 或 200 粒子的长度: 这是由优化问题决定, 就是问题解的长度 粒子的范围: 由优化问题决定,每一维可是设定不同的范围 Vmax: 最大速度,决定粒子在一个循环中最大的移动距离,通常设定为粒子的范围宽度,例如上面的例子里,粒子 (x1, x2, x3) x1 属于 -10, 10, 那么 Vmax 的大小就是 20 学习因子: c1 和 c2 通常等于 2. 不过在文献中也有其他的取值. 但是一般 c1 等于 c2 并且范围在0和4之间 中止条件: 最大循环数以及最小错误要求. 例如, 在上面的神经网络训练例子中, 最小错误可以设定为1个错误分类, 最大循环设定为2000, 这个中止条件由具体的问题确定. 全局PSO和局部PSO: 我们介绍了两种版本的粒子群优化算法: 全局版和局