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

1、1/47目录o 第一章第一章绪论绪论o 第二章第二章知识表示知识表示 o 第三章搜索技术第三章搜索技术o 第四章推理技术第四章推理技术o 第五章机器学习第五章机器学习 o 第六章专家系统第六章专家系统 o 第七章自动规划系统第七章自动规划系统o 第八章第八章 自然语言理解自然语言理解o 第九章第九章 智能控制智能控制o 第十章第十章 人工智能程序设计人工智能程序设计2/47o 自动规划概述自动规划概述o 基于谓词逻辑的规划基于谓词逻辑的规划o STRIPS规划系统规划系统o 分层规划分层规划o 基于专家系统的机器人规划基于专家系统的机器人规划o 轨迹规划简介轨迹规划简介3/477.1 自动规划

2、概述7.1.1 规划的概念及作用规划的概念及作用 1.规划的概念规划的概念 定义定义7.1 从某个特定的问题状态出发，寻求一系列行为从某个特定的问题状态出发，寻求一系列行为动作，并建立一个操作序列，直到求得目标状态为止。这个求动作，并建立一个操作序列，直到求得目标状态为止。这个求解过程就称为解过程就称为规划规划。定义定义7.2 规划是对某个待求解问题给出求解过程的步骤。规划是对某个待求解问题给出求解过程的步骤。规划涉及如何将问题分解为若干相应的子问题，以及如何记录规划涉及如何将问题分解为若干相应的子问题，以及如何记录和处理问题求解过程中发现的各子问题间的关系。和处理问题求解过程中发现的各子问题

3、间的关系。定义定义7.3 规划系统是一个涉及有关问题求解过程步骤的系规划系统是一个涉及有关问题求解过程步骤的系统。如计算机或飞机设计、火车或汽车运输路径、财政和军事统。如计算机或飞机设计、火车或汽车运输路径、财政和军事规划等问题。规划等问题。4/477.1 自动规划概述7.1.1 规划的概念及作用规划的概念及作用 例：例：救援仿真机器人系统救援仿真机器人系统（RoboCup Rescue Simulation System，RCRSS）消防智能体消防智能体 医疗智能体医疗智能体 警察智能体警察智能体 普通市民普通市民 中心智能体中心智能体 路障路障 避难所避难所 着火建筑物着火建筑物 普通建筑

4、物）普通建筑物）5/477.1 自动规划概述7.1.1 规划的概念及作用规划的概念及作用 2.规划的作用规划的作用 规划可用来监控问题求解过程，并能够在造成较大的危害规划可用来监控问题求解过程，并能够在造成较大的危害之前发现差错。规划的好处可归纳为简化搜索、解决目标矛盾之前发现差错。规划的好处可归纳为简化搜索、解决目标矛盾以及为差错补偿提供基础。以及为差错补偿提供基础。“十二五十二五”规划、城市规划、企业发展规划规划、城市规划、企业发展规划6/477.1 自动规划概述7.1.2 规划的分类和问题分解途径规划的分类和问题分解途径 1.规划的分类规划的分类 （1）按规划内容分）按规划内容分 国家、

5、地方、重大项目、企业、交通、城市、环境国家、地方、重大项目、企业、交通、城市、环境 （2）按规划方法分）按规划方法分 非递阶（非分层）规划与递阶（分层）规划；线性规划与非递阶（非分层）规划与递阶（分层）规划；线性规划与非线性规划；同步规划与异步规划；基于脚本、框架和本体的非线性规划；同步规划与异步规划；基于脚本、框架和本体的规划；基于专家系统的规划；基于竞争机制的规划；规划；基于专家系统的规划；基于竞争机制的规划；（3）按规划实质分）按规划实质分 任务规划、路径规划、轨迹规划任务规划、路径规划、轨迹规划7/477.1 自动规划概述7.1.2 规划的分类和问题分解途径规划的分类和问题分解途径 2

