IOI2002集训队论文
遗传算法的特点及其应用
张宁
遗传算法的特点及其应用
上海复旦大学附属中学张宁
目录
【关键词】【摘要】【正文】§1遗传算法的基本概念§2简单的遗传算法1．2．3．1．2．1．2．§5结束语【附录】1．2．【参考文献】子集和问题源程序TSP（旅行商）问题源程序选择交换变异计算机公司的经营策略优化问题函数优化问题子集和问题TSP（旅行商）问题
§3简单的遗传算法运算示例
§4遗传算法应用举例
第1页共20页
fIOI2002集训队论文
遗传算法的特点及其应用
张宁
【关键词】遗传算法【摘要】遗传算法是基于达尔文进化论，在计算机上模拟生命进化机制而发展起来的一门新学科。它根据适者生存，优胜劣汰等自然进化规则来进行搜索计算和问题求解。文章的第一部分介绍了遗传算法的基本概念。第二部分介绍了遗传算法的原理以及三种运算：选择、交换、变异。第三部分着重介绍三种运算的具体实现，以及简单实例，主要体现遗传算法的实现过程。第四部分介绍了两个具体问题，都是属于NP完全问题，如何用遗传算法来解决，以及实现时的一些基本问题。文章在介绍遗传算法的原理以及各种运算的同时，还分析了一些应用中出现的基本问题，对于我们的解题实践有一定的指导意义。【正文】
遗传算法作为一门新兴学科，在信息学竞赛中还未普及，但由于遗传算法对许多用传统数学难以解决或明显失效的复杂问题，特别是优化问题，提供了一个行之有效的新途径，且能够较好地解决信息学竞赛中的NP难题，因此值得我们进行深入的讨论。要掌握遗传算法的应用技巧，就要了解它的各方面的特点。首先，让我们来了解一下什么是遗传算法。
遗传
变异
染色体
基因
群体
§1遗传算法的基本概念
遗传算法（Ge
eticAlgorithms，简称GA）是人工智能的重要新分支，是基于达尔文进化论，在计算机上模拟生命进化机制而发展起来的一门新学科。它
第2页共20页
fIOI2002集训队论文
遗传算法的特点及其应用
张宁
根据适者生存，优胜劣汰等自然进化规则来进行搜索计算和问题求解。对许多用传统数学难以解决或明显失效的复杂问题，特别是优化问题，GA提供了一个行之有效的新途径，也为人工智能的研究带来了新的生机。GA由美国JHHolla
d博士1975年提出，当时并没有引起学术界的关注，因而发展比较缓慢。从80年代中期开始，随着人工智能的发展和计算机技术的进步，遗传算法逐步成熟，应用日渐增多，不仅应用于人工智能领域（如机器学习和神经网络），也开r