粒子群算法的研究

1、目录 TOC o 1-5 h z HYPERLINK l bookmark0 o Current Document 目录 I HYPERLINK l bookmark2 o Current Document 摘要 II前言 III2引言 1 HYPERLINK l bookmark4 o Current Document 背景研究和课题意义 1 HYPERLINK l bookmark7 o Current Document 应用领域 13基本粒子群算法 2粒子群思想的起源 2 HYPERLINK l bookmark12 o Current Document 算法原理 3 HYPERLINK

2、 l bookmark14 o Current Document 带权重的粒子群算法 34粒子群算法的改进策略 4粒子群初始化 4 HYPERLINK l bookmark19 o Current Document 领域拓扑 4 HYPERLINK l bookmark21 o Current Document 混合策略 45测试结果 5参数设置 5 HYPERLINK l bookmark26 o Current Document 实验结果 5 HYPERLINK l bookmark28 o Current Document 6总结 7 HYPERLINK l bookmark30 o C

3、urrent Document 致谢 8 HYPERLINK l bookmark32 o Current Document 附录代码 9摘要粒子群优化是一种新兴的基于群体智能的启发式全局搜索算法，粒子群 优化算法通过粒子间的竞争和协作以实现在复杂搜索空间中寻找全局最优 点。它具有易理解、易实现、全局搜索能力强等特点，倍受科学与工程领域 广泛关注，已经成为发展最快的智能优化算法之一。论文介绍了粒子群优化 算法的基本原理，分析了其特点。论文中围绕粒子群优化算法的原理、特点、 参数设置与应用等方面进行全面综述，重点利用单因子方差分析方法，分析 了粒群优化算法中的惯性权值，加速因子的设置对算法基本性

4、能的影响，给 出算法中的经验参数设置。最后对其未来的研究提出了 一些建议及研究方向 的展望。关键词：粒子群优化算法；参数；方差分析；最优解II刖百群体智能算法(SwarmIntelligenceAlgoHthm,SIA)的研究开始于20世纪 90年代，其基本思想是模拟自然界生物的群体行为来构造随机优化算法1,2,3,通常单个自然界的生物并不是智能的，但是整个生物群体却表现出处理复杂问题的能力，群体智能算法就是模仿这些生物的团体行为并把它应用在人工智能问 题中，其中粒子群优化算法(ParticleSwarmOptimization,PSO) 就是群体智能算法的一种，它是由美国社会心理学家 Jam

5、esKennedy和电气工程师RussellEberhart在1995年提出的，具基本思想是对鸟群、鱼群的觅食过程中的迁徙和聚集的行 为模拟，并利用了生物学家 FrankHeppner的生物群体模型4,5,6。PSO算法是一类基于群体智能的随机优化技术，相对遗传算法而言，二者都是基于群体的迭代搜索，但是PSO算法没有交叉、变异算子，粒子群优化算法是 通过个体之间的协作来搜寻最优解，它利用了生物群体中信息共享的思想，其概念简单、易于实现，同时又有深刻的智能背景，既适合科学研究，又特别适合工程应用。因此，PSO一提出，就引起了众多学者的关注，并在短短几年的时间里出现了大量的研究成果III2引言背景

6、研究和课题意义现在已经有很多源于生物现象的计算技巧。例如，人工神经网络是简化的大脑模型。遗传算法是模拟基因进化过程的。现在我们讨论另一种生物系统-社会系统。也可称做“群智能”(swarm intelligence)。这些模拟系统利用局部信息从而可能产生不可预测的群体行为。粒子群优化算法(PSO)也是起源对简单社会系统的模拟。最初设想是模拟鸟群觅食的过程。但后来发现PSO是一种很好的优化工具。优化是科学研究、工程技术和经济管理等领域的重要研究课题。粒子群优化算法1(简称PSO)是由Kennedy和Eberhart通过对鸟群、鱼群和人类社会某 些行为的观察研究，于1995年提出的一种新颖的进化算法

