粒子群优化算法

《粒子群优化算法》由会员分享，可在线阅读，更多相关《粒子群优化算法（20页珍藏版）》请在装配图网上搜索。

1、1.1 1群体智能概述群体智能的概念与特点群体智能的概念源于对蜜蜂、蚂蚁、大雁等这类群居生物群体行为的观察和研究，是一种在自然界生物群体所表现出的智能现象启发下提出的人工智能实现模式，是对简单生物群体的智能涌现现象的具体模式研究。群体智能指的是“简单智能的主体通过合作表现出复杂智能行为的特性”。该种智能模式需要以相当数目的智能体来实现对某类问题的求解功能。作为智能个体本身，在没有得到智能群体的总体信息反馈时，它在解空间中的行进方式是没有规律的。只有受到整个智能群体在解空间中行进效果的影响之后，智能个体在解空间中才能表现出具有合理寻优特征的行进模式。自然界中动物、昆虫常以集体的力量进行觅食生存，

2、在这些群落中单个个体所表现的行为是简单缺乏智能的，且各个个体之间的行为是遵循相同规则的，但由个体组成的群体则表现出了一种有效的复杂的智能行为。群体智能可以在适当的进化机制引导下通过个体交互以某种突现形式发挥作用，这是个体的智能难以做到的。通常，群体智能是指一种人工智能模式，体现的是一种总体的智能特性。人工智能主要有两种研究范式，即符号主义和联接主义。符号主义采用知识表达和逻辑符号系统来模拟人类的智能。联接主义则从大脑和神经系统的生理背景出发来模拟它们的工作机理和学习方式。符号主义试图对智能进行宏观研究，而联接主义则是一种微观意义上的探索。20世纪90年代后，计算智能的研究逐渐成为了联接主义人工

3、智能的一个代表性流派。计算智能系统是在神经网络、模糊系统、进化计算三个分支发展相对成熟的基础上，通过相互之间的有机融合而形成的新的科学方法，也是智能理论和技术发展的崭新阶段。神经网络反映大脑思维的高层次结构；模糊系统模仿低层次的大脑结构；进化系统则是从生物种群的群体角度研究智能产生和进化过程。对群居性生物群体行为涌现的群体智能的研究是进化系统的一个新兴研究领域。群体智能中，最小智能但自治的个体利用个体与个体和个体与环境的交互作用实现完全分布式控制，其具有以下特点：（1）自组织。自组织是一种动态机制，由底层单元（部件）的交互而呈现出系统的全局性的结构。交互的规则仅依赖于局部信息，而不依赖于全局的

4、模式。自组织并不是外部的影响施加给系统而体现的一种性质，而是系统自身涌现出的一种性质。系统中没有一个中心控制模块，也不存在一个部分控制另一部分。正反馈（positivefeedback）群体中的每个具有简单能力的个体表现出某种行为，会遵循已有的结构或者信息指引自己的行动，并且释放自身的信息素，这种不断的反馈能够使得某种行为加强。尽管一开始都是一些随机的行为，大量个体遵循正反馈的结果是呈现出一种结构。自然界通过系统的自组织来解决问题。理解了大自然中如何使生物系统自组织，就可以模仿这种策略使系统自组织。（2）自恢复。群体是由很多的个体组成的，不存在中央控制，几乎每一个个体都在群体中享有同样重要的地

5、位。群体中单个个体的状态，不会直接影响到整个群体。这个特点在自然界生物原型中体现得非常明显：在蚂蚁群体中，单个蚂蚁意外死亡不会影响整个群体的觅食；在鸟群的飞行过程中，一只鸟出现意外，整个鸟群在经过短暂的惊慌之后，仍然会恢复整齐有序的飞行；人体皮肤受创后，表皮细胞能“记忆”受创前的皮肤特征，并生成新的表皮细胞，重构出原来的形状和颜色。由此可见，群体在此过程中具有自我恢复的能力。当然，群体的恢复也是有限度的，当其数量减少到一定的程度，就会失去恢复能力。群体的这种特性，在网络、军事、医学等领域都有广阔的应用前景。（3）间接通信。群体系统中个体之间如何进行交互是个关键问题。个体之间有直接的交流，如触角

6、的碰触、食物的交换、视觉接触等，但个体之间的间接接触更为微妙，群体中个体传递信息，通常都是通过改变局部环境来实现，其他个体通过感知环境变化，也就获得了相应的信息。已有研究者用Stigmergy来描述这种间接通信机制：也就是个体感知环境，对此作出反应，又作用于环境。Grasse首先引入Stigmergy来解释白蚁筑巢中的任务协调。Stigmergy在宏观上提供了一种将个体行为和群体行为联系起来的机制。个体行为影响着环境，又因此而影响着其他个体的行为。个体之间通过作用于环境并对环境的变化作出反应来进行合作。这在蚂蚁觅食的过程中表现得非常明显：先行的蚂蚁在路上留下一种信息素，后面的蚂蚁选择信息素浓度

7、更高的路径，由此形成一种信息正反馈机制，通过不断重复，最终绝大多数蚂蚁走的都是最短的路线。对于习惯了直接通信的人类来说，生物种群的这种行为特点，不能不说是一种启发。从蚂蚁寻食到蚂蚁聚集尸体到蚂蚁搬运、筑巢，个体之间的通信机制总是离不开Stigmergy机制，对于作为个体之间交流、交互的媒介环境的作用，通常由各种各样的信息素来体现。（4）学习。学习的目的在于适应和优化。适应是为了生存，优化是为了更好地发展。对于自然生命或者是自然智能而言，学习都是其最重要的特征。自组织、自适应是群体生物的重要特点，群体智能中的学习又有其独特之处。群体生物的独特学习方法就是进化。它们总是先以其数量占据优势，然后随着

