粒子群算法简介

粒子群算法简介

小组成员：吴航海周运远集群智能〔SwarmIntelligence〕集群智能〔SwarmIntelligence〕在某群体中，假设存在众多无智能的个体，它们通过相互之间的简单合作所表现出来的智能行为。最早在分子自动机系统中提出。分子自动机中的主体在一维或二维网格空间中与相邻的个体相互作用，从而实现自组织。

目前,集群智能主要有两种算法模式,分别是蚁群算法(AntColonySystem,简称ACS)和粒子群算法(ParticleSwarmOptimization,简称PSO)。集群智能—根本原那么(1)邻近原那么(ProximityPrinciple)集群能够进行简单的空间和时间计算；(2)品质原那么(QualityPrinciple)集群能够响应环境中的品质因子；(3)多样性反响原那么(PrincipleofDiverseResponse)集群的行动范围不应该太窄；(4)稳定性原那么(StabilityPrinciple)集群不应在每次环境变化时都改变自身的行为；(5)适应性原那么(AdaptabilityPrinciple)在所需代价不太高的情况下，集群能够在适当的时候改变自身的行为。

这些原那么说明实现群体智能的智能主体必须能够在环境中表现出自主性、反响性、学习性和自适应性等智能特性。粒子群算法〔PSO〕简介粒子群算法〔particleswarmoptimization〕，由Kennedy和Eberhart在1995年提出，该算法模拟鸟集群飞行觅食的行为，鸟之间通过集体的协作使群体到达最优目的，是一种基于集群智能〔SwarmIntelligence〕的优化方法。系统初始化为一组随机解，通过迭代搜寻最优值。但是它没有遗传算法用的交叉以及变异，而是粒子在解空间追随最优的粒子进行搜索。同遗传算法比较，PSO的优势在于简单容易实现并且没有许多参数需要调整。这种算法以其实现容易、精度高、收敛快等优点引起了学术界的重视，并且在解决实际问题中展示了其优越性。目前已广泛应用于函数优化，神经网络的训练，参数优化，组合优化等多个领域。根本粒子群算法〔PSO〕粒子群优化算法源于1987年Reynolds对鸟群社会系统boids的仿真研究。在boids中，一群鸟在空中飞行，每只鸟遵守以下三条规那么：〔1〕防止与相邻的鸟发生碰撞冲突；〔2〕尽量与自己周围的鸟在速度上保持协调和一致；〔3〕尽量试图向自己所认为的群体中靠近。仅通过这三条规那么，boids系统就出现非常逼真的群体聚集行为，鸟成群地在空中飞行，当遇到障碍时它们会分开绕行而过，然后又会重新形成群体。Kennedy和Eberhart在其中参加了一个特定点，定义为食物，鸟根据周围鸟的觅食行为来寻找食物。他们的初衷是希望通过这种模型来模拟鸟群寻找食物来源的现象，然而实验结果却揭示了这个仿真模型中蕴含着很强的优化能力，尤其是在多维空间寻优中。粒子群算法具体内容粒子群算法算法〔ＰＳＯ〕中，每个优化问题的解都是搜索空间中的一只鸟。称之为“粒子〔Ｐａｒｔｉｃｌｅ〕〞。所有的粒子都有一个被优化的函数决定的适应值，每个粒子还有一个速度决定他们飞翔的方向和距离。然后粒子们就追随当前的最优粒子在解空间中搜索。粒子群算法算法〔ＰＳＯ〕初始化为一群随机粒子。然后通过迭代找到最优解。在每一次迭代中，粒子通过跟踪两个“极值〞来更新自己。第一个就是粒子本身所找到的最优解。这个解叫作个体极值。另一个极值是整个种群目前找到的最优解。这个解叫作全局极值。另外，也可以不用整个种群而只是用其中的一局部的邻居。粒子群算法〔ＰＳＯ〕数学表示粒子群算法算法〔ＰＳＯ〕数学表示如下：设搜索空间为Ｄ维，总粒子数为ｎ。第ｉ个粒子的位置表示为向量第ｉ个粒子的速度〔速率〕表示为向量第ｉ个粒子“飞行〞历史中去过的最优位置〔即该位置对应解最优〕为

