Chapter9 神经网络与遗传算法(二)课件

1、Chap10神经网络与遗传算法(二)遗传算法目录(遗传算法)10.4 遗传算法10.5 基于遗传算法的分类学习系统附: 进化神经网络10.4 遗传算法 遗传算法（Genetic Algorithms,GA）是模拟生物在自然环境中的遗传和进化过程而形成的一种自适应全局优化搜索算法。它模拟了生物的繁殖、交配和变异现象，从初始的种群，产生一群更适应环境的后代。 1975年美国Michigan大学J.Holland教授提出。美国人De.Jong博士将遗传算法应用于函数优化Goldberg成了遗传算法的框架。 10.4 遗传算法 遗传学原理遗传是作为一种指令码封装在每个染色体（个体）中，并以基因（位）的

2、形式包含在染色体（个体）中。基因杂交和基因突变能产生对环境适应性强的后代，通过优胜劣汰的自然选择，适应值高的基因结构就保存下来。 选择适应值高的染色体进行复制，通过遗传算子：选择、交叉（重组）、变异，来产生一群新的更适应环境的染色体，形成新的种群。 这样一代一代不断繁殖、进化，最后收敛到一个最适应环境的个体上，求得问题的最优解。 10.4.1遗传算法基本原理初始化初始种群（编码成位串形式）计算每一个染色体（个体）的适应值是否满足优化准则输出结果YesNo选择交叉变异 产生新一代种群遗传算子 遗传算法的处理流程图（1）问题编码 如何将问题描述成位串的形式，即问题编码。一般将问题中各参数用二进制编

3、码，构成子串，再将子串拼接起来构成“染色体”位串。 不同串长和不同的码制，对问题求解的精度和遗传算法收敛时间会有很多影响。 目前也出现采用其它编码方式，如用向量、规则来表示染色体。 （2）初始群体的生成遗传算法是群体型操作，这样必须为遗传操作准备一个由若干初始解组成的初始群体。初始群体的每个个体都是通过随机方法产生的（3）适应值函数的确定 适应值函数是根据目标函数确定的。适应值总是非负的，任何情况下总是希望越大越好。适应值函数的选取至关重要，它直接影响到算法的收敛速度即最终能否找到最优解。函数优化问题可直接将目标函数本身作为适应值函数10.4.2遗传算子 1、选择(Selection)算子依据

4、每个染色体的适应值大小，适应值越大，被选中的概率就越大，其子孙在下一代产生的个数就越多。选择操作是建立在群体中个体的适应值评估基础上的，目前常用的选择算子有适应值比例法、最佳个体保存法、期望值方法等。2、交叉(Crossover)算子通过染色体重组来产生新一代染色体。如有两个用二进制编码的个体A和B。交叉前后为： A=a1a2a3a4a5 A=a1a2a3b4b5 B=b1b2b3b4b5 B=b1b2b3a4a5 (父代) (子代)遗传算法用于优化计算 10.4.3遗传算法实例 问题：求发f(x)=x2在0，31上的 最大值。一、初始种群1.编码：用五位二进制表示x，有x=0 0 0 0 0

5、 0 x=31 1 1 1 1 1 2.初始种群随机产生4个个体：13 ， 24 ， 8 ，193.适应值fi直接用目标函数作为适应值：fi=xi2非负 ; (2)逐步增大4.选择率ps和期望值选择率： ps=fi/fi平均适应值： f =fi/n期望值： fi/f5.实选值期望值取整数 编号初始种群位串 参数值x值目标适应值f(x)=x2选择率fi/fi期望值fi/f实选值12340 1 1 0 11 1 0 0 00 1 0 0 0 1 0 0 1 1132489169576643610.140.490.060.310.581.970.221.231201总和平均值最大值117029357

6、61.000.250.494.001.001.974.01.02.0初始种群参数计算二、遗传选择后的交配池（下划线部分交叉）交叉对象（随机选择）交叉位置（随机选择）新的种群xf(x)=x20 1 1 0 11 1 0 0 01 1 0 0 0 1 0 0 1 1214344220 1 1 0 01 1 0 0 11 1 0 1 1 1 0 0 0 0 12252716144625729256总和平均值最大值1754439729说明：1.选择（繁殖） 在种群众，实选值（期望值）高者多繁殖；实选值（期望值）低者少繁殖或不繁殖。 繁殖（复制）的个体放入交配池中。2.交叉 随机选择交配对象（相同个体不

7、交配），如个体1和2，3 和4。 随机选择交叉点进行交叉。三、再遗传一代编号初始种群位串 参数值x值目标适应值f(x)=x2选择率fi/fi期望值fi/f实选值12340 1 1 0 01 1 0 0 11 1 0 1 11 0 0 0 0122527161446257292560.080.360.420.150.331.421.660.580121总和平均值最大000.250.424.001.001.664.01.02.0选择后的交配池（下划线部分交叉）交叉对象（随机选择）交叉位置（随机选择）新的种群xf(x)=x21 1 0 0 11 1 0 1 11 1 0 1

