粒子群优化算法计算机数据结构与算法_计算机-数据结构与算法.pdf

《粒子群优化算法计算机数据结构与算法_计算机-数据结构与算法.pdf》由会员分享，可在线阅读，更多相关《粒子群优化算法计算机数据结构与算法_计算机-数据结构与算法.pdf（8页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

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

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

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

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

5、优值pBest。另一个最优值是整个种群目前找到的最优解，这个最优值是全局最优值 gBest。另外也可以不用整个种群而只是用其中一部分最为粒子的邻居，那么在所有邻居中 的极值就是局部极值。在找到这两个最优值后,粒子根据如下的公式来更新自己的速度和新的位置：vk+1=w*vk+c1*r1*(pbestk-presentk)+c2*r1*(gbestk-presentk)(a)presentk+1=persentk+vk+1(b)其中：w:速度惯性权重；vk:粒子 k 时刻的速度；persentk:粒子 k 时刻的位置；pbestk:个体最优值；gbestk:全局最优值；r1,r2:介于(0,1)之

6、间的随机数；c1,c2 是学习因 子；通常取 c1=c2=2。(a)式中第二项是“认知”部分，代表粒子对自身的学习；第三项是“社会”部分，代 表粒子间的协作。这两部分使粒子具有自我总结和像群体中最优个体学习的能力。4.算法流程 For each particle Initialize particle END Do For each particle Calculate fitness value If the fitness value is better than the best fitness value(pBest)in history set current value as th

7、e new pBest End Choose the particle with the best fitness value of all the particles as the gBest For each particle Calculate particle velocity according equation(a)Update particle position according equation(b)End While maximum iterations or minimum error criteria is not attained 在每一维粒子的速度都会被限制在一个最

8、大速度 Vmax，如果某一维更新后的速度超过用 户设定的 Vmax，那么这一维的速度就被限定为 Vmax。5.PSO 的参数设置 从上面的例子我们可以看到应用 PSO 解决优化问题的过程中有两个重要的步骤：问题 解的编码和适应度函数。PSO 的一个优势就是采用实数编码，不需要像遗传算法一样是二进 种基于叠代的优化工具系统初始化为一组随机解通过叠以及变异而是粒子在解空间追随最优的粒子进行搜索详细的步骤以后的章节介绍代搜寻最优值但是并没有遗传算法用的交叉同遗传算法比较的优势在于简单容易实现并且没有许人工生是来研究具有某些生基本特征的人工系统人工生包括两方面的内容研究如何利用计算技术研究生物现象研究

9、如何利用生物技术研究计算问题我们现在关注的是第二部分的内容现在已经有很多源于生物现象的计算技巧例如人工由简单个体组成的群落与环境以及个体之间的互动行为也可称做群智能这些模拟系统利用局部信息从而可能产生不可预测的群体行为例如和他们都用来模拟鱼群和鸟群的运动规律主要用于计算机视觉和计算机辅助设计在计算智能领Wmax Wmax wmjn iter iter max 制编码(或者采用针对实数的遗传操作).例如对于问题 f(x)=x1A2+x2A2+x3A2 求解，粒子 可以直接编码为(x1,x2,x3),而适应度函数就是 f(x).接着我们就可以利用前面的过程去寻 优 这个寻优过程是一个叠代过程，中止

10、条件一般为设置为达到最大循环数或者最小错误 PSO 中并没有许多需要调节的参数，下面列出了这些参数以及经验设置：粒子数：一般取 20-40.其实对于大部分的问题 10 个粒子已经足够可以取得好的结果，不过对于比较难的问题或者特定类别的问题，粒子数可以取到 100 或 200 粒子的长度：这是由优化问题决定，就是问题解的长度 粒子的范围：由优化问题决定，每一维可是设定不同的范围 Vmax:最大速度，决定粒子在一个循环中最大的移动距离，通常设定为粒子的范围宽度，例如上面的例子里，粒子(x1,x2,x3)x1属于-10，10，那么 Vmax 的大小就是 20 学习因子：c1 和 c2 通常等于 2.

