6 遗传算法与神经网络.ppt

遗传算法与神经网络 遗传算法简介 遗传算法与神经网络 遗传算法简介 Holland 在上世纪60年代提出了了遗传算法，并与他的同事一起完善了该算法； 算法特点 进化过程通过一代群体向下一代群体的演化完成； 每一个群体由若干个个体组成； 每个个体有一个染色体表示； 不同染色体有一系列的基因组成基因串；染色体的性能不同－适应度不同； 通过选择、交叉、变异算子完成新一代的进化。 遗传算法简介 标准遗传算法和基本概念 基因链码： （染色体） 每一个个体表示成一个基因链码； 可以由多种的形式：二进制，实数等等； 1551 ? 1100001000 群体：一些个体的集合； 适应度： 生物体对环境的适应能力； 对应于优化问题的函数值； 影响后面的选择算子 遗传算法简介 标准遗传算法和基本概念 交叉： 双亲 后代 X1 1000 | x1’ 1000 X2 0110 | x2’ 0110 遗传算法简介 标准遗传算法和基本概念 变异：在染色体的某些基因位置产生突变,产生新的个体 对于群体中的某个个体,基因链码,随机选择某一位,将该基因反转(0?1, 1?0) 100011000110 ? 100011010110 遗传算法简介 标准遗传算法和基本概念 选择：从当前群体中选出优良的个体,使他们有机会作为父代产生后代个体; 多种的算法方式:采用和适应度值成比例的概率方法来进行选择; 遗传算法简介 遗传算法的标准算法 1. 令进化代数g=0,并改（给）出初始化群体P(g); 2. 对于P(g)中每个个体进行计算适应度；并进行选择出下一代个体； 3. 从P(g)中选择两个个体,进行交叉、变异操作，完成新的一代群体P(g+1), g=g+1 4. 如果终止条件满足,则算法结束,否则转到2. 遗传算法简介 例子: 使用遗传算法求出函数最大值: 遗传算法简介 遗传算法简介 模式定理: 模式: {1, 0 *}组成的能够描述某些结构相似性的0,1字符串集的字符串. 100*1 模式阶:模式中确定位置的个数称作该模式的模式阶; 011*1* = 4 定义距:模式中第一个确定位置和最后一个确定位置之间的距离称为定义距; 011*1* = 4 模式定理:在选择、交叉和变异的作用下，具有低阶、短定义距以及平均适应度高于群体平均适应度的模式在后代中将以指数级增长； 遗传算法简介 基因块假设： 低阶、短定义距、高平均适应度的模式在遗传算子作用下，相互结合，能生成高阶、长定义距、高平均适应度的模式，可最终生成全局最优解。 遗传算法简介 遗传算法的设计 编码方法; 适应度函数; 遗传算子; 选择算子; 交叉算子; 变异算子; 其他问题: 参数选择,其他操作 遗传算法简介 编码方法: 遗传算法不能够直接处理问题空间,而只能处理以及因链码形式表示的个体; 将优化问题的解的参数形式转换成基因链码的表示形式—编码; 这个编码大都为一个维的形式; {0,1} 串 遗传算法简介 编码方法: 编码原则: 完备性:Completeness:对于问题可能解.也就是问题空间的所有可能解都能表示为所设计基因链码的形式; 健全性:Soundness:对于表达空间中的任何一个点都有问题空间中的一个点与之对应,即任何一个基因链码都对应一个可能的解; 非冗余性:non-redundancy:问题空间与表达空间一一对应; 完备性必须满足 遗传算法简介 编码方法 编码规则: (容易操作的原则) 有意义的基因块编码规则:所设计的编码的方案应当易于生成与所求问题相关的短定义距和低阶的基因块; 最小字符集编码规则:所设计的编码方案应采用最小的字符集意识问题得到自然的表示或描述; 遗传算法简介 编码方式： 二进制编码： 使用{0,1}串表示基因; 二进制编码方法能表达的模式最多; 简单易行; 符合最小字符集编码原则; 便于用模式定理进行分析; 遗传算法简介 编码方式: Gray 编码:可以克服Hamming距离“悬崖”问题:相近的二进制可能有较大的Hamming距离; 遗传算法简介 编码方法 实数编码: 直接采用十进制编码的特性,引入其它的一些遗传算子.通过引入一些专门设计的遗传算子,采用实数编码比采用二进制的编码算法平均效率高. 遗传算法简介 编码方法 有序串编码: 问题目标函数不仅与表示解的字符串个字符有关系,而且与它们相互之间的位置有关系;例如:TSP问题; 需要有特殊的能够保证产生合理的后代的遗传算子; 多参数映射编码: 可以将多个参数的编码串连起来即可; 遗传算法简介 编码方法