1、IOI2002 集训队论文 遗传算法的特点及其应用 张宁第 0 页 共 20 页遗传算法的特点及其应用上海复旦大学附属中学 张宁目录【关键 词】【摘要】【 正文】1 遗传算法的基本概念2 简单的遗传算法1 选择2 交换3 变异3 简单的遗传算法运算示例1 计算机公司的经营策略优化问题2 函数优化问题4 遗传算法应用举例1 子集和问题2 TSP（旅行商）问题5 结束语【附录】1 子集和问题源程序2 TSP（旅行商）问题源程序【参考文 献】IOI2002 集训队论文 遗传算法的特点及其应用 张宁第 1 页 共 20 页【关键词】遗传 算法 遗传 变异 染 色体 基因 群体【摘要】遗传算法是基于达尔
2、文进化论，在计算机上模拟生命进化机制而发展起来的一门新学科。它根据适者生存，优胜劣汰等自然进化规则来进行搜索计算和问题求解。文章的第一部分介绍了遗传算法的基本概念。第二部分介绍了遗传算法的原理以及三种运算：选择、交换、变异。第三部分着重介绍三种运算的具体实现，以及简单实例，主要体现遗传算法的实现过程。第四部分介绍了两个具体问题，都是属于 NP-完全问题，如何用遗传算法来解决，以及实现时的一些基本问题。文章在介绍遗传算法的原理以及各种运算的同时，还分析了一些应用中出现的基本问题，对于我们的解题实践有一定的指导意义。【正文】遗传算法作为一门新兴学科，在信息学竞赛中还未普及，但由于遗传算法对许多用传
3、统数学难以解决或明显失效的复杂问题，特别是优化问题，提供了一个行之有效的新途径，且能够较好地解决信息学竞赛中的 NP难题，因此值得我们进行深入的讨论。要掌握遗传算法的应用技巧，就要了解它的各方面的特点。首先，让我们来了解一下什么是遗传算法。1 遗传算法的基本概念遗传算法（Genetic Algorithms，简称 GA）是人工智能的重要新分支，是基于达尔文进化论，在计算机上模拟生命进化机制而发展起来的一门新学科。IOI2002 集训队论文 遗传算法的特点及其应用 张宁第 2 页 共 20 页它根据适者生存，优胜劣汰等自然进化规则来进行搜索计算和问题求解。对许多用传统数学难以解决或明显失效的复杂
4、问题，特别是优化问题，GA提供了一个行之有效的新途径，也为人工智能的研究带来了新的生机。GA由美国 J. H. Holland博士 1975年提出，当时并没有引起学术界的关注，因而发展比较缓慢。从 80年代中期开始，随着人工智能的发展和计算机技术的进步，遗传算法逐步成熟，应用日渐增多，不仅应用于人工智能领域（如机器学习和神经网络） ，也开始在工业系统，如控制、机械、土木、电力工程中得到成功应用，显示出了诱人的前景。与此同时，GA 也得到了国际学术界的普遍肯定。从 1985年至今国际上已举行了五届遗传算法和进化计算会议，第一本进化计算杂志 1993年在 MIT创刊，1994 年 IEEE神经网络
5、汇刊出版了进化规划理论几应用专集，同年 IEEE将神经网络，模糊系统，进化计算三个国际会议合并为94IEEE 全球计算智能大会（WCCI） ，会上发表进化计算方面的论文 255篇，引起了国际学术界的广泛关注。目前，GA 已在组合优化问题求解、自适应控制、程序自动生成、机器学习、神经网络训练、人工生命研究、经济组合等领域取得了令人著目的应用成果，GA也成为当前人工智能及其应用的热门课题。2 简单的遗传算法遗传算法（Genetic Algorithms，以下简称 GA）是基于自然选择，在计算机上模拟生物进化机制的寻优搜索算法。在自然界的演化过程中，生物体通过遗传（传种接代，后代与夫辈非常相像） 、
6、变异（后代与夫辈又不完全相像）来适应外界环境，一代又一代地优胜劣汰，发展进化。GA则模拟了上述进化现象。它把搜索空间（欲求解问题的解空间）映射为遗传空间，即把每一个可能的解编码为一个向量（二进制或十进制数字串） ，称为一个染色体（chromosome，或个体） ，向量的每一个元素称为基因(genes)。所有染色体组成群体（population，或集团） 。并按预定的目标函数（或某种评价指标，如商业经营中的利润、工程项目中的最小费用、最短路径等）对每个染色提进行评价，根据其结果给出一个适应度的值。算法开始时先随机地产生一些染色体（欲求解问题的侯选解） ，计算其适应度，根据适应度对诸染色体进行选择
7、、交换、变异等遗传操作，剔除适应度低（性能不佳）的染色体，留下适应度高（性能优良）的染色体，从而得到新的群体。由于新群体的成员是上一代群体的优秀者，继承了上一代的优良性态，因而在总体上明显优于上一代。GA 就这样反复迭代，向着更优解的方向进化，直至满足某种预定的优化指标。上述 GA的工作过程可用 图 1简要描述。IOI2002 集训队论文 遗传算法的特点及其应用 张宁第 3 页 共 20 页简单遗传算法的三个基本运算是选择、交换、变异，下面详细介绍。1 选择选择运算又称为繁殖、再生，或复制运算，用于模拟生物界去劣存优的自然选择现象。它从旧种群中选择出适应性强的某些染色体，放入匹配集（缓冲区）
8、，为染色体交换和变异运算产生新种群做准备。适应度越高的染色体被选择的可能性越大，其遗传基因在下一代群体中的分布就越广，其子孙在下一代出现的数量就越多。有多种选择方法，使用比较普遍的一种是适应度比例法，简述如下：适应度比例法又称为轮转法，它把种群中所有染色体适应度的总和看作一个轮子的圆周，而每个染色体按其适应度在总和中所占的比例占据轮子的一个扇区。每次染色体的选择可看作轮子的一次随机转动，它转到哪个扇区停下来，那个扇区对应的染色体就被选中。其实就是将适应度值视为其权值，权值大的被选中的概率也大。尽管这种选择方法是随机的，但它与各染色体适应度成比例。某一染色体被选中的概率（选择概率）为Y问题的初始
9、（侯选）解种群满足预定指标编码为染色体（向量）种群 P（t）计算各染色体适应度通过遗传运算存优去劣种群 P（t+1 ）复制交换变异种群 P（t）种群P（t+1）解码染色体问题解答空间N图 1 遗传算法工作原理示意图IOI2002 集训队论文 遗传算法的特点及其应用 张宁第 4 页 共 20 页)(/)(iccxffP式中 xi为种群中第 i个染色体对应的数字串，f(x i)是第 i个染色体的适应度值， 是种群中所有染色体的适应度值之和。)(if用适应度比例法进行选择时，首先计算每个染色体的适应度，然后按比例于各染色体适应度的概率进入交换（匹配）集的染色体，其具体步骤如下：（1） 计算每个染色体
10、的适应度值 f(xi)；（2） 累加所有染色体的适应度值，得最终累加值 SUM= ，记录)(ixf对应于每个染色体的中间累加值 g(xi)；（3） 产生一个随机数 N，0。其中，S 是一个正整数的集合x1，x 2，x n，t 是一个正整数。子集和问题要求判定是否存在 S的一个子集 S，使得 。我们已知道该问题是一个 NP-完全问题。在实际应用中，Sii我们常遇到的是最优化子集和问题。在这种情况下，我们要找出 S的一个子集S，使得其和不超过 t，但又尽可能接近于 t。例如，我们有一辆载重车，其载重量不能超过 t公斤。有 n个不同的箱子要用载重车来装运，其中第 i个箱子重 xi公斤。我们希望在不超
11、过载重限制的前提下将载重车尽可能地装满。这个问题实质上就是一个最优化形式的子集和问题。下面用遗传算法来解决：若集合 S中元素的个数为 n，每个元素只有两种可能：属于 S或不属于S。因此我们可以用 n为二进制数来表示每个染色体。每一位，若为 0则说明这个元素不属于 S，若为 1则说明这个元素属于 S。IOI2002 集训队论文 遗传算法的特点及其应用 张宁第 9 页 共 20 页确定了问题的描述方式，我们只需随机取出染色体组成初始群体。接着，便可以按前所述，进行选择、交换以及变异运算。我们将染色体所表示的子集的元素和与所给 t的差异记为适应度。即令染色体 x的每一位为 xi，所表示元素的值为 S
12、i则tSfi0)(但是经过实践后发现由于适应度相对差异较小，使得适应度非常接近，难以区分优秀的染色体，使得遗传进化变得非常缓慢，且 f(x)可能为负值，因此还需对适应度函数做一下变换，才可以适合本题的要求。令|f(k)|为当前群体中所有染色体适应度的最大值f(x)=|f(k)-f(x)|所以适应度为 f(x)。选择时可以用前面所介绍的适应度比例法，但采用随机方式，可能会出现随机错误，使得优秀的染色体没有子孙。因此，在这里我们对选择方法作一下改进，采用确定性选择法，使得选择不依靠随机的好坏，先计算群体中每个串的生存概率 ，1jn，然后计算期望复制数 ei=Ps*n，式中：n 为jisfP/群体中
13、染色体的数目。根据 ei值的整数部分给每个染色体串分配一个复制数，而按 ei的小数部分对群体中的染色体串排序，最后按排列的大小顺序选择要保留到下一代的染色体串（子孙） 。接着可以进行交换运算，交换运算与前述相同，不过若进行单点交换有可能使得两个染色体在交换时产生的差异过大，使得遗传变得不稳定，优秀的染色体不能遗传到下一代。因此可以采用多点交换，不过本题中只需进行两点交换即可，其实两点交换与单点交换是类似的。设有两个父辈染色体 A和 B：A：10100100101110B：01001110110001设两个交换点选择如下：A：10100|10010|1110B：01001|11011|0001则两点交换运算就是交换染色体 A和染色体 B，两个交换点之间的部分，则交换结果如下：A：10100110111110B：01001100100001交换运算完成后，可进行变异运算，变异运算时，只需注意变异概率的取值，至于具体算法如前面所述。在本题中的一些数值不妨取值如下：种群长度（染色体个数）：20选择概率：0.9变异概率：0.1结束条件：当前最优解在 100代遗传后仍未改变，或已取到最优解2.例 6：GA 在 TSP（旅行商）问题求解中的应用设存在 N个城市， Dij表示城 i与城 j之间的距离， Dij=Dji，现在要求一
