6章-计算智能-人工智能研究生课程

1、第6章 计算智能,1,6.1 神经网络 6.2 遗传算法 6.3 模糊计算 6.4 粒群优化 6.5 人工免疫 CI AI BI,AArtificial BBiological CComputational,6.1神经网络,2,3.5.1 神经网络的基本知识,(neural net),神经元、连接权值、阈值，激励函数、, 神经元模型(B-P), 激励函数（作用,非线性体现）,Sigmoid函数 f = 1/(1+ex ) 压缩映射，多阶连续可微,神经网络例子,x1 x2 Z 0 0 0 0 1 1 1 0 1 1 1 0,Yj=f( xi wij ) =U( xi wij ) w11 =5.2

2、4；w12 = 5.23； w21 = 6.68； w22 = 6.64； 1 = 8.01； 2 = 2.98； T1 = 10； T2 = 10； = 4.79,T1= U(0 5.24 + 0 5.23 8.01 )= U ( 8.01) =0 T2= U(0 6.68 + 0 6.64 2.98 )= U ( 2.98 ) =0 Z= U(0 )( 10) + (0 10) 4.79 )= U ( 4.79) =0 T1= U(0 5.24 + 1 5.23 8.01 )= U ( 2.85) =0 T2= U(0 6.68 + 1 6.64 2.98 )= U (3.66 ) =1

3、Z= U(0 )( 10) + (1 10) 4.79 )= U (5.21) =1,识别四个动物的神经网络例子,模式识别,四个动物的样本 (1) 某动物特征是暗斑点、黄褐色、有毛发、吃肉，它就是豹。 (2) 某动物特征是黄褐色、有毛发、吃肉、黑条纹，它就是虎。 (3) 某动物特征是不飞、黑白色、会游泳、有羽毛，它就是企鹅。 (4) 某动物特征是有羽毛、善飞，它就是信天翁。,暗斑点 黄褐色 有毛发 吃肉 黑条纹 不飞 黑白色 会游泳 有羽毛 善飞 编 码 动物名 1 111 0 0 0 0 0 0 1 0 0 0 豹 0 111 1 0 0 0 0 0 0 1 0 0 虎 0 000 0 1

4、1 1 1 0 0 0 1 0 企鹅 0 000 0 0 0 0 1 1 0 0 0 1 信天翁,结果,输入输 出 输出相近 暗 黄 毛 肉 纹 不飞 黑白 泳 羽 飞 豹 虎 企鹅 信天翁 1 0 1 0 0 0 0 0 0 0.8463 0.0245 0.048l 0.0950 豹 0 1 0 1 1 0 0 0 0 0.0200 0.9473 0.0204 0.0030 虎 0 0 0 0 1 1 1 1 1 0.0148 0.2133 0.8971 0.0978 企鹅 0 0 0 0 0 0 0 1 0 0.1156 0.0298 0.1262 0.6662 信天翁 1 1 1 0 0

5、 0 0 0 0 0.8677 0.0231 0.0647 0.071l 豹 0 0 0 0 0 0 0 0 0 0.1798 0.0283 0.0125 0.9043 信天翁 0 0 1 1 1 1 0 0 0 0.0140 0.9286 0.0368 0.0029 虎 1 0 0 1 0 0 0 0 0 0.8486 0.0193 0.0550 0.1618 豹 0 1 0 0 1 0 0 0 0 0.0241 0.9291 0.0358 0.0044 虎 0 0 0 0 0 0 1 0 1 0.0735 0.0296 0.6562 0.1502 企鹅 0 1 1 1 0 0 0 0 0

6、0.3394 0.4203 0.0317 0.0135 豹，虎 1 1 0 0 0 1 1 0 0 0.6774 0.0200 0.3668 0.0461 豹，企鹅 0 0 1 1 0 0 1 1 0 0.0455 0.2547 0.4704 0.0124 虎，企鹅 1 1 1 0 0 1 1 0 1 0.4067 0.0236 0.1170 0.0577 豹，企鹅,B-P神经网络,1 给定神经网络结构 （三层： 输入层（输入神经元=输入维数） 隐含层、（?） 输出层： （输出神经元=输出个数） 2 给定初始权值、阈值。 3 运用样本，按公式计算每个神经远的输出，直至输出神经元 4 求出误差

