算法合集之《遗传算法的特点及其应用》

算法合集之《遗传算法的特点及其应用》 IOI2002集训队论文 遗传算法的特点及其应用 张宁 上海复旦大学附属中学 张宁 TSP 1 TSP 第 1 页 共20页 IOI2002集训队论文 遗传算法的特点及其应用 张宁 遗传算法作为一门新兴学科，在信息学竞赛中还未普及，但由于遗传算法对 许多用传统数学难以解决或明显失效的复杂问，特别是优化问题，提供了一个 行之有效的新途径，且能够较好地解决信息学竞赛中的NP难题，因此值得我们进行深入的讨论。 要掌握遗传算法的应用技巧，就要了解它的各方面的特点。首先，让我们来 了解一下什么是遗传算法。 遗传算法（Genetic Algorithms，简称GA）是人工智能的重要新分支，是基于达尔文进化论，在计算机上模拟生命进化机制而发展起来的一门新学科。它 第 2 页 共20页 IOI2002集训队论文 遗传算法的特点及其应用 张宁 根据适者生存，优胜劣汰等自然进化规则来进行搜索计算和问题求解。 对许多用传统数学难以解决或明显失效的复杂问题，特别是优化问题，GA提供了一个行之有效的新途径，也为人工智能的研究带来了新的生机。 GA由美国J. H. Holland博士1975年提出，当时并没有引起学术界的关注， 因而发展比较缓慢。从80年代中期开始，随着人工智能的发展和计算机技术的 进步，遗传算法逐步成熟，应用日渐增多，不仅应用于人工智能领域（如机器学 习和神经网络），也开始在工业系统，如控制、机械、土木、电力工程中得到成 功应用，显示出了诱人的前景。与此同时，GA也得到了国际学术界的普遍肯定。 从1985年至今国际上已举行了五届遗传算法和进化计算会议，第一本《进 化计算》杂志1993年在MIT创刊，1994年IEEE神经网络汇刊出版了进化规划 理论几应用专集，同年IEEE将神经网络，模糊系统，进化计算三个国际会议合 并为’94IEEE全球计算智能大会（WCCI），会上发表进化计算方面的论文255篇，引起了国际学术界的广泛关注。 目前，GA已在组合优化问题求解、自适应控制、程序自动生成、机器学习、 神经网络训练、人工生命研究、经济组合等领域取得了令人著目的应用成果，GA也成为当前人工智能及其应用的热门课题。 遗传算法（Genetic Algorithms，以下简称GA）是基于自然选择，在计算 机上模拟生物进化机制的寻优搜索算法。 在自然界的演化过程中，生物体通过遗传（传种接代，后代与夫辈非常相像）、 变异（后代与夫辈又不完全相像）来适应外界环境，一代又一代地优胜劣汰，发 展进化。 GA则模拟了上述进化现象。它把搜索空间（欲求解问题的解空间）映射为 遗传空间，即把每一个可能的解编码为一个向量（二进制或十进制数字串），称 为一个染色体（chromosome，或个体），向量的每一个元素称为基因(genes)。所有染色体组成群体（population，或集团）。并按预定的目标函数（或某种评价 指标，如商业经营中的利润、工程项目中的最小费用、最短路径等）对每个染色 提进行评价，根据其结果给出一个适应度的值。 算法开始时先随机地产生一些染色体（欲求解问题的侯选解），计算其适应 度，根据适应度对诸染色体进行选择、交换、变异等遗传操作，剔除适应度低（性 能不佳）的染色体，留下适应度高（性能优良）的染色体，从而得到新的群体。 由于新群体的成员是上一代群体的优秀者，继承了上一代的优良性态，因而 在总体上明显优于上一代。GA就这样反复迭代，向着更优解的方向进化，直至 满足某种预定的优化指标。上述GA的工作过程可用图1简要描述。 第 3 页 共20页 IOI2002集训队论文 遗传算法的特点及其应用 张宁 问题的初始（侯选）解 编码为染色体（向量） 种群P（t） 计算各染色体适应度 复制 种群P（t）,种群P（t+1） 交换 通过遗传运算存优去劣 变异 种群P（t+1） N 种群满足预定指标 Y 解码染色体 问题解答空间 图1 遗传算法工作原理示意图 简单遗传算法的三个基本运算是选择、交换、变异，下面详细介绍。 选择运算又称为繁殖、再生，或复制运算，用于模拟生物界去劣存优的 自然选择现象。它从旧种群中选择出适应性强的某些染色体，放入匹配集（缓 冲区），为染色体交换和变异运算产生新种群做准备。适应度越高的染色体被 选择的可能性越大，其遗传基因在下一代群体中的分布就越广，其子孙在下 一代出现的数量就越多。有多种选择方法，使用比较普遍的一种是适应度比 例法，简述如下： 适应度比例法又称为轮转法，它把种群中所有染色体适应度的总和看作 一个轮子的圆周，而每个染色体按其适应度在总和中所占的比例占据轮子的 一个扇区。每次染色体的选择可看作轮子的一次随机转动，它转到哪个扇区 停下来，那个扇区对应的染色体就被选中。其实就是将适应度值视为其权值， 权值大的被选中的概率也大。尽管这种选择方法是随机的，但它与各染色体 适应度成比例。某一染色体被选中的概率（选择概率）为 第 4 页 共20页 IOI2002集训队论文 遗传算法的特点及其应用 张宁 Pc,f(x)c/f(x)i, 式中x为种群中第i个染色体对应的数字串，f(x)是第i个染色体的适ii 应度值，是种群中所有染色体的适应度值之和。 f(xi), 用适应度比例法进行选择时，首先计算每个染色体的适应度，然后按比 例于各染色体适应度的概率进入交换（匹配）集的染色体，其具体步骤如下： （1） 计算每个染色体的适应度值f(x)； i （2） 累加所有染色体的适应度值，得最终累加值SUM=，记录对f(xi), 应于每个染色体的中间累加值g(x)； i （3） 产生一个随机数N，0标准

excel标准偏差excel标准偏差函数exl标准差函数国标检验抽样标准表免费下载红头文件格式标准下载