人工智能基础之自动规划系统(ppt 48页)33509.pptx

合肥工业大学 合肥工业大学 人工智能与数据挖掘研究室 人工智能与数据挖掘研究室 1/47目录o 第一章绪论o 第二章知识表示 o 第三章搜索技术o 第四章推理技术o 第五章机器学习 o 第六章专家系统o 第七章自动规划系统o 第八章自然语言理解o 第九章智能控制o 第十章人工智能程序设计合肥工业大学 合肥工业大学 人工智能与数据挖掘研究室 人工智能与数据挖掘研究室 2/47o 自动规划概述o 基于谓词逻辑的规划o STRIPS 规划系统o 分层规划o 基于专家系统的机器人规划o 轨迹规划简介合肥工业大学 合肥工业大学 人工智能与数据挖掘研究室 人工智能与数据挖掘研究室 3/477.1 自动规划概述7.1.1规划的概念及作用1.规划的概念定义7.1从某个特定的问题状态出发，寻求一系列行为动作，并建立一个操作序列，直到求得目标状态为止。这个求解过程就称为规划。定义7.2规划是对某个待求解问题给出求解过程的步骤。规划涉及如何将问题分解为若干相应的子问题，以及如何记录和处理问题求解过程中发现的各子问题间的关系。定义7.3规划系统是一个涉及有关问题求解过程步骤的系统。如计算机或飞机设计、火车或汽车运输路径、财政和军事规划等问题。合肥工业大学 合肥工业大学 人工智能与数据挖掘研究室 人工智能与数据挖掘研究室 4/477.1 自动规划概述7.1.1规划的概念及作用例：救援仿真机器人系统（RoboCupRescueSimulationSystem，RCRSS）消防智能体医疗智能体警察智能体普通市民中心智能体路障避难所着火建筑物普通建筑物）合肥工业大学 合肥工业大学 人工智能与数据挖掘研究室 人工智能与数据挖掘研究室 5/477.1 自动规划概述7.1.1规划的概念及作用2.规划的作用规划可用来监控问题求解过程，并能够在造成较大的危害之前发现差错。规划的好处可归纳为简化搜索、解决目标矛盾以及为差错补偿提供基础。“十二五”规划、城市规划、企业发展规划合肥工业大学 合肥工业大学 人工智能与数据挖掘研究室 人工智能与数据挖掘研究室 6/477.1 自动规划概述7.1.2规划的分类和问题分解途径1.规划的分类（1）按规划内容分国家、地方、重大项目、企业、交通、城市、环境（2）按规划方法分非递阶（非分层）规划与递阶（分层）规划；线性规划与非线性规划；同步规划与异步规划；基于脚本、框架和本体的规划；基于专家系统的规划；基于竞争机制的规划；（3）按规划实质分任务规划、路径规划、轨迹规划合肥工业大学 合肥工业大学 人工智能与数据挖掘研究室 人工智能与数据挖掘研究室 7/477.1 自动规划概述7.1.2规划的分类和问题分解途径2.问题分解途径把某些较复杂的问题分解为一些较小的子问题。有两条实现这种分解的重要途径。第一条重要途径是当从一个问题状态移动到下一个状态时，无需计算整个新的状态，而只要考虑状态中可能变化了的那些部分。第二条重要途径是把单一的困难问题分割为几个有希望的较为容易解决的子问题。合肥工业大学 合肥工业大学 人工智能与数据挖掘研究室 人工智能与数据挖掘研究室 8/477.1 自动规划概述7.1.2规划的分类和问题分解途径3.域的预测和规划的修正（1）域的预测问题论域的预测。对于不可预测的论域，考虑可能的结果集合，按照它们出现的可能性以某个次序排列。然后，产生一个规划、并试图去执行这个规划。（2）规划的修正规划执行失败导致对规划的修正。在规划过程中不仅要记录规划的执行步骤，而且要记录每一步必须要执行的理由。合肥工业大学 合肥工业大学 人工智能与数据挖掘研究室 人工智能与数据挖掘研究室 9/477.2 基于谓词逻辑的规划用谓词逻辑来描述世界模型及规划过程。o世界模型的谓词逻辑表示n 定义谓词n 确定问题初始状态n 确定问题目标状态n 确定基本操作o基于谓词逻辑规划的基本过程n 问题分解n 子问题规划n 得到操作序列合肥工业大学 合肥工业大学 人工智能与数据挖掘研究室 人工智能与数据挖掘研究室 10/477.3 STRIPS 规划系统7.3.1积木世界的机器人规划求解机器人完成规定工作的动作序列B ACCBA机械手 机械手(a)(b)合肥工业大学 合肥工业大学 人工智能与数据挖掘研究室 人工智能与数据挖掘研究室 11/477.3 STRIPS 规划系统7.3.1积木世界的机器人规划1.积木世界的机器人问题机器人能够执行的动作举例如下：unstack(a,b)：把堆放在积木b 上的积木a拾起。在进行这个动作之前，要求机器人的手为空手，且积木a的顶上是空的。stack(a,b)：把积木a堆放在积木b 上。动作之前要求机械手必须已抓住积木a，而且积木b 顶上必须是空的。pickup(a)：从桌面上拾起积木a，并抓住它不放。在动作之前要求机械手为空手，而且积木a顶上没有任何东西。putdown(a)：把积木a放置到桌面上。要求动作之前机械手已抓住积木a。合肥工业大学 合肥工业大学 人工智能与数据挖掘研究室 人工智能与数据挖掘研究室 12/477.3 STRIPS 规划系统7.3.1积木世界的机器人规划1.积木世界的机器人问题状态描述谓词：ON(a,b)：积木a在积木b 之上。ONTABLE(a)：积木a在桌面上。CLEAR(a)：积木a顶上没有任何东西。HOLDING(a)：机械手正抓住积木a。HANDEMPTY：机械手为空手。合肥工业大学 合肥工业大学 人工智能与数据挖掘研究室 人工智能与数据挖掘研究室 13/477.3 STRIPS 规划系统7.3.1积木世界的机器人规划2.用F 规则求解规划序列采用F 规则表示机器人的动作，这是一个叫做STRIPS 规划系统的规则，它由3部分组成：第一部分是先决条件。为了使F 规则能够应用到状态描述中去。第二部分是一个叫做删除表的谓词。当一条规则被应用于某个状态描述或数据库时，就从该数据库删去删除表的内容。第三部分叫做添加表。当把某条规则应用于某数据库时，就把该添加表的内容添进该数据库。合肥工业大学 合肥工业大学 人工智能与数据挖掘研究室 人工智能与数据挖掘研究室 14/477.3 STRIPS 规划系统7.3.1积木世界的机器人规划2.用F 规则求解规划序列例：move(x,y,z):把物体x从物体y上面移到物体z 上面。先决条件：CLEAR(x),CLEAR(z),ON(x,y)删除表：ON(x,y),CLEAR(z)添加表：ON(x,z),CLEAR(y)合肥工业大学 合肥工业大学 人工智能与数据挖掘研究室 人工智能与数据挖掘研究室 15/477.3 STRIPS 规划系统7.3.2STRIPS 规划系统斯坦福大学人工智能研究所于1966-72 年研制的Shakey 机器人是第一台能够进行行动推理的多用移动机器人，该项目融合了机器人视觉、机器人学和自动推理研究成果。机器人的任务是在一些相连的房间里，将用户指定的箱子推到指定的位置。对于用户输入的每一个任务，Shakey 自主地规划完成该任务的行动并依次执行。Shakey 项目技术：规划语言STRIPS（STanfordResearchInstituteProblemSolverSTRIPS）和A*算法等。STRIPS 语言用来描述外部世界模型并支持任务规划，它提供了框架问题的一种简洁、高效的解法，但理论上并不完备。合肥工业大学 合肥工业大学 人工智能与数据挖掘研究室 人工智能与数据挖掘研究室 16/477.3 STRIPS 规划系统7.3.2STRIPS 规划系统STRIPS 系统的组成如下：(1)世界模型。为一阶谓词演算公式。(2)操作符(F 规则)。包括先决条件、删除表和添加表。(3)操作方法。应用状态空间表示和中间-结局分析。规划过程每个STRIPS 问题的解答为某个实现目标的操作符序列，即达到目标的规划。A Service Robot Copes with Changes Understanding,Learning,Planning,and Acting合肥工业大学 合肥工业大学 人工智能与数据挖掘研究室 人工智能与数据挖掘研究室 17/477.4 分层规划探索规划时首先只考虑一层的细节，然后再注意规划中比这一层低一层的细节，所以把它叫做长度优先搜索。NOAH规划系统1.应用最小约束策略一个寻找非线性规划而不必考虑操作符序列的所有排列的方法是把最少约束策略应用来选择操作符执行次序的问题。问题求解系统NOAH采用一种网络结构来记录它所选取的操作符之间所需要的排序。它也分层进行操作运算，即首先建立起规划的抽象轮廓，然后在后续的各步中，填入越来越多的细节。合肥工业大学 合肥工业大学 人工智能与数据挖掘研究室 人工智能与数据挖掘研究室 18/477.4 分层规划2.检验准则准则法已被应用于各种规划生成系统。对于早期的系统，如HACKER 系统，准则只用于舍弃不满足的规划。在NOAH系统中，准则被用来提出推定的方法以便修正所产生的规划。第一个涉及的准则是归结矛盾准则。第二个准则叫做消除多余先决条件准则，包括除去对子目标的多余说明。可以把分层规划和最少约束策略十分直接地结合起来，以求得非线性规划而不产生一个庞大的搜索树。合肥工业大学 合肥工业大学 人工智能与数据挖掘研究室 人工智能与数据挖掘研究室 19/477.5 基于专家系统的机器人规划1.系统结构及规划机理（1）知识库：用于存储某些特定领域的专家知识和经验，包括机器人工作环境的世界模型、状态、物体描述等事实和可行操作或规则等。（2）控制策略：包含综合机理，确定系统应当应用什么规则以及采取什么方式去寻找该规则。（3）推理机：用于记忆所采用的规则和控制策略及推理策略。（4）知识获取：首先获取某特定域的专家知识。然后用程序设计语言把这些知识变换为计算机程序。最后把它们存入知识库待用。合肥工业大学 合肥工业大学 人工智能与数据挖掘研究室 人工智能与数据挖掘研究室 20/477.5 基于专家系统的机器人规划(5)解释与说明：通过用户接口，在专家系统与用户之间进行对话，从而使用户能够输入数据、提出问题、知道推理结果以及了解推理过程等。2.任务级机器人规划三要素（1）建立模型：世界模型。（2）任务说明：定义状态及状态变换次序。（3）程序综合。3.ROPES 机器人规划系统合肥工业大学 合肥工业大学 人工智能与数据挖掘研究室 人工智能与数据挖掘研究室 21/477.6 轨迹规划简介 轨迹：机械手在运动过程中的位移、速度和加速度。轨迹规划：根据任务的要求，计算出预期的轨迹。在机械手运动学和动力学基础上，讨论在关节空间和笛卡尔空间中机器人运动的轨迹规划和轨迹生成方法合肥工业大学 合肥工业大学 人工智能与数据挖掘研究室 人工智能与数据挖掘研究室 22/477.6 轨迹规划简介 例：NAO 机器人检球动作。合肥工业大学 合肥工业大学 人工智能与数据挖掘研究室 人工智能与数据挖掘研究室 23/47地球上的生物物种在漫长的过程中形成了丰富的行为地球上的生物物种在漫长的过程中形成了丰富的行为特性，并且一直不断地完善和发展，以更好地适应其所生特性，并且一直不断地完善和发展，以更好地适应其所生存的环境。生物群体和自然生态系统可以通过自身的演化存的环境。生物群体和自然生态系统可以通过自身的演化就能使许多在人类看起来高度复杂的优化问题得到完美解就能使许多在人类看起来高度复杂的优化问题得到完美解决。因此，各种模仿生物群体的智能仿生算法被相继提出，决。因此，各种模仿生物群体的智能仿生算法被相继提出，得到了深入研究和应用实践。得到了深入研究和应用实践。群智能思想的产生主要源于复杂适应系统理论以及人群智能思想的产生主要源于复杂适应系统理论以及人工生命的研究。工生命的研究。群智能算法群智能思想起源合肥工业大学 合肥工业大学 人工智能与数据挖掘研究室 人工智能与数据挖掘研究室 24/47群智能算法群智能思想起源复杂适应系统(ComplexAdaptiveSystem,CAS)理论：1994年由Holland教授正式提出。CAS中成员称为具有适应性的主体,简称主体。主体的适应性,是指它能够与环境以及其它主体进行交流，在交流的过程中“学习”或“积累经验”，并且根据学到的经验改变自身的结构和行为方式。CAS具有四个基本特点:（1）首先,主体是主动的、活的实体。具有适应性的主体的概念把个体主动性提高到了系统进化基本动因的位置,从而成为研究与考察宏观行为的出发点。（2）其次,个体与环境(包括个体之间)之间的相互影响、相互作用是系统演变和进化的主要动力。相互作用是“可记忆”的,它表现为进化过程中每个个体的结构和行为方式的变化，以不同的方式“存储”在个体内部。合肥工业大学 合肥工业大学 人工智能与数据挖掘研究室 人工智能与数据挖掘研究室 25/47群智能算法群智能思想起源（3）再次,这种方法不像许多其他的方法那样,把宏观和微观截然分开,而是把它们有机地联系起来。（4）最后,这种建模方法还引进了随机因素的作用,使它具有更强的描述和表达能力。随机因素的影响不仅影响状态,而且影响组织结构和行为方式。具有主动性的个体会接受教训,总结经验,并且以某种方式把“经历”记住,使之“固化”在自己以后的行为方式中。CAS理论提供了模拟生物、生态、经济、社会等复杂系统的巨大潜力。合肥工业大学 合肥工业大学 人工智能与数据挖掘研究室 人工智能与数据挖掘研究室 26/47群智能算法群智能思想起源人工生命(ArtificialLife,AL)是用来研究具有某些生命基本特征的人工系统。近年来,人工生命的研究发展非常快,在某些方面的研究已与传统的生物科学形成了互补。人工生命包括两方面的内容:如何利用计算技术研究生物现象;如何利用生物技术研究计算问题。第二部分的内容的研究中，现已经有了很多源于生物现象的计算技巧，例如，人工神经网络是简化的大脑模型，遗传算法是模拟基因进化的过程，目前这一类计算技术被统称为自然计算。群智能属于自然计算中的一类，它模拟另一种生物系统：社会系统，更确切地说，是模拟由简单个体组成的群落与环境以及个体之间的互动行为，这些模拟系统利用局部信息从而可能产生不可预测的群体行为。合肥工业大学 合肥工业大学 人工智能与数据挖掘研究室 人工智能与数据挖掘研究室 27/47群智能算法群智能思想起源群智能(SwarmIntelligence,SI)：1992年由Beni,Hack-wood和Wang在分子自动机系统中提出。1999年,Bonabeau,Dorigo和Theraulaz在SwarmIntel-ligence:FromNaturaltoArtificialSystems中对群智能进行了详细的论述和分析。2003年IEEE第一届国际群智能研讨会在美国印第安纳州首府召开。群智能定义：任何一种由昆虫群体或其它动物社会行为机制而激发设计出的算法或分布式解决问题的策略均属于群智能。合肥工业大学 合肥工业大学 人工智能与数据挖掘研究室 人工智能与数据挖掘研究室 28/47群智能算法群智能思想起源Swarm可被描述为一些相互作用相邻个体的集合体,蜂群、蚁群、鸟群、鱼群都是Swarm的典型例子。社会性动物群体所拥有的这种特性能帮助个体很好地适应环境，个体所能获得的信息远比它通过自身感觉器官所取得的多，其根本原因在于个体之间存在着信息交互能力。信息的交互过程不仅仅在群体内传播了信息，而且群内个体还能处理信息，并根据所获得的信息(包括环境信息和附近其它个体的信息)改变自身的一些行为模式和规范,这样就使得群体涌现出一些单个个体所不具备的能力和特性,尤其是对环境的适应能力。这种对环境变化所具有的适应能力可以被认为是一种智能,也就是说动物个体通过聚集成群而涌现出了智能。合肥工业大学 合肥工业大学 人工智能与数据挖掘研究室 人工智能与数据挖掘研究室 29/47群智能算法群智能思想起源SI的定义进一步推广（Bonabeau）:无智能或简单智能的主体通过任何形式的聚集协同而表现出智能行为的特性。群智能理论还非常不成熟,但已成为有别于传统人工智能中连接主义、行为主义和符号主义的一种新的关于智能的描述方法,并成为人工智能领域的新研究热点。合肥工业大学 合肥工业大学 人工智能与数据挖掘研究室 人工智能与数据挖掘研究室 30/47群智能算法群智能理论JamesKennedy和RussellC.Eberhart在2001年出版的SwarmIntelligence是群智能发展的一个重要历程碑。他们不反对Bonabeau关于SI的定义，赞同其定义的基本精神，但反对定义中使用“主体”一词。其理由是“主体”所带有的自治性和特殊性是许多Swarm的个体所不具备和拥有的，这将大大限制Swarm的定义范围。MarkMillonas(1994)构建一个SI系统所应满足的五条基本原则:ProximityPrinciple:群内个体具有能执行简单的时间或空间上的评估和计算的能力。合肥工业大学 合肥工业大学 人工智能与数据挖掘研究室 人工智能与数据挖掘研究室 31/47群智能算法群智能理论QualityPrinciple:群内个体能对环境(包括群内其它个体)的关键性因素的变化做出响应。PrincipleofDiverseResponse:群内不同个体对环境中的某一变化所表现出的响应行为具有多样性。StabilityPrinciple:不是每次环境的变化都会导致整个群体的行为模式的改变。AdaptabilityPrinciple:环境所发生的变化中,若出现群体值得付出代价的改变机遇,群体必须能够改变其行为模式。合肥工业大学 合肥工业大学 人工智能与数据挖掘研究室 人工智能与数据挖掘研究室 32/47群智能算法群智能理论以上五条原则现在成为了群智能的最基本理论，现有的群智能方法和策略都符合这些原则。SwarmIntelligence最重要的观点是：Mindissocial,也就是认为人的智能是源于社会性的相互作用，文化和认知是人类社会性不可分割的重要部分，这一观点成为了群智能发展的基石。群智能模拟的是社会系统的变化，其最基本单位是“敏因”(Meme)，这一词由Dawkin在TheSelfishGene中提出，它是指思想文化传播中的基本单位，个体在社会中会根据环境来改变自身的思想，敏因的传播途径是在个体与个体之间，在人类社会中它还可以在人脑与书本之间、人脑与计算机、计算机与计算机之间传播。当然，“敏因”应该如何严格描述和定义还没有定论。合肥工业大学 合肥工业大学 人工智能与数据挖掘研究室 人工智能与数据挖掘研究室 33/47群智能算法群智能理论群智能研究的更进一步目标是对人类思想变化的社会行为的模拟。人类心理中存在着群体性、习惯性、一致性,常常是习惯性地遵循一些习俗和规则。无论什么时候,人们思想和行为总是因相互影响而变得非常近似,道德规范以及文化的形成就是这种通过相互间影响而导致近似的结果。人类的社会思想行为并不简单类似鸟群或鱼群的行为,人类思想的形成过程是一种在高维认知空间的探索历程。两种思想意见在认知空间上聚集到一点上,被称为“一致”或“认同”,而不是鸟群或鱼群系统中的“碰撞”。如果某人认同认知空间某个点,那么就努力靠近它,反之则尽量远离它,这里认知空间中的某个点就是某个人的思想。人类通过这种社会行为达成社会的共识:习俗、道德规范等。目前,群智能理论研究处于基本思想描述阶段,还未能提出一些较为明确的概念和定义,尽管已经有人提出广义群智能的模型。合肥工业大学 合肥工业大学 人工智能与数据挖掘研究室 人工智能与数据挖掘研究室 34/47蚁群算法(AntColonyOptimizationACO)由Colorni,Dorigo和Maniezzo于1991年提出,它是通过模拟自然界蚂蚁社会的寻找食物的方式而得出的一种仿生优化算法。自然界种蚁群寻找食物时会派出一些蚂蚁分头在四周游荡,如果一只蚂蚁找到食物,它就返回巢中通知同伴并沿途留下“信息素”(pheromone)作为蚁群前往食物所在地的标记。信息素会逐渐挥发,如果两只蚂蚁同时找到同一食物,又采取不同路线回到巢中,那么比较绕弯的一条路上信息素的气味会比较淡,蚁群将倾向于沿另一条更近的路线前往食物所在地。ACO算法设计虚拟的“蚂蚁”,让它们摸索不同路线,并留下会随时间逐渐消失的虚拟“信息素”。根据“信息素较浓的路线更近”的原则,即可选择出最佳路线。群智能算法蚁群算法合肥工业大学 合肥工业大学 人工智能与数据挖掘研究室 人工智能与数据挖掘研究室 35/47 ACO ACO算法首先应用于 算法首先应用于 TSP TSP问题中 问题中,这里以 这里以 TSP TSP问题为例 问题为例对算法作简单介绍。当某一个蚂蚁走到一个城市 对算法作简单介绍。当某一个蚂蚁走到一个城市,下一步可选 下一步可选的路径集合为 的路径集合为 E,E,集合中任一条路径 集合中任一条路径 e e E E上的信息素浓度为 上的信息素浓度为 e e,走这条路的代价为 走这条路的代价为 e e,那么选择某一条路径 那么选择某一条路径 v v E E的几率为：的几率为：群智能算法蚁群算法合肥工业大学 合肥工业大学 人工智能与数据挖掘研究室 人工智能与数据挖掘研究室 36/47其中,和两个参数分别用来控制信息素和路径长度的相对重要程度。当蚂蚁在所有城市走过一遍之后，路径上的信息素浓度将变为:e(t+1)=(1-)e(t)+e其中，01用于控制信息素随时间挥发的速度，e是上次蚂蚁经过此路段所留下的信息素，未经过则为0。上式以及e可以根据问题进行设计。目前，ACO算法已被广泛应用于组合优化问题中，在车辆调度问题、机器人路径规划问题、路由算法设计等领域均取得了良好的效果。由于ACO算法具有广泛实用价值，成为了群智能领域第一个取得成功的实例，曾一度成为群智能的代名词，相应理论研究及改进算法近年来不断取得新的成果。群智能算法蚁群算法合肥工业大学 合肥工业大学 人工智能与数据挖掘研究室 人工智能与数据挖掘研究室 37/47粒子群优化算法（ParticleSwarmOptimizationPSO)源于1987年Reynolds对鸟群社会系统boids的仿真研究，boids也是一个CAS。在boids中,一群鸟在空中飞行,每个鸟遵守以下三条规则:（1）避免与相邻的鸟发生碰撞冲突;（2）尽量与自己周围的鸟在速度上保持协调和一致;（3）尽量试图向自己所认为的群体中心靠近。仅仅通过使用这三条规则,boids系统就出现非常逼真的群体聚集行为,鸟成群地在空中飞行,当遇到障碍时它们会分开绕行而过,随后又会重新形成群体。不过Reynolds仅仅将其作为CAS的一个实例作仿真研究,而并未将它用于优化计算中,也无任何实用价值。群智能算法粒子群优化算法合肥工业大学 合肥工业大学 人工智能与数据挖掘研究室 人工智能与数据挖掘研究室 38/47 Kennedy Kennedy和 和 Eberhart Eberhart（1995 1995年）在 年）在 boids boids 中加入了一个 中加入了一个特定点 特定点,定义为食物 定义为食物,鸟根据周围鸟的觅食行为来寻找食物。鸟根据周围鸟的觅食行为来寻找食物。他们的初衷是希望通过这种模型来模拟鸟群寻找食源的现象 他们的初衷是希望通过这种模型来模拟鸟群寻找食源的现象,然而实验结果却揭示这个仿真模型中蕴涵着很强的优化能力 然而实验结果却揭示这个仿真模型中蕴涵着很强的优化能力,尤其是在多维空间寻优中。尤其是在多维空间寻优中。由于最初的仿真系统中每个鸟在 由于最初的仿真系统中每个鸟在计算机屏幕上表示为一个点 计算机屏幕上表示为一个点,而 而“点 点(Points)”(Points)”这个词在 这个词在数学领域具有非常多的意义 数学领域具有非常多的意义,因此作者用了 因此作者用了“粒子 粒子(Particle)”Particle)”来表示每一个个体。于是也就得到了基本 来表示每一个个体。于是也就得到了基本 PSO PSO算 算法。法。群智能算法粒子群优化算法合肥工业大学 合肥工业大学 人工智能与数据挖掘研究室 人工智能与数据挖掘研究室 39/47群智能算法粒子群优化算法合肥工业大学 合肥工业大学 人工智能与数据挖掘研究室 人工智能与数据挖掘研究室 40/47粒子群特性 粒子群特性群智能算法粒子群优化算法合肥工业大学 合肥工业大学 人工智能与数据挖掘研究室 人工智能与数据挖掘研究室 41/47 在 在PSO PSO系统初始化为一群随机粒子 系统初始化为一群随机粒子(随机解 随机解)，然后通过迭 然后通过迭代找到最优解。在每一次迭代中 代找到最优解。在每一次迭代中,粒子通过跟踪两个 粒子通过跟踪两个“极值 极值”来更新自己 来更新自己,同时也通过跟踪它们实现粒子间的信息交换。同时也通过跟踪它们实现粒子间的信息交换。第一个就是粒子本身所找到的最优解 第一个就是粒子本身所找到的最优解,这个解叫作个体极值 这个解叫作个体极值pBest pBest(“(“自身经验 自身经验”)”)。另一个极值是整个群体目前找到的最优解。另一个极值是整个群体目前找到的最优解,这个极值是群体极值 这个极值是群体极值 gBest(gBest(群体的 群体的“社会经验 社会经验”)”)。群智能算法粒子群优化算法合肥工业大学 合肥工业大学 人工智能与数据挖掘研究室 人工智能与数据挖掘研究室 42/47 1998 1998年 年,Shi,Shi和 和Eberhart Eberhart正式给出标准 正式给出标准PSO PSO算法的数学描述 算法的数学描述如下 如下:设搜索空间为 设搜索空间为M M维 维,粒子数为 粒子数为N N。第。第i i个粒子位置表示为向 个粒子位置表示为向量 量Xi=(xi1,xi2,xiD);Xi=(xi1,xi2,xiD);第 第i i个粒子 个粒子“飞行 飞行”历史中的过去最 历史中的过去最优位置 优位置(即该位置对应解最优 即该位置对应解最优)为 为Pi=(pi1,pi2,piD)Pi=(pi1,pi2,piD)也就是 也就是 pBest pBest，其中所有 其中所有Pi(i=1,N)Pi(i=1,N)中的最优个体被记作 中的最优个体被记作Pg Pg也就是 也就是 gBest gBest；第 第i i个粒子的位置变化率 个粒子的位置变化率(速度 速度)为向量 为向量Vi=(vi1,vi2,Vi=(vi1,vi2,viD)viD)。每。每个粒子的位置按如下公式进行变化 个粒子的位置按如下公式进行变化(“(“飞行 飞行”):):群智能算法粒子群优化算法合肥工业大学 合肥工业大学 人工智能与数据挖掘研究室 人工智能与数据挖掘研究室 43/47 其中 其中,c1,c2,c1,c2为正常数 为正常数,称为加速因子 称为加速因子;rand();rand()为 为0,1 0,1之间的 之间的随机数 随机数;w;w称惯性因子。第 称惯性因子。第d(1dM)d(1dM)维的位置变化范围和速度 维的位置变化范围和速度变化范围分别为 变化范围分别为-x-xd,max d,max,x,xd,max d,max 和 和-v-vd,max d,max,v,vd,max d,max(变化范围可 变化范围可通过平移处理使之对称 通过平移处理使之对称),),迭代中若某一维的 迭代中若某一维的x xid id 或 或v vid id 超过边界 超过边界则取边界值。粒子群初始位置和速度随机产生 则取边界值。粒子群初始位置和速度随机产生,然后按公式进行 然后按公式进行迭代 迭代,直至满足停止条件。直至满足停止条件。群智能算法粒子群优化算法合肥工业大学 合肥工业大学 人工智能与数据挖掘研究室 人工智能与数据挖掘研究室 44/47 2003 2003年李晓磊、年李晓磊、邵之江等提出的 邵之江等提出的人工鱼群算法（人工鱼群算法（ArtificialFish-ArtificialFish-SwarmAlgorithmAFSA)SwarmAlgorithmAFSA)，它利用自上而下的寻优模式模仿自然，它利用自上而下的寻优模式模仿自然界鱼群觅食行为 界鱼群觅食行为,主要利用鱼的觅食、聚群和追尾行为 主要利用鱼的觅食、聚群和追尾行为,构造个体 构造个体底层行为 底层行为;通过鱼群中各个体的局部寻优 通过鱼群中各个体的局部寻优,达到全局最优值在群体 达到全局最优值在群体中凸现出来的目的。在基本运算中引入鱼群的生存机制、竞争机 中凸现出来的目的。在基本运算中引入鱼群的生存机制、竞争机制以及鱼群的协调机制 制以及鱼群的协调机制,提高算法的有效效率。李晓磊等又采用分 提高算法的有效效率。李晓磊等又采用分解协调的思想构造一种改进的人工鱼群算法 解协调的思想构造一种改进的人工鱼群算法,并以换热器系统为例 并以换热器系统为例,验证了该算法，结果表明该算法具有较好的收敛性。验证了该算法，结果表明该算法具有较好的收敛性。AFSA AFSA只使用目标函数的函数值，无需目标函数的梯度值等特殊 只使用目标函数的函数值，无需目标函数的梯度值等特殊信息，对搜索空间具有一定的自适应能力。算法对初值无要求，信息，对搜索空间具有一定的自适应能力。算法对初值无要求，对各参数的选择也不很敏感。对各参数的选择也不很敏感。群智能算法人工鱼群算法合肥工业大学 合肥工业大学 人工智能与数据挖掘研究室 人工智能与数据挖掘研究室 45/47群智能算法人工鱼群算法合肥工业大学 合肥工业大学 人工智能与数据挖掘研究室 人工智能与数据挖掘研究室 46/47 基于 基于SI SI的优化算法和 的优化算法和EC EC都是基于群体迭代的启发式随机优化算法 都是基于群体迭代的启发式随机优化算法,有 有着非常多相似之处 着非常多相似之处,它们都是对自然中随机系统的仿真 它们都是对自然中随机系统的仿真,都具有本质并行 都具有本质并行性。另外 性。另外,与 与EC EC还一样的是 还一样的是,SI,SI的目的并不是为了忠实地模拟自然现象 的目的并不是为了忠实地模拟自然现象,而是利用它们的某些特点去解决实际问题。而是利用它们的某些特点去解决实际问题。ACO ACO和 和PSO PSO也一度曾被归类 也一度曾被归类于 于EC EC之中 之中,但它们与 但它们与EC EC之间的区别也是明显的。之间的区别也是明显的。ACO ACO、PSO PSO在本质上不 在本质上不能用广义 能用广义EC EC算法的流程进行描述。算法的流程进行描述。首先 首先，EC EC和 和SI SI所模拟的自然随机系统不一样。所模拟的自然随机系统不一样。EC EC是模拟生物系统进 是模拟生物系统进化过程 化过程,其最基本单位是基因 其最基本单位是基因(Gene),(Gene),它在生物体的每一代之间传播 它在生物体的每一代之间传播;已有 已有的基于 的基于SI SI的优化算法都是源于对动物社会通过协作解决问题行为的模拟 的优化算法都是源于对动物社会通过协作解决问题行为的模拟,它主要强调对社会系统中个体之间相互协同作用的模拟 它主要强调对社会系统中个体之间相互协同作用的模拟,其最基本单位是 其最基本单位是敏因。敏因。群智能算法与进化计算比较合肥工业大学 合肥工业大学 人工智能与数据挖掘研究室 人工智能与数据挖掘研究室 47/47 其次 其次，EC EC中强调 中强调“适者生存 适者生存”,”,不好的个体在竞争中被淘汰 不好的个体在竞争中被淘汰;SI SI强调 强调“协同合作 协同合作”,”,不好的个体通过学习向好的方向转变 不好的个体通过学习向好的方向转变,不好 不好的个体被保留还可以增强群体的多样性。的个体被保留还可以增强群体的多样性。EC EC中最好的个体通过 中最好的个体通过产生更多的后代来传播自己的基因 产生更多的后代来传播自己的基因,而 而 SI SI中的优秀个体通过吸引 中的优秀个体通过吸引其它个体向它靠近来传播自己的敏因。其它个体向它靠近来传播自己的敏因。最后，最后，EC EC的迭代由选择、变异和交叉重组操作组成，而 的迭代由选择、变异和交叉重组操作组成，而 SI SI的迭代中的操作是 的迭代中的操作是“跟随 跟随”，ACO ACO中蚂蚁跟随信息素浓度爬行 中蚂蚁跟随信息素浓度爬行,PSO,PSO中粒子跟随最优粒子飞行。在某种程度上看，中粒子跟随最优粒子飞行。在某种程度上看，SI SI的跟随操 的跟随操作中隐含了选择、作中隐含了选择、变异和交叉重组操作。变异和交叉重组操作。群智能算法与进化计算比较合肥工业大学 合肥工业大学 人工智能与数据挖掘研究室 人工智能与数据挖掘研究室 48/47 例如，例如，PSO PSO中 中 gBest gBest和 和pBest pBest的更新可以类似一种弱选择；的更新可以类似一种弱选择；而粒子位置更新则类似于 而粒子位置更新则类似于3 3个父代：个父代：Xi Xi、gBest gBest和 和 pBest pBest的之间 的之间重组，其中还包含了变异的成分。重组，其中还包含了变异的成分。SI SI中所隐含的变异是有偏好 中所隐含的变异是有偏好的，而并非通常 的，而并非通常 EC EC中的完全随机变异，这与最近对实际生物 中的完全随机变异，这与最近对实际生物系统变异行为的新研究成果相符。系统变异行为的新研究成果相符。Kennedy Kennedy认为，认为，EC EC和 和 SI SI所分别模拟的两个伟大的自然随 所分别模拟的两个伟大的自然随机系统：机系统：Evolution Evolution和 和 Mind Mind之间存在着显著的差异，尽管它们 之间存在着显著的差异，尽管它们都是基于群体的，都是由其中的随机成分带来创新，但其本质 都是基于群体的，都是由其中的随机成分带来创新，但其本质是不同的，因此不能将 是不同的，因此不能将 SI SI简单地归类于 简单地归类于 EC EC中。现在，人工智 中。现在，人工智能领域已将 能领域已将 SI SI作为一个独立方向，与 作为一个独立方向，与 EC EC的地位是同等的。的地位是同等的。群智能算法与进化计算比较