高级人工智能-计算智能课件

《高级人工智能-计算智能课件》由会员分享，可在线阅读，更多相关《高级人工智能-计算智能课件（82页珍藏版）》请在金锄头文库上搜索。

1、人工智能,计算智能,2016年秋季,罗平 ,本章内容,概述 演化计算 模糊计算,本章内容,概述 演化计算 模糊计算,计算智能（Computational Intelligence，CI） 计算智能是在神经网络（Neural Networks,NN）、演化计算（Evolutionary Computation,EC）及模糊系统（Fuzzy System,FS）这3个领域发展相对成熟的基础上形成的一个统一的学科概念。,什么是计算智能,神经网络是一种对人类智能的结构模拟方法，它是通过对大量人工神经元的广泛并行互联，构造人工神经网络系统去模拟生物神经系统的智能机理。 演化计算是一种对人类智能的演化模拟

2、方法，它是通过对生物遗传和演化过程的认识，用进化算法去模拟人类智能的进化规律的。 模糊计算是一种对人类智能的逻辑模拟方法，它是通过对人类处理模糊现象的认知能力的认识，用模糊逻辑去模拟人类的智能行为的。,本章内容,概述 演化计算 模糊计算,7,演化计算（Evolutionary Computation,EC）： 在基因和种群层次上模拟自然界生物进化过程与机制的问题求解技术和计算模型。 思想源于生物遗传学和适者生存的自然规律 基于达尔文（Darwin）的进化论和孟德尔（Mendel）的遗传变异理论 典型代表： 遗传算法（Genetic Algorithm，GA） 进化策略（Evolutionary

3、 Strategy,ES） 进化规划（Evolutionary Programming,EP） 遗传规划（Genetic Programming,GP）,演化计算,达尔文的自然选择学说是一种被人们广泛接受的生物进化学说： 生物要生存下去，就必须进行生存斗争。 具有有利变异的个体容易存活下来，并且有更多的机会将有利变异传给后代；具有不利变异的个体就容易被淘汰，产生后代的机会也少的多。 适者生存，不适者淘汰：自然选择。 遗传和变异是决定生物进化的内在因素。（相对稳定+新的物种）,演化计算,9,孟德尔基因遗传原理 遗传以密码方式存在细胞中，并以基因形式包含在染色体内。 每个基因有特殊的位置并控制某种

4、特殊性质；所以，每个基因产生的个体对环境具有某种适应性。 基因突变和基因杂交可产生更适应于环境的后代。 经过存优去劣的自然淘汰，适应性高的基因结构得以保存下来。,演化计算,10,演化计算：一种模拟自然界生物进化过程与机制进行问题求解的自组织、自适应的随机搜索技术。 演化规则：“物竞天择、适者生存” 演化操作： 繁殖（Reproduction） 变异（Mutation） 竞争（Competition） 选择（Selection）,演化计算及其生物学基础,遗传算法的基本思想是从初始种群出发，采用优胜劣汰、适者生存的自然法则选择个体，并通过杂交、变异来产生新一代种群，如此逐代进化，直到满足目标为止

5、基本概念： 种群（Population）：多个备选解的集合。 个体（Individual）：种群中的单个元素，通常由一个用于描述其基本遗传结构的数据结构来表示。例如，长度为L 的0、1串 染色体（Chromos）：对个体仿照基因编码进行编码后所得到的编码串。染色体中的每一位称为基因，染色体上由若干个基因构成的一个有效信息段称为基因组。,遗传算法,基本概念： 适应度（Fitness）函数：用来对种群中各个个体的环境适应性进行度量的函数，函数值是遗传算法实现优胜劣汰的主要依据 遗传操作（Genetic Operator）：作用于种群而产生新的种群的操作。 选择（Selection） 交叉（Cros

