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

IOI2002集训队论文遗传算法的特点及其应用张宁第1页共20页遗传算法的特点及其应用上海复旦大学附属中学张宁目录【关键词】【摘要】【正文】§1遗传算法的基本概念§2简单的遗传算法1．选择2．交换3．变异§3简单的遗传算法运算示例1．计算机公司的经营策略优化问题2．函数优化问题§4遗传算法应用举例1．子集和问题2．TSP（旅行商）问题§5结束语【附录】1．子集和问题源程序2．TSP（旅行商）问题源程序【参考文献】IOI2002集训队论文遗传算法的特点及其应用张宁第2页共20页【关键词】遗传算法遗传变异染色体基因群体【摘要】遗传算法是基于达尔文进化论，在计算机上模拟生命进化机制而发展起来的一门新学科。它根据适者生存，优胜劣汰等自然进化规则来进行搜索计算和问题求解。文章的第一部分介绍了遗传算法的基本概念。第二部分介绍了遗传算法的原理以及三种运算：选择、交换、变异。第三部分着重介绍三种运算的具体实现，以及简单实例，主要体现遗传算法的实现过程。第四部分介绍了两个具体问题，都是属于NP-完全问题，如何用遗传算法来解决，以及实现时的一些基本问题。文章在介绍遗传算法的原理以及各种运算的同时，还分析了一些应用中出现的基本问题，对于我们的解题实践有一定的指导意义。【正文】遗传算法作为一门新兴学科，在信息学竞赛中还未普及，但由于遗传算法对许多用传统数学难以解决或明显失效的复杂问题，特别是优化问题，提供了一个行之有效的新途径，且能够较好地解决信息学竞赛中的NP难题，因此值得我们进行深入的讨论。要掌握遗传算法的应用技巧，就要了解它的各方面的特点。首先，让我们来了解一下什么是遗传算法。§1遗传算法的基本概念遗传算法（GeneticAlgorithms，简称GA）是人工智能的重要新分支，是基于达尔文进化论，在计算机上模拟生命进化机制而发展起来的一门新学科。它IOI2002集训队论文遗传算法的特点及其应用张宁第3页共20页根据适者生存，优胜劣汰等自然进化规则来进行搜索计算和问题求解。对许多用传统数学难以解决或明显失效的复杂问题，特别是优化问题，GA提供了一个行之有效的新途径，也为人工智能的研究带来了新的生机。GA由美国J.H.Holland博士1975年提出，当时并没有引起学术界的关注，因而发展比较缓慢。从80年代中期开始，随着人工智能的发展和计算机技术的进步，遗传算法逐步成熟，应用日渐增多，不仅应用于人工智能领域（如机器学习和神经网络），也开始在工业系统，如控制、机械、土木、电力工程中得到成功应用，显示出了诱人的前景。与此同时，GA也得到了国际学术界的普遍肯定。从1985年至今国际上已举行了五届遗传算法和进化计算会议，第一本《进化计算》杂志1993年在MIT创刊，1994年IEEE神经网络汇刊出版了进化规划理论几应用专集，同年IEEE将神经网络，模糊系统，进化计算三个国际会议合并为’94IEEE全球计算智能大会（WCCI），会上发表进化计算方面的论文255篇，引起了国际学术界的广泛关注。目前，GA已在组合优化问题求解、自适应控制、程序自动生成、机器学习、神经网络训练、人工生命研究、经济组合等领域取得了令人著目的应用成果，GA也成为当前人工智能及其应用的热门课题。§2简单的遗传算法遗传算法（GeneticAlgorithms，以下简称GA）是基于自然选择，在计算机上模拟生物进化机制的寻优搜索算法。在自然界的演化过程中，生物体通过遗传（传种接代，后代与夫辈非常相像）、变异（后代与夫辈又不完全相像）来适应外界环境，一代又一代地优胜劣汰，发展进化。GA则模拟了上述进化现象。它把搜索空间（欲求解问题的解空间）映射为遗传空间，即把每一个可能的解编码为一个向量（二进制或十进制数字串），称为一个染色体（chromosome，或个体），向量的每一个元素称为基因(genes)。所有染色体组成群体（population，或集团）。并按预定的目标函数（或某种评价指标，如商业经营中的利润、工程项目中的最小费用、最短路径等）对每个染色提进行评价，根据其结果给出一个适应度的值。算法开始时先随机地产生一些染色体（欲求解问题的侯选解），计算其适应度，根据适应度对诸染色体进行选择、交换、变异等遗传操作，剔除适应度低（性能不佳）的染色体，留下适应度高（性能优良）的染色体，从而得到新的群体。由于新群体的成员是上一代群体的优秀者，继承了上一代的优良性态，因而在总体上明显优于上一代。GA就这样反复迭代，向着更优解的方向进化，直至满足某种预定的优化指标。上述GA的工作过程可用图1简要描述。IOI2002集训队论文遗传算法的特点及其应用张宁第4页共20页简单遗传算法的三个基本运算是选择、交换、变异，下面详细介绍。1．选择选择运算又称为繁殖、再生，或复制运算，用于模拟生物界去劣存优的自然选择现象。它从旧种群中选择出适应性强的某些染色体，放入匹配集（缓冲区），为染色体交换和变异运算产生新种群做准备。适应度越高的染色体被选择的可能性越大，其遗传基因在下一代群体中的分布就越广，其子孙在下一代出现的数量就越多。有多种选择方法，使用比较普遍的一种是适应度比例法，简述如下：适应度比例法又称为轮转法，它把种群中所有染色体适应度的总和看作一个轮子的圆周，而每个染色体按其适应度在总和中所占的比例占据轮子的一个扇区。每次染色体的选择可看作轮子的一次随机转动，它转到哪个扇区停下来，那个扇区对应的染色体就被选中。其实就是将适应度值视为其权值，权值大的被选中的概率也大。尽管这种选择方法是随机的，但它与各染色体适应度成比例。某一染色体被选中的概率（选择概率）为Y问题的初始（侯选）解种群满足预定指标编码为染色体（向量）种群P（t）计算各染色体适应度通过遗传运算存优去劣种群P（t+1）复制交换变异种群P（t）种群P（t+1）解码染色体问题解答空间N图1遗传算法工作原理示意图IOI2002集训队论文遗传算法的特点及其应用张宁第5页共20页)(/)(iccxfxfP式中xi为种群中第i个染色体对应的数字串，f(xi)是第i个染色体的适应度值，)(ixf是种群中所有染色体的适应度值之和。用适应度比例法进行选择时，首先计算每个染色体的适应度，然后按比例于各染色体适应度的概率进入交换（匹配）集的染色体，其具体步骤如下：（1）计算每个染色体的适应度值f(xi)；（2）累加所有染色体的适应度值，得最终累加值SUM=)(ixf，记录对应于每个染色体的中间累加值g(xi)；（3）产生一个随机数N，0NSUM；（4）选择其对应的中间累加值满足g(xi-1)N=g(xi)的染色体进入交换集。（5）重复（3），（4），直到交换集中包含足够多的染色体数字串为止。重复上述过程，直到交换集中包含足够多的染色体为止。显然，此法要求染色体的适应度应为正值。请看下例：[例1]：某种群包含10个染色体，按适应度比例法选择进入交换集的过程示于表1及表2。表1染色体编号12345678910适应度8231661211737选择概率0.110.030.040.210.080.160.150.090.040.09适应度累加值8101329354758656875表2随机数23497014283757所选染色体号47104467由表1,表2可以看到，3号染色体的选择概率最高，被选中的次数最多，其他选择概率较低的染色体被选中的次数就少。当然，用适应度比例法进行选择时，性能最坏的染色体也可能被选择，但概率极小，当种群长度较大时，这种情况可以忽略不计。2．交换复制操作虽然能够从旧种群中选择出优秀者，但不能创造新的染色体，因此，遗传算法的开创者提出了交换操作。它模拟生物进化过程中的繁殖现象，优良品种，即：在匹配集中任选两个染色体（称为双亲的染色体）；随机选择一点或多点交换点位置J（0JL，L是染色体数字串的长度）；交换双亲染色体交换点右边的部分，即可得到两个新的（下一代）染色体数字串。也就是说，交换操作能够创造新的染色体（子孙染色体），从而允许测试在搜索空间中的新点。交换也体现了自然界中信息交换的思想。请看下例：[例2]：从匹配集中取出的一对染色体为：染色体A0111|1010染色体B0101|0010IOI2002集训队论文遗传算法的特点及其应用张宁第6页共20页随机产生的一点交换位置是4，交换染色体A，B中第4位右边的部分——1010和0010，则得两个下一代（子孙）染色体数字串：染色体A’01111010染色体B’010100103．变异变异运算用来模拟生物在自然界的遗传环境中由于各种偶然因素引起的基因突变，它以很小概率随机地改变遗传基因（表示染色体的符号串的某一位）的值。在染色体以二进制编码的系统中，它随机地将染色体的某一个基因由1变成0，或由0变成1。若只有选择和交换，而没有变异操作，则无法在初始基因组合以外的空间进行搜索，使进化过程在早期就陷入局部解而终止进化过程，从而使解的质量受到很大限制。通过变异操作，可确保群体中遗传基因类型的多样性，以使搜索能在尽可能大的空间中进行，避免丢失在搜索中有用的遗传信息而陷入局部解，获得质量较高的优化解答。§3简单的遗传算法运算示例让我们从下面两个非常简单的例子来具体了解一下简单遗传算法的各种操作。虽然下面的例子都有更好处理方式，但为了深入了解遗传算法的各种操作，还是从简单的例子入手：[例3]：计算机公司的经营策略优化问题一个计算机公司追求的目标是最高的利润，为达此目标，必须选择适当的经营策略。一种可能的策略是对以下四个问题作出决策：·每台PC计算机的价格定为5000元（低价）还是8000元（高价）；·与PC机配套的免费软件是Windows2000还是Linux；·是否提供网络技术服务；·提供保修期为半年或是一年；下面用遗传算法来解决这个决策优化问题。（1）把问题的可能解表示为染色体数字串。因为有四个决策变量，而每个变量只有两种选择，其取值可用0或1来表示，于是，可用四位的二进制数表示一种可能的经营策略，解的搜索空间为24=16，即共有16种经营策略可供选择，表3表示出了其中计算机公司经理已知的4种经营策略（初始解答）。表中数字串的第一位取0表示高价，1表示低价；第二位取0表示Windows2000，1表示配套Linux；第三位取0表示不支持网络技术服务，1表示支持网络技术服务；第四位取0表示保修期为一年，1表示表示保修期为半年。表3问题的初始解答序号价格配套软件网络服务保修期染色体数字串1高Linux支持一年01102高Windows2000支持半年00113低Linux不支持一年11004高Linux不支持半年0101IOI2002集训队论文遗传算法的特点及其应用张宁第7页共20页（2）求各染色体的适应度。在这个问题中，我们不妨设染色体的适应度就是染色体的二进制数字串的数值，对应经营策略的利润。表4第0代种群的适应度序号i染色体串xi适应度f(xi)1011062001133110012401015适应度总和26最坏适应度3最好适应度12平均适应度6.5（3）选择进入交换集的染色体由表4可知，所有染色体串适应度的总和是26，串1100的适应度是12，占适应度总和的6/13，也就是串1100被选中的机会接近两次；串0110，0011，0101被选中的概率分别是3/13，3/26，5/26。按前述适应度比例法，选择进入交换集的染色体串及其适应度情况如表5所示。表5第0代种群选择后的适应度序号i染色体串xi适应度f(xi)10110621100123110012401015适应度总和35最坏适应度5最好适应度12平均适应度8.75由表5可知，选择操作的作用是改进了种群的平均适应度，使其由原来的6.5提高到了8.75，最坏适应度由原来的3改进为5，性能最差的染色体已从种群中删除。但是，选择不能创造新的染色体，须进行交换操作。（4）交换操作设采用单点交换，随机产生的交换点是2，从交换集中任取一对染色体1100和0101，互换它们的第3，4位，得子孙染色体串1101和0100。由此得到下一代种群。如表6所示。表6