7、。鉴于 PSO的发展历史尚短，它在理论基础与应用推广上都还存在一些缺陷，有待解决。本文通过对PSO算法的步骤的归纳、特点的分析，利用统计中的方差分析，通过抽样实验方法，论证了该算法中关键参数因子：惯性权值、加速因子对算法整体性能的影响效果，并提出了参数设置的指导原则，给出了关键参数设置，为PSO算法的推广与改进提供了思路。应用领域近年来，PSO快速发展，在众多领域得到了广泛应用。本文将应用研究分 典型理论问题研究和实际工业应用两大类。典型理论问题包括：组合优化、约 束优化、多目标优化、动态系统优化等。实际工业应用有：电力系统、滤波器设计、自动控制、数据聚类、模式识 别与图像处理、化工、机械、通

8、信、机器人、经济、生物信息、医学、任务分 配、TSP等等。3基本粒子群算法粒子群思想的起源粒子群优化(Particle Swarm Optimization, PSO痹法1是 Kennedy 和 Eberhart 受人工生命研究结果的启发、通过模拟鸟群觅食过程中的迁徙和群聚行为而提出的 一种基于群体智能的全局随机搜索算法，1995年IEEE国际神经网络学术会议发表 了题为一Particle Swarm Optimization II的论文，标志着 PSO算法诞生(注：国内也 有很多学者译为一微粒群优化II )。它与其他进化算法一样，也是基于一种群II和一 进化口的概念，通过个体间的协作与竞争，

9、实现复杂空间最优解的搜索；同时，PSO 又不像其他进化算法那样对个体进行交叉、变异、选择等进化算子操作，而是将群 体(swarm)中的个体看作是在D维搜索空间中没有质量和体积的粒子(particle),每 个粒子以一定的速度在解空间运动，并向自身历史最佳位置pbest和邻域历史最佳位置pbest聚集，实现对候选解的进化。PSO算法具有很好的生物社会背景2而易 理解、参数少而易实现，对非线性、多峰问题均具有较强的全局搜索能力，在科学 研究与工程实践中得到了广泛关注。自然界中各种生物体均具有一定的群体行为，而人工生命的主要研究领域之一 是探索自然界生物的群体行为，从而在计算机上构建其群体模型。自然

10、界中的鸟群 和鱼群的群体行为一直是科学家的研究兴趣，生物学家 Craig Reynolds在1987年 提出了一个非常有影响的鸟群聚集模型7,在他的仿真中，每一个个体遵循：(1)避免与邻域个体相冲撞；(2)匹配邻域个体的速度；(3)飞向鸟群中心，且整个群体飞向目标。算法原理粒子群优化算法的实现步骤如下：假设在一个D维的搜索空间中，有 m个粒子组成一个群落，其中第i个粒子表示为一个D维的向量 Xi =(Xii,Xi2,., XiD)o即第I个粒子在 D维搜索空间的位置是 X。换言之， 每个粒子的位置就是一个潜在的解。将X代入一个目标函数就可以计算出其适应值，根据适应值的大小衡量解的优劣。第 i个

11、粒子的“飞翔”速度也是一个 D维向量记为V =(Vii,Vi2,., ViD)。记第i个粒子迄今为止搜索到的最优位 置为P =( Pii, Pi 2,. PiD),整个粒子群迄今为止搜索到的最优位置为 Pg (Pg1，Pg2,., PgD) 带权重的粒子群算法探索是偏离原来的寻优轨迹去寻找一个更好的解，探索能力是一个算法的 全局搜索能力。开发是利用一个好的解，继续原来的寻优轨迹去搜索更好的解，它是算法的局部搜索能力。如何确定局部搜索能力和全局搜索能力的比例，对 一个问题的求解过程很重要。1998年，Yuhui Shi9提出了带有惯性权重的改进粒子群算法。具进化过程为：Vi(k 1) = (wv

12、i(k),储口-Xi(k)/ tc2r4Pg - Xi(k)八 tXi(k 1)= Xi(k) Vi(k 1) - t其中，w为惯性权重，其值可取为常数，也可以自适应调整，例如随迭代 次数的增加而线性地减少，C1和C2为调节Pi和Pg相对重要性的参数；1和2是介于0和1之间的随机数；是时间问隔，通常取为单位时间；通常附加 限制，其中是常数，可根据具体问题设定。4粒子群算法的改进策略粒子群初始化研究表明，粒子群初始化对算法性能产生一定影响。为了初始种群尽可能 均匀覆盖整个搜索空间，提高全局搜索能力，Richard和Ventura提出了基于centroidal voronoi tessellati

13、ons (CVTs)的种群初始化方法；薛明志等人采用正交设计方法对种群进行初始化；Campana等人将标准 PSO迭代公式改写成线性动态系统，并基于此研究粒子群的初始位置，使它们具有正交的运动轨迹；认 为均匀分布随机数进行初始化实现容易但尤其对高维空间效果差，并另外比较 了 3种初始化分布方法。领域拓扑空间邻域直接在搜索空间按粒子间的距离(如欧式距离)进行划分，如 Suganthan23引入一个时变的欧式空间邻域算子：在搜索初始阶段，将邻域定 义为每个粒子自身；随着迭代次数的增加，将邻域范围逐渐扩展到整个种群。性能空间指根据性能指标(如适应度、目标函数值)划分的邻域。环形拓扑 (ring or

14、 circle topology)、 轮形拓扑 (wheel topology)或星形拓扑 (star topology)、塔形拓扑 (pyramid topology)、冯一诺以曼拓扑 (Von Neumann topology)以及随机拓扑(random topology)等。针对不同的优化问题，这些拓扑 的性能表现各异；但总的来说，随机拓扑往往对大多数问题能表现出较好的性 能，初始阶段粒子采用环形拓扑(ring-type topology),随着迭代次数的增加，逐渐增加粒子间连接，最后形成星形拓扑(star-type topology)。混合策略混合策 略混合pso就是将 其它进化算法或

15、传统 优化算法或其它技术 应用到PSO中，用于提高粒子多样性、增强粒子的全局探索能力，或者提高局部开发能力、增强收敛速度与精度。这种结合的途径通常有两种：一是利用其它优化技术自适应调整收缩因子 /惯性权值、加速常数等；二是将 PSO与其它进化算法操作算子或其它技术结合。5测试结果5.1参数设置PSO的参数主要包括最大速度、两个加速常数和惯性常数或收缩因等。a）最大速度的选择：如式（2.1）所示的粒子速度是一个随机变量，由粒子位置更新公式（2.2）产生的运动轨迹是不可控的，使得粒子在问题空间循环跳动3,6 o Vmax增大，有利于全局探索 （global exploration） ； Vmax减

16、小，则有利于局 部开发。但是 Vmax过高，粒子运动轨迹可能失去规律性，甚至越过最优解所 在区域，导致算法难以收敛而陷入停滞状态；相反 maxv太小，粒子运动步长 太短，算法可能陷入局部极值。Vmax的选择通常凭经验给定，并一般设定为问题空间的1020%。b）加速常数的选择：式 （1）中的加速常数 c1和c2分别用于控制粒子指向 自身或邻域最佳位置的运动。通常去c1=c2=2 。5.2实验结果x2 %cos(2?i)cos(222)-0. 2函数 f(x) - -20e2- e 2202.71289当 Ci =C2 = 1.49445, Vmin = -1,Vmax = 1,种群规模 20,迭

17、代次数 200 时, 运行结果如下图:由于每次产生随机数不可能相同，所有绘制曲线不一致。但大体趋势是相似的：随着迭代次数增加，适应度逐渐减低，最终弄那个趋近于06总结大四第一学期，我学习了技能计算，初步了解了如何利用MATLAB语言编写面向过程的程序。在这门课程的学习过程中，我常常对傅里叶变换的 性质及其应用感到难以适应，感觉自己对这方面太没有天赋了，久而久之，便 失去了学习的乐趣。好在老师在这一年里一直在鼓励着我们。她告诉我们，这东西其实不难， 最主要的就是那个快速傅里叶变换，只要把这个搞懂行了。老师的这些话，我 感到有一定的道理，心里却仍存疑虑，将信将疑。但也不好拂却了老师的好意 与付出，

18、于是，我只好硬着头皮坚持着，坚持了几个月。这次课程设计，是我与同学一起第一次合作完成较大的程序编写，开始时,我们心里根本没底，想都不敢想自已能写出一点东西来，并真正地解决这一实 际问题。但随着工作的逐渐深入，对问题的理解越来越透彻，想写的东西越来 越多，信心越来越足，程序越编越大，能够解决的问题也就越多，自己心中的 疑问就越来越少。总体来说这篇课程设计还是比较满意的，但还是有不足的地 方。不过，我很庆幸能够又一次理论与实践结合的机会，让我能够深入探索傅 里叶变换。在以后的学习生活中我会不断完善自己，用更过的知识来丰富和充 实自己，为以后的人生道路打下坚实的基础。致谢一份课程设计的总结，一份对老

19、师的感谢。虽然我们课程设计程序代码在这学期开始的时候已经有了，但是在明天即 将给老师的时刻，程序代码也发生了许多变化，功能也逐渐提高；一些变化， 一些收获。老师说过：“道虽远，不行不至；事虽难，不为不成。”这专业真的很累, 老师们累，学生们也累，谢谢老师们和我们一起坚持着。明天结果如何是无法 知道的，而今天我们都努力过。附录代码function varargout = PSO(varargin)mfilename, .gui_Singleton = 1;gui_State = struct(gui_Name,gui_Singleton, gui_Singleton, .gui_OpeningF

20、cn, PSO_OpeningFcn, . function pushbutton1_Callback(hObject, eventdata, handles) cl = str2num(get(handles.c1,String);gui_OutputFcn,PSO_OutputFcn, .gui_LayoutFcn,gui_Callback,);if nargin & ischar(varargin1)gui_State.gui_Callback = str2func(varargin1);endif nargoutvarargout1:nargout = gui_mainfcn(gui_

21、State, varargin:); elsegui_mainfcn(gui_State, varargin:);endfunction PSO_OpeningFcn(hObject, eventdata, handles, varargin) handles.output = hObject;guidata(hObject, handles);function varargout = PSO_OutputFcn(hObject, eventdata, handles) varargout1 = handles.output;c2 = str2num(get(handles.c2,String

22、);maxgen=str2num(get(handles.edit2,String);sizepop=str2num(get(handles.edit3,String);Vmin=str2num(get(handles.Vmin,String);Vmax=str2num(get(handles.Vmax,String);popmin = str2num(get(handles.Popmin,String);popmax = str2num(get(handles.Popmax,String);%产生初始粒子和速度for i=1:sizepop%随机产生一个种群pop(i,:)=5*rands(

23、1,2);%初始种群V(i,:)=rands(1,2);% 初始化速度%计算适应度fitness(i)=fun(pop(i,:);%染色体的适应度end%找最好的染色体bestfitness bestindex=min(fitness);zbest=pop(bestindex,:);% 全局最佳gbest=pop;%个体最佳fitnessgbest=fitness;%个体最佳适应度值fitnesszbest=bestfitness;% 全局最佳适应度值%迭代寻优for i=1:maxgen10for j=1:sizepop%速度更新V(j,:) = V(j,:) + c1*rand*(gbest(j,:) - pop(j,:) + c2*rand*(zbest - pop(j,：)；V(j,find(V(j,:)Vmax)=Vmax;V(j,find(V(j,:)popmax)=popmax;pop(j,find(pop(j,:)0.8k