毕业论文：遗传算法的特点及其应用

也就是说，交换操作能够创造新的染色体子孙染色体，从而允许测试在搜索空间中的新点。

交换也体现了自然界中信息交换的思想。

请看下例例从匹配集中取出的对染色体为染色体染色体随机产生的点交换位置是，交换染色体，中第位右边的部分和，则得两个下代子孙染色体数字串染色体染色体变异变异运算用来模拟生物在自然界的遗传环境中由于各种偶然因素引起的基因突变，它以很小概率随机地改变遗传基因表示染色体的符号串的位的值。

在染色体以二进制编码的系统中，它随机地将染色体的个基因由变成，或由变成。

若只有选择和交换，而没有变异操作，则无法在初始基因组合以外的空间进行搜索，使进化过程在早期就陷入局部解而终止进化过程，从而使解的质量受到很大限制。

通过变异操作，可确保群体中遗传基因类型的多样性，以使搜索能在尽可能大的空间中进行，避免丢失在搜索中有用的遗传信息而陷入局部解，获得质量较高的优化解答。

简单的遗传算法运算示例让我们从下面两个非常简单的例子来具体了解下简单遗传算法的各种操作。

虽然下面的例子都有更好处理方式，但为了深入了解遗传算法的各种操作，还是从简单的例子入手例计算机公司的经营策略优化问题个计算机公司追求的目标是最高的利润，为达此目标，必须选择适当的经营策略。

种可能的策略是对以下四个问题作出决策每台计算机的价格定为元低价还是元高价与机配套的免费软件是还是是否提供网络技术服务提供保修期为半年或是年下面用遗传算法来解决这个决策优化问题。

把问题的可能解表示为染色体数字串。

因为有四个决策变量，而每个变量只有两种选择，其取值可用或来表示，于是，可用四位的二进制数表示种可能的经营策略，解的搜索空间为，即共有种经营策略可供选择，表表示出了其中计算机公司经理已知的种经营策略初始解答。

表中数字串的第位取表示高价，表示低价第二位取表示，表示配套第三位取表示不支持网络技术服务，表示支持网络技术服务第四位取表示保修期为年，表示表示保修期为半年。

表问题的初始解答序号价格配套软件网络服务保修期染色体数字串高支持年高支持半年低不支持年高不支持半年求各染色体的适应度。

在这个问题中，我们不妨设染色体的适应度就是染色体的二进制数字串的数值，对应经营策略的利润。

表第代种群的适应度序号染色体串适应度适应度总和最坏适应度最好适应度平均适应度选择进入交换集的染色体由表可知，所有染色体串适应度的总和是，串的适应度是，占适应度总和的，也就是串被选中的机会接近两次串被选中的概率分别是。

按前述适应度比例法，选择进入交换集的染色体串及其适应度情况如表所示。

表第代种群选择后的适应度序号染色体串适应度适应度总和最坏适应度最好适应度平均适应度由表可知，选择操作的作用是改进了种群的平均适应度，使其由原来的提高到了，最坏适应度由原来的改进为，性能最差的染色体已从种群中删除。

但是，选择不能创造新的染色体，须进行交换操作。

交换操作设采用单点交换，随机产生的交换点是，从交换集中任取对染色体和，互换它们的第，位，得子孙染色体串和。

由此得到下代种群。

如表所示。

表第代种群的适应度序号染色体串适应度适应度总和最坏适应度最好适应度平均适应度估新代的种群的适应度由表可知，在新代第代种群中，最优染色体适应度由原来提高到了，其对应的二进制串是，表示种优化的经营策略。

平均适应度由原来的提高到，整个种群的适应度从总体上提高了，被优化了。

遗传算法重复地执行每代的运算操作，产生新的代，直到满足些终止标准或条件。

在本例中，假定已知染色体数字串代表的是已知的最好利润，则遗传算法停止运行。

例函数优化问题设有函数∈，∈求其在区间内的最大值。

下面用遗传算法求解这问题。

确定适当的编码，把问题的可能解表示为染色体数字串。

因为有个决策变量，其取值范围为，使用位无符号二进制数组成染色体数字串，即可表达变量，以及问题的解答方案。

选择初始种群。

通过随机的方法产生由个染色体数字串组成的初始种群，见表。

计算适应度值及选择概率。

此问题中染色体的适应度取函数自身。

将每个染色体的计算出来，作为适应度值。

在此基础上计算选择概率，初始化遗传算法适应度选择运算适应度复制数计算适应度适应度作变换计算交换部分差距若差异变大则不交换交换变异运算染色体基因是否满足结束条件交换变异输出主程序说明在子集和问题中，随机构造的数据基本上都能达到最优解，偶尔也会收敛到准最优解。

总体情况非常良好。

例问题源程序输入文件输出文件城市最大值染色体个数遗传概率结束条件无通路邻接矩阵染色体结果城市个数当前最短路径长度输入初始化贪心，构造初始群遗传算法适应度选择变异输出主程序说明由于问题本身就是个问题。

对于随机构造的数据，无从知道最优解，而且由于随机性，最优解与局部最优解的差距不会非常明显，虽然差距不明显，但是可能路线截然不同。

因此，可能会收敛到局部最优解。

而人为构造的数据，最优解有较明显的区别时，般可以收敛到最优解。