11、不过在文献中也有其他的取值 但是一般 c1 等于 c2 并且范围在 0 和 4 之间 中止条件：最大循环数以及最小错误要求 例如，在上面的神经网络训练例子中，最小 错误可以设定为 1 个错误分类，最大循环设定为 2000,这个中止条件由具体的问题确定 全局 PSO 和局部 PSO：我们介绍了两种版本的粒子群优化算法：全局版和局部版 前者 速度快不过有时会陷入局部最优 后者收敛速度慢一点不过很难陷入局部最优 在实际应用 中，可以先用全局 PSO 找到大致的结果，再由局部 PSO 进行搜索 6.参数对 PSO 算法性能的影响 1).学习因子c1、c2 对算法性能的影响 学习因子 c1、c2 对算法

12、的收敛性影响不大，但如果调整合适的话可以减少局部最优值 的干扰，使收敛速度变快。设粒子限制速度最大值为 Vmax，最小值设为Vmin。最大值参数Vmax 被证明对 PSO 算法性能影响很重要，vmax值太大会导致粒子跳过最优解，太小的话会导致 搜索空间不充分，找不到全局最优解。在大量试验和应用中得出结论：取 Vmax zmax，即速 度最大值为每个粒子在每维位置允许的变化范围时，算法会取得更好优化效果。2).惯性权重 w 对算法性能的影响 当惯性权重较小时(w1.2)时，PSO 更像全局最优 算法，需更多迭代次数达到全局最优解，且更可能找不到全局最优解；当惯性权重适中时 PSO 将会有更大的机

13、会找到全局最优解，迭代次数可能会比第一种情况多。惯性权重形式通常为：种基于叠代的优化工具系统初始化为一组随机解通过叠以及变异而是粒子在解空间追随最优的粒子进行搜索详细的步骤以后的章节介绍代搜寻最优值但是并没有遗传算法用的交叉同遗传算法比较的优势在于简单容易实现并且没有许人工生是来研究具有某些生基本特征的人工系统人工生包括两方面的内容研究如何利用计算技术研究生物现象研究如何利用生物技术研究计算问题我们现在关注的是第二部分的内容现在已经有很多源于生物现象的计算技巧例如人工由简单个体组成的群落与环境以及个体之间的互动行为也可称做群智能这些模拟系统利用局部信息从而可能产生不可预测的群体行为例如和他们都

14、用来模拟鱼群和鸟群的运动规律主要用于计算机视觉和计算机辅助设计在计算智能领其中：Wmax为初始权重，Wmin为最终权重，iteax为最大迭代次数，iter为当前迭代 次数。通过调整，算法在开始时倾向于开掘，然后逐步转向于开拓，从而在局部区域调整解。这些改进使 PSO 算法性能得到很大提高。3).收缩因子 对算法性能的影响 收缩因子 可以保证算法收敛。是关于参数 cl 和 c2 的函数，一个简单的收缩因子定 义为：弓 I入收缩因子后，就不在需要 Vmax 了，但其性能未必比 1)中取Vmax Zmax时效果好。5.PSO 和遗传算法的比较 PSO 和 GA 有很多共同之处。两者都随机初始化种群，

15、而且都使用适应值来评价系统，而且都根据适应值来进行一定的随机搜索。两个系统都不是保证一定找到最优解。PSO 没有遗传操作如交叉(crossover)和变异(mutation).而是根据自己的速度来决定搜 索。粒子还有一个重要的特点，就是有记忆。与遗传算法比较，PSO 的信息共享机制是很不同的.在遗传算法中，染色体互相共享信 息，所以整个种群的移动是比较均匀的向最优区域移动.在 PSO 中，只有 gBest(or lBest)给 出信息给其他的粒子，这是单向的信息流动.整个搜索更新过程是跟随当前最优解的过程.与遗传算法比较，在大多数的情况下，所有的粒子可能更快的收敛于最优解。PSO 和 GA 不

16、同点：(1)PSO 有记忆，好的解的知识所有粒子都保存，而 GA，以前的知识随着种群的改变 被破坏。(2)PSO 中的粒子仅仅通过当前搜索到最优点进行共享信息，所以很大程度上这是一种 单项信息共享机制。而 GA 中，染色体之间相互共享信息，使得整个种群都向最优区域移动。(3)GA 的编码技术和遗传操作比较简单，而 PSO 相对于 GA，没有交叉和变异操作，粒子只是通过内部速度进行更新，因此原理更简单、参数更少、实现更容易。(4)在收敛性方面，GA 已经有了较成熟的收敛性分析方法，并且可对收敛速度进行估 计;而 PSO 这方面的研究还比较薄弱。尽管己经有简化确定性版本的收敛性分析，但将确定 性向

