《第四章智能技术的决策支持和智能决策支持系统.ppt》由会员分享，可在线阅读，更多相关《第四章智能技术的决策支持和智能决策支持系统.ppt（95页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、LOGO现在学习的是第1页，共95页第四章智能技术的决策支持和智能决策支持系统(3)部分内容部分内容v4.4神经网络的决策支持神经网络的决策支持v4.5遗传算法的决策支持遗传算法的决策支持现在学习的是第2页，共95页4.4神经网络的决策支持神经网络的决策支持v神经元的结构神经元的结构现在学习的是第3页，共95页v神经元由神经元由细胞体、树突和轴突细胞体、树突和轴突三部分组成；三部分组成；v细胞体对接收到的信息进行处理；细胞体对接收到的信息进行处理；v轴突是较长的神经纤维，是发出信息的；轴突是较长的神经纤维，是发出信息的；v树突的神经纤维较短，是接收信息的；树突的神经纤维较短，是接收信息的；v一
2、一个个神神经经元元的的轴轴突突末末端端，与与另另一一个个神神经经元元的的树树突突之之间间密密切切接接触触，传递神经元冲动的地方称为突触。传递神经元冲动的地方称为突触。4.4神经网络的决策支持神经网络的决策支持现在学习的是第4页，共95页神经元具有如下性质：神经元具有如下性质：（1 1）多输入单输出；多输入单输出；（2 2）突触具有）突触具有加权加权的效果；的效果；（3 3）信息进行传递；）信息进行传递；（4 4）信息加工是信息加工是非线性。非线性。4.4神经网络的决策支持神经网络的决策支持现在学习的是第5页，共95页1、神经元的数学模型、神经元的数学模型 其其中中：V1、V2、Vn为为输输入入
3、，i为为该该神神经经元元的的输输出出，ij为为外外面面神神经经元元与与该该神神经经元元连连接接强强度度（即即权权值值）,为为阈阈值值，f(X)为为该该神神经经元的作用函数。元的作用函数。4.4神经网络的决策支持神经网络的决策支持现在学习的是第6页，共95页vMP（神经元的数学模型）（神经元的数学模型）模型方程为：模型方程为：v其中其中Wij是神经元之间的连接强度，是神经元之间的连接强度，vWii0，Wij（ij）是可调实数，由学习过程来调整。）是可调实数，由学习过程来调整。现在学习的是第7页，共95页2、神经元作用函数、神经元作用函数0,1阶梯函数阶梯函数:-1,1阶梯函数阶梯函数：现在学习的
4、是第8页，共95页神经元作用函数神经元作用函数 (-1,1)S型函数：型函数：(0,1)S型函数：型函数：现在学习的是第9页，共95页3、学习规则、学习规则神经元的学习规则是神经元的学习规则是Hebb规则。规则。Hebb学习规则学习规则：若：若i与与j两种神经元之间同时处于兴奋状两种神经元之间同时处于兴奋状态，则它们间的连接应加强，即：态，则它们间的连接应加强，即：Wij SiSj(0)这一规则与这一规则与“条件反射条件反射”学说一致，并得到神经细胞学说的学说一致，并得到神经细胞学说的证实。证实。设设1，当，当SiSj1时，时，Wij1，在在Si，Sj中有一个为中有一个为0时，时，Wij0。现
5、在学习的是第10页，共95页4.4.2 反向传播模型反向传播模型(BP模型模型)BP模模型型（Backpropagation），需需要要确确定定它它的的网网络络结结构构、作作用用函函数数和和误误差函数。差函数。1.多层网络结构多层网络结构:有输入层、输出层，一个或多个隐含层有输入层、输出层，一个或多个隐含层现在学习的是第11页，共95页 2.作用函数为作用函数为(0,1)S型函数型函数 3.误差函数误差函数对第对第p个样本误差计算公式为：个样本误差计算公式为：其中其中pi，Opi分别是期望输出与计算输出。分别是期望输出与计算输出。4.4.2 反向传播模型反向传播模型(BP模型模型)现在学习的是
6、第12页，共95页 公公式式推推导导思思想想是是：修修正正网网络络权权值值与与阈阈值值，使使误误差差函函数数沿沿梯度方向下降。梯度方向下降。BP网网络络表表示示：输输入入结结点点xj，隐隐结结点点yi，输输出出结结点点Ol，输输入入结结点点与与隐隐结结点点间间的的网网络络权权值值为为Wij，隐隐结结点点与与输输出出结结点点间间的的网网络权值为络权值为Tli，输出结点的期望输出为，输出结点的期望输出为tl。4.4.2 反向传播模型反向传播模型(BP模型模型)现在学习的是第13页，共95页2.输出结点计算输出：输出结点计算输出：其中：其中：其中：其中：BP模型的计算公式为：模型的计算公式为：4.4
7、.2 反向传播模型反向传播模型(BP模型模型)1.隐结点的输出：隐结点的输出：现在学习的是第14页，共95页3.输出结点的误差公式：输出结点的误差公式：4.4.2 反向传播模型反向传播模型(BP模型模型)现在学习的是第15页，共95页1.输出结点输出输出结点输出Ol计算公式计算公式（1）输入结点的输入）输入结点的输入xj（2）隐结点的输出：）隐结点的输出：其中：其中：Wij连接权值，结点阈值连接权值，结点阈值。(3)输出结点输出：输出结点输出：其中：其中：Tij连接权值，连接权值，结点阈值结点阈值。2输出层（隐结点到输出结点间）的修正公式输出层（隐结点到输出结点间）的修正公式（1）输出结点的期
8、望输出）输出结点的期望输出tl（2）误差控制）误差控制所有样本误差：所有样本误差：BP模型计算公式汇总模型计算公式汇总现在学习的是第16页，共95页其中一个样本误差：其中一个样本误差：其中，其中，p为样本数，为样本数，n为输出结点数。为输出结点数。（3）误差公式：）误差公式：（4）权值修正：）权值修正：其中其中k为迭代次数。为迭代次数。（5）阈值修正：阈值修正：BP模型计算公式汇总模型计算公式汇总现在学习的是第17页，共95页3、隐结点层（输入结点到隐结点间）的修正公式、隐结点层（输入结点到隐结点间）的修正公式（1）误差公式：）误差公式：（2）权值修正：）权值修正：（3）阈值修正：）阈值修正：
9、BP模型计算公式汇总模型计算公式汇总现在学习的是第18页，共95页误差反向传播示意图误差反向传播示意图隐结点误差的含义：隐结点误差的含义：现在学习的是第19页，共95页 求 l(2)i(1)Ol=f（l）yi=f（i）l(k+1)=l(k)+l(2)j 修正（Tli，l），（Wij，i）修正权 l(2)=Ol(1Ol)(dlOl)Til(k+1)=Til(k)l(2)yi i(1)=yi(1yi)Wij(k+1)=Wij(k)i(1)xj输出节点lTli 隐节点 i修正权Wij输入节点xji(k+1)=i(k)+i(1)现在学习的是第20页，共95页 按按问问题题要要求求，设设置置输输入入结结
10、点点为为两两个个（x1,x2），输输出出结结点点为为1个个（z），隐隐结结点点定定为为2个个（y1，y2），各各结结点点阈阈值值和和网网络络权权值值见见图图说说明。明。异或问题求解实例异或问题求解实例现在学习的是第21页，共95页计算机计算结果计算机计算结果迭代次数：迭代次数：16745次；总误差：次；总误差：0.05隐层网络权值和阈值：隐层网络权值和阈值：w11=5.24 w12=5.23 1=8.01 w21=6.68 w22=6.64 2=2.98输出层网络权值和阈值：输出层网络权值和阈值：T1=-10 T2=10 =4.79异或问题求解实例异或问题求解实例现在学习的是第22页，共95页
11、一、神经网络专家系统特点一、神经网络专家系统特点1.神神经经元元网网络络知知识识库库：为为神神经经元元之之间间的的连连接接强强度度（权权值值）。这这种种知识是分布式存储的，适合并行处理。知识是分布式存储的，适合并行处理。2.推推理理机机：是是基基于于神神经经元元的的信信息息处处理理过过程程。它它是是以以P模模型型为为基基础础的，采用数值计算方法。的，采用数值计算方法。4.4.3神经网络专家系统及实例神经网络专家系统及实例现在学习的是第23页，共95页3.成成熟熟的的学学习习算算法法：感感知知机机采采用用delta规规则则；BP模模型型采采用用误误差差沿沿梯梯度度方方向向下下降降、以以及及隐隐节
12、节点点的的误误差差由由输输出出结结点点误误差差反反向向传传播播的的思想进行的。思想进行的。.容容错错性性好好：由由于于信信息息是是分分布布式式存存贮贮，在在个个别别单单元元上上即即使使出出错错或或丢失丢失，所有单元的总体计算结果，可能并不改变所有单元的总体计算结果，可能并不改变。4.4.3神经网络专家系统及实例神经网络专家系统及实例现在学习的是第24页，共95页二、神经网络专家系统结构二、神经网络专家系统结构用用 户户知知识识工工程程师师 学学 习习 样样 本本 确定确定 系统系统 框架框架 神经元神经元 学习学习 形成形成 学习样本学习样本 知识库知识库（分布式）（分布式）实际问题实际问题
13、参数参数输入模式输入模式 转换转换 推推 理理 机机 制制输出模式输出模式 转换转换实际问题实际问题 结果结果开发环开发环境境运行环境运行环境现在学习的是第25页，共95页（一）确定系统框架（一）确定系统框架1.完成对神经元网络的拓朴结构设计：完成对神经元网络的拓朴结构设计：（1）神经元个数）神经元个数（2）神经元网络层次）神经元网络层次（3）网络单元的连接）网络单元的连接2.确定神经元的作用函数和阈值确定神经元的作用函数和阈值作用函数用得较多的有两种：作用函数用得较多的有两种：（1）阶梯函数）阶梯函数（2）S型函数型函数阈值的选取可为定值如阈值的选取可为定值如 i=0或或 i=0.5，或者进
14、行迭代计算。，或者进行迭代计算。现在学习的是第26页，共95页（二）学习样本（二）学习样本学习（训练）样本：实际问题中学习（训练）样本：实际问题中已有结果已有结果的实例。的实例。（三）学习算法（三）学习算法不同的网络模型采用不同的学习算法，但都以不同的网络模型采用不同的学习算法，但都以Hebb规则为基础。规则为基础。1.Perception(感知机感知机)模型：采用模型：采用delta规则。规则。2.Back-propagation(反向传播反向传播)模型：采用误差反向传播模型：采用误差反向传播方法。方法。现在学习的是第27页，共95页（四）推理机（四）推理机推理机是基于神经元的信息处理过程推
15、理机是基于神经元的信息处理过程。1.神经元神经元j的输入：的输入：其其中中，Wjk为为神神经经元元j和和下下层层神神经经元元k之之间间的的连连接接权权值值。Ok为为k神神经元的输出。经元的输出。2.神经元神经元j的输出的输出:Oj=f(Ij-j)j为阈值，为阈值，f为神经元作用函数。为神经元作用函数。现在学习的是第28页，共95页（五）知识库（五）知识库知识库主要是存放各个神经元之间连接权值。知识库主要是存放各个神经元之间连接权值。由于上下两层间各神经元都有关系，用数组表示为由于上下两层间各神经元都有关系，用数组表示为(Wij)i行对应上层结点，行对应上层结点，j列对应下层结点。列对应下层结点
16、。现在学习的是第29页，共95页（六）输入模式转换（六）输入模式转换实际问题的输入，一般是以一种概念形式表示，而神经元实际问题的输入，一般是以一种概念形式表示，而神经元的输入，要求以的输入，要求以(-,)间的数值形式表示，因此需要将文字概间的数值形式表示，因此需要将文字概念转换成数值。念转换成数值。建立两个向量集：建立两个向量集：（1）实际输入实际输入概念集概念集：各输入节点的具体物理意义。：各输入节点的具体物理意义。（2）神经元输入神经元输入数值集数值集：各输入节点的数值。：各输入节点的数值。现在学习的是第30页，共95页（七）输出模式转换（七）输出模式转换实际问题的输出，一般也是以一种概念
17、形式表示。而神经元的实际问题的输出，一般也是以一种概念形式表示。而神经元的输出，一般是在输出，一般是在0,1间的数值形式，这需要将数值向文字间的数值形式，这需要将数值向文字概念的转换。概念的转换。现在学习的是第31页，共95页v城市医疗服务能力评价系统。城市医疗服务能力评价系统。5个输入：个输入：病床数、医生数、医务人员数、门诊数和死亡率；病床数、医生数、医务人员数、门诊数和死亡率；4个输出：级别个输出：级别v、g、a和和b；建立一个三层神经元网络。建立一个三层神经元网络。v训练样本（集）训练样本（集）:10城市的数据城市的数据,训练后可对其它城市进行评价。训练后可对其它城市进行评价。v输输入
18、入输输出出模模式式转转换换：文文字字概概念念的的数数值值转转换换。输输入入节节点点数数据据范范围围范范围围(-,)，输出数据范围，输出数据范围0,1。v输输入入节节点点：五五个个节节点点分分别别表表示示五五个个指指标标，每每个个指指标标节节点点都都有有v,g,a,b四种可能。四种可能。三、神经网络专家系统实例三、神经网络专家系统实例现在学习的是第32页，共95页城市医疗服务能力评价系统城市医疗服务能力评价系统神经网络结构图神经网络结构图现在学习的是第33页，共95页城市医疗服务能力训练集城市医疗服务能力训练集现在学习的是第34页，共95页文字概念的数值转换的五方案：文字概念的数值转换的五方案：
19、方案方案1：v=3g=1a=-1b=-3方案方案2：v=1.5g=0.5a=-0.5b=-1.5方案方案3：v=6g=2a=-2b=-6方案方案4：v=1g=0.66a=0.33b=0方案方案5：v=10g=7a=4 b=1计计算算结结果果表表明明，方方案案2收收敛敛最最快快Count=360，计计算算结结果果也也很很合合理理，其次是方案其次是方案1，Count=451，方案，方案3,4,5均较差。均较差。结论：尽量采用结论：尽量采用(-1,1)附近较合适。附近较合适。现在学习的是第35页，共95页4种动物样本：种动物样本：（1）某动物是暗斑点、黄褐色、有毛发、吃肉，它就是豹。）某动物是暗斑点
20、、黄褐色、有毛发、吃肉，它就是豹。（2）某动物是黄褐色、有毛发、吃肉、黑条纹，它就是虎。）某动物是黄褐色、有毛发、吃肉、黑条纹，它就是虎。（3）某动物是不飞、黑白色、会游泳、有羽毛，它就是企鹅。）某动物是不飞、黑白色、会游泳、有羽毛，它就是企鹅。（4）某动物是有羽毛、善飞，它就是信天翁）某动物是有羽毛、善飞，它就是信天翁。4.4.4神经元网络的容错性神经元网络的容错性现在学习的是第36页，共95页现在学习的是第37页，共95页训练完成后，对样本进行缺省条件输入。训练完成后，对样本进行缺省条件输入。（1）缺）缺1个条件的情况个条件的情况（2）缺）缺2个条件的情况个条件的情况（3）介于中间的情况）
21、介于中间的情况缺省条件推理结果表缺省条件推理结果表现在学习的是第38页，共95页 从计算结果中，可以看出容错效果很好，从计算结果中，可以看出容错效果很好，缺缺1个条件时：例如对豹缺省黄褐色条件时，输出结果仍然个条件时：例如对豹缺省黄褐色条件时，输出结果仍然是豹（是豹（0.8463）；）；缺缺2个条件时：对虎缺省黄褐色和多一个不飞的条件时，个条件时：对虎缺省黄褐色和多一个不飞的条件时，输出结果仍然是虎（输出结果仍然是虎（0.9286）；）；输入豹和虎的共同信息（黄褐色、有毛发、吃肉）时，输入豹和虎的共同信息（黄褐色、有毛发、吃肉）时，神经网络的输出是既靠近豹（神经网络的输出是既靠近豹（0.339
22、4）又靠近虎（）又靠近虎（0.4203），输出结论：该动物是一个介于豹和虎的中间新品种。），输出结论：该动物是一个介于豹和虎的中间新品种。现在学习的是第39页，共95页4.5、遗传算法的决策支持、遗传算法的决策支持 遗传算法遗传算法(Genetic Algorithm，GA)是模拟生物进化的是模拟生物进化的自然选择自然选择和和遗传机制遗传机制的一种寻优算法。的一种寻优算法。（1 1）模拟）模拟生物的繁殖和变异现象；生物的繁殖和变异现象；（2 2）从任意）从任意一初始种群一初始种群出发，出发，产生产生一群新的更适应环境一群新的更适应环境的后代。的后代。（3 3）不断繁殖、进化，最后收敛到一个最优
23、个体上。）不断繁殖、进化，最后收敛到一个最优个体上。优点：对复杂的优化问题优点：对复杂的优化问题无需建模无需建模和和复杂运算复杂运算，只需利用，只需利用遗传算法的遗传算法的算子，即可算子，即可求得问题的求得问题的最优解或满意解。最优解或满意解。现在学习的是第40页，共95页遗传算法发展的三个阶段遗传算法发展的三个阶段（1 1）7070年代的兴起阶段年代的兴起阶段 19751975年美国年美国Michigan Michigan 大学大学J.HollandJ.Holland首次系统地阐述了遗传算法的基本理论和首次系统地阐述了遗传算法的基本理论和方法。方法。在这一时期的大部分研究都处于在这一时期的大
24、部分研究都处于理论研究理论研究和和建立实验模型阶段建立实验模型阶段。（2 2）8080年代的发展阶段年代的发展阶段 19801980年年SmithSmith教授将遗传算法教授将遗传算法应用于机器学习领域应用于机器学习领域，研制出了一个著名的，研制出了一个著名的分分类器类器(Classifier)(Classifier)系统系统。这期间许多学者对遗传算法进行了大量的这期间许多学者对遗传算法进行了大量的改进和发展改进和发展，提出了许多成功的，提出了许多成功的遗遗传算法模型传算法模型，使遗传算法应用于更广泛的领域。，使遗传算法应用于更广泛的领域。（3 3）9090年代的高潮阶段年代的高潮阶段 进入进
25、入9090年代后，遗传算法作为一种年代后，遗传算法作为一种实用实用、高效高效、鲁棒性强鲁棒性强的优化技术，得到了的优化技术，得到了极为迅速的发展。极为迅速的发展。现在学习的是第41页，共95页一、遗传算法的工作过程一、遗传算法的工作过程 遗传算法是遗传算法是一种群体型操作一种群体型操作，该操作以群体中的，该操作以群体中的所有个体为所有个体为对象对象。选择（选择（selection）、交叉（）、交叉（crossover）和变异（）和变异（mutation）是遗传算法的三个）是遗传算法的三个主要操作算子主要操作算子，它们构成了遗传操作，它们构成了遗传操作（Genetic operation），），
26、使遗传算法具有了其他传统方法所没有使遗传算法具有了其他传统方法所没有的特性。的特性。遗传算法的工作过程如图所示：遗传算法的工作过程如图所示：4.5遗传算法原理遗传算法原理现在学习的是第42页，共95页遗传算法的工作过程遗传算法的工作过程遗遗传传算算子子编码和初始群体形成编码和初始群体形成输出种群输出种群选择选择 个体适应值满意否？个体适应值满意否？交叉交叉产生新一代群体产生新一代群体变异变异NY现在学习的是第43页，共95页1.群体中个体的编码群体中个体的编码如何将问题描述成位串的形式，即问题编码。一般将问如何将问题描述成位串的形式，即问题编码。一般将问题的题的参数参数用用二进制位（基因）编码
27、构成二进制位（基因）编码构成子串子串，再将，再将子串拼接子串拼接起来构成起来构成“染色体染色体”位串位串。2.适应值函数的确定适应值函数的确定适应值函数适应值函数(即评价函数即评价函数)是是根据目标函数确定的根据目标函数确定的。适应值。适应值总是非负的，任何情况下总是希望越大越好。如果目标总是非负的，任何情况下总是希望越大越好。如果目标函数不是取最大值时，需要将它映射成适应值函数。函数不是取最大值时，需要将它映射成适应值函数。现在学习的是第44页，共95页 遗传算法的执行过程中，每一代有许多不同的染色体（个体）遗传算法的执行过程中，每一代有许多不同的染色体（个体）同时存在，这些染色体中哪个保留
28、同时存在，这些染色体中哪个保留(生存生存)、哪个淘汰、哪个淘汰(死亡死亡)是根据是根据它们对环境的适应能力决定的，适应性强的有更多的机会保留它们对环境的适应能力决定的，适应性强的有更多的机会保留下来。下来。适应性强弱是计算个体适应值函数适应性强弱是计算个体适应值函数f(x)的值来判别的，这个值的值来判别的，这个值称为称为适应值适应值(fitness)。适应值函数适应值函数f(x)的构成与目标函数有密切关系，往往是目的构成与目标函数有密切关系，往往是目标函数的变种。标函数的变种。3 遗传算法的三个算子遗传算法的三个算子现在学习的是第45页，共95页（一）选择（一）选择(Selection)算子算
29、子 它又称复制它又称复制(reproduction)、繁殖算子。、繁殖算子。选择是从种群中选择生命力强的染色体产生新种群的过程。依据每选择是从种群中选择生命力强的染色体产生新种群的过程。依据每个染色体的适应值大小，适应值越大，被选中的概率就越大，其子孙在个染色体的适应值大小，适应值越大，被选中的概率就越大，其子孙在下一代产生的个数就越多。下一代产生的个数就越多。选择操作是建立在群体中个体的适应值估评基础上的，目选择操作是建立在群体中个体的适应值估评基础上的，目前常用的选择算子有以下几种：前常用的选择算子有以下几种：重组重组(recombination)、配对、配对(breeding)算子算子。
30、现在学习的是第46页，共95页 染色体重组分两步染色体重组分两步（1）首先在新复制的群体中随机选取两个个体；）首先在新复制的群体中随机选取两个个体；（2）沿着这两个个体）沿着这两个个体(字符串字符串)随机取一个位置，二者互换从该位随机取一个位置，二者互换从该位置起的末尾部分。置起的末尾部分。如有两个用二进制编码的个体如有两个用二进制编码的个体A和和B。长度。长度L=5，A=a1a2a3a4a5，B=b1b2b3b4b5随机选择一整数随机选择一整数k1，L-1，设，设k=4，经交叉后变，经交叉后变为：为：A=a1a2a3|a4a5 A=a1a2a3b4b5B=b1b2b3|b4b5 B=b1b2
31、b3a4a5交叉算子在遗传算法中起着核心作用。交叉算子在遗传算法中起着核心作用。现在学习的是第47页，共95页 选择和交叉算子基本上完成了遗传算法的大部分搜索功能，选择和交叉算子基本上完成了遗传算法的大部分搜索功能，而变异则增加了遗传算法找到接近最优解的能力。而变异则增加了遗传算法找到接近最优解的能力。变异就是以很小的概率，随机地改变字符串某个位置上变异就是以很小的概率，随机地改变字符串某个位置上的值。变异操作是按位（的值。变异操作是按位（bit）进行的，即把某一位的内容进行）进行的，即把某一位的内容进行变异。变异。在二进制编码中，就是将某位在二进制编码中，就是将某位0变成变成1，1变成变成0
32、。变异发生的。变异发生的概率即变异概率概率即变异概率Pm都取得很小都取得很小(一般在一般在0.0010.02之间之间)，它保证，它保证了遗传算法的有效性。了遗传算法的有效性。现在学习的是第48页，共95页控制参数的设定控制参数的设定遗传算法中的参数包括：群体中个体的数目、交叉遗传算法中的参数包括：群体中个体的数目、交叉概率、变异概率等。这些参数的设定随具体问题的不同概率、变异概率等。这些参数的设定随具体问题的不同将有所差别，带有经验性，它会影响遗传算法的迭代收将有所差别，带有经验性，它会影响遗传算法的迭代收敛过程。敛过程。现在学习的是第49页，共95页遗传算法的理论基础遗传算法的理论基础v1.
33、模式定理模式定理遗传算法的理论基础是遗传算法的理论基础是Holland提出的模式定理。一个模提出的模式定理。一个模式式(Schema)就是一个描述种群中在位串的某些确定位置上具就是一个描述种群中在位串的某些确定位置上具有相似性的位串子集的相似性模板有相似性的位串子集的相似性模板(SimilarityTemplate)。模式定理是遗传算法的理论基础，它说明模式定理是遗传算法的理论基础，它说明高适应值、长度短、高适应值、长度短、阶数低的模式在后代中至少以指数增长包含该模式阶数低的模式在后代中至少以指数增长包含该模式H的位串的位串的数目。的数目。原因在于遗传使高适应值的模式复制更多的后代。原因在于遗
34、传使高适应值的模式复制更多的后代。现在学习的是第50页，共95页遗传算法的理论基础遗传算法的理论基础v2基因块假设基因块假设高适应值、长度短、低阶的模式叫基因块。高适应值、长度短、低阶的模式叫基因块。长度短的、低阶的、高适应值的模式长度短的、低阶的、高适应值的模式(基因块基因块)通过遗传操作通过遗传操作繁殖、交换、变异，再繁殖、再交换、再变异的逐渐进化，形成繁殖、交换、变异，再繁殖、再交换、再变异的逐渐进化，形成潜在的适应性较高的位串，这就是基因块假说。潜在的适应性较高的位串，这就是基因块假说。该假设指出，通过遗传算法能寻找到接近全局最优解的该假设指出，通过遗传算法能寻找到接近全局最优解的能力
35、。能力。现在学习的是第51页，共95页1.遗传算法的处理对象是问题参数的编码个体（位串）遗传算法的处理对象是问题参数的编码个体（位串）遗传算法要求将问题的参数编码成长度有限的位串。遗传算遗传算法要求将问题的参数编码成长度有限的位串。遗传算法是在求解问题的编码串上进行操作，从中找出高适应值的位法是在求解问题的编码串上进行操作，从中找出高适应值的位串，而不是对问题目标函数和它们的参数直接操作。遗传算法串，而不是对问题目标函数和它们的参数直接操作。遗传算法不受函数限制条件不受函数限制条件(如导数存在、连续性、单极值等如导数存在、连续性、单极值等)的约束。的约束。遗传算法的基本特征遗传算法的基本特征
36、现在学习的是第52页，共95页2.遗传算法的搜索是从问题解位串集开始搜索，而不是从单个解开始遗传算法的搜索是从问题解位串集开始搜索，而不是从单个解开始在最优化问题中，传统的方法是从一个点开始搜索，如爬山法。在最优化问题中，传统的方法是从一个点开始搜索，如爬山法。一般复杂问题会在一般复杂问题会在“地形地形”中出现若干中出现若干“山峰山峰”，传统的方法很，传统的方法很容易走入假容易走入假“山峰山峰”。而遗传算法同时从种群的每个个体开始搜。而遗传算法同时从种群的每个个体开始搜索，象一张网罩在索，象一张网罩在“地形地形”上，数量极大的个体同时在很多区域上，数量极大的个体同时在很多区域中进行搜索，这样就
37、减少了陷入局部解的可能性。中进行搜索，这样就减少了陷入局部解的可能性。现在学习的是第53页，共95页v3.遗传算法只使用目标函数遗传算法只使用目标函数(即适应值即适应值)来搜索，而不需要导数来搜索，而不需要导数等其他辅助信息。等其他辅助信息。传统搜索算法需要一些辅助信息，如梯度算法需要导数，传统搜索算法需要一些辅助信息，如梯度算法需要导数，当这些信息不存在时，这些算法就失效了。而遗传算法只当这些信息不存在时，这些算法就失效了。而遗传算法只需目标函数和编码串，因此，遗传算法几乎可以处理任何需目标函数和编码串，因此，遗传算法几乎可以处理任何问题。问题。现在学习的是第54页，共95页v4.遗传算法使
38、用的三种遗传算子是一种随机操作，而不是确定性遗传算法使用的三种遗传算子是一种随机操作，而不是确定性规则规则遗传算法使用随机操作，但并不意味着遗传算法是简单的随遗传算法使用随机操作，但并不意味着遗传算法是简单的随机搜索。遗传算法是使用随机工具来指导搜索向着一个最优解前机搜索。遗传算法是使用随机工具来指导搜索向着一个最优解前进。进。现在学习的是第55页，共95页4.5.2优化模型的遗传算法求解优化模型的遗传算法求解优化模型的计算优化模型的计算是遗传算法最基本的也是最重要的研是遗传算法最基本的也是最重要的研究和应用领域之一。一般说来，优化计算问题通常带有究和应用领域之一。一般说来，优化计算问题通常带
39、有大量的局部极值点，往往是不可微的、不连续的、多维大量的局部极值点，往往是不可微的、不连续的、多维的、有约束条件的、高度非线性的问题。的、有约束条件的、高度非线性的问题。精确地求解优化问题的全局最优解一般是不可能的。精确地求解优化问题的全局最优解一般是不可能的。现在学习的是第56页，共95页1 1、适应值函数、适应值函数遗遗传传算算法法在在进进化化搜搜索索中中用用目目标标函函数数即即适适应应值值函函数数为为依依据。据。遗遗传传算算法法的的目目标标原原函函数数不不受受连连续续可可微微的的约约束束,且且定定义义域可以为任意集合。域可以为任意集合。对对目目标标函函数数的的唯唯一一要要求求是是，对对输
40、输入入个个体体可可计计算算出出能能进进行行比比较较的的非负适应值非负适应值。这一特点使得遗传算法应用范围很广。这一特点使得遗传算法应用范围很广。适应值函数评估适应值函数评估是是选择操作的依据选择操作的依据，适应值函数设计直接，适应值函数设计直接影响到遗传算法的性能。影响到遗传算法的性能。现在学习的是第57页，共95页遗传算法中，适应值函数要比较排序并在此基础上计算选遗传算法中，适应值函数要比较排序并在此基础上计算选择概率，所以适应值函数的值要取正值。择概率，所以适应值函数的值要取正值。将目标函数映射成求最大值形式且函数值非负的适应将目标函数映射成求最大值形式且函数值非负的适应值函数是必要的。值
41、函数是必要的。现在学习的是第58页，共95页2 2、约束条件的处理、约束条件的处理遗传算法是由适应值来评估和引导搜索，而对求解问题的遗传算法是由适应值来评估和引导搜索，而对求解问题的约束条件不能明确地表示出来。用遗传算法求解这些带约束约束条件不能明确地表示出来。用遗传算法求解这些带约束的问题，需要进行一些处理。的问题，需要进行一些处理。在等式约束方程中，对在等式约束方程中，对P个等式方程中抽出个等式方程中抽出P个变量，经过线个变量，经过线性组合变换后，用其余变量表示为该性组合变换后，用其余变量表示为该P个变量的等式，并将它代个变量的等式，并将它代入目标函数中，消去该入目标函数中，消去该P个变量
42、。这样，在目标函数中，就包含个变量。这样，在目标函数中，就包含了这些等式约束条件。了这些等式约束条件。现在学习的是第59页，共95页3、遗传算法的迭代终止条件、遗传算法的迭代终止条件当适应值函数的最大值已知时，一般以发现满足最大值或当适应值函数的最大值已知时，一般以发现满足最大值或准最优解作为遗传算法迭代终止条件。准最优解作为遗传算法迭代终止条件。但是，在许多优化计算问题中，适应值函数的最大值但是，在许多优化计算问题中，适应值函数的最大值并不清楚，迭代终止条件一般定为：并不清楚，迭代终止条件一般定为：群体中群体中个体的进化个体的进化已趋于稳定状态已趋于稳定状态，即发现，即发现占群体中一定占群体
43、中一定比例的个体比例的个体已完全是同一个体已完全是同一个体。现在学习的是第60页，共95页旅行商问题（旅行商问题（TSP）的遗传算法求解实例）的遗传算法求解实例 已知已知n个城市的地理位置（个城市的地理位置（x,y），求经过所有城市，），求经过所有城市，并回到出发城市且每个城市仅经过一次的最短距离。并回到出发城市且每个城市仅经过一次的最短距离。其计算量为城市个数的指数量级。现用遗传算法其计算量为城市个数的指数量级。现用遗传算法来解决这个问题。来解决这个问题。现在学习的是第61页，共95页1 1、编码、编码每每条条路路径径对对应应一一个个个个体体，个个体体形形式式地地表表示示为为R=City_N
44、o|City_No互互不不重重复复n，n为为城城市市数数。例例如如对对于于n=10的的TSP问问题题，对对其其中中一一个个个体个体它表示一条城市路径它表示一条城市路径：3 1 5789104263 1 5 7 8 9 10 4 2 6现在学习的是第62页，共95页2 2、适应值函数、适应值函数每个个体代表一条可能的路径。个体每个个体代表一条可能的路径。个体n的适应值为：的适应值为：其中其中N为种群数，为种群数，Dn为为沿个体标示的城市序列的所经过的距离：沿个体标示的城市序列的所经过的距离：其中其中ni表示个体中第表示个体中第i位的城市编号，位的城市编号，n11=n1。适应值为非负，且取值越大越
45、好。适应值为非负，且取值越大越好。表示所有个体的路径长度的总和表示所有个体的路径长度的总和现在学习的是第63页，共95页3 3、交叉、交叉 随随机机地地从从种种群群中中选选出出要要交交叉叉的的两两个个不不同同个个体体，随随机机地地选选取取一一个个交交叉叉段段。交交叉叉段段中中两两个个个个体体的的对对应应部部分分通通过过匹匹配配换换位位实实现现交交叉叉操操作作。对对个个体体A和和B：A984|567|13210B871|4103|2965交叉段交叉段对个体对个体A，对，对交叉段交叉段中由中由B换位来的数换位来的数，如，如4、10、3，在，在A中其它位相同的数进中其它位相同的数进行行反交换反交换，
46、即，即4换为换为5，10换为换为6，3换为换为7；对个体；对个体B，相似处理，最后得到：，相似处理，最后得到：A，985|4103|1726B，831|567|29104现在学习的是第64页，共95页4 4、变异、变异 根根据据变变异异概概率率Pe，随随机机地地从从种种群群中中选选出出要要变变异异的的个个体体，随随机机地地在在该该个个体体上上选选出出变变异异两两个个位位置置，然然后后两两个个位位置置上上的的城城市市序号序号进行交换。如：进行交换。如：A=98456713210下划线部分为要变异的两个位置。下划线部分为要变异的两个位置。变异为：变异为：A=97456813210v计算结果表明：计
47、算结果表明：vn个城市的最佳路径接近一个外圈无交叉的环路。个城市的最佳路径接近一个外圈无交叉的环路。现在学习的是第65页，共95页4.5.3获取知识的遗传算法获取知识的遗传算法v1980年，年，Smith采用采用遗传算法遗传算法研制了一种研制了一种分类器系统，分类器系统，这是遗这是遗传算法在传算法在机器学习中机器学习中的重要应用系统。他使用的重要应用系统。他使用单个字符串单个字符串来表示一条规则来表示一条规则。v分类器系统的规则形式如下：分类器系统的规则形式如下：vIFTHENv意思是当条件（意思是当条件（condition）满足时，就可能采取行动）满足时，就可能采取行动（action）。）。
48、分类器系统的规则采用固定长度表示。这便于遗分类器系统的规则采用固定长度表示。这便于遗传算子的处理。传算子的处理。现在学习的是第66页，共95页一、分类学习系统的结构一、分类学习系统的结构检检测测器器消息表消息表遗传算法遗传算法分类器分类器信任分配算法信任分配算法测测试试表表作作用用器器客观环境客观环境现在学习的是第67页，共95页客观环境信息通过客观环境信息通过分类器系统分类器系统的的检测器检测器（Detector）被编码被编码成有限长的消息成有限长的消息（Messages）然后发往消息表；消息表中的消息然后发往消息表；消息表中的消息触发触发位串规则（称为分类器）位串规则（称为分类器），被触发
49、的分类器又向消息表发消息被触发的分类器又向消息表发消息，这些消息又有，这些消息又有可能触发其可能触发其它的分类器或引发一个行动。它的分类器或引发一个行动。通过通过执行机构（作用器执行机构（作用器Effector）作用于客观环境。）作用于客观环境。现在学习的是第68页，共95页1.检测器检测器（Detector）v一条消息一条消息Mi是一个二元组，其形式如下：是一个二元组，其形式如下：Mi=xi,yiv其中：其中：i为消息号；为消息号；x为条件部分，即训练例子的各特征编码，为条件部分，即训练例子的各特征编码，y为结论部分，即训练例子的类别。为结论部分，即训练例子的类别。例如：例如：(100010
50、11),(1011)是一条由一个是一条由一个8位条件和位条件和4位结论位结论组成的消息。组成的消息。2.消息表（消息表（MessageList）v包含当前所有的消息（训练例子集）。包含当前所有的消息（训练例子集）。现在学习的是第69页，共95页v3.分类器（分类器（Classifier）v所获得的规则中包含通配符所获得的规则中包含通配符#，如：，如：1#0，1110是一致的。是一致的。v规则集越小，系统的时间性能当然越好。规则集越小，系统的时间性能当然越好。v一个规则一个规则Ci是一个三元组，形式如下：是一个三元组，形式如下：Ci=Ui,Vi,fitnessi其中，其中，Ui是条件部分，是条件