所有粒子中“飞行〞历史中去过的最优位置为粒子群算法〔ＰＳＯ〕数学表示每个粒子的位置按如下公式进行变化〔“飞行〞〕：〔１〕〔２〕粒子群算法〔ＰＳＯ〕数学表示

其中Ｃ１，Ｃ２为正常数，称为加速因子，通常Ｃ１＝Ｃ２＝２；ｒａｎｄ〔〕为［０，１］之间的随机数；ｗ称惯性因子，ｗ大时适合于对解空间进行大范围探查〔ｅｘｐｌｏｒａｔｉｏｎ〕，ｗ较小时适合于进行小范围开挖〔ｅｘｐｌｏｉｔａｔｉｏｎ〕。

第ｄ维的位置变化范围为［－ＸＭＡＸｄ，ＸＭＡＸｄ］，速度变化范围为［－ＶＭＡＸｄ，ＶＭＡＸｄ］，迭代中假设位置和速度超过边界范围那么取边界值。 粒子群算法〔ＰＳＯ〕数学表示粒子群初始位置和初始速度随机产生，然后按公式〔１〕〔２〕进行迭代，直至找到满意的解。目前，常用的粒子群算法将全体粒子群〔Ｇｌｏｂａｌ〕分成假设干个有局部粒子重叠的相邻子群，每个粒子根据子群〔Ｌｏｃａｌ〕内历史最优Ｐｌ调整，即公式〔２〕中Ｐｇｄ换为Ｐｌｄ。粒子群算法〔ＰＳＯ〕算法表示Step

1

初始化粒子群，即随机设定各粒子的初始位置和初始速度；Step

2

计算每个粒子的适应值，适应值与最优解的距离直接有关；

Step

3

对每个粒子，比较它的适应值和它经历过的最好位置的适应值；假设更好，更新粒子当前最好位置Pid；

粒子群算法〔ＰＳＯ〕算法表示Step

4

对每个粒子的Pid

进行比较，最好的位置如果优于Pgd，那么更新Pgd

的值为Pid；

Step

5

根据式(1)

和式(2)

更新粒子速度和位置；

Step

6

如果到达结束条件(一般为足够好的位置或最大迭代次数)

，那么结束，否那么转Step

2。算法中的w，c1

和c2

是影响算法性能的重要参数。w

值较大时，算法的全局搜索能力强；反之，局部搜索能力强。c1

的值决定了粒子更新时受自身影响的程度，c2

的值决定了整个种群对个体粒子的影响程度。简单例如这里我们用一维空间例如两点找其[0,1]间的最值这里的初始点采用随机生成0,1之间的随机数v1=0.5*v1+2.0*suijishu()*(x1hmax-x1)+2.0*suijishu()*(xmax-x1);v2=0.5*v2+2.0*suijishu()*(x2hmax-x2)+2.0*suijishu()*(xmax-x2);x1=x1+v1;x2=x2+v2;while(((0.25-c1)>0.001)|((0.25-c2)>0.001))这里是循环结束条件c1,c2表示生成的点的值0.25-c1,0.25-c2那么对应离目标点的距离到达目标后结束循环，得出结果。代码#include<QCoreApplication>#include<stdio.h>#include<stdlib.h>doublesuijishu(){doublea;a=(double)qrand()/RAND_MAX;returna;}

doublejisuan(doublea){doublesum;sum=-a*a+a;returnsum;}

doublebest(doublex1,doublex2){if((0.25-jisuan(x1))<(0.25-jisuan(x2)))returnx1;elsereturnx2;}

intmain(intargc,char*argv[]){QCoreApplicationa(argc,argv);doublex1,x2,x1hmax,x2hmax,xmax,v1,v2;doublec1,c2;x1=suijishu();printf("%lf\n",x1);x2=suijishu();v1=suijishu();v2=suijishu();c1=jisuan(x1);c2=jisuan(x2);x1hmax=x1;x2hmax=x2;xmax=best(x1,x2);while(((0.25-c1)>0.001)|((0.25-c2)>0.001)){v1=0.5*v1+2.0*suijishu()*(x1hmax-x1)+2.0*suijishu()*(xmax-x1);v2=0.5*v2+2.0*suijishu()*(x2hmax-x2)+2.0*suijishu()*(xmax-x2);x1=x1+v1;x2=x2+v2;x1hmax=best(x1hmax,x1);x2hmax=b