第六章 计算智能 6.1 概述 6.2 神经计算 6.3 进化计算 6.4 模糊计算 6.5 粗糙集理论 6.6 其他.

Presentation on theme: "第六章 计算智能 6.1 概述 6.2 神经计算 6.3 进化计算 6.4 模糊计算 6.5 粗糙集理论 6.6 其他."— Presentation transcript:

1 第六章 计算智能 6.1 概述 6.2 神经计算 6.3 进化计算 6.4 模糊计算 6.5 粗糙集理论 6.6 其他

2 6.1 概述 6.1.1 什么是计算智能 6.1.2 计算智能的产生与发展 6.1.3 计算智能与人工智能的关系

3 6.1.1 什么是计算智能 计算智能（Computational Intelligence，CI）目前还没有一个统一的定义
使用较多的是美国科学家贝慈德克（J.C.Bezdek）从计算智能系统角度所给出的定义: 如果一个系统仅处理低层的数值数据，含有模式识别部件，没有使用人工智能意义上的知识，且具有计算适应性、计算容错力、接近人的计算速度和近似于人的误差率这4个特性，则它是计算智能的。 从学科范畴看，计算智能是在神经网络（Neural Networks,NN）、进化计算（Evolutionary Computation,EC）及模糊系统（Fuzzy System,FS）这3个领域发展相对成熟的基础上形成的一个统一的学科概念。

4 从贝慈德克对计算智能的定义和计算智能学科范畴的分析：
计算智能是借鉴仿生学的思想，基于生物神经系统的结构、进化和认知对自然智能进行模拟的。 计算智能是一种以模型（计算模型、数学模型）为基础，以分布、并行计算为特征的自然智能模拟方法。

5 进化计算是一种对人类智能的演化模拟方法，它是通过对生物遗传和演化过程的认识，用进化算法去模拟人类智能的进化规律的。
神经网络是一种对人类智能的结构模拟方法，它是通过对大量人工神经元的广泛并行互联，构造人工神经网络系统去模拟生物神经系统的智能机理的。 进化计算是一种对人类智能的演化模拟方法，它是通过对生物遗传和演化过程的认识，用进化算法去模拟人类智能的进化规律的。 模糊计算是一种对人类智能的逻辑模拟方法，它是通过对人类处理模糊现象的认知能力的认识，用模糊逻辑去模拟人类的智能行为的。

6 6.1.2 计算智能的产生与发展 1992年: 贝慈德克在《Approximate Reasoning》学报上首次 提出了“计算智能”的概念。 1994年6月底到7月初: IEEE在美国佛罗里达州的奥兰多市召开了首届国际计算智能大会(简称WCCI’94)。会议第一次将神经网络、进化计算和模糊系统这三个领域合并在一起，形成了“计算智能”这个统一的学科范畴。 在此之后: WCCI大会就成了IEEE的一个系列性学术会议，每4年举办一次。1998年5月，在美国阿拉斯加州的安克雷奇市又召开了第2届计算智能国际会议WCCI’98。2002年5月，I在美国州夏威夷州首府火奴鲁鲁市又召开了第3届计算智能国际会议WCCI’02。此外，IEEE还出版了一些与计算智能有关的刊物。 目前，计算智能的发展得到了国内外众多的学术组织和研究机构的高度重视，并已成为智能科学技术一个重要的研究领域。

7 6.1.3 计算智能与人工智能的关系 两种不同观点: 计算智能是人工智能的子集 计算智能和人工智能是不同的范畴

8 第一种观点 CNN CPR CI ANN APR AI BNN BPR BI 人类知识 (+)传感输入 知识 (+)传感数据 计算
(+)传感器 B~生物的 A~符号的 C~数值的 复杂性 输入 层次 贝慈德克的智能的3个层次

9 第二种观点 是大多数学者所持有的观点，其代表人物是艾伯哈特（R.C.Eberhart）。他们认为：虽然人工智能与计算智能之间有重合，但计算智能是一个全新的学科领域，无论是生物智能还是机器智能，计算智能都是其最核心的部分，而人工智能则是外层。 事实上，CI和传统的AI只是智能的两个不同层次，各自都有自身的优势和局限性，相互之间只应该互补，而不能取代。 大量实践证明，只有把AI和CI很好地结合起来，才能更好地模拟人类智能，才是智能科学技术发展的正确方向。

10 6.2 神经计算 6.2.1 神经计算基础 6.2.2 人工神经网络的互连结构 6.2.3 人工神经网络的典型模型

11 6.2.1 神经计算基础 生物神经系统: 生物神经系统是人工神经网络的基础
人工神经网络是对人脑神经系统的简化、抽象和模拟，具有人脑功能的许多基本特征。

12 生物神经系统: 生物神经元的结构 生物神经元的功能 人脑神经系统的联结机制

13 (1) 生物神经元的结构 它由细胞体(Soma)、轴突(Axon)和树突(Dendrite)三个主要部分组成 。 细胞核 神经末梢 突触

14 (2) 生物神经元的功能 生物神经元的2个主要功能: 神经元的兴奋与抑制 神经元内神经冲动的传导

15 神经元的抑制与兴奋 抑制状态: 指神经元在没有产生冲动时的工作状态。 兴奋状态: 是指神经元产生冲动时的工作状态。 神经元内神经冲动的传导

16 (3) 人脑神经系统的联结机制 人脑神经系统就是由这些巨量的生物神经元经广泛并行互连所形成的一个高度并行性、非常复杂的神经网络系统。 人脑神经系的记忆和处理功能是有机的结合在一起的，每个神经元既具有存储功能，同时又具有处理能力。 人脑神经系统又是一种分布式系统。人类大脑的各个部分是协同工作、相互影响的。 在大脑中，不仅知识的存储是分散的，而且其控制和决策也是分散的。

17 6.2.1 神经计算基础 人工神经元的结构 常用的人工神经元模型
人工神经网络简介: 人工神经网络是由大量的人工神经元经广泛互联所形成的一种人工网络系统，用以模拟人类神经系统的结构和功能。 人工神经元的结构 常用的人工神经元模型

