人工智能基础07--自动规划系统课件

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