第4章(3遗传算法)好文档.ppt

1、第4章,计算智能的仿生技术 (3) 遗 传 算 法,43 遗传算法,431 遗传算法原理 432 优化模型的遗传算法求解 433 基于遗传的分类学习系统,4.3.1 遗传算法原理,遗传算法（Genetic Algorithms,GA）是模拟生物在自然环境中的遗传和进化过程而形成的一种自适应全局优化搜索算法。 它模拟了生物的繁殖、交配和变异现象，从初始的种群，产生一群更适应环境的后代。,1975年美国Michigan大学J.Holland教授提出。 美国人De.Jong博士将遗传算法应用于函数优化。 Goldberg完成了遗传算法的框架。,4.3.1.1 遗传算法概述,遗传算法（Genetic

2、Algorithms，GA）是一种基于遗传学的搜索优化算法。 遗传是作为一种指令码封装在每个染色体（个体）中，并以基因（位）的形式包含在染色体（个体）中。 在遗传算法中，“染色体”对应的是数据或数组，通常是由一维的串结构数据来表现。串上各个位置对应“基因”，而各位置上的值对应基因的取值。基因组成的串就是染色体，或者叫做基因型个体。一定数量的个体组成了群体。,遗传算法将问题的每个可能的解按某种形式进行编码，编码后的解称作染色体（个体）。 随机选取N个染色体（个体）构成初始种群，再根据预定的评价函数对每个染色体计算适应值，使得性能较好的染色体具有较高的适应值。,选择适应值高的染色体进行复制，通过遗

3、传算子：选择、交叉（重组）、变异，来产生一群新的更适应环境的染色体，形成新的种群。 这样一代一代不断繁殖、进化，最后收敛到一个最适应环境的个体上，求得问题的最优解。,遗传算法的处理流程图,4.3.1.2遗传算法中的基本要素,遗传算法中包含了如下五个基本要素： 1）问题编码 2）初始群体的设定 3）适应值函数的设计 4）遗传操作设计 5）控制参数设定（主要是指群体大小和使用遗传操作的概率等） 这五个要素构成了遗传算法的核心内容。,（1）问题编码,如何将问题描述成位串的形式，即问题编码。一般将问题中各参数用二进制编码，构成子串，再将子串拼接起来构成“染色体”位串。 不同串长和不同的码制，对问题求解

4、的精度和遗传算法收敛时间会有很多影响。 目前也出现采用其它编码方式，如用向量、规则来表示染色体。,（2）初始群体的生成,遗传算法是群体型操作，这样必须为遗传操作准备一个由若干初始解组成的初始群体。 初始群体的每个个体都是通过随机方法产生的。,（3）适应值函数的确定,适应值函数是根据目标函数确定的。适应值总是非负的，任何情况下总是希望越大越好。 适应值函数的选取至关重要，它直接影响到算法的收敛速度即最终能否找到最优解。 函数优化问题可直接将目标函数本身作为适应值函数。,（4）控制参数,参数主要有个体编码长度、群体大小M、交叉概率Pc、变异概率Pm、终止代数T等 这些参数对遗传算法的运行影响很大，

5、需要认真选择。,4.3.1.3 遗传算子,1、选择(Selection)算子 依据每个染色体的适应值大小，适应值越大，被选中的概率就越大，其子孙在下一代产生的个数就越多。 选择操作是建立在群体中个体的适应值评估基础上的，目前常用的选择算子有适应值比例法、最佳个体保存法、期望值方法等。,2、交叉(Crossover)算子 通过染色体重组来产生新一代染色体。 如有两个用二进制编码的个体A和B。 交叉前后为： A=a1a2a3a4a5 A=a1a2a3b4b5 B=b1b2b3b4b5 B=b1b2b3a4a5 (父代) (子代),3、变异(Mutation)算子 变异增加了遗传算法找到接近最优解的

6、能力。 变异就是以很小的概率，随机地改变字符串某个位置上的值。把某一位的内容进行变异。 在二进制编码中，就是将某位0变成1，1变成0。 如：110010的第四位变异成110110 （父代） （子代）,4.3.1.4 遗传算法的理论基础,1.模式定理 遗传算法的理论基础是Holland提出的模式定理。一个模式(Schema)就是一个描述种群中在位串的某些确定位置上具有相似性的位串子集的相似性模板(Similarity Template)。 模式定理是遗传算法的理论基础，它说明： 高适应值、长度短、阶数低的模式在后代中至少以指数增长包含该模式H的位串的数目。 原因在于遗传使高适应值的模式复制更多的

7、后代。,2基因块假设 高适应值、长度短、低阶的模式叫基因块。基因块假说： 长度短的、低阶的、高适应值的模式(基因块)通过遗传操作繁殖、交换、变异，的逐渐进化，形成潜在的适应性较高的位串。 该假设指出，通过遗传算法能寻找到接近全局最优解的能力。,4.3.1.5 遗传算法的特点,遗传算法是进行群体的搜索。 它对多个个体进行群体搜索，构成一个不断进化的群体序列，它能找到全局最优解（优于爬山法） 遗传算法是一种随机搜索方法，三个算子都是随机操作，利用概率转移规则。,遗传算法的处理对象是问题参变量进行编码的个体，而不是参变量自身。 参变量编码成位串个体，通过遗传算子进行操作。不是对参数变量进行直接操作。