18 wi: 第i个输入的连接强度，称为连接权值； Θ: 神经元的阈值; y: 神经元的输出; 人工神经元是一个具有多输入，单输出的非线性器件
人工神经元的结构 w1 x1 w2 y MP神经元模型 x2 θ … xn wn 1943年，心理学家麦克洛奇(W.Mclloch)和数理逻辑学家皮茨(W.Pitts)根据生物神经元的功能和结构，提出了一个将神经元看作二进制阈值元件的简单模型，即MP模型。 x1, x2, … ,xn: 表示某一神经元的n个输入； wi: 第i个输入的连接强度，称为连接权值； Θ: 神经元的阈值; y: 神经元的输出; 人工神经元是一个具有多输入，单输出的非线性器件 其输入为 ,输出为 其中，f称为神经元功能函数（或作用函数，激活函数）

19 常用的人工神经元模型 根据功能函数的不同，可得到不同的神经元模型。 常用模型包括： 1. 阈值型(Threshold)
θ f(θ) 1 这种模型的神经元没有内部状态，作用函数f是一个阶跃函数，他表示激活值和输出之间的关系。 2.分段线性强饱和型(Linear Saturation) 这种模型又称为伪线性，其输入/输出之间在一定范围内满足线性关系，一直延续到输出为最大值1为止。但当达到最大值后，输出就不再增。

20 常用的人工神经元模型(2) 3.S型(Sigmoid) 这是一种连续的神经元模型，其输入输出特性常用指数、对数或双曲正切等S型函数表示。
4.子阈累积型(Subthreshold Summation) 一个非线性函数，当产生的激活值超过T值时，该神经元被激活产生个反响。在线性范围内，系统的反响是线性的。 T 1

21 6.2.2 人工神经网络的互联结构 人工神经网络的互连结构（或称拓扑结构）是指单个神经元之间的连接模式 它是构造神经网络的基础
也是神经网络诱发偏差的主要来源

22 6.2.2 人工神经网络的互联结构 从互连结构的角度：分为前馈网络和反馈网络两种类型 单层前馈网络 前馈网络 只包含前向联结 多层前馈网络
仅含输入层和输出层，且只有输出层的神经元是可计算节点 除拥有输入、输出层外，还至少含有一个、或更多个隐含层的前向网络 只包含前向联结 反馈网络 单层反馈网络 多层反馈网络 指不拥有隐含层的反馈网络 指拥有隐含层的反馈网络 可含有反馈联结

23 前馈网络 单层前馈网络：只拥有单层计算节点的前向网络。它仅含有输入层和输出层，且只有输出层的神经元是可计算节点 单层前馈网络结构 x1 y1
… x1 X2 X3 xn y1 Y2 ym 权值 wij 输出层 输入层 单层前馈网络结构

24 单层前馈网络 若假设各神经元的阈值分别是θj，j=1,2,…,m， 则各神经元的输出yj, j=1,2,..,m分别为：
x1 X2 X3 xn y1 Y2 ym 权值 wij 输出层 输入层 单层前馈网络结构 若假设各神经元的阈值分别是θj，j=1,2,…,m， 则各神经元的输出yj, j=1,2,..,m分别为： 其中，由所有连接权值wij构成的连接权值矩阵W为：

25 除拥有输入、输出层外，还至少含有一个、或更多个隐含层的前馈网络
多层前馈网络 除拥有输入、输出层外，还至少含有一个、或更多个隐含层的前馈网络 x1 X2 Xn y1 Ym 隐含层 输出层 输入层 多层前馈网络结构 … 权值

26 隐含层是指由那些既不属于输入层又不属于输出层的神经元所构成的处理层,也被称为中间层。
隐含层的作用是通过对输入层信号的加权处理，将其转移成更能被输出层接受的形式。 多层前馈网络的输入层的输出向量是第一隐含层的输入信号，而第一隐含层的输出则是第二隐含层的输入信号，以此类推，直到输出层。 多层前馈网络的典型代表是BP网络。 x1 X2 Xn y1 Ym 隐含层 输出层 输入层 多层前馈网络结构 … 权值

27 6.2.2 人工神经网络的互联结构 反馈网络 反馈网络是指允许采用反馈联结方式所形成的神经网络。所谓反馈联结方式是指一个神经元的输出可以被反馈至同层或前层的神经元。 反馈网络的典型例子是Hopfield网络

28 反馈网络和前馈网络不同： 前馈网络属于非循环连接模式，它的每个神经元的输入都没有包含该神经元先前的输出，因此不具有“短期记忆”的性质。 反馈网络则不同，它的每个神经元的输入都有可能包含有该神经元先前输出的反馈信息，即一个神经元的输出是由该神经元当前的输入和先前的输出这两者来决定的，这就有点类似于人类的短期记忆的性质。

29 6.2.3 人工神经网络的典型模型 人工神经网络的模型： 是指对网络结构、联结权值和学习能力的总括。 感知机（Perceptron）模型
反向传播（BP）模型 反馈网络（Hopfield）模型

30 1. 感知器模型 感知器是美国学者罗森勃拉特（Rosenblatt）于1957年为研究大脑的存储、学习和认知过程而提出的一类具有自学习能力的神经网络模型 拓扑结构是一种分层前向网络 包括：单层感知器和多层感知器

31 若假设各神经元的阈值分别是θj，j=1,2,…,m，则各神经元的输出yj, j=1,2,..,m分别为：
单层感知器 输入向量：X=(x1,x2,…,xn)； 输出向量：Y=(y1,y2,…,ym)； 输入层各个输入到相应神经元的连接权值分别是wij，i=1,2,..,n，j=1,2,.., m … x1 x2 xn y1 ym 输入层 输出层 权值 wij 若假设各神经元的阈值分别是θj，j=1,2,…,m，则各神经元的输出yj, j=1,2,..,m分别为：