6、.问题分解途径问题分解途径把某些较复杂的问题分解为一些较小的子问题。有两条实把某些较复杂的问题分解为一些较小的子问题。有两条实现这种分解的重要途径。现这种分解的重要途径。第一条重要途径是当从一个问题状态移动到下一个状态时第一条重要途径是当从一个问题状态移动到下一个状态时，无需计算整个新的状态，而只要考虑状态中可能变化了的那，无需计算整个新的状态，而只要考虑状态中可能变化了的那些部分。些部分。第二条重要途径是把单一的困难问题分割为几个有希望的第二条重要途径是把单一的困难问题分割为几个有希望的较为容易解决的子问题。较为容易解决的子问题。8/477.1 自动规划概述7.1.2 规划的分类和问题分解途

7、径规划的分类和问题分解途径 3.域的预测和规划的修正域的预测和规划的修正 （1）域的预测）域的预测 问题论域的预测。对于不可预测的论域，考虑可能的结果问题论域的预测。对于不可预测的论域，考虑可能的结果集合，按照它们出现的可能性以某个次序排列。然后，产生一集合，按照它们出现的可能性以某个次序排列。然后，产生一个规划、并试图去执行这个规划。个规划、并试图去执行这个规划。（2）规划的修正）规划的修正 规划执行失败导致对规划的修正。规划执行失败导致对规划的修正。在规划过程中不仅要记录规划的执行步骤，而且要记录每在规划过程中不仅要记录规划的执行步骤，而且要记录每一步必须要执行的理由。一步必须要执行的理由

8、。9/477.2 基于谓词逻辑的规划 用谓词逻辑来描述世界模型及规划过程。用谓词逻辑来描述世界模型及规划过程。o 世界模型的谓词逻辑表示世界模型的谓词逻辑表示n 定义谓词定义谓词n 确定问题初始状态确定问题初始状态n 确定问题目标状态确定问题目标状态n 确定基本操作确定基本操作o 基于谓词逻辑规划的基本过程基于谓词逻辑规划的基本过程n 问题分解问题分解n 子问题规划子问题规划n 得到操作序列得到操作序列10/477.3 STRIPS规划系统 7.3.1 积木世界的机器人规划积木世界的机器人规划求解机器人完成规定工作的动作序列求解机器人完成规定工作的动作序列 BACCBA机械手机械手机械手机械手

9、(a)(b)11/477.3 STRIPS规划系统 7.3.1 积木世界的机器人规划积木世界的机器人规划 1.积木世界的机器人问题积木世界的机器人问题 机器人能够执行的动作机器人能够执行的动作举例如下：举例如下：unstack(a,b)：把堆放在积木：把堆放在积木b上的积木上的积木a拾起。在进行这个拾起。在进行这个动作之前，要求机器人的手为空手，且积木动作之前，要求机器人的手为空手，且积木a的顶上是空的。的顶上是空的。stack(a,b)：把积木把积木a堆放在积木堆放在积木b上。动作之前要求机械上。动作之前要求机械手必须已抓住积木手必须已抓住积木a，而且积木，而且积木b顶上必须是空的。顶上必须

10、是空的。pickup(a)：从桌面上拾起积木从桌面上拾起积木a，并抓住它不放。在动作，并抓住它不放。在动作之前要求机械手为空手，而且积木之前要求机械手为空手，而且积木a顶上没有任何东西。顶上没有任何东西。putdown(a)：把积木把积木a放置到桌面上。要求动作之前机械放置到桌面上。要求动作之前机械手已抓住积木手已抓住积木a。12/477.3 STRIPS规划系统 7.3.1 积木世界的机器人规划积木世界的机器人规划 1.积木世界的机器人问题积木世界的机器人问题状态描述谓词状态描述谓词：ON(a,b)：积木积木a在积木在积木b之上。之上。ONTABLE(a)：积木积木a在桌面上。在桌面上。CL

11、EAR(a)：积木积木a顶上没有任何东西。顶上没有任何东西。HOLDING(a)：机械手正抓住积木机械手正抓住积木a。HANDEMPTY：机械手为空手。机械手为空手。13/477.3 STRIPS规划系统 7.3.1 积木世界的机器人规划积木世界的机器人规划 2.用用F规则求解规划序列规则求解规划序列采用采用F规则表示机器人的动作，这是一个叫做规则表示机器人的动作，这是一个叫做STRIPS规划规划系统的规则，它由系统的规则，它由3部分组成：部分组成：第一部分是先决条件。为了使第一部分是先决条件。为了使F规则能够应用到状态描述规则能够应用到状态描述中去。中去。第二部分是一个叫做删除表的谓词。当一

