第6章遗传算法及其应用(导论)报告.ppt

* Introduction of Artificial Intelligence THE END * * * * 6.2.4 选择 2. 选择个体方法 （2）锦标赛选择方法（tournament selection model） 锦标赛选择方法：从群体中随机选择个个体，将其中适应度最高的个体保存到下一代。这一过程反复执行，直到保存到下一代的个体数达到预先设定的数量为止。 随机竞争方法（stochastic tournament）：每次按赌轮选择方法选取一对个体，然后让这两个个体进行竞争，适应度高者获胜。如此反复，直到选满为止。 * 6.2.4 选择 2. 选择个体方法 最佳个体（elitist model）保存方法：把群体中适应度最高的个体不进行交叉而直接复制到下一代中，保证遗传算法终止时得到的最后结果一定是历代出现过的最高适应度的个体。 （3）最佳个体保存方法 * 6.2.5 交叉 1. 基本的交叉算子 （1）一点交叉（single-point crossover） 一点交叉：在个体串中随机设定一个交叉点，实行交叉时，该点前或后的两个个体的部分结构进行互换，并生成两个新的个体。 二点交叉：随机设置两个交叉点，将两个交叉点之间的码串相互交换。 （2）二点交叉 （two-point crossover） * 6.2.5 交叉 2. 修正的交叉方法 部分匹配交叉PMX：Goldberg D. E.和R. Lingle(1985) * 6.2.6 变异 （1）位点变异：群体中的个体码串，随机挑选一个或多个基因座，并对这些基因座的基因值以变异概率作变动。 （2）逆转变异：在个体码串中随机选择两点（逆转点），然后将两点之间的基因值以逆向排序插入到原位置中。 （3）插入变异：在个体码串中随机选择一个码，然后将此码插入随机选择的插入点中间。 （4）互换变异：随机选取染色体的两个基因进行简单互换。 （5）移动变异：随机选取一个基因，向左或者向右移动一个随机位数。 * 6.2.7 遗传算法的一般步骤 * 6.2.7 遗传算法的一般步骤 （1）使用随机方法或者其它方法，产生一个有N个染色体的初始群体 pop(1)， ； （2）对群体中的每一个染色体popi(t)，计算其适应值 （3）若满足停止条件，则算法停止；否则，以概率 从pop(t)中随机选择一些染色体构成一个新种群 * 6.2.7 遗传算法的一般步骤 （4）以概率 进行交叉产生一些新的染色体，得到一个新的群体 （5）以一个较小的概率 使染色体的一个基因发生变异，形成 ； ，成为一个新的群体 返回 （2）。 * 6.2.8 遗传算法的特点 可直接对结构对象进行操作。 利用随机技术指导对一个被编码的参数空间进行高效率搜索。 采用群体搜索策略，易于并行化。 仅用适应度函数值来评估个体，并在此基础上进行遗传操作，使种群中个体之间进行信息交换。 * 第6章 遗传算法及其应用 6.1 遗传算法的产生与发展 6.2 遗传算法的基本算法 6.3 遗传算法的改进算法 6.4 遗传算法的应用 * 6.3 遗传算法的改进算法 6.3.1 双倍体遗传算法 6.3.2 双种群遗传算法 6.3.3 自适应遗传算法 * 6.3.1 双倍体遗传算法 1. 基本思想 双倍体遗传算法采用显性和隐性两个染色体同时进行进化，提供了一种记忆以前有用的基因块的功能。 双倍体遗传算法采用显性遗传。 双倍体遗传延长了有用基因块的寿命，提高了算法的收敛能力，在变异概率低的情况下能保持一定水平的多样性。 * 6.3.1 双倍体遗传算法 2. 双倍体遗传算法的设计 （1）编码/解码：两个染色体（显性、隐性） （2）复制算子：计算显性染色体的适应度，按照显性染色体 的复制概率将个体复制到下一代群体中。 （3）交叉算子：两个个体的显性染色体交叉、隐性染色体也同时交叉。 （4）变异算子：个体的显性染色体按正常的变异概率变异；隐性染色体按较大的变异概率变异。 （5）双倍体遗传算法显隐性重排算子：个体中适应值较大的染色体设为显性染色体，适应值较小的染色体设为隐性染色体。 * 双种群遗传算法程序流程图 * 6.3.2 双种群遗传算法 基本思想 在遗传算法中使用多种群同时进化，并交换种群之间优秀个体所携带的遗传信息，以打破种群内的平衡态达到更高的平衡态，有利于算法跳出局部最优。 多