8、环境的变化，淘汰不能适应环境的个体。在这个过程中，对每一个个体而言，并没有发生任何学习行为。但是，从整体来看，环境变化后的群体具有更强的适应能力。进化的目的也是为了适应和优化，这与学习完全一致。当然，进化的实现有其前提条件，最重要的两个是多样性和正反馈。只有不断保持种群自身的多样性，生物有了多种选择，才有实现进化的可能；同样，只有实现了对有利条件的正反馈，形成一个吸引子，进化才能够总是向着有利于群体生存的方向，进化的成果才能得以巩固和发展。1.2 群体智能中的知识涌现群体智能中的智能就是大量个体在无中心控制的情况下体现出来的宏观有序的行为。这种大量个体表现出来的宏观有序行为称为涌现现象。没有涌

9、现(Emergenc现象，就无法体现出智能。因此，涌现是群体智能系统的本质特征。只知道孤立的个体行为并不能了解整个系统(如蚁群)的情况，仅仅研究孤立的部分无法有效地研究整体性质，因此，对涌现现象的研究必须既研究各个部分，又研究各个部分之间的相互作用。涌现最早是作为系统科学的重要概念被提出来的。系统科学的创始人贝塔郎菲(Bertlanfy)从一开始就把一般系统论界定为关于整体性的科学，把整体性界定为一种“涌现”的性质。全部系统研究的任务集中到一点，就是阐明整体为何大于部分之和，然后制定描述大于部分之和的整体性质(即涌现性)的方法。“遗传算法之父”约翰霍兰对涌现现象进行了较为深入的探索。他认为涌现

10、现象的本质是“由小生大，由简入繁”，并且把细胞组成生命体，简单的走棋规则衍生出复杂的棋局等现象都视为涌现现象。他认为神经网络、元胞自动机等可算作涌现现象的模型。对于涌现现象的研究，一直都是和复杂系统联系在一起的。涌现不仅是复杂系统中的现象，同时也是群体智能的重要特征。群体智能的涌现现象与系统论和复杂系统中阐述的涌现本质上是相同的，它是基于主体的涌现。群体中的个体结构和功能都非常简单，通过相互通讯和协调组成群体系统，同时涌现出一些整体的性质和新的功能。这种智能本身也正是群体系统中涌现的结果。研究群体智能系统，要弄清涌现现象的普遍原理，建立由简单规则控制的模型来描述涌现现象的规律。在群体智能中，涌

11、现现象具有如下的性质：(1)涌现现象的出现是很多个体相互关联的结果，这些个体规则简单，相互影响；(2) 这种现象是从底部向上的，从低层次向高层次的，是总体的或者说是宏观层次的；(3) 某一层次涌现的集成可以产生更上一层次的涌现，例如原子构成分子，分子构成细胞，后者都是在前者涌现性质的基础上产生新的整体性质；(4) 涌现作为一种整体现象，不因为部分个体的改变而改变；涌现是显示性的；（6）涌现是一种组织效应、结构效应，它在一定程度上可以预测；（7）涌现有层次水平的高低，水平越高的涌现越复杂。1.3群体智能研究方法群体智能是目前智能领域非常活跃的新兴研究领域，作为智能计算和群体智能领域的关键技术，同

12、时作为仿生智能计算领域的重要分支，群体智能计算在获得更大的发展的同时，也必将推动群体智能与计算智能以及相关学科和研究领域的壮大与发展。从方法上看，国内外对群体智能的研究，主要体现在：群体行为模拟、群体智能计算和分布式问题解决装置研究等方面。群体智能研究框图如图1.1所示。群体智能研究图1.1群体智能研究框图Table1.1Researchframeofswarmintelligenee（1）群体行为模拟研究群体行为模拟研究包括：蚁群觅食行为研究，群体分工和任务分配行为研究，巢穴组织和自组织行为研究，筑巢行为和群体合作搬运行为研究，鸟类聚集飞行行为研究等。群体行为研究和计算机仿真为群体智能算法研

13、究提供了思路。（2）算法设计及改进研究在算法研究方面，作为群体智能算法的两种典型实现，蚁群算法（ACO）和粒子群算法（PSO）得到了广泛关注。在基本蚁群算法提出之后，在前面所提到的群体行为模拟研究的基础上，被多个领域的研究工作者进行了改进，提出了很多新的算法并成功用于实际工程中。对粒子群算法的研究与改进主要从参数选择与设计、种群拓扑结构、群体组织与进化以及混合粒子群算法进行。（3）算法应用研究群体智能自提出以来，由于其在解决复杂的组合优化类问题方面所具有的优越性能，在诸如工程设计与优化、电力系统领域、机器人设计与控制、交通规划、工业生产优化以及计算机网络等领域取得了较为成功的应用。此外，群体智

14、能算法还用于交通导航与路径规划的动态规划问题、任务分配问题、数据挖掘和数据高层综合问题以及系统辨识与状态估计等。(4) 分布式装置实现根据群体智能的特点，很多研究者在分布式问题解决装置研制方面也进行了尝试。美国五角大楼资助了群体智能系统的研究虫群战略。群体智能为设计智能系统提供了另一种选择途径，这种方法用自治、涌现和分布式运行代替了控制、预先编制程序和集总式运行。其中群体智能计算是最为活跃的一个研究分支。群体智能计算包括：群体智能算法设计与改进、群体智能算法在优化问题求解和工程领域中的应用。群体智能计算是在群体智能领域中计算智能研究的逐步深入而产生的一种新兴的计算智能模式，它是群体智能研究中的

15、一个重要分支，在对某些群体行为模拟研究的基础上，运用一定的数学工具和计算机工具，提出相应的群体智能算法，并用来解决那些因为难以建立有效的形式化模型而用传统优化方法又难以有效解决甚至无法解决的问题。2粒子群优化算法粒子群优化(ParticleSwarmOptimization,PSO)算法最初是由Kennedy和Eberhart于1995年受人工生命研究结果启发，在模拟鸟群觅食过程中的迁徙和群集行为时提出的一种基于群体智能的进化计算技术。鸟群中的每只鸟在初始状态下是处于随机位置向各个随机方向飞行的，但是随着时间的推移，这些初始处于随机状态的鸟通过自组织(self-organization)逐步聚

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

17、物位置的信息，可以大大的加快找到食物的速度，也即是通过合作可以加快发现目标的速度，通常群体搜寻所获得利益要大于群体成员之间争夺资源而产生的损失。这些简单的经验事实如果加以提炼，可以用如下规则来说明：当整个群体在搜寻某个目标时，对于其中的某个个体，它往往是参照群体中目前处于最优位置的个体和自身曾经达到的最优位置来调整下一步的搜寻。Kennedy和Eberhart把这个模拟群体相互作用的模型经过修改并设计成了一种解决优化问题的通用方法，称之为粒子群优化算法。PSO算法不像遗传算法那样对个体进行选择、交叉和变异操作，而是将群体中的每个个体视为多维搜索空间中一个没有质量和体积的粒子(点)，这些粒子在搜

18、索空间中以一定的速度飞行，并根据粒子本身的飞行经验以及同伴的飞行经验对自己的飞行速度进行动态调整，即每个粒子通过统计迭代过程中自身的最优值和群体的最优值来不断地修正自己的前进方向和速度大小，从而形成群体寻优的正反馈机制。PSO算法就是这样依据每个粒子对环境的适应度将个体逐步移到较优的区域，并最终搜索、寻找到问题的最优解。粒子群优化研究人员对粒子群体组织和协作模式以及算法参数等进行了研究，提出了如模糊PSO、带选择的PSO、具有高斯变异的PSO、具有繁殖和子种群的混合PSO簇分析PSO、协同PSO以及多阶段PSO等。虽然这些算法基于对不同物理系统的模拟，然而它们有相通的共性，如：在这些方法中，没

19、有一个作为核心的个体，每个个体只拥有简单的智能，通过大量这样个体的信息交互(Interaction)，群体表现强大的智能。在优化领域，这些方法已经被成功的应用于常规算法难以求解的非凸、非线性，离散优化问题，积累了丰富的实际经验和理论成果。2.1 粒子群优化算法的研究现状群体智能已成为分布式人工智能研究的一个重要领域。在美国成立有专门的组织研究群体的仿真。由欧洲联盟资助的群体智能相关研究项目也于2001年在欧洲多个研究机构启动。在国内，国家自然科学基金“十五”期间学科交叉类优先资助领域中认知科学及其信息处理的研究内容就明确列出了群体智能的进化、自适应与现场认知。相关项目还有复杂系统与复杂性。它的

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

21、粒子群优化算法的研究方向PSO自1995年提出以来，由于其简单和明确的实际背景，以及前述的诸多优点，使得很多研究者加入到对这种算法的研究中，目前粒子群优化算法的理论研究与应用研究都取得了很大的进展，对于算法的原理已经有了初步的了解，算法的应用也已经在不同学科中得以实现。这些研究主要集中在如下几个方面：（1）粒子群优化算法的理论分析具体来说，这个问题的研究分为三个方面：一是单个粒子的运动轨迹，现有的研究发现，单个粒子不断的在各种正弦波上“跳跃”，即其轨迹是各种正弦波的随机的叠加组合，这里所用的主要工具是微分方程和差分方程；二是收敛性问题，关于粒子群算法的收敛性研究比较多的集中在一些简化条件下的结

22、果，采用的主要工具是动态系统理论。其它还有采用集合论的方法来研究此问题，得出的结论是：在没有任何改进的情况下，原始的粒子群优化算法既不能收敛到全局极值点，也不能收敛到局部极值点，但是这种证明是非构造性证明，对于理解算法的工作原理没有太大帮助。三是整个粒子系统随时间的演化和分布，这方面的研究目前还少有人涉及。（2）粒子群优化算法的改进这方面的内容非常庞杂，从改进的策略来说，可以分为如下几种类型，一是从算法本身的改进，例如对算法迭代式的改进，或对算法参数的优化。二是和进化计算的结合，例如采用杂交的算子来优选粒子。三是拓扑结构的研究，通过数值实验来寻找最合适的邻域结构，或者随着计算的进行，动态的改变

23、邻域结构。四是基于函数变换的方法，在算法运行的过程中，不断的改变被优化函数的形状。以上这些方法，从根本上说，主要是为了克服粒子群优化算法在优化多峰复杂函数时，会出现早熟，粒子的多样性减低，以致于不能收敛到全局极值点的现象。（3）粒子群优化算法的应用粒子群优化算法的应用已经扩展到很多领域，从最初的复杂多峰非线性函数的优化、多目标优化等传统问题，到电力系统的分析，动态系统的跟踪与优化、神经网络的权值训练并将其用于复杂系统的建模，非线性系统的优化控制问题等等。算法研究的目的是应用，如何将粒子群算法应用于更多领域，同时研究应用中存在的问题也非常值得关注。2.2.2 粒子群优化算法的应用现状实际应用方面

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

25、电力系统的应用粒子群优化算法在电力系统优化中有着广泛的应用，例如在配电网扩展规划、检修计划、机组组合、负荷经济分配、最优潮流计算与无功优化控制、谐波分析与电容器配置、配电网状态估计、参数辨识、优化设计等方面。此外，在电力系统机组组合优化问题求解、多机器功率系统稳定器的最优设计等方面，粒子群算法具有突出的求解性能。日本的Fuji电力公司的研究人员将电力企业著名的RPVC（ReactivePowerandVoltageControl）问题简化为函数的最小值问题，并使用改进的PSO算法进行优化求解。与传统方法如专家系统、敏感性分析相比，实验结果证明了PSO算法在解决该问题上的优势。（3）计算机领域中

26、的应用 任务分配。任务分配问题的解决是有效利用分布或并行式计算机系统能力的核心步骤之一，是将一程序任务在分布计算机系统的不同处理器之间进行分配，以减少程序的运行时间，增加系统解决问题的能力。它是一个NP完全问题，其目标通常是，在最大化和平衡资源利用的同时最小化处理器之间的通信。用粒子群算法求解任务分配问题，可用相互作用图的形式描述任务分配问题，寻找问题解和算法中粒子间的恰当映射，使得所有处理器的最大处理时间为最小。 神经网络训练。研究表明，PSO是一种很有潜力的神经网络训练算法，粒子群优化算法保留了基于种群的、并行的全局搜索策略，其采用的速度位移模型操作简单，避免了复杂的遗传操作。通过训练神经

27、网络，粒子群优化算法已成功应用到对医学中震颤行为的分析。震颤行为（包括帕金森症和人的本能颤抖）的诊断仍是医学研究的挑战性领域之一，经PSO训练的人工神经网络已经能够区分人的本能震颤和病理性震颤。将PSO算法与BP算法相结合训练神经网络已用于对电动汽车燃料电池组实时充电情况的模拟。对电动汽车燃料电池带电状况的模拟是电动汽车以及混合动力汽车技术发展过程中的重大课题。此外，粒子群优化算法还在数据挖掘、图像处理以及计算机图形学领域都有着成功的应用。（4）控制领域中的应用 莫糊控制系统。利用PSO算法优化模糊控制系统，设计模糊控制器。目前，从模糊神经网络系统自动提取模糊规则的研究在一些典型的问题上已经取

28、得进展，这对于自动生成模糊系统控制规则的模糊控制器在应用领域的推广有很大的启示。 冶金自动化。例如，在对粗轧宽展控制模型进行优化方面，采用粒子群算法对粗轧宽展控制模型进行优化。另外，粒子群算法还被用于计算机数字控制的研磨。（5）其他实际应用除了上述应用领域外，粒子群优化算法在化工领域，生物医学以及电磁学等领域都有一定的应用。粒子群算法已被美国一家公司用于将各种生物化学成分进行优化组合，进而人工合成微生物。与传统的工业优化方法比较，PSO产生合成结果的适应度是传统方法的两倍。2.3粒子群优化算法面临的难题虽然粒子群优化算法已在多个领域被有效应用，但其发展历史尚短，还存在很多问题。（1）粒子群优化

29、算法是一种概率算法，缺乏系统化、规范化的理论基础，从数学上对于它们的正确性与可靠性的证明还比较困难，所做的工作也比较少，特别是全局收敛性研究方面。将PSO算法的粒子轨迹分析基于随机事件理论作出定量分析就是一个艰巨的课题，这关系到PSO算法收敛性、参数选取等关键问题。（2）系统的高层次的行为是需要通过低层次的昆虫之间的简单行为交互突现产生的。单个个体控制的简单并不意味着整个系统设计的简单，必须能够将高层次的复杂行为也就是系统所要执行的功能映射到低层次的简单个体的简单行为上面，而这二者之间是存在较大差别的。在系统设计时还要保证多个个体简单行为的交互能够涌现出希望看到的高层次的复杂行为。这是一个极为

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

31、研究发现，粒子群优化算法早期收敛速度较快，但到寻优的后期，其结果改进则不甚理想。这主要归因于算法收敛到局部极小，缺乏有效的机制使算法逃离极小点。2.4粒子群优化算法的统一框架对应于不同实际问题，构造算法主要依赖经验和大量实验。为了更好地使用这些算法求解相关实际问题，有必要研究使用粒子群优化算法求解问题的统一框架。然后，在这个统一的框架下，研究各种具体算法。依据行为主义人工智能框架的一般描述，同时比较多种群体智能算法的个案，如粒子群算法、蚁群算法以及遗传算法等，可以看到：这些算法虽然有不同的物理背景和优化机制，但是从优化流程上看，却具有很大的一致性。这些算法都采用“生成+检测”的框架，通过“邻域

32、搜索+全局搜索”的策略寻优。首先，将原问题空间映射为算法空间；接着初始化一组初始解（在通常意义下，使初始解均匀分布于可行域中）；然后，在算法参数控制下根据搜索策略对个体进行搜索从而产生若干待选解；进而按照接受准则（确定性、概率性或混沌方式）更新当前状态，如此反复迭代直到满足某种收敛准则；最后通过空间的反变换，输出原问题的解。算法大致可用框图1表示：图1粒子群优化算法框架算法的核心包括：算法空间变换和反变换；初始个体的产生准则；邻域搜索策略；全局搜索策略；接受准则以及收敛准则。2.5粒子群优化算法的设计步骤根据上述的粒子群优化算法求解问题的统一框架，可得到粒子群优化算法的设计步骤如下：（1）确定

33、问题的表示方案（编码方案或者称为粒子表示方法）与其他的进化算法相同，粒子群算法在求解问题时，其关键步骤是将问题的解从解空间映射到具有某种结构的表示空间，即用特定的码串表示问题的解。根据问题的特征选择适当的编码方法，将会对算法的性能以及求解结果产生直接的影响。粒子群算法的大部分研究均集中在数值优化领域中，其位置一速度计算模型使用于具有连续特征的问题函数，因此，目前算法大多采用实数向量的编码方式，以粒子的位置向量来表示问题的解。比如，对于生产调度这类属于离散空间的非数值优化问题，如何用粒子群算法的粒子表示方法来映射调度问题的解空间，是求解问题的最关键环节。（2）确定优化问题的适应度函数在求解过程中

34、，借助于适应值来评价解的质量。因此，在求解问题时，必须根据问题的具体特征，选取适当的目标函数来计算适应值，适应值是唯一能够反映并引导优化过程不断进行的参量。（3）选择控制参数粒子群算法的控制参数通常包括粒子种群数量、算法执行的最大代数、惯性权重系数、学习因子系数及其他一些辅助控制参数，如粒子位置和速度的控制范围等。针对不同的算法模型，选择适当的控制参数，直接影响算法的优化性能。（4）选择粒子群优化模型目前，粒子群算法己经发展了多种位置速度计算模型，如惯性权重PSO模型、收敛因子PSO模型、采用拉伸技术的PSO模型、二进制PSO模型等等，在求解不同类型优化问题时，不同PSO模型的优化性能也有差异

35、。由于惯性权重线性递减PSO模型能够有效地在全局搜索和局部搜索之间进行平衡，因此，目前这一PSO模型得到的较多的应用。（5）确定算法的终止准则与其他进化算法一样，PSO算法中最常用的终止准则是预先设定一个最大的迭代次数，或者当搜索过程中解的适应值在连续多少代后不再发生明显改变时，终止算法。2.6.1 2.6粒子群优化算法描述算法原理在1995年的IEEE国际神经网络学术会议上Kennedy和Eberhart发表了题为“ParticleSwarmOptimization的文章，在文章中提出了一种新的智能优化算法粒子群算法。PSO算法和其他进化算法类似，也采用“群体”和“进化”的概念，通过个体间的

36、协作与竞争，实现复杂空间中最优解的搜索。PSO先生成初始种群，即在可行解空间中随机初始化一群粒子，每个粒子都为优化问题的一个可行解，并由目标函数为之确定一个适应值（fitnessvalue）.PSO不像其他进化算法那样对于个体使用进化算子，而是将每个个体看作是在n维搜索空间中的一个没有体积和重量的粒子，每个粒子将在解空间中运动，并由一个速度决定其方向和距离。通常粒子将追随当前的最优粒子而动，并经逐代搜索最后得到最优解。在每一代中，粒子将跟踪两个极值，一为粒子本身迄今找到的最优解pbest，另一为全种群迄今找到的最优解gbest假设在D维搜索空间中，有m个粒子组成一群体，第i个粒子在D维空间中的

37、位置表示为x=区1必2,，心)，第i个粒子经历过的最好位置(有最好适应度)记为Pi=(Pii,Pi2,，PiD)，每个粒子的飞行速度为V=(Vii,Vi2，ViD),i=1,2,m。在整个群体中，所有粒子经历过的最好位置为Pg=(Pg1,Pg2,PgD)，每一代粒子根据下面公式更新自己的速度和位置：vidwvidC1ri(Pid-xid)c2r2(Pgd_Xid)(2.1)xid=Xidvid.(2.2)其中，w为惯性权重；Ci和C2为学习因子；ri和2是10,11之间的随机数。公式由三部分组成，第一部分是粒子先前的速度，说明了粒子目前的状态；第二部分是认知部分(CognitionModal)