32 关于单层感知器 单层感知器是一种只具有单层可调节连接权值神经元的前向网络，这些神经元构成了单层感知器的输出层，是感知器的可计算节点。
在单层感知器中，每个可计算节点都是一个线性阈值神经元。当输入信息的加权和大于或等于阈值时，输出为1，否则输出为0或-1。 单层感知器的输出层的每个神经元都只有一个输出，且该输出仅与本神经元的输入及联接权值有关，而与其他神经元无关。

33 使用感知器的主要目的是为了对外部输入进行分类。
已经证明，如果外部输入是线性可分的（指存在一个超平面可以将它们分开），则单层感知器一定能够把它划分为两类。其判别超平面由如下判别式确定：

34 可以证明此表有解，例如取w1=1，w2=1，θ=1.5
感知器模型 例： “与”运算（x1∧x2） 输入 输出 超平面 阈值条件 x1 x2 x1∧x2 w1*x1+ w2* x2-θ=0 w1*0+ w2*0 -θ＜0 θ＞0 1 w1*0+ w2*1 -θ＜0 θ＞w2 w1*1+ w2*0 -θ＜0 θ＞w1 w1*1+ w2*1-θ≥0 θ≤w1+ w2 (0,0) (1,1) (0,1) (1,0) 与运算问题图示 可以证明此表有解，例如取w1=1，w2=1，θ=1.5

35 例 “非”运算（¬x1） 此表也有解，例如取w1=-1，θ=-0.5 输入 输出 超平面 阈值条件 x1 ¬x1 w1*x1-θ=0 1
1 w1*0 -θ ≥ 0 θ≤0 w1*1 –θ<0 θ >w1 此表也有解，例如取w1=-1，θ=-0.5 图 非运算问题图示 1

36 例 “异或”运算（x1 XOR x2） 输入 输出 超平面 阈值条件 x1 x2 X1 XOR x2 w1*x1+ w2* x2-θ=0
w1*0+ w2*0 -θ＜0 θ＞0 1 w1*0+ w2*1 -θ≥0 θ≤w2 w1*1+ w2*0 -θ≥0 θ≤w1 w1*1+ w2*1-θ<0 θ>w1+ w2 (0,1) (0,0) (1,0) 图 异或运算问题图示 (1,1) 此表无解，即无法找到满足条件的w1、w2和θ。因为异或问题是一个非线性可分问题，需要用多层感知器来解决。

37 1. 感知器模型----多层感知器 通过在单层感知器的输入、输出层之间加入一层或多层处理单元所构成的。 x12 图 “异或”问题的多层感知器
1. 感知器模型----多层感知器 通过在单层感知器的输入、输出层之间加入一层或多层处理单元所构成的。 x11 y=x1 XOR x2 x1 X2 x12 1 -1 输入层 隐层 输出层 权值 图 “异或”问题的多层感知器 阈值0.5 阈值-1.5 阈值1.5

38 图 异或问题的解决 图 “异或”问题的多层感知器 x11所确定的直线方程: x12 x12所确定的直线方程:
阈值0.5 1 x1 1 1 x11 y=x1 XOR x2 x12 阈值1.5 -1 1 X2 x12所确定的直线方程: -1 阈值-1.5 输入层 权值 隐层 权值 输出层 图 “异或”问题的多层感知器 (0,1) (0,0) (1,0) 图 异或问题的解决 (1,1) 输出层神经元所确定的直线方程为:

39 2. BP网络模型 误差反向传播(Error Back Propagation)网络, 简称为BP(Back Propagation)
是由美国加州大学的鲁梅尔哈特和麦克莱兰在研究并行分布式信息处理方法，探索人类认知微结构的过程中，于1985年提出的一种网络模型 网络拓扑结构是多层前向网络 同层节点之间不存在相互连接，层与层之间多采用全互连方式，且各层的连接权值可调 BP网络实现了明斯基的多层网络的设想，是当今神经网络模型中使用最广泛的一种。 y1 y2 ym x1 x2 xn 输出层 隐含层 输入层 权可调 … 图 一个多层BP网络的结构

40 BP网络模型 BP网络的每个处理单元均为非线性输入/输出关系，其作用函数通常采用的是Sigmoid函数，如：
y1 y2 ym x1 x2 xn 输出层 隐含层 输入层 权可调 … 图 一个多层BP网络的结构 BP网络的每个处理单元均为非线性输入/输出关系，其作用函数通常采用的是Sigmoid函数，如： 学习过程是由工作信号的正向传播和误差信号的反向传播组成的。

41 BP网络模型 正向传播和反向传播 正向传播: 输入模式经隐层到输出层，最后形成输出模式
y1 y2 ym x1 x2 xn 输出层 隐含层 输入层 权可调 … 图 一个多层BP网络的结构 正向传播: 输入模式经隐层到输出层，最后形成输出模式 误差反向传播: 从输出层开始逐层将误差传到输入层，并修改各层联接权值，使误差信号为最小的过程

42 3. Hopfield网络模型 Hopfield网络是由美国加州工学院物理学家霍普菲尔特1982年提出来的一种单层全互连的对称反馈网络模型 可用作联想存储器的互连网络 是一种循环神经网络，从输出到输入有反馈连接 分为离散Hopfield网络和连续Hopfield网络 重点讨论离散Hopfield网络

43 离散Hopfield网络结构 图 离散Hopfield网络的结构
ym Y2 Y1 x1 … x2 xn 输入层 输出层 由若干基本神经元构成的一种单层全互连网络，其任意神经元之间均有连接，并且是一种对称连接结构。 离散Hopfield网络模型是一个离散时间系统，每个神经元只有0和1（或-1和1）两种状态，任意神经元i和j之间的连接权值为wij。由于神经元之间为对称连接，且神经元自身无连接，因此有： 由该连接权值所构成的连接矩阵是一个零对角的对称矩阵

44 图 离散Hopfield网络的结构 ym Y2 Y1 x1 … x2 xn 输入层 输出层 Hopfidld网络是一种反馈神经网络

