第六讲计算智能与群智能ppt课件.ppt

《第六讲计算智能与群智能ppt课件.ppt》由会员分享，可在线阅读，更多相关《第六讲计算智能与群智能ppt课件.ppt（81页珍藏版）》请在三一办公上搜索。

1、人工智能课程改革与建设第六讲 计算智能与群智能Computational Intelligence & Swarm Intelligence中南大学 刘丽珏,2011,本讲要点,涉及人工智能中新的研究内容和方向。许多算法、方法等比较抽象，不好理解，所以尽量以实例、动画，甚至游戏等方式激发学生兴趣，帮助其掌握知识。计算智能主要以神经计算为例。先通过简单的神经元展示神经元的基本功能分类，再介绍较深入的知识，借助游戏让学生对权值、阈值和变换函数有直观的了解。群智能属于较新的前沿领域，主要以原理介绍为主，拓宽学生视野，鼓励学生自己深入研究。,主要内容,引言神经计算模糊计算进化计算人工生命,引言,计算智

2、能是信息科学与生命科学相互交叉的前沿领域，是现代科学技术发展的一个重要体现。 计算智能涉及神经网络、模糊逻辑、进化计算和人工生命等领域，它的研究和发展正反映了当代科学技术多学科交叉与集成的重要发展趋势。,关于A，B，C 智能,贝兹德克于1994年提出一种表示ABC与神经网络(NN)、模式识别(PR)和智能(I)之间的关系，见下页图示： AArtificial，表示人工的、 符号的(非生物的) BBiological, 表示生物的 CComputational，表示计算的 计算智能是一种智力方式的低层认知，它与人工智能的区别只是认知层次从中层下降至低层而已。中层系统含有知识，低层系统则没有。,计

3、算智能与人工智能的区别和关系,计算智能系统与人工智能系统,当一个系统只涉及数值(低层)数据，含有模式识别部分，不应用人工智能意义上的知识，而且能够呈现出： (1) 计算适应性； (2) 计算容错性； (3) 接近人的计算速度； (4) 计算误差率与人相近。 则该系统就是计算智能系统。当一个智能计算系统以非数值方式加上知识，即成为人工智能系统。,神经计算研究的进展1943年麦卡洛奇和皮茨提出神经网络模型(称为MP模型)的概念。20世纪60年代威德罗和霍夫提出自适应线性元件。60年代末期至80年代中期，整个神经网络研究处于低潮。 80年代后期以来，人工神经网络研究得到复苏和发展，在模式识别、图像处

4、理、自动控制等领域得到广泛应用。,神经计算（Neural Computation）,人工神经网络特性人工神经网络（ANN）的特性,并行分布处理非线性映射通过训练进行学习适应与集成硬件实现 这些特性使得人工神经网络具有应用于各种智能系统的巨大潜力。,生物神经元,生物神经元结构细胞体树突轴突突触末端,生物神经元的工作机理,Refractory time,Action potential,Action potential 40mV Activation threshold -30mVRest potential -70mV Spike time 1-2msRefractory time 10-20m

5、s,神经元膜电位约为-70 毫伏，膜内为负，膜外为正，处于抑制状态 当神经元受到外部刺激时，膜内电位上升、膜外电位下降，当膜内外的电位差大于阈值电位（约+40毫伏）时，神经元产生冲动而进入兴奋状态。,人工神经元的结构,神经元单元由多个输入xi，i =1,2,.,n和一个输出y组成。中间状态由输入信号的权和表示，而输出为式中，j为神经元单元的偏置，wji为连接权系数，f为变换函数,神经元模型,常用变换函数,又称激励函数可以是线性或非线性函数常用函数包括二值型函数线性变换函数Sigmoid函数,二值型函数,a = 0, if n 0a = 1, if n 0MATLAB function: har

6、dlim,线性变换函数,a = nMATLAB function: purelin,Sigmoid 函数,a = 1/1+exp(n)MATLAB function: logsig,线性阈值单元,最简单的神经元为线性阈值单元(Linear Threshold Unit or Threshold Logic Unit, TLU)变换函数采用二值型函数,当输入的x1和x2位于直线上或上方时, w1x1+w2x2+b0，即net0，则y=1,TLU,TLU的基本功能为线性划分当有两个输入x1和x2时，若将x1和x2分别看成平面上的横轴和纵轴，则不同的x1和x2值将对应该平面上的不同点。,直线方程,若