38、，是从当前点指向此粒子自身最好点的一个矢量，表示粒子的动作来源于自身经验的部分；第三部分为社会部分(SocialModal)，是一个从当前点指向种群最好点的一个矢量，反映了粒子间的协同合作和知识的共享。三个部分共同决定了粒子的空间搜索能力。第一部分起到了平衡全局和局部搜索的能力。第二部分使粒子有了足够强的全局搜索能力，避免局部极小。第三部分体现了粒子间的信息共享。在这三部分的共同作用下粒子才能有效的到达最好位置。更新过程中，粒子每一维的位置、速度都被限制在允许范围之内。如果当前对粒子的加速导致它在某维的速度Vi超过该维的最大速度Vdmax，则该维的速度被限制为该维最大速度上限Vdmax。一般来

39、说，Vdmax的选择不应超过的粒子宽度范围，如果Vdmax太大，粒子可能飞过最优解的位置；如果太小，可能降低粒子的全局收索能力。2.6.2算法流程每个粒子的优劣程度根据已定义好的适应度函数来评价，这和被解决的问题相关。下面为PSO算法的算法流程：Step1:初始化粒子群，包括群体规模，每个粒子的位置和速度；Step2计算每个粒子的适应度值；Step3:对每个粒子，用它的适应度值和个体极值Pbest比较，如果较好，则替换pbest；Step4:对每个粒子，用它的适应度值和全局极值gbest比较，如果较好，则替换gbest；Step5:根据公式(2.1)、(2.2)更新粒子的速度和位置；Step6