12、条规则被应用于第二部分是一个叫做删除表的谓词。当一条规则被应用于某个状态描述或数据库时，就从该数据库删去删除表的内容。某个状态描述或数据库时，就从该数据库删去删除表的内容。第三部分叫做添加表。当把某条规则应用于某数据库时，第三部分叫做添加表。当把某条规则应用于某数据库时，就把该添加表的内容添进该数据库。就把该添加表的内容添进该数据库。14/477.3 STRIPS规划系统 7.3.1 积木世界的机器人规划积木世界的机器人规划 2.用用F规则求解规划序列规则求解规划序列例：例：move(x,y,z):把物体把物体x从物体从物体y上面移到物体上面移到物体z上面。上面。先决条件：先决条件：CLEAR

13、(x),CLEAR(z),ON(x,y)删除表：删除表：ON(x,y),CLEAR(z)添加表：添加表：ON(x,z),CLEAR(y)15/477.3 STRIPS规划系统 7.3.2 STRIPS规划系统规划系统 斯坦福大学人工智能研究所于斯坦福大学人工智能研究所于1966-72年研制的年研制的Shakey机器机器人是第一台能够进行行动推理的多用移动机器人，该项目融合人是第一台能够进行行动推理的多用移动机器人，该项目融合了机器人视觉、机器人学和自动推理研究成果。机器人的任务了机器人视觉、机器人学和自动推理研究成果。机器人的任务是在一些相连的房间里，将用户指定的箱子推到指定的位置。是在一些相

14、连的房间里，将用户指定的箱子推到指定的位置。对于用户输入的每一个任务，对于用户输入的每一个任务，Shakey自主地规划完成该任务的自主地规划完成该任务的行动并依次执行。行动并依次执行。Shakey项目技术：规划语言项目技术：规划语言STRIPS（STanford Research Institute Problem SolverSTRIPS）和）和A*算法等。算法等。STRIPS语言用来描述外部世界模型并支持任务规划，它提语言用来描述外部世界模型并支持任务规划，它提供了框架问题的一种简洁、高效的解法，但理论上并不完备。供了框架问题的一种简洁、高效的解法，但理论上并不完备。16/477.3 ST

15、RIPS规划系统 7.3.2 STRIPS规划系统规划系统 STRIPS系统的组成如下：系统的组成如下：(1)世界模型。为一阶谓词演算公式。世界模型。为一阶谓词演算公式。(2)操作符操作符(F规则规则)。包括先决条件、删除表和添加表。包括先决条件、删除表和添加表。(3)操作方法。应用状态空间表示和中间操作方法。应用状态空间表示和中间-结局分析。结局分析。规划过程规划过程每个每个STRIPS问题的解答为某个实现目标的操作符序列，问题的解答为某个实现目标的操作符序列，即达到目标的规划。即达到目标的规划。A Service Robot Copes with Changes Understanding

16、,Learning,Planning,and Acting17/477.4 分层规划 探索规划时首先只考虑一层的细节，然后再注意规划中比探索规划时首先只考虑一层的细节，然后再注意规划中比这一层低一层的细节，所以把它叫做长度优先搜索。这一层低一层的细节，所以把它叫做长度优先搜索。NOAH规划系统规划系统1.应用最小约束策略应用最小约束策略一个寻找非线性规划而不必考虑操作符序列的所有排列的一个寻找非线性规划而不必考虑操作符序列的所有排列的方法是把最少约束策略应用来选择操作符执行次序的问题。方法是把最少约束策略应用来选择操作符执行次序的问题。问题求解系统问题求解系统NOAH采用一种网络结构来记录它所

17、选取的采用一种网络结构来记录它所选取的操作符之间所需要的排序。它也分层进行操作运算，即首先建操作符之间所需要的排序。它也分层进行操作运算，即首先建立起规划的抽象轮廓，然后在后续的各步中，填入越来越多的立起规划的抽象轮廓，然后在后续的各步中，填入越来越多的细节。细节。18/477.4 分层规划 2.检验准则检验准则准则法已被应用于各种规划生成系统。对于早期的系统，准则法已被应用于各种规划生成系统。对于早期的系统，如如HACKER系统，准则只用于舍弃不满足的规划。在系统，准则只用于舍弃不满足的规划。在NOAH系统中，准则被用来提出推定的方法以便修正所产生的规划。系统中，准则被用来提出推定的方法以便