45 6.3 进化计算 （Evolutionary Computation,EC）
是在达尔文（Darwin）的进化论和孟德尔（Mendel）的遗传变异理论的基础上产生的一种在基因和种群层次上模拟自然界生物进化过程与机制的问题求解技术。 主要包括： 遗传算法（Genetic Algorithm，GA） 进化策略（Evolutionary Strategy,ES） 进化规划（Evolutionary Programming,EP） 遗传规划（Genetic Programming,GP） GA是进化计算中最初形成的一种具有普遍影响的模拟进化优化算法。

46 6.3.1 进化计算概述 随机搜索技术 模拟自然界生物进化过程与机制进行问题求解 自组织、自适应
什么是进化计算？ 随机搜索技术 模拟自然界生物进化过程与机制进行问题求解 自组织、自适应 以达尔文进化论的“物竟天择、适者生存”作为算法的进化规则，并结合孟德尔的遗传变异理论，将生物进化过程引入到算法中： 繁殖（Reproduction） 变异（Mutation） 竞争（Competition） 选择（Selection）

47 1. 进化计算及其生物学基础 （1）遗传理论： 细胞（Cell） 染色体（Chromosome） 基因（Gene） 基因组(Genome)
自然界生物进化过程是进化计算的生物学基础 主要包括遗传、变异和进化理论 （1）遗传理论： 细胞（Cell） 染色体（Chromosome） 基因（Gene） 基因组(Genome) 细胞在分裂过程中，其遗传物质DNA通过复制转移到新生细胞中，从而实现了生物的遗传功能。

48 1. 进化计算及其生物学基础 （2） 变异理论 引起变异的主要原因有以下两种： 杂交： 复制差错： （3）进化论
遗传和变异是生物进化的两种基本现象，优胜劣汰、 适者生存是生物进化的基本规律

49 2. 进化计算的产生与发展 1. 萌芽阶段: 20世纪50年代后期到70年代中期
进化计算自20世纪50年代以来，发展过程大致可分为三个阶段: 1. 萌芽阶段: 20世纪50年代后期到70年代中期 20世纪50年代后期, 遗传算法: 1962年由美国密执安（Michigan）大学霍兰德（Holland）提出。 1965年德国数学家雷切伯格（Rechenberg）等人提出了一种只有单个个体参与进化，并且仅有变异这一种进化操作的进化策略。 同年，美国学者弗格尔（Fogel）提出了一种具有多个个体和仅有变异一种进化操作的进化规划。 霍兰德（Holland）提出了系统本身和外部环境相互协调的遗传算法。

50 成长阶段: 20世纪70年代中期到80年代后期 1975年，霍兰德出版专著《自然和人工系统的适应性（Adaptation in Natural and Artificial System）》，全面介绍了遗传算法。 同年，德国学者施韦费尔（Schwefel）在其博士论文中提出了一种由多个个体组成的群体参与进化的，并且包括了变异和重组这两种进化操作的进化策略。 1989年，霍兰德的学生戈尔德伯格（Goldberg）博士出版专著《遗传算法----搜索、优化及机器学习（Genetic Algorithm----in Search Optimization and Machine Learning）》，使遗传算法得到了普及与推广。

51 3. 发展阶段: 20世纪90年代至今 1989年，美国斯坦福（Stanford）大学的科扎（Koza）提出了遗传规划的新概念，并于1992年出版了专著《遗传规划----应用自然选择法则的计算机程序设计（Genetic Programming :on the Programming of Computer by Means of Natural Selection）》，标志着遗传规划作为计算智能的一个分支已基本形成。 进入20世纪90年代以来，进化计算得到了众多研究机构和学者的高度重视，新的研究成果不断出现、应用领域不断扩大。 目前，进化计算已成为人工智能领域的又一个新的研究热点。