40、:如果满足结束条件(误差足够好或到达最大循环次数)退出，否则回到Step2。算法的伪代码如下：ForeachparticleDoInitializeparticle;DoForeachparticleCalculatefitnessvalue;Ifthefitnessvalueisbetterthanthebestfitnessvalue(pBest)inhistory;SetcurrentvalueasthenewpBest;ChoosetheparticlewiththebestfitnessvalueofalltheparticlesasthegBest;ForeachparticleC

41、alculateparticlevelocityaccordingequation(2.1);Updateparticlepositionaccordingequation(2.2);Whilemaximumiterationsorminimumcriteriaisnotattained;2.7粒子群优化算法与其他进化算法比较粒子群算法与其他进化算法，如遗传算法、进化策略、进化规划等具有很多共同之处：（1）粒子群算法和其它进化算法相同，都使用“种群”概念，用于表示一组解空间中的个体集合。两者都随机初始化种群，而且都使用适应值来评价系统，而且都根据适应值来进行一定的随机搜索。两个系统都不是保证一

42、定找到最优解。（2）如果将粒子所持有的最好位置也看作种群的组成部分，则粒子群的每一步迭代都可以看作是一种弱化的选择机制。在进化策略算法中，子代与父代竞争，若子代具有更好的适应值，则子代将替换父代，而PSO算法的进化方程式也具有与次类似的机制，其唯一的差别在于，粒子群算法只有当粒子的当前位置与所经历的最好位置相比具有更好的适应值时，其粒子所经历的最好位置才会唯一地被该粒子当前的位置所替代。可见，PSO算法中也隐藏着一定形式的“选择”机制。（3）在遗传算法中存在着交叉（crossover和变异（mutation）操作，粒子群算法中虽然在表面上不具备这样的操作，但在本质上却有相通之处。粒子群算法的速

