pso的计算方法

《pso的计算方法》由会员分享，可在线阅读，更多相关《pso的计算方法（5页珍藏版）》请在装配图网上搜索。

1、.引言粒子群优化算法(PSO)是一种进化计算技术(evolutionary computation)，有Eberhart博士和kennedy 博士发明。源于对鸟群捕食的行为研究PSO同遗传算法类似，是一种基于叠代的优化工具。系统初始化为一组随机解，通过叠代搜寻最优值。但是并没有遗传算法用的交叉(crossover)以及变异(mutation)。而是粒子在解空间追随最优的粒子进行 搜索。详细的步骤以后的章节介绍同遗传算法比较，PSO的优势在于简单容易实现并且没有许多参数需要调整。目前已广泛应用于函数优 化，神经网络训练，模糊系统控制以及其他遗传算法的应用领域2. 背景：人工生命人工生命是来研究具

2、有某些生命基本特征的人工系统.人工生命包括两方面的内容1. 研究如何利用计算技术研究生物现象2. 研究如何利用生物技术研究计算问题我们现在关注的是第二部分的内容.现在已经有很多源于生物现象的计算技巧.例如，人工神经网络是 简化的大脑模型.遗传算法是模拟基因进化过程的.现在我们讨论另一种生物系统-社会系统.更确切的是，在由简单个体组成的群落与环境以及个体之间 的互动行为.也可称做群智能(swarm intelligence).这些模拟系统利用局部信息从而可能产生不可 预测的群体行为例如floys和boids，他们都用来模拟鱼群和鸟群的运动规律，主要用于计算机视觉和计算机辅助设 计.在计算智能(c

3、omputational intelligence)领域有两种基于群智能的算法.蚁群算法(ant colony optimization)和粒子群算法(particle swarm optimization).前者是对蚂蚁群落食物采集过程的模拟. 已经成功运用在很多离散优化问题上.粒子群优化算法(PSO)也是起源对简单社会系统的模拟.最初设想是模拟鸟群觅食的过程.但后来发现 PSO是一种很好的优化工具.3. 算法介绍如前所述，PSO模拟鸟群的捕食行为。设想这样一个场景：一群鸟在随机搜索食物。在这个区域里只有 一块食物。所有的鸟都不知道食物在那里。但是他们知道当前的位置离食物还有多远。那么找到食

4、物的 最优策略是什么呢。最简单有效的就是搜寻目前离食物最近的鸟的周围区域。PSO从这种模型中得到启示并用于解决优化问题。PSO中，每个优化问题的解都是搜索空间中的一只鸟。 我们称之为“粒子”。所有的例子都有一个由被优化的函数决定的适应值(fitness value)，每个粒子还 有一个速度决定他们飞翔的方向和距离。然后粒子们就追随当前的最优粒子在解空间中搜索PSO初始化为一群随机粒子(随机解)。然后通过叠代找到最优解。在每一次叠代中，粒子通过跟踪两个 极值来更新自己。第一个就是粒子本身所找到的最优解。这个解叫做个体极值pBest.另一个极值是整 个种群目前找到的最优解。这个极值是全局极值gBe

5、st。另外也可以不用整个种群而只是用其中一部分 最为粒子的邻居，那么在所有邻居中的极值就是局部极值。在找到这两个最优值时，粒子根据如下的公式来更新自己的速度和新的位置v = v + cl * 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.程序的伪代码如下For each parti

6、cleInitialize 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 particleCalculate particle v

7、elocity 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 value).适应值与最优解的距离直接

8、有关3. 种群根据适应值进行复制4. 如果终止条件满足的话，就停止，否则转步骤2 从以上步骤，我们可以看到PSO和GA有很多共同之处。两者都随机初始化种群，而且都使用适应值来评价系统，而且都根据适应值来进行一定的随机搜索。两个系统都不是保证一定找到最优解但是，PSO没有遗传操作如交叉(crossover)和变异(mutation).而是根据自己的速度来决定搜索。粒子 还有一个重要的特点，就是有记忆。与遗传算法比较，PSO的信息共享机制是很不同的.在遗传算法中，染色体(chromosomes)互相共享信 息，所以整个种群的移动是比较均匀的向最优区域移动.在PSO中，只有gBest (or lBe

9、st)给出信息 给其他的粒子，这是单向的信息流动.整个搜索更新过程是跟随当前最优解的过程.与遗传算法比较， 在大多数的情况下，所有的粒子可能更快的收敛于最优解5. 人工神经网络和PSO人工神经网络(ANN )是模拟大脑分析过程的简单数学模型，反向转播算法是最流行的神经网络训练算法。 进来也有很多研究开始利用演化计算(evolutionary computation)技术来研究人工神经网络的各个方 面。演化计算可以用来研究神经网络的三个方面：网络连接权重，网络结构(网络拓扑结构，传递函数)，网 络学习算法。不过大多数这方面的工作都集中在网络连接权重，和网络拓扑结构上。在GA中，网络权重和/或拓扑

10、结 构一般编码为染色体(Chromosome)，适应函数(fitness function)的选择一般根据研究目的确定。例如 在分类问题中，错误分类的比率可以用来作为适应值演化计算的优势在于可以处理一些传统方法不能处理的例子例如不可导的节点传递函数或者没有梯度信 息存在。但是缺点在于：在某些问题上性能并不是特别好。2.网络权重的编码而且遗传算子的选择有时 比较麻烦最近已经有一些利用PSO来代替反向传播算法来训练神经网络的论文。研究表明PSO是一种很有潜力的 神经网络算法。PSO速度比较快而且可以得到比较好的结果。而且还没有遗传算法碰到的问题这里用一个简单的例子说明PSO训练神经网络的过程。这个