52 3. 进化计算的基本结构 假设P为种群(Population，或称为群体)，t为进化代数， P(t)为第t代种群 进化计算的基本结构：
{ 确定编码形式并生成搜索空间； 初始化各个进化参数，并设置进化代数t=0； 初始化种群P(0); 对初始种群进行评价（即适应度计算）； while（不满足终止条件）do { t=t+1; 利用选择操作从P(t-1)代中选出P(t)代群体； 对P(t)代种群执行进化操作； 对执行完进化操作后的种群进行评价（即适应度计算）； }

53 6.3.2 遗传算法 是一种进化方法 广义的观点来看： 首先，生成若干个分类器，称为一个“种群”（population），其中每一个个体分类器都或多或少地与其他个体有所不同。然后，依据一个典型的任务完成情况（适应度或适应函数），对每一个个体进行评价或估计得分，根据 “适者生存”，保留其中一部分得分高的个体。而后，随机地改变一下“生存下来”的分类器，以产生子代种群。重复进行上述过程。如果到了某一代，其中性能好的那个个体的得分已经超过了预期的目标，则进化过程停止。

54 基本概念： 种群（Population）：是指用遗传算法求解问题时，初始给定的多个解的集合。遗传算法的求解过程是从这个子集开始的。 个体（Individual）：是指种群中的单个元素，它通常由一个用于描述其基本遗传结构的数据结构来表示。例如，可以用0、1组成的长度为L的串来表示个体。 染色体（Chromos）：是指对个体进行编码后所得到的编码串。染色体中的每1位称为基因，染色体上由若干个基因构成的一个有效信息段称为基因组。 适应度（Fitness）函数：是一种用来对种群中各个个体的环境适应性进行度量的函数。其函数值是遗传算法实现优胜劣汰的主要依据 遗传操作（Genetic Operator）：遗传操作是指作用于种群而产生新的种群的操作。 标准的遗传操作包括以下3种基本形式： 选择（Selection） 交叉（Crosssover） 变异（Mutation）

55 遗传算法的基本结构 主要由染色体编码、初始种群设定、适应度函数设定、遗传操作设计等几大部分所组成 主要内容和基本步骤：
(1) 选择编码策略，将问题搜索空间中每个可能的点用相应的编码策略表示出来，即形成染色体； (2) 定义遗传策略，包括种群规模N，交叉、变异方法，以及选择概率Pr、交叉概率Pc、变异概率Pm等遗传参数； (3) 令t=0，随机选择N个染色体初始化种群P(0)； (4) 定义适应度函数f（f>0）； (5) 计算P(t)中每个染色体的适应值； (6) t=t+1； (7) 运用选择算子，从P(t-1)中得到P(t)； (8) 对P(t)中的每个染色体，按概率Pc参与交叉； (9) 对染色体中的基因，以概率Pm参与变异运算； (10) 判断群体性能是否满足预先设定的终止标准，若不满足则返回(5)。

56 例：八皇后问题 * 问题表示：从k个随机生成的状态（种群）开始 每个个体用一个有限长度的字符串表示-通常用0，1表示 8 7
每列八个皇后的位置：如 * 8 7 6 5 4 3 2 1

57 例：八皇后问题 24 31% 23 29% 20 26% 11 14% 初始种群 适应度函数 选择 杂交 变异

58 遗传算法的特点 不同于传统的搜索和优化方法： 自组织、自适应和自学习性 本质并行性 不需要其他知识，只需要影响搜索方向的目标函数和相应的适应度函数 更加直接地应用 函数优化、组合优化、生产调度、自动控制、机器人控制智能、图象处理和模式识别、机器学习等

59 2. 遗传算法的基本结构 算法流程 编码和生成初始种群 Y 满足终止条件吗？ N 终止 交叉 变异 图 基本遗传算法的算法流程图
2. 遗传算法的基本结构 算法流程 计算种群中各个个体的适应度，并进行评价 满足终止条件吗？ 终止 选择 交叉 变异 Y 图 基本遗传算法的算法流程图 编码和生成初始种群 N

60 3. 遗传编码 常用的遗传编码算法有: 霍兰德二进制码 格雷码（Gray Code） 实数编码 字符编码

61 (1)二进制编码（Binary encoding）
在二进制编码中，首先要确定二进制字符串的长度L，该长度与变量的定义域和所求问题的计算精度有关。 优点: 自然且易于实现 缺点: 汉明（Hamming）悬崖

62 (2) 格雷编码（Gray encoding）
格雷编码是对二进制编码进行变换后所得到的一种编码方法。 这种编码方法要求两个连续整数的编码之间只能有一个码位不同，其余码位都是完全相同的。 设有二进制串b1,b2,…,bn，对应的格雷串为a1,a2,…,an，则从二进制编码到格雷编码的变换为： 从一个格雷串到二进制串的变换为：

63 例:十进制数7和8的二进制编码分别为0111和1000 格雷编码分别为 。 0100和1100

64 (3) 实数编码（Real encoding）
实数编码是将每个个体的染色体都用某一范围的一个实数（浮点数）来表示，其编码长度等于该问题变量的个数。 这种编码方法是将问题的解空间映射到实数空间上，然后在实数空间上进行遗传操作。 由于实数编码使用的是变量的真实值，因此这种编码方法也叫做真值编码方法。

65 4. 适应度函数 常用的适应度函数: 原始适应度函数 标准适应度函数 是用于对个体的适应性进行度量的函数。
4. 适应度函数 是用于对个体的适应性进行度量的函数。 一个个体的适应度值越大，它被遗传到下一代种群中的概率也就越大。 常用的适应度函数: 原始适应度函数 标准适应度函数

66 如: 优点: 能够直接反映出待求解问题的最初求解目标 缺点: 有可能出现适应度值为负的情况 原始适应度函数
直接将待求解问题的目标函数f(x)定义为遗传算法的适应度函数。 如: 优点: 能够直接反映出待求解问题的最初求解目标 缺点: 有可能出现适应度值为负的情况

67 标准适应度函数 极小化问题 标准适应度函数可定义为: 其中，fmax (x)是原始适应函数f(x)的一个上界。如果fmax (x) 未知，则可用当前代或到目前为止各演化代中的f(x)的最大值来代替。

68 标准适应度函数 极大化问题 标准适应度函数可定义为: 其中，fmin(x)是原始适应函数f(x)的一个下界。如果fmin(x) 未知，则可用当前代或到目前为止各演化代中的f(x)的最小值来代替。

69 适应度函数的设计 适应度函数的加速变换 f’(x)=αf(x)+β 两种基本方法: 线性加速 非线性加速 幂函数变换方法:
f’(x)=f(x)k 指数变换方法: f’(x)=exp(-βf(x))

70 5. 基本遗传操作 (选择、交叉和变异) 选择操作（Selection）: 根据选择概率按某种策略从当前种群中挑选出一定数目的个体，使它们能够有更多的机会被遗传到下一代中 常用的选择策略可分为比例选择、排序选择和竞技选择三种类型。

71 比例选择（Proportional Model）的基本思想
各个个体被选中的概率与其适应度大小成正比 常用的比例选择策略: 轮盘赌选择 P(xi)是个体xi的相对适应度，即个体xi被选中的概率

72 从统计角度看，个体的适应度值越大，其对应的扇区的面积越大，被选中的可能性也越大。
P(x1) P(x2) P(xN) … P(xi) 2πp(xi) 轮盘赌选择 从统计角度看，个体的适应度值越大，其对应的扇区的面积越大，被选中的可能性也越大。

73 (2)交叉操作 是指按照某种方式对选择的父代个体的染色体的部分基因进行交配重组，从而形成新的个体。 是遗传算法中产生新的个体的最主要方法。 根据个体编码方法的不同，遗传算法中的交叉操作可分为二进制交叉和实值交叉两种类型。

74 二进制交叉（Binary Valued Crossover）
包括: 单点交叉 两点交叉 多点交叉 均匀交叉

75 单点交叉(简单交叉) 假设两个父代的个体串分别是： X=x1 x2 … xk xk+1 … xn
Y=y1 y2 … yk yk+1 … yn 随机选择第k位为交叉点，若采用对交叉点后面的基因进行交换的方法，但点交叉是将X中的xk+1到xn部分与Y中的yk+1到yn部分进行交叉，交叉后生成的两个新的个体是： X’= x1 x2 … xk yk+1 … yn Y’= y1 y2 … yk xk+1 … xn 例: 设有两个父代的个体串A= 和B= ，若随机交叉点为4，则交叉后生成的两个新的个体是：? A’= B’=

76 两点交叉 假设两个父代的个体串分别是： X=x1 x2 … xi … xj … xn Y=y1 y2 … yi … yj …,yn
随机设定第i、j位为两个交叉点（其中i<j<n），两点交叉是将X中的xi+1到xj部分与Y中的yi+1到yj部分进行交换，交叉后生成的两个新的个体是： X’= x1 x2 … xi yi+1 … yj xj+1 … xn Y’= y1 y2 … yi xi+1 … xj yj+1 … yn 例: 设有两个父代的个体串A= 和B= ，若随机交叉点为3和5，则交叉后的两个新的个体是：? A’= B’=

77 多点交叉 假设交叉点个数为m，则可将个体串划分为m+1个分段，其划分方法是：
当m为奇数时，对前(m-1)个交叉点依次进行两两配对，构成(m-1)/2个交叉段，而第m个交叉点则按单点交叉方法构成一个交叉段。 下面以m=3为例进行讨论。假设两个父代的个体串分别是X=x1 x2 … xi … xj … xk … xn和Y=y1 y2 … yi … yj … yk … yn，随机设定第i、j、k位为三个交叉点（其中i<j<k<n），则将构成两个交叉段。交叉后生成的两个新的个体是： X’= x1 x2 … xi yi+1 … yj xj+1 … xk yk+1 … yn Y’= y1 y2 … yi xi+1 … xj yj+1 … yk xk+1 … xn 设有两个父代的个体串A= 和B= ，若随机交叉点为1、3和5，则交叉后的两个新的个体是：? A’= B’=

78 例： 设有两个父代的个体串A=001101和B=110010，若随机生成的模版T=010011，则交叉后的两个新的个体是？
均匀交叉 ----先随机生成一个与父串具有相同长度，并被称为交叉模版（或交叉掩码）的二进制串; ----然后再利用该模版对两个父串进行交叉，即将模版中1对应的位进行交换，而0对应的位不交换，依此生成子代中的两个新的个体。 例： 设有两个父代的个体串A=001101和B=110010，若随机生成的模版T=010011，则交叉后的两个新的个体是？ A： B： T： A’： B’：

79 (3) 变异操作 对选中个体的染色体中的某些基因进行变动，以形成新的个体。 变异操作增加了算法的局部随机搜索能力，从而可以维持种群的多样性。 根据个体编码方式的不同，变异操作可分为二进制变异和实值变异两种类型。

80 二进制变异 先随机地产生一个变异位，然后将该变异位置上的基因值由“0”变为“1”，或由“1”变为“0”，产生一个新的个体。 例：设变异前的个体为A= 若随机产生的变异位置：2 变异后的新的个体是？ A’=

81 6. 遗传算法应用简例 例1. 用遗传算法求函数 f(x)=x2 的最大值，其中x为[0，31]间的整数。 求解过程： (1) 编码
例1. 用遗传算法求函数 f(x)=x2 的最大值，其中x为[0，31]间的整数。 求解过程： (1) 编码 采用二进制编码方法，其编码串的长度为5 (2) 生成初始种群 若假设给定的种群规模N=4，则可用4个随机生成的长度为5的二进制串作为初始种群。再假设第0代随机生成的初始种群为： s01= s02= s03= s04=

82 (3) 计算适应度 直接用f(x)来作为适应度函数。即： f(s)=f(x) 其中的二进制串s对应着变量x的值。 初始种群情况表 编号
个体串（染色体） x 适应值 百分比% 累计百分比% 选中次数 S01 01101 13 169 14.44 1 S02 11001 25 625 52.88 67.18 2 S03 01000 8 64 5.41 72.59 S04 10010 18 324 27.41 100 可以看出，在4个个体中S02的适应值最大，是当前最佳个体。

83 其中，染色体11001在种群中出现了2次，而原染色体01000则因适应值太小而被淘汰
(4) 选择操作 假设采用轮盘赌方式选择个体，且依次生成的4个随机数（相当于轮盘上指针所指的数）为0.85、0.32、0.12和0.46，经选择后得到的新的种群为： S01=10010 S02=11001 S03=01101 S04=11001 其中，染色体11001在种群中出现了2次，而原染色体01000则因适应值太小而被淘汰

84 (5) 交叉 假设交叉概率Pi为50%，则种群中只有1/2的染色体参与交叉。若规定种群中的染色体按顺序两两配对交叉，且有S01与S02交叉，S03与S04不交叉 初始种群的交叉情况表 可见，经交叉后得到的新的种群为： S01=10001 S02=11010 S03=01101 S04=11001 编号 个体串（染色体） 交叉对象 交叉位 子代 适应值 S01 10010 S02 3 10001 289 11001 11010 676 S03 01101 S04 N 169 625

85 (6) 变异 变异概率Pm一般都很小，假设本次循环中没有发生变异，则变异前的种群即为进化后所得到的第1代种群。即： S11=10001 S12=11010 S13=01101 S14=11001 然后，对第1代种群重复上述(4)-(6)的操作

86 对第1代种群，同样重复上述(4)-(6)的操作。其选择情况: 第1代种群的选择情况表
其中若假设按轮盘赌选择时依次生成的4个随机数为0.14、0.51、0.24和0.82，经选择后得到的新的种群为： S11=10001 S12=11010 S13=11010 S14=11001 可以看出，染色体11010被选择了2次，而原染色体01101则因适应值太小而被淘汰。 编号 个体串（染色体） x 适应值 百分比% 累计百分比% 选中次数 S11 10001 27 289 16.43 16.437 1 S12 11010 26 676 38.43 54.86 2 S13 01101 13 169 9.61 64.47 S14 11001 25 625 35.53 100

87 可以看出，第3位基因均为0，已经不可能通过交配达到最优解。这种过早陷入局部最优解的现象称为早熟。为解决这一问题，需要采用变异操作。
对第1代种群，其交叉情况: 第1代种群的交叉情况表 可见，经杂交后得到的新的种群为： S11=10010 S12=11001 S13=11001 S14=11010 可以看出，第3位基因均为0，已经不可能通过交配达到最优解。这种过早陷入局部最优解的现象称为早熟。为解决这一问题，需要采用变异操作。 编号 个体串（染色体） 交叉对象 交叉位 子代 适应值 S11 10001 S12 3 10010 324 11010 11001 625 S13 S14 2 675

88 它是通过对S14的第3位的变异来实现的。变异后所得到的第2代种群为： S21=10010 S22=11001 S23=11001
对第1代种群，其变异情况: 第1代种群的变异情况表 它是通过对S14的第3位的变异来实现的。变异后所得到的第2代种群为： S21=10010 S22=11001 S23=11001 S24=11110 接着，再对第2代种群同样重复上述(4)-(6)的操作： 编号 个体串（染色体） 是否变异 变异位 子代 适应值 S11 10010 N 324 S12 11001 625 S13 S14 11010 Y 3 11110 900

89 对第2代种群，同样重复上述(4)-(6)的操作。其选择情况:。 第2代种群的选择情况表
其中若假设按轮盘赌选择时依次生成的4个随机数为0.42、0.15、0.59和0.91，经选择后得到的新的种群为： S21=11001 S22=10010 S23=11001 S24=11110 编号 个体串（染色体） x 适应值 百分比% 累计百分比% 选中次数 S21 10010 18 324 23.92 1 S22 11001 25 625 22.12 46.04 S23 68.16 S24 11110 30 900 31.84 100

90 这时，函数的最大值已经出现，其对应的染色体为11111，经解码后可知问题的最优解是在点x=31处。 求解过程结束。
对第2代种群，其交叉情况: 这时，函数的最大值已经出现，其对应的染色体为11111，经解码后可知问题的最优解是在点x=31处。 求解过程结束。 编号 个体串（染色体） 交叉对象 交叉位 子代 适应值 S21 11001 S22 3 11010 676 10010 10001 289 S23 S24 4 11000 576 11110 11111 961

91 6.4 模糊计算 美国加州大学扎德(Zadeh)教授于1965年提出的模糊集合与模糊逻辑理论是模糊计算的数学基础。它主要用来处理现实世界中因模糊而引起的不确定性。目前，模糊理论已经在推理、控制、决策等方面得到了非常广泛的应用。本节主要讨论模糊理论的基础，对于模糊推理将放到下一章讨论。

92 5.4.1 模糊集及其运算 定义5.1 设U是给定论域， 是把任意u∈U映射为[0, 1]上某个实值的函数，即 ：U→[0, 1] u→
1. 模糊集的定义(1/2) 定义5.1 设U是给定论域， 是把任意u∈U映射为[0, 1]上某个实值的函数，即 ：U→[0, 1] u→ 则称 为定义在U上的一个隶属函数，由 （对所有 ）所构成的集合F称为U上的一个模糊集， 称为u对F的隶属度。 说明： ① 模糊集F完全是由隶属函数 来刻画的， 把U中的每一个元素u都映射为[0, 1]上的一个值 。 ② 的值表示u隶属于F的程度，其值越大，表示u隶属于F的程度越高。当 仅取0和1时，模糊集F便退化为一个普通集合。

93 5.4.1 模糊集及其运算 1. 模糊集的定义(2/2) 例5.15 设论域U={20, 30, 40, 50, 60}给出的是年龄，请确定一个刻画模糊概念“年轻”的模糊集F。 解：由于模糊集是用其隶属函数来刻画的，因此需要先求出描述模糊概念“青年”的隶属函数。假设对论域U中的元素，其隶属函数值分别为： 则可得到刻画模糊概念“年轻”的模糊集 F={ 1, 0.8, 0.4, 0.1, 0} 说明其含义。

94 5.4.1 模糊集及其运算 (1) 离散且为有限论域的表示方法 F={ , , … , } 也可写成
2. 模糊集的表示(1/3) (1) 离散且为有限论域的表示方法 设论域 U={u1, u2, … , un}为离散论域，则其模糊集可表示为： F={ , , … , } 为了能够表示出论域中的元素与其隶属度之间的对应关系，扎德引入了一种模糊集的表示方式：先为论域中的每个元素都标上其隶属度，然后再用“+”号把它们连接起来，即 也可写成 其中，为ui对F的隶属度；“ / ui ”不是相除关系，只是一个记号；“+”也不是算术意义上的加，只是一个连接符号。

95 5.4.1 模糊集及其运算 在这种表示方法中，当某个ui对F的隶属度=0时，可省略不写。例如，前面例5.15的模糊集F可表示为：
2. 模糊集的表示(2/3) 在这种表示方法中，当某个ui对F的隶属度=0时，可省略不写。例如，前面例5.15的模糊集F可表示为： F= 1/ / / /50 有时，模糊集也可写成如下两种形式： 其中，前一种称为单点形式，后一种称为序偶形式。

96 5.4.1 模糊集及其运算 2. 模糊集的表示(3/3) (2) 连续论域的表示方法
如果论域是连续的，则其模糊集可用一个实函数来表示。例如，扎德以年龄为论域，取U=[0, 100]，给出了“年轻”与“年老”这两的模糊概念的隶属函数 (3) 一般表示方法 不管论域U是有限的还是无限的，是连续的还是离散的，扎德又给出了一种类似于积分的一般表示形式： 这里的记号不是数学中的积分符号，也不是求和，只是表示论域中各元素与其隶属度对应关系的总括。

97 5.4.1 模糊集及其运算 定义5.2 设F、G分别是U 上的两个模糊集，对任意u∈U，都有 成立，则称F等于G，记为F=G。
3. 模糊集的运算(1/2) 定义5.2 设F、G分别是U 上的两个模糊集，对任意u∈U，都有 成立，则称F等于G，记为F=G。 定义5.3 设F、G分别是U上的两个模糊集，对任意u∈U，都有 成立，则称F包含G，记为F G。 定义5.4 设F、G分别是U上的两个模糊集，则F∪G、F∩G分别称为F与G的并集、交集，它们的隶属函数分别为： 定义5.5 设F为U上的模糊集，称﹁F为F的补集，其隶属函数为：

98 5.4.1 模糊集及其运算 例5.16 设U={1,2,3}，F和G分别是U上的两个模糊集，即 F=小=1/1+0.6/2+0.1/3
3. 模糊集的运算(2/2) 例5.16 设U={1,2,3}，F和G分别是U上的两个模糊集，即 F=小=1/1+0.6/2+0.1/3 G=大=0.1/1+0.6/2+1/3 则 F∪G=(1∨0.1)/1+(0.6∨0.6)/2+(0.1∨1)=1/1+0.6/1+1/1 F∩G=(1∧0.1)/1+(0.6∧0.6)/2+(0.1∧1)=0.1/1+0.6/1+0.1/1 ﹁F=(1-1)/1+(1-0.6)/2+(1-0.1)=0.4/2+0.9/3 从这个例子可以看出，两个模糊集之间的运算实际上就是逐点对隶属函数作相应的运算。

99 5.4.2 模糊关系及其运算 设V与W是两个普通集合，V与W的笛卡尔乘积为 V×W ={(v,w)∣任意 ，任意 }
1. 模糊关系的定义(1/4) 设V与W是两个普通集合，V与W的笛卡尔乘积为 V×W ={(v,w)∣任意 ，任意 } 所谓从V到W的关系R，是指V×W上的一个子集，即 R V×W 记为 对于V×W中的元素(v,w)，若(v,w)∈R，则称v与w有关系R； 若(v,w) R，则称v与w没有关系。

100 5.4.2 模糊关系及其运算 例5.17 设V={1班，2班，3班}，W={男队，女队} 则V×W中有6个元素，即
1. 模糊关系的定义(2/4) 例5.17 设V={1班，2班，3班}，W={男队，女队} 则V×W中有6个元素，即 V×W ={(1班，男队)，(2班，男队)，(3班，男队)，(1班，女队)，(2班，女队)，(3班，女队)} 其中，每个元素是一代表队。假设要进行一种双方对垒的循环赛，则每一个赛局都是V×W中的一个子集，它构成了V×W上的一个关系。

101 5.4.2 模糊关系及其运算 定义5.6 设Fi是Ui(i=1,2,…,n)上的模糊集，则称
1. 模糊关系的定义(3/4) 定义5.6 设Fi是Ui(i=1,2,…,n)上的模糊集，则称 为F1,F2,…,Fn的笛卡尔乘积，它是U1×U2×…×Un上的一个模糊集。 定义5.7 在U1×U2×…×Un上的一个n元模糊关系R是指以U1×U2×…×Un为论域的一个模糊集，记为

102 5.4.2 模糊关系及其运算 1. 模糊关系的定义(4/4) 例5.18 设有一组学生 U={u1,u2}={秦学，郝玩}，一些在计算机上的活动V={v1,v2,v3}={编程，上网，玩游戏} 并设每个学生对各种活动的爱好程度分别为 i=1,2；j=1,2,3，即 则U×V上的模糊关系R为

103 5.4.2 模糊关系及其运算 2. 模糊关系的合成(1/2) 定义5.8 设R1与R2分别是U×V与V×W上的两个模糊关系，则R1与R2的合成是从U到W的一个模糊关系，记为 R1οR2 。其隶属函数为 其中，∧和∨分别表示取最小和取最大。

104 5.4.2 模糊关系及其运算 例5.19 设有以下两个模糊关系 则R1与R2的合成是
2. 模糊关系的合成(2/2) 例5.19 设有以下两个模糊关系 则R1与R2的合成是 其方法是把R1的第i行元素分别与R2的第j列的对应元素相比较，两个数中取最小者，然后再在所得的一组最小数中取最大的一个，并以此数作为R1οR2的元素R(i,j)。

105 5.4.2 模糊关系及其运算 3. 模糊变换 定义5.9 设F={μF(u1),μF(u2),.., μF(un),}是论域U上的模糊集，R是U×V上的模糊关系，则FοR=G 称为模糊变换。 例5.20 设F=(1, 0.6, 0.2) 则G= FοR={1∧1∨0.6∧0.5∨0.2∧0, 1∧0.5∨0.6∧1∨0.2∧0.5, ∧0∨0.6∧0.5∨0.2∧1, 1∧0∨0.6∧0∨0.2∧0.5,} ={1, 0.6, 0.5, 0.2}

106 作 业 5-15 用遗传算法求f(x)=x﹒sin(10π﹒x)+1.0的最大值,其中x∈[-1,2]。（选作） 5-19 设有论域
作 业 5-15 用遗传算法求f(x)=x﹒sin(10π﹒x)+1.0的最大值,其中x∈[-1,2]。（选作） 5-19 设有论域 U={u1, u2, u3, u4, u5} 并设F、G是U上的两个模糊集，且有 F=0.9/u1+0.7/u2+0.5/u3+0.3/u4 G=0.6/u3+0.8/u4+1/u5 请分别计算 F∩G，F∪G，﹁F。 5-21设有如下两个模糊关系： 请写出R1与R2的合成R1οR2。

107 选 做 实 验 实验题目：基于剪枝技术的一字棋博弈系统 1. 实验目的
选 做 实 验 实验题目：基于剪枝技术的一字棋博弈系统 1. 实验目的 理解和掌握博弈树的启发式搜索过程，能够用某种程序语言建立一个简单的博弈系统。 2. 实验环境 在微型计算机上，任选一种编程语言。 3. 实验要求 (1) 规定棋盘大小为5行5列，要求自行设计估价函数，按极大极小搜索方法，并采用α-β剪枝技术。 (2) 采用人机对弈方式，一方走完一步后，等待对方走步，对弈过程每一时刻的棋局都在屏幕上显示出来。 (3) 提交完整的软件系统和相关文档，包括源程序和可执行程序。