43、度更新公式（2.1）与实数编码的遗传算法的算术交叉算子很类似。通常，算术交叉算子由两个父代个体的线性组合产生两个子代个体，而在PSO算法的速度更新公式（2.1）中，如果不考虑第一项，也就是带惯性权重的速度项，就可以将公式理解成由两个父代个体产生一个子代个体的算术交叉运算。从另一个角度上看，同样不考虑第一项，速度更新方程也可以看作是一个变异算子，其变异的强度大小取决于个体最好位置和全局最好位置之间的距离，可以把个体最好位置和全局最好位置看作父代，变异就可以看作是由两个父代到子代的变异。至于前面略去的惯性速度项，也可以理解为一种变异的形式，其变异的大小与速度相乘的惯性因子相关，惯性因子越接近1，则

44、变异强度越小；越远离1，则变异强度越大。粒子群算法与其他进化算法的区别在于：（1）通常在进化算法的分析中，人们习惯将每一步迭代计算理解为用新个体（即子代）替换旧个体（即父代）的过程，而粒子群算法的进化迭代过程则是一个自适应过程，粒子的位置不是被新的粒子所代替，而是根据粒子的速度进行自适应变化。因此，粒子群算法与其他进化算法的一个不同点在于：粒子群算法在进化过程中同时保留和利用位置和速度的信息，而其他进化算法仅仅保留和利用位置的信息。（2）如果将粒子群算法中的位置计算公式（2.2）看作为一个变异算子，那么粒子群算法就与进化规划很相似，而不同之处在于，在每一代，粒子群算法中的每个粒子只朝着一些根据