18、修正所产生的规划。第一个涉及的准则是归结矛盾准则。第一个涉及的准则是归结矛盾准则。第二个准则叫做消除多余先决条件准则，包括除去对子目第二个准则叫做消除多余先决条件准则，包括除去对子目标的多余说明。标的多余说明。可以把分层规划和最少约束策略十分直接地结合起来，以可以把分层规划和最少约束策略十分直接地结合起来，以求得非线性规划而不产生一个庞大的搜索树。求得非线性规划而不产生一个庞大的搜索树。19/477.5 基于专家系统的机器人规划1.系统结构及规划机理系统结构及规划机理（1）知识库：用于存储某些特定领域的专家知识和经验）知识库：用于存储某些特定领域的专家知识和经验，包括机器人工作环境的世界模型、

19、状态、物体描述等事实和，包括机器人工作环境的世界模型、状态、物体描述等事实和可行操作或规则等。可行操作或规则等。（2）控制策略：包含综合机理，确定系统应当应用什么控制策略：包含综合机理，确定系统应当应用什么规则以及采取什么方式去寻找该规则。规则以及采取什么方式去寻找该规则。（3）推理机：用于记忆所采用的规则和控制策略及推理推理机：用于记忆所采用的规则和控制策略及推理策略。策略。（4）知识获取：首先获取某特定域的专家知识。然后用）知识获取：首先获取某特定域的专家知识。然后用程序设计语言把这些知识变换为计算机程序。最后把它们存入程序设计语言把这些知识变换为计算机程序。最后把它们存入知识库待用。知识

20、库待用。20/477.5 基于专家系统的机器人规划(5)解释与说明：通过用户接口，在专家系统与用户之间解释与说明：通过用户接口，在专家系统与用户之间进行对话，从而使用户能够输入数据、提出问题、知道推理结进行对话，从而使用户能够输入数据、提出问题、知道推理结果以及了解推理过程等。果以及了解推理过程等。2.任务级机器人规划三要素任务级机器人规划三要素（1）建立模型：世界模型。）建立模型：世界模型。（2）任务说明：定义状态及状态变换次序。）任务说明：定义状态及状态变换次序。（3）程序综合。）程序综合。3.ROPES机器人规划系统机器人规划系统21/477.6 轨迹规划简介 轨迹：机械手在运动过程中的

21、位移、速度和加速度。轨迹：机械手在运动过程中的位移、速度和加速度。轨迹规划：根据任务的要求，计算出预期的轨迹。轨迹规划：根据任务的要求，计算出预期的轨迹。在机械手运动学和动力学基础上，讨论在关节空间和笛卡尔空在机械手运动学和动力学基础上，讨论在关节空间和笛卡尔空间中机器人运动的轨迹规划和轨迹生成方法间中机器人运动的轨迹规划和轨迹生成方法 22/477.6 轨迹规划简介 例：例：NAO机器人检球动作。机器人检球动作。23/47群智能算法群智能算法群智能思想起源群智能思想起源24/47群智能算法群智能算法群智能思想起源群智能思想起源 复杂适应系统复杂适应系统(Complex Adaptive Sy

22、stem,CAS)理论理论：1994 年由年由 Holland 教授正式提出。教授正式提出。CAS中成员称为具有适应性的主体中成员称为具有适应性的主体,简称主体。简称主体。主体的适应性主体的适应性,是指它能够与环境以及其它主体进行交流，在交流的过是指它能够与环境以及其它主体进行交流，在交流的过程中程中“学习学习”或或“积累经验积累经验”，并且根据学到的经验改变自身的结构和，并且根据学到的经验改变自身的结构和行为方式。行为方式。CAS具有四个基本特点具有四个基本特点:（1）首先）首先,主体是主动的、活的实体。具有适应性的主体的概念把个体主体是主动的、活的实体。具有适应性的主体的概念把个体主动性提