6、s-over） 变异（Mutation）,遗传算法,遗传算法主要由染色体编码、初始种群设定、适应度函数设定、遗传操作设计等几大部分所组成， 算法基本步骤： 选择编码策略，将问题搜索空间中每个可能的点用相应的编码策略表示出来，即形成染色体； 定义遗传策略，包括种群规模N，交叉、变异方法，以及选择概率Pr、交叉概率Pc、变异概率Pm等遗传参数； 令t=0，随机选择N个染色体初始化种群P(0)； 定义适应度函数f； 计算P(t)中每个染色体的适应值； t=t+1； 运用选择算子，从P(t-1)中得到P(t)； 对P(t)中的每个染色体，按概率Pc参与交叉； 对染色体中的基因，以概率Pm参与变异运算；

7、 判断群体性能是否满足预先设定的终止标准，若不满足返回(5)。,遗传算法,遗传算法,遗传算法 生物进化 适应函数 环境 适应函数值 适应性 适应函数值最大的解被保留的概率最大 适者生存 问题的一个解 个体 解的编码 染色体 编码的元素 基因 被选定的一组解 群体 根据适应函数选择的一组解（以编码形式表示） 种群 以一定的方式由双亲产生后代的过程 繁殖 编码的某些分量发生变化的过程 变异,遗传算法与生物进化之间对应关系,二进制编码（Binary encoding） 二进制编码是将原问题的结构变换为染色体的位串结构。假设某一参数的取值范围是A，B，A来表示。 优点：易于理解和实现，可表示的模式数最

8、多 主要缺点: 海明悬崖。 例如，7和8的二进制数分别为0111和1000，当算法从7改进到8时，就必须改变所有的位。,遗传编码,格雷编码（Gray encoding） 要求两个连续整数的编码之间只能有一个码位不同，其余码位都是完全相同的。有效地解决了海明悬崖问题。 基本原理： 二进制码-格雷码（编码）：从最右边一位起，依次将每一位与左边一位异或(XOR)，作为对应格雷码该位的值，最左边一位不变； 格雷码-二进制码（解码）：从左边第二位起，将每位与左边一位解码后的值异或，作为该位解码后的值，最左边一位依然不变。,遗传编码,符号编码（Symbol encoding） 个体染色体编码串中的基因值取

9、自一个无数值含义、而只有代码含义的符号集。,由于是回路，记wn+1= w1。 它其实是1，n的一个循环排列。 要注意w1， w2， wn是互不相同的。,遗传编码,例如，对于TSP问题，采用符号编码方法，按一条回路中城市的次序进行编码，一般情况是从城市w1开始，依次经过城市w2 ， wn，最后回到城市w1，我们就有如下编码表示：,适应度函数是一个用于对个体的适应性进行度量的函数。个体的适应度值越大，它被遗传到下一代种群中的概率越大 常用的适应度函数 原始适应度函数: 直接将待求解问题的目标函数f(x)定义为遗传算法的适应度函数。 例如：求最大值 时，f(x)即为x的原始适应度函数。 优点：能够直

10、接反映出待求解问题的最初求解目标， 缺点：有可能出现适应度值为负的情况,适应度函数,TSP的目标是路径总长度为最短，路径总长度可作为TSP问题的适应度函数：,适应度函数,标准适应度函数 在遗传算法中，一般要求适应度函数非负，并其适应度值越大越好。这就往往需要对原始适应函数进行某种变换，将其转换为标准的度量方式，以满足进化操作的要求，这样所得到的适应度函数被称为标准适应度函数fNormal(x)。 例：对极小化问题，其标准适应度函数可定义为 其中，fmax (x)是原始适应函数f(x)的一个上界。如果fmax (x) 未知，则可用当前代或到目前为止各演化代中的f(x)的最大值来代替。 fmax

11、(x) 是会随着进化代数的增加而不断变化的。,适应度函数,极大化问题 对极大化问题，其标准适应度函数可定义为 其中，fmin(x)是原始适应函数f(x)的一个下界。如果fmin(x) 未知，则可用当前代或到目前为止各演化代中的f(x)的最小值来代替。,适应度函数,遗传算法中的基本遗传操作包括选择、交叉和变异。 选择(selection)操作: 根据选择概率按某种策略从当前种群中挑选出一定数目的个体，使它们能够有更多的机会被遗传到下一代中 常用的选择策略可分为比例选择、排序选择和竞技选择三种类型。 比例选择 基本思想是：各个个体被选中的概率与其适应度大小成正比。,基本遗传操作,轮盘赌选择 个体被