45、群体的经验认为是好的方向飞行，而进化规划是通过一个随机函数变异到任何方向。也就是说，粒子群算法在优化计算过程中执行着一种有“意识”的变异。（3）粒子群算法与其他进化算法的最显著区别在于，粒子群算法将粒子的位置和速度模型化，从而给出了一组显式的进化计算方程。（4）在收敛性方面，GA已经有了较成熟的收敛性分析方法，并且可对收敛速度进行估计；而PSO这方面的研究还比较薄弱。尽管已经有简化确定性版本的收敛性分析，但将确定性向随机性的转化尚需进一步研究。（5）在应用方面，PSO算法主要应用于连续问题，包括神经网络训练和函数优化等，而GA除了连续问题之外，还可应用于离散问题，比如TSP问题、货郎担问题、工

46、作车间调度等。从以上分析中看，基本PSO算法与其他进化算法有相似之处，但同时也具备其它算法不具备的特性，特别的是，PSO算法同时将粒子的位置与速度模型化，并给出了它们的进化方程。2.8粒子群优化算法的改进策略粒子群优化算法的改进可谓层出不穷，这方面的研究非常庞杂，这些改进基于各种不同的策略和方法。但从根本目的来说，都是为了改进粒子群优化算法的两个缺点，其一是粒子群优化算法容易陷入到局部极值点中，导致得不到全局最优解，造成这种现象的原因有两方面，一是待优化函数的性质，有许多测试函数是多峰函数、形状复杂，而粒子群优化算法并不是从理论上严格证明收敛于任何类型函数的全局极值点，因此对于复杂的测试函数，

47、很可能难以得到满意的结果。二是粒子群优化算法在运行时，由于算法的参数设计、或者是粒子数的选择不恰当等原因，导致在计算的过程中，粒子的多样性迅速的消失，造成算法“早熟”现象，从而导致算法不能收敛到全局极值点。这两个因素通常密不可分的纠缠在一起，很难说在一个具体的问题中，到底是那一个因素在起作用，使得算法不能收敛到全局极值点。有比较多的改进是基于这两个方面的因素，对于第一个方面的缺点，有些研究者试图在函数优化的过程中，动态的改变函数的某些全局或局部的形态，使得函数的形状逐渐的变得简单，但同时又不改变函数的全局极值点的性质。比如可以设计一个变换，随着优化过程的进行，使得函数最终由多峰函数变为单峰函数

48、，从而克服此问题。第二个方面的问题通常可以采用如下方法解决，对粒子群的多样性设置某些指标，比如粒子群的熵，随着计算的进行，实时监测这些指标，一旦这些指标超过某个事先设定的临界值，则对整个群体实施某种操作，比如按指定的概率重新初始化，从而改善群体的多样性，克服早熟的问题。其二是粒子群优化算法的收敛速度比较慢。在解决实际问题时，通常需要在一定的时间内达到相应的精度，如果耗费很长的计算时间来得到一个可行解，有时是不值得的。造成这种问题的原因是粒子群优化算法并没有很充分的利用计算过程中得到的信息，在每一步迭代中，仅仅利用了全局最优和个体最优的信息，此外，算法本身没有比较充分的优选机制，以淘汰比较差的待

49、选解，从而导致算法收敛速度较慢。要解决这方面的问题，需要充分的吸收进化算法的优点，在粒子的操作中，加入繁殖、变异和优选算子，以加快算法的收敛速度。另外一个思路就是把粒子群优化算法较强的全局搜索能力与基于梯度算法的较好局部搜索能力相结合，设计一种混合算法，以克服二者的缺点，发挥二者的优点。基于前面的理论分析，本节重点讨论以下几个方面PSO算法的改进策略及其效果：调整惯性权重；引入收缩因子；依据一定的标准调整群体或某些粒子的状态；引入邻域算子、使用新的组织结构、结合进化算法利用选择和杂交机制等。2.8.1 调整惯性权重惯性权重w描述了粒子上一代速度对当前代速度的影响。控制其取值大小可调节PSO算法

50、的全局与局部寻优能力。惯性权重类似模拟退火中的温度，w值较大，全局寻优能力强，局部寻优能力弱，反之，则局部寻优能力增强，而全局寻优能力减弱。由于不同问题对算法的全局或局部搜索能力会有不同要求，所以算法的全局搜索能力和局部搜索能力之间的平衡关系最好可以调整，也就是说惯性权重可以根据不通问题进行自动调整。文献提出自适应调整的线性递减权重(linearlydecreasingweigh)策略，随迭代进行，线性减少w的值，即：W(t)(Wnend)*(TmaxTmax_t)Wend其中，Tmax为最大迭代次数，WiN为初始惯性权重，Wd为进化到最大迭代次数时的惯性权重，通常取Wini0.9,Wend=

