粒子群算法综述

粒子群算法综述【摘要】：粒子群算法(pso)是一种新兴的基于群体智能的启发式全局搜索算法，具有易理解、易实现、全局搜索能力强等特点，倍受科学与工程领域的广泛关注，已得到广泛研究和应用。为了进一步推广应用粒子群算法并为深入研究该算法提供相关资料，本文对目前国内外研究现状进行了全面分析，在论述粒子群算法基本思想的基础上，围绕pso的运算过程、特点、改进方式与应用等方面进行了全面综述，并给出了未来的研究方向展望。【关键词】：粒子群算法优化综述优化理论的研究一直是一个非常活跃的研究领域。它所研究的问题是在多方案中寻求最优方案。人们关于优化问题的研究工作，随着历史的发展不断深入，对人类的发展起到了重要的推动作用。但是，任何科学的进步都受到历史条件的限制，直到二十世纪中期，由于高速数字计算机日益广泛应用，使优化技术不仅成为迫切需要，而且有了求解的有力工具。因此，优化理论和算法迅速发展起来，形成一门新的学科。至今已出现线性规划、整数规划、非线性规划、几何规划、动态规划、随机规划、网络流等许多分支。这些优化技术在诸多工程领域得到了迅速推广和应用，如系统控制、人工智能、生产调度等。随着人类生存空间的扩大，以及认识世界和改造世界范围的拓宽，常规优化法如牛顿法、车辆梯度法、模式搜索法、单纯形法等已经无法处理人们所面的复杂问题，因此高效的优化算法成为科学工作者的研究目标之一。1.粒子群算法的背景粒子群算法(particleswarmoptimization，pso)是一种新兴的演化算法。该算法是由j.kennedy和r.c.eberhart于1995年提出的一种基于群智能的随机优化算法。这类算法的仿生基点是：群集动物(如蚂蚁、鸟、鱼等)通过群聚而有效的觅食和逃避追捕。在这类群体的动物中，每个个体的行为是建立在群体行为的基础之上的，即在整个群体中信息是共享的，而且在个体之间存在着信息的交换与协作。如在蚁群中，当每个个体发现食物之后，它将通过接触或化学信号来招募同伴，使整个群落找到食源；在鸟群的飞行中，每只鸟在初始状态下处于随机位置，且朝各个方向随机飞行，但随着时间推移，这些初始处于随机状态的鸟通过相互学习(相互跟踪)组织的聚集成一个个小的群落，并以相同的速度朝着相同的方向飞行，最终整个群落聚集在同一位置──食源。这些群集动物所表现的智能常称为“群体智能”，它可表述为：一组相互之间可以进行直接通讯或间接通讯(通过改变局部环境)的主体，能够通过合作对问题进行分布求解。换言之，一组无智能的主体通过合作表现出智能行为特征。粒子群算法就是以模拟鸟的群集智能为特征，以求解连续变量优化问题为背景的一种优化算法。因其概念简单、参数较少、易于实现等特点，自提出以来已经受到国内外研究者的高度重视并被广泛应用于许多领域。2.国内外研究现状粒子群算法一经提出就吸引了各国学者的注意，各种关于pso算法的理论与应用研究的成果不断涌现，有力地推动了pso算法的研究。研究主要从下面两个方向开展：一个是从具体优化的应用着手，根据具体情况，对算法进行改进，以满足应用要求；另外一个是粒子群算法的理论方面着手，分析算法的收敛性能，提高算法的优化性。3.粒子群算法概述3.1粒子群算法的基本思想粒子群算法是基于群体的演化算法。reynolds对鸟群飞行的研究发现，鸟仅仅是追踪它有限数量的邻居，但最终的整体结果是整个鸟群好像在一个中心的控制之下，即复杂的全局行为是由简单规则的相互作用引起的。pso即源于对鸟群捕食行为的研究，一群鸟在随机搜寻食物，如果这个区域里只有一块食物，那么找到食物的最简单有效的策略就是搜寻目前离食物最近的鸟的周围区域。pso就是从这种模型中得到启示而产生的，并用于解决优化问题。另外，人们通常是以他们自己及他人的经验作为决策的依据，这就构成了pso的基本概念。算法采用速度一位置搜索模型，每个粒子代表解空间的一个候选解，解的优劣程度由适应度函数决定。速度vi=(vi1，vi2，…，vid)决定粒子在搜索空间迭代时的位移。其中，适应度函数根据优化目标定义。粒子群算法随机初始化为一群粒子，其中第i个粒子在d维解空间的位置表示为xi=(xi1，xi2，…，xin)。与进化算法比较，粒子群算法保留了基于种群的全局搜索策略，但是其采用的速度一位置模型，操作简单，避免了复杂的遗传操作。它特有的记忆使其可以动态跟踪当前整个种群的最优粒子。3.2粒子群算法的运算过程粒子群算法的主要运算过程描述如下:①种群初始化。随机生成m个个体作为初始群体p(0)。由于粒子群群体为运算对象，所以我们必须为粒子群操作准备一个由若干初始解组成群体。②个体评价(适应度评价)。计算群体中各个个体的适应度。粒子群算法在搜索进化过程中一般不需要其他外部信息，仅用评估函数值来评价个体或优劣，并作为以后粒子群操作的依据。评估函数值又称为适应度。③根据图1－1、图1－2更新粒子群的速度和位置。这是整个粒子群最关键的一步，种群的“个体学习”和“社会学习”都在这一步实现。④终止条件判断。若满足终止条件(达到最大迭代次数或满足最小)，则以进化过程中所得到的具有最大适应度的个体作为最优解输出，终止计算；否则，转至第一步，继续迭代。3.3粒子群算法的特点粒子群算法有很强的鲁棒性，与传统的优化技术相比，它采用了许多独特的方法和技术。①传统的优化算法都是从一个初始点出发，再逐步迭代以求最优解。pso则不然，它是以一个群体，多点同时出发经过不断迭代求得满意解。②传统的优化算法不仅需要利用目标函数值，而且往往需要目标函数的导数值等其它一些辅助信息才能确定搜索方向。粒子群算法仅使用由目标函数值变换来的适应度函数值就可以确定进一步的搜索方向和搜索范围，无需目标函数的导数值等其他一些辅助信息。③传统的优化算法大都采用确定性的搜索方法，一个点到另一个点的搜索转移有确定的转移关系和转移方向，这种确定性往往使得搜索可能永远达不到最优点，因而限制了算法的应用范围。而粒子群算法属于一种群体搜索方法，具有潜在的自适应性。4.粒子群算法的几种改进方式现在的粒子群算法大都在收敛速度与摆脱局部最优这两个方面下功夫，其实这又是两个矛盾的方面。如何平衡这两方面，各国研究人员相继提出了各种改进措施，概括起来主要有以下四点：变更公式法、分群方法、混合算法和扰动方法。5.粒子群算法的应用kennedy和eberhart首先将pso算法应用到非线性函数优化及神经网络的训练。在随后的应用中，eberhart等又将粒子群算法与神经网络进行结合用于分析人的颤抖。此后pso算法的应用领域不断扩大，如将pso算法应用到各类连续问题和离散问题的参数优化，包括模糊控制器的设计、机器人路径规划和模式识别等；将离散pso算法应用到0-1规划问题及带有排序关系的优化问题，包括背包问题、电网机组控制、数据挖掘、tsp问题、vrp问题、job-shop及资源分配等。如wang等将量子理论应用到粒子群算法中，提出了离散化量子群算法，对背包问题进行设计和求解，得到较满意的结果。此后，吕强等提出了基于信息素机制的离散粒子群算法，利用蚁群的信息素机制来设计0-1背包问题，也取得不错的效果；ting使用混合粒子群算法处理机组的开关控制并求解经济负载分配问题，效果理想；elon利用bpso算法解决了生物信息数据集中的属性选择问题；clerc设计的tsp-dpso算法求解14个城市的tsp问题时，只搜索了问题空间的0.064%就找到了最优值。此后肖健梅对粒子的速度分三次进行更新，每次都以更新后的结果代替原式中的位置进行比较，提高了算法求解tsp问题的计算速度和寻优能力；对于车辆路径问题，学者们大都通过近似取整的方法，将粒子连续位置空间映射到离散排序空间，再通过粒子在连续空间的位置迁移引发离散状态的变化；cagnina等用随机键表示法表示粒子的位置解决单一机器调度问题；tasgetiren也用相同的方式把pso算法应用于排列流水作业调度及单一机器人调度问题上。除此之外，pso算法的应用包括系统设计、多目标优化、自动目标检测、时频分析等。6.总结粒子群算法(pso)是一种新兴的基于群体智能的启发式全局随机搜索算法，具有易理解、易实现、全局搜索能力强等特点，为各个领域的研究人员提供了一种有效的全局优化技术。本文对pso的基本思想、运算过程、特点、改进方式与应用等方面进行了全面综述。在科学与工程实践领域，关心pso的读者的共同兴趣所在是pso本身，即“pso是什么”和“有些什么样的改进形式”，而“用pso怎样解决某个具体问题”则依赖于相应领域的专业知识，为了让尽可能多的国内读者从中受益而不局限于具体的工作背景，综述内容侧重于对pso基本思想、算法改进方式，特别是相关国外国内发展现状进行分析，pso应用列出了典型的一些主要应用对象。参考文献：[1]《最优化理论与算法》[m]，陈宝林，清华大学出版社，2005。[2]《智能优化算法及其应用》[m]，王凌，清华大学出版社，2001。[3]《粒子群算法一理论、应用与软件实现》[m]，王小平，曹立明，西安交通大学出版社，2002。[4]《粒子群优化算法的理论与实践》[j]，张丽平，浙江大学学报，2005。[5]《粒子群优化算法的分析与改进》[j]，张丽军，俞欢军，陈德钊等，信息与控制，2004。[6]《多粒子群协同优化算法》[j]，李爱国，复旦学报，2004。