8、 遗传算法利用适应值信息，而不需要导数或其它辅助信息。 遗传算法用适应值评估个体，用遗传算子产生更优后代，不需要像神经网络中用梯度公式引导。,隐含并行性： 遗传算法是对N个位串个体进行运算，它隐含了大量的模式（用通配符#包含的个体）,4.3.2 优化模型的遗传算法求解,遗传算法用于优化计算例,例1：求发f(x)=x2 在0，31上的 最大值。 一、初始种群 1.编码：用五位二进制表示x，有 x=0 0 0 0 0 0 x=31 1 1 1 1 1 2.初始种群 随机产生4个个体：13 ， 24 ， 8 ，19 3.适应值fi 直接用目标函数作为适应值：fi=xi2,非负 ; (2)逐步增大 4

9、.选择率ps和期望值 选择率： ps=fi/fi 平均适应值： f =fi/n 期望值： fi/f 5.实选值 期望值取整数,初始种群参数计算,二、遗传,说明：,1.选择（繁殖） 在种群众，实选值（期望值）高者多繁殖；实选值（期望值）低者少繁殖或不繁殖。 繁殖（复制）的个体放入交配池中。 2.交叉 随机选择交配对象（相同个体不交配），如个体1和2，3 和4。 随机选择交叉点进行交叉。,3.变异 取变异概率pe=0.01，表示每100个体中有一个个体的一位发生变异。（暂不变异） 新的种群，其平均值和最大值都有很大提高。 均值：293 439 最大值：576 729 新种群中四个个体，有2个变好：

10、25，25；2个变坏：12，16。,三、再遗传一代,单纯用交叉而没有用变异，则遗传多少代得不到最优解31(1 1 1 1 1 )。主要是第三位所有个体都是0，这样只能得到27（1 1 0 1 1） 次优解。 若在第四位中挑选一个个体进行变异，由0变成1，在进行遗传将会得到最优解。,说明：,例2：旅行商路径问题（TSP）,已知n个城市的地理位置（x,y），求经过所有城市，并回到出发城市且每个城市仅经过一次的最短距离。 这是一个NP完全问题，其计算量为城市个数的指数量级。现用遗传算法来解决这个问题。,1、编码,每条路径对应一个个体，个体形式地表示为R=City_No|City_No互不重复n，n为

11、城市数。例如对于n=10的TSP问题，对其中一个个体 它表示一条城市路径： 3 1 5 7 8 9 10 4 2 6,2、适应值函数,每个个体代表一条可能的路径。个体n的适应值为： 其中N为种群数，Dn为 沿个体标示的城市序列的所经过的距离： 其中ni表示个体中第i位的城市编号，n11=n1。 适应值为非负，且取值越大越好。 表示所有个体的路径长度的总和,3、交叉,随机地从种群中选出要交叉的两个不同个体，随机地选取一个交叉段。交叉段中两个个体的对应部分通过匹配换位实现交叉操作。对个体A和B： A9 8 4 |5 6 7| 1 3 2 10 B8 7 1 |4 10 3| 2 9 6 5 交叉段

12、 对个体A，对交叉段中由B换位来的数，如4、10、3，在A中其它位相同的数进行反交换，即4换为5，10换为6，3换为7；对个体B，相似处理，最后得到： A，9 8 5 |4 10 3| 1 7 2 6 B，8 3 1 |5 6 7| 2 9 10 4,4、变异,根据变异概率Pe，随机地从种群中选出要变异的个体，随机地在该个体上选出变异两个位置，然后两个位置上的城市序号进行交换。如： A =9 8 4 5 6 7 1 3 2 10 下划线部分为要变异的两个位置。 变异为： A=9 7 4 5 6 8 1 3 2 10,5、遗传算法结果,计算结果表明： n个城市的最佳路径接近一个外圈无交叉的环路。

13、,4.3.3 基于遗传的分类学习系统,分类器系统是一种学习字符串规则（又称分类器）的学习系统，它由规则与消息系统、信任分配系统及遗传算法三个主要部分组成，其中规则与消息系统是产生式系统的一种特殊形式。 产生式规则的一般形式为： IF THEN 在分类器系统中，对产生式规则的语法作了很大的限制，采用了定长的表示形式，从而适于采用遗传操作。,4.3.3.1遗传分类学习系统 GCLS的基本原理,我们研制的遗传分类学习系统GCLS是一种字符串规则（分类器）的学习系统。 它将规则“条件condition”和“结论action”合并成消息个体，也称分类器。 适应值设计成分类器（规则）覆盖消息的个数，覆盖消

14、息个数越多，规则的有效性愈大。,GCLS系统由五个部件组成,检测器 消息表 分类器 测试表 作用器 分类器系统的详细结构框图如下：,分类学习系统的工作流程,1. 初始化所有预置参数。 2. 将环境信息放入消息表中。 3. 对初始种群调用信任分配算法，修改其中规则的适应值。 4. 对种群进行合并操作，合并后的种群设为种 群M。,5. 假如种群M已经收敛，则复制该种群的规则到精炼分类器中，而后跳至步骤（8）。 6. 调用遗传算法，生成新一代种群L，将其与种群M合并后送给种群F，从而形成新的初始种群。 7. 返回步骤（3）。 8. 对测试表T调用精炼分类器规则，生成结论部分。 9. 将T送往作用器，转换成实际的输出值以作用于环境。,4.3.3.2 遗传分类器学习系统 GCLS的应用,这是一个学习识别脑出血和脑血栓两种疾病的诊断规则的应用实例。为了作出判断，应当考虑如下几个方面的特征（属性）：,编码原则,获取知识,1、编码方式 ：每个训练例子是由12个特征和1个 类别组成。,将例子编码成二进制字符串：消息就是一个有24位条件，2位结论组成的二元组。 如上面的例子： M=(010001010101010101100101),(01),获取知识,本试验在对30个训练样本进行学习后，