粒子群算法在函数优化问题中的应用【毕业论文绝对精品】.doc

1、目录第1章概述11.1课题研究的目的及意义11.2国内外对粒子群算法（PSO）研究现状与发展趋势11.3本课题所要研究的主要内容51.4本文的研究方案51.5本章小结6第2章粒子群优化算法72.1引言72.2粒子群优化算法的统一框架72.3粒子群优化算法的设计步骤82.4粒子群优化算法描述92.5粒子群算法的改进122.6本章小结16第3章粒子群算法在函数优化问题中的应用173.1前言173.2常用测试函数173.3常用测试函数的介绍173.4基本粒子群算法在函数优化问题中的实验结果与分析183.5参数改进的粒子群算法在函数优化问题中的实验结果与分析203.6本章小结24结 论25参考文献26

2、致 谢29附 录130附 录232附 录333第1章概述1.1课题研究的目的及意义近年来，受自然隐喻的启发，人们提出了各种各样的计算智能方法，如人工神经网络、遗传算法( Genetic Algorithm，GA )、蚁群优化算法( Ant Colony Optimization ，ACO)、粒子群优化算法( Particle Swarm Optimization ，PSO)和人工免疫系统等等，它们被广泛应用于各种NP - 困难的优化问题的求解，虽然不能保证获取最优解，但在问题规模较大时也能在可行时间内找到问题的满意解。粒子群优化(Particle Swarm Optimization，PSO)

3、算法是一种新兴的优化技术，其思想来源于人工生命和进化计算理论。PSO算法通过粒子追随自己找到的最好解和整个群体的最好解完成优化。为了避免PSO算法在求解最优化问题时陷入在局部最优及提高PSO算法的收敛速度，提出了对PSO算法进行改进。对无约束和有约束最优化问题分别设计了基于PSO算法的不同的求解方法和测试函数，并对PSO算法求解多目标优化问题进行了研究。仿真实验表明了改进的PSO算法求解最优化问题时的有效性。以函数的优化问题为例，提出了一种改进的粒子群优化算法，根据优化问题及连续量的特点，对粒子的位置速度等量及其运算规则进行了研究，为抑制早熟停滞现象,算法中使用高效的学习算子来提高算法的局部求

4、精能力，使算法在空间探索和局部求精间取得了很好的平衡，与领域中的基本算法进行仿真比较，改进粒子群优化算法要求具有很好的性能，可以达到较优化的结果。1.2国内外对粒子群算法（PSO）研究现状与发展趋势粒子群优化（Particle Swarm Optimization，PSO）算法最初是由Kennedy和Eberhart1,2于1995年受人工生命研究结果启发，在模拟鸟群觅食过程中的迁徙和群集行为时提出的一种基于群体智能的进化计算技术。鸟群中的每只鸟在初始状态下是处于随机位置向各个随机方向飞行的，但是随着时间的推移，这些初始处于随机状态的鸟通过自组织(self-organization)逐步聚集成

5、一个个小的群落，并且以相同速度朝着相同方向飞行，然后几个小的群落又聚集成大的群落，大的群落可能又分散为一个个小的群落。这些行为和现实中的鸟类飞行的特性是一致的。可以看出鸟群的同步飞行这个整体的行为只是建立在每只鸟对周围的局部感知上面，而且并不存在一个集中的控制者。也就是说整个群体组织起来但却没有一个组织者，群体之间相互协调却没有一个协调者(organized without an organizer，coordinated without a coordinator)。Kennedy和Eberhart从诸如鸟类这样的群居性动物的觅食行为中得到启示，发现鸟类在觅食等搜寻活动中，通过群体成员之间分

6、享关于食物位置的信息，可以大大的加快找到食物的速度，也即是通过合作可以加快发现目标的速度，通常群体搜寻所获得利益要大于群体成员之间争夺资源而产生的损失。这些简单的经验事实如果加以提炼，可以用如下规则来说明：当整个群体在搜寻某个目标时，对于其中的某个个体，它往往是参照群体中目前处于最优位置的个体和自身曾经达到的最优位置来调整下一步的搜寻。Kennedy和Eberhart把这个模拟群体相互作用的模型经过修改并设计成了一种解决优化问题的通用方法，称之为粒子群优化算法。PSO算法的基本原理源于对鸟群捕食行为的仿真。与ACO算法类似，PSO算法是一种基于群智能方法的优化技术，同时还与GA类似，是一种基于