7、5 反向送回。 根据误差的大小（梯度下降，确定步长），修正权值、阈值 6 直至误差在允许范围内。 注意问题 收敛性（能否，速度） 局部最优问题（梯度）,BACK-PROPAGATION,神经网络特点,1)学习能力。学习能力是神经网络具有智能的重要表现，即通过训练可抽 象出训练本的主要特征，表现出强大的自适应能力。 2)分布式。信息则分散分布在神经元的联接上，神经元组合起来，就能从 宏观上反映一定的信息特征。对个别神经元和连接权值的损坏，并不会对 信息特征造成太大的影响，现了神经网络强大的鲁棒性和容错能力。 3)并行性。神经网络偏重对结构的模拟。各种神元在处理信息时是各自 独立的，它们分别接受输

8、入，作用后产生输出。并行计算可能用于适时 快速处理信息。 4)非线性。可有效地实现输入空间到输出空间的非线性映射。寻求输入到 出间的非线性关系模型，成为非线性系统研究的重要工具。 黑箱映射,6.2遗传算法,9, 生物学知识： 染色体、基因、基因座、 个体、种群、适应度、 物种选择、杂交、变异。 选择、杂交与变异3个主要的算子：,(genetic algorithmGA),物竞天择，适者生存, 1参数编码,10,遗传算法一般不能直接处理问题空间的参数，必须把它们转化成遗传空间 由基因按一定结构组成的染色体或个体，这种转换操作就称为编码。 (1) 完备性：问题的所有候选解都能被遗传空间中的点(染色

9、体)所表现 ； (2) 健全性：遗传空间的染色体能对应所有问题空间的候选解； (3) 非冗余性：染色体和候选解一一对应。 2初始种群的生成 遗传算法具有群体型操作的特点，必须为其准备一个由若干初始解组成的 初始种群。遗传算法以此为起点经过一代代进化直到终止，得到最后一代 (或种群)。初始种群中的个体一般是随机产生的。 初始种群的确定原则： (1)基于问题的先验知识，确定最优解所占空间在整个问题空间中的分布 范围，然后在此范围内设定初始种群； (2)先随机生成一定数目的个体，然后从中挑选出最好的个体加入到初始 种群中去。,110 01 00 10 11 010, 3适应度函数的设计,11,设计适

10、应度函数的主要方法是把问题的目标函数转换成合适的适应度函数 评价指标； 能满足强约束条件 4. 遗传操作设计 遗传操作包括选择、杂交与变异3个主要的算子： 确定选择算子的方法主要有： (1) Montecarlo方法，也叫赌轮方法； (2) 最佳个体保存方法； (3) 期望值方法； (4) 排序方法； (5) 联赛选择方法；, 4杂交算子,12,杂交算子是遗传算法中的核心操作算子，该算子与自然界生物基因的 重组的作用相当。 杂交操作就是把配好对的两个父本个体的部分结构加以替换重组， 而生成新个体的操作。基本的杂交算子有： (1)一点杂交(onepoint crossover)； (2)两点杂交