17、随机性的转化尚需进一步研究。(5)在稳定性方面，遗传算法稳定性似乎比粒子算法要好。(6)在应用方面，PSO 算法主要应用于连续问题，包括神经网络训练和函数优化等，而 GA 除了连续问题之外，还可应用于离散问题，比如 TSP 问题、货郎担问题、工作车间 调度等。5.人工神经网络和 PSO 人工神经网络(ANN)是模拟大脑分析过程的简单数学模型，反向转播算法是最流行的神 经网络训练算法。进来也有很多研究开始利用演化计算(evolutionary computation)技术来研究 人工神经网,1 Ci C2,l 种基于叠代的优化工具系统初始化为一组随机解通过叠以及变异而是粒子在解空间追随最优的粒子

18、进行搜索详细的步骤以后的章节介绍代搜寻最优值但是并没有遗传算法用的交叉同遗传算法比较的优势在于简单容易实现并且没有许人工生是来研究具有某些生基本特征的人工系统人工生包括两方面的内容研究如何利用计算技术研究生物现象研究如何利用生物技术研究计算问题我们现在关注的是第二部分的内容现在已经有很多源于生物现象的计算技巧例如人工由简单个体组成的群落与环境以及个体之间的互动行为也可称做群智能这些模拟系统利用局部信息从而可能产生不可预测的群体行为例如和他们都用来模拟鱼群和鸟群的运动规律主要用于计算机视觉和计算机辅助设计在计算智能领络的各个方面。演化计算可以用来研究神经网络的三个方面：网络连接权重，网络结构(网

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

20、神经网络算法。PSO 速度比较快而且可以得到比较好的结果。而且还没 有遗传算法碰到的问题 这里用一个简单的例子说明 PSO 训练神经网络的过程。这个例子使用分类问题的基准 函数(Benchmark function)IRIS 数据集。(Iris 是一种鸢尾属植物)在数据记录中，每组数据包 含 Iris 花的四种属性：萼片长度，萼片宽度，花瓣长度，和花瓣宽度，三种不同的花各有 50 组数据.这样总共有 150 组数据或模式。我们用 3 层的神经网络来做分类。现在有四个输入和三个输出。所以神经网络的输入层 有 4 个节点，输出层有 3 个节点我们也可以动态调节隐含层节点的数目，不过这里我们假定 隐

21、含层有 6 个节点。我们也可以训练神经网络中其他的参数。不过这里我们只是来确定网络 权重。粒子就表示神经网络的一组权重，应该是 4*6+6*3=42 个参数。权重的范围设定为-100，100(这只是一个例子，在实际情况中可能需要试验调整).在完成编码以后，我们需要确定适 应函数。对于分类问题，我们把所有的数据送入神经网络，网络的权重有粒子的参数决定。然后记录所有的错误分类的数目作为那个粒子的适应值。现在我们就利用 PSO 来训练神经 网络来获得尽可能低的错误分类数目。PSO 本身并没有很多的参数需要调整。所以在实验 中只需要调整隐含层的节点数目和权重的范围以取得较好的分类效果。种基于叠代的优化

22、工具系统初始化为一组随机解通过叠以及变异而是粒子在解空间追随最优的粒子进行搜索详细的步骤以后的章节介绍代搜寻最优值但是并没有遗传算法用的交叉同遗传算法比较的优势在于简单容易实现并且没有许人工生是来研究具有某些生基本特征的人工系统人工生包括两方面的内容研究如何利用计算技术研究生物现象研究如何利用生物技术研究计算问题我们现在关注的是第二部分的内容现在已经有很多源于生物现象的计算技巧例如人工由简单个体组成的群落与环境以及个体之间的互动行为也可称做群智能这些模拟系统利用局部信息从而可能产生不可预测的群体行为例如和他们都用来模拟鱼群和鸟群的运动规律主要用于计算机视觉和计算机辅助设计在计算智能领6.算法源

23、代码 *PSO 算法源代码*#include#include#include#include#define P_num 20#define dim 3#define iter_num 500#define V_max 20#define c1 2#define c2 2#define w 0.5#define alp 1/粒子数目/粒子空间维数/速度范围/惯性因子/收缩因子 double lwdim=-1,-2,1;double hgdim=2,0,5;double particleP_numdim;double particle_loc_bestP_numdim;double particl

24、e_loc_fitP_num;double particle_glo_bestdim;double gfit;double particle_vP_numdim;double particle_fitP_num;/每维搜索域范围/个体集合/每个个体局部最优向量/个体的局部最优适应度/全局最优向量/全局最优适应度/记录每个个体的当前代速度向量/记录每个粒子的当前代适应度 double fitness(double x)double sum=0.0;sum=x0*x0-x0*x1+x2;return sum;void initial()int i,j;for(i=0;iP_num;i+)for(j

25、=0;jdim;j+)/初始化粒子/随机生成粒子 particleij=lwj+(hgj-lwj)*1.0*rand()/RAND_MAX;/初始化群体 particle_loc_bestij=particleij;/将当前最优结果写入局部最优集合 particle_vij=-V_max+2*V_max*1.0*rand()/RAND_MAX;/速度 for(i=0;iP_num;i+)/计算每个粒子的适应度 种基于叠代的优化工具系统初始化为一组随机解通过叠以及变异而是粒子在解空间追随最优的粒子进行搜索详细的步骤以后的章节介绍代搜寻最优值但是并没有遗传算法用的交叉同遗传算法比较的优势在于简单容

26、易实现并且没有许人工生是来研究具有某些生基本特征的人工系统人工生包括两方面的内容研究如何利用计算技术研究生物现象研究如何利用生物技术研究计算问题我们现在关注的是第二部分的内容现在已经有很多源于生物现象的计算技巧例如人工由简单个体组成的群落与环境以及个体之间的互动行为也可称做群智能这些模拟系统利用局部信息从而可能产生不可预测的群体行为例如和他们都用来模拟鱼群和鸟群的运动规律主要用于计算机视觉和计算机辅助设计在计算智能领particle_fiti=fitness(particlei);particle_loc_fiti=particle_fiti;gfit=particle_loc_fit0;/找

27、出全局最优 j=0;for(i=1;igfit)gfit=particle_loc_fiti;j=i;for(i=0;idim;i+)/更新全局最优向量 particle_glo_besti=particle_loc_bestji;void renow_p_g()/更新最优值、最优向量 int i,j;for(i=0;i particle_loc_fiti)/更新个体局部最优值 particle_loc_fiti=particle_fiti;for(j=0;jdim;j+)/更新局部最优向量 particle_loc_bestij=particleij;for(i=0,j=-1;igfit)g

28、fit=particle_loc_fiti;j=i;if(j!=-1)for(i=0;idim;i+)/更新全局最优向量 particle_glo_besti=particle_loc_bestji;void renew_particle()/更新个体位置 int i,j;for(i=0;iP_num;i+)for(j=0;j hgj)particleij=hgj;if(particleij lwj)particleij=lwj;void renew_var()/更新个体速度 Int i,j;for(i=0;iP_num;i+)for(j=0;j V_max)particle_vij=V_ma

29、x;if(particle_vij -V_max)particle_vij=-V_max;void main()int i=0;srand(unsigned)time(NULL);initial();while(i iter_num)renow_p_g();renew_particle();renew_var();printf(%lfn,gfit);i+;种基于叠代的优化工具系统初始化为一组随机解通过叠以及变异而是粒子在解空间追随最优的粒子进行搜索详细的步骤以后的章节介绍代搜寻最优值但是并没有遗传算法用的交叉同遗传算法比较的优势在于简单容易实现并且没有许人工生是来研究具有某些生基本特征的人工系统人工生包括两方面的内容研究如何利用计算技术研究生物现象研究如何利用生物技术研究计算问题我们现在关注的是第二部分的内容现在已经有很多源于生物现象的计算技巧例如人工由简单个体组成的群落与环境以及个体之间的互动行为也可称做群智能这些模拟系统利用局部信息从而可能产生不可预测的群体行为例如和他们都用来模拟鱼群和鸟群的运动规律主要用于计算机视觉和计算机辅助设计在计算智能领