7、进化的优化工具。在PSO算法中，系统初始化为一群随机粒子(代表问题的一组随机解)，通过迭代来搜寻最优值，但是并没有GA所使用的交叉以及变异算子，而是通过粒子在解空间中追随最优的粒子进行搜索。与GA比较，PSO算法的优势在于简单、易于实现同时又有深刻的智能背景，既适合科学研究，又特别适合工程应用。因此，PSO算法一提出，立刻引起了演化计算等领域的学者们的广泛关注，并在短短的几年时间里出现大量的研究成果，形成了一个研究热点。1.2.1粒子群算法的应用现状实际应用方面，粒子群优化算法已经在优化问题求解、电力系统、计算机、控制等诸多领域得到了成功应用，下面是一些具体应用。（1）经典优化问题求解组合优化

8、。旅行商问题(TSP)是一类经典的组合优化问题，继蚁群算法之后，粒子群算法通过一定的改进或变形也已经成功用于TSP问题的求解3。约束优化。目前，粒子群优化算法已被有效应用于约束优化问题求解。例如，可对约束优化问题引入半可行域的概念，提出竞争选择的新规则，并改进基于竞争选择和惩罚函数的进化算法适应度函数，可求解约束优化问题。多目标优化。粒子群优化算法在多目标优化问题求解中有成功的应用。通过对粒子群算法全局极值和个体极值选取方式的改进，可实现了对多目标优化问题非劣最优解集的搜索。（2）电力系统的应用4-8粒子群优化算法在电力系统优化中有着广泛的应用，例如在配电网扩展规划、检修计划、机组组合、负荷经

9、济分配、最优潮流计算与无功优化控制、谐波分析与电容器配置、配电网状态估计、参数辨识、优化设计等方面。此外，在电力系统机组组合优化问题求解、多机器功率系统稳定器的最优设计等方面，粒子群算法具有突出的求解性能。日本的Fuji电力公司的研究人员将电力企业著名的RPVC(Reactive Power and Voltage Control)问题简化为函数的最小值问题，并使用改进的PSO算法进行优化求解。与传统方法如专家系统、敏感性分析相比，实验产生的结果证明了PSO算法在解决该问题的优势。（3）控制领域中的应用模糊控制系统。利用PSO算法优化模糊控制系统，设计模糊控制器。目前从模糊神经网络系统自动提取

10、模糊规则的研究在一些典型的问题上已经取得进展，这对于自动生成模糊系统控制规则的模糊控制器在应用领域的推广有很大的启示。冶金自动化。例如，在对粗轧宽展控制模型进行优化方面，采用粒子群算法对粗轧宽展控制模型进行优化9。另外，粒子群算法还被用于计算机数字控制的研磨。（4）其他实际应用除了上述应用领域外，粒子群优化算法在化工领域，生物医学以及电磁学等领域都有一定的应用10-12。粒子群算法已被美国一家公司用于将各种生物化学成分进行优化组合，进而人工合成微生物。与传统的工业优化方法比较，PSO产生合成结果的适应度是传统方法的两倍。蚂蚁优化算法在电信网络的路由问题(ACR)上的应用已经比较成熟，HP公司、

11、英国电信公司都在20世纪90年代后期就展开了这方面的研究13。该算法也越来越多地应用于企业，英国联合利华公司已率先利用这种技术改善其一家牙膏厂的运转状况。美国通用汽车公司、法国液气公司、荷兰公路交通部和美国一些移民事务机构也都采用相应技术以改善其运转的机能。1.2.2国内外对粒子群算法的研究现状在美国成立有专门的组织研究群体的仿真。由欧洲联盟资助的群体智能相关研究项目也于2001年在欧洲多个研究机构启动。在国内，国家自然科学基金“十五”期间学科交叉类优先资助领域中认知科学及其信息处理的研究内容就明确列出了群体智能的进化、自适应与现场认知。相关项目还有复杂系统与复杂性。它的主要研究方向及内容是复

12、杂系统与复杂性的理论与方法研究；物质层次复杂系统的研究；生命层次复杂系统的研究：社会层次复杂系统的研究。2001年3月8日在北京召开的第六届全国人工智能联合会议暨“863”计划智能计算机主题学术会议戴汝为院士特邀报告的主要内容就是群体智能的研究进展。到现在，国家自然科学基金委员会基本每年资助数项粒子群优化算法相关理论和应用的研究。IEEE计算智能协会（IEEE Computational Intelligence Society）自2003年起每年举行一次群体智能会议（IEEE Swarm Intelligence Symposium），而粒子群优化算法是会议的重要主题。1.2.3粒子群优化算

