算法合集之《遗传算法应用的分析与研究》.ppt

《算法合集之《遗传算法应用的分析与研究》.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、关于遗传算法应用的分析与研究福州八中钱自强IOI2005集训队论文一个问题：道路铺设电网架设网络构设…………537(,154,……)线形时间Prim算法Kruskal算法指数时间搜索算法方案基本费用难度系数生态破坏e1,e2504030e2,e3503050e3,e1405040综合评价260310300(20,30,10)(30,10,20)(20,20,30)e1e2e3CITY1CITY2CITY3架设铁路的基本费用架设铁路的难度系数铁路造成的生态破坏修建一条铁路需要考虑的因素×1×2×4一个简单的例子一个问题：道路铺设电网架设网络构设…………537(,154,……)线形时间P

2、rim算法Kruskal算法指数时间搜索算法一个问题：数据规模1~789101112131415……估计用时1s内2s40s20m6h8d270d30y1200y天文数字537(,154,……)搜索算法的时间复杂度我们真的要等1200年？如果有一种方法能在短短的时间内得到一组与最优解十分逼近的近似解呢？遗传算法历史背景遗传算法（GeneticAlgorithm）是一种模拟自然选择和遗传的随机搜索算法。它由JohnHolland提出，最初用于研究自然系统的适应过程和设计具有自适应性能的软件。近年来，遗传算法作为问题求解和最优化的有效工具，已被非常成功地应用与解决许多最优化问题并越来越流行

3、。42578714769940初始化群体估价－工作流程问题的一个可行解编码理论编码理论57409987761442遗传算法－工作流程估价保持遗传交配遗传变异遗传概率控制遗传算法－多目标最小生成树编码理论Prüfer编码机制每一棵树与一个长度为n-2的数字串对应对于任意一个长度为n-2的数字串也与唯一的一棵生成树相对应★编码过程▲编码串初始为空串▲令j为树中编号最小的叶节点；▲如果j与i相邻，则把i加入当前编码串的最右端▲把j以及连接i和j的边从树中删除，这时候树只有n-1个顶点▲重复以上步骤直到树中只剩下一条边这时候得到的编码串即为相应树的Prüfer编码★解码过程▲设P为编码串，S为

4、图的顶点编号不出现在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、上的优势避免了由于每个目标的取值范围不同或者费用的整体趋势不同而造成的某些个体在某些目标的优势无法被体现遗传算法－多目标最小生成树编码理论估价函数遗传算子PARENT12565交配遗传错位交叉算子从当前群体中抽出两条染色体，在两条染色体上随机抽取一个等位的长度不超过２的片段进行交换，并择择优选取。PARENT28３577228优势由于编码理论的性质，这种操作很大程度地保留了亲本优良特性，并且能一定程度上引入另一个样本一些特性。变异遗传从当前群体中抽出一条染色体(Parent)，在染色体上随机抽取一个位置，用一个随机的值替换。单点变异算子优势由于编码理论的性质，这种操作也可以在较大程度上

6、保留亲本的优良性质。概率控制保持遗传（54％）交配遗传（45％）变异遗传（1％）遗传算法－多目标最小生成树编码理论估价函数遗传算子遗传算法－多目标最小生成树算例分析遗传算法－多目标最小生成树算例分析遗传算法－多目标最小生成树算例分析小结编码理论估价函数遗传算子通过测试结果我们可以看到遗传算法在解决组合优化类问题有着和其他算法无法比拟的强大优势，它的特点就是可以在较短的时间内，得到令人满意的解，而且算法相对简洁。对于现实生活中的大量常规算法无法解决的问题，遗传算法都有着良好的应用前景。谢谢！遗传算法不仅一种算法，更是一种思想。在各种常用算法中通过灵活地渗透进化的思想来解决问题，往往能够收

7、到事半功倍的效果。本论文的目的就是希望越来越多的信息学爱好者了解遗传算法，了解进化算法的思想。算法因为闪耀着睿智的光芒而美丽！