本科毕业设计说明书（论文）
第 2 页 共 32 页
然和人工自适应系统的研究。70年代De Jong基于遗传算法的思想在计算机上进行了大量纯数值函数优化计算实验。在一系列研究工作的基础上80年代Goldberg进行总结归纳，形成了遗传算的基本框架。
进入八十年代，遗传算法迎来了兴盛发展时期，无论是理论研究还是应用研究都成了十分热门的课题。1985年，在美国召开了第一届遗传算法国际会议
（International Conference on Genetic Algorithms ，ICGA），并且成立国际遗传算法学会（International Society of Genetic Algorithms ，ISGA），以后每两年举行一次。
1989年，Holland的学生D.E.Goldberg出版了专著《搜索、优化和机器学习中的遗传算法》（Genetic Algorithms in Search , Optimization, and Machine Learning）。该书总结了遗传算法研究的主要成果，对遗传算法及其应用作了全面而系统的论述。同年，美国斯坦福大学的Koza基于自然选择原则创造性地提出了用层次化的计算机程序来表达问题的遗传程序设计( genetic programming, GP)方法，成功地解决了许多问题。
在欧洲，从1990年开始每隔一年举办一次Parallel Problem Solving from Nature 学术会议，其中遗传算法是会议主要内容之一。此外，以遗传算法的理论基础为中心的学术会议还有Foundations of Genetic Algorithms，该会也是从1990年开始隔年召开一次。这些国际会议论文，集中反映了遗传算法近些年来的最新发展和动向。
1991年，L.Davis编辑出版了《遗传算法手册》（Handbook of Genetic lgorithms），其中包括了遗传算法在工程技术和社会生活中的大量应用实例。
1992年，Koza发表了他的专著《遗传程序设计:基于自然选择法则的计算机程序设计》。1994年，他又出版了《遗传程序设计，第二册:可重用程序的自动发现》深化了遗传程序设计的研究，使程序设计自动化展现了新局面。有关遗传算法的学术论文也不断在《Artificial Intelligence》、《Machine Learning》、《Information science》、《Parallel Computing》、《Genetic Programming and Evoluable Machines》、《IEEE Transactions on Neural Networks》、《IEEE Transactions on Signal Processing》等杂志上发表。1993年，MIT出版社创刊了新杂志《Evolutionary Computation》。1997年，IEEE又创刊了《Transactions on Evolutionary Computation》。《Advanced Computational Intelligence》杂志即将发刊，由模糊集合创始人L.A.Zadeh教授为
本科毕业设计说明书（论文）
究人员已经或正在置身于有关遗传算法的研究或应用之中。
第 3 页 共 32 页
名誉主编。目前，关于遗传算法研究的热潮仍在持续，越来越多的从事不同领域的研
遗传算法(Genetic Algorithm, GA)是近三十年来迅速发展起来的一种全新的随机搜索与优化算法,其基本思想是基于Darwin的进化论和Mendel的遗传学说。该算法由密执安大学教授Holland及其学生于1975年创建。此后，遗传算法的研究引起了国内外学者的关注。自1985年以来.国际上已召开了多次遗传算法的学术会议和研讨会.国际遗传算法学会组织召开的ICGA( International Conference on Genetic Algorithms)会议和FOGA( Workshop on Foundation of Genetic Algorithms)会议。为研究和应用遗传算法提供了国际交流的机会。
作为一种通用的问题求解方法，遗传算法采用简单的编码技术来表示各种复杂的结构并通过对一组编码表示进行简单的遗传操作和优胜劣汰的自然选择来指导学习和确定搜索的方向。
近年来，遗传程序设计运用遗传算法的思想自动生成计算机程序解决了许多问题，如预测、分类、符号回归和图像处理等，作为一种新技术，它已经与遗传算法并驾齐驱。 1996年，举行了第1次遗传程序设计国际会议，该领域己引起越来越多的相关学者们的兴趣。现在的基因表达式算法应该算是遗传算法的继承者。
1.3 本文研究的内容
本文通过对遗传算法的研究来解决TSP问题。在运用遗传算法成功解决TSP问题基础上，再通过采用不同的初始种群数目、遗传代数、交叉率、变异率来比较算法的质量与效率。从而观察、验证这类参数对算法质量和效率的影响程度。
1.4 本文结构
第一章引言,首先对本文的研究背景、遗传算法在国内外的发展情况进行了简单的描述。然后再对本文研究的大致内容进行了阐述。
第二章：遗传算法与TSP问题的介绍,首先对遗传算法和TSP问题进行了简单的介绍。然后对遗传算法的基本术语、个体的编码方式、初始化种群、适应度函数、选择算子、交叉算子、变异算子、运行参数和全局最优收敛以及TSP问题的数学模型进行了阐述。
第三章：遗传算法在TSP上的应用与实现,首先通过选取10个城市的TSP问题为例，运用遗传算法求解该TSP问题。然后通过选取不同参数进行结果对比，从而验证
本科毕业设计说明书（论文）
遗传算法的各参数对算法质量和效率的影响程度。
第 4 页 共 32 页
第四章：混合遗传算法的展望,简单介绍了一些近年来与遗传算法想结合的高效算法。如模拟退火遗传算法、免疫遗传算法、小生境遗传算法、模糊遗传算法、混沌遗传算法、量子遗传算法。
第五章：结论,对第三章的计算结果进行了总结与归纳。验证了种群大小、遗传代数、交叉率、变异率等参数对算法质量和效率的影响程度。
本科毕业设计说明书（论文）
2 遗传算法与TSP问题介绍
2.1 遗传算法介绍
2.1.1 遗传算法简介
第 5 页 共 32 页
遗传算法是一种借鉴生物界自然选择和自然遗传机制的随机化搜索算法，由美国Holland 教授提出。与自然界相似，遗传算法对求解问题的本身一无所知，它需要的仅仅是对算法产生的每个染色体进行评价，并基于适应度值来选择染色体，使适应性好的染色体有更多的繁殖机会。在遗传算法中，通过随机方式产生若干个所求问题的数字编码（即染色体），形成初始种群；根据所要解决的问题设定一个适应度函数，并且给每一个个体一个适应度的评价，淘汰适应度低的个体，选择适应度高的个体进行遗传操作，经过遗传操作后形成新一代的种群，对新一代的种群进行下一轮进化。直到产生近似最优解。这就是遗传算法的基本原理。
这种算法是1960年由Holland提出来的,其最初的目的是研究自然系统的自适应行为，并且设计了具有自适应功能的软件系统。
遗传算法的3个主要操作算子是：选择(selection)算子、交叉(crossover)算子和变异(mutation)算子[8]，遗传算法中包含了如下5个基本要素:
(1) 对参数进行编码； (2) 设定初始种群大小； (3) 适应度函数的设计； (4) 遗传操作设计；
(5) 控制参数设定(包括种群大小、最大进化代数、交叉率、变异率等)。 为了读者能够更好的阅读本文，下面介绍一下遗传算法中的一些基本概念[9]： 串：它是个体(Individual)的形式，在算法中为二进制串，并且对应于遗传学中的染色体(Chromosome)。
群体：个体的集合称为群体，“串”是群体的元素。 群体大小：在群体中个体的数目被称为群体的大小。
基因：基因是串中的元素，基因用于表现个体的特征。列入一个串{1,2,3}，其中1，2,3这3个元素都是基因。
基因位置：一个基因在串中的位置被称为基因位置。基因位置从左到右,开始计算。
本科毕业设计说明书（论文）
第 6 页 共 32 页
串结构空间：在串中，基因任意组合所构成的串的集合。基因操作是在结构空间中进行的。串结构空间对应于遗传学中的基因型(Genotype)的集合。
参数空间：这是“串空间”在物理系统中的映射，它对应于遗传学中的表现型(Phenotype)的集合。
适应度：表示某个个体对环境的适应程度。 2.1.2 遗传算法应用中的关键问题
(1) 个体的编码方式：
编码：在遗传算法中如何把一个问题的可行解从其空间中转换到遗传算法所能处理的搜索空间的转换方法称为编码。编码是应用遗传算法时要解决的主要问题，也是设计遗传算法时的一个关键步骤。编码方法除了决定个体染色体的排列形式之外，还决定了个体从搜索空间的基因型变成解决空间的表现型的编码方法，编码方法也影响到了交叉算子、变异算子的运算方法。通常编码方法有二进制编码、格雷码编码、浮点数编码、参数编码等。在TSP问题中常用：访问路径顺序进行编码。
二进制编码：二进制编码是遗传算法中最常用的一种编码方式，它使用的编码符号集是由二进制符号0和1组成的二值符号集{0,1}，它所构成的个体是一个二进制编码符号串。二进制编码符号串长度与问题所要求的精度有关。由于二进制不便于反应所求问题的结构特征，对于一些连续函数的优化问题等，也由于遗传运算的随机特性二使得其局部搜索能力较差，因而人们提出了用格雷码来对个体进行编码。
格雷码：连续两个整数所对应的编码值之间只有一个编码位不相同。格雷码有这样一个特点：任意两个整数的差事这两个整数所对应的海明距离（Hamming distance）。这个特点是遗传算法中使用格雷码进行个体编码的主要原因。
浮点数编码：个体的每个基因值用某一范围内的一个浮点数来表示，个体的编码长度等于其决策变量的个数，个体变量的长度等于其决策变量的真实值，所以也叫真实值编码方法。
参数编码：参数编码方法是对含有多个变量的个体进行编码的方法，包含两种编码方法多参数级联编码方法，多参数交叉编码方法。
以访问路径顺序进行编码是如今解决TSP问题的一种常用的编码方式。在第三章中会重点介绍。
(2) 初始化种群：
选择一个群体，就是选择一个个体的集合。这个初始群体也就是问题假设解得集