13、法面临的难题虽然粒子群优化算法已在多个领域被有效应用，但其发展历史尚短，还存在很多问题。粒子群优化算法是一种概率算法，缺乏系统化、规范化的理论基础，从数学上对于它们的正确性与可靠性的证明还比较困难，所做的工作也比较少，特别是全局收敛性研究方面。将PSO算法的粒子轨迹分析基于随机事件理论作出定量分析就是一个艰巨的课题，这将关系到PSO算法收敛性、参数选取等关键问题。系统的高层次的行为是需要通过低层次的昆虫之间的简单行为交互突现产生的。单个个体控制的简单并不意味着整个系统设计的简单，必须能够将高层次的复杂行为也就是系统所要执行的功能。在系统设计时还要保证多个个体简单行为的交互能够涌现出希望看到的高

14、层次的复杂行为。这是群体智能中一个极为困难的问题。对于具体的实际问题而言，设计算法时，对算法搜索的效率和收敛的全局性之间要作某种平衡，这种平衡很大程度上是根据经验以算法参数的形式给出的，如何在理论上给出准则，需要对算法进一步进行研究。粒子群优化算法应用于高维复杂问题优化时，往往会遇到早熟收敛的问题，也就是种群在还没有找到全局最优点时已经聚集到一点停滞不动。这些早熟收敛点，有可能是局部极小点，也有可能是局部极小点邻域的一个点。换句话说，早熟收敛并不能保证算法收敛到局部极小点。因而，对算法早熟收敛行为的研究可为算法的进一步改进奠定基础。粒子群优化算法在接近或进入最优点区域时的收敛速度也比较缓慢。实

15、际上对粒子群优化算法的研究发现，粒子群优化算法早期收敛速度较快，但到寻优的后期，其结果改进则不甚理想。这主要归因于算法收敛到局部极小，缺乏有效的机制使算法逃离极小点。1.2.4粒子群算法研究展望综上可推出，以下几点可能是粒子群算法未来可能研究的主要方向和热点：算法基理的数学基础研究。PSO算法在实际应用中被证明是有效的，但目前还没有给出收敛性、收敛速度速度估计等方面的数学证明，已有的工作还远远不够；同时还存在着收敛性分析，鲁棒性分析，计算复杂性分析，参数设置的理论分析以及如何避免陷入局部最优等问题。将各种先进理论引入到PSO算法中。各种先进理论的引入,首先可以研究性能良好的新型粒子群拓扑结构。

16、不同的粒子群拓扑结构是对不同类型社会的模拟,研究不同拓扑结构的适用范围,对算法推广和使用有重要意义；其次可以优化PSO的参数及其选择。参数的选择分别关系到粒子速度的3各部分：惯性部分、社会部分和自身部分在搜索中的作用。如何选择、优化和调整参数，使得算法既能避免早熟又能比较快速地收敛，对工程实践有着重要意义。特别是新的算法模型的提出。目前PSO算法在求解离散问题、非数值化问题上的研究相对滞后。要使用PSO算法处理非数值化问题，关键是要建立与具体问题相适应的新的PSO模型。如何提出一种适合求解这类问题的普遍的算法模型将是很有挑战性的一项工作。与其他智能优化算法的融合。将PSO算法和其他优化算法进行

17、融合，主要是考虑如何将PSO的优点和其他算法的有点相结合，取长补短，构出有特色、有实用价值的混合算法。例如PSO算法主要的一个缺点是容易陷入局部最优，因此如何与其他演化算法，比如遗传算法，模拟退火算法，免疫算法，禁忌搜索算法等等相结合，优势互补，扬长避短，组成一个混和的高性能的优化算法，亦将是未来研究的一个热点。PSO算法的扩展应用。进一步拓展PSO算法的应用领域，对推动算法的研究有着重要的意义。目前PSO的多数研究是针对直角坐标系统描述的系统、离散系统和单一优化系统，而实际系统中,很多系统是非直角坐标系统描述的系统、离散系统、组合优化的系统，目前在这些系统中应用PSO算法可供参考的研究还较少