23、高到了系统进化基本动因的位置主动性提高到了系统进化基本动因的位置,从而成为研究与考察宏观行为从而成为研究与考察宏观行为的出发点。的出发点。（2）其次）其次,个体与环境个体与环境(包括个体之间包括个体之间)之间的相互影响、相互作用是系之间的相互影响、相互作用是系统演变和进化的主要动力。相互作用是统演变和进化的主要动力。相互作用是“可记忆可记忆”的的,它表现为进化过程它表现为进化过程中每个个体的结构和行为方式的变化，以不同的方式中每个个体的结构和行为方式的变化，以不同的方式“存储存储”在个体内在个体内部。部。25/47群智能算法群智能算法群智能思想起源群智能思想起源 （3）再次）再次,这种方法不像

24、许多其他的方法那样这种方法不像许多其他的方法那样,把宏观和微观把宏观和微观截然分开截然分开,而是把它们有机地联系起来。而是把它们有机地联系起来。（4）最后）最后,这种建模方法还引进了随机因素的作用这种建模方法还引进了随机因素的作用,使它具有使它具有更强的描述和表达能力。随机因素的影响不仅影响状态更强的描述和表达能力。随机因素的影响不仅影响状态,而且影而且影响组织结构和行为方式。具有主动性的个体会接受教训响组织结构和行为方式。具有主动性的个体会接受教训,总结经总结经验验,并且以某种方式把并且以某种方式把“经历经历”记住记住,使之使之“固化固化”在自己以后在自己以后的行为方式中。的行为方式中。CA

25、S理论提供了模拟生物、理论提供了模拟生物、生态、生态、经济、经济、社会等复杂系统的社会等复杂系统的巨大潜力。巨大潜力。26/47群智能算法群智能算法群智能思想起源群智能思想起源 人工生命人工生命(Artificial Life,AL)是用来研究具有某些生命基本特征的人工是用来研究具有某些生命基本特征的人工系统。系统。近年来近年来,人工生命的研究发展非常快人工生命的研究发展非常快,在某些方面的研究已与传统在某些方面的研究已与传统的生物科学形成了互补。人工生命包括两方面的内容的生物科学形成了互补。人工生命包括两方面的内容:如何利用计算技术研究生物现象如何利用计算技术研究生物现象;如何利用生物技术研

26、究计算问题。如何利用生物技术研究计算问题。第二部分的内容的研究中，现已经有了很多源于生物现象的计算技巧，第二部分的内容的研究中，现已经有了很多源于生物现象的计算技巧，例如，人工神经网络是简化的大脑模型，遗传算法是模拟基因进化的过程例如，人工神经网络是简化的大脑模型，遗传算法是模拟基因进化的过程，目前这一类计算技术被统称为自然计算。群智能属于自然计算中的一类，目前这一类计算技术被统称为自然计算。群智能属于自然计算中的一类，它模拟另一种生物系统：社会系统，更确切地说，是模拟由简单个体组，它模拟另一种生物系统：社会系统，更确切地说，是模拟由简单个体组成的群落与环境以及个体之间的互动行为，这些模拟系统

27、利用局部信息从成的群落与环境以及个体之间的互动行为，这些模拟系统利用局部信息从而可能产生不可预测的群体行为。而可能产生不可预测的群体行为。27/47群智能算法群智能算法群智能思想起源群智能思想起源 群智能群智能(Swarm Intelligence,SI)：1992年由年由 Beni,Hack-wood 和和 Wang在分子自动机系统中提出。在分子自动机系统中提出。1999 年年,Bonabeau,Dorigo 和和 Theraulaz 在在 Swarm Intel-ligence:From Natural to Artificial Systems中对群智能进行了详中对群智能进行了详细的论述

28、和分析。细的论述和分析。2003年年 IEEE 第一届国际群智能研讨会在美国印第安纳州首府召第一届国际群智能研讨会在美国印第安纳州首府召开。开。群智能定义：任何一种由昆虫群体或其它动物社会行为机制而激群智能定义：任何一种由昆虫群体或其它动物社会行为机制而激发设计出的算法或分布式解决问题的策略均属于群智能。发设计出的算法或分布式解决问题的策略均属于群智能。28/47群智能算法群智能算法群智能思想起源群智能思想起源 Swarm 可被描述为一些相互作用相邻个体的集合体可被描述为一些相互作用相邻个体的集合体,蜂群、蚁蜂群、蚁群、鸟群、鱼群都是群、鸟群、鱼群都是Swarm的典型例子。社会性动物群体所拥有

