搜索
PSO粒子群优化算法1.引言粒子群优化算法(PSO)是一种进化计算技术(evolutionarycomputation)，由Eberhart博士和kennedy博士发明。源于对鸟群捕食的行为研究PSO同遗传算法类似，是一种基于迭代的优化工具。系统初始化为一组随机解，通过迭代搜寻最优值。但是并没有遗传算法用的交叉(crossover)以及变异(mutation)。而是粒子在解空间追随最优的粒子进行搜索。详细的步骤以后的章节介绍同遗传算法比较，PSO的优势在于简单容易实现并且没有许多参数需要调整。目前已广泛应用于函数优化，神经网络训练，模糊系统控制以及其他遗传算法的应用领域2.背景:人工生命人工生命是来研究具有某些生命基本特征的人工系统.人工生命包括两方面的内容1.研究如何利用计算技术研究生物现象2.研究如何利用生物技术研究计算问题我们现在关注的是第二部分的内容.现在已经有很多源于生物现象的计算技巧.例如,人工神经网络是简化的大脑模型.遗传算法是模拟基因进化过程的.现在我们讨论另一种生物系统-社会系统.更确切的是,在由简单个体组成的群落与环境以及个体之间的互动行为.也可称做群智能(swarmintelligence).这些模拟系统利用局部信息从而可能产生不可预测的群体行为例如floys和boids,他们都用来模拟鱼群和鸟群的运动规律,主要用于计算机视觉和计算机辅助设计.在计算智能(computationalintelligence)领域有两种基于群智能的算法.蚁群算法(antcolonyoptimization)和粒子群算法(particleswarmoptimization).前者是对蚂蚁群落食物采集过程的模拟.已经成功运用在很多离散优化问题上.粒子群优化算法(PSO)也是起源对简单社会系统的模拟.最初设想是模拟鸟群觅食的过程.但后来发现PSO是一种很好的优化工具.3.算法介绍如前所述，PSO模拟鸟群的捕食行为。设想这样一个场景：一群鸟在随机搜索食物。在这个区域里只有一块食物。所有的鸟都不知道食物在那里。但是他们知道当前的位置离食物还有多远。那么找到食物的最优策略是什么呢。最简单有效的就是搜寻目前离食物最近的鸟的周围区域。PSO从这种模型中得到启示并用于解决优化问题。PSO中，每个优化问题的解都是搜索空间中的一只鸟。我们称之为“粒子”。所有的例子都有一个由被优化的函数决定的适应值(fitnessvalue)，每个粒子还有一个速度决定他们飞翔的方向和距离。然后粒子们就追随当前的最优粒子在解空间中搜索PSO初始化为一群随机粒子(随机解)。然后通过叠代找到最优解。在每一次叠代中，粒子通过跟踪两个极值来更新自己。第一个就是粒子本身所找到的最优解。这个解叫做个体极值pBest.另一个极值是整个种群目前找到的最优解。这个极值是全局极值gBest。另外也可以不用整个种群而只是用其中一部分最为粒子的邻居，那么在所有邻居中的极值就是局部极值。程序的伪代码如下Foreachparticle____InitializeparticleENDDo____Foreachparticle________Calculatefitnessvalue________Ifthefitnessvalueisbetterthanthebestfitnessvalue(pBest)inhistory____________setcurrentvalueasthenewpBest____End____ChoosetheparticlewiththebestfitnessvalueofalltheparticlesasthegBest____Foreachparticle________Calculateparticlevelocityaccordingequation(a)________Updateparticlepositionaccordingequation(b)____EndWhilemaximumiterationsorminimumerrorcriteriaisnotattained在每一维粒子的速度都会被限制在一个最大速度Vmax，如果某一维更新后的速度超过用户设定的Vmax，那么这一维的速度就被限定为Vmax4.遗传算法和PSO的比较大多数演化计算技术都是用同样的过程1.种群随机初始化2.对种群内的每一个个体计算适应值(fitnessvalue).适应值与最优解的距离直接有关3.种群根据适应值进行复制4.如果终止条件满足的话，就停止，否则转步骤2从以上步骤，我们可以看到PSO和GA有很多共同之处。两者都随机初始化种群，而且都使用适应值来评价系统，而且都根据适应值来进行一定的随机搜索。两个系统都不是保证一定找到最优解但是，PSO没有遗传操作如交叉(crossover)和变异(mutation).而是根据自己的速度来决定搜索。粒子还有一个重要的特点，就是有记忆。与遗传算法比较,PSO的信息共享机制是很不同的.在遗传算法中，染色体(chromosomes)互相共享信息，所以整个种群的移动是比较均匀的向最优区域移动.在PSO中,只有gBest(orlBest)给出信息给其他的粒子，这是单向的信息流动.整个搜索更新过程是跟随当前最优解的过程.与遗传算法比较,在大多数的情况下，所有的粒子可能更快的收敛于最优解5.人工神经网络和PSO人工神经网络(ANN)是模拟大脑分析过程的简单数学模型，反向转播算法是最流行的神经网络训练算法。进来也有很多研究开始利用演化计算(evolutionarycomputation)技术来研究人工神经网络的各个方面。演化计算可以用来研究神经网络的三个方面：网络连接权重，网络结构(网络拓扑结构，传递函数)，网络学习算法。不过大多数这方面的工作都集中在网络连接权重，和网络拓扑结构上。在GA中，网络权重和/或拓扑结构一般编码为染色体(Chromosome)，适应函数(fitnessfunction)的选择一般根据研究目的确定。例如在分类问题中，错误分类的比率可以用来作为适应值演化计算的优势在于可以处理一些传统方法不能处理的例子例如不可导的节点传递函数或者没有梯度信息存在。但是缺点在于：在某些问题上性能并不是特别好。2.网络权重的编码而且遗传算子的选择有时比较麻烦最近已经有一些利用PSO来代替反向传播算法来训练神经网络的论文。研究表明PSO是一种很有潜力的神经网络算法。PSO速度比较快而且可以得到比较好的结果。而且还没有遗传算法碰到的问题这里用一个简单的例子说明PSO训练神经网络的过程。这个例子使用分类问题的基准函数(Benchmarkfunction)IRIS数据集。(Iris是一种鸢尾属植物)在数据记录中，每组数据包含Iris花的四种属性：萼片长度，萼片宽度，花瓣长度，和花瓣宽度，三种不同的花各有50组数据.这样总共有150组数据或模式。我们用3层的神经网络来做分类。现在有四个输入和三个输出。所以神经网络的输入层有4个节点，输出层有3个节点我们也可以动态调节隐含层节点的数目，不过这里我们假定隐含层有6个节点。我们也可以训练神经网络中其他的参数。不过这里我们只是来确定网络权重。粒子就表示神经网络的一组权重，应该是4*6+6*3=42个参数。权重的范围设定为[-100，100](这只是一个例子，在实际情况中可能需要试验调整).在完成编码以后，我们需要确定适应函数。对于分类问题，我们把所有的数据送入神经网络，网络的权重有粒子的参数决定。然后记录所有的错误分类的数目作为那个粒子的适应值。现在我们就利用PSO来训练神经网络来获得尽可能低的错误分类数目。PSO本身并没有很多的参数需要调整。所以在实验中只需要调整隐含层的节点数目和权重的范围以取得较好的分类效果。6.PSO的参数设置从上面的例子我们可以看到应用PSO解决优化问题的过程中有两个重要的步骤:问题解的编码和适应度函数PSO的一个优势就是采用实数编码,不需要像遗传算法一样是二进制编码(或者采用针对实数的遗传操作.例如对于问题f(x)=x1^2+x2^2+x3^2求解,粒子可以直接编码为(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:我们介绍了两种版本的粒子群优化算法:全局版和局部版.前者速度快不过有时会陷入局部最优.后者收敛速度慢一点不过很难陷入局部最优.在实际应用中,可以先用全局PSO找到大致的结果,再有局部PSO进行搜索.另外的一个参数是惯性权重,由Shi和Eberhart提出,有兴趣的可以参考他们1998年的论文(题目:Amodifiedparticleswarmoptimizer)蚁群算法简介：蚁群算法(antcolonyoptimization,ACO)，又称蚂蚁算法，是一种用来在图中寻找优化路径的机率型技术。它由MarcoDorigo于1992年在他的博士论文中引入，其灵感来源于蚂蚁在寻找食物过程中发现路径的行为。事实上，每只蚂蚁并不是像我们想象的需要知道整个世界的信息，他们其实只关心很小范围内的眼前信息，而且根据这些局部信息利用几条简单的规则进行决策，这样，在蚁群这个集体里，复杂性的行为就会凸现出来。这就是人工生命、复杂性科学解释的规律！那么，这些简单规则是什么呢？下面详细说明：1、范围：蚂蚁观察到的范围是一个方格世界，蚂蚁有一个参数为速度半径（一般是3），那么它能观察到的范围就是3*3个方格世界，并且能移动的距离也在这个范围之内。2、环境：蚂蚁所在的环境是一个虚拟的世界，其中有障碍物，有别的蚂蚁，还有信息素，信息素有两种，一种是找到食物的蚂蚁洒下的食物信息素，一种是找到窝的蚂蚁洒下的窝的信息素。每个蚂蚁都仅仅能感知它范围内的环境信息。环境以一定的速率让信息素消失。3、觅食规则：在每只蚂蚁能感知的范围内寻找是否有食物，如果有就直接过去。否则看是否有信息素，并且比较在能感知的范围内哪一点的信息素最多，这样，它就朝信息素多的地方走，并且每只蚂蚁多会以小概率犯错误，从而并不是往信息素最多的点移动。蚂蚁找窝的规则和上面一样，只不过它对窝的信息素做出反应，而对食物信息素没反应。4、移动规则：每只蚂蚁都朝向信息素最多的方向移，并且，当周围没有信息素指引的时候，蚂蚁会按照自己原来运动的方向惯性的运动下去，并且，在运动的方向有一个随机的小的扰动。为了防止蚂蚁原地转圈，它会记住最近刚走过了哪些点，如果发现要走的下一点已经在最近走过了，它就会尽量避开。5、避障规则：如果蚂蚁要移动的方向有障碍物挡住，它会随机的选择另一个方向，并且有信息素指引的话，它会按照觅食的规则行为。7、播撒信息素规则：每只蚂蚁在刚找到食物或者窝的时候撒发的信息素最多，并随着它走远的距离，播撒的信息素越来越少。根据这几条规则，蚂蚁之间并没有直接的关系，但是每只蚂蚁都和环境发生交互，而通过信息素这个纽带，实际上把各个蚂蚁之间关联起来了。比如，当一只蚂蚁找到了食物，它并没有直接告诉其它蚂蚁这儿有食物，而是向环境播撒信息素，当其它的蚂蚁经过它附近的时候，就会感觉到