7、令,当输入的x1和x2位于直线下方时，w1x1+w2x2+b0，即net0，则y=0,TLU,对于两个输入，TLU通过权值阈值决定的直线，将平面上的点划分为两类，分别对应神经元的兴奋状态和抑制状态。 对于三个输入，TLU则通过权值阈值决定的平面，将空间中的点划分为两类。 对于多个输入来说，权值阈值对应的就是一个超平面，将超空间中的点进行分类。称能通过单个TLU解决的问题为线性可分的。与、或、非等简单逻辑都可通过单个TLU实现。最早的神经网络感知器模型就是由单个TLU构成的,单个TLU的局限性,单个TLU只能解决线性可分问题，解决不了线性不可分问题。例：异或问题,异或逻辑真值表,输出0,输出1,

8、无论怎样，都不可能用一条直线将两类点分开,必须使用多个神经元网络来解决,人工神经网络的基本结构,神经网络是多个神经元以一定的拓扑结构互连组成的网络，按其结构可分为：递归（反馈）网络多个神经元互连组织成一个互连神经网络，如图a前馈（多层）网络具有递阶分层结构，同层神经元间不存在互连，如图b,a. 递归（反馈）网络 b.前馈（多层）网络,人工神经网络的基本结构,异或问题既可以用前馈网络实现，也可以用反馈网络实现。,人工神经网络的基本结构,异或问题的实现其实质就是通过多个神经元互联构成网络，形成多条直线对平面上的点进行分类，从而实现最终目的。,l1: b1+w11x1+w12x2=0, l2, l1

9、 or l2 ),l2: b2+w21x1+w22x2=0,人工神经网络的基本结构,当问题更加复杂，通过直线已经无法对空间进行有效划分时，则Sigmoid函数对应一个S型曲线，多个曲线相交可将空间进行更复杂的划分，完成所需任务,ANN的主要学习算法,有师学习：能够根据期望的和实际 的网络输出（对应于给定输入）间的 差来调整神经元间连接的强度或权。无师学习：不需要知道期望输出。增强学习：采用一个“评论员”来评 价与给定输入对应的神经网络输出的优度（质量因数）。增强学习算法的一个例子是遗传算法（GA）。,感知器学习,最简单的神经网络模型 “单层感知器”就是由一个权值可调的TLU构成的，可以区分线性

10、可分的模式权值的调整采用有师学习的方式进行感知器学习算法步骤输入：给定正例集合P和反例集合N，对所有x P， f (x) = 1 ，所有x N， f (x) = 0输出： w Rn+1,1.初始化权值为,2.随机选择 x P N 3.更新 w = w + (t-o)x（为学习常数，t为期望输出，o为实际输出）4.回到2直到当前权值对所有训练例误差为0,感知器学习:示例,w = (6,1) + (3, 1) (0,1) (7,2) = (4, 3),P = (6,1), (3, 1)N= (0,1), (7,2)1,x1,x2,w x 0w = w + (1-0)x =(-4, 3)+(6, -

11、1)=(2, 2),P = (6,1), (3, 1)N= (0,1), (7,2)1,感知器学习: 示例,w x 0w = w + (1-0)x =(-4, 3)+(6, -1)=(2, 2),P = (6,1), (3, 1)N= (0,1), (7,2)1,感知器学习:示例,w x 0w = w + (1-0)x =(2, 2)+(-3, 1)=(-1, 3),P = (6,1), (3, 1)N= (0,1), (7,2)1,w x 0w = w + (1-0)x =(-4, 3)+(6, -1)=(2, 2),感知器学习:示例,w x 0w = w + (1-0)x =(-1, 3)

12、+(6, -1)=(5, 2),P = (6,1), (3, 1)N= (0,1), (7,2)1,w x 0w = w + (1-0)x =(2, 2)+(-3, 1)=(-1, 3),感知器学习:示例,w x 0w = w + (1-0)x =(-1, 3)+(6, -1)=(5, 2),P = (6,1), (3, 1)N= (0,1), (7,2)1,w x 0w = w + (1-0)x =(5, 2)+(-3, 1)=(2, 3),感知器学习:示例,P = (6,1), (3, 1)N= (0,1), (7,2)1,w x 0w = w + (0-1)x =(2, 3)-(7, -

13、2)=(-5, 5),w x 0w = w + (1-0)x =(5, 2)+(-3, 1)=(2, 3),感知器学习:示例,P = (6,1), (3, 1)N= (0,1), (7,2)1,w x 0w = w + (0-1)x =(2, 3)-(7, -2)=(-5, 5),w x 0w = w + (1-0)x =(-5, 5)+(6, -1)=(1, 4),感知器学习:示例,其他神经网络学习方法将在机器学习中具体介绍,神经网络游戏Bug Brain,神经网络被广泛应用于自动控制、模式识别等众多领域让我们通过一个游戏，为瓢虫小姐构造一个大脑来看看神经网络的应用,游戏可分为实验室、瓢虫世

