第八章启发式算法.ppt

⑥ 单亲遗传法 单亲遗传的一个特点是只有一个父代，下一代的 产生通过单亲自身的基因变化 . 如选定一个单亲，随机选两个基因位置，将两个 位置的元素进行交换： 父代 1 1 0 1 0 0 1 子代 1 0 0 1 0 1 1 或选定两个交叉位，通过交叉位之内的基因倒排 得到子代 . 父代 1 1 0 1 0 0 1 子代 1 0 1 0 1 0 1 单亲遗传法使得染色体中的基因取值受到限制， 如例中的 1 的个数为 4 个，0 的个数为 3 因此限制搜 索的范围 . 在使用单亲遗传时应加大变异的概率 . 单 亲遗传法可以同双亲遗传法结合使用 . 第八章 启发式算法 ⑦ 基于 “ 与/或 ”交叉 法 对父代 A、B 按位 “ 与 ” 逻辑运算产生一子代 A ; 按位 “ 或 ” 逻辑运算产生另一子代 B . 父代 A 0100101101 父代 B 1101110100 子代 A 0100100100 子代 B 1101111101 该交叉策略在解背包问题中效果较好 . §3 遗传算法 适应函数 即目标函数就取每种方案实行后的利润， 为简单起，每种方案所对应的利润（适应值）恰为 这三位二进制所对应的十进制数值 . 确定群体规模 N GA 不是一个个的考虑方案，而是 同时考虑 N 个方案，体现了并行性 . 取 N =4，在 8 个方案中随机抽取 4 个方案作为初始群体 （第 0 代）. xi 011 001 110 010 f (xi) 3 1 6 2 总和 12 最小值 1 平均值 3 最大值 6 第八章 启发式算法 选择算子 希望 110 在新的群体中出现 次, 类似希望 011、010 各出现 1 次，而001 消失 . 因 GA 是随机的, 按概率随机选择，以上只是期望 . 6 3 2 1 如 随机数 5 选择的个体 110 2 12 9 011 010 110 由选择算子产生的新群体（可能有重复） 称为种群，其规模仍为 N . 011 001 110 010 0 3 4 10 12 §3 遗传算法 把当前群体中的个体按与适应值成比例的 概率 复制到新的群体中（适者生存）. 轮盘赌选择： 2、产生一个在 0 与 S 之间的随机数 m ; 步骤：1、求群体中所有个体的适应值的总和 S ; 3、从群体中编号为 1 的个体开始，将其适应 值与后继个体的适应值相加，直到累加和等 于或大于 m , 则停止. 其中那个最后加进去 的个体即为选择的个体 . xi 110 011 010 110 f (xi) 6 3 2 6 总和 17 最小值 2 平均值 4.25 最大值 6 选择算子作用的效果是提高了群体的平均适应值 及最差的适应值，低适应值的个体趋于被淘汰，高适 应值的个体趋于被复制. 但是以损失群体的多样性为 代价，选择算子并没有产生新的个体，当然群体中最 好个体的适应值不会改进 . 第八章 启发式算法 交叉（杂交）算子 交叉算子每次作用在种群中随机选取的两个个体上, 产生两个不同的子个体，它们一般与父个体不同，但又 包含两个父个体的遗传物质 . 介绍一个最简单的方法 . 首先，产生一个 1 到 l -1（其中 l 为染色体分量的 个数）的随机数 i (交叉点) , 然后配对的两个个体相互 交换从 i+1 到 l 的位子 . 如 对 x1，x2 配对且交叉点选 在 2 ，则 对种群要确定交叉概率 Pc , 随机选择 N×Pc 个个体进行交叉，其余不变 . 假设 Pc = 50% xi 111 010 010 110 f (xi) 7 2 2