人工智能课件 －04.计算智能

1、第4章 计算智能第一节 概述1、什么是计算智能 广义的定义：借鉴仿生学思想，基于生物体系的生物进化、细胞免疫、神经细胞网络等机制，用数学语言抽象描述的计算方法。 软计算。2、主要研究内容 以神经元网络、模糊计算和进化计算为核心。第一节 概述3、计算智能的重要特征 Bezdek的定义：一个系统是计算智能的，当它仅处理低级层次的数字信息，具有模式识别元件，没有使用在AI意义上的知识。 具有四个层次的特征： (1)适应性运算能力 (2)计算的容错能力 (3)人脑的计算速度 (4)与人脑一样决策与思维的正确性 从硬件上看，计算神经网络是低层次的，是由生物机器产生的模型，而ANN是中等层次的模型，是由计

2、算神经网络加知识组成，生物神经网络就是人脑。 从软件上看，计算智能是低层次的算法，它计算地推理，而传统AI是中等层次的模型，它是计算智能加知识，生物智能就是指人脑中的思维。第一节 概述4、AI与计算智能的关系 认为：计算智能是AI的一个子集，包含3个层次。输入复杂性程度人类知识+传感输入知识要点+传感数据计算+传感器BNN BPR BIANN APR AICNN CPR CIB组织A符号C数字复杂性Bezdek提出的智能的3个层次 第一层：生物智能(BI)，由大脑中的物理化学过程所反映出来。 第二层：人工智能(AI)，是非生物的，其基础是符号系统及其处理，并且来源于人的知识和有关数据。 第三层

3、：计算智能(CI)，是由计算机通过数学计算来实现，它的来源是数值计算和传感器所得的数据。 研究者认为：ANN、NC在计算智能中具有基石地位，计算智能由计算机通过数值计算来实现。第二节 模糊计算一、模糊理论1、模糊性 所谓模糊性是指客观事物在性态及其类属方面的不分明性，其根源是在类似事物间存在一系列过渡状态，它们互相渗透，互相贯通，使得彼此之间没有明显的分界线。例如，“某人个子高”，“较高”等术语。 模糊性是客观世界中某些事物本身所具有的一种特性，它与随机性有着本质区别。对随机性而言，事物本身的含义是明确的，只是在一定条件下可能发生，也可能不发生，而且事先不能确切预知；而模糊性反映的是事物本身是

4、模糊不清的。第二节 模糊计算2、集合与特征函数 在论域中，把具有某种属性的事物的全体称为集合。 集合中的每一种事物称为这个集合的一个元素。 集合通常用大写的英文字母表示；集合中的元素用小写字母表示。 由于集合中的元素都具有某种属性，因此，可用集合表示某一确定性概念，而且可用一个函数来刻画它，该函数称为特征函数。第二节 模糊计算定义：设A是论域U上的一个集合，对任意uU， 1, 当uA 令 CA(u) = 0, 当uA则，称CA(u)为集合A的特征函数。 特征函数CA(u)在u = u0处的取值CA(u0)称为u0对集合的隶属度。第二节 模糊计算3、模糊集与隶属函数定义：设U是论域，A是把任意u

5、A映射为0,1上某个值的函数，即 A : U0,1 u A(u)则称A为定义在U上的一个隶属函数，由A(u)所构成的集合A，称为U上的一个模糊集，A(u)称为u对A的隶属度。 模糊集完全由隶属函数刻画。第二节 模糊计算4、模糊集的表示方法 若论域是离散且有限的集时，其模糊集用 A = A(u1), A(un) 表示。其他的形式： A= A(u1)/u1+ A(un)/un A = A(ui)/ui第二节 模糊计算 若论域是连续的，模糊集可用实函数表示。例如，取U = 0,100，则“年轻”、“年老”两个集合的隶属函数为： 1 , 0u25 年轻(u) = 1 +( (u-25)/5 )2 -1

6、, 25u100 0 , 0u50 年老(u)= 1+ (5/(u-50) )2-1 , 50u100第二节 模糊计算5、模糊集的运算(1) 包含运算 设A,B是定义在U上的两个模糊集合，若对任意的uU，都有 B(u) A(u) 成立，则称A包含B。记为：B A第二节 模糊计算(2) 并、交、补运算 设A,B是定义在U上的两个模糊集合，分别称AB、AB为A与B的并集、交集；称A为A的补集或余集。对应的隶属函数计算为 AB: AB(u) = maxA(u) , B(u) AB: AB(u) = min A(u) , B(u) A: A(u) = 1 - A(u) 一般用 V 表示取极大，用 表示

7、取极小。第二节 模糊计算6、模糊集的水平截集定义：设A是定义在U上模糊集合，0，1则称普通集合 A= u | uU,A(u) 为A的一个水平截集。性质：(1) (AB) = AB (AB) = AB(2) 若10 分别是模糊集 A的核及支集。当Ker A0时，称A为正规模糊集合。A(u)u1KerAASuppA第二节 模糊计算分解定理和扩张原理：(1) 分解定理定理：设A为论域U上的一个模糊子集，A是A的截集， 0,1，则有 A = U A0,1其中，A为与A的乘积，可由与A的特征函数相乘得到，即CA(u) = , A(u) 0, A(u)第二节 模糊计算分解定理的直观理解：u1123 一个模