14、界、工厂、蠕虫世界等几关，每关难度增加,神经网络游戏Bug Brain,实验室游戏从最简单的实验室任务开始，在这里，玩家被要求完成包括与、或、非在内的各种任务，搭建能够完成相应任务的神经网络并测试成功后才能进入下一任务实验室所有任务完成后可进入下一关例：构造完成“或”逻辑的神经网络如图，所有权值阈值都可自行设置以完成任务,神经网络游戏Bug Brain,完成网络设计后，可进行测试，检验是否成功例如：“或”任务要求在两个开关中的任何一个被按下时灯能够亮，测试我们的网络成功,神经网络游戏Bug Brain,在进入瓢虫世界后任务变得更加实际，要求为瓢虫小姐来设计大脑，让她能够完成不同任务如：在有宽度

15、传感器（范围0100）的情况下，如何让瓢虫小姐既能吃到蚜虫又不会掉下树干？,扎德(Zadeh) 1965年提出了模糊集理论,模糊计算（Fuzzy Computation） 模糊集合,模糊计算结构原理,模糊计算的基本原理,进化计算（EvolutionalComputation）,生物种群的生存过程普遍遵循达尔文的物竞天择、适者生存的进化准则。种群中的个体根据对环境的适应能力而被大自然所选择或淘汰。进化过程结果反映在个体结构上，其染色体包含若干基因，体现了个体的外部特性与内部机理间的逻辑关系。生物通过个体间的选择、交叉、变异来适应大自然环境。20世纪60年代以来，如何模仿生物来建立功能强大的算法，

16、进而将它们运用于复杂的优化问题，越来越成为一个研究热点。进化计算正是在这一背景下蕴育而生的。进化计算包括遗传算法 、进化策略 、进化编程和遗传编程，本讲中着重讨论遗传算法。,遗传算法是模仿生物遗传学（孟德尔，摩尔根）和自然选择机理（达尔文），通过人工方式所构造的一类优化搜索算法，是对生物进化过程进行的一种数学仿真，是进化计算的最重要的形式。遗传算法为那些难以找到传统数学模型的难题指出了一个解决方法。进化计算和遗传算法借鉴了生物科学中的某些知识，这也体现了人工智能这一交叉学科的特点。,遗传算法（Genetic Algorithm）,遗传算法原理,编码与解码适应度函数 遗传操作,遗传算法编码与解码

17、,将问题结构变换为位串形式编码表示的过程叫编码；而相反将位串形式编码表示变换为原问题结构的过程叫解码或译码。把位串形式编码表示叫染色体，有时也叫个体。遗传算法的编码方法有二进制编码、浮点数编码方法、格雷码、符号编码方法、多参数编码方法等。,遗传算法适应度函数,体现染色体的适应能力，对问题中的每一个染色体都能进行度量的函数，叫适应度函数(fitness function)。对优化问题，适应度函数就是目标函数。例如，TSP（旅行商问题）的目标是路径总长度为最短，路径总长度可作为TSP问题的适应度函数：,遗传算法遗传操作,简单遗传算法的遗传操作主要有选择、交叉、变异三种。选择操作根据个体的适应度函数

18、值所度量的优劣程度决定它在下一代是被淘汰还是被遗传。一般地说，选择将使适应度较大(优良)个体有较大的存在机会，而适应度较小(低劣)的个体继续存在的机会也较小。,遗传算法交叉操作,交叉操作的简单方式是将被选择出的两个个体P1和P2作为父母个体，将两者的部分码值进行交换。假设有八位长的两个体，产生一个在1到7之间的随机数c，假如现在产生的是3，将P1和P2的低三位交换。 P1 P2,遗传算法变异操作,变异操作的简单方式是改变数码串的某个位置上的数码二进制编码表示的简单变异操作是将0与1互换：0变异为1，1变异为0TSP的变异操作：随机产生一个1至n之间的数k，对回路中的第k个城市的代码wk作变异操