29、的典型例子。社会性动物群体所拥有的这种特性能帮助个体很好地适应环境，个体所能获得的信息远的这种特性能帮助个体很好地适应环境，个体所能获得的信息远比它通过自身感觉器官所取得的多，其根本原因在于个体之间存比它通过自身感觉器官所取得的多，其根本原因在于个体之间存在着信息交互能力。信息的交互过程不仅仅在群体内传播了信息在着信息交互能力。信息的交互过程不仅仅在群体内传播了信息，而且群内个体还能处理信息，并根据所获得的信息，而且群内个体还能处理信息，并根据所获得的信息(包括环境信包括环境信息和附近其它个体的信息息和附近其它个体的信息)改变自身的一些行为模式和规范改变自身的一些行为模式和规范,这样这样就使得

30、群体涌现出一些单个个体所不具备的能力和特性就使得群体涌现出一些单个个体所不具备的能力和特性,尤其是对尤其是对环境的适应能力。这种对环境变化所具有的适应能力可以被认为环境的适应能力。这种对环境变化所具有的适应能力可以被认为是一种智能是一种智能,也就是说动物个体通过聚集成群而涌现出了智能。也就是说动物个体通过聚集成群而涌现出了智能。29/47群智能算法群智能算法群智能思想起源群智能思想起源 SI 的定义进一步推广的定义进一步推广（Bonabeau）:无智能或简单无智能或简单智能的主体通过任何形式的聚集协同而表现出智能行为智能的主体通过任何形式的聚集协同而表现出智能行为的特性。的特性。群智能理论还非

31、常不成熟群智能理论还非常不成熟,但已成为有别于传统人但已成为有别于传统人工智能中连接主义、工智能中连接主义、行为主义和符号主义的一种新的行为主义和符号主义的一种新的关于智能的描述方法关于智能的描述方法,并成为人工智能领域的新研究热并成为人工智能领域的新研究热点。点。30/47群智能算法群智能算法群智能理论群智能理论 James Kennedy 和和 Russell C.Eberhart 在在 2001 年出年出版的版的Swarm Intelligence 是群智能发展的一个重要历是群智能发展的一个重要历程碑。他们不反对程碑。他们不反对Bonabeau 关于关于 SI 的定义，赞同其定义的定义，

32、赞同其定义的基本精神，但反对定义中使用的基本精神，但反对定义中使用“主体主体”一词。一词。其理由其理由是是“主体主体”所带有的自治性和特殊性是许多所带有的自治性和特殊性是许多 Swarm的个的个体所不具备和拥有的，这将大大限制体所不具备和拥有的，这将大大限制 Swarm的定义范围的定义范围。Mark Millonas(1994)构建一个构建一个 SI 系统所应满足的五系统所应满足的五条基本原则条基本原则:Proximity Principle:群内个体具有能执行简单的时间群内个体具有能执行简单的时间或空间上的评估和计算的能力。或空间上的评估和计算的能力。31/47群智能算法群智能算法群智能理论

33、群智能理论 Quality Principle:群内个体能对环境群内个体能对环境(包括群内其它个体包括群内其它个体)的的关键性因素的变化做出响应。关键性因素的变化做出响应。Principle of Diverse Response:群内不同个体对环境中的某群内不同个体对环境中的某一变化所表现出的响应行为具有多样性。一变化所表现出的响应行为具有多样性。Stability Principle:不是每次环境的变化都会导致整个群体不是每次环境的变化都会导致整个群体的行为模式的改变。的行为模式的改变。Adaptability Principle:环境所发生的变化中环境所发生的变化中,若出现群体值若出现群

34、体值得付出代价的改变机遇得付出代价的改变机遇,群体必须能够改变其行为模式。群体必须能够改变其行为模式。32/47群智能算法群智能算法群智能理论群智能理论 以上五条原则现在成为了群智能的最基本理论，现有的群智能以上五条原则现在成为了群智能的最基本理论，现有的群智能方法和策略都符合这些原则。方法和策略都符合这些原则。Swarm Intelligence 最重要的观点是：最重要的观点是：Mind is social,也就是也就是认为人的智能是源于社会性的相互作用，文化和认知是人类社会性认为人的智能是源于社会性的相互作用，文化和认知是人类社会性不可分割的重要部分，这一观点成为了群智能发展的基石。不可分