18、，广泛地开拓PSO算法在这些领域的应用不仅具有实际意义，同时对生化研究PSO算法也非常有意义。1.3本课题所要研究的主要内容通过分析粒子群的内部机制及原理，分析每个粒子对整个粒子群起到的作用，从而充分理解粒子群算法的算法原理，为本课题所要研究的主要内容做好了理论准备。本课题的主要内容从以下方面进行研究：(1)根据粒子群算法的算法原理，分析了粒子群算法求解优化问题的统一框架，在此基础上提出了粒子群优化算法的设计步骤，绘制粒子群算法的流程图；(2)在流程图的基础上编写了粒子群基本算法的Matlab环境下的程序，并将基本算法运用得到函数优化问题中；(3)着重根据基本粒子群算法在优化函数时存在的不足，

19、对算法中的参数进行了多次试验，使其在优化函数问题时可以达到比基本粒子群算法较好的结果。1.4本文的研究方案通过学习、查阅相关粒子群的有关资料，从而熟练掌握粒子群算法的运算流程及步骤，在大量的阅读资料过程中，理解应用的范畴，为本课题打下较好的基础，为下面将粒子群算法运用到函数的优化问题中，准备了理论知识。本文所提供的研究方案主要是大量的实验与统计相结合：(1)在基本的粒子群算法中，参数均为常数，为可得到较好的效果，将参数改进为关于迭代次数的函数；(2)将改进参数的算法运用得到函数优化中，从Matlab仿真结果判断参数的改进是否合理；(3)如果改进参数可以达到较好的效果，然后进行大量的实验，并将实

20、验结果进行统计，确保改进的参数可以在一定的范围为具有实用性；如果改进的参数得到的效果较差，则继续改进参数，知道满足要求。1.5本章小结本章首先介绍了本课题研究的目的和意义，以及粒子群优化算法在国内外的研究现状，接着叙述了本课题所研究的主要内容和所用到研究方案，为下面的章节对粒子群优化算法的一系列研究和改进做好准备。第2章粒子群优化算法2.1引言粒子群优化算法（Particle Swarm Optimization，PSO）具有并行处理、鲁棒性好等特点，能以较大概率找到问题的全局最优解，且计算效率比传统随机方法高。其最大的优势在于简单易实现、收敛速度快，而且有深刻的智能背景，目前已经在函数优化、

21、神经网络设计、分类、模式识别、信号处理、机器人技术等应用领域取得了成功的应用。所以算法自提出以来，引起了国际上相关领域的众多学者的关注和研究，研究者对其改进也非常多，但其基本原理相差无几。2.2粒子群优化算法的统一框架对应于不同实际问题，构造算法主要依赖经验和大量实验。为了更好地使用这些算法求解相关实际问题，有必要研究使用粒子群优化算法求解问题的统一框架。然后，在这个统一的框架下，研究各种具体算法。依据行为主义人工智能框架的一般描述，同时比较多种群体智能算法的个案，如粒子群算法、蚁群算法以及遗传算法等，可以看到：这些算法虽然有不同的物理背景和优化机制，但是从优化流程上看，却具有很大的一致性。这

22、些算法都采用“生成检测”的框架，通过“邻域搜索全局搜索”的策略寻优。本节将试图用一个统一的框架描述粒子群优化算法所具有的共性特征。这些算法中，首先将原问题空间映射为算法空间；接着初始化一组初始解（在通常意义下，使初始解均匀分布于可行域中）；然后，在算法参数控制下根据搜索策略对个体进行搜索从而产生若干待选解；进而按照接受准则（确定性、概率性或混沌方式）更新当前状态，如此反复迭代直到满足某种收敛准则；最后通过空间的反变换，输出原问题的解。算法大致可用框图2-1表示：将问题空间映射为算法空间初始化解与相关参数根据搜索策略产生待选解迭代直到满足终止准则空间反变换并输出原问题解图2-1 粒子群优化算法框

23、架算法的核心包括：算法空间变换和反变换；初始个体的产生准则；邻域搜索策略；全局搜索策略；接受准则以及收敛准则。2.3粒子群优化算法的设计步骤根据上述的粒子群优化算法求解问题的统一框架，可得到粒子群优化算法的设计步骤如下：（1）确定问题的表示方案（编码方案或者称为粒子表示方法）与其他的进化算法相同，粒子群算法在求解问题时，其关键步骤是将问题的解从解空间映射到具有某种结构的表示空间，即用特定的码串表示问题的解。根据问题的特征选择适当的编码方法，将会对算法的性能以及求解结果产生直接的影响。粒子群算法的大部分研究均集中在数值优化领域中，其位置一速度计算模型使用于具有连续特征的问题函数，因此，目前算法大

