钱自强 关于遗传算法应用的分析与研究.pptVIP

关于遗传算法应用 的分析与研究 福州八中 钱自强 一个问题： 道路铺设 电网架设 网络构设 ………… 一个问题： 道路铺设 电网架设 网络构设 ………… 一个问题： 遗传算法 历史背景 遗传算法（Genetic Algorithm）是一种模拟自然选择和遗传的随机有哪些信誉好的足球投注网站算法。它由John Holland提出，最初用于研究自然系统的适应过程和设计具有自适应性能的软件。近年来，遗传算法作为问题求解和最优化的有效工具，已被非常成功地应用与解决许多最优化问题并越来越流行。 遗传算法－工作流程 遗传算法－多目标最小生成树 编码理论 遗传算法－多目标最小生成树 编码理论 估价函数 遗传算法－多目标最小生成树 编码理论 估价函数 遗传算子 遗传算法－多目标最小生成树 编码理论 估价函数 遗传算子 遗传算法－多目标最小生成树 算例分析 遗传算法－多目标最小生成树 算例分析 遗传算法－多目标最小生成树 算例分析 小结 编码理论 估价函数 遗传算子 * * IOI2005集训队论文 537 ( 　,154,……) 线形时间 Prim 算法 Kruskal算法 指数时间 有哪些信誉好的足球投注网站算法 40 50 40 e3,e1 50 30 50 e2,e3 30 40 50 e1,e2 生态破坏 难度系数 基本费用 方案 300 310 260 综合评价 (20,30,10) (30,10,20) (20,20,30) e1 e2 e3 CITY1 CITY2 CITY3 架设铁路的基本费用 架设铁路的难度系数 铁路造成的生态破坏 修建一条铁路需要考虑的因素 ×1 ×2 ×4 一个简单的例子 537 ( 　,154,……) 线形时间 Prim 算法 Kruskal算法 指数时间 有哪些信誉好的足球投注网站算法 天文数字 …… 1200y 15 30y 14 20m 10 8d 12 270d 13 6h 40s 2s 1s内 估计用时 11 9 8 1~7 数据规模 537 ( 　 ,154,……) 有哪些信誉好的足球投注网站算法的时间复杂度 我们真的要等1200年？ 如果有一种方法能在短短的时间内得到一组与最优解十分逼近的近似解呢？ 42 57 87 14 76 99 40 初始化群体 估价 －工作流程 问题的一个可行解 编码理论 编码理论 57 40 99 87 76 14 42 估价 保持遗传 交配遗传 变异遗传 概率控制 Prüfer编码机制 每一棵树与一个长度为n-2的数字串对应 对于任意一个长度为n-2的数字串也与唯一的一棵生成树相对应 ★编码过程 ▲ 编码串初始为空串 ▲ 令j为树中编号最小的叶节点； ▲ 如果j与i相邻，则把i加入当前编码串的最右端 ▲ 把j以及连接i和j的边从树中删除，这时候树只有n-1个顶点 ▲ 重复以上步骤直到树中只剩下一条边这时候得到的编码串即为相应树的Prüfer编码 ★解码过程 ▲设P为编码串，S为图的顶点编号不出现在P中的顶点的集合； ▲设i为S中编号最小的顶点，j为P中最左端的顶点，则将连接i和j的边加入到树中，然后分别把i和j从P和S中删除，如果P中不在出现顶点j则把j加入到S中 ▲重复以上步骤，直到P为空； ▲当P为空串时，S中刚好剩下两个顶点，将连接这两个顶点的边加入到树中，最后构成的树即为与最初P对应的生成树。 优势 可以很容易地随机生成一棵生成树 很适合执行各类遗传操作 估价函数设置 fi(x)表示待估价的染色体在目标i的费用情况，min[i]表示截止到上一代为止，产生的所有染色体在目标i的费用的最小值。 优势 更好的突出了每个染色体在各个目标上的优势 避免了由于每个目标的取值范围不同或者费用的整体趋势不同而造成的某些个体在某些目标的优势无法被体现 5 6 5 2 PARENT 1 交配遗传 错位交叉算子 从当前群体中抽出两条染色体，在两条染色体上随机抽取一个等位的长度不超过２的片段进行交换，并择择优选取。 7 5 ３ 8 PARENT 2 7　　　　　　 　　 　　　　　　2 2　　　　 　　　　8 优势 由于编码理论的性质，这种操作很大程度地保留了亲本优良特性，并且能一定程度上引入另一个样本一些特性。 变异遗传 从当前群体中抽出一条染色体(Parent)，在染色体上随机抽取一个位置，用一个随机的值替换。 单点变异算子 优势 由于编码理论的性质，这种操作也可以在较大程度上保留亲本的优良性质。 概率控制 保持遗传（54％） 交配遗传（45％） 变异遗传（ 1％） 通过测试结果我们可以看到遗传算法在解决组合优化类问题有着和其他算法无法比拟的强大优势，它的特点就是可以在较短的时间内，得到令人满意的解，而且算法相对简洁。对于现实生活中的大量常规算法无法