35、割的重要部分，这一观点成为了群智能发展的基石。群智能模拟的是社会系统的变化，其最基本单位是群智能模拟的是社会系统的变化，其最基本单位是“敏因敏因”(Meme)，这一词由，这一词由 Dawkin 在在 The Selfish Gene中提出，它中提出，它是指思想文化传播中的基本单位，个体在社会中会根据环境来改变是指思想文化传播中的基本单位，个体在社会中会根据环境来改变自身的思想，敏因的传播途径是在个体与个体之间，在人类社会中自身的思想，敏因的传播途径是在个体与个体之间，在人类社会中它还可以在人脑与书本之间、它还可以在人脑与书本之间、人脑与计算机、人脑与计算机、计算机与计算机之间计算机与计算机之间

36、传播。当然，传播。当然，“敏因敏因”应该如何严格描述和定义还没有定论。应该如何严格描述和定义还没有定论。33/47群智能算法群智能算法群智能理论群智能理论 群智能研究的更进一步目标是对人类思想变化的社会行为的模拟。人群智能研究的更进一步目标是对人类思想变化的社会行为的模拟。人类心理中存在着群体性、习惯性、一致性类心理中存在着群体性、习惯性、一致性,常常是习惯性地遵循一些习俗常常是习惯性地遵循一些习俗和规则。无论什么时候和规则。无论什么时候,人们思想和行为总是因相互影响而变得非常近似人们思想和行为总是因相互影响而变得非常近似,道德规范以及文化的形成就是这种通过相互间影响而导致近似的结果。道德规范

37、以及文化的形成就是这种通过相互间影响而导致近似的结果。人类的社会思想行为并不简单类似鸟群或鱼群的行为人类的社会思想行为并不简单类似鸟群或鱼群的行为,人类思想的形成人类思想的形成过程是一种在高维认知空间的探索历程。过程是一种在高维认知空间的探索历程。两种思想意见在认知空间上聚两种思想意见在认知空间上聚集到一点上集到一点上,被称为被称为“一致一致”或或“认同认同”,而不是鸟群或鱼群系统中的而不是鸟群或鱼群系统中的“碰撞碰撞”。如果某人认同认知空间某个点。如果某人认同认知空间某个点,那么就努力靠近它那么就努力靠近它,反之则尽反之则尽量远离它量远离它,这里认知空间中的某个点就是某个人的思想。人类通过这

38、种社这里认知空间中的某个点就是某个人的思想。人类通过这种社会行为达成社会的共识会行为达成社会的共识:习俗、道德规范等。习俗、道德规范等。目前目前,群智能理论研究处于基本思想描述阶段群智能理论研究处于基本思想描述阶段,还未能提出一些较为明还未能提出一些较为明确的概念和定义确的概念和定义,尽管已经有人提出广义群智能的模型。尽管已经有人提出广义群智能的模型。34/47 蚁群算法蚁群算法(Ant Colony OptimizationACO)由由 Colorni,Dorigo 和和 Maniezzo 于于 1991 年提出年提出,它是通过模拟自然界蚂蚁社会的寻找食它是通过模拟自然界蚂蚁社会的寻找食物的

39、方式而得出的一种仿生优化算法。物的方式而得出的一种仿生优化算法。自然界种蚁群寻找食物时会自然界种蚁群寻找食物时会派出一些蚂蚁分头在四周游荡派出一些蚂蚁分头在四周游荡,如果一只蚂蚁找到食物如果一只蚂蚁找到食物,它就返回巢它就返回巢中通知同伴并沿途留下中通知同伴并沿途留下“信息素信息素”(pheromone)作为蚁群前往食物作为蚁群前往食物所在地的标记。所在地的标记。信息素会逐渐挥发信息素会逐渐挥发,如果两只蚂蚁同时找到同一食如果两只蚂蚁同时找到同一食物物,又采取不同路线回到巢中又采取不同路线回到巢中,那么比较绕弯的一条路上信息素的气那么比较绕弯的一条路上信息素的气味会比较淡味会比较淡,蚁群将倾向