51、。必。这使得算法在迭代初期探索能力较强，可以不断搜索新的区域，然后开发能力逐渐增强，使算法在可能最优解周围精细搜索。这是目前使用最广泛的算法形式。然而搜索过程是一个复杂的非线性过程，让W线性过渡的方法并不能正确地反映真实的搜索过程。因而，文献提出了一种用模糊规则动态调整W的方法，通过对当前最好性能评价和当前惯性权重制定相应的隶属度函数和模糊推理规则，确定惯性权重W的增量。实验结果表明，与W线性减小的算法相比，模糊自适应方法有类似的或更好的结果。2.8.2引入收缩因子Clerc提出了收缩因子的概念，描述了一种带收缩因子的粒子群优化算法，其位置和速度更新如下式所描述：Vid=VidC1(Pid-X

52、id)C22(Pgd-Xid)其中，收缩因子/-=,+C242_J申2_4申实验结果表明，与使用惯性权重的粒子群优化算法相比，使用收缩因子的粒子群优化算法有更快的收敛速度。其实只要恰当地选取因子，带收缩因子的粒子群优化算法可被看作是PSO算法的一个特例。2.8.3调整粒子状态量粒子的状态量包括粒子的位置和速度。为了刺激群体持续进化，避免群体的早熟收敛和停滞现象，很多研究者指出可依据一定的标准为整个群体或某些粒子的状态量重新赋值，以维持群体的多样性，使算法可持续进化。文献将自然进化过程中的群体灭绝现象引入粒子群优化算法。该混合算法在粒子的位置和速度更新之后，按照一个预先定义的灭绝间隔重新初始化所

53、有粒子的速度。文献描述了个体层次上的自适应粒子群优化算法，它用一个新的粒子替换不活泼的粒子，来保持群体的多样性。如果非全局最优粒子与全局最优粒子之间适应度差值的绝对值连续小于事先定义的临界常数的次数达到一定值，则该非全局最优粒子就被视为不活泼的粒子，被一个新的粒子替换，替换操作在更新粒子位置和速度之前进行的。文献根据耗散结构的自组织性，提出一种耗散粒子群优化算法。该算法通过附加噪声持续为粒子群引入负熵，使得系统处于远离平衡态的状态，又由于群体中存在内在的非线性相互作用，从而形成自组织耗散结构，使粒子群能够“持续进化”。文献将进化规划中使用的联赛选择方法引入PSO算法。该混合算法根据个体当前位置

54、的适应度，将每一个个体与其它若干个个体相比较，然后依据比较结果对整个群体进行排序，用粒子群中最好一半的当前位置和速度替换最差一半的位置和速度，同时保留每个个体所记忆的个体最好位置。虽然混合PSO算法与基本PSO算法的差异很小，但是选择方法的引入使得混合算法成为一种更具开发力的搜索机制。284引入邻域算子尽管PSO算法能比其他进化算法更快地得到质量相当的解，但当迭代次数增加时，由于不能进行更精确的细部搜索，从而无法提高解的质量。为此，可引入一个变化的邻域算子：在优化的初始阶段，一个粒子的邻域就是它本身；优化代数增加后，邻域逐渐增大，最后将包括所有粒子。此时，PSO算法将采用局部模型，而不是全局模

55、型，并且局部模型的邻域是不断增加的。为定义粒子的邻域，需计算候选粒子与其他所有粒子的距离，其中第i个粒子的距离为disti，而最大距离为max_dist，并定义一个与当前进化代数t有关的分数frac=0.6+3.0t/T。如果frac0.9，且fracAdisti/max_dist，则米用局部模型lbest进行搜索；否则使用全局模型gbest。对SphereRosenbrockRastrigrin和Griewank函数的试验结果显示，该方法平均结果好于标准PSO。惯性权重可对算法探测和开发能力进行调节。实际上，邻域算子的改进也是为了更好地完成此任务。首先，粒子邻域的不断增加可以增加算法探测能力

56、；其次，通过域值的设定，使得全局模型和局部模型得以切换，也使探测和开发能力得以有效调节。2.8.5使用新的组织结构文献使用簇分析改进PSO算法的性能。其具体实现为：首先将整个粒子群划分为几个簇，确定每个簇的中心，然后用个体i的簇中心CLUSI代替或用目前找到的最优个体的簇中心CLUSG代替Pg来进行粒子速度和位置的更新。该文采用带收缩因子的粒子群优化算法进行实验。结果表明，用CLUSI代替Xi可显著改善PSO算法的性能，而用CLUSG代替pg则会降低算法的性能。该文指出上述现象的产生原因在于，簇中心的性能一定优于组成簇的所有个体的平均性能，而比簇中最好个体的性能差。2.8.6结合进化计算利用选

57、择机制的方法PSO算法的搜索过程很大程度上依赖pbest和gbes，它的搜索区域受到pbest和gbest的限制。在通常的进化算法中，选择机制用来选择相对较好的区域和淘汰较差的区域，可以更合理地分配有限的资源。而在一般的粒子群算法中，每个粒子的最优位置的确定相当于隐含了选择机制，因此文献引入了具有明显选择机制的改进粒子群算法，仿真结果表明算法对某些测试函数具有优越性。改进算法将每个个体的适应度，基于当前位置，与k个其它个体进行比较，并记下最差的一个点。群体在用这个记录排序，最高的得分出现在群体头部。算法流程为：(1) 群体选择一个个体。将该个体的适应度与种群中的其它个体的适应度逐一进行比较，如