24、多采用实数向量的编码方式，以粒子的位置向量来表示问题的解。对于生产调度这类属于离散空间的非数值优化问题，如何用粒子群算法的粒子表示方法来映射调度问题的解空间，是求解问题的最关键环节。（2）确定优化问题的适应度函数在求解过程中，借助于适应值来评价解的质量。因此，在求解问题时，必须根据问题的具体特征，选取适当的目标函数或者费用函数来计算适应值，适应值是唯一能够反映并引导优化过程不断进行的参量。（3）选择控制参数粒子群算法的控制参数通常包括粒子种群数量、算法执行的最大代数、惯性权重系数、学习因子系数及其他一些辅助控制参数，如粒子位置和速度的控制范围等。针对不同的算法模型，选择适当的控制参数，直接影响

25、算法的优化性能。（4）选择粒子群优化模型目前，粒子群算法己经发展了多种位置一速度计算模型，如惯性权重PSO模型、收敛因子PSO模型、采用拉伸技术的PSO模型、二进制PSO模型等等，在求解不同类型优化问题时，不同PSO模型的优化性能也有差异。由于惯性权重线性递减PSO模型能够有效地在全局搜索和局部搜索之间进行平衡，因此，目前这一PSO模型得到的较多的应用。（5）确定算法的终止准则与其他进化算法一样，PSO算法中最常用的终止准则是预先设定一个最大的迭代次数，或者当搜索过程中解的适应值在连续多少代后不再发生明显改变时，终止算法。2.4粒子群优化算法描述2.4.1算法原理在1995年的IEEE国际神经

26、网络学术会议上Kennedy和Eberhart发表了题为“Particle Swarm Optimization”的文章，在文章中提出了一种新的智能优化算法粒子群算法。PSO算法和其他进化算法类似，也采用“群体”和“进化”的概念，通过个体间的协作与竞争，实现复杂空间中最优解的搜索。PSO先生成初始种群，即在可行解空间中随机初始化一群粒子，每个粒子都为优化问题的一个可行解，并由目标函数为之确定一个适应值(fitness value)。PSO不像其他进化算法那样对于个体使用进化算子，而是将每个个体看作是n维搜索空间中的一个没有体积和重量的粒子，每个粒子将在解空间中运动，并由一个速度决定其方向和距离

27、。通常粒子将追随当前的最优粒子而动，并经逐代搜索最后得到最优解。在每一代中，粒子将跟踪两个极值，一为粒子本身迄今找到的最优解pbest，另一为全种群迄今找到的最优解gbest。PSO 算法不像遗传算法那样对个体进行选择、交叉和变异操作，而是将群体中的 每个个体视为多维搜索空间中一个没有质量和体积的粒子(点)，这些粒子在搜索空间中以一定的速度飞行，并根据粒子本身的飞行经验以及同伴的飞行经验对自己的飞行速度进行动态调整，即每个粒子通过统计迭代过程中自身的最优值和群体的最优值来不断地修正自己的前进方向和速度大小，从而形成群体寻优的正反馈机制。PSO 算法就是这样依据每个粒子对环境的适应度将个体逐步移

