1、IOI2002集训队论文 遗传算法的特点及其应用 张宁遗传算法的特点及其应用上海复旦大学附属中学 张宁目录【关键词】【摘要】【正文】1遗传算法的基本概念2简单的遗传算法1 选择2 交换3 变异3简单的遗传算法运算示例1 计算机公司的经营策略优化问题2 函数优化问题4遗传算法应用举例1 子集和问题2 TSP（旅行商）问题5结束语【附录】1 子集和问题源程序2 TSP（旅行商）问题源程序【参考文献】【关键词】遗传算法 遗传 变异 染色体 基因 群体【摘要】遗传算法是基于达尔文进化论，在计算机上模拟生命进化机制而发展起来的一门新学科。它根据适者生存，优胜劣汰等自然进化规则来进行搜索计算和问题求解。文
2、章的第一部分介绍了遗传算法的基本概念。第二部分介绍了遗传算法的原理以及三种运算：选择、交换、变异。第三部分着重介绍三种运算的具体实现，以及简单实例，主要体现遗传算法的实现过程。第四部分介绍了两个具体问题，都是属于NP-完全问题，如何用遗传算法来解决，以及实现时的一些基本问题。文章在介绍遗传算法的原理以及各种运算的同时，还分析了一些应用中出现的基本问题，对于我们的解题实践有一定的指导意义。【正文】遗传算法作为一门新兴学科，在信息学竞赛中还未普及，但由于遗传算法对许多用传统数学难以解决或明显失效的复杂问题，特别是优化问题，提供了一个行之有效的新途径，且能够较好地解决信息学竞赛中的NP难题，因此值得
3、我们进行深入的讨论。要掌握遗传算法的应用技巧，就要了解它的各方面的特点。首先，让我们来了解一下什么是遗传算法。1遗传算法的基本概念遗传算法（Genetic Algorithms，简称GA）是人工智能的重要新分支，是基于达尔文进化论，在计算机上模拟生命进化机制而发展起来的一门新学科。它根据适者生存，优胜劣汰等自然进化规则来进行搜索计算和问题求解。对许多用传统数学难以解决或明显失效的复杂问题，特别是优化问题，GA提供了一个行之有效的新途径，也为人工智能的研究带来了新的生机。GA由美国J. H. Holland博士1975年提出，当时并没有引起学术界的关注，因而发展比较缓慢。从80年代中期开始，随着
4、人工智能的发展和计算机技术的进步，遗传算法逐步成熟，应用日渐增多，不仅应用于人工智能领域（如机器学习和神经网络），也开始在工业系统，如控制、机械、土木、电力工程中得到成功应用，显示出了诱人的前景。与此同时，GA也得到了国际学术界的普遍肯定。从1985年至今国际上已举行了五届遗传算法和进化计算会议，第一本进化计算杂志1993年在MIT创刊，1994年IEEE神经网络汇刊出版了进化规划理论几应用专集，同年IEEE将神经网络，模糊系统，进化计算三个国际会议合并为94IEEE全球计算智能大会（WCCI），会上发表进化计算方面的论文255篇，引起了国际学术界的广泛关注。目前，GA已在组合优化问题求解、自
5、适应控制、程序自动生成、机器学习、神经网络训练、人工生命研究、经济组合等领域取得了令人著目的应用成果，GA也成为当前人工智能及其应用的热门课题。2简单的遗传算法遗传算法（Genetic Algorithms，以下简称GA）是基于自然选择，在计算机上模拟生物进化机制的寻优搜索算法。在自然界的演化过程中，生物体通过遗传（传种接代，后代与夫辈非常相像）、变异（后代与夫辈又不完全相像）来适应外界环境，一代又一代地优胜劣汰，发展进化。GA则模拟了上述进化现象。它把搜索空间（欲求解问题的解空间）映射为遗传空间，即把每一个可能的解编码为一个向量（二进制或十进制数字串），称为一个染色体（chromosome，
6、或个体），向量的每一个元素称为基因(genes)。所有染色体组成群体（population，或集团）。并按预定的目标函数（或某种评价指标，如商业经营中的利润、工程项目中的最小费用、最短路径等）对每个染色提进行评价，根据其结果给出一个适应度的值。算法开始时先随机地产生一些染色体（欲求解问题的侯选解），计算其适应度，根据适应度对诸染色体进行选择、交换、变异等遗传操作，剔除适应度低（性能不佳）的染色体，留下适应度高（性能优良）的染色体，从而得到新的群体。由于新群体的成员是上一代群体的优秀者，继承了上一代的优良性态，因而在总体上明显优于上一代。GA就这样反复迭代，向着更优解的方向进化，直至满足某种预定
7、的优化指标。上述GA的工作过程可用图1简要描述。Y问题的初始（侯选）解种群满足预定指标编码为染色体（向量）种群P（t）计算各染色体适应度通过遗传运算存优去劣种群P（t+1）复制交换变异种群P（t）种群P（t+1）解码染色体问题解答空间N图1 遗传算法工作原理示意图简单遗传算法的三个基本运算是选择、交换、变异，下面详细介绍。1 选择选择运算又称为繁殖、再生，或复制运算，用于模拟生物界去劣存优的自然选择现象。它从旧种群中选择出适应性强的某些染色体，放入匹配集（缓冲区），为染色体交换和变异运算产生新种群做准备。适应度越高的染色体被选择的可能性越大，其遗传基因在下一代群体中的分布就越广，其子孙在下一代
8、出现的数量就越多。有多种选择方法，使用比较普遍的一种是适应度比例法，简述如下：适应度比例法又称为轮转法，它把种群中所有染色体适应度的总和看作一个轮子的圆周，而每个染色体按其适应度在总和中所占的比例占据轮子的一个扇区。每次染色体的选择可看作轮子的一次随机转动，它转到哪个扇区停下来，那个扇区对应的染色体就被选中。其实就是将适应度值视为其权值，权值大的被选中的概率也大。尽管这种选择方法是随机的，但它与各染色体适应度成比例。某一染色体被选中的概率（选择概率）为式中xi为种群中第i个染色体对应的数字串，f(xi)是第i个染色体的适应度值，是种群中所有染色体的适应度值之和。用适应度比例法进行选择时，首先计
9、算每个染色体的适应度，然后按比例于各染色体适应度的概率进入交换（匹配）集的染色体，其具体步骤如下：（1） 计算每个染色体的适应度值f(xi)；（2） 累加所有染色体的适应度值，得最终累加值SUM=，记录对应于每个染色体的中间累加值g(xi)；（3） 产生一个随机数N，0NSUM；（4） 选择其对应的中间累加值满足g(xi-1)N= g(xi)的染色体进入交换集。（5） 重复（3），（4），直到交换集中包含足够多的染色体数字串为止。重复上述过程，直到交换集中包含足够多的染色体为止。显然，此法要求染色体的适应度应为正值。请看下例：例1：某种群包含10个染色体，按适应度比例法选择进入交换集的过程示于
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 交换复制操作虽然能够从旧种群中选择出优秀者，但不能创造新的染色体，因此，遗传算法的开创者提
11、出了交换操作。它模拟生物进化过程中的繁殖现象，优良品种，即：在匹配集中任选两个染色体（称为双亲的染色体）；随机选择一点或多点交换点位置J（0JL，L是染色体数字串的长度）；交换双亲染色体交换点右边的部分，即可得到两个新的（下一代）染色体数字串。也就是说，交换操作能够创造新的染色体（子孙染色体），从而允许测试在搜索空间中的新点。交换也体现了自然界中信息交换的思想。请看下例：例2：从匹配集中取出的一对染色体为：染色体A 0111|1010染色体B 0101|0010随机产生的一点交换位置是4，交换染色体A，B中第4位右边的部分1010和0010，则得两个下一代（子孙）染色体数字串：染色体A 011
12、11010染色体B 010100103 变异变异运算用来模拟生物在自然界的遗传环境中由于各种偶然因素引起的基因突变，它以很小概率随机地改变遗传基因（表示染色体的符号串的某一位）的值。在染色体以二进制编码的系统中，它随机地将染色体的某一个基因由1变成0，或由0变成1。若只有选择和交换，而没有变异操作，则无法在初始基因组合以外的空间进行搜索，使进化过程在早期就陷入局部解而终止进化过程，从而使解的质量受到很大限制。通过变异操作，可确保群体中遗传基因类型的多样性，以使搜索能在尽可能大的空间中进行，避免丢失在搜索中有用的遗传信息而陷入局部解，获得质量较高的优化解答。3简单的遗传算法运算示例让我们从下面两
13、个非常简单的例子来具体了解一下简单遗传算法的各种操作。虽然下面的例子都有更好处理方式，但为了深入了解遗传算法的各种操作，还是从简单的例子入手：例3：计算机公司的经营策略优化问题一个计算机公司追求的目标是最高的利润，为达此目标，必须选择适当的经营策略。一种可能的策略是对以下四个问题作出决策：每台PC计算机的价格定为5000元（低价）还是8000元（高价）；与PC机配套的免费软件是Windows2000还是Linux；是否提供网络技术服务；提供保修期为半年或是一年；下面用遗传算法来解决这个决策优化问题。（1） 把问题的可能解表示为染色体数字串。因为有四个决策变量，而每个变量只有两种选择，其取值可用
14、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不支持半年0101（2）
15、求各染色体的适应度。在这个问题中，我们不妨设染色体的适应度就是染色体的二进制数字串的数值，对应经营策略的利润。表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代种群
16、选择后的适应度序号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 第1代种群的适应度序号i染色体串xi适应度f(xi)1
17、0110621101133110012401004适应度总和35最坏适应度4最好适应度13平均适应度8.75（5） 估新一代的种群的适应度由表6可知，在新一代（第1代）种群中，最优染色体适应度由原来12提高到了13，其对应的二进制串是1101，表示一种优化的经营策略。平均适应度由原来的6.5提高到8.75，整个种群的适应度从总体上提高了，被优化了。遗传算法重复地执行每一代的运算操作，产生新的一代，直到满足某些终止标准或条件。在本例中，假定已知染色体数字串1111代表的是已知的最好利润15%，则遗传算法停止运行。例4：函数优化问题设有函数f(x)=2x2-5x+4（xZ，x0，63），求其在区间
18、内的最大值。下面用遗传算法求解这一问题。（1） 确定适当的编码，把问题的可能解表示为染色体数字串。因为有一个决策变量x，其取值范围为0，63，26=64，使用6位无符号二进制数组成染色体数字串，即可表达变量x，以及问题的解答方案。（2） 选择初始种群。通过随机的方法产生由4个染色体数字串组成的初始种群，见表7。表7 函数优化过程编号染色体X值适应度（目标函数）f(x)=2x2-5x+4选择概率实选染色体编号10110102612260.15121001003624160.2913010101217810.09041011104640060.482和842914平均2107.250.251最大4
19、0060.492（3） 计算适应度值及选择概率。此问题中染色体的适应度取函数自身f(x)=2x2-5x+4。将每个染色体的f(x)计算出来，作为适应度值。在此基础上计算选择概率Ps=。（4） 选择进入交换集的染色体。按适应度比例法，选择进入交换集的染色体串，如表8。可见，染色提1和2都被选择了1次；染色体4被选择了2次；染色体3没有被选择。所选的4个染色体被送到交换集，准备参加交换。（5） 交换染色体。首先对进入交换集的染色体进行随机配对，此例中是染色体1和3配对，染色体2和4配对。接着随机确定交换位置，结果是第1对染色体的交换位置是1，第2对染色体的交换位置是4。经过交换操作后得到的新种群如
20、表8所示。（6） 变异。若此例中变异概率取0.01。由于种群中4个染色体总共只有24位代码，变异的期望值为24*0.01=0.24位，可以忽略不计。表8 函数优化过程复制后交换集种群交换配对交换位置新染色体X值适应度（目标函数）f(x)=2x2-5x+40110103300111014326100100441001103827021011101311101058644210111024101100443656和13126平均3281.5最大6442从表8可以看出，虽然仅进行了一代遗传操作，但种群适应度的平均值及最大值却比初始群有了很大提高，平均值由2107.25变到3281.5，最大值由400
21、6变到6442。这说明随着遗传运算的进行，种群正向着优化的方向发展。4遗传算法应用举例1.例5：GA在子集和问题上的应用子集和问题SUBSET_SUM：给定正整数集合S和一个整数t，判定是否存在S的一个子集使得S中整数的和为t。例如，若S=1，4，16，64，256，1040，1041，1093，1284，1344且t=3754，则子集S=1，16，64，256，1040，1093，1284是一个解。设子集和问题的一个实例为。其中，S是一个正整数的集合x1，x2，xn，t是一个正整数。子集和问题要求判定是否存在S的一个子集S，使得。我们已知道该问题是一个NP-完全问题。在实际应用中，我们常遇到
22、的是最优化子集和问题。在这种情况下，我们要找出S的一个子集S，使得其和不超过t，但又尽可能接近于t。例如，我们有一辆载重车，其载重量不能超过t公斤。有n个不同的箱子要用载重车来装运，其中第i个箱子重xi公斤。我们希望在不超过载重限制的前提下将载重车尽可能地装满。这个问题实质上就是一个最优化形式的子集和问题。下面用遗传算法来解决：若集合S中元素的个数为n，每个元素只有两种可能：属于S或不属于S。因此我们可以用n为二进制数来表示每个染色体。每一位，若为0则说明这个元素不属于S，若为1则说明这个元素属于S。确定了问题的描述方式，我们只需随机取出染色体组成初始群体。接着，便可以按前所述，进行选择、交换
23、以及变异运算。我们将染色体所表示的子集的元素和与所给t的差异记为适应度。即令染色体x的每一位为xi，所表示元素的值为Si则但是经过实践后发现由于适应度相对差异较小，使得适应度非常接近，难以区分优秀的染色体，使得遗传进化变得非常缓慢，且f(x)可能为负值，因此还需对适应度函数做一下变换，才可以适合本题的要求。令|f(k)|为当前群体中所有染色体适应度的最大值f(x)=|f(k)-f(x)|所以适应度为f(x)。选择时可以用前面所介绍的适应度比例法，但采用随机方式，可能会出现随机错误，使得优秀的染色体没有子孙。因此，在这里我们对选择方法作一下改进，采用确定性选择法，使得选择不依靠随机的好坏，先计算
24、群体中每个串的生存概率，1jn，然后计算期望复制数ei=Ps*n，式中：n为群体中染色体的数目。根据ei值的整数部分给每个染色体串分配一个复制数，而按ei的小数部分对群体中的染色体串排序，最后按排列的大小顺序选择要保留到下一代的染色体串（子孙）。接着可以进行交换运算，交换运算与前述相同，不过若进行单点交换有可能使得两个染色体在交换时产生的差异过大，使得遗传变得不稳定，优秀的染色体不能遗传到下一代。因此可以采用多点交换，不过本题中只需进行两点交换即可，其实两点交换与单点交换是类似的。设有两个父辈染色体A和B：A：10100100101110B：01001110110001设两个交换点选择如下：A
25、：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，现在要求一条遍历所有N个城
26、市，且不走重复路的最短路径（最短哈密尔顿圈）。这是一个典型的排列顺序问题，属于NP-完全问题。传统解法诸如：限界剪枝法，或是最小支撑树算法，对此都并不太奏效（或是运算速度上的缺陷，或是解的质量上的缺陷）。下面我们试着用遗传算法来解决这道题目。我们先采用十进制编码，每个染色体由按一定顺序排列的N个城市的序号组成，表示一条可能的旅行路径，其中每个基因表示一个城市。染色体的长度为N，解空间为N!。适应度为一条旅行路径对应的距离，路径越短的染色体适应度越高。例如，取N=10，城市代号为1，2，3，4，5，6，7，8，9，10。则种群中的染色体：2 8 4 10 5 1 7 3 6 9；表示一条旅行路径
27、：284105173692；其总路径长我们可以采用非负变换，把最小化优化目标函数变换为以最大值为目标的适应度函数，可以如下定义：其中cmax为可以取为进化过程中路径长度的最大值，或者为了保证f(x)为正而预先设定为一个与种群无关的常数。下面介绍具体算法：首先我们由城市数目N，可以确定染色体长度为N，染色体的基因代码由城市编码组成。但是，我们仍须确定种群长度、变异概率等参数。这些参数都由人为确定，与算法无关，可暂时不考虑，讨论完算法后，可再行确定具体数值。随机组合成染色体，每个染色体须表示一条哈密尔顿回路，生成初始种群。然后分别计算每一个染色体的适应度，按适应度比例法选择染色体到交换集。不过，我
28、们也可以考虑一下改进后的选择方法。适应度比例法实现简单，缺点是选择过程中最好的染色体可能在下一代产生不了子孙，可能发生随机错误。因此我们可以采用择优选择法，即对于群体中最优秀（适应度最高）的染色体不进行交换和变异运算，而是直接把它们复制到下一代。以免交换和变异运算破坏种群中的优秀解答。这种方法可加快局部搜索速度，但又可能因群体中优秀染色体的急剧增加而导致搜索陷入局部最优解。同时，我们也可以采用确定性选择法，使得选择不依靠随机的好坏，先计算群体中每个串的生存概率，1jn，然后计算期望复制数ei=Ps*n，式中：n为群体中染色体的树木。根据ei值的整数部分给每个染色体串分配一个复制数，而按ei的小
29、数部分对群体中的染色体串排序，最后按排列的大小顺序选择要保留到下一代的染色体串（子孙）。完成选择运算后，可以进行交换运算。但是，此处的交换运算不同于前，须改进原有的交换运算，具体做法如下：因为两个染色体，若进行简单的交换运算，可能会使得染色体所表示路径中会重复经过同一城市，即同一染色体中的两个基因有着相同的城市编号。这就造成了染色体不再表示一条哈密尔顿回路，因此须改进交换运算。我们可以采用部分匹配交换运算（PMX）。它先用随机均匀分布方法在欲交换两父染色体串中各产生两个交换点，把这两点之间的区域定义为匹配区域，再对两个匹配区域中的基因通过对应匹配置换。例如，两父染色体串为：A： 2 8 4 10 * 5 1 7 3 * 6 9B： 5 6 7 1 * 10 2 8 3 * 9 4符号“*”表示交换点。对染色体串A，其匹配区域中有四个元素5，1，7，3，应与染色体串B匹配区域中的四个元素10，2，8，3，逐一匹配，即通过在染色体串A内进行元素间的置换，使得匹配区域内这四个元素换为10，2，8，3。为此，染色体串A