8、糊集合可以由无穷多个普通集合(A)数乘的并来构成，因此，可以把模糊集合转换为普通集合来分析。当在0,1区间内连续变化时，它们的外轮廓线将逼近A(u)。第二节 模糊计算(2)扩张原理(公理)问题：给定一个映射f: XY,y=f(x)，如果A是X上的一个模糊集合，那么它经过映射f在Y上生成的像f(A)是否是一个模糊集合？如果是，其隶属函数如何确定？反过来，如果B是Y上的一个模糊集合，B在X上的原像f-1(B)是否是一个模糊集合？如果是，其隶属函数如何确定？第二节 模糊计算(扩张原理) 设f是普通集合X到Y的映射，A是X上的模糊集合，则A在f下的像f(A)是Y上的模糊集合，其隶属函数规定为 A(x)

9、, f-1(y) f(A)(y)= 0, f-1(y) =x=f-1(y)若B是Y上的模糊集合，则B在f下的原像f-1(B)是X上的模糊集合，其隶属函数规定为f-1(B)(x) = B(f(x) 扩张原理的含义： 当A经过映射f生成f(A)时，其隶属函数可以无保留地传递过去，即，A和f(A)中相应元素的隶属度保持不变。若f不是单射，规定像的隶属度取几个原像隶属度中的最大值；若f不是满射时，规定Y中未被映射的元素的隶属度为0。第二节 模糊计算例、设X= x1,x2,x3,x4,x5 ,Y = y1,y2,y3, 映射f:XY,f(x1)=f(x2)=f(x3)=y1,f(x4)=f(x5)=y2

10、已知X上的模糊集合 则f(A) = 0.5/y1+0.8/y2+0/y3若已知 则 f-1第二节 模糊计算7、模糊度 模糊度是模糊集模糊程度的一种度量。 定义：设A是定义在U上的模糊集合，d是定义在U上的一个实函数，如果它满足下列条件 (1)对任意A,有d(A)0,1; (2)当且仅当A是一个普通集合时，d(A)=0; (3)若A的隶属函数A(u) 0.5,则d(A)=1; (4)若有A,B，且对任意uU，满足 B(u)A(u)0.5 或 B(u)A(u) 0.5 则有： d(B) d(A) (5)对任意A,有 A(A) = d(A)则称d为定义在U上的一个模糊度，d(A)称为A的模糊度。性质

11、： 任何模糊集的模糊度都是0,1上的一个数； 普通集合的模糊度为0； 越靠近时越模糊,隶属度为时最模糊； 模糊集与其补集具有相同的模糊度。第二节 模糊计算8、模糊数 例如术语“500左右”、“大约80%”等。 定义：如果实数域R上的模糊集A的隶属函数A(u)在R上连续且具有性质： (1) A是凸模糊集，即对任意的0,1，A的水平截集是闭区间； (2)A是正规模糊集，即存在一个uR，使A(u)=1；则称 A是一个模糊数。第二节 模糊计算 模糊数的隶属函数的图形是单峰的，且在峰顶使隶属度达到1。 例如，“u0左右”的数。1u0 模糊数可以用其隶属函数表示，例如“6左右”，可以用如下的隶属函数描述。

12、6(u) =e 10(u-6)20当| u 6 |3当| u 6 | 3第二节 模糊计算模糊数的运算： A+B: A+B(z) = V (A(x) B(y) )z=x+yA-B: A-B(z) = V (A(x) B(y) )z=x-yAB: AB(z) = V (A(x) B(y) )z=xyAB: AB(z) = V (A(x) B(y) )z=xy 运算实际上是它们相应的元素做对应的运算，而对它们的隶属度取极小，然后再对相同的元素取极大。第二节 模糊计算例如，设有： 3左右 2左右则，3左右 + 2左右 0.7/(2+3)+ 1 0.4/(3+1) + 1 1/(3+2) + 1 0.7

13、/(3+3) 0.7/(4+3)第二节 模糊计算9、模糊关系及其合成传统集合的关系： 笛卡尔积 设U和V是两个集合，则称 UV = (u,v)| uU,v V 为U与V的笛卡尔积。 关系 UV的一个子集，称为U到V的一个关系。 U VR第二节 模糊计算(1)、模糊关系定义：设Ai是Ui上的模糊集，称 A1An = (A1(u1) An(un)/(u1,un)为A1，An 的笛卡尔积。定义：在U1Un上的一个n元模糊关系R是指以U1Un论域的一个模糊集合。 R = R(u1,un)/(u1,un)其中，R(u1,un)/(u1,un)是模糊关系的隶属函数，它把U1Un上的一个元素映射为0,1上的

14、一个实数。第二节 模糊计算例如，设有一组学生：U = 张,李,王，他们对球类运动V = 篮球,排球,足球,乒乓球有不同的爱好，把他们对各种球类运动的爱好列成一张表，就构成了UV上的一个模糊关系R。张 李 0 0.6 0 0.5 王 0.5 0.3 0.8 0 篮球 排球 足球 乒乓球UV第二节 模糊计算(2)、模糊关系的合成定义：设R1,R2分别是UV,VW上的两个模糊关系，则R1与R2的合成是指从U到W的一个模糊关系。记为R1R2其隶属函数为： R1R2(u,w) = V R1(u,v) R2(v,w) 即，取R1的第i行元素，分别与R2的第j列对应元素相比较，两者中取较小者，然后再在所得得

15、一组最小数中取最大的一个，并以此作为R1R2 的第i行,第j列的元素。第二节 模糊计算例如，设 则 R1R2 第二节 模糊计算10、模糊变换定义：设 A = A(u1), A(un) 是论域U上的模糊集，R是UV上的模糊关系，则 A R = B 称为模糊变换。例如、设 A = 0.2,0.5,0.3 0.2 0.7 0.1 0 0.2 0.3 0.4 0.1 则， B = A R = 0.2, 0.4, 0.5, 0.1 第二节 模糊计算二、模糊推理1、模糊命题 “李是个年轻人” “张的身高约在左右” “他考上大学的可能性约在60%左右” 含有模糊概念、模糊数据或带有确定信程度的语句称为模糊命

16、题。第二节 模糊计算模糊命题的一般表示形式 x is A或者 x is A (CF) 其中，x是论域上的变量；A是模糊概念或模糊数，用相应的隶属函数描述；CF是可信度因子，可以是一个确定的数，也可以是一个模糊数。第二节 模糊计算2、模糊知识的表示 模糊产生式规则的一般表示形式： IF E Then H (CF,)例如， IF x is A Then B () IF x1 is A1 and x2 is A2 Then B (CF,) 推理中的证据也用模糊命题表示。第二节 模糊计算3、模糊匹配与冲突消解(1)模糊匹配方法：贴近度、语义距离、相似度.贴近度方法 设A、B是论域上的两个模糊集，则它们

17、的贴近度为： (A,B) = A B + ( 1 AB ) /2其中: A B = (A(ui) B(ui) ) AB = (A(ui) B(ui) )第二节 模糊计算例如、设 U = a, b, c, d, e, f A = 0.6, 0.8, 1, 0.8, 0.6, 0.4 B = 0.4, 0.6, 0.8, 1, 0.8, 0.6 则： A (A,B) = 0.8 + ( 1 0.6 )/2第二节 模糊计算. 语义距离 海明距离 d(A,B) = | A(ui) - B(ui)| / n 欧几里德距离 d(A,B) = (A(ui) - B(ui) )21/2 / n1/2第二节 模

18、糊计算. 相似度 最大最小法r(A,B)=minA(ui), B(ui) maxA(ui), B(ui) 算术平均值法r(A,B)=minA(ui), B(ui) (A(ui)+B(ui) )/2几何平均值法、相关系数法、指数法等。第二节 模糊计算(2) 冲突消解. 按匹配度大小排序. 按加权平均值排序基本思想：把求两个模糊概念的匹配度问题转化为一个对另一个隶属程度的计算。例、设 U = u1,u2,u3,u4,u5 C = 0.5/u3 + 0.8/u4 + 1/u5第二节 模糊计算并设有如下知识： r1: IF x is A then y is H1 r2: IF x is B then

19、y is H2 r3: IF x is C then y is H3用户提供的初始证据为 E is D则，A与D的匹配度按下式计算： match(A,D) = D(u1)/A(u1)+ D(u2)/A(u2) +D(u3)/A(u3)同样：match match第二节 模糊计算 因此，D分别与A、B、C的匹配度为match(A,D)、match(B,D)和match(C,D)，是一个模糊集。 比较这些匹配度的大小，以确定相应知识被应用的顺序。 计算每个匹配度的加权平均值AV，根据AV的大小来确定知识的应用顺序。 AV(match(A,D)= 同理： AV(match AV(match第二节 模

20、糊计算4、模糊推理的基本模式(1)模糊假言推理 设，有规则 IF x is A Then y is B若有A，且A 可以和A模糊匹配，则可推出y is B。称为模糊假言推理知识：IF x is A Then y is B证据： x is A 结论： y is B第二节 模糊计算(2)模糊拒取式推理 设，有规则 IF x is A Then y is B若有B，且B 可以模糊匹配B，则可推出x is A。称为模糊拒取式推理。知识：IF x is A Then y is B证据： y is B 结论： x is A第二节 模糊计算(3)模糊三段论推理 若由 IF x is A Then y is

21、B IF y is B Then z is C可以推出 IF x is A Then z is C则称为模糊三段论推理。第二节 模糊计算5、简单模糊推理 知识中只含简单条件，且不带可信度因子。推理： 对于知识 IF x is A Then y is B首先要构造出A和B之间的模糊关系R，然后通过R与证据的合成求出结论。 如果已知证据是 x is A，且A与A 模糊匹配，则通过合成运算 B = A R, 求出B。 如果已知证据是 y is B，且B与B模糊匹配，则通过合成运算 A = RB, 求出A。第二节 模糊计算 推理的关键是如何构造R。 扎德方法、麦姆德尼方法、米祖莫托方法等。 条件命题的

22、极大极小规则(Rm)扎德的两种方法 条件命题的算术规则(Ra)第二节 模糊计算设， A = A(u)/u B = B(v)/v Rm = (AB)( AV ) = (A(u)B(v) )(1 - A(u) )/(u,v) Ra = (AV ) (UB) = 1(1 - A(u) + B(v) )/(u,v) :有界和算子，A B = min 1, A(u) + B(u) 第三节 粗糙集理论 粗糙集理论的基本思想：使用等价关系将集合中的元素进行分类，生成集合的某种划分，与等价关系相对应。根据等价关系的理论，同一分组（等价类）内的元素是不可分辨的，对信息的处理可以在等价类的粒度上进行，由此可以达到

23、对信息进行简化的目的。第三节 粗糙集理论粗糙集的直观理解:属性(Attribute)a1(姓名)a2(性别)a3(年龄)a4(出生地)记录(Record)R1R2R3R4R5张三李四王五赵六刘七男女男女男2021202319北京上海北京广州重庆一个关系数据库表第三节 粗糙集理论 该表用集合论描述为一个二元关系 S=(U,A) U = R1,R2,R3,R4,R5 A = a1,a2,a3,a4 在该表中，如果只看某些属性，一些记录是无法区分的（等价的），即不同记录在被考虑的属性上具有相同的值。例如、属性集合a2,a3,a4，则U中的个体R1和R3是无法区分的。 因此，A中的任何一个属性子集都可

24、以对U进行分类。如上属性把U分类为 R1,R3,R2,R4,R5第三节 粗糙集理论 设 X U ，X= R2,R3,R4 B A ，B = a2则 X关于属性a2的值是 女、男、女即，X既不能说明是“男”的集合，也不能说明是“女”的集合或“男,女”的集合(因为，有两个个体没有被包含)。因此，子集X对于a2属性是不可定义的，即是粗糙的，X是粗糙集。 如果：X=R2,R4、或X=R1,R3,R5、或X=R1,R2,R3,R4,R5，则 X对a2属性不是粗糙的。第三节 粗糙集理论一、粗糙集理论的基本概念1、二元关系 笛卡尔积的子集。2、等价关系 若集合A上的二元关系满足，(1)自反性：xRx；(2)

25、对称性：xRy=yRx；(3)传递性：xRy,yRz=xRz；则称R是等价关系。3、等价类 对于A中的元素a，A中所有与a关于R等价的元素组成的集合x|xRa称为a的等价类，记为：aR，或a第三节 粗糙集理论4、等价划分 设，A是非空集合，R是A上的一个等价关系，R的等价类集合 aR|aA称为A上的等价划分。记为A/R。5、可定义集 R的一个等价类称为A的一个原子集；一个或多个原子集的并，称为A的一个可定义集，空集也是一个可定义集，集合Def(A)表示全体可定义集。第三节 粗糙集理论例、集合A =a,b,c,d,e,f, A上二元等价关系 R= (a,a),(b,b), (c,c), (d,d

26、), (e,e), (f,f), (a,b),(b,a), (a,c), (c,a),(b,c),(c,b),(d,e),(e,d) 则R上所有的等价类为： a=b=c =a,b,c;d=e=d,e;f=f a,b,c、d,e、f都是A的原子集，构成A的一个划分：A/R= a,b,c,d,e,f A的所有可定义集为：Def(A)=, a,b,c,d,e,f , a,b,c,d,e, a,b,c,f,d,e,f,A 第三节 粗糙集理论6、近似空间 近似空间S是一个四元组：S=。 其中，U是对象集合(论域)，R=CD是属性集合，子集C和D分别称为条件属性集和结果属性集；V是属性取值集合； f:UR

27、V是一个信息函数。 可以根据任一属性或属性集合对论域进行划分，因此，R上任一属性或属性集合都可以看成是U上的一个等价关系。属性集合R的所有等价类集合称为基本知识，相应的等价类称为基本概念,f指定U中的每个对象的属性值。第三节 粗糙集理论 RU头痛流鼻涕体温流感x1是是正常否x2是是高是x3是是很高是x4否是正常否x5否否高否x6否是很高是医疗诊断系统部分数据表格例、第三节 粗糙集理论 按单个属性，例如“头痛”的划分表示为 U/头痛= x1,x2,x3,x4,x5,x6 按两个属性，例如“头痛,流鼻涕”的划分表示为 U/头痛和流鼻涕=x1,x2,x3,x4,x6,x5 论域U的条件属性集C=头痛

28、,流鼻涕,体温，结果属性集D = 流感；属性头痛、流鼻涕的值域是是,否，体温的值域是正常,高,很高。 信息函数f将每个对象的属性取值映射到具体的属性值上，例如f(x1,头痛) = “是”。第三节 粗糙集理论7、不可分辨关系 对于近似空间S=，设PR，P，P中所有等价关系称为P上的不可分辨关系,记为 ind(P)。8、划分细分 对近似空间S=，若P,Q两个二元关系满足PQ，则Q上的不可分辨关系ind(Q)是P上的不可分辨关系ind(P)的划分细分。例如、P=头痛,Q =头痛,流鼻涕则 ind(Q)是ind(P)的划分细分，粒度更小。X1 x2 x3X4 x5 x6X1 x2 x3X5 x4 x6

29、ind(P)ind(Q)第三节 粗糙集理论9、粗糙集(Rough集) 对近似空间S=，称XU为U上的一个概念，当X是属性子集R所确定的U上的不分明集的并时，即X是R可定义的，R的可定义集也称为R的精确集，否则X是R不可定义的，R的不可定义集称为R的非精确集或Rough集。 例如，集合X=x2,x3,x4,x5是条件属性子集R=头痛,流鼻涕不可定义的，是R的Rough集，因为根据R，对象x1,x2,x3是不可分辨的，x4,x6是不可分辨的，所以不能根据R来对所有的对象实例是否属于集合X作出精确判断.第三节 粗糙集理论10、上近似、下近似 设，XU，X关于R的下近似R-(X)和上近似R-(X)分别

30、定义为： R-(X) = xRU/R | xRX -所有元素在X中 R-(X) = xRU/R | xRX-部分元素在X中11、边界、正域、负域 集合 BNR(X) = R-(X) - R-(X) 称为X的R边界； POSR(X) = R-(X) 称为X的R正域； NEGR(X) = U - R-(X) 称为X的R负域。第三节 粗糙集理论例、属性子集R = 头痛,流鼻涕,集合X=x2,x3,x5是一个R的Rough集，因此，集合X的上近似、下近似、边界、正域。由U|ind(R)=x1,x2,x3,x4,x6,x5,令R1= x1,x2,x3, R2=x4,x6,R3=x5,则XR1=x2,x3

31、,XR2=，XR3=x5因此得到： R-(X) = R1R3 = x1,x2,x3,x5 R-(X) = R3 = x5 POSR(X) = R-(X) = x5 BNR(X) = R1= x1,x2,x3第三节 粗糙集理论12、R-(X),R-(X)是集合X U关于等价关系R的上近似和下近似，若R-(X) R-(X)，即X是不可定义集，则有(1)如果R-(X)且R-(X)U，称X为R粗糙可定义的；(2)如果R-(X) =且R-(X)U，称X为R内不可定义的；(3)如果R-(X)且R-(X)=U，称X为R外不可定义的；(4)如果R-(X)=且R-(X)=U，称X为R全不可定义的。第三节 粗糙集

32、理论 当R-(X)= R-(X)时，集合X的边界为空，根据R可以完全地判断任意元素是否属于X，即X时确定；若边界不为空，根据R则有部分元素不能确定是否属于X；若是可定义的，则可确定U中的部分元素是否属于X或X；若X是R内不可定义的，则可以确定U中的部分元素是否属于X，但不能确定U中任何元素是否属于X；若X是R外不可定义的，则可以确定U中部分元素是否属于X,但不能确定U中任何元素是否属于X;若是全不可定义的，则不能确定U中的元素是否属于X或X。第三节 粗糙集理论13、设 X U，X关于R的近似度定义为： dR(X) = | R-(X) | / | R-(X) | 近似质量定义为： rR(X) =

33、 1 - | R-(X) | / |U| 粗糙度定义为： R(X) = 1 - | R-(X) | / | R-(X) | 近似度表示集合X中的元素有多大的概率确实属于该集合；近似质量描述了处理知识分类质量的度量；粗糙度反映了知识的不完全程度。第三节 粗糙集理论14、粗糙集的特点(1)粗糙集不需要先验知识；(2)粗糙集理论是一个强大的数据分析工具。(3)粗糙集和模糊集描述了不完备知识的两个方面.第三节 粗糙集理论二、粗糙集信息处理的方法与过程原始信息表数据预处理决策表约简数据推理新规则获取核心是数据预处理、决策表约简、数据推理。第三节 粗糙集理论1、数据预处理 原始数据的采样、收集、整理。 (

34、1)决策表的补齐 (2)数据离散化2、数据表约简 约去过剩的条件属性，用最少的属性区分不同的决策,提供同样多的信息，使决策表的决策属性和条件属性的依赖关系不发生变化。内容包括属性约简和值约简。3、数据推理 使用粗集的方法进行分析和预测。第三节 粗糙集理论例、数据和属性约简 设 S = ( U,A,V,)，其中，U=x1,x2,x8，属性集A=c1,c2,c3,c4，V1=V2=V3=1,2,3，V4=1,2。Uc1c2c3c4X1X2X3X4X5X6X7x811112233121222331212113311111122S的函数第三节 粗糙集理论则，U/c1=x1,x2,x3,x4,x5,x6

35、,x7,x8 U/c2=x1,x3,x2,x4,x5,x6,x7,x8 U/c3=x1,x3,x5,x6,x2,x4,x7,x8 U/c4=x1,x2,x3,x4,x5,x6,x7,x8 U/A =x1,x3,x2,x4,x5,x6,x7,x8则数据压缩后：U/Ac1c2c3c4x1,x3x2,x4x5,x6x7,x81123122312131112第三节 粗糙集理论 设S = ( U,A,V,)，对所有的aA，如果，RA=RAa，则称属性a是多余的。 属性c4是多余属性。 最简压缩表为：c1c2c3112312231213第四节 遗传算法 进化计算-模仿生物机理而建立的一类计算方法。 包括：

36、遗传算法、进化策略、进化编程、粒群算法、蚁群算法、免疫计算等。 遗传算法是模仿生物遗传学和自然选择机理，通过人工方式构造的一类优化搜索算法，是对生物进化过程进行的一种数学仿真，是进化计算的一种最重要形式。使用遗传算法可以解决使用传统数学方法难以解决的问题。第四节 遗传算法一、遗传算法的基本机理编码和生成初始群体对群体中的个体适应度进行评估满足终止条件选择交叉变异终止进化进程输出最终结果是否第四节 遗传算法 编码 初始群体设定遗传算法中的5个基本要素 适应度函数设计 遗传操作设计 控制参数设定第四节 遗传算法例：用遗传算法求函数f(x) = x2 , x0,31的最大值。1、编码编码的基本策略：

37、(1)完备性(2)健全性(3)非冗余性 把变量x编码为5位长的二进制无符号整数表示形式。第四节 遗传算法2、初始群体的生成关键问题：(1) 群体规模(2) 进化过程中各代规模如何维持 设定初始群体的大小为 n=4,即初始群体包含4个串，采用随机方法生成。 例如： 01101 - 13 11000 - 24 01000 - 8 10011 - 19第四节 遗传算法3、适应度函数设计 遗传算法在搜索过程中一般不需要其他的外部信息，仅用评估函数来评估个体或解的优劣，并作为以后遗传操作的依据。 适应度函数设计的好坏直接影响到遗传算法的性能。一般应根据具体的问题进行设计，常用做法是将目标函数映射成适应度

38、函数，并取最大化问题。 根据函数f(x) = x2的值来评估群体中的个体。第四节 遗传算法4、选择(复制) 选择操作的目的是为了从当前的群体中选出优良的个体，是它们有机会作为父代为下一代繁衍子孙。判断的准则是各自的适应度函数。 常用的选择方法有轮盘赌选择、排序选择、锦标赛选择等。第四节 遗传算法采用轮盘赌方法： 首先计算群体中所有个体的适应度总和(f)，再计算每个个体的适应度所占的比例(fi/f)，并以此作为相应的选择概率。例如： f(x) fi/f 01101 13 169 0.14 10011 19 361 0.31 被选中的个体是01101、11000、10011，其中，11000被复制

39、2次,个体01000被淘汰.第四节 遗传算法5、交叉 设计要点：满足交叉算子的评估准则，即保证前一代的优秀个体的性状能在新个体中得到遗传和继承。 基本的交叉算子： (1)一点交叉 (2)二点交叉 (3)多点交叉 (4)一致交叉第四节 遗传算法采用一点交叉： 简单的交叉分两步进行：首先对选择下来的个体进行随机配对；其次，在配对个体中随机设定交叉处，进行交叉生成新的个体。例如： 新个体 0110 1 01100 - 12 1100 0 11001 - 25 11 000 11011 - 27 10 011 10000 - 16第四节 遗传算法6、变异 变异操作的目的：具有局部的随机搜索能力；维持群

40、体的多样性，以防止出现未成熟收敛现象。 常用的变异算子： (1)基本变异算子 随机挑选一个或多个位(基因座)，并对这些基因座的值做变动； (2)逆转算子 随机挑选两个逆转点，将这两个逆转点间的基因值逆向排列。第四节 遗传算法例如： 变异操作按位进行，即把某一位由0变为1，由1变为0。通常变异的概率Pm都取得很小。 例如，取 Pm，由于群体中共有20位，所以有0.001 位变异。第四节 遗传算法编号初始群体X值适应度f(x)=x2选择概率实际计数选择后交叉处新一代个体X值1 01101 13 169 0.14 1 0110 1 01100 122 11000 24 576 0.49 2 1100

41、 0 11001 253 01000 8 64 0.06 0 11 000 11011 274 10011 19 361 0.31 1 10 011 11000 16计算过程总结第四节 遗传算法二、遗传算法的收敛性1、遗传算法收敛性的定义 渐进收敛(针对整个群体进行的定义) 两种定义 概率定义(针对群体中的个体进行的定义)t则称算法收敛到x0。经典遗传算法不具有渐进收敛的性质。(1)渐进收敛定义：若算法在t时刻的种群满足： lim xt = x0 x0X第四节 遗传算法(2)概率收敛定义：设Zt为t时刻种群中所包含的个体的适应度函数的最大值，f*为适应度函数f(x)在所有可能的个体所组成的集合

42、X中所取的最大值。若Zt满足： lim P Zt = f*=1t则称算法收敛到最优解。 在这个定义下，经典遗传算法不会收敛到最优解，但如果在遗传算法中保留每一代的最佳个体，则算法将收敛到最优解。第四节 遗传算法2、未成熟收敛 未成熟收敛是遗传算法中不可忽视的问题，主要表现在两个方面：(1)群体中所有个体都陷于同一极值而停止进化；(2)接近最优解的个体总是被淘汰，进化过程不收敛。第四节 遗传算法导致未成熟收敛的因素：(1)在进化初始阶段，生成了具有很高适应度的个体X；(2)在基于适应度比例选择下，其他个体被淘汰，大部分个体与X一致；(3)相同的两个个体进行交叉，未生成新的个体；(4)通过变异或逆

43、转所生成的个体适应度高，但数量少，所以被淘汰的概率很大；(5)群体中大部分个体都处于与X一致的状态。克服对策：(1)提高变异概率；(2)调整选择概率；(3)合适定标(4)维护群体中个体的多样性。 需要在算法过程中，分阶段、交替使用这些策略。第四节 遗传算法三、遗传算法的基本原理1、模式定理(1)模式 模式是一个描述字符串集的样板，该字符串集中的串的某些位置上存在相似性。 对二进制串，定义为：基于三值字符集0,1,*所产生的能描述具有某些结构相似性的0、1字符串集的字符串称为模式。 例如，模式“ 000* ”，描述了 0000和0001 遗传算法中串的运算实质上是模式的运算。第四节 遗传算法(2

44、) 模式定理 模式阶 模式H中确定位置的个数称为该模式的阶，记为O(H)。 例如，011*1* 的阶为4，*的为0 定义距 模式H中第一个确定位置和最后一个确定位置之间的距离称为该模式的定义距，记为(H)。 例如、011*1*的定义距为4，0*的为0第四节 遗传算法 模式定理 在遗传算子选择、交叉和变异的作用下，具有低阶、短定义距以及平均适应度高于群体平均适应度的模式在子代中将得以指数级增长。 这种性质有利于找到最优解？。第四节 遗传算法2、积木块假设 定义：具有低阶、短定义距以及高适应度的模式称为积木块。 积木块假设：积木块在遗传算子的作用下，相互结合，能生成高阶、长距、高平均适应度的模式，

45、可最终生成最优解。 一个问题能否用遗传算法求解，取决于问题编码是否满足积木块假设，满足者用遗传算法求解效率较高，不满足者效率较低，甚至找不到满意解。第四节 遗传算法3、欺骗问题 遗传算法运行过程具有将低阶、短定义距和高适应度的模式重组成高阶模式的趋势。如果在低阶模式中包含了最优解的话，则遗传算法就可能找出它。但是低阶、高适应度的模式可能没有包含最优解，因此，遗传算法可能就会收敛到一个次优解。 定义(竞争模式)： 若模式H与H中，*的位置完全一致，但任一确定位的编码均不同，则称H与H互为竞争模式。第四节 遗传算法 定义(欺骗性)：设f(X)的最大值对应的X集合为X*，H为一包含X*的m阶模式。H

46、的竞争模式为H，且f(H)f(H),则f为m阶欺骗问题。 当m=l时，模式中不包含*，所以不存在欺骗问题。例、对3位二进制编码的模式，如果f(111)为最大值，如果下面的任意一个不等式成立，将存在欺骗问题。 f(*1)f(*0), f(*1*)f(*0*), f(1*)f(0*) f(*11)f(*00), f(1*1)f(0*0), f(11*)f(00*) f(*11)f(*01), f(1*1)f(0*1), f(11*)f(01*) f(*11)f(*10), f(1*1)f(1*0), f(11*)f(10*)第四节 遗传算法 欺骗性的化解： 欺骗性的产生与适应度函数的设计和调整，编

47、码方式有关。 一般的规则是适应度函数与编码方式增大的趋势应保持一致，并采用变异算子，编码方式满足积木块假设。第五节 进化策略一、进化策略的基本算法构成 进化策略的基本算法构成类似于遗传算法的构成形式，通常也是由编码、初始群体生成、适应度计算、进化操作组成。 与遗传算法的主要区别是进化算子的不同选择，在遗传算法中主要采用交叉进行新个体的产生，而变异算子是辅助手段；而进化策略主要采用变异算子来生成新个体，而交叉算子则较少使用。第五节 进化策略1、个体的表示方法 在进化策略中，搜索空间是一个n维空间。因此，搜索点就是一个n维向量xRn。 个体的一般表示(三元表示)： X=x,=(x1,xn),(1,

48、 n),(1,n) 取连续值的向量x由两部分组成 微小的变动量 微小由步长Rn和回转角Rn(n+1)/2组成，服从正态分布。第五节 进化策略2、初始群体的产生 由个个体组成，采用随机方法产生。3、适应度函数 直接采用目标函数作为适应度函数，不进行任何变换处理。 f(x) = F(x)4、变异算子 变异操作是产生新个体的主要方法，变异规则为 = iexpt N(0,1) + t Ni(0,1) xi = xi + N(0,)其中，N(0,1)表示均值为0,方差为1的正态随机变量。第五节 进化策略5、交叉算子 是一种辅助手段6、选择算子两种方法：(1)从个个体中选择出个适应度最高的个体。(2)将个

49、父个体和其所产生的个子代个体合并在一起，并从+ 个中选择个适应度最高的个体。第五节 进化策略二、进化策略与遗传算法的区别(1)研究领域不同。 进化策略-数值优化方法 遗传算法-自适应搜索方法(2)表示个体的方法不同 进化策略-浮点向量表示 遗传算法-二进制向量(3)选择过程不同(4)复制参数不同 进化策略-时时改变 遗传算法-保持恒定第六节 进化编程(进化规划)一、进化规划的基本算法构成1、个体的表示方法 在进化编程中，搜索空间是一个n维空间。因此，搜索点就是一个n维向量xRn。2、适应度函数 对目标函数作一定的变换，即 f(x) =(F(x) 3、变异算子 出发点：从整体的角度出发来模拟生物

50、的进化过程，其着眼点是群体的进化，强调的是“物种的进化过程”。因此，在进化规划中，不使用交叉等强调个体进化的算子。变异操作是进化规划的惟一最优搜索算子。第六节 进化编程4、选择算子 在进化规划种，选择是按一种随机竞争的方式进行的。过程为： (1)将个父代个体P(t)和对它经过一次变异运算后所产生的个子代个体P(t)合并； (2)从这个集合中选择出q个个体，并同这个集合中的其他每一个个体xk比较适应度，以其中适应度比xk高的个体数目作为个体xk的得分； (3)按得分排序,取出得分最高的个个体作为下一代.第六节 进化编程二、主要特点(1)着眼于整体进化；(2)选择运算着重于群体中个体之间的竞争。比

51、较项目 遗传算法(GA) 进化策略(ES) 进化规划(EP) 个体表示形式离散值连续值连续值参数调整方法无标准偏差,协方差方差适应度评价方法变换目标函数变换目标函数直接采用目标函数GA、ES、EP的主要特点比较第七节 人工生命一、人工生命研究的起源和发展 1943年MP模型的提出； 1945年在普林斯顿大学召开的有关脑和计算机的研讨会，认知工程和ANN是研究大脑的重要基础； 1948年，维纳提出了控制论；冯诺依曼研究了脑和计算机的相似性； 1946年的控制会议上，相成了以维纳为代表的控制论学派和以冯诺依曼为代表的形式理论学派； 20世纪60年代建立了感知机模型； 20世纪70年代，康拉德研究了

52、人工仿生系统中的自适应、进化和群等问题，提出不断完善的“人工世界”模型。 20世界80年代ANN再度兴起 1987年，圣达菲研究所的兰顿正式提出了人工生命的概念 1997年，我国举办了“人工生命与进化机器人研讨班”第七节 人工生命二、人工生命的定义和研究内容1、人工生命的定义 兰顿的定义“人工生命是研究能够演示出自然生命系统特征行为的人造系统”。人工生命应具有的特征： 自繁殖、自进化、自寻优 自学习、自成长、自组织 自稳定、自适应、自协调 物质构造 能量转换 信息处理第七节 人工生命2、人工生命研究的意义(1)开发基于人工生命的工程技术新方法,新系统,新产品;(2)为自然生命的提供新模型、新工

53、具、新环境;(3)延伸人类的寿命;(4)扩展自然生命，实现人工进化；(5)促进生命科学、信息科学、系统科学的交叉与发展。第七节 人工生命三、人工生命的研究内容和方法1、研究内容 构成生物体的内部系统 生物体及其群体的外部系统具体为: (1)生命现象的仿生系统； (2)生命现象的建模与仿真； (3)进化动力学； (4)人工生命的计算理论和工具 (5)进化机器人； (6)进化和学习的结合； (7)人工生命的应用。第七节 人工生命2、人工生命的研究方法 信息模型法研究方法 工作原理法 工程技术途径研究途径 生物科学途径第七节 人工生命四、人工生命的实例1、人工脑2、计算机病毒3、计算机进程4、细胞自

54、动机第八节 粒群优化(PSO)一、群智能和粒群优化概述1、群智能的概念2、粒群优化概念 粒群优化算法是一种基于群体搜索的算法，它建立在模拟鸟群社会的基础上。 在粒群优化，粒子在通过超维空间流动，粒子在搜索空间的位置变化是以个体成功地超越其他个体的社会心理意向为基础的，因此，群中粒子的变化受到其他邻近粒子的行为或经验的影响。所以，粒群算法是一种共生合作算法。第八节 粒群优化3、粒群优化与进化计算的比较相同： 两者都是优化算法，都力图在自然特性的基础上模拟个体种群的适应性；都采用概率变换规则通过搜索空间求解。区别： (1)粒群优化有存储器，而进化计算没有； (2)粒子保持它们及其邻域的最好解答；

55、(3)粒子的适应性是通过向同等的粒子的学习得到的； (4)粒群优化不用适应度函数，而是由同等粒子间的社会交互作用来带动搜索过程的。第八节 粒群优化二、粒群优化算法 粒群优化是以邻域原理为基础进行操作的。驱动粒群优化的特性是社会驱动。群种的个体相互学习，而且基于获得的知识移动到更相似与它们的、较好的邻域。 群由粒子组成，每一个粒子代表一个潜在的解答。 设xi(t)表示t时刻Pi在超空间的位置。 则， xi(t) = xi(t-1) + vi(t)其中， vi(t)是速度向量。 速度向量推动优化过程，并反映出社会所交换的信息。第八节 粒群优化1、个体最佳算法 个体最佳算法的特点是，每一个个体只把它

56、的当前位置与自己的最佳位置相比较，而不使用其他粒子的信息。算法过程： (1)对粒群P(t)初始化，使得t=0时每个粒子在超空间的位置xi(t)是随机的。 (2)通过每个粒子的当前位置评价其性能。 (3)比较每个个体的当前性能与其有过的最佳性能，如果, (xi(t) ) pBesti，那么 pBesti = (xi(t) ) x pBesti = xi(t)第八节 粒群优化 (4)改变每个粒子的速度向量 vi(t) = vi(t-1) + (x pBesti - xi(t) )， 为一随机数每个粒子移动到新位置： xi(t) = xi(t-1) + vi(t) t = t + 1 (5)转(2)

57、第八节 粒群优化2、全局最佳算法 全局最佳算法的特点是，每个粒子能与其他粒子进行通信，形成一个全连接的网络。用于驱动各粒子移动的社会知识包括全群中选择的最佳粒子位置。算法过程：(1)对粒群P(t)初始化，使得t=0时每个粒子在超空间的位置xi(t)是随机的。(2)通过每个粒子的当前位置评价其性能。第八节 粒群优化(3)比较每个粒子的当前性能与其有过的最佳性能，如果, (xi(t) ) pBesti，那么 pBesti = (xi(t) ) x pBesti = xi(t)(4)把每个粒子的性能与全局最佳粒子的性能比较，如果，(xi(t) ) gBesti，那么 gBesti = (xi(t)

58、) x gBesti = xi(t)改变粒子的速度向量 vi(t) = vi(t-1)+1(x pBesti - xi(t) )+2(x gBesti - xi(t) )其中，1, 2 为随机数。第八节 粒群优化每个粒子移动到新位置： xi(t) = xi(t-1) + vi(t) t = t + 1(5)转(2)第八节 粒群优化3、局部最佳算法 局部最佳算法的特点是，每个粒子能与它的n个邻域粒子进行通信，形成一个环。用于驱动各粒子移动的社会知识包括自己的最佳位置和邻域粒子的最佳位置。算法过程：将全局最佳算法过程的gbest该为lbest即可。第九节 蚁群算法(ANG)一、蚁群算法的基本原理E

59、DBAHCd=2d=2d=1d=1蚂蚁觅食：A是蚂蚁的巢穴，E是食物源，HC是障碍物，HD的距离是CD距离的一倍。设每单位时间有30只蚂蚁由A到达B，又有30只从E到达D。蚂蚁过后留下的刺激信息为1，且设保留的时间为1。开始时随机寻路，各边各通过15只，经过1个时间单位后， BCD上的信息将是BHD上的两倍，这时，将有20只蚂蚁由B经过C到达D，随着时间的推移，蚂蚁将会以越来越大的概率选择路径BCD，最终完全选择路径BCD，从而找到最短路径。第九节 蚁群算法二、蚁群算法的应用用蚁群算法解决问题的基本思路 用蚂蚁的行走路线表示待求解问题的可行解，每只蚂蚁在解空间中独立地搜索可行解，解的质量越高，

60、在“行走路线”上留下的信息量也就越多，随着算法的推进，代表较好解的路径上的信息量也逐渐增多，最终整个蚁群在正反馈的作用下集中到代表最优解的路径上，即找到了最优解。第九节 蚁群算法例、用蚁群算法解决TSP问题设：用m表示蚁群中蚂蚁的数量； dij表示城市 i 和城市 j 之间的距离； bi(t)表示 t 时刻位于城市 i 的蚂蚁的数量； ij(t)表示 t 时刻在ij连线上残留的信息量，在初始时刻各条路径上的信息量相等，设为C； 蚂蚁k在运动过程中，根据各条路径上的信息量决定转移方向，pijk(t)表示在t时刻由位置 i 转移到位置 j 的概率。第九节 蚁群算法pijk(t)=ijij(t)ij