11、例子使用分类问题的基准函数(Benchmark function)IRIS数据集。(Iris是一种鸢尾属植物)在数据记录中，每组数据包含Iris花的四种属性： 萼片长度，萼片宽度，花瓣长度，和花瓣宽度，三种不同的花各有50组数据.这样总共有150组数据或 模式。我们用3层的神经网络来做分类。现在有四个输入和三个输出。所以神经网络的输入层有4个节点，输 出层有3个节点我们也可以动态调节隐含层节点的数目，不过这里我们假定隐含层有6个节点。我们也 可以训练神经网络中其他的参数。不过这里我们只是来确定网络权重。粒子就表示神经网络的一组权重， 应该是4*6+6*3=42个参数。权重的范围设定为T00,

12、100(这只是一个例子，在实际情况中可能需要 试验调整)在完成编码以后，我们需要确定适应函数。对于分类问题，我们把所有的数据送入神经网络, 网络的权重有粒子的参数决定。然后记录所有的错误分类的数目作为那个粒子的适应值。现在我们就利 用PSO来训练神经网络来获得尽可能低的错误分类数目。PSO本身并没有很多的参数需要调整。所以在 实验中只需要调整隐含层的节点数目和权重的范围以取得较好的分类效果。6. PSO的参数设置 从上面的例子我们可以看到应用PSO解决优化问题的过程中有两个重要的步骤：问题解的编码和适应度 函数PSO的一个优势就是采用实数编码，不需要像遗传算法一样是二进制编码(或者采用针对实数

13、的遗传操 作.例如对于问题f(x) = x2 + x2”2+x3”2求解，粒子可以直接编码为(x1, x2, x3),而适应度函数 就是f(x).接着我们就可以利用前面的过程去寻优这个寻优过程是一个叠代过程，中止条件一般为设 置为达到最大循环数或者最小错误PSO中并没有许多需要调节的参数,下面列出了这些参数以及经验设置粒子数：一般取20 - 40.其实对于大部分的问题10个粒子已经足够可以取得好的结果，不过对于比 较难的问题或者特定类别的问题，粒子数可以取到100或200粒子的长度：这是由优化问题决定，就是问题解的长度粒子的范围：由优化问题决定,每一维可是设定不同的范围Vmax:最大速度,决定

14、粒子在一个循环中最大的移动距离,通常设定为粒子的范围宽度，例如上面的例子 里，粒子(x1, x2, x3) x1属于T0, 10,那么Vmax的大小就是20学习因子：cl和c2通常等于2.不过在文献中也有其他的取值.但是一般cl等于c2并且范围在0 和4之间中止条件：最大循环数以及最小错误要求.例如，在上面的神经网络训练例子中，最小错误可以设定为 1个错误分类，最大循环设定为2000,这个中止条件由具体的问题确定.全局PSO和局部PSO：我们介绍了两种版本的粒子群优化算法：全局版和局部版.前者速度快不过有时 会陷入局部最优.后者收敛速度慢一点不过很难陷入局部最优.在实际应用中，可以先用全局PS

15、O找到 大致的结果，再有局部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 particle swarm theory.One can

16、find much information from the internet Following are some information you can get online:http：/www. particleswarm .net 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

17、liography of particle swarmoptimization and some online paper links http:/www. researchindex .com/ you can search particle swarm related papers and referencesReferences:http:/www engriupui edu/eberhart/ http:/userserols .com/cathyk/jimkhtml http:/www alifeorghttp:/www aridolan com http:/iridia.ulb.a

18、c. be/mdorigo/ACO/AC0. html http:/www engriupui edu/shi/Coference/psopap4htmlKennedy, J and Eberhart, R C Particle swarm optimization Proc IEEE intl conf on neural networks Vol IV, pp 1942T948. IEEE service center, Piscataway, NJ, 1995 Eberhart, R C and Kennedy, J A new optimizer using particle swar

19、m theory. Proceedings of the sixth international symposium on micro machine and human science pp 39-43 IEEE service center, Piscataway, NJ, Nagoya, Japan, 1995Eberhart, R C and Shi, Y Particle swarm optimization: developments, applications and resources Proc congress on evolutionary computation 2001

20、 IEEE service center, Piscataway, 町,Seoul, Korea,2001.Eberhart, R C and Shi, Y Evolving artificial neural networks Proc 1998 Intl Con f on neural networks and brain pp PL5-PL13 Beijing, P R China, 1998Eberhart, R C and Shi, Y Comparison between genetic algorithms and particle swarm optimization Evol

21、utionary programming vii: proc 7th ann conf on evolutionary conf, Springer-Verlag, Berlin, San Diego, CA, 1998Shi, Y and Eberhart, R C Parameter selection in particle swarm optimization Evolutionary Programming VII: Proc. EP 98 pp. 591-600. Springer-Verlag, New York, 1998Shi, Y and Eberhart, R C A modified particle swarm optimizer Proceedings of the IEEE International Conference on Evolutionary Computation pp 69-73 IEEE Press, Piscataway, NJ, 1998