19、作，又产生一个1至n之间的数w，替代wk ，并将wk加到尾部，得到：,遗传算法框图,人工生命 (ALife),人工生命(Artificial Life，AL)试图通过人工方法建造具有自然生命特征的人造系统。人工生命是生命科学、信息科学和系统科学等学科交叉研究的产物，其研究成果必将促进人工智能的发展。通俗地讲，人工生命即人造的生命，非自然的生命。然而，要对人工生命做出严格的定义，却需要对问题进行深入研究。,人工生命定义,1987年兰德提出的人工生命定义为：“人工生命是研究能够演示出自然生命系统特征行为的人造系统”。兰德在计算机上演示了他们的具有生命特征的软件系统，并把这类人造系统称为人工生命系统

20、。,人工生命研究意义,人工生命是自然生命的模拟、延伸与扩展，其研究开发有重大的科学意义和广泛的应用价值。开发基于人工生命的工程技术新方法、新系统、新产品。 为自然生命的研究提供新模型、新工 具、新环境。延伸人类寿命、减缓衰老、防治疾病。扩展自然生命，人工进化、优生优育。 促进生命、信息、系统科学的交叉发展。,人工生命研究内容,人工生命的研究内容大致可分为两类： (1) 构成生物体的内部系统，包括脑、神经系统、内分泌系统、免疫系统、遗传系统、酶系统、代谢系统等。 (2) 在生物体及其种群的外部系统，包括环境适应系统和遗传进化系统等。,人工生命示例,人工脑 波兰人工智能和心理学教授安奇布勒(And

21、rzej Buller)及一些日本学者在日本现代通讯研究所进化系统研究室对人工脑的研究，已取得重要进展。 计算机病毒 计算机进程 细胞自动机 人工核苷酸,群？,群智能,“群”的特征,相互作用的相邻个体的集合个体的行为简单既有竞争又有协作智能化的集体行为个体间不仅能够交互信息，还能够处理信息，根据信息改变自身行为。没有一个集中控制中心，分布式、自组织。作为群体协同工作时，能够突现出非常复杂的行为特征智能。,群智能的起源和发展,贝尼(Beni ),1989年，加利福尼亚大学的教授贝尼在其元胞自动机系统中首次提出群智能的概念,任何一种由昆虫群体或其它动物社会行为机制而激发设计出的算法，或分布式解决问

22、题的策略均属于群智能伯纳堡等 ，群智能：从自然到人工系统，1999,伯纳堡(Bonabeau),无智能或简单智能的主体，通过任何形式的聚集协同而表现出智能行为的特性 伯纳堡,群智能的起源和发展,艾伯哈特(Eberhart),2001年，肯尼迪和艾伯哈特出版了群体智能一书群智能发展的里程碑赞同伯纳堡关于群智能定义的基本精神，但反对“主体”一词，认为会限制“群”的定义范围最重要观点：智能源于社会性的相互作用群智能发展的基石认为暂时无法给出合适的定义群智能已成为有别于传统人工智能中连接主义和符号主义的一种新的关于智能的描述方法,典型算法蚁群算法（蚂蚁觅食）,基于群智能的优化算法,粒子群算法（蜂群或鸟

23、群觅食）,优点灵活性稳健性自组织潜在的并行性和分布式,已有的群智能理论和应用研究证明群智能方法是一种能够有效解决大多数优化问题的新方法,多里戈(Dorigo),蚁群算法,1992年由意大利学者多里戈提出模拟自然界中蚂蚁寻找从巢穴到食物的最佳路径的行为一种新型的优化算法,蚂蚁如何搜索路径？,双桥实验,1989年戈斯等研究蚂蚁觅食行为所做的实验,实验进行到4分钟时,实验进行到8分钟时,？,神奇的信息素,蚂蚁觅食过程随机移动遇到食物分泌信息素信息素：挥发性化学物质在搬运食物回家的路上留下信息素其他蚂蚁发现留有信息素的路径结束漫游，沿该路径移动，遇到食物同样开始分泌信息素,信息素会随着时间慢慢挥发，短

24、路径上的信息素相对浓度高,蚁群算法原理分析,基于蚂蚁寻找食物时的最优路径选择问题，可以构造人工蚁群，来解决最优化问题。人工蚁群中把具有简单功能的工作单元看作蚂蚁人工蚁群与自然蚁群相似之处：优先选择信息素浓度大的路径区别人工蚁群有一定的记忆能力，能够记忆已经访问过的节点；人工蚁群在选择下一条路径的时候是按一定算法规律有意识地寻找最短路径，而不是盲目的。,蚂蚁系统,多里戈在其博士论文中提出一种蚂蚁系统（Ant System，AS），以解决旅行商问题（TSP）TSP问题一个售货员希望去访问n个城市的每一个,开始和结束于v1城市。每两城市间都有一条直接通路, 怎么走才能使走过的路径最短呢？,可能的解有

