遗传算法.pptVIP

2005-12-16 第二节 遗传算法 一、相关概念 染色体(chromosome)或个体(individual) 把每一个可能的解编码为一个向量，用来描述基本的遗传结构。例如，用0，1 组成的串可以表示染色体。 基因 向量中的每一个元素 适应度(fitness) 每个染色体所对应的一个适应值。在优化问题中，适应度来自于一个目标评价函数。 群体(population) 由染色体组成的集合。 代遗传操作 遗传操作作用于群体而产生新的群体。 二、基本算法 三、基本遗传算子 选择算子(Selection) 交叉算子(Crossover) 变异算子(Mutation) 例 在[0, 31]的取值范围找出使函数f(x)=x2最大的x。 pop-size=4 Pc=1 Pm=0.011 * * 遗传算法(GA)是在20世纪60年代提出来的，是受遗传学中自然选择和遗传机制启发而发展起来的一种搜索算法。它的基本思想是使用模拟生物和人类进化的方法求解复杂的优化问题，因而也称为模拟进化优化算法。遗传算法在计算原理上是自适应的，结构上是并行的，而且模仿了人的智能处理特征，因而成为人工智能的一个重要研究领域。 遗传算法将择优与随机信息交换结合在一起，在每一代中，用上代中最好的，即选择最适应环境的位或片段形成新的人工生物集。虽然遗传算法是随机化方法，但它不是简单的随机搜索，而是有效利用历史信息来推测新的搜索点。所以，遗传算法是计算机与遗传学相结合的产物。 CR2被选中与其他染色体进行交叉 Pc=1 群体中所有的染色体将会进行交叉操作；pc=0.5 群体中只有一半的染色体进行交叉操作，其余一半不进行任何改变，直接补充到新群体中。 遗传算法(GA)是一种搜索算法。它的基本思想是使用模拟生物和人类进化的方法求解复杂的优化问题，因而也称为模拟进化优化算法。遗传算法在计算原理上是自适应的，结构上是并行的，而且模仿了人的智能处理特征，因而成为人工智能的一个重要研究领域。 遗传算法将择优与随机信息交换结合在一起，在每一代中，用上代中最好的，即选择最适应环境的位或片段形成新的人工生物集。虽然遗传算法是随机化方法，但它不是简单的随机搜索，而是有效利用历史信息来推测新的搜索点。所以，遗传算法是计算机与遗传学相结合的产物。 用于比较不同的解以确定哪 一个解是更好的一个措施。 用于模拟生物界去劣存优的自然选择现象。它从旧种群中选择出适应性强的某些染色体，放人匹配集(缓冲区)，为染色体交换和变异运算产生新种群作准备。 适应度越高的染色体被选择的可能性越大，其遗传基因在下一代群体中的分布就越广，其子孙在下一代出现的数量就越多。 轮盘法 (1) 计算每个染色体xi 的适应度f(xi)； (2) 找出群体的适应度之和； (3) 计算某染色体xi的选择概率pi； (4) 计算每个染色体的中间累计概率； (5) 生成区间[0, 1]内的随机数r ； (6) 如果r q1，选择第一个染色体x1，否则选择第i个染色体,使得qi-1 r ? qi,放入缓冲区； (7) 重复执行(5)(6)直到缓冲区中有足够多的染色体。 6.5% 25.4% 35.9% 42.2% (1) 缓冲区中任选两个染色体(双染色体)； (2) 随机选择交换点位置J，0JL(染色体长度)； (3) 交换双亲染色体交换点右边的部分。（单点交叉） 具体做法： 例 J=51011011010110010 两点10011010 例 第6位突变随机地将某染色体的某个基因 0?1 或 1?0 编码：最简单但要具有完整的表现力 二进制 m=5 初始群体：随机创建一个指定长度的染色体的群体 CR1=01101 CR2=11000 CR3=01000 CR4=10011 评价：直接利用目标函数值作为染色体的适应度 361 19 10011 4 64 8 01000 3 576 24 11000 2 169 13 01101 1 f(x) x(十进制数) 代码 CRi n=1 选择操作 361 19 10011 4 64 8 01000 3 576 24 11000 2 169 13 01101 1 f(x) X (十进制数) 代码 CRi 总和? 1170 1.00 0.31 0.