《PSO粒子群优化算法》由会员分享，可在线阅读，更多相关《PSO粒子群优化算法（11页珍藏版）》请在金锄头文库上搜索。
1、PSO粒子群优化算法1. 引言粒子群优化算法(PSO)是一种进化计算技术(evolutionary computation),由Eberhart博士和 kennedy博士发明。源于对鸟群捕食的行为研究PSO同遗传算法类似，是一种基于迭代的优化工具。系统初始化为一组随机解，通过迭代搜 寻最优值。但是并没有遗传算法用的交叉(crossover)以及变异(mutation)。而是粒子在解空间 追随最优的粒子进行搜索。详细的步骤以后的章节介绍同遗传算法比较，PSO的优势在于简单容易实现并且没有许多参数需要调整。目前已广泛应 用于函数优化，神经网络训练，模糊系统控制以及其他遗传算法的应用领域2. 背景：
2、人工生命人工生命是来研究具有某些生命基本特征的人工系统.人工生命包括两方面的内容1. 研究如何利用计算技术研究生物现象2. 研究如何利用生物技术研究计算问题我们现在关注的是第二部分的内容.现在已经有很多源于生物现象的计算技巧.例如，人工 神经网络是简化的大脑模型.遗传算法是模拟基因进化过程的.现在我们讨论另一种生物系统-社会系统.更确切的是，在由简单个体组成的群落与环境以 及个体之间的互动行为.也可称做群智能(swarm intelligence).这些模拟系统利用局部信息 从而可能产生不可预测的群体行为例如floys和boids,他们都用来模拟鱼群和鸟群的运动规律,主要用于计算机视觉和计算
3、机辅助设计.在计算智能(computational intelligence)领域有两种基于群智能的算法.蚁群算法(ant colony optimization)和粒子群算法(particle swarm optimization).前者是对蚂蚁群落食物采集过程的 模拟.已经成功运用在很多离散优化问题上.粒子群优化算法(PSO)也是起源对简单社会系统的模拟.最初设想是模拟鸟群觅食的过程. 但后来发现PSO是一种很好的优化工具.3. 算法介绍如前所述，PSO模拟鸟群的捕食行为。设想这样一个场景：一群鸟在随机搜索食物。在这个 区域里只有一块食物。所有的鸟都不知道食物在那里。但是他们知道当前的位置
4、离食物还有 多远。那么找到食物的最优策略是什么呢。最简单有效的就是搜寻目前离食物最近的鸟的周 围区域。PSO从这种模型中得到启示并用于解决优化问题。PSO中，每个优化问题的解都是搜索空间 中的一只鸟。我们称之为“粒子”。所有的例子都有一个由被优化的函数决定的适应值(fitness value)，每个粒子还有一个速度决定他们飞翔的方向和距离。然后粒子们就追随当前的最优 粒子在解空间中搜索PSO初始化为一群随机粒子(随机解)。然后通过叠代找到最优解。在每一次叠代中，粒子通 过跟踪两个极值来更新自己。第一个就是粒子本身所找到的最优解。这个解叫做个体极值 pBest.另一个极值是整个种群目前找到的最优
5、解。这个极值是全局极值gBest。另外也可以 不用整个种群而只是用其中一部分最为粒子的邻居，那么在所有邻居中的极值就是局部极值。 在找到这两个最优值时，粒子根据如下的公式来更新自己的速度和新的位置 v = v + c1 * rand() * (pbest - present) + c2 * rand() * (gbest - present) (a) present = persent + v (b)v是粒子的速度，persent是当前粒子的位置.pbest and gbest如前定义rand ()是介 于(0， 1)之间的随机数.c1, c2是学习因子.通常c1 = c2 = 2.程序的伪代
6、码如下For each particleInitialize particleENDDoFor each particleCalculate fitness valueIf the fitness value is better than the best fitness value (pBest) in history set current value as the new pBestEndChoose the particle with the best fitness value of all the particles as the gBestFor each particleCal
7、culate particle velocity according equation (a)Update particle position according equation (b)EndWhile maximum iterations or minimum error criteria is not attained在每一维粒子的速度都会被限制在一个最大速度Vmax，如果某一维更新后的速度超过用户 设定的Vmax，那么这一维的速度就被限定为Vmax4,遗传算法和PSO的比较大多数演化计算技术都是用同样的过程1. 种群随机初始化2. 对种群内的每一个个体计算适应值(fitness val
8、ue).适应值与最优解的距离直接有关3. 种群根据适应值进行复制4. 如果终止条件满足的话，就停止，否则转步骤2从以上步骤，我们可以看到PSO和GA有很多共同之处。两者都随机初始化种群，而且都使 用适应值来评价系统，而且都根据适应值来进行一定的随机搜索。两个系统都不是保证一定 找到最优解但是，PSO没有遗传操作如交叉(crossover)和变异(mutation).而是根据自己的速度来决定搜 索。粒子还有一个重要的特点，就是有记忆。与遗传算法比较,PSO的信息共享机制是很不同的.在遗传算法中，染色体(chromosomes) 互相共享信息，所以整个种群的移动是比较均匀的向最优区域移动.在PSO
9、中，只有gBest (or lBest)给出信息给其他的粒子，这是单向的信息流动.整个搜索更新过程是跟随当前最优 解的过程.与遗传算法比较，在大多数的情况下，所有的粒子可能更快的收敛于最优解5. 人工神经网络和PSO人工神经网络(ANN )是模拟大脑分析过程的简单数学模型，反向转播算法是最流行的神经网 络训练算法。进来也有很多研究开始利用演化计算(evolutionary computation)技术来研究人 工神经网络的各个方面。演化计算可以用来研究神经网络的三个方面：网络连接权重，网络结构(网络拓扑结构，传 递函数)，网络学习算法。不过大多数这方面的工作都集中在网络连接权重，和网络拓扑结构
10、上。在GA中，网络权重 和/或拓扑结构一般编码为染色体(Chromosome)，适应函数(fitness function)的选择一般根据 研究目的确定。例如在分类问题中，错误分类的比率可以用来作为适应值演化计算的优势在于可以处理一些传统方法不能处理的例子例如不可导的节点传递函数或 者没有梯度信息存在。但是缺点在于：在某些问题上性能并不是特别好。2.网络权重的编 码而且遗传算子的选择有时比较麻烦最近已经有一些利用PSO来代替反向传播算法来训练神经网络的论文。研究表明PSO是一 种很有潜力的神经网络算法。PSO速度比较快而且可以得到比较好的结果。而且还没有遗传 算法碰到的问题这里用一个简单的例子
11、说明PSO训练神经网络的过程。这个例子使用分类问题的基准函数 (Benchmark function)IRIS数据集。(Iris是一种鸢尾属植物)在数据记录中，每组数据包含Iris 花的四种属性：萼片长度，萼片宽度，花瓣长度，和花瓣宽度，三种不同的花各有50组数 据.这样总共有150组数据或模式。我们用3层的神经网络来做分类。现在有四个输入和三个输出。所以神经网络的输入层有4 个节点，输出层有3个节点我们也可以动态调节隐含层节点的数目，不过这里我们假定隐含 层有6个节点。我们也可以训练神经网络中其他的参数。不过这里我们只是来确定网络权重。 粒子就表示神经网络的一组权重，应该是4*6+6*3=4
12、2个参数。权重的范围设定为-100，100 (这只是一个例子，在实际情况中可能需要试验调整).在完成编码以后，我们需要确定适应函 数。对于分类问题，我们把所有的数据送入神经网络，网络的权重有粒子的参数决定。然后 记录所有的错误分类的数目作为那个粒子的适应值。现在我们就利用PSO来训练神经网络 来获得尽可能低的错误分类数目。PSO本身并没有很多的参数需要调整。所以在实验中只需 要调整隐含层的节点数目和权重的范围以取得较好的分类效果。6. PSO的参数设置从上面的例子我们可以看到应用PSO解决优化问题的过程中有两个重要的步骤：问题解的 编码和适应度函数PSO的一个优势就是采用实数编码，不需要像遗传
13、算法一样是二进制编码(或者采用针对实 数的遗传操作.例如对于问题f(x) = x1A2 + x2A2+x3A2求解，粒子可以直接编码为(x1, x2, x3), 而适应度函数就是f(x).接着我们就可以利用前面的过程去寻优.这个寻优过程是一个叠代过 程，中止条件一般为设置为达到最大循环数或者最小错误PSO中并没有许多需要调节的参数，下面列出了这些参数以及经验设置粒子数：一般取20 - 40.其实对于大部分的问题10个粒子已经足够可以取得好的结果, 不过对于比较难的问题或者特定类别的问题 粒子数可以取到100或200 粒子的长度：这是由优化问题决定，就是问题解的长度粒子的范围：由优化问题决定,每
14、一维可是设定不同的范围Vmax:最大速度，决定粒子在一个循环中最大的移动距离，通常设定为粒子的范围宽度，例如 上面的例子里，粒子(x1, x2, x3) x1属于-10, 10,那么Vmax的大小就是20学习因子：c1和c2通常等于2.不过在文献中也有其他的取值.但是一般c1等于c2并 且范围在0和4之间中止条件：最大循环数以及最小错误要求.例如，在上面的神经网络训练例子中，最小错误 可以设定为1个错误分类，最大循环设定为2000,这个中止条件由具体的问题确定.全局PSO和局部PSO：我们介绍了两种版本的粒子群优化算法：全局版和局部版.前者速度 快不过有时会陷入局部最优.后者收敛速度慢一点不过
15、很难陷入局部最优.在实际应用中, 可以先用全局PSO找到大致的结果，再有局部PSO进行搜索.另外的一个参数是惯性权重，由Shi和Eberhart提出，有兴趣的可以参考他们1998年的论文(题目：A modified particle swarm optimizer)7. Online Resources of PSOThe development of PSO is still ongoing. And there are still many unknown areas in PSO research such as the mathematical validation of partic
16、le swarm theory.One can find much information from the internet. Following are some information you can get online：http:/ lots of information about Particle Swarms and, particularly, Particle Swarm Optimization. lots of Particle Swarm Links.http:/icdweb.cc.purdue.edu/hux/PSO.shtml lists an updated bib