11、(two-point crossover)； (3)多点杂交(multi-point crossover)； (4)一致杂交(uniform crossover)等。 变异算子的功能就是对个体串的某些基因座上的基因值作变动。10，01） 5. 控制参数设定 (主要指种群的规模和采用的遗传操作的概率等)。,Schaffer涟漪函数,13,遗传算法例子MAX: f(x1,x2)=x12+x22,14,MAX: f(x1,x2)=x12+x22 x1,x2 (空间很小） 个体编号初始群体P(0) 适应度 f / f 选择次数(轮盘概率) 1 011 101 3534 f= 143 0.24 1 01

12、1101(1) 2 101 011 5334 fMAX =50 0.24 1 111001 (4) 3 011 100 3425 0. 17 0 101011 (2) 4 111 001 7 1 50 f均=35.75 0.35 2 111001 (4) 配对交叉点位置交叉结果变异点变异结果（子代P(1) ） 3 011001 4 011101 f= 235 3，5 1-2 3111101 5 111111 fMAX =98 7，7 3-4 5111001 2 111001 7，1 5111011 6 111010 f均=58.75 7，2,遗传算法的特点,15,(1) 以决策变量的编码作为运

13、算对象。可以适合一些无数值概念或很 难有数值概念。(步骤，颜色，） (2) 遗传算法直接以目标函数值作为搜索信息。 遗传算法仅使用由目标函数值变换来的适应度函数值，就可确定进一步 的搜索方向和搜索范围，无需目标函数的导数值等其他一些辅助信息。 搜索范围集中到适应度较高的部分搜索空间中，从而提高了搜索效率。 (3) 遗传算法同时使用多个搜索点的搜索信息。 （初始种群的位置，隐含并行性。） (4) 遗传算法使用概率搜索技术。 不同很多传统的优化算法往往使用的是确定性的搜索方法， 增加了其搜索过程的灵活性。,6.3 模糊计算,16,(思路方法）,“非此即彼”, “亦此亦彼”的现象。 不相容原理 人脑

14、的思维活动具有两重性 运用数学方法来描述模糊概念，其关键的思想是承认由于客观事物的差异所 引起的中介过渡的“不分明性”，允许“渐变的关系”，即承认一个集合可以有 部分属于它的元素，一个命题也可能部分为真和部分为假。 模糊搜索、模糊决策、模糊控制、模糊专家系统、模糊数据库、 模糊模式识别、模糊数字模拟电路，模糊神经网络以及 模糊计算机和模糊软件,17,6.3 模糊信息处理,3.7.1 模糊集合的基本概念 1 模糊子集的定义 定义给定论域U上的一个模糊子集A，对于任意uU，都指定了一个数 A(u)0，1，叫做u对A的隶属程度。 即映射：A(u)：U0，1uA(u) ,则A叫u对A的隶属函数 模糊子

15、集完全由其隶属函数所刻划。 例 1。 某人的个子高矮 例 2。如图所示.在此论域上定义一模糊子集A 表示“轴心轨迹为椭圆形这一模糊概念， 则各元素 U：a，b，c，d，e 对A的隶属度可以定为 a 0.9 ，b0.8，c0.4，d0.2，e0.0 用向量来表示A=(0.9 ，0.8，0.4，0.2，0),6.3.2 隶属函数的确定方法,18,3.7.2.1 专家打分法 专家打分法就是根据专家的经验，直接给予打分。方法表面上看起来是主观的，但是专家经验是状态在专家头脑中的客观反映，受客观的制约，实际上是客观的。 3.7.2.2 二元对比排序法 二元对比排序法就是将研究对象排成优先顺序，根据此优先

16、顺序建立模糊子集A的隶属值。A的隶属函数的大致轮廓就出来了。,0.25 0.50 1 2 3 4 o,3.7.2.3 模糊统计法,模糊统计法是通过模糊统计实验得到隶属函数，,6.3.3 常用的隶属函数类型,19,1) 正态型2) 型3) 戒下型4) 戒上型,6.3.4. 基本运算,20,定义设A，BF (U)，AB，AB，AC它们分别具有隶属函数 并集 交集 余集 例在例中，若定义。 A(0.9，0.8，0.4，0.2，0) (椭圆形) B(0.2，0.3，0.6，0.1，0) (双环椭圆形) 则AB (0.9，0.5，0.6，0.2， 0) (或椭圆或双环椭圆) AB (0.2，0.3，0.

17、4，0.1，0) (亦椭圆或双环椭圆) AC (0.1，0.1，0.6，0.8，0) (不是椭圆),6.3.5 模糊推理 -最大隶属判别原则,21,设A1，A2，AnF（U）。uoU若i 1，2，n ， 使Ai（uo）= maxA1(uo)，A2(uo)，Ain (uo) 则认为uo相对隶属于Ai。 在故障诊断中，已经认识的故障种类是有限的，且任何两种故障都可同时并发，所以难找全模糊子集，即被识别对象uo 有可能是A1(uo)，A2(uo)，Ain (uo)均较小， 但Ai（uo）= maxA1(uo)，A2(uo)，Ain (uo)总是存在的， 若用最大隶属原则判断，则必然存在误判的可能性。

18、 因此，在故障诊断中若要应用最大隶属原则，需加一条限制，即增加一个阈值T，Ai（uo）不仅满足式(2-13)，还需满足Ai（uo）T这样才能判断uo隶属于Ai。,6.4群优化算法,6.4.1 群智能和粒群优化概述 1群智能 群定义为某种交互作用的组织或Agent之结构集合。 群体中的个体在结构上是很简单的，群提供了个体间交换经验知识的通信通道，因为个体行为和全局群行为之间存在某种紧密的联系，而使它们的集体行为却可能变得相当复杂和完善。 个体的集体行为构成和支配了群行为，群行为又决定了个体执行其作用的条件。这些作用可能改变环境，因而也可能改变这些个体自身的行为及其地位。由群行为决定的条件包括空间

19、和时间两种模式。群行为不能仅由独立于其他个体的个体行为所确定。个体间的交互作用在构建群行为中起到重要的作用，个体间的交互作用帮助改善对环境的经验知识，增强了到达优化的群进程。,22,t=2时刻,个体的渺小，群体的伟大,2粒群优化概念,粒群优化(particle swarm optimization，PSO)算法是一种基于群体搜索的算法， 粒群优化中的粒子的个体是通过超维搜索空间“流动”的。粒子在搜索空间中的位置变化是以个体成功地超过其他个体的社会心理意向为基础的。 群中粒子的变化是受其邻近粒子(个体)的经验或知识影响的，一个粒子的搜索行为受到群中其他粒子的搜索行为的影响，粒群优化是一种共生合作