25、(n-1)!/2个 ， (n-1)!/22n-2 ，(n4),蚂蚁在这些城市点之间移动两城市之间的信息素越多，蚂蚁就越有可能选择他们之间的路径能够成功完成遍历的蚂蚁会在路径上留下信息素，路越短，留下的信息素越多,蚂蚁系统,最初提出的AS有三种版本在不大于75城市的TSP中，这三种基本算法的求解能力比较理想但是当问题规模扩展时，AS的解题能力大幅度下降改进精英策略，对所有已发现的最好路径给予额外的增强蚁群系统(Ant Colony System，ACS)负反馈机制，当一只蚂蚁由一个节点移动到另一个节点时，该路径上的信息素被相应的消除一部分，以减小已选择过的路径再次被选择的概率,蚁群算法的应用,蚁

26、群算法具有广泛实用价值群智能领域第一个取得成功的实例一度成为群智能的代名词蚁群算法已被广泛应用于很多优化问题中聚类问题路由算法设计图着色问题车辆调度问题机器人路径规划问题,蚁群算法应用举例聚类问题,起源于对蚁群蚁卵的分类研究基本思想将待聚类数据随机地散布到一个二维平面内虚拟蚂蚁分布在这个空间内，并以随机方式移动当一只蚂蚁遇到一个待聚类数据时即将之拾起并继续随机运动若运动路径附近的数据与背负的数据相似性高于设置的标准则将其放置在该位置，然后继续移动重复上述数据搬运过程,HP公司和英国电信公司在90年代中后期都开展了这方面的研究设计了蚁群路由算法（Ant Colony Routing, ACR）,

27、蚁群算法应用举例路由问题,粒群优化算法,艾伯哈特(Eberhart),肯尼迪Kennedy),由艾伯哈特博士和肯尼迪博士于1995年提出模拟鸟群或蜂群的觅食行为基本思想：通过群体中个体之间的协作和信息共享来寻找最优解,鸟群觅食,一群鸟在随机的搜索食物。在这个区域里只有一块食物，所有的鸟都不知道食物在那。但是它们知道自己当前的位置距离食物还有多远。那么找到食物的最优策略是什么？,群体协作,蜂群或鸟群在觅食时有类似的行为,每只鸟抽象为一个无质量，无体积的“粒子” 每个粒子有一个适应度以模拟每只鸟与食物的距离每个粒子有一个速度决定它们的飞行方向和距离，初始值可随机确定每一次单位时间的飞行后，所有粒子

28、分享信息，下一步将飞向自身最佳位置和全局最优位置的加权中心,粒子群优化算法,初始化为一群随机粒子，通过迭代找到最优。每次迭代中，粒子通过跟踪“个体极值”和“全局极值”来更新自己的位置。,粒子群优化算法,速度更新公式：,位置更新公式：,粒子群优化算法流程,初始化一群粒子（群体规模为m），包括随机的位置和速度；评价每个粒子的适应度；对每个粒子，更新个体最优位置；更新全局最优位置；根据速度和位置更新方程更新粒子速度和位置；如未达到结束条件（通常为足够好的适应值或达到一个预设最大迭代次数） ，回到2。,粒子群优化算法示例,找函数的最大值,广泛运用在各类优化问题上,粒子群优化算法的应用,在军事领域中的应

29、用对巡航导弹的飞行高度进行优化不同飞行高度对巡航导弹的撞地概率和突破防空系统的成功概率有较大的影响,通过优化可以得到在突防阶段损失最小的最佳飞行高度。,车辆路径问题的应用邮政投递火车及汽车的调度港口装卸集装箱,粒子群优化算法的应用,相同点均为概率搜索算法。目的都不是为了模拟自然现象，而是利用他们的某些特点去解决实际问题。区别群智能优化算法的灵感来源于群居动物的社会行为，强调对社会系统中个体之间相互协作的模拟。进化计算是对生物演化中适者生存的模拟。,群智能优化算法与进化计算,不足数学理论基础相对薄弱，涉及的各种参数设置没有确切的理论依据。带有随机性，每次的求解不一定一样。当处理突发事件时，系统的反应可能是不可测的，这在一定程度上增加了其应用风险。,基于群智能的优化算法,谢谢大家,