40、于沿另一条更近的路线前往食物所在地。蚁群将倾向于沿另一条更近的路线前往食物所在地。ACO算法设计虚拟的算法设计虚拟的“蚂蚁蚂蚁”,让它们摸索不同路线让它们摸索不同路线,并留下会随并留下会随时间逐渐消失的虚拟时间逐渐消失的虚拟“信息素信息素”。根据。根据“信息素较浓的路线更近信息素较浓的路线更近”的原则的原则,即可选择出最佳路线。即可选择出最佳路线。群智能算法群智能算法蚁群算法蚁群算法35/47群智能算法群智能算法蚁群算法蚁群算法36/47 其中其中,和和 两个参数分别用来控制信息素和路径长度的相对重要两个参数分别用来控制信息素和路径长度的相对重要程度。当蚂蚁在所有城市走过一遍之后，路径上的信息

41、素浓度将变程度。当蚂蚁在所有城市走过一遍之后，路径上的信息素浓度将变为为:e(t+1)=(1-)e(t)+e 其中，其中，0 1 用于控制信息素随时间挥发的速度，用于控制信息素随时间挥发的速度，e是上次蚂蚁是上次蚂蚁经过此路段所留下的信息素，未经过则为经过此路段所留下的信息素，未经过则为 0。上式以及。上式以及e可以根据问可以根据问题进行设计。题进行设计。目前，目前，ACO算法已被广泛应用于组合优化问题中，在车辆调算法已被广泛应用于组合优化问题中，在车辆调度问题、度问题、机器人路径规划问题、机器人路径规划问题、路由算法设计等领域均取得了良好路由算法设计等领域均取得了良好的效果。的效果。由于由于

42、 ACO算法具有广泛实用价值，成为了群智能领域第算法具有广泛实用价值，成为了群智能领域第一个取得成功的实例，曾一度成为群智能的代名词，相应理论研究一个取得成功的实例，曾一度成为群智能的代名词，相应理论研究及改进算法近年来不断取得新的成果。及改进算法近年来不断取得新的成果。群智能算法群智能算法蚁群算法蚁群算法37/47 粒子群优化算法（粒子群优化算法（Particle Swarm OptimizationPSO)源于源于 1987 年年 Reynolds 对鸟群社会系统对鸟群社会系统boids的仿真研究，的仿真研究，boids 也是一个也是一个 CAS。在在 boids 中中,一群鸟在空中飞行一

43、群鸟在空中飞行,每个鸟遵守以下三条规则每个鸟遵守以下三条规则:（1）避免与相邻的鸟发生碰撞冲突）避免与相邻的鸟发生碰撞冲突;（2）尽量与自己周围的鸟在速度上保持协调和一致）尽量与自己周围的鸟在速度上保持协调和一致;（3）尽量试图向自己所认为的群体中心靠近。）尽量试图向自己所认为的群体中心靠近。仅仅通过使用这三条规则仅仅通过使用这三条规则,boids 系统就出现非常逼真的群体聚集系统就出现非常逼真的群体聚集行为行为,鸟成群地在空中飞行鸟成群地在空中飞行,当遇到障碍时它们会分开绕行而过当遇到障碍时它们会分开绕行而过,随后随后又会重新形成群体。不过又会重新形成群体。不过 Reynolds 仅仅将其作

44、为仅仅将其作为 CAS的一个实例的一个实例作仿真研究作仿真研究,而并未将它用于优化计算中而并未将它用于优化计算中,也无任何实用价值。也无任何实用价值。群智能算法群智能算法粒子群优化算法粒子群优化算法38/47群智能算法群智能算法粒子群优化算法粒子群优化算法39/47群智能算法群智能算法粒子群优化算法粒子群优化算法40/47群智能算法群智能算法粒子群优化算法粒子群优化算法41/47群智能算法群智能算法粒子群优化算法粒子群优化算法42/47群智能算法群智能算法粒子群优化算法粒子群优化算法43/47群智能算法群智能算法粒子群优化算法粒子群优化算法44/47群智能算法群智能算法人工鱼群算法人工鱼群算法45/47群智能算法群智能算法人工鱼群算法人工鱼群算法46/47群智能算法群智能算法与进化计算比较与进化计算比较47/47群智能算法群智能算法与进化计算比较与进化计算比较48/47群智能算法群智能算法与进化计算比较与进化计算比较