12、选中的概率取决于该个体的相对适应度。而相对适应度的定义为： 其中，P(xi)是个体xi的相对适应度，即个体xi被选中的概率；f(xi)是个体xi的原始适应度；是种群的累加适应度。 轮盘赌选择算法的基本思想是：根据每个个体的选择概率P(xi)将一个圆盘分成N个扇区，其中第i个扇区的中心角为： 并再设立一个固定指针。当进行选择时，可以假想转动圆盘，若圆盘静止时指针指向第i个扇区，则选择个体i。,基本遗传操作,从统计角度看，个体的适应度值越大，其对应的扇区的面积越大，被选中的可能性也越大。这种方法有点类似于发放奖品使用的轮盘，并带有某种赌博的意思，因此亦被称为轮盘赌选择。,基本遗传操作,交叉(cro

13、ssover)操作: 按照某种方式对选择的父代个体的染色体的部分基因进行交配重组，从而形成新的个体。 常见的交叉操作： 二进制交叉：二进制编码情况下所采用的交叉操作，它主要包括： 单点交叉 两点交叉 多点交叉 均匀交叉,基本遗传操作,单点交叉 先在两个父代个体的编码串中随机设定一个交叉点，然后对这两个父代个体交叉点前面或后面部分的基因进行交换，并生成子代中的两个新的个体。 假设两个父代的个体串分别是： X=x1 x2 xk xk+1 xn Y=y1 y2 yk yk+1 yn 随机选择第k位为交叉点，交叉后生成的两个新的个体是： X= x1 x2 xk yk+1 yn Y= y1 y2 yk

14、xk+1 xn 设有两个父代的个体串A=0 0 1 1 0 1 和B=1 1 0 0 1 0 ，若随机交叉点为4， 则交叉后生成的两个新的个体是： A= 0 0 1 1 1 1 B= 1 1 0 0 0 0,基本遗传操作,两点交叉 先在两个父代个体的编码串中随机设定两个交叉点，然后再按这两个交叉点进行部分基因交换，生成子代中的两个新的个体。 假设两个父代的个体串分别是： X=x1 x2 xi xj xn Y=y1 y2 yi yj ,yn 随机设定第i、j位为两个交叉点（其中ijn），交叉后生成的两个新的个体是： X= x1 x2 xi yi+1 yj xj+1 xn Y= y1 y2 yi

15、xi+1 xj yj+1 yn 例: 设有两个父代的个体串A= 0 0 1 1 0 1 和B= 1 1 0 0 1 0 ，若随机交叉点为3和5，则交叉后的两个新的个体是： A= 0 0 1 0 1 1 B= 1 1 0 1 0 0,基本遗传操作,均匀交叉 先随机生成一个与父串具有相同长度的二进制串（交叉模版），然后再利用该模版对两个父串进行交叉，即将模版中1对应的位进行交换，而0对应的位不交换，依此生成子代中的两个新的个体。 事实上，这种方法对父串中的每一位都是以相同的概率随机进行交叉的。 例5.10 设有两个父代的个体串A=001101和B=110010，若随机生成的模版T=010011，则

16、交叉后的两个新的个体是A=011010和B=100101。即 A： 0 0 1 1 0 1 B： 1 1 0 0 1 0 T： 0 1 0 0 1 1 A： 0 1 1 1 1 0 B：1 0 0 0 0 1,基本遗传操作,实值交叉 在实数编码情况下所采用的交叉操作，主要包括离散交叉和算术交叉 部分离散交叉：先在两个父代个体的编码向量中随机选择一部分分量，然后对这部分分量进行交换，生成子代中的两个新的个体。 整体交叉：对两个父代个体的编码向量中的所有分量，都以1/2的概率进行交换，从而生成子代中的两个新的个体。 假设两个父代个体的n维实向量分别是 X=x1x2 xixkxn和Y=y1y2yiykyn，若