28、到较优的区域，并最终搜索、寻找到问题的最优解。PSO算法具有鲜明的生物社会背景:认知行为和社会行为，即在寻求一致的认知过程中，个体往往记住它们的信念，同时考虑其它同伴的信念，当个体察觉同伴的信念较好时，将进行适应性调整。在PSO算法中，用粒子的位置表示待优化问题的解，每个粒子性能的优劣程度取决于待优化问题目标函数确定的适应值，每个粒子由一个速度矢量决定其飞行方向和速率大小。设在一个d维的目标搜索空间中， 有m个粒子组成一个群体，其中，在第t次迭代时粒子i的位置表示为 Xi(t)=(xi1(t)，xi2(t)，xid(t)，相应的飞行速度表示为 Vi(t)=(vi1(t)，vi2(t)，vid(

29、t)。开始执行PSO 算法时，首先随机初始化m个粒子的位置和速度，然后通过迭代寻找最优解，在每一次迭代中，粒子通过跟踪两个极值来更新自己的速度和位置:一个极值是粒子本身迄今搜索到的最优解，称为个体极值，表示为 Pi(t)=(pi1(t)，pi2(t)，pid(t);另一个极值是整个粒子群到目前为止找到的最优解，称为全局极值，表示为Pg(t)=(pg1(t)，pg2(t)，pgd(t)。在第t+1次迭代计算时,粒子i根据下列规则来更新自己的速度和位置： (2-1) (2-2)式中为惯性权重，取大值可使算法具有较强的全局搜索能力，取小值则算法倾向于局部搜索。一般的做法是将初始取0.9并使其随迭代次

30、数的增加而线性递减至0.4，这样就可以先侧重于全局搜索,使搜索空间快速收敛于某一区域，然后采用局部精细搜索以获得高精度的解;c1、c2:为两个学习因子，一般取为 2;randl和rand2 为两个均匀 分布在(0，l)之间的随机数;i=1，2，m; k=1，2，d。另外，粒子在每一维的速度Vi都被一个最大速度Vmax所限制。如果当前粒子的加速度导致它在某一维的速度超过该维上的最大速度Vmax，则该维的速度被限制为最大速度。式2-1中第1部分可理解为粒子先前的速度或惯性；第2部分可理解为粒子的“认知”行为，表示粒子本身的思考能力;第3部分可理解为粒子的“社会”行为，表示粒子之间的信息共享与相互合

31、作。更新过程中，粒子每一维的位置、速度都被限制在允许范围之内。如果当前对粒子的加速导致它在某维的速度Vi超过该维的最大速度Vdmax，则该维的速度被限制为该维最大速度上限Vdmax。一般来说，Vdmax的选择不应超过的粒子宽度范围,如果Vdmax太大，粒子可能飞过最优解的位置；如果太小，可能降低粒子的全局收索能力。2.4.2算法流程每个粒子的优劣程度根据已定义好的适应度函数来评价，这和被解决的问题相关。下面为标准PSO算法流程如下： (1)随机初始化粒子群体的位置和速度;通常是在允许的范围内随机产生的,每个粒子的pbest坐标设置为其当前位置,且计算出其相应的个体极值(即个体的适应度值), 而

32、全局极值(即全局的适应度值)就是个体极值中最好的，记录该最好值的粒子序号，并将gbest设置为该最好粒子的当前位置;(2)计算每个粒子的适应值；(3)对每个粒子，将其适应值与个体极值pbest进行比较，如果较优，则更新当前的个体极值；(4)对每个粒子，将其适应值与全局极值gest进行比较，如果较优，则更新当前的全局极值；(5)根据式（2-1）、(2-2)，更新每个粒子的位置和飞行速度；(6)如未达到预先设定的停止准则(通常设置为最大迭代次数)，则返回步骤（2），若达到则停止计算。PSO算法可用伪代码表示如下：DO For each particleDoInitialize particle;D

33、oFor each particleCalculate fitness value；If the fitness value is better than the best fitness value(pBest)in history；Set current value as the new pBest；Choose the particle with the best fitness value of all the particles as the gBest；For each particleCalculate particle velocity according equation(2

34、-1)；Update particle position according equation(2-2)；While maximum iterations or minimum criteria is not attained；初始化粒子群；For 每个粒子计算其适应度；If (适应度优于粒子历史最佳值) 用Xi更新历史最佳个体Pi；End选取当前粒子群中最佳粒子；If (当前最佳粒子优于群历史最佳粒子) 用当前群最佳粒子更新Pg；For 每个粒子 按式(2-1)更新粒子速度；按式(2-2)更新粒子位置；EndWhile 最大迭代数未达到或最小误差未达到。粒子群优化算法流程图见图2-2：初始化

35、粒子速度及位置计算粒子适应度Present优于pbestPresent=pbsetPresent优于gbestPresent=gbest更新粒子速度及位置算法收敛准则满足？输出gbest否否否是是图2-2 粒子群优化算法流程2.5粒子群算法的改进2.5.1粒子群算法的优缺点粒子群算法是一种新的群体智能优化算法，自从提出以来，以其独特的魅力受到了研究者们的青睐。目前已经得到了较大的发展。但是由于提出时间不 长，算法还缺乏深刻的理论分析和坚实的数学基础，还存在许多不完善的地方，还有很多问题有待进一步解决。参考国内外大量的研究文献和工程实践，基本PSO算法优缺点可以分别归纳如下：基本粒子群算法的优点

36、：PSO算法没有交叉和变异运算，依靠粒子速度完成搜索，并且在迭代进化中只有最优的粒子把信息传递给其他粒子，搜索速度快； PSO算法具有记忆性，粒子群体的历史最好最好位置可以记忆并传递给其他粒子； 需要调整的参数较少，结构简单，易于工程实现； 采用实数编码，直接由问题的解决定，问题解的变量数直接作为粒子的维数。 基本粒子群算法的缺点： 容易陷入局部最优，导致收敛精度低和不易收敛； 不能有效解决李三机组和优化问题； 不能有效求解一些非直角坐标系描述问题，如有关能量场或场内粒子运动规律的求解问题（这些求解空火箭的边界大部分是基于极坐标、球坐标或柱坐标的）。2.5.2粒子群算法的改进自从 Kenned

37、y 在1995提出基本PSO算法后，PSO算法引起了众多研究者们的兴趣，他们提出了各种改进的PSO算法。我们归纳了主要的几类改进的PSO算法：增加惯性因子的改进；基于收敛性分析的改进；导入其他演化算法思想的改进；建立非数值问题模型的改进。增加惯性因子的改进粒子群算法(标准PSO算法）在求解实际应用的各种问题中，对算法的局部搜索能力和全局搜索能力的比例要求不尽相同，甚至对同一个问题，在其进化的不同阶段，对它们的要求也有可能是不一样的。基于这么一个事实，Yuhui Shi 等 提出了带惯性因子的 PSO 算法。进化方程为： (2-3) (2-4)以上算式经常被学者们引用作为标准 PSO 算法。其中

38、惯性因子表征粒子惯性大小：对原来速度的保持程度。Yuhui Shi在文中建议的取值在0,1.4。而在实验结果表明的取值在0.8,1.2之间算法收敛速度更快一点。较大时，具有较强的全局收敛能力，较小时具有较强的局部收敛能力，因此有点类似于模拟退火中的温度，随着迭代次数的增加，的值应该不断地减小，从而使得在算法开始初期，要求有较强的全局搜索能力，在后期，要求有较强的局部搜索能力，以提高算法的整体性能。Yuhui Shi在文献14中提出了在 0.9 到0.4之间线性递减的策略： (2-5)其中t为当前迭代次数，MaxNumber是最大迭代次数。通过对四个Benchmark 函数的测试结果表明算法收敛

39、性能有了明显的改进。但是，惯性因子在进化的过程中线性递减的策略往往不能反映实际的优化算法搜索过程，为此文献15提出了一种基于模糊系统的惯性因子动态调整策略，取得了良好的效果。基于收敛性分析的改进粒子群算法由于标准PSO算法有可能出现太早收敛的情况，文献16提出了一种保证收敛的改进粒子群算法GCPSO。文中注意到当粒子位置达到最优的时候，从公式（2-1）可以看出，速度算式的第二、第三部分均为零。因此粒子只能按原来的速度进行调整，一直沿着,一个方向直线飞行直到边界或找到更好的解为止。而粒子直线飞行能找到更优解的概率是非常小的。为了保证达到最优解的粒子能够正常的移动，GCPSO提出了最佳粒子的位置和

40、速度的更新等式： (2-6) (2-7)其中是达到最优解的粒子的下标,p(t)是比例因子，如果算法连续成功找到最优解达到指定次数，则增大p(t)的值，如果连续失败达到指定次数，则减小p(t)的值，如果连续成功或失败没有达到指定次数，则保持p(t)不变。仿真结果表明：GCPSO可得到比标准PSO更好的结果或类似结果，但是该算法不能保证全局收敛。曾建潮等人提出了一种保证全局收敛的SPSO算法，并证明了收敛条件： 0c1c22。在标准PSO算法中，粒子仅仅追随个体最优和全局最优两个粒子运性动，这种策略在一定程度上影响了算法的全局收敛性能。为了改善算法收敛能，Suganthan提出了一种基于动态邻域的

41、PSO模型17，其基本思想是用每个粒子所定义的当前邻域极值代替全局极值。在算法开始的阶段，每个粒子的领域为其本身，随着进化代数的增加，邻域范围也在不断地增大，直至整个种群。该算法在一定程度上克服了PSO算法在优化搜索后期随迭代次数增加，结果却没有明显改进的缺点。使用Benchmark函数测试，对不同函数和参数效果不大相同，但总的看来，改进效果比较弱，这主要是与算法的邻域结构的选择有关。为了改善算法性能，Kennedy 等提出了几种基本的邻域结构18：环形结构，轮形结构及其推广,使得算法收敛性能得到了提高。导入其他演化算法思想的改进 PSO算法标准 PSO算法中粒子在解空间追随最优的粒子进行搜索

42、，但是PSO算法中没有明显的选择、交叉以及变异等演化运算。适当地引入演化算子，在一定程度上可以提高算法的性能。导入其他演化算法思想来改进 PSO算法是目前一个研究热点。Angelin提出了一种具有选择机制的改进PSO算法19。该算法基本思路是：在进化过程中保存种群中所有粒子适应度的排序，然后用适应度好的前一半的粒 子替代适应度不好的后一半粒子。对四个Benchmark 函数的测试结果表明，该算法提高了求解三个测试函数的性能，但是也增加了陷入局部最优的可能性。Angeline提出了一种杂交的粒子群算法20。该算法的基本思路是：在迭代的过程中，按已经设定的杂交概率选择指定数量的粒子放到杂交池中随机

43、杂交，并用生成的子代替代父代。仿真实验结果表明杂交操作降低了单峰函数的收敛率。但是对多峰值函数来说，收敛速度和精度都有了提高。窦全胜等人提出一种基于模拟退火的PSO算法和有分工策略的PSO算法21。针对标准粒子群算法容易陷入局部最优的缺陷，提出将模拟退火引入并行PSO 算法中。测试的结果表明，该算法在温度变换相对缓慢时，能够搜索到较好的结果，而增加基本PSO算法的迭代次数时不能收到这样的效果。这种改进PSO算法在解决无约束问题上具有较强的应用价值高鹰等人提出了免疫PSO算法22。免疫PSO算法受生物系统免疫机制的启发，把免疫信息引入到PSO算法中，算法结合了标准PSO所具有的全局最优搜索能力和

44、免疫算法的免疫信息处理机制，实验结果表明该算法改善了基本PSO跳出局部最优的能力，提高了算法优化过程中的收敛质量和收敛速度。建立非数值问题模型的改进PSO算法由于PSO简单的位置和速度算式，对数值化的问题很容易表达出来，因此处理数值化问题的各种PSO改进算法得到了较大的发展；而对于非数值化问题而言，不能直接用位置和速度把问题表达出来，因此目前处理非数值化问题的PSO算法研究相对滞后。我们认为：要使用 PSO算法处理非数值化问题，关键是要建立与具体问题相适应的新的PSO算法模型，使得这个模型的位置和速度两个量以及它们的运算可以清晰地把非数值化问题描述出来。Kang- Ping Wang 等人提出

45、一种求TSP问题的PSO改进算法23。把粒子位置直接定义TSP问题的解，即是结点的序列，而将速度定义为两个结点之间的交换集，并将它们之间的加法算子定义为对结点序列（粒子位置）依次交换交换集（速度）中的交换子。文章也做出了仿真试验：粒子个数设置为100，在迭代20000 次，可以求解到14个城市的最佳路径。实验结果可看出，该改进算法求解TSP问题效果不佳。高海兵等人提出了一种适合求解离散问题和组合优化问题的广义的粒子群模型24。该模型根据优化 问题的特点设计其粒子的更新策略，可以实现与已有方法的融合。文章以TSP问题为例，针对遗传算法解决该问题的成功经验，使用遗传算子作为模型的更新算子，进一步提

46、出基于遗传操作的粒子群优化模型，并以 Inver- over 算子作为模型中具体的遗传操作设计了基于广义模型TSP算法，文中做了对广义模型PSO算法和采用相同遗传操作的遗传算法进行了对比实验。实验结果表明：广义模型的PSO求解的质量和收敛稳定性均优于遗传算法。文献2324均做出了求解 TSP 问题的实验，实验结果可以看出，文献24算法的求解性能要远远好于文献23算法。两种算法性能差异主要原因是在建立的求解模型的差异上，因此我们认为：建立合适的非数值问题模型是PSO算法求解非数值问题关键所在。2.6本章小结本章首先对使用粒子群优化算法求解问题的统一框架进行了分析，在此基础上提出了粒子群优化算法的

47、设计步骤；接着对基本粒子群优化算法的原理进行了分析，从算法的产生机理、编码、迭代过程等方面介绍了粒子群优化算法。从而对粒子群算法有了更深一步的理解，为下章粒子群算法在函数的优化问题中的应用打下基础。第3章粒子群算法在函数优化问题中的应用3.1前言在第二章已经分析基本粒子群的算法理论及标准粒子群算法的公式，这一章主要是在标准的粒子群算法的基础上引入参数并且对参数进行改进设置，然后运用测试函数对修改后的参数进行测试，并且通过Matlab仿真，使其具有实际可行性。3.2常用测试函数 PSO算法常用的测试函数：Sphere、Rosen-brock、Schaffers f6、Ackley、Griewank和Rastrigrin等。测试函数的最优点x*均为(0,0)或1，函数的最优值(全局最优解)f(x*)=0。前两个测试函数是