20、算法。建立这种社会行为模型的结果是：在搜索过程中，粒子随机地回到搜索空间中一个原先成功的区域。,23,t=2时刻,particle swarm optimization，PSO,3粒群优化算法,粒群优化是以邻域原理为基础 。群是粒子的集合，每个粒子的位置代表一个潜在的解答。每个粒子的位置按照其经验和邻近粒子的位置而发生变化，粒子在超空间流动，与最佳解答的接近度-适应度函数正比的速度矢量推动优化过程。 1个体最佳算法pbest每一个体只把它的当前位置与自己的最佳位置相比较。 2全局最佳算法 gbest 每个粒子能与其他粒子(个体)进行通信，形成一个全连接的社会网络，用于驱动各粒子移动的社会知识包

21、括全群中选出的最佳粒子位置。此外，每个粒子还根据先前已发现的最好的解答来运用它的历史经验。 3局部最佳算法lbest 每个粒子与它的邻近粒子通信。粒子受它们邻域的最佳位置和自己过去经验的影响。,24,星形(star) 邻域拓扑结构,3蚁群算法基本原理,蚁群的集体行为便表现出一种信息(外激素)正反馈现象：某一路径上走过的蚂蚁越多，则后来者选择该路径的概率就越大。蚂蚁个体之间就是通过信息的交流达到搜索食物的目的。,25,t=2时刻,t=1时刻,意大利学者-多里戈实验,实例-蚁群TSP系统模型1,模拟实际蚂蚁的行为。 m表示蚁群中蚂蚁的数量； dij (il，2.n)表示城市i和城市j之间的距离；

22、bi(t)表示t时刻位于城市i的蚂蚁个数； ij表示t时刻在ij连线上残留的信息量。 在初始时刻，设ij(0)C(C为常数)，各条路径上信息量相等。 蚂蚁k(k=l,2m)在运动过程中，根据各条路径上的信息量决定转移方向。 表示在t时刻蚂蚁由位置i转移到位置j 的概率：,26,应用-蚁群TSP系统模型2,上述蚁群系统模型是一个递归过程，计算机上实现过程可用伪代码如下： begin ncycle: = 0; bestcycle: = 0; ij=C; ij(0) =0; ij由某种启发算法定 tabuk=; while (not termination condition) ncycle =nc

23、ycle+1; for (index =0; indexn;index+ +) index表示当前已经走过的城市个数 for (k = 0; km;k+) 以概率选择城市j; j0,1,n-1tabuk; 将刚刚选择的城市j加到tabuk中 计算(index)，ij (index+n) 确定本次循环中找到的最佳路径 输出最佳路径及最佳结果 end,27,应用,电话网络路径选择 数据通信网络的路由优化 机器人建模和优化等。它们合作搬运的特性产生了机器人式的实现。 二次分配问题； 作业调度问题； 图表着色问题； 最短公超序问题； 蚁群算法源于对自然界中的蚂蚁寻找蚁巢到食物以及食物回到蚁巢的最短 路

24、径方法的研究。它是一种并行算法，所有“蚂蚁”均独立行动，没有监督 机构。它又是一种合作算法，依靠群体行为进行寻优；它还是一种鲁棒算 法，只要对算法稍作修改，就可以求解其他组合优化问题。,28,6.5人工免疫。,生物系统中的信息处理系统四种类型(人是最完美的系统) 脑神经系统(神经网络)、遗传系统(进化计算)、 免疫系统(人工免疫系统)和内分泌系统。 自然免疫系统是复杂自适应系统，免疫系统的主要作用是识别所有身体内的细胞，并将分类为自体（我要）和非自体（我不要）。免疫系统在外部病原体和身体自己的细胞之间进行辨别，产生抗体消除病原体，通过进化学习、记忆和模式识别能力，有效地使用多种机制防御外部病原体。免疫系统对外来抗原的识别过程是一个寻找能够和抗原结合力最大的抗体的过程。 免疫系统不依靠任何中心控制，具有分布式任务处理能力，具有在局部采取行动的智能，也通过起交流作用的化学信息构成网络，形成全局观念。,29,定义,抗原(antigen)是指所有可能错误的基因，即非最佳个体的基因； 疫苗(vaccine)