58、果当前的个体的适应度优于某个个体的适应度，则每次授予该个体一分。对每一个个体重复这一过程。(2) 根据前一步所计算的分数对种群中的个体进行由大到小的排列。(3) 选择种群顶部的一半个体，并对它们进行复制，取代种群底部的一半个体，在此过程中最佳个体的适应度并未改变。对测试函数的实验仿真结果表明，除了个别测试函数外，上述算法的性能超过基本粒子群算法。利用杂交操作的方法Angeline提出了杂交的粒子群算法，粒子群中的粒子被赋予一个杂交概率，这个杂交概率是随机确定的，与粒子的适应值无关。在每次迭代中，依据杂交概率选取指定数量的粒子放入一个池中。池中的粒子随机地两两杂交，产生相同数目的子代粒子，并用子

59、代粒子取代父代粒子，以保持种群的粒子数目不变。经过杂交操作，由亲代个体随机产生了两个新的位置。速率的交叉将两个亲代个体的速率之和的长度规格化，因此只有方向受到影响，数量却没有受到影响。Lovbjerg等人的研究结果表明，繁殖操作降低了单峰值函数的收敛率，因此应用了繁殖算子的PSO比一般的PSO效率更低。但是在拥有多个局部最小值的函数中情况刚好相反。所以应用了繁殖算子的PSO比较先进。实验结果显示，结合进化计算改进的粒子群优化算法的收敛速度比较快，搜索精度也相对比较高，对一类非线性优化问题可以得到满意的结果。不过引入了较多的待调整参数，对使用者的经验有一定要求。2.8.7其他改进策略其他的一些改

60、进的方法主要是提高粒子群算法收敛性能的，其中包括J.Riget提出的一种保证种群多样性的粒子群算法(AttractiveandRepulsiveParticleSwarmOptimizer，简称ARPSO)。该算法引入“吸引”(Attractive)和“扩散”(Repulsive)两个算子，动态地进行调整，以避免粒子群算法所存在的过早收敛问题，从而能更好地提高算法效率。另一个改进算法是有F.vandenBergh提出的具有局部收敛性能的改进粒子群算法GCPSO(GuaranteedConvergenceParticleSwarmOptimizer)。文献提出了一种协同PSO算法，其基本思想是用

61、K个相互独立的粒子群分别在D维的目标搜索空间中的不同维度方向上进行搜索。具体做法是选定划分因子(splitfactor)K和粒子群的粒子数M，将输入的D维向量(粒子的位置及速度向量)划分到K个粒子群。前(DmodK)个粒子群，其粒子的位置及速度向量都是D/K维的；而后K一(DmodK)个粒子群，其粒子的位置及速度向量也是D/K维的。在每一步迭代中，这K个的粒子群相互独立地进行状态更新，粒子群之间不共享信息。计算适应值时，将每个粒子群中最优粒子的位置向量拼接起来，组成D维向量并代入适应函数计算适应值。例如，考虑有24个自变量的优化问题，即D=24。如果选取M=10，K=5，那么每个粒子的位置及速

62、度向量的维数就是D/K=5。这种协同PSO算法有明显的“启动延迟”(startupdelay)现象，在迭代初期，适应值下降缓慢，换言之，收敛速度慢。不过这种协同PSO算法因为实际上采用的是局部学习策略，因此比基本PSO算法更易跳出局部极小点，达到较高的收敛精度。对于具体的优化问题，往往存在这样的情况，一些普适性算法，比如遗传算法、模拟退火，它们的全局收敛性己经在理论上得到严格证明，然而在实际应用中，对某些函数效果不是太好，或者速度太慢。但是一些专门为某类特定问题设计的特定算法，比如专门为优化连续、可微的单峰函数设计的梯度算法，可能收敛速度很快，但是这类算法对于不符合上述前提条件的待优化函数，效

63、果通常不好。所以，算法的通用性和专用性之间通常存在着矛盾。现实世界是复杂多变的，在解决实际问题时，通常很少只依赖一种手段。必须根据问题的特点，对不同的问题、在不同的阶段，灵活的采用适合于问题的不同算法。理论研究的问题通常是去掉了实际问题中很多复杂因素后的简化模型，因此，所用的方法和所得的结果也仅能看成是一种理想情形。有许多实际的优化问题常常是通过经验知识或理论分析得到一个可行范围，然后采用算法搜寻得到更精细的结果，这样作的目的一是为了提高收敛速度，而是为了节约计算的成本。因此，除了算法本身的性能之外，如何在应用算法时与实际问题的特点紧密结合，适当的选择某种专用性或通用性算法，或者是二者的结合，

64、是一问题的另一方面。3离散粒子群优化算法由于标准粒子群算法只能用于连续空间，然而许多实际问题都是描述为组合优化问题，所以Kennedy和Eberhart提出了一种二进制离散粒子群算法(DPSO)。离散二进制PSO算法的提出有效地解决了离散空间的优化问题。DPSO算法中，粒子的位置每一维只有0或1两种状态，速度更新的方法与连续PSO类似，位置的更新则取决于由粒子速度决定的状态转移概率，速度大于一定的数值，粒子取1的可能性越大，反之越小。而且这个阈值要位于0,1范围之内。sigmoid函数能够满足这个要求，所以速度转换米用sigmoid函数。其中vid要设定一个上下变化幅值，保证sigmoid(v

65、id)值不能太靠近0.0或1.0,这样就增大改变比特位置的机会，不会陷入局部极值。离散粒子群算法调整公式如下：idWdciri(Pid-xid)c2r2(Pgd-Xid)，(5.1)id1,当凡:sigmoidM),(5.2)0,当?idsigmoid(%)其中凡是一个0.0,1.0之间的随机数，sigmoid仏)i1exp(-Vid)，其它参数类似基本PSO。(1)函数f1(RastrigrinFunction):n2f(x)=Xj10cos(2冗x)+10,X5.12izlminf(x)=f(0,0,，0)=0Rastrigrin函数为多峰函数，当Xi=o时达到全局极小点，在S=Xi-5.12,5.12,i=1,2,，n范围内大约存在10n个局部极小点。几种算法的计算结果见表3.1。表3.1Rastrigrin函数的平均适应