8、 1 1 0 0 0 0214311331 1 0 1 11 1 0 0 11 1 0 0 0 1 0 0 1 127252419729625576361总和平均值最大值229157272910.4.4遗传算法的特点 遗传算法是进行群体的搜索。它对多个个体进行群体搜索，构成一个不断进化的群体序列，它能找到全局最优解（优于爬山法）遗传算法是一种随机搜索方法，三个算子都是随机操作，利用概率转移规则。遗传算法的处理对象是问题参变量进行编码的个体，而不是参变量自身。参变量编码成位串个体，通过遗传算子进行操作。不是对参数变量进行直接操作。遗传算法利用适应值信息，而不需要导数或其它辅助信息。遗传算法用适应

9、值评估个体，用遗传算子产生更优后代，不需要像神经网络中用梯度公式引导。 隐含并行性：遗传算法是对N个位串个体进行运算，它隐含了大量的模式（用通配符#包含的个体）遗传机器学习10.5基于遗传算法的分类学习系统我们研制的遗传分类学习系统GCLS是一种字符串规则（分类器）的学习系统。它将规则“条件condition”和“结论action”合并成消息个体，也称分类器。适应值设计成分类器（规则）覆盖消息的个数，覆盖消息个数越多，规则的有效性愈大。GCLS系统由五个部件组成 检测器 消息表 分类器 测试表 作用器分类器系统的详细结构框图如下：检测器消息表信任分配算法工作分类器遗传算法测试表作用器客观环境增

10、生操作精炼分类器系统的工作流程1. 初始化所有预置参数。2. 将环境信息放入消息表中。3. 对初始种群调用信任分配算法，修改其中规 则的适应值。4. 对种群进行合并操作，合并后的种群设为种 群M。系统的工作流程5. 假如种群M已经收敛，则复制该种群的规则到精炼分类器中，而后跳至步骤（8）。6. 调用遗传算法，生成新一代种群L，将其与种群M合并后送给种群F，从而形成新的初始种群。7. 返回步骤（3）。8. 对测试表T调用精炼分类器规则，生成结论部分。9. 将T送往作用器，转换成实际的输出值以作用于环境。应用实例 这是一个学习识别脑出血和脑血栓两种疾病的诊断规则的应用实例。为了作出判断，应当考虑如

11、下几个方面的特征（属性）：高 血 压：00 无，01 有动 脉 硬 化：00 无，01 有起 病 方 式：00 慢，01 快偏 瘫：00 否，01 是瞳孔不等大：00 否，01 是两 便 失 禁：00 否，01 是呕 吐：00 否，01 是语言障碍：00 否，01 是意识障碍：00 无，01 深度，10 轻度膝腱反射：00 无，01 活跃，10 不活跃病理反射：00 阴性（-），01 阳性（+）病情发展：00 慢，01 快类 别：00 脑血栓，01 脑出血编码原则获取知识1、编码方式 ：每个训练例子是由12个特征和1个 类别组成。动脉硬化偏瘫两便失禁语言障碍膝腱反射病情发展0100010101

12、0101010110010101高血压起病方式瞳孔不等大呕吐意识障碍病理反射类别 将例子编码成二进制字符串：消息就是一个有24位条件，2位结论组成的二元组。 如上面的例子M=(010001010101010101100101),(01)识别效果 本试验在对30个训练样本进行学习后，得到如图5.4所示9个规则：学习时间Tm=65m，学习终止于第170代。获取规则如下：1、高血压=有瞳孔不等大=是膝腱反射=不活跃 脑出血 （11）2、瞳孔不等大=是语言障碍=是 脑出血 （12）3、高血压=有起病方式=快意识障碍=深度 脑出血 （13）4、起病方式=快瞳孔不等大=是 脑出血 （4）5、膝腱反射=不活

13、跃 脑出血 （1）6、高血压=有病情发展=快 脑出血 （15）7、高血压=有动脉硬化=有起病方式=慢 脑血栓 （13）8、动脉硬化=有病情发展=慢 脑血栓 （15）9、动脉硬化=有意识障碍=无 脑血栓 （12）附：进化神经网络 遗传算法和神经网络是当前常用的两种优化搜索技术，也是当前研究的一个热点。将遗传算法和神经网络结合，可以充分利用两者的优点，使新算法既有神经网络的学习能力和鲁棒性，又有遗传算法的全局随机搜索能力，从而能更好地解决实际问题。基于遗传算法的神经网络设计设计思想： 用遗传算法构造人工神经网络时，我们将网络的误差用来构造适应值函数。 一组以编码形式出现的网络结构和相关参数，则可被认为是神经网络学