本科毕业论文-群智能优化算法在机器人路径规划中的应用.docx

西 安 邮 电 大 学 毕 业 设 计（论 文）论文题目： 群智能优化算法在机器人路径规划中的应用 院 （系）： 自动化学院 专 业： 智能科学与技术 班 级： 学生姓名： 导师姓名： 职称： 讲师 起止时间： 2012.12.182013.6.20目录摘要IABSTRACTII引言11绪论41.1选题的背景和选题的意义41.2应用领域51.3该选题在相应学科领域中的发展进程和研究方向61.4电子资源61.5主要工作61.6研究内容的创新点72群智能优化算法粒子群优化算法(PSO)82.1粒子群优化算法(PSO)的思想起源82.2算法原理92.3粒子群优化算法(PSO)的流程112.3.1基本粒子群算法流程图132.4基本粒子群算法Matlab主要代码及效果图142.4.1代码运行效果图:152.5特点与不足162.6粒子群算法的研究现状173机器人路径规划183.1路径规划的定义183.2机器人路径规划的思想起源183.3移动机器人路径规划的原理203.3.1基本原理203.3.2相关定义213.3.3机器人位置编码方法213.3.4初始种群的产生223.4路径规划的规划流程233.5路径规划所要达到的目的233.6路径规划的问题描述和建模243.6.1建立移动机器人移动的环境模型243.6.2建立环境模型的主要代码：293.6.3路径搜索方法304群智能优化算法之粒子群优化算法在机器人路径规划中的具体应用314.1问题描述与建模314.2算法步骤324.3算法流程图344.4粒子群算法与机器人路径规划的结合实现354.4.1优化算法的适应度函数的确定方式354.4.2参数的选择354.4.3粒子位置和速度更新策略354.5粒子群优化算法的改进364.6仿真效果图385结论406致谢41参考文献42附录4347摘要智能优化不仅是学术研究的重要方面也是工程计算中的重要问题之一。其原理就是在达到必要的约束条件下，来寻求一组有效的参数值使得系统中的有些性能指标达到最值（最小值或是最大值），这就是我们所说的优化思想。在我们的生活中到处都遍及优化的思想，例如：经济、管理、工程、社会、科学研究等各个方面，遍及人类生活的方方面面，那么它的重要性我们就众所周知了5。人们把群居昆虫的集体行为称作“群智能”（“群体智能”、“群集智能”、“集群智能”等），群智能作为一种新兴的演化计算技术已成为研究焦点，其模拟社会性动物的各种群体行为，利用群体中的个体之间的信息交互和合作来实现寻优的目的，它与人工生命，特别是进化策略以及遗传算法有着极为特殊的关系。其中最著名的群智能优化算法有：蚁群算法和粒子群算法。本文介绍了群智能算法之粒子群算法,粒子群优化是一种新兴的基于群体智能的启发式全局搜索算法，群体中的每一个微粒代表待解决问题的一个候选解, 算法通过粒子间信息素的交互作用发现复杂搜索空间中的最优区域，它具有易理解、易实现、全局搜索能力强等特点，倍受科学与工程领域的广泛关注，已经成为发展最快的智能优化算法之一。路径规划是自主机器人导航的一个重要问题。信息融合技术作为一门新兴的实践应用技术，为各领域的信息处理以及决策支持提供了可靠的手段，也是实现机器人智能化的关键技术之一。论文介绍了粒子群优化算法的基本原理，通过对粒子群算法的改进、优化，采用Matlab语言对典型的机器人路径规划实例进行编程仿真。同时本论文采取了栅格法对路径规划进行环境建模，将现实生活中的路径抽象成为坐标图中的路径，这样做的目的有助于反复真软件的仿真以及观测者的观测。概率搜索算法有很多种，而群集智能算法就是其中一种, 其约束条件不是集中控制的,而且整个问题的求解结果不会受个别粒子的影响, 并且有很强的鲁棒性的优点, 因此具有很显著的的优点尤其是在机器人全局路径规划中。通过仿真结果就可以测得粒子群算法的有效性, 通过仿真的效果，我们发现它解决了机器人路径规划中的很多不合理规划的问题，所以它可以成为机器人路径规划的一个较好的方法。关键词：群智能算法、粒子群算法、matlab、优化、启发式、搜索算法、栅格法、环境建模、机器人路径规划。AbstractIntelligent optimization is not only an important aspect of academic research in engineering calculations is one of the important issues. Its principle is to achieve the necessary constraints, to seek a set of valid parameter values so that system performance indicators to achieve some of the best value (minimum or maximum), and this is what we call the idea of optimization. In our lives everywhere throughout the optimization ideas, such as: economics, management, engineering, social, scientific research and other aspects, throughout all aspects of human life, then its important that we all know of 5. People to the collective behavior of social insects called swarm intelligence (swarm intelligence, swarm intelligence, swarm intelligence and so on), swarm intelligence as an emerging computing technology evolution has become a research focus, its analog social behavior of various groups of animals, the use of groups in the information exchange between individuals and collaboration to achieve optimization purposes, it is with artificial life, especially the evolution strategy and genetic algorithm has a very special relationship. The most famous of swarm intelligence optimization algorithms: ant colony algorithm and particle swarm algorithm. This article describes the swarm intelligence of particle swarm optimization algorithm, particle swarm optimization is a new heuristic based global search swarm intelligence algorithm, groups of each particle represents a problem to be solved a candidate solution, the algorithm through pheromone particles complex interactions find the optimum area search space, which are easy to understand, easy to implement, global search ability and other characteristics, much of the broad field of science and engineering concern, has become the fastest growing intelligent optimization algorithm. Autonomous robot navigation path planning is an important issue. Information fusion technology as a practical application of emerging technologies for information processing in various fields as well as decision support provides a reliable means for achieving one of the key technologies of intelligent robots. This paper introduces the basic particle swarm optimization principle, through the particle swarm algorithm, optimization, using Matlab language typical instance of robot path planning simulation programming. Meanwhile, the paper took a grid method to path planning for environmental modeling, real-life path will become abstract plot the path, the purpose of doing so really helps repeated simulation software and the observers observation. There are many probabilistic search algorithm, and is one of swarm intelligence algorithm, its constraints are not centrally controlled, and the whole problem solving results are not affected by the impact of individual particles, and has the advantages of robustness, so has a very significant advantage especially in robot global path planning. The simulation results can be measured by the effectiveness of PSO, the simulation results, we found that it solves a lot of robot path planning unreasonable planning issues, so it can become a better robot path planning method.Keywords: swarm intelligence algorithm, particle swarm optimization, matlab, optimization, heuristic search algorithm, grid method, environmental modeling, robot path planning.引言优化是一个古老的课题，现在在我们的生活学习有许多可以解决优化问题的数学方法，但是随着社会以及智能技术的发展和进步，已经有很多方法不能满足我们学习和生活的需要，所以为了解决这种很现实的问题，通过人们的努力，研究出了仿生优化算法。仿生优化算法是一种以仿生学理论为基础的智能优化算法，其原理是以模拟个体动物种群的运动来解决智能优化的问题。在我们的现实生活中，我们每天努力的工作是为了追求更好的生活，然而面临强大的工作压力，繁重的工作量，我们该如何解决呢？学生为了取得好的学习成绩，要不断的完善学习方法，是学习效率达到最优；老师为了学生更好地接受课堂上所讲的内容要不断的探索好的授课方式；工作人员为了更好地完成老板所下达的任务，要不断改进工作方式，是的工作效率达到最好；而老板为了获得更丰厚的利润要不断的改进经营方式、运营方式，最终使得公司的体制达到一个比较好的状态；生产车间的工人为了提高生产效率，要不断的改进生产线等等这些我们身边发生的事情。以上这些事例足以说明不管我们的工作是什么，我们每个人做每一件事情的时候都会思考同一个问题，怎样做最优。好几年以前，在美国的金融领域，它影响了全球的经济发展。众所周知，一直处于领先地位的美国金融的崩溃很清楚告诉人们，以前人们大多认为的全世界最优秀的美国经济系统也不是那么完善的，那么到底什么样的系统才是更加完美优秀的呢？这依然是人们要解决的问题，所以我们就需要不断的寻优。但是针对非常复杂的经济系统，寻找那样一条接近完美的道路和方法可能永远都不会有尽头。寻优是我们大家每个人所要追求的梦想，它是和人类追求美好生活的梦想相一致的先天本能。自从出现人类智慧之后，人类想要寻找最优的策略而且这种想法一直没有停止过。尤其是近现代社会，由于生产力的高度发展，人类在各个生产领域对于寻优的要求变得越来越普遍。比如，在一个自动控制系统的运行过程中，怎样选择PID调节器的控制参数P、I以及D，以致整个系统的超调量小于等于20的条件下，系统的反应时间最短？对于生产、安排的方面，怎样以现有的人力物力，优化生产配置的产能，以使利润可以取得最大化？又如，对于金融投资活动，怎样评估获利与风险之间的关系以及资金的合理化应用，使投资活动既能尽可能规避风险，又能保证存在一定比例的获利空间？国家工业化生产的过程中，如何发展以致在工业化生产和环境保护方面获得尽可能的平衡？寻优的优点取决于，在不改变现有条件的现状下，通过选择一些更好的方案和计算方法，来尽最大可能的提高目标的达成效率和提高生产效率。所以，采取优化的策略对于达成目标的效果常常是显而易见的，同时也有一些人称智能优化为“不用投资的技术改造”。一直以来，人们经常为了取得最优的方案而进行不懈的努力和探索，就是渴望能够发现行之有效并且完整的求解最优策略的方法。所以，我们把寻求最优化解决方案的方法称为最优化方法或是智能优化方法。在自然界中，大多数生物体通常都具有所谓的群集行为方式，但是探索自然界生物的群体行为就是人工生命研究领域一项重要的工作，使得在计算机上构建群体的环境模型。一般来说，群体行为存在几条简单的规则来进行种群的建模，例如：鸟群、鱼群、蚁群等。虽然每个单独的个体都具有比较简单的行为准则，但是每个群体的运行行为却相当复杂。仿生学是在二十世纪中后期被人们创建的，大多数人们都是以模仿生物的研究为出发点，所以人们也创造了非常多的具有新功能的实际生活所需的具有实用价值的工具软件。在那样的科研环境下，群体性动物(如蜂群、鸟群、蚁群等动物)的身体组织的行为得到了人们的普遍关注，多数研究人员对上述的组织行为进行数学建模而且通过计算机计算机对其进行仿真研究，所以，由此就产生了群智能算法这一概念。人们惊奇地发现，群体性动物的不同之处在于：能力非常局限、而且个体行为非常的简单，但是它们在一起协同工作时，效果就完全不同了，而且会出现“涌现”同时它们的行为特征变得非常的复杂，但是这种复杂的行为并不是人们想像的那样是所有个体行为的叠加。譬如，每个能力有限的蚂蚁个体组合成蚁群，它们可以完成集体捕食、筑巢等等非常复杂的行为特征。就像当小鱼遭到其他动物袭击的时候，它们就经常会非常快速的抱成一团并且不停止的绕中心运行，它们这样做的目的就是一方面抵御敌人的攻击，另一方面将总损失降至最小化。在目前来看，我们知道群智能算法现有了一些实际的应用，大概有三个不同的研究方向：群智能环境模型的研究，新的模型的生成，并且实现生成的模型，将其应用到实际生活中是一个方面；另一个方面是研究分布式装置，就是利用一种群智能算法特有的分布式的特点，通过结合机器人的先进设备，生产和设计一些具有自组织能力的设备；最后一个就是以群智能优化算法的应用和研究为基础。目前，已经出现了一些基于群智能系统的优化方法和策略。其中最著名的群智能优化算法有：蚁群算法(ACO,Ant Colony Optimization)和粒子群算法（PSO,Particle Swarm Optimization）。在机器人学中路径规划是一个比较重要的研究课题。目前路径规划的方法分为局部路径规划方法和全局路径规划方法两个方向。局部规划方法以人工势场法的直角坐标空间为主要的方法，关节式机械手和移动式机器人是路径规划的两个不同的研究方向；然而全局路径规划方法主要以拓扑法和构形空间的几何法为主要的研究方向；一般来说，全局路径规划方法拥有更多的自由维度，但是局部的路径规划则有更大的的作业范围。以最简易的方法来说，机器人的路径规划问题可以这样来定义：设X为一机器人规划系统，这个规划系统有k个自由度，并且假设X运行在一个二维环境空间中，在一种空间环境中，而且该空间中环境信息即障碍物都已经被机器人感知，此时机器人能够做无碰撞运动。因此，针对X的路径规划问题可以这样认为：在已知的环境空间中，给定X一个初始位置Z1和一个目标位置Z2，以及一系列的障碍物，此时机器人应该搜寻一条从起始点到目标点、连续的无碰撞的最佳路径，假设存在这样的路径，则规划出满足条件的这样一条运动路径。不知道大家有没有听说过“汽车白车身焊接机器人路径规划”这个案例，自车身焊接过程中，机器人固定在白车身两侧，采用机器人手持焊钳、工件静止不动的焊接方式。各工位的零件同步移动，无交义或回流，没有人工干预。在焊接机器人工作过程中，焊枪从原始位置出发，途经各个焊点，最终回到原始位置，完成一个工作循环。那么大家有没有想过，倘若这个循环过程我们能对机器人的移动路径进行一个更全面的优化，让它可以在一个最优路径上工作，那么是不是可以解决汽车白车身焊接机器人路径规划中存在的不合理问题，进而有效的提高生产效率呢？这是我们值得思考的问题，本论文将通过对群智能算法在机器人路径规划中的应用展开分析，运用matlab仿真软件对结果进行仿真展示，最终说明群智能算法对机器人路径规划所起的关键性作用。1绪论1.1选题的背景和选题的意义随着经济的发展，科学技术也有了巨大的改善，人们的生活水平也发生了翻天覆地的改变。不管是国家的发展还是人民生活的发展不再仅仅是追求最基本的满足，不再是仅仅只追求表面化的经济数据，社会在发展人们的思想观念也在发展，人们渴望更优秀的科研技术来满足他们精神生活和物质生活的需要。那么，怎样使得工作效率和生产效率的提高呢？我们不然而然的就想到了优化这个词语。所以最优化这个词语成为人们的社会生活中经常使用的术语，它体现出了人们社会活动的非常常见的现象，可以用这样一句话总结最优化这个术语：它就是在人力、物力、财力不变条件况下，怎样可以使得资源的利用率最大，而且获得利润最大。最优化实际上是以数学技术为基础的一门技术，一直以来人们为了满足生活的需要不断地对最优化进行不断地努力和探索，在很久以前，就有科学家发明了具有优化思想的微积分、以梯度下降法解决无约束优化问题。早起有一位苏联数学家康托罗维奇发表了一篇文章名为生产组织与计划中的数学方法，这篇文章首次提出了解决生产计划优化决策的线性规划问题的解乘数法。虽然人类不断地对最优化进行探索，但是有很多限制因素的存在，所以，一直都没有很大的突破。但是随着计算科学的不断发展，人们对于最优化的有了很迫切的需要，计算机成为很有效的求解工具，一些超大规模的问题得到了一个很好地解决，从此优化理论的应用得到了广泛的应用。但是仅仅通过计算机这样的计算工具是不能够解决所有复杂的问题，所以人们受到达尔文进化论思想和自然现象的启发，科学家们研究出了一些群智能优化算法，如：粒子群算法、蚁群算法、差分进化算法、人工免疫算法。这种算法不需要目标函数和约束的连续性与凸性、可导、可行域连通，即使没有解析表达式也可以进行优化，而且这些算法在计算复杂方面也表现除了相当大的优势，为优化思想理论的发展提供了一个很有利的平台。所以对于粒子群算法（PSO），每年有大量的论文的涌现都是关于粒子群算法的，这足以说明它依然是群智能算法研究的一个热点，当然这也是因为它所具有的与其他算法不同的优势所产生的结果。移动机器人在存在障碍物的环境中遵循一定的评价标准(如行走路径最短，工作代价最小, 行走所需时间最短等标准),搜寻一条从所给起点到达目标终点的无碰撞路径，这就是移动机器人路径规划技术。移动机器人路径规划的方式有很多种，在此我介绍两种:一种是基于算法的不同,分为智能路径规划和传统路径规划。而传统路径规划是以图论为思想的,它首先要建立几何模型通过一定的方式,来对空间存在的所有路径的搜索,有链接图法、栅格法、图搜索法、动态路径规划算法等等；动态路径规划是一种优化算法，它是对人工智能的深入不断深入研究而发展起来的,其中包含神经网络法、模糊逻辑法、遗传算法和现在非常热门的算法，如免疫算法、蚁群算法、蜂群算法、粒子群算法等等，智能算法能够对人或者动物的行为和经验进行模仿,其良好的自组织学习能力和非线性逼近能力使得具有很广泛的应用范围；另一种是通过对认知程度和环境的规划体,分为基于已知环境模型的全局机器人路径规划方法和基于传感器信息的局部机器人路径规划方法。其中机器人局部的路径规划方法,其又被称为在线的或是动态的机器人路径规划方法,其中的作业环境部分或完全已知或完全未知或部分已知,有: 蚁群智能算法、粒子群智能算法、人工势场算法和免疫算法以及模糊逻辑算法等方法。而机器人全局路径规划方法,也被称为离线或静态规划路径,有完全已知作业的环境信息,有:可视图法、栅格法、概率路径图法、链接图法、拓扑法等方法。基于栅格法、几何构造的方法、人工势场法、智能化路径规划方法是机器人路径规划的常用方法。最优化技术我们的日常生活中的应用带来了巨大的社会效益和经济效益，基于大量的实践效果表明，在相同的人力、物力、财力的条件下，通过优化技术处理过的，对系统效率的提高、能耗的降低和资源最高效率的使用等都具有明显的效果，而且这种优势随着群体规模的不断增大而变得越来越显著。选这个论文题目进行研究的目的就是：首先，想让大家了解群智能优化算法在实践中的应用，群智能算法的特点、分类及应用领域；其次想让大家了解机器人路径规划应用现状，通过将群智能算法与机器人路径规划的结合来解决路径规划中所存在的问题，最终使得机器人给人类带来的利益达到最大化，提高机器人的工作效率，使机器人工作的路径最优。让大家充分了解机器人的路径是可以通过一种群智能算法来优化的。我们不仅仅是让机器人沿着一条路径来移动，而是要让机器人不断地搜寻最佳路径，最终确定出一条最优路径来完成任务。因此，在我看来研究优化算法对于实际生活具有很重大的意义，对于节约资源也有很大的意义。1.2应用领域该选题具有很大的应用范围内，它对人们的生活、工作都有很大的启发意义。近几年来，PSO算法得到了快速的发展，它不仅在移动机器人路径规划中有很大的用途，也在化工、农业、金融、国防、交通、通信等许多领域得到了很大的应用。在上述生活和生产领域，最优化已经让很多厂家和国家感受到了其明显的优势。实际工业应用有：训练人工神经网络、解决多目标优化问题、求解带有约束满足的问题、电力系统、滤波器设计、自动控制、数据聚类、模式识别与图像处理、化工、机械、通信、机器人、经济、生物信息、医学、任务分配、TSP等等。1.3该选题在相应学科领域中的发展进程和研究方向群集智能的理论与方法不仅是对复杂系统内在运行机制进行研究和仿真的一种重要途径和手段，而且现有的群集智能模型和算法已经广泛应用于许多自然科学与工程科学领域，显示出强大的优势和潜力。本论文主要分析的是粒子群优化算法的应用，以它当前的发展状况来说，我们熟知的有基于粒子群优化算法的无人机航迹规划、基于粒子群优化算法的机器人最短路径规划、基于群智能算法的CDMA多用户检测方法研究、基于粒子群优化算法的集群调度策略研究等等，这些研究成果足以说明其现在的发展状况和研究方向。 1.4电子资源身处信息和网络时代的我们是幸运的，丰富的电子资源能让我们受益匪浅。如果想较快地对PSO有一个比较全面的了解，借助网络空间的电子资源无疑是不二之选。对一些初学者而言，哪里能下载得到PSO的源程序，是他们很关心的话题；即使对一些资深的读者，为了验证自己提出的新算法或改进算法，如果能找到高级别国际期刊或会议上最近提出的算法源程序，那也是事半功倍的美事。这里介绍当今PSO研究领域较有影响的一个网址：http:/clerc.maurice.free.fr/pso/该主页主要介绍Maurice Clerc博士带领的PSO研究小组的研究成果。除了从中可以得到他们近几年公开发表的相关文献和源代码，还可以下载一些未公开发表的文章。这些未公开发表的文章往往是Maurice Clerc博士的一些设想，而且在不断更新，如“Back to random topology”、“Initialisations for particle swarm optimization”、“Some ideas about PSO” 对PSO研究人员很有启发，以及像中国知网、万方这种大的学习网站都是为我们可以学习的地方。所以对于参考资料的查找我们完全可以通过网络来完成，其实这项工作就能反映出我们搜集整合信息的能力，面对大量的电子资源，我们应该如何利用呢，我们不能盲目搜寻资料，我们应该有目的寻找对我们有用的信息，这样才能达到事半功倍的效果。 1.5主要工作本论文中我们既然要研究群智能优化算法以及机器人路径规划，那么我们最主要的工作有两方面。一方面，我们要很清楚粒子群算法的工作原理以及如何最实际问题进行优化的以及我们应该怎样对基本粒子群算法进行优化，使其精度最高、效率最大；另一方面，既然我们要研究路径规划，那么我们就需要对机器人运行的环境进行模拟，即我们首先要解决环境建模的问题，同时在环境建模的基础上对机器人的路径进行规划。所以我有以下工作要做：首先，要高效率的搜集有关群智能优化算法的各种算法研究其实现原理以及如何实现、如何使用，掌握粒子群优化算法应如何作用到机器人的路径规划中；其次，掌握机器人路径规划的常用方法，最终选择一种规划方法进行深入研究，机器人路径规划关系到一个机器人的工作效率问题，路径规划实际上就是在原有路径的基础上再对机器人的路径进行更好的规划，在不断的实验后，选择最优路径；再次，是最重要的一步，就是我们如何将粒子群优化算法与机器人路径规划连接起来；最后，在完成了以上工作后，我们应该对其结果进行仿真，这就要用到matlab仿真软件，将仿真效果图展示出来，看其是否达到预定的效果。1.6研究内容的创新点该篇论文我主要是环绕粒子群算法的优化以及路径规划来完成的。在我看来，本篇论文有三个创新点：1） 我在群智能众多算法中选择了粒子群算法，因为我发现粒子群算法思想简单，易理解，易实现，而且还可以与其他算法，例如遗传算法结合使用，提高优化效率，该篇论文我就采用了粒子群算法和遗传算法进行融合得到了一种混合粒子群优化算法对机器人路径进行规划；2） 在路径规划方面，我首先对机器人路径进行了环境建模的工作，环境建模的思路我是受到一种根据权值求取最短路径的启发，最终选择栅格法对机器人环境建摸，对栅格图进行规划，设置规则，设置路径的起点与终点，以及路径中的障碍物。同时利用搜索算法dijkstra产生初始路径，最终我根据粒子群优化算法对所产生的初始路径进行选择，不断地迭代最终产生一条既能避开障碍物又长度最短的路径。2粒子群优化算法2.1粒子群优概述群居昆虫以集体的力量，进行觅食、御敌、筑巢的能力。这种由于个体之间以及个体与环境之间交互而使群体所表现出来的智能，就称之为群智能。粒子群算法是一种仿生优化算法，它是通过模拟鸟类群体的捕食行为，其中每只鸟都代表模拟中的一个粒子，这种优化算法是：设想有一块每个小鸟都想吃到的食物在一片未知的区域内(即最优化问题中解的位置)，并且要求每只鸟(即个体粒子)都不知道食物的精确位置，但是在这种情况下，它们每个个体是知道它们自己的具体位置的，并且它们每一个个体都有能力判断，它们的位置是不是食物所在的位置以及它们现在离食物的距离，此外它们还知道群体中别的鸟的大体位置，所以我们大家肯定想知道它们是如何快速的寻找到到食物的呢？最简单效的方法是寻找种群中离食物距离最近的鸟的位置。基于这种思想,就出现了粒子群算法(Particle Swarm Optimization，PSO)，它是一种进化了的计算机技术（evolutionary computation），最早出现是在1995年由Russell Eberhart和James Kennedy博士在文献6-7中提出了粒子群优化算法，它的核心想法是受到鸟类的群体行为，并且它们对这种群体行为进行环境建模与仿真研究，这种研究给予他们了一些启发，但是他们的环境模型和仿真优化算法主要还是借用了生物学家Frank Heppner的建模模型6。PSO算法同遗传算法类似，是一种基于迭代的优化工具。系统初始化为一组随机解，通过迭代搜索最优值。但是并没有遗传算法用的交叉（crossover）以及变异（mutation），而是粒子在解空间追随最优的粒子进行搜索。在Hepper的仿真中，个体鸟是在一块地附近栖息聚群，这块栖息地吸引着所有鸟的到来，最终它们都降落到这块栖息地上。Frank Heppner的鸟类模型中在反映群体行为方面与其他类模型有许多相同之处，不同之处在于：鸟类是被诱引飞向这块栖息地。因此Kennedy等就认为鸟类之间存在着信息的相互交换，因此他们在仿真算法中添加了一点内容：粒子群算法，首先所有种群初始化成在定义域内的一组初始化解，其中每一个解分别对应与空间搜索中的一只鸟(即一个“粒子”)，并且每一个个体粒子都决定一个适应度值，而此适应度值由所解决的实际问题所决定，在这个模型中，任何个体粒子存在两个分向量：一个是速度向量，决定它飞行速度；另一个是位置向量，决定它的位置。第一个向量决定它的飞向速度，第二个向量决定它的飞行方向。通过粒子群的初始化后，基于迭代的运算方式搜索最佳解，并且在每一次迭代运算的过程中，每个粒子通过寻找两个极值来不断地改变更新自己的速度和位置。它们是粒子所经历的历史个体最优位置pbest和整个种群目前的全局最优位置gbest，它们分别代表了粒子个体对自身和社会的认知水平7。另外也可以使用粒子邻居个体寻找最优解而不用整个种群寻找全局最优解，这样在所有邻居中的极值就是局部极值。从某种程度上说，粒子群算法是介于进化算法和遗传算法之间。这种算法的随机性很强，这种特征适合进化算法非常相似的。遗传算法中的交叉算子就和该算法中局部最优靠近全局最优的调整非常的相像。同时适应函数的概念也被此算法广泛应用，当然这种应用也是几乎全部进化计算方法都是使用的。而且这两位研究者Eherhart和Kennedy也将此优化算法在神经网络权重的训练上有所应用，而且针对求解一些测试函数的最优值方面有很大的效果，以上的一些应用都验证了粒子群算法的实际应用性。2.2算法原理在PSO算法中，搜索空间中的每一只鸟都对应着优化问题的解，每一只鸟被形象的化作没有体积和质量的粒子，并将其延伸到N维空间。在N维空间里，粒子i位置被看做是一个矢量，粒子i的飞行速度也被看做是一个矢量。每一个都有一个适应度值（fitness），这个值是由被优化的函数决定的，每个粒子飞翔的距离和力向取决于一个速度。每个微粒都明确地知道自己当前的位置和他们截止到当前所发现的最好的位置（pbest），飞行经验就是指这种先天的优势。另外，更神奇的是所有的微粒都知道截止到当前整个粒子群体中所有粒子所发现的最好的位置（gbest,gbest是局部最好位置pbest中最好的位置），这种本领称为粒子所具有的同伴经验。此时我们就知道了粒子能够快速找到食物的原因了，粒子就是基于自己的飞行经验和同伴经验决定自己下一步的如何运动。例如，在一个D维的目标搜索空间中，每个微粒看成是搜索空间内的一个点（位置）。假设群体由n个微粒所组成。N代表了群体规模的大小，n的大小会直接影响算法的收敛性和运算速度。群体中第i个微粒为Xi=(xi1,xi2,.,xid,.,xiD)第i个粒子(i=1,2,.,n)的D维位置矢量，它经历过的位置为Pi=(pi1,pi2,.,pid,.piD)依据之前给定的适应度函数来计算微粒此时的适应值，适应值的大小可以衡量当前粒子位置的优劣；Vi=(vi1.vid.viD)为第i个微粒的飞行速度，就是粒子在一段时间内运行的长度， pbesti=(pbesti1,pbesti2,.,pbestiD)为粒子到目前寻找到的最优位置；gbesti =(gbest1,.,gbestD)为整个微粒群到目前寻找到的最优位置。每一次迭代运算，微粒可根据式(1)、(2)更新自身的速度和位置：vidk+1=vidk+c1rand1(pbestidk-xidk)+c2rand2(gbestdk-xidk)(1)xidk+1=xidk+vidk+1 (2)其中，i=1，2，n，d=l，2，D，k是迭代运算进行的次数，rand1和rand2为（0,1）之间的任意常数，保持群体的多样性是通过这两个参数来完成的。c1和c2为学习因子，也称为加速因子，其使用粒子具有向群体中优秀个体学习和自我总结的能力，进而向群体的历史最优位置及自身的历史最优位置不断地逼近。虽然这两个参数对粒子群算法的收敛起得作用不大，但是通过合适的调整它们的大小，能够使得局部最小值的困扰减小，并且也可以让群体的收敛速度加快。vidk是粒子i在第k次迭代中第d维的速度分量，它的更新值vidk+1由三部分组成：上一步的惯性vidk；向该粒子自身的最优位置pbest逼近的加速度c1rand1(pbestidk-xidk)；向所有粒子的最优位置gbest逼近的加速度c2rand2(gbestdk-xidk)。后两者由加速度系数c1、c2和随机数rand1、rand2来调节。位置更新值xidk+1是上一步的位置xidk与更新后的速度vidk+1之和。为了让每个粒子不远离搜索空间，所有微粒每一维的速度vd都会被限制在-vdmin, vdmin之间，vdmin取值过大，就会导致这个区间的范围过大，而且微粒很容易脱离最优位置，这个区间过小就会使粒子群陷入局部最优的麻烦。通常情况下，每一维速度值的取法是vdmin=kxdmin,其中0.1k1.09。粒子群算法的结束条件是取得的最优解在迭代计算的过程中值变化很小或者算法迭代步数超过事先所预设的值。由于粒子群算法中没有实际的机制来控制粒子速度，所以速度的最大值也需要有一个限制值，如果速度超过这个限制值时，设为vmax，这个参数对于算法的收敛是十分重要的因素，由于这个值过大将使得粒子群跳出最优解的范围，但是如果这个值过小的话又会造成对搜索空间搜索的不全面。速度vi最小值为vmin，位置zi的取值范围为xminxmax。式(1)的第二部分c1rand1(pbestidk-xidk)是“认知”部分(cognition part)，体现了微粒对自身的学习。公式的第三部分c2rand2(gbestdk-xidk)是“社会”部分(social part)，代表着粒子群体间的协作能力。式(1)则是根据粒子之前一次的速度及现在的位置和自身最好的飞行经验与群体中最好经验之间的差距来不断改变速度的当前值。然后微粒根据式(2)逼近新的位置。在此总结出，粒子群算法是主要遵循了五项基本原则，分别为：(1)邻近原则(proximity)：在简单的时间和空间计算方面，粒子群必须有能力执行；(2)品质原则(quality)：在周围环境的品质因数有所变化时，粒子群必须有所感应 (变量pbest和gbest隐含着这一原则)；(3)多样性反应原则(diverse response)：粒子群尽量避免在过于狭小的空间内运动；(4)定性原则(stability)：在每次环境改变的时候，粒子群不应该每一次都改变自己的行为准则；(5)适应性原则(adaptability)：在能够接受的计算量下，粒子群能够在适当的时候改变他们的行为。以上式(1)、(2)的各个参数制定的准则：粒子数：粒子数的多少应该根据问题的自身的复杂程度进行选取。针对普通的问题取2040个粒子即可，对于复杂程度较高的优化问题，粒子数可以取得大一点来提高优化的精度；粒子的维度：问题解的维度决定；粒子的范围：每一维可设定不同的粒子范围，这是根据优化问题的性质决定的；最大速度Vmax：是粒子在其优化过程，在一个完整时间段的最大的移动距离，一般情况下，它可以作为粒子的范围宽度；学习因子：粒子所拥有的向群体中优秀个体学习和自我总结的能力都是因为学习因子，这样可以使得粒子可以向群体内或邻域内最优点不断靠近，通常取c1和c2为2，一般c1等于c2，且一般取值范围在04之间；惯性权重：对粒子当前速度继承的多少具有决定性，其取值的大小选择，恰当的取值可以使粒子具有均衡的开发能力和探索能力，惯性权重的取法一般有线性递减法、常数法、自适应法8。2.3粒子群优化算法(PSO)的流程粒子群算法的流程如下所示：1）根据粒子群的初始化流程，对粒子群中的每一个粒子的随机速度和位置进行初始设置；2）通过适应度函数(fitness)计算每个粒子的适应度值；3）针对每一个粒子，将每个微粒当前的适应度值与微粒目前为止所经历的最好的位置pbesti的适应度值进行比较大小，若较好，就将粒子当前的位置替换最好的位置pbesti；4）针对每一个粒子，将每个微粒当前的适应度值和微粒所经历的全局的最好位置gbest的适应度值比较大小，若较好，则将其当前的位置替换全局的最好的位置gbest；5）根据式(1)、式(2)对该粒子的位置和速度不断地来更新；6）如未达到结束条件（通常为足够好的适应值或达到一个事先设好的最大迭代数(Gmax)），则返回步骤(2)。2.3.1基本粒子群算法流程图初始化粒子的速度和位置计算每个微粒当前的适应值 与pbesti比较大小 pbesti较小pbesti较大交换它的值，更新微粒在位置保持其值不变与gbest比较大小 Gbest较小gbest较大交换它的值，更新微粒在位置保持其值不变根据(1)(2)式进化粒子位置和速度结 束根据以上流程图，可对微粒群算法做此小结：粒子群算法是一种群体搜索寻优的过程，群体中的每一个个体可以称作粒子，在D维搜索看空间中，该粒子可作为待优化问题的一个潜在解，该解保存有粒子群中所有粒子的最优位置和历史最优位置的记忆，以及速度。在每一代的演化过程中，粒子的信息被组合起来调整速度关于每一维上的分量，继而被用来计算新的粒子位置。每一个粒子在多维度的搜索空间中不断改变它们的状态，直到达到平衡或最优状态，或者超过了算法的截止范围。2.4基本粒子群算法Matlab主要代码及效果图主要代码：%-先计算各个粒子的适应度，并初始化Pi和Pg-figure(3)for i=1:N P(i)=fitness2(x(i,:); y(i,:)=x(i,:);endPg=x(N,:); %Pg为全局最优for i=1:(N-1) if fitness2(x(i,:)fitness2(Pg) Pg=x(i,:); endend%-进入主要循环，按照公式依次迭代，直到满足精度要求-for t=1:MaxDT for i=1:N v(i,:)=w*v(i,:)+c1*rand*(y(i,:)-x(i,:)+c2*rand*(Pg-x(i,:); x(i,:)=x(i,:)+v(i,:); if fitness2(x(i,:)P(i) P(i)=fitn