第37卷第4期河北工业大学学报2008年8月V ol.37No.4JOURNAL OF HEBEI UNIVERSITY OF TECHNOLOGY August2008 文章编号：1008-2373(2008)04-0055-05 改进的粒子群优化算法 宋洁，董永峰，侯向丹，杨彦卿 （河北工业大学计算机科学与软件学院，天津300401） 摘要粒子群优化算法是一种基于群体的自适应搜索优化算法，存在后期收敛慢、搜索精度低、容易陷入局部极 小等缺点，为此提出了一种改进的粒子群优化算法，从初始解和搜索精度两个方面进行了改进，提高了算法的计 算精度，改善了算法收敛性，很大程度上避免了算法陷入局部极小．对经典函数测试计算，验证了算法的有效性． 关键词粒子群优化算法；均匀化；变量搜索；初始解；搜索精度 中图分类号TP391文献标识码A A Modified Particle Swarm Optimization Algorithm SONG Jie,DONG Yong-feng,HOU Xiang-dan,Y ANG Yan-qing (School of Computer Science and Engineering,Hebei University of Technology,Tianjin300401,China) Abstract Particle Swarm Optimization Algorithm is a kind of auto-adapted search optimization based on community. But the standard particle swarm optimization is used resulting in slow after convergence,low search precision and easily leading to local minimum.A new Particle Swarm Optimization algorithm is proposed to improve from the initial solution and the search precision.The obtained results showed the algorithm computation precision and the astringency are im- proved,and local minimum is avoided.The experimental results of classic functions show that the improved PSO is ef- ficient and feasible. Key words PSO；average；variable search；initial solution；search accuracy 0引言 粒子群优化（Particle Swarm Optimization，PSO）算法是一种基于群体的随机优化技术，最早在1995年由美国社会心理学家James Kennedy和电气工程师Russell Eberhart[1]共同提出，基本思想源于对鸟群觅食行为的研究．PSO将每个可能产生的解都表述为群中的一个微粒，每个微粒都具有自己的位置向量和速度向量，和一个由目标函数决定的适应度，通过类似梯度下降算法使各粒子向适应度函数值最高的方向群游．该算法控制参数少、程序相对简单，因此在应用领域表现出了很大的优越性．由于PSO算法容易理解、易于实现，所以PSO算法发展很快．目前，多种PSO改进算法已广泛应用于函数优化、神经网络训练、模式识别、模糊系统控制以及其他的应用领域． 许多学者对PSO算法进行研究，发现其容易出现早熟、最优解附近收敛慢等现象，并提出了一些改进方案，例如自适应PSO算法、混合PSO算法、杂交PSO算法等[2-4]．因此，本文从初始解和收敛精度两个角度出发对PSO算法进行了改进，提高了算法的计算精度，有效的改善了算法的优化性能． 1基本PSO算法 PSO算法是一种基于群体的随机优化技术，基本思想源于对鸟群觅食行为的研究．通过对鸟群飞行时经常会突然改变方向、散开、聚集，但整体总保持一致性，个体与个体间鸟群好像在一个中心的控制 收稿日期：2008-04-17 基金项目：河北省自然科学基金（F2006000109） 作者简介：宋洁（1967-），女（汉族），副教授．
1.Pso算法 function [xm,fv] = SAPSO( fitness,N,c1,c2,wmax,wmin,M ) % fitness 适应度函数 % N 种群个数 % c1 % c2 % wmax 最大权重 % wmin 最小权重 % M 迭代次数 cg=32;%传感器个数 format long; %-----------------------初始化种群个体 ------------------------------------- for i=1:N %粒子个数为n a1=-17.5:10:12.5; a11=a1*(i+5)/10; [a2,a3]=meshgrid(a1,a11); a4=reshape(a2,1,16); a5=reshape(a3,1,16); b1=-12.5:10:17.5; b11=b1*(i+5)/10; [b2,b3]=meshgrid(b1,b11); b4=reshape(b2,1,16); b5=reshape(b3,1,16); x11=[a4,b4;a5,b5]+20;%ó|ó?μè±èàyà?é￠y1ì?¨ x(:,:,i)=x11';%初始化传感器个数为20 v(:,:,i)=10*rand(cg,2); end %----------------------计算各个粒子适应度------------------------------for i=1:N; p(i)=fitness(x(:,:,i)); y(:,:,i)=x(:,:,i); end pg=x(:,:,N); %pg为全局最优 for i=1:(N-1) if fitness(x(:,:,i)) 基本粒子群算法的原理和matlab程序 作者——niewei120（nuaa） 一、粒子群算法的基本原理 粒子群优化算法源自对鸟群捕食行为的研究，最初由Kennedy和Eberhart提出，是一种通用的启发式搜索技术。一群鸟在区域中随机搜索食物，所有鸟知道自己当前位置离食物多远，那么搜索的最简单有效的策略就是搜寻目前离食物最近的鸟的周围区域。PSO 算法利用这种模型得到启示并应用于解决优化问题。PSO 算法中，每个优化问题的解都是粒子在搜索 空间中的位置，所有的粒子都有一个被优化的目标函数所决定的适应值，粒子还有一个速度值决定它们飞翔的方向和距离，然后粒子群就追随当前的最优粒子在解空间中搜索。 PSO 算法首先在给定的解空间中随机初始化粒子群，待优化问题的变量数决定了解空间的维数。每个粒子有了初始位置与初始速度。然后通过迭代寻优。在每一次迭代中，每个粒子通过跟踪两个“极值”来更新自己在解空间中的空间位置与飞翔速度。第一个极值就是单个粒子本身在迭代过程中找到的最优解粒子，这个粒子叫做个体极值。另一个极值是种群所有粒子在迭代过程中所找到的最优解粒子，这个粒子是全局极值。上述的方法叫全局粒子群算法。如果不用种群所有粒子而只用其中一部分作为该粒子的邻居粒子，那么在所有邻居粒子中的极值就是局部极值，该方法称为局部PSO 算法。 速度、位置的更新方程表示为： 每个粒子自身搜索到的历史最优值p i ，p i=(p i1,p i2,....,p iQ)，i=1,2,3,....,n。所有粒子搜索到的最优值p g，p g=(p g1,p g2,....,p gQ)，注意这里的p g只有一个。 是保持原来速度的系数，所以叫做惯性权重。 是粒子跟踪自己历史最优值的权重系数，它表示粒子自身的认识，所以叫“认知”。通常设置为2。 是粒子跟踪群体最优值的权重系数，它表示粒子对整个群体知识的认识，所以叫做“社会知识”，经常叫做“社会”。通常设置为2。 是[0,1]区间内均匀分布的随机数。 是对位置更新的时候，在速度前面加的一个系数，这个系数我们叫做约束因子。通常设 置为1 。 第７期２０１６年７月电 子 学 报ＡＣＴＡＥＬＥＣＴＲＯＮＩＣＡＳＩＮＩＣＡＶｏｌ．４４ Ｎｏ．７Ｊｕｌ． ２０１６ 收稿日期：２０１５-０４-０７；修回日期：２０１５-０６-２１；责任编辑：覃怀银 基金项目：国家自然科学基金（Ｎｏ．６１３０００５９，Ｎｏ．６１４７２０５６）；安徽高校省级自然科学基金（Ｎｏ．ＫＪ２０１２Ｚ０３１，Ｎｏ．ＫＪ２０１２Ｚ０２４） 并行协作骨干粒子群优化算法 申元霞１，曾传华２，王喜凤１，汪小燕１ （１．安徽工业大学计算机科学与技术学院，安徽马鞍山２４３０３２；２．安徽工业大学数理科学与工程学院，安徽马鞍山２４３０３２） 摘 要： 为解决骨干粒子群优化（Ｂａｒｅ-ＢｏｎｅＰａｒｔｉｃｌｅＳｗａｒｍＯｐｔｉｍｉｚａｔｉｏｎ，ＢＢＰＳＯ）的早期收敛问题，本文通过粒子的运动行为分析了导致ＢＢＰＳＯ早期收敛的因素， 并提出并行协作ＢＢＰＳＯ，该算法采用并行的主群和从群之间的协作学习来平衡勘探和开采能力．为了增强主群的勘探能力，提出动态学习榜样策略以保持群体多样性；同时提出随机反向学习机制以实现从群的从全局到局部的自适应搜索功能．在１４个不同特征的测试函数上将本文算法与６种知名的ＢＢＰＳＯ算法进行对比，仿真结果和统计分析表明本文算法在收敛速度和精度上都有显著提高． 关键词： 骨干粒子群优化；协作学习；反向学习；多样性 中图分类号： ＴＰ３８ 文献标识码： Ａ 文章编号： ０３７２-２１１２（２０１６）０７-１６４３-０６电子学报ＵＲＬ：ｈｔｔｐ：／／ｗｗｗ．ｅｊｏｕｒｎａｌ．ｏｒｇ．ｃｎ ＤＯＩ：１０．３９６９／ｊ．ｉｓｓｎ．０３７２-２１１２．２０１６．０７．０１８ ＡＰａｒａｌｌｅｌ-ＣｏｏｐｅｒａｔｉｖｅＢａｒｅ-ＢｏｎｅＰａｒｔｉｃｌｅＳｗａｒｍＯｐｔｉｍｉｚａｔｉｏｎＡｌｇｏｒｉｔｈｍ ＳＨＥＮＹｕａｎ-ｘｉａ１，ＺＥＮＧＣｈｕａｎ-ｈｕａ２，ＷＡＮＧＸｉ-ｆｅｎｇ１，ＷＡＮＧＸｉａｏ-ｙａｎ１ （１．ＳｃｈｏｏｌｏｆＣｏｍｐｕｔｅｒＳｃｉｅｎｃｅａｎｄＴｅｃｈｎｏｌｏｇｙ，ＡｎｈｕｉＵｎｉｖｅｒｓｉｔｙｏｆＴｅｃｈｎｏｌｏｇｙ，Ｍａａｎｓｈａｎ，Ａｎｈｕｉ２４３００２，Ｃｈｉｎａ； ２．ＳｃｈｏｏｌｏｆＭａｔｈｅｍａｔｉｃｓ＆Ｐｈｙｓｉｃｓ，ＡｎｈｕｉＵｎｉｖｅｒｓｉｔｙｏｆＴｅｃｈｎｏｌｏｇｙ，Ｍａａｎｓｈａｎ，Ａｎｈｕｉ２４３００２，Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ： Ｔｏｄｅａｌｗｉｔｈｔｈｅｐｒｅｍａｔｕｒｅｃｏｎｖｅｒｇｅｎｃｅｏｆｔｈｅｂａｒｅ-ｂｏｎｅｐａｒｔｉｃｌｅｓｗａｒｍｏｐｔｉｍｉｚａｔｉｏｎ（ＢＢＰＳＯ）ａｌｇｏ-ｒｉｔｈｍ，ｗｅｍａｋｅｔｈｅａｎａｌｙｓｉｓｏｆｔｈｅｍｏｔｉｏｎｂｅｈａｖｉｏｒｏｆｔｈｅｐａｒｔｉｃｌｅｓａｎｄｐｏｉｎｔｏｕｔｔｈｅｒｅａｓｏｎｓｌｅａｄｉｎｇｔｏｔｈｅｐｒｅｍａｔｕｒｅｃｏｎ-ｖｅｒｇｅｎｃｅ．Ａｃｃｏｒｄｉｎｇｔｏｔｈｅａｎａｌｙｓｉｓｒｅｓｕｌｔｓ，ａｐａｒａｌｌｅｌ-ｃｏｏｐｅｒａｔｉｖｅＢＢＰＳＯ（ＰＣＢＢＰＳＯ）ａｌｇｏｒｉｔｈｍｉｓｐｒｏｐｏｓｅｄｉｎｗｈｉｃｈｔｈｅｐａｒａｌｌｅｌ-ｃｏｏｐｅｒａｔｉｖｅｌｅａｒｎｉｎｇｏｆａｍａｓｔｅｒｓｗａｒｍａｎｄａｓｌａｖｅｓｗａｒｍｂａｌａｎｃｅｓｂｅｔｗｅｅｎｅｘｐｌｏｒａｔｉｏｎａｎｄｅｘｐｌｏｉｔａｔｉｏｎａｂｉｌｉｔｉｅｓ．Ｉｎｏｒｄｅｒｔｏｉｍｐｒｏｖｅｔｈｅｅｘｐｌｏｒａｔｉｏｎａｂｉｌｉｔｙｏｆｔｈｅｍａｓｔｅｒｓｗａｒｍ，ａｄｙｎａｍｉｃｌｅａｒｎｉｎｇｅｘｅｍｐｌａｒｓｔｒａｔｅｇｙｉｓｐｒｅｓｅｎｔｅｄｔｏｐｒｅｓｅｒｖｅｔｈｅｓｗａｒｍｄｉｖｅｒｓｉｔｙ．Ｍｅａｎｗｈｉｌｅ，ａｓｔｏｃｈａｓｔｉｃｏｐｐｏｓｉｔｉｏｎ-ｂａｓｅｄｌｅａｒｎｉｎｇｍｅｃｈａｎｉｓｍｉｓｄｅｖｅｌｏｐｅｄｔｏａｃｈｉｅｖｅｔｈｅａｂｉｌｉｔｉｅｓｏｆｔｈｅｓｌａｖｅｓｗａｒｍｆｒｏｍｔｈｅｇｌｏｂａｌｓｅａｒｃｈｔｏｔｈｅｌｏｃａｌｓｅａｒｃｈ．Ｔｈｅｐｒｏｐｏｓｅｄａｌｇｏｒｉｔｈｍｗａｓｅｖａｌｕａｔｅｄｏｎ１４ｂｅｎｃｈｍａｒｋｆｕｎｃｔｉｏｎｓｗｉｔｈｄｉｆｆｅｒｅｎｔｃｈａｒａｃｔｅｒｉｓｔｉｃｓ．Ｔｈｅｅｘｐｅｒｉｍｅｎｔａｌｒｅｓｕｌｔｓａｎｄｓｔａｔｉｓｔｉｃａｎａｌｙｓｉｓｓｈｏｗｔｈａｔｔｈｅｐｒｏｐｏｓｅｄｍｅｔｈｏｄｓｉｇｎｉｆｉｃａｎｔｌｙｏｕｔ-ｐｅｒｆｏｒｍｓｓｉｘｓｔａｔｅ-ｏｆ-ｔｈｅ-ａｒｔＢＢＰＳＯｖａｒｉａｎｔｓｉｎｔｅｒｍｓｏｆｃｏｎｖｅｒｇｅｎｃｅｓｐｅｅｄａｎｄｓｏｌｕｔｉｏｎａｃｃｕｒａｃｙ． Ｋｅｙｗｏｒｄｓ： ＢＢＰＳＯ；ｃｏｏｐｅｒａｔｉｖｅｌｅａｒｎｉｎｇ；ｏｐｐｏｓｉｔｉｏｎ-ｂａｓｅｄｌｅａｒｎｉｎｇ；ｄｉｖｅｒｓｉｔｙ １ 引言 粒子群优化（ＰａｒｔｉｃｌｅＳｗａｒｍＯｐｔｉｍｉｚａｔｉｏｎ，ＰＳＯ）［１］ 是一种基于群体的随机优化技术，源于对鸟群，鱼群及人类集体行为的研究．由于ＰＳＯ概念简洁、易于实现和优 良的性能使其在诸多领域的优化问题中得到应用． 但是ＰＳＯ的优化性能和收敛行为依赖学习参数的选择， 如惯性权重，加速系数等［２，３］ ．为了提高ＰＳＯ的优化性 能，很多改进策略被提出［４～７］ ．但是在保持算法简洁结构的前提下，同时提高算法的收敛速度和精度仍是ＰＳＯ 一个富有挑战性的问题［８］ ． ２００３年， Ｋｅｎｎｅｄｙ提出了一种无参数的骨干粒子群优化［９］ （ＢＢＰＳＯ），该算法采用基于群体最优和个体历史最优信息的高斯采样在解空间中进行搜索．与传统的ＰＳＯ相比，ＢＢＰＳＯ减少了速度项、加速系数、速度阈值等参数，使得算法结构更为简洁易于操作．目前，ＢＢ-ＰＳＯ在图像的特征选择，经济调度和故障诊断等实际问 题中的应用取得优良的效果［１０，１１］． 由于ＢＢＰＳＯ收敛速度快，当解决复杂多峰问题时， 群体容易迅速聚集，从而陷入早期收敛．为了提高算法 的勘探能力，Ｋｒｏｈｌｉｎｇ等［１２］ 提出了高斯和柯西跳跃策略 的ＢＢＰＳＯ算法．Ｏｒｍａｎ等［１３］ 将差分算法操作引入ＢＢＰ- 主函数源程序（main.m） %------基本粒子群优化算法（Particle Swarm Optimization）-----------%------名称：基本粒子群优化算法（PSO） %------作用：求解优化问题 %------说明：全局性，并行性，高效的群体智能算法 %------初始格式化--------------------------------------------------clear all; clc; format long; %------给定初始化条件---------------------------------------------- c1=1.4962;%学习因子1 c2=1.4962;%学习因子2 w=0.7298;%惯性权重 MaxDT=1000;%最大迭代次数 D=10;%搜索空间维数（未知数个数） N=40;%初始化群体个体数目 eps=10^(-6);%设置精度(在已知最小值时候用) %------初始化种群的个体(可以在这里限定位置和速度的范围)------------for i=1:N for j=1:D x(i,j)=randn;%随机初始化位置 v(i,j)=randn;%随机初始化速度 end end %------先计算各个粒子的适应度，并初始化Pi和Pg----------------------for i=1:N p(i)=fitness(x(i,:),D); y(i,:)=x(i,:); end pg=x(1,:);%Pg为全局最优 for i=2:N if fitness(x(i,:),D) 粒子群算法解决函数优化问题 1、群智能算法研究背景 粒子群优化算法（Particle Swarm Optimization，PSO）是由Kennedy 和Eberhart 在研究鸟类和鱼类的群体行为基础上于1995 年提出的一种群智能算法，其思想来源于人工生命和演化计算理论，模仿鸟群飞行觅食行为，通过鸟集体协作使群体达到优。 PSO算法作为一种新的群智能算法，可用于解决大量非线性、不可微和多峰值的复杂函数优化问题，并已广泛应用于科学和工程领域，如函数优化、神经网络训练、经济调度、模式识别与分类、结构设计、电磁场和任务调度等工程优化问题等。 PSO算法从提出到进一步发展，仅仅经历了十几年的时间，算法的理论基础还很薄弱，自身也存在着收敛速度慢和早熟的缺陷。如何加快粒子群算法的收敛速度和避免出现早熟收敛，一直是大多数研究者关注的重点。因此，对粒子群算法的分析改进不仅具有理论意义，而且具有一定的实际应用价值。 2、国内外研究现状 对PSO算法中惯性权重的改进：Poli等人在速度更新公式中引入惯性权重来更好的控制收敛和探索，形成了当前的标准PSO算法。 研究人员进行了大量的研究工作，先后提出了线性递减权值( LDIW)策略、模糊惯性权值( FIW) 策略和随机惯性权值( RIW) 策略。其中，FIW 策略需要专家知识建立模糊规则，实现难度较大，RIW 策略被用于求解动态系统，LDIW策略相对简单且收敛速度快， 任子晖，王坚于2009 年，又提出了基于聚焦距离变化率的自适应惯性权重PSO算法。 郑春颖和郑全弟等人，提出了基于试探的变步长自适应粒子群算 法。这些改进的PSO算法既保持了搜索速度快的特点, 又提高了全局搜索的能力。 对PSO算法的行为和收敛性的分析：1999 年采用代数方法对几种典型PSO算法的运行轨迹进行了分析，给出了保证收敛的参数选择范围。在收敛性方面Fransvan den Bergh引用Solis和Wets关于随机性算法的收敛准则，证明了标准PSO算法不能收敛于全局优解，甚至于局部优解；证明了保证收敛的PSO算法能够收敛于局部优解，而不能保证收敛于全局优解。 国内的学者：2006 年，刘洪波和王秀坤等人对粒子群优化算法的收敛性进行分析，指出它在满足收敛性的前提下种群多样性趋于减小，粒子将会因速度降低而失去继续搜索可行解的能力，提出混沌粒子群优化算法。 2008 年，黄翀鹏和熊伟丽等人分析惯性权值因子大小对PSO算法收敛性所带来的影响，对粒子群算法进行了改进。2009 年，高浩和冷文浩等人，分析了速度因子对微粒群算法影响，提出了一种基于Gaussian 变异全局收敛的粒子群算法。并证明了它能以概率 1 收敛到全局优解。 2010 年，为提高粒子群算法的收敛性,提出了基于动力系统的稳定性理论，对惯性权重粒子群模型的收敛性进行了分析，提出了使得在算法模型群模型收敛条件下的惯性权重和加速系数的参数约束关系，使算法在收敛性方面具有显著优越性。在PSO算法中嵌入别的算法的思想和技术。 1997年，李兵和蒋慰孙提出混沌优化方法； 1998年，Angeline在PSO算法中引入遗传算法中的选择算子，该算法虽然加快了算法的收敛速度，但同时也使算法陷入局部优的概率大增，特别是在优化Griewank 基准函数的优值时得到的结果不理想； 2004 年，高鹰和谢胜利将混沌寻优思想引入到粒子群优化算法中，首先对当前群体中的优粒子进行混沌寻优, 再用混沌寻优的结果随机替换群体中的一个粒子，这样提出另一种混沌粒子群优化算法。 粒子群算法原理及其在函数优化中的应用 1 粒子群优化（PSO ）算法基本原理 1.1 标准粒子群算法 假设在一个D 维的目标搜索空间中，有m 个代表问题潜在解的粒子组成一个种群12[,,...,]m =x x x x ，第i 个粒子的信息可用D 维向量表示为 12[,,...,]T i i i iD x x x =x ，其速度为12[,,...,]T i i i iD v v v =v 。算法首先初始化m 个随机粒 子，然后通过迭代找到最优解。每一次迭代中，粒子通过跟踪2个极值进行信息交流，一个是第i 个粒子本身找到的最优解，称之为个体极值，即 12[,,...,]T i i i iD p p p =p ；另一个是所有粒子目前找到的最优解，称之为群体极值， 即12[,,...,]T g g g gD p p p =p 。粒子在更新上述2个极值后，根据式(1)和式(2)更新自己的速度和位置。 11122()()t t t t t t i i i i g i w c r c r +=+-+-v v p x p x (1) 11t t t i i i ++=+x x v (2) 式中，t 代表当前迭代次数，12,r r 是在[0,1]之间服从均匀分布的随机数，12 ,c c 称为学习因子，分别调节粒子向个体极值和群体极值方向飞行的步长，w 为惯性权重，一般在0.1~0.9之间取值。在标准的PSO 算法中，惯性权重w 被设为常数，通常取0.5w =。在实际应用中，x 需保证在一定的围，即x 的每一维的变化围均为min max [,]X X ，这在函数优化问题中相当于自变量的定义域。 1.2 算法实现步骤 步骤1：表示出PSO 算法中的适应度函数()fitness x ；（编程时最好以函数的形式保存，便于多次调用。） 步骤2：初始化PSO 算法中各个参数(如粒子个数，惯性权重，学习因子，最大迭代次数等)，在自变量x 定义域随机初始化x ，代入()fitness x 求得适应度值，通过比较确定起始个体极值i p 和全局极值g p 。 步骤3：通过循环迭代更新x 、i p 和g p ： ①确定惯性权重w 的取值（当w 不是常数时）。 ②根据式(1)更新粒子的速度1k i +v ，若速度中的某一维超过了max V ，则取为 max V 。 ③根据式(2)更新自变量x ，若x 的取值超过其定义域，则在其定义域重新初 基本粒子群算法的原理和matlab 程序 作者—— niewei120 （nuaa） 一、粒子群算法的基本原理 粒子群优化算法源自对鸟群捕食行为的研究，最初由Kennedy 和 Eberhart 提出，是一种通 用的启发式搜索技术。一群鸟在区域中随机搜索食物，所有鸟知道自己当前位置离食物多远， 那么搜索的最简单有效的策略就是搜寻目前离食物最近的鸟的周围区域。PSO 算法利用这种模型得到启示并应用于解决优化问题。PSO 算法中，每个优化问题的解都是粒子在搜索 空间中的位置，所有的粒子都有一个被优化的目标函数所决定的适应值，粒子还有一个速度值决定它们飞翔的方向和距离，然后粒子群就追随当前的最优粒子在解空间中搜索。 PSO 算法首先在给定的解空间中随机初始化粒子群，待优化问题的变量数决定了解空间的维数。每个粒子有了初始位置与初始速度。然后通过迭代寻优。在每一次迭代中，每个粒子通过跟踪两个“极值”来更新自己在解空间中的空间位置与飞翔速度。第一个极值就是单个粒子本身在迭代过程中找到的最优解粒子，这个粒子叫做个体极值。另一个极值是种群所有粒子在迭代过程中所找到的最优解粒子，这个粒子是全局极值。上述的方法叫全局粒子群算法。如果不用种群所有粒子而只用其中一部分作为该粒子的邻居粒子，那么在所有邻居粒子中的极值就是局部极值，该方法称为局部PSO 算法。 速度、位置的更新方程表示为： 每个粒子自身搜索到的历史最优值p i，p i=(p i1 ,p i2 ,....,p iQ )， i=1,2,3,....,n 。所有粒子搜索到的最优值p g， p g=(p g1 ,p g2,....,p gQ )，注意这里的p g只有一个。 是保持原来速度的系数，所以叫做惯性权重。 是粒子跟踪自己历史最优值的权重系数，它表示粒子自身的认识，所以叫“认知”。通常设置为 2 。 是粒子跟踪群体最优值的权重系数，它表示粒子对整个群体知识的认识，所以叫做“社会知识”，经常叫做“社会”。通常设置为2。 是[0,1] 区间内均匀分布的随机数。 是对位置更新的时候，在速度前面加的一个系数，这个系数我们叫做约束因子。通常设 置为 1 。 ———————————— 基金项目基金项目：：国家自然科学基金资助项目(51009036, 51109041) 作者简介作者简介：：刘利强(1980－)，男，副教授、博士，主研方向：计算智能，认知科学；汪相国、范志超，硕士研究生 收稿日期收稿日期：：2012-08-10 修回日期修回日期：：2012-10-24 E-mail ：llq9842222@https://www.doczj.com/doc/318109165.html, 基于小生境粒子群优化的船舶多路径规划方法 刘利强刘利强，，汪相国汪相国，，范志超 (哈尔滨工程大学自动化学院，哈尔滨 150001) 摘 要：针对船舶全局路径规划中的多路径规划问题，提出一种基于小生境粒子群优化的多路径规划方法。借鉴遗传算法求解多峰函数的思想，在基本粒子群优化算法的基础上，引入小生境生成、隔离进化和交叉算子等策略，分别采用主群粒子进行区域划分，使用子群粒子完成区域内的局部寻优，从而实现船舶多路径规划。仿真结果表明，该方法能正确、有效地规划出多条最优及次优路径。 关键词关键词：：多路径规划；粒子群优化；小生境；隔离进化；交叉算子；多种群 Multi-path Planning Method for Ships Based on Niche Particle Swarm Optimization LIU Li-qiang, WANG Xiang-guo, FAN Zhi-chao (College of Automation, Harbin Engineering University, Harbin 150001, China) 【Abstract 】For the problem of multi-path planning in global path planning for ships, a multi-path planning method based on niche Particle Swarm Optimization(PSO) is proposed. Based on the idea of Genetic Algorithm(GA) to solve multi-modal function, it takes the formation of niche, isolated evolution and crossover operator into the PSO, uses the main particle swarm to decompose the region, and the sub-particle swarm to optimize the local region respectively to accomplish the multi-path planning for ships. Simulation results show that this method can plan multiple optimal and sub-optimal paths correctly and efficiently. 【Key words 】multi-path planning; Particle Swarm Optimization(PSO); niche; isolated evolution; crossover operator; multi-population DOI: 10.3969/j.issn.1000-3428.2013.09.051 计 算 机 工 程 Computer Engineering 第39卷 第9期 V ol.39 No.9 2013年9月 September 2013 ·人工智能及识别技术人工智能及识别技术·· 文章编号文章编号：：1000—3428(2013)09—0227—06 文献标识码文献标识码：：A 中图分类号中图分类号：：TP391 1 概述 路径规划是实现船舶智能化航行的关键技术之一，其主要任务是在环境已知、部分已知或未知的情况下，按照一定的评价标准，寻找从起点到终点的最优航行路线[1-2]。路径规划分为全局规划和局部规划，其中，全局路径规划是在环境信息完全已知的情况下，在大范围内进行最优航线规划，而局部路径规划需要传感器实时地获取环境信息，在小范围内进行避碰航线规划[2-3]。本文进行船舶全局路径规划研究。目前，大部分的船舶全局路径规划方法，对路径优劣的评价完全依据给定的适应值函数，生成一条具有最优适应度的路径。由于路径规划问题本身、船舶运动以及外部环境的复杂性，很难用一个统一的适应值函数将所有的因素都考虑进去[4]。 针对上述的问题，一种有效的途径是预先规划出多条最优及次优路径，在任务执行时，决策者根据不同的需求临时选择合适的航线[5]。近年来，一些学者开展了多路径规划研究，文献[6]子群内的交叉、变异等操作会破坏已创建 的子群，导致算法多路径规划效率降低；文献[4]在粒子群多样化阶段完成子群的创建，因此，子群的数量依赖于粒子群的多样化程度。鉴于此，本文对子群间采用隔离进化的策略，子群内用粒子群优化(Particle Swarm Optimization, PSO)算法进行区域内局部寻优，没有交叉、变异等操作；对主群用认知的PSO 进行更新，引入交叉算子，增强主群粒子对新区域的探索能力，并进行仿真实验。 2 问题描述与建模 船舶航行在海洋等环境中，存在着静态环境约束和动态环境约束，静态约束包括岛礁、海底地形等，动态约束包括船舶、气候变化等。本文采用在直角坐标系下进行二维空间建模，对于船舶，路径规划就是寻找其在环境中航行时所经过的点的集合。路径编码原理如图1所示。 在图1全局坐标系-O XY 中，黑色不规则的多边形表示障碍物，S 为船舶航行的起点，G 为终点，船舶的路径规划即寻找一个点的集合： 12{,,,,,}n P S P P P G =? (1) 粒子群优化算法(1)—粒子群优化算法简介 PSO算法就是模拟一群鸟寻找食物的过程，每个鸟就是PSO中的粒子，也就是我们需要求解问题的可能解，这些鸟在寻找食物的过程中，不停改变自己在空中飞行的位置与速度。大家也可以观察一下，鸟群在寻找食物的过程中，开始鸟群比较分散，逐渐这些鸟就会聚成一群，这个群忽高忽低、忽左忽右，直到最后找到食物。这个过程我们转化为一个数学问题。寻找函数y=1-cos(3*x)*exp(-x)的在[0,4]最大值。该函数的图形如下： 当x=0.9350-0.9450，达到最大值y=1.3706。为了得到该函数的最大值，我们在[0, 4]之间随机的洒一些点，为了演示，我们放置两个点，并且计算这两个点的函数值，同时给这两个点设置在[0, 4]之间的一个速度。下面这些点就会按照一定的公式更改自己的位置，到达新位置后，再计算这两个点的值，然后再按照一定的公式更新自己的位置。直到最后在y=1.3706这个点停止自己的更新。这个过程与粒子群算法作为对照如下： 这两个点就是粒子群算法中的粒子。 该函数的最大值就是鸟群中的食物。 计算两个点函数值就是粒子群算法中的适应值，计算用的函数就是粒子群算法中的适应度函数。 更新自己位置的公式就是粒子群算法中的位置速度更新公式。 下面演示一下这个算法运行一次的大概过程： 第一次初始化 第一次更新位置 第二次更新位置 第21次更新 最后的结果（30次迭代） 最后所有的点都集中在最大值的地方。 粒子群优化算法(2)—标准粒子群优化算法 在上一节的叙述中，唯一没有给大家介绍的就是函数的这些随机的点（粒子）是如何运动的，只是说按照一定的公式更新。这个公式就是粒子群算法中的位置速度更新公式。下面就介绍这个公式是什么。在上一节中我们求取函数y=1-cos(3*x)*exp(-x)的在[0, 4]最大值。并在[0,4]之间放置了两个随机的点，这些点的坐标假设为x1=1.5，x2=2.5；这里的点是一个标量，但是我们经常遇到的问题可能是更一般的情况—x 为一个矢量的情况，比如二维z=2*x1+3*x22的情况。这个时候我们的每个粒子均为二维，记粒子P1＝(x11,x12),P2=(x21,x22),P3=(x31,x32)，......Pn=(xn1,xn2)。这里n 为粒子群群体的规模，也就是这个群中粒子的个数，每个粒子的维数为2。更一般的是粒子的维数为q ，这样在这个种群中有n 个粒子，每个粒子为q 维。 由n 个粒子组成的群体对Q 维（就是每个粒子的维数）空间进行搜索。每个粒子表示为：x i ＝（x i1,x i2,x i3,...,x iQ ），每个粒子对应的速度可以表示为v i =(v i1,v i2,v i3,....,v iQ )，每个粒子在搜索时要考虑两个因素： 1. 自己搜索到的历史最优值 p i ，p i =(p i1,p i2,....,p iQ )，i=1,2,3,....,n ； 2. 全部粒子搜索到的最优值p g ，p g =(p g1,p g2,....,p gQ )，注意这里的p g 只有一个。 下面给出粒子群算法的位置速度更新公式： 112()()()()k k k k i i i i v v c rand pbest x c rand gbest x ω+=+??-+??-, 11k k k i i i x x av ++=+. 这里有几个重要的参数需要大家记忆，因为在以后的讲解中将会经常用到，它们是： ω是保持原来速度的系数，所以叫做惯性权重。1c 是粒子跟踪自己历史最优值的权重系数，它表示粒子自身的认识，所以叫“认知”。通常设置为2。2c 是粒子跟踪群体最优值的权重系数，它表示粒子对整个群体知识的认识，所以叫做“社会知识”，经常叫做“社会”。通常设置为2。()rand 是[0,1]区间内均匀分布的随机数。a 是对位置更新的时候，在速度前面加的一个系数，这个系数我们叫做约束因子。通常设置为1。这样一个标准的粒子群算法就介绍结束了。下图是对整个基本的粒子群的过程给一个简单的图形表示。 判断终止条件可是设置适应值到达一定的数值或者循环一定的次数。 注意：这里的粒子是同时跟踪自己的历史最优值与全局（群体）最优值来改变自己的位置预速度的，所以又叫做全局版本的标准粒子群优化算法。 一、粒子群算法概述 粒子群优化算法(PSO)是一种进化计算技术(evolutionary computation)，1995 年由Eberhart 博士和kennedy博士提出，源于对鸟群捕食的行为研究。该算法最初是受到飞鸟集群活动的规律性启发，进而利用群体智能建立的一个简化模型。粒子群算法在对动物集群活动行为观察基础上，利用群体中的个体对信息的共享使整个群体的运动在问题求解空间中产生从无序到有序的演化过程，从而获得最优解。 PSO中，每个优化问题的解都是搜索空间中的一只鸟。我们称之为“粒子”。所有的粒子都有一个由被优化的函数决定的适应值(fitness value)，每个粒子还有一个速度决定他们飞翔的方向和距离。然后粒子们就追随当前的最优粒子在解空间中搜索。 PSO 初始化为一群随机粒子(随机解)。然后通过迭代找到最优解。在每一次迭代中，粒子通过跟踪两个”极值”来更新自己。第一个就是粒子本身所找到的最优解，这个解叫做个体极值pBest。另一个极值是整个种群目前找到的最优解，这个极值是全局极值gBest。另外也可以不用整个种群而只是用其中一部分作为粒子的邻居，那么在所有邻居中的极值就是局部极值。 二、算法原理 粒子群算法采用常数学习因子，及惯性权重，粒子根据如下的公式更新自己的速度和位置。 V ki=ωk V i?1i+c1r1(Q bi?Q k?1i)+c2r2(Q bg?Q k?1i)Q ki=Q k?1i+V ki 三、算法步骤 1、随机初始化种群中各微粒的位置和速度； 2、评价个粒子的适应度，将各粒子的位置和适应度储存在各微粒的pbest（Q bi）中，将所有pbest中适应度最优的个体的位置和适应度存储在gbest（Q bg）中。 3、更新粒子的速度和位移。 V ki=ωk V i?1i+c1r1(Q bi?Q k?1i)+c2r2(Q bg?Q k?1i)Q ki=Q k?1i+V ki 4、对每个微粒，与其前一个最优位置比较，如果较好，则将其作为当前的最优位置。 5、比较当前所有的pbest和上一迭代周期的gbest，更新gbest。 6、若满足停止条件（达到要求精度或迭代次数），搜索停止，输出结果，否则，返回2。 附录 程序1 当22111==c c ，5.12212==c c ，2.1=w 。 a)%主函数源程序（main.m ） %------基本粒子群算法 （particle swarm optimization ） %------名称： 基本粒子群算法 %------初始格式化 clear all ; %清除所有变量 clc; %清屏 format long ; %将数据显示为长整形科学计数 %------给定初始条条件------------------ N=40; %3初始化群体个数 D=10; %初始化群体维数 T=100; %初始化群体最迭代次数 c11=2; %学习因子1 c21=2; %学习因子2 c12=1.5; c22=1.5; w=1.2; %惯性权重 eps=10^(-6); %设置精度（在已知最小值的时候用） %------初始化种群个体（限定位置和速度）------------ x=zeros(N,D); v=zeros(N,D); for i=1:N for j=1:D x(i,j)=randn; %随机初始化位置 v(i,j)=randn; %随机初始化速度 end end %------显示群位置---------------------- figure(1) for j=1:D if(rem(D,2)>0) subplot((D+1)/2,2,j) else subplot(D/2,2,j) end plot(x(:,j),'b*');grid on xlabel('粒子') ylabel('初始位置') tInfo=strcat('第',char(j+48),'维'); if(j>9) tInfo=strcat('第',char(floor(j/10)+48),char(rem(j,10)+48),'维'); end title(tInfo) end %------显示种群速度 figure(2) for j=1:D if(rem(D,2)>0) subplot((D+1)/2,2,j) else subplot(D/2,2,j) end plot(x(:,j),'b*');grid on xlabel('粒子') ylabel('初始速度') tInfo=strcat('第,char(j+48),'维'); if(j>9) tInfo=strcat('第',char(floor(j/10)+48), char(rem(j,10)+48),'维); end title(tInfo) end figure(3) 基于收缩因子的改进粒子群算法 陈国鸿 （河池学院计算机与信息科学系广西河池 546300） 摘要：针对基本粒子群优化算法(ParticleSwarmOptimization，简称PSO )存在的早熟收敛问题，提出了一种既保持粒子活性又保证粒子快速收敛于全局极值点的改进粒子群优化（XARPSO）算法。在算法运行过程中，如果种群多样性逐步减小，直至超出下限时，种群不再向整体最优位置靠近，而是纷纷远离该最优位置，从而执行了“扩散”操作，而当种群多样性逐步增大，直至超出上限时，种群又开始向整体最优位置靠拢，即执行了“吸引”操作，从而保持了粒子的多样性。同时，该方法引入收缩因子的概念，即通过正确选择惯性权重系数与加速常数即学习因子这些控制参数的值的方法，确保算法收敛。通过Goldstern-Price 函数的最小化测试结果表明，该算法不仅具有较快的收敛速度，而且能够更有效地进行全局搜索。 关键词：粒子算法；收缩因子；吸引；扩散；多峰值函数 引言 粒子群算法最早是在1995年由美国社会心理学家James Kennedy和电气工程师Russell Eberhart共同提出的，简称PSO算法。其基本思想是受他们早期对许多鸟类的群体行为进行建模与仿真研究结果的启发。粒子群算法与其他进化类算法一样，也是一类基于群智能的随机优化算法。但与其它进化计算方法相比， PSO算法具有收敛速度快、设置参数少、程序实现异常简洁、具有深刻的智能背景等特点，既适合科学研究，又特别适合工程应用。因此PSO算法一经提出就引起了国际上相关领域众多学者的关注和研究。目前PSO 算法已广泛应用于函数寻优、神经网络训练、模式分类、模糊系统控制以及其它的应用领域。但是，由于PSO算法在优化过程中所有粒子都向最优解方向飞去，所以粒子趋向同一化，群体的多样性逐渐丧失，即存在早收敛问题，因而也就难以获得较好的优化结果。 为了克服这一缺点，近年来出现了不少改进的PSO算法。如：Shi Y.(1998)提出的带惯性权重的PSO算法、Angeline P.（1999）提出 一种改进的粒子群优化算法 武燕Wu Yan；张冰Zhang Bing （江苏科技大学电子信息学院，镇江212003） （School of Electronics and Information，Jiangsu University of Science and Technology，Zhenjiang 212003，China） 摘要：介绍基本粒子群优化算法的原理、特点，并在此基础上提出了一种改进的粒子群算法。通过在粒子初始化时引入相对基的原理使粒子获得更好的初始解，以及在迭代过程中引入变异模型，部分粒子生成相对应的扩张及收缩粒子，比较其适应度，保留最佳粒子进行后期迭代，使算法易跳出局部最优。通过经典函数的测试结果表明，新算法的全局搜索能力有了显著提高，并且能够有效避免早熟问题。 Abstract: This paper introduces the principles and characteristics of Particle Swarm Optimization algorithm，and puts forward an improved particle swarm optimization algorithm. It adopted Opposition-Based Learning in initialization to get a better solution and adopted variation model which make some particles generate two corresponding shrink and expand particles and keep the best fitness particle iterate in later iteration to avoid getting into local minumum. The experimental results of classical function show this algorithm improves the global convergence ability and efficiently prevents the algorithm from the local optimization and early maturation. 关键词：粒子群优化算法；相对基；变异模型 Key words: Particle Swarm Optimization（PSO）；Opposition-Based Learning；variation model 中图分类号：TP301.6 文献标识码： A 文章编号：1006-4311（2011）07-0161-02 0 引言 粒子群优化算法（Particle Swarm Optimization，PSO）是一种新型的仿生算法，由Kennedy和Eberhart于1995年提出[1，2]。该算法是基于群体智能（Swarm I ntelligence，(完整word版)基本粒子群算法的原理和matlab程序
并行协作骨干粒子群优化算法
基本粒子群算法的matlab源程序
粒子群算法解决函数优化问题
粒子群算法原理及在函数优化中的应用(附程序)
(完整word版)基本粒子群算法的原理和matlab程序.doc
基于小生境粒子群优化的船舶多路径规划方法
粒子群优化算法介绍及matlab程序
标准粒子群算法(PSO)及其Matlab程序和常见改进算法
粒子群优化算法及其参数设置
基于收缩因子的改进粒子群算法
一种改进的粒子群优化算法-《价值工程》武燕 张冰
相关主题
文本预览