参考文献邵军力张景魏长华人工智能基础电子工业出版社傅清祥王晓东算法与数据结构电子工业出版社吴文虎王建德实用算法的分析与程序设计电子工业出版社遗传算法的特点及其应用上海复旦大学附属中学张宁目录关键词摘要正文遗传算法的基本概念简单的遗传算法选择交换变异简单的遗传算法运算示例计算机公司的经营策略优化问题函数优化问题遗传算法应用举例子集和问题旅行商问题结束语附录子集和问题源程序旅行商问题源程序参考文献关键词遗传算法遗传变异染色体基因群体摘要遗传算法是基于达尔文进化论，在计算机上模拟生命进化机制而发展起来的门新学科。

它根据适者生存，优胜劣汰等自然进化规则来进行搜索计算和问题求解。

文章的第部分介绍了遗传算法的基本概念。

第二部分介绍了遗传算法的原理以及三种运算选择交换变异。

第三部分着重介绍三种运算的具体实现，以及简单实例，主要体现遗传算法的实现过程。

第四部分介绍了两个具体问题，都是属于完全问题，如何用遗传算法来解决，以及实现时的些基本问题。

文章在介绍遗传算法的原理以及各种运算的同时，还分析了些应用中出现的基本问题，对于我们的解题实践有定的指导意义。

正文遗传算法作为门新兴学科，在信息学竞赛中还未普及，但由于遗传算法对许多用传统数学难以解决或明显失效的复杂问题，特别是优化问题，提供了个行之有效的新途径，且能够较好地解决信息学竞赛中的难题，因此值得我们进行深入的讨论。

要掌握遗传算法的应用技巧，就要了解它的各方面的特点。

首先，让我们来了解下什么是遗传算法。

遗传算法的基本概念遗传算法，简称是人工智能的重要新分支，是基于达尔文进化论，在计算机上模拟生命进化机制而发展起来的门新学科。

它根据适者生存，优胜劣汰等自然进化规则来进行搜索计算和问题求解。

对许多用传统数学难以解决或明显失效的复杂问题，特别是优化问题，提供了个行之有效的新途径，也为人工智能的研究带来了新的生机。

由美国博士年提出，当时并没有引起学术界的关注，因而发展比较缓慢。

从年代中期开始，随着人工智能的发展和计算机技术的进步，遗传算法逐步成熟，应用日渐增多，不仅应用于人工智能领域如机器学习和神经网络，也开始在工业系统，如控制机械土木电力工程中得到成功应用，显示出了诱人的前景。

与此同时，也得到了国际学术界的普遍肯定。

从年至今国际上已举行了五届遗传算法和进化计算会议，第本进化计算杂志年在创刊，年神经网络汇刊出版了进化规划理论几应用专集，同年将神经网络，模糊系统，进化计算三个国际会议合并为全球计算智能大会，会上发表进化计算方面的论文篇，引起了国际学术界的广泛关注。

目前，已在组合优化问题求解自适应控制程序自动生成机器学习神经网络训练人工生命研究经济组合等领域取得了令人著目的应用成果，也成为当前人工智能及其应用的热门课题。

简单的遗传算法遗传算法，以下简称是基于自然选择，在计算机上模拟生物进化机制的寻优搜索算法。

在自然界的演化过程中，生物体通过遗传传种接代，后代与夫辈非常相像变异后代与夫辈又不完全相像来适应外界环境，代又代地优胜劣汰，发展进化。

则模拟了上述进化现象。

它把搜索空间欲求解问题的解空间映射为遗传空间，即把每个可能的解编码为个向量二进制或十进制数字串，称为个染色体，或个体，向量的每个元素称为基因。

所有染色体组成群体，或集团。

并按预定的目标函数或种评价指标，如商业经营中的利润工程项目中的最小费用最短路径等对每个染色提进行评价，根据其结果给出个适应度的值。

算法开始时先随机地产生些染色体欲求解问题的侯选解，计算其适应度，根据适应度对诸染色体进行选择交换变异等遗传操作，剔除适应度低性能不佳的染色体，留下适应度高性能优良的染色体，从而得到新的群体。

由于新群体的成员是上代群体的优秀者，继承了上代的优良性态，因而在总体上明显优于上代。

就这样反复迭代，向着更优解的方向进化，直至满足种预定的优化指标。

上述的工作过程可用图简要描述。

简单遗传算法的三个基本运算是选择交换变异，下面详细介绍。

选择选择运算又称为繁殖再生，或复制运算，用于模拟生物界去劣存优的自然选择现象。

它从旧种群中选择出适应性强的些染色体，放入匹配集缓冲区，为染色体交换和变异运算产生新种群做准备。

适应度越高的染色体被选择的可能性越大，其遗传基因在下代群体中的分布就越广，其子孙在下代出现的数量就越多。

有多种选择方法，使用比较普遍的种是适应度比例法，简述如下适应度比例法又称为轮转法，它把种群中所有染色体适应度的总和看作个轮子的圆周，而每个染色体按其适应度在总和中所占的比例占据轮子的个扇区。

每次染色体的选择可看作轮子的次随机转动，它转到哪个扇区停下来，那个扇区对应的染色体就被选中。

其实就是将适应度值视为其权值，权值大的被选中的概率也大。

尽管这种选择方法是随机的，但它与各染色体适应度成比例。

染色体被选中的概率选择概率为问题的初始侯选解种群满足预定指标编码为染色体向量种群计算各染色体适应度通过遗传运算存优去劣种群复制交换变异种群种群解码染色体问题解答空间图遗传算法工作原理示意图式中为种群中第个染色体对应的数字串，是第个染色体的适应度值，是种群中所有