遗传算法解决TSP问题 C++、MFC界面编程 - 图文

南 京 理 工 大 学

毕业设计说明书(论文)

作 者: 学院(系): 专 业: 题 目:

杨敏 学 号： 0606230236

计算机科学与技术学院 计算机科学与技术

基于遗传算法的TSP问题求解方法

的研究与实现

朱保平 副教授 指导者：

(姓 名) (专业技术职务)

评阅者：

(姓 名) (专业技术职务)

2010年 5 月

毕业设计说明书（论文）中文摘要

旅行商问题是一个典型的NP完全问题，遗传算法是解决这类问题一个比较理想的算法。遗传算法是近年来迅速发展起来的一种全新的随机搜索与优化方法。它的基本思想来自于Darwin的进化论和Mendel的遗传学。 论文首先对遗传算法和旅行商问题进行了简单的描述。接着用数学的方式描述了TSP问题。然后，阐述了遗传算法在编码表示和遗传算子（包括选择算子、交叉算子、变异算子）等其他方面的应用情况，最后通过对初始种群、交叉率、变异率、遗传代数等参数进行修改、测试、对比、来验证这些参数对算法的求解结果和求解效率的影响。 关键字 遗传算法 旅行商问题 遗传算子 编码

毕业设计说明书（论文）外文摘要

Title Solving Traveling Salesman Problem by Genetic Algorithm Abstract TSP (Traveling Salesman Problem) is a typical NP - complete problem and genetic algorithm (GA) is the perfect method for solving NP - complete problem. Genetic Algorithm (Genetic Algorithm, GA) is a new random search and optimization algorithm ，develop rapidly in recent years, the basic idea of the theory is Darwin and Mendel's genetics. Paper first introduces genetic algorithm and Tsp. Then paper describes the mathematical approach the problem of TSP，and then paper explains that genetic algorithm coding and genetic operators(including selection operator, crossover operator, mutation operator) and other aspects of the application。 Finally, the initial population, crossover rate, mutation rate, genetic algebra modifies the parameters, testing, comparison, To verify these parameters on the algorithm results and efficiency. Keywords genetic algorithm TSP genetic operator coding 本科毕业设计说明书（论文）

目 次

第 I 页 共 I 页

1 引言 .............................................................................................................................. 1 1.1 研究背景 ...................................................................................................................... 1 1.2 国内外发展现状 .......................................................................................................... 1 1.3 本文研究的内容 .......................................................................................................... 3 1.4 本文结构 ...................................................................................................................... 3 2 遗传算法与TSP问题介绍 .......................................................................................... 5 2．1 遗传算法介绍 .............................................................................................................. 5 2.1.1遗传算法简介 ............................................................................................................. 5 2.1.2 遗传算法应用中的关键问题 .................................................................................... 6 2.1.2 遗传算法特点 ............................................................................................................ 8 2.1.3 遗传算法的应用步骤 ................................................................................................ 9 2.1.4 遗传算法的流程图 .................................................................................................. 10 2.2 TSP问题介绍 ........................................................................................................... 10 3 遗传算法在TSP上的应用与实现 .......................................................................... 12 3.1 算法的实现 .............................................................................................................. 12 3.1.1 遗传算法运用在TSP上的流程图 .......................................................................... 12 3.1.2 编码 .......................................................................................................................... 13 3.1.3 初始化种群 .............................................................................................................. 13 3.1.4 适应度函数 .............................................................................................................. 14 3.1.5 选择操作 .................................................................................................................. 14 3.1.6 交叉操作 .................................................................................................................. 17 3.1.7 变异操作 .................................................................................................................. 21 3．2 不同参数下的计算结果对比 .................................................................................. 21 3.2.1 初始种群10和100的对比 .................................................................................... 21 3.2.2 不同交叉率和变异率的对比 .................................................................................. 24 3．3 程序计算过程截图 .................................................................................................. 25 4 混合遗传算法的展望 .............................................................................................. 28 结 论 .................................................................................................................................. 30 致 谢 .................................................................................................................................. 31 参 考 文 献 ........................................................................................................................ 32

本科毕业设计说明书（论文）

1 引言

第 1 页 共 32 页

在过去,人们往往只能够处理一些简单的问题，对于大型复杂系统的优化和自适应仍然无能为力。但是在自然界中，生物在这方面表现出了其优异的能力，他们能够通过优胜劣汰、适者生存的自然进化规则进行生存和繁衍，并且慢慢的产生对其生存环境适应性越来越高的优良物种。遗传算法就是模拟自然进化的一种高效的算法。其基本思想就是模拟自然界进化机制和生物进化论而形成的一种过程搜索最优解得算法。

遗传算法是一门新的学科，各种理论、方法都尚未成熟，有待于进一步地发展和完善，但它却让我们看到了解决许多复杂问题的希望。尽管在遗传算法的研究和应用过程中出现过许多难题，同时也会产生许多不同的算法设计，但是，目前遗传算法的运用过程中已经展现出了其优异的性能和巨大的发展前景。我们相信，随着研究工作的进一步深入和发展，遗传算法一定能够在智能计算领域中起到关键性作用。

巡回旅行商问题(Traveling Salesman Problem, TSP),是一个著名的组合优化问题[1],该类问题具有很强的运用背景。如数控机床上的最优钻孔路线的选取、电路板的焊接、物流的调度问题都属于旅行商问题。因此旅行商问题受到了各方面的关注。目前解决TSP问题的主要方法有启发式搜索法、模拟退火算法、遗传算法、Hopfield神经网络算法、二叉树描述算法。有效解决TSP问题在计算理论和实际应用上都有很高的价值。本文主要介绍了运用遗传算法来解决TSP问题。

1.1 研究背景

如今的科学技术正在步入多学科相互交叉、互相渗透、互相影响的时代、生命科学与工程科学的交叉、渗透和相互促进是其中一个典型的例子，也是近代科学技术发展的一个显著点。遗传算法从此诞生。

TSP问题，也称为巡回旅行商问题，就是为人们所广泛研究的典型的组合优化为题。而且TSP问题由于其典型性已经成为各种启发式的搜索、优化算法(如遗传算法、神经网络优化法、列表寻优法、模拟退火法等[2][3][4])的间接比较标准。遗传算法在此体现出了不俗的表现[5]。

1.2 国内外发展现状

最早美国Ｍichigan(密执安大学) [6] [7]的Holland教授提出，起源于60年代对自

本科毕业设计说明书（论文）

第 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) 初始化种群：

选择一个群体，就是选择一个个体的集合。这个初始群体也就是问题假设解得集

本科毕业设计说明书（论文）

第 7 页 共 32 页

合。在遗传算法求解TSP问题中通常以随机方式产生串或者个体的集合[10]。初始种群个数越多，得到最优解的希望越大，但个数过多会导致每进行一轮的机器时间变长，致使算法效率低下。

(3) 适应度函数：

在研究自然界中生物的遗传和进化现象时，生物学家常常使用适应度这个术语来衡量某个物种对环境的适应率。适应度较高的物种将会得到更多的繁殖的机会；从而导致适应度低的物种被淘汰。度量物种适应度的函数就被称为适应度函数。

在遗传算法中，根据个体的适应值，就可决定在此环境下的生存能力。个体适应度大小决定该个体被遗传到下一代群体中的概率。遗传算法仅仅使用所求问题的目标函数就可以得到下一步的有关搜索信息。目标函数值的使用是通过评价个体适应度来体现的。

由于个体适应度大小决定该个体被遗传到下一代群体中的概率。所以评价个体适应度在遗传算法中也是一个重要的步骤。其一般过称为：1.对个体编码的串，进行解码处理后，可以得到个体的表现型。2.由个体的表现型计算出对应的个体的目标函数值。3.根据最优化问题的类型，由目标函数值按一定的转换规则求出个体的适应度。

(4) 选择算子：

选择算子是遗传算法中的又一个关键步骤。遗传算法通过它来对群体中的个体进行优胜劣汰操作。适应度值高的个体被选中的几率高。适应度低的个体选中的概率低。遗传算法的选择操作就是用来确定如何从父代群体中按某种方式选取一些较优的个体进行杂交、变异操作。

选择操作建立在对个体适应度值进行评价的基础上。选择的目的是为了避免基因缺失、提高收敛率和计算效率。有以下几种常用的选择算子的操作方法：比例选择（轮盘赌选择）、最优保存策略、确定式采样选择、无放回随机选择、排序选择等。

(5) 交叉算子：

在生物的自然进化中，两个同源染色体通过交配而重新组合，形成新的染色体，从而产生新的个体或物种。遗传算法通过模仿这个过程，使用交叉算子来产生新的个体。交叉运算是建立在选择运算之后，两个相互配对的染色体按某种方式交换其部分基因，从而形成新的个体。交叉运算是遗传算法区别与其他算法的重要特征，在遗传算法中充当着重要的作用，是产生新个体的主要方式。交叉算子有：单点交叉算子、双点交叉算子、均匀交叉算子、部分映射交叉算子（PMX）、顺序交叉算子（OX）等。

本科毕业设计说明书（论文）

(6) 变异算子：

第 8 页 共 32 页

在生物的遗传和自然进化中，其细胞的分裂复制环节有可能会因为某些偶然因素的影响而产生一些复制差错，就会导致生物的某些基因发生变异，从而产生新的个体。在遗传算法中，变异操作也是如此。交叉操作是产生新个体的主要方式。它决定了遗传算法的全局搜索能力。而变异操作就是起着辅助作用，它提高了算法的局部搜索能力，避免算法陷入局部最优。两种算子的理想结合，才大大的提高了整个算法可行性。使计算结果大大的接近了全局最优解。

变异算子的2个重要作用：1.改善遗传算法的局部搜索能力。2.维持群体多样性防止早熟现象。

(7)运行参数:

在遗传算法中需要选择的参数主要有个体的编码长度、群体大小、交叉概率、变异概率、遗传代数。

个体编码长度：根据具体问题进行设定。

群体大小：表示群体中所含个体数量。当群体较小的时候，可以提高遗传算法的运算速度，却降低了群体的多样性，从而导致遗传算法早熟现象；而当群体较大的时候，又会增大机器的开销、降低了算法的效率。

交叉率：交叉是产生新个体的主要方式，一般应取较大值，但取值过大会破坏群体的中优秀的个体，对进化反而产生不利影响；取值过小的话，会导致收敛速度过慢所以一般取0.4到0.9。

变异概率:取值较大，虽然能帮助种群产生较多的新的个体，但同时也可能破坏了很多较好的个体，使得遗传算法的性能靠近随机搜索算法的性能；取值过小的话，变异操作产生新个体的能力和抑制早熟的能力就变差。一般取值0.0001到0.1。

(8) 全局最优收敛

当指定的遗传代数循环结束，计算得到的最优个体就是全局最优解，就说明算法全局最优收敛。但如果得到的解并不是全局最优解，同时计算得到的解，已经过早的不发生变化，说明算法陷入了局部最优解。另外当循环结束的时候，最优解还在缓慢的变优，则需要提高遗传代数，从而得到全局最优解。 2.1.2 遗传算法特点

（1）遗传算法从问题解的部分集合开始搜索。传统的优化算法是从单个解，开始搜索。这是遗传算法和传统优化算法的几大区别。传统优化算法从单个个体开始迭

本科毕业设计说明书（论文）

第 9 页 共 32 页

代，很容易陷入局部最优。遗传算法从“串集”开始搜索覆盖面积大，利于全局最优。

（2）遗传算法对优化问题没有太多的要求，只需要知道目标函数的信息即可，容易形成通用的算法。

（3）遗传算法使用的选择、交叉、变异算子都是随机产生的，这样能帮助整个算法来慢慢的接近全局最优解。选择体现了向最优解靠近、交叉体现了最优解的产生、变异体现了全局最优解得覆盖。 2.1.3 遗传算法的应用步骤

第一步：确定决策变量，即确定出个体的表现型和问题的解得空间。

第二步：建立目标函数，即根据问题确定是求最大值还是最小值，然后建立相应数学表达式来确定目标函数。

第三步：确定个体的编码方式。

第四步：确定解码方式，即确定个体基因型到表现型的对应关系的转换方式，在TSP 问题中，用最短距离为目标函数，访问路径为编码方式，所以不需要解码。

第五步：设计遗传算子（即确定选择、交叉、变异等遗传算子的具体操作方法）。 第六步：确定遗传算法的相关运行参数，如：种群大小、遗传代数、交叉率、变异率等。

本科毕业设计说明书（论文）

2.1.4 遗传算法的流程图

变异操作 交叉操作 选择操作 计算适应度值 初始化种群 开始 第 10 页 共 32 页

否

停止条件 是

图2.1 遗传算法流程图

结束 输出适应度最高的个体 2.2 TSP问题介绍

TSP问题，也称为巡回旅行商问题。已知n个城市之间的相互距离，现有一个推销员必须遍访这n个城市，并且每个城市只能访问一次，最后又必须返回出发城市。如何安排他的访问次序，可使其旅行的总长度最短[11]。用图论的术语来说，假设有一个图g=(v,e),其中v是顶点集，e是边集，设d=dij是由顶点i和顶点j之间的距离所组成的距离举证，旅行商问题就是求出一条通过所有顶点且每个顶点只通过一次的具有最短距离的回路。这个问题可分为对称旅行商问题(dij=dji)任意（i,j=1,2,3，?,n)

本科毕业设计说明书（论文）

第 11 页 共 32 页

和非对称旅行商问题(dij?dji)任意i,j=（1,2,3，?,n)。城市v?{v1,v2,v3,...,vn}的一个访问顺序为t(t1,t2,t3...,ti,...,tn),其中ti∈v(i=1,2,3,?,n)，且记t(n?1)?t1，则旅行商问题的数学模型为：min =σd(t(i),t(i+1)) （i=0,?,9）本文讨论的是对称性旅行商问题。

本科毕业设计说明书（论文）

3 遗传算法在TSP上的应用与实现

第 12 页 共 32 页

本文通过遗传算法来解决10个城市的旅行商问题。即一个商人需要经过10个城市去交易，每个城市必须且仅能经过一次。最后回到初始点。然后求出最短路径。

首先，本文运用基本遗传算法解决了TSP问题。然后通过改变各参数的值来观察计算结果，接着对计算结果的进行对比分析，从而验证了各参数对遗传算法的影响。主程序分为两个主模块。分别为初始种群10和100的模块。同时各模块还可以设定遗传代数、交叉率、变异率。以下对初始种群为100的模块进行代码分析。模块10代码类似，固不做分析。然后进行各参数设定后的结果对比。

3.1 算法的实现

3.1.1 遗传算法运用在TSP上的流图程

交叉操作 输出结果 以每次访问总距离的倒数作为评估函数，对每个个体进行评估，初始化代数p=0 不成立 P<=遗传代数 成立 结束 选择操作 P=p=1 以访问路径顺序进行编码 采用随机方式初始化种群 外部输入初始化种群个数、遗传代数、交叉率、变异率

变异操作 图3.1 遗传算法运用在tsp上的流程图 本科毕业设计说明书（论文）

3.1.2 编码

第 13 页 共 32 页

遗传算法设计的第一个重点就是编码。上文已经阐述过编码的各种主要方式。如：二进制表示、浮点编码、格雷码、参数编码等。由于二进制表示不自然且需要额外的修正算子，以保证个体的合法性，在实际运用中很少出现。在TSP问题中，路径表示可能是最自然、最直接的表示方式。它直接采用城市在整个路径中的相对位置来表示。遗传算法中的每个个体，就是一次访问的顺序。如有10个城市：0,1，2,3,4,5,6,7,8,9。商人的一次访问顺序为（4,2,1,0,5,8,3,9,6,7,4）。就用（4,2,1,0,5,8,3,9,6,7）作为种群中的一个个体的编码。表示商人从城市4出发路径为4,2,1,0,5,8,3,9,6,7最后回到城市4。这显然是一种非常自然的编码方式。其主要的缺点在于普通的单点、双点交叉操作后往往会引起非法路径的访问（在整个访问过程中有些城市访问了不止1次）。为了消除这一缺点，本文采用次序交叉方法代替了传统的单点、双点交叉。

本文采用数组a[10]来存放群众中的一个个体的访问顺序。City[100][10]存放种群中100个个体各自的访问顺序。 3.1.3 初始化种群

初始化种群：采用随机方式获得初始化种群。它适合与对问题的解无任何先验知识的情况。代码如下：

void CTestDlg2::chushi(int a[10],int city[100][10]) {

int trsf; int ii,jj;

for ( ii=0;ii<=99;ii++)//随机排列城市

{

for(jj=9;jj>=1;jj--) {

int n = rand()%(jj+1); trsf=a[jj]; a[jj]=a[n]; a[n]=trsf;

city[ii][jj]=a[jj];

本科毕业设计说明书（论文）

}

city[ii][0]=a[0];

第 14 页 共 32 页

} }

3.1.4 适应度函数

为了体现种群中个体的适应能力，引入了对种群中每个个体进行度量的函数，叫做适应度函数。通过它来决定个体的优劣。它体现了自然进化中优胜劣汰的原则。对于优化问题，适应度函数就是目标函数。

TSP问题的目标就是访问路径最短。本文采用路径距离和的倒数作为适应函数。本文用数组存放eval[100]每个个体的总路程。eval1[100]每个个体总路程的倒数，作为适应度函数。

for(i=0;i<=99;i++){eval1[i]=1/(eval[i]);} 3.1.5 选择操作

选择操作也称为复制操作。根据个体适应度函数所度量的优劣程度来决定个体是被淘汰还是遗传。对于求解TSP问题，常用的选择机制有轮盘赌选择、最佳个体保存选择，期望值模型机制，排序模型选择机制等。在遗传算法中，算法“早熟”是一个需要关注的问题。为了避免算法进入局部收敛，保证全局收敛性，就要维持种群个体的多样性，避免有效个体的丢失。Rudolhp C[12]提出采用精英选择策略即保持群体中最好的个体不丢失，以保证算法的收敛性。Konstantin Boukreev[14]采用联赛选择方法和最优个体保存方法相结合的方法。为了保证最好个体不丢失，本文采用轮盘赌算法和最优保存算法的结合。

(1) 轮盘算法：

将个体的适应度值按比例转换为选中的概率。使得适应度值高的个体的被选中的概率也高。令for(i=0;i<=99;i++){gailv[i]=eval1[i]/total;}。在将轮盘分成100个扇区进行100次选择。产生100个0到1之间的随机数。相当于轮盘转动100次，可以获得n次转盘停止时的指针位置，指针停放在某一个扇区。就代表选中了该扇区的个体。所以概率越大面积越大，被选中的几率越大。

(2) 最优保存算法：

在遗传算法的过程中，通过对个体进行交叉、变异等遗传操作不断产生新一代的种群个体，虽然随着不断的进化，会产生越来越多的优秀个体。但是由于遗传操作的

本科毕业设计说明书（论文）

第 15 页 共 32 页

随机性，可能破坏掉当代种群中最优秀的个体。我们希望适应度最好的个体要尽可能的保存到下一代群体中。为了实现这一目标，我们使用最优保存策略辅助轮盘算法来进行选择操作。最优保存的具体过程：首先找出当代个体中的最优个体和最差个体。如果当代个体中的最优个体比总优个体（也就是第一代种群到今的最优个体）的适应度值还要高的时候。则以当代最优个体来替换总最优个体中保存的个体。如果当代个体的最优个体比总最优个体要差，则说明最优个体被破坏，则用总最优个体替换掉当代个体中的最差个体。总最优个体不变。

下面为轮盘算法和最有保存算法代码: 轮盘算法:

int CTestDlg2::select(double gailv[100],int city[100][10])//选择函数 {

int q=0;

double suiji=(double)rand()/RAND_MAX;

while(suiji==0){ suiji=(double)rand()/RAND_MAX;} }

最优保存算法：

mi=int(Min(eval));//存放最优个体序号

for(i=0;i<=9;i++)//存放最优个体 { }

milen=int(eval[mi]);//存放当代最优路劲距离

mi1[i]=(city[mi][i]);

double leiji=0.0;

while((leiji

leiji=leiji+gailv[q]; } q--; return(q);

q++;

本科毕业设计说明书（论文）

ma=int(Max(eval));//存放当代最差个体序号

第 16 页 共 32 页

for(i=0;i<=9;i++)ma1[i]=city[ma][i];//存放最差个体 malen=int(eval[ma]);//存放当代最差路径距离 if(tmilen==0) { } else {

if(milen<=tmilen) { } else {

for(i=0;i<=9;i++)city[ma][i]=( tmi1[i]);//上代最优个体被破

tmilen=milen;//更改总最优路径距离

for(i=0;i<=9;i++)//存储首代最优路径的访问顺序 { }

tmi1[i]=( mi1[i]);

tmilen=milen;//存储首代最优路径距离 for(i=0;i<=9;i++)//存储首代最优路径顺序 { }

tmi1[i]=( mi1[i]);

坏，用上代最优个体替换本代的最差个体.总最优路径不变

}

}

其中的Min（）为求最优路径，Max（）求最差路径 int CTestDlg2::Min(double eval[100]) {

本科毕业设计说明书（论文）

参 考 文 献

第 32 页 共 32 页

[1] Garey MR, Johnson Ds. A guide to the Theory of NP Completeness[J].

Computers and Intractability,1979,3(5):23-26

[2] 高经维,张煦,李峰,赵晖.求解TSP 问题的遗传算法实现[J].计算机时代,2004 ,2:19-21.

[3] 邓娟,陈莘萌.一种基于最大相似性的TSP 问题求解算法[J].计算机工

程,2004,30(17):1-2,11.

[4] 谢胜利,张燕姑,李广. 基于遗传算法的旅行商问题求解[J ].温州师范学院

学报(自然科学版),2002,,23 (3):7-10.

[5] 李华昌,谢淑兰,易忠胜. 遗传算法的原理与应用[J]. 矿冶,北京矿冶研究

总院1005-7854(2005)01-0087–04

[6] Holland J H. Adaptation in Natural and artificial Systems[M]. Ann

Arbor: The University of Michigan Press ,1975. [7] Cong Peisheng, Li Tonghua.Numeric genetic algorithm [J]. Anal , Chem. Acta,1994,293:191-203.

[8] 王辉.用遗传算法求解TSP问题[J].计算机与现代化,2009,7:12-16 [9] 周明,孙树栋.遗传算法原理及应用[M].国防工业出版社.1999. [10] 张文修,梁怡.遗传算法数学基础[M].西安交通大学出版社.2003.

[11] 张辉,赵正德,杨立朝,赵郁亮.TSP问题的算法与应用的研究[J].计算机应

用与软件,2009,26(4):274-276.

[12] 陈国良,等.遗传算法及其应用.北京:人民邮电出版社,1995

[13] 刘勇等.非数值并行算法（二）--遗传算法[M].北京:科学出版社，1995. [14] Sushil J.Louis.Genetic Algorithm for TSP[OL]. http://www.cs. unr .edu/～sushil/ papers/ conference/

[15] 谢胜利,等.求解TSP问题的一种改进的遗传算法[J].计算机工程与应

用,2002(8):58-245

本科毕业设计说明书（论文）

}

int CTestDlg2::Max(double eval[100]) { }

3.1.6 交叉操作

int n; int ii=0; double comp[100];

for(ii=0;ii<=99;ii++){comp[ii]=eval[ii];} int n =0; int ii=0; double comp[100];

for(ii=0;ii<=99;ii++){comp[ii]=eval[ii];}

第 17 页 共 32 页

for(ii=1;ii<=99;ii++){if(comp[0]>comp[ii]){comp[0]=comp[ii];}} for(ii=0;ii<=99;ii++){if(comp[0]==eval[ii]){n=ii;break;}} return n;

for(ii=1;ii<=99;ii++){if(comp[0]

采用访问顺序编码后。如果采用简单的一点杂交或者多点杂交，就会产生非法路径。如：若采用一点杂交，随机杂交处为4：0 1 2 3 4| 5 6 7 8 9； 9 8 7 6 5| 4 3 2 1 0。杂交后的个体为：0 1 2 3 4 4 3 2 1 0；9 8 7 6 5 5 6 7 8 9。导致某些城市访问了不止1次。不符合TSP问题的定义。所以本文采用次序交叉来弥补这一缺陷。

次序交叉(OX,ORDER CROSSOVER):由Davis等人提出OX算法。次序杂交算法首先随机地在上代群体中选择两个杂交点，再交换杂交段，其他位置根据保持上代城市的相对次序来确定。例如：

A1[10]={0,1,2,3,4,5,6,7,8,9} A2[10]={9,8,7,6,5,4,3,2,1,0}随机杂交点为3和5。首先交换杂交段。

B1[10]={#,#,#|6,5,4|#,#,#,#}

本科毕业设计说明书（论文）

B2[10]={#,#,#|3,4,5|#,#,#,#}

第 18 页 共 32 页

从B1的第二个杂交点开始6-7-8-9-0-1-2-3-4-5，去除杂交段中的6,5,4。变成7-8-9-0-1-2-3。一次顺序从第二个杂交点开始填入得:

B1[10]={1,2,3,6,5,4,7,8,9,0} 同理得:B2[10]={8,7,6,3,4,5,2,1,0,9} 本文采用上述交叉算法，代码如下：

个体p;

double ww=0;

ww=(double)rand()/RAND_MAX; o=select(gailv,city); p=select(gailv,city); while(o==p) {

p=select(gailv,city);//由于2次选择了同一个个体重新选择一个

}

for(i=0;i<=9;i++){A1[i]=city[o][i];} for(i=0;i<=9;i++){A2[i]=city[p][i];} if(ww<=pcross)//条件成立则，发生交叉 { int p1 =-1; int p2 =-1; while(p1==p2) { p1=rand()%(9)+1; p2=rand()%(9)+1;

} if(p1>p2) { temp1=p1;

p1=p2;

本科毕业设计说明书（论文）

} else { }

int xy=0; }

for(i=p1; i<=p2;i++) { }

convert(p1,p2,A1,B1); convert(p1,p2,A2,B2); int xy=0;

B1[i] = A2[i]; B2[i] = A1[i]; p2=temp1;

第 19 页 共 32 页

for( xy=0;xy<=9;xy++){city1[k][xy]=B1[xy];} for( xy=0;xy<=9;xy++){city1[k+1][xy]=B2[xy];}

for( xy=0;xy<=9;xy++){city1[k][xy]=A1[xy];} for( xy=0;xy<=9;xy++){city1[k+1][xy]=A2[xy];}

其中的convert(p1,p2,A1,B1)函数打代码如下：

void CTestDlg2::convert(int pos1,int pos2,int *so,int *dest) {

int temp[10];

int ii = 0; int jj = 0; int kk = 0;

for(ii=0; ii<10; ii++) { }

temp[ii] = so[(ii+pos2+1)];

本科毕业设计说明书（论文）

}

for(kk=0; kk<(10-(pos2-pos1)-1); kk++) { }

dest[(kk+pos2+1)] = temp[kk]; for(ii=0; ii<10; ii++) { } jj = 0; ii = 0; while(jj<10) { }

if(temp[jj] != 100) { } jj++;

temp[ii] = temp[jj]; ii++;

for(jj=pos1; jj<=pos2; jj++) { }

if(temp[ii] == dest[jj]) { }

temp[ii] = 100; break;

第 20 页 共 32 页

本科毕业设计说明书（论文）

3.1.7 变异操作

第 21 页 共 32 页

在遗传算法中，变异操作并不是最主要的。遗传算法强调的是杂交功能。变异操作是改善遗传算法的局部搜索能力和维持群体的多样性防止早熟现象。针对TSP问题，陈国良等介绍了四种主要的变异技术：（1）点位变异，变异仅以某一很小的概率对串的某些位值变异；（2）逆转变异，在串中随机选择两点，再将这两点内的内容按反序插入到原来的位置中。（3）对换操作，随机选择两个交换点，使交换点处的码值交换。这种变异操作在TSP问题中常被采用.(4) 插入变异，从串中随机选择1个码，将此码插入随机选择的插入点之后。

本文采用对换变异操作，代码如下： void CTestDlg2::bianyi(int bianyi[10]) { int trasfs;

for(kk=1;kk<=2;kk++) {

ii=rand(); jj=rand();

while(ii==jj){ jj=rand();} trasfs=bianyi[jj]; int ii=0; int jj=0; int kk=0;

bianyi[jj]=bianyi[ii]; }

bianyi[ii]=trasfs;

此外，对于变异操作还有一些变体形式，如Sushil Jouis提出的贪心对换变异、谢胜利[15]等提出倒位变异算子。

3.2 不同参数下的计算结果对比

3.2.1 初始种群10和100的对比

理论上，在遗传算法中初始种群的个数决定了种群个体的多样性。初始种群过少会导致程序陷入局部最优，而无法得到近似最优解。增加种群个数可以避免进入局部

本科毕业设计说明书（论文）

的结果对比。

第 22 页 共 32 页

最优，但是种群过大会减慢程序的运算速度，导致算法效率的低下。下面是2个模块

本文采用网络上已有的城市距离矩阵来验证所写程序的正确性: int length[10][10]=

{

0, 23, 93, 18, 40, 34, 13, 75, 50, 35,

23, 0, 75, 4, 72, 74, 36, 57, 36, 22, 93, 75, 0, 64, 21, 73, 51, 25, 74, 89, 18, 4, 64, 0, 55, 52, 8, 10, 67, 1, 40, 72, 21, 55, 0, 43, 64, 6, 99, 74, 34, 74, 73, 52, 43, 0, 43, 66, 52, 39, 13, 36, 51, 8, 64, 43, 0, 16, 57, 94, 75, 57, 25, 10, 6, 66, 16 , 0, 23, 11, 50, 36, 74, 67, 99, 52, 57 ,23, 0, 42, 35, 22, 89, 1, 74, 39, 94 ,11 ,42, 0,

};

其最优距离已被求解为226

下表为交叉率Pc=0.9，变异率 Pm=0.01,初始种群分别为10,100，最大遗传代数分别为100,200的实验结果对比：

表3.1 不同初始种群的算法结果对比表

次数 遗传代数 初始种群大 小 100 最优解代数 1 10 100 2 10 100 3 10 100 4 10 40 11 60 24 71 94 27 最优解路径 最优解 6318247950 246 7810639542 232 4278931065 238 6058139742 229 2781395604 245 7819360542 226 6247931850 229 200 最优解代数 100 131 193 50 74 30 102 最优解路径 最优解 9310654278 238 5063918724 226 8193605427 226 3918724506 226 2601395874 233 0542781936 226 5427601398 240 本科毕业设计说明书（论文）

100 5 10 100 6 10 100 7 10 100 8 10 100 9 10 100 10 10 100 11 10 100 12 10 100 13 10 100 14 10 100 15 10 100 91 55 54 14 35 43 80 90 30 40 30 50 18 25 62 80 25 18 34 30 100 50 87 1936054278 226 6319587240 247 4506391872 226 7936018542 233 4260581397 229 4793185062 229 4278913605 235 3105897426 252 3954278106 232 4581930672 247 0593187426 228 0639187245 226 6059318742 228 3972458106 233 5813906724 229 6058139742 229 4781395062 228 8593106247 233 9360542781 226 2450631987 235 7245063198 235 247601395 249 124 94 161 95 57 100 78 193 75 129 78 171 77 123 140 119 50 50 67 150 100 100 100 第 23 页 共 32 页 5063918724 226 6013958742 233 9360542781 226 6013958742 233 2450639187 226 4793185062 229 9360187245 232 2450639187 226 9360542781 226 7931850624 229 8724593601 232 0624781395 228 1872450639 226 4260593187 228 5063918724 226 2458931067 240 5813974260 229 3958742601 233 7813950624 228 7931850624 229 8106395427 232 2479318506 229 3918724506 226 5936018724 232 初始种群为10，遗传代数为100的平均最优解为:

(246+238+245+229+247+233+229+252+247+226+233+229+233+235+249)/15=238.1 初始种群为10，遗传代数为200的平均最优解为:

(238+226+233+240+233+233+229+226+229+228+228+240+233+229+229)/10=231.6 初始种群为100，遗传代数为100的平均最优解:

(232+229+226+226+226+229+235+232+228+228+229+228+226+235+232)/10=229.4 初始种群为100，遗传代数为200的平均最优解:

本科毕业设计说明书（论文）

第 24 页 共 32 页

(226+226+226+226+226+226+232+226+232+226+226+229+228+232+226)/10=227.5

以上结果非常显然的表示出了当初始种群个数增加后，获得的平均解更接近全局最优解。但增加初始种群的同时增加的算法的循环次数，从而降低了算法的效率。10个城市的TSP问题初始种群应取50-200为宜。

在上述结果中，选取初始种群为10，遗传代数为100的个体（除去获得全局最优解的个体）。然后计算获得最优解的代数的平均值：

(40+60+71+27+55+14+43+90+40+25+80+18+30+50)/14=45.9

计算结果表现出了：算法在没有获得全局最优解的前提下过早的确定了解。原因：初始种群个数过少。导致陷入局部最优解。理论上可以通过改变交叉率和变异率来改善。

3.2.2 不同交叉率和变异率的对比

（1）下面是初始种群为10的模块。相同的交叉率、不同的变异率来观察两组计算的对比结果。

下面列出的运算次数为那些到达遗传代数后，依旧没有找到最优解，但是过早获得局部最优解得次数 。

表3.2 相同交叉率、不同变异率的算法结果对比表

条件 遗传代数 运算次数 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 Pc=0.9 Pm=0.001 300 最优解代数 30 108 147 83 66 270 98 163 144 117 70 55 69 140 88 500 Pc=0.9 Pm=0.1 300 最优解 最优解代数 229 232 229 238 228 232 228 228 232 229 228 228 233 232 228 233 241 181 152 218 196 200 278 258 197 273 264 170 150 154 500 最优解 最优解代数 240 244 235 232 240 232 248 232 238 232 238 232 257 233 240 317 290 365 212 301 350 242 276 295 313 189 348 250 200 290 最优解 249 233 233 228 232 241 233 229 232 232 233 232 232 229 233 最优解 最优解代数 246 229 241 233 238 228 233 240 228 233 228 228 229 228 240 63 76 311 82 37 450 198 256 87 79 200 160 122 99 120 本科毕业设计说明书（论文）

状态1 Pc=0.9 Pm=0.001

初始种群300 平均最优解代数为109.9 初始种群500 平均最优解代数156 状态2 Pc=0.9 Pm=0.1

初始种群 300 平均最优解代数为211 初始种群 500 平均最优解代数为282.5

第 25 页 共 32 页

从上述结果可观察到。在众多计算结果中，未得到全局最优解得计算中，状态1比起状态2来，过早收敛。

状态2往往可以通过增加种群大小来得到最优解。但是状态1则很难通过增加种群个体来突破局部收敛的限制。

（2）接下来分别选择交叉率为0.3和0.9、变异率为0.1、初始种群为10、来作为运行参数。运算结果中当交叉率从0.9变为0.3时，在获取最优解的同时，遗传代数也随之大大增加。

从此可以看出，交叉是产生新个体的主要方式，交叉率过小会导致产生新个体过慢，而导致收敛速度降低。但是也不能取太大。太大可能会破坏群体中的优秀个体。

以上几个对比，进一步证明了以下几个结论：

(1) 初始种群的大小决定了种群的多样性。种群个体过少会导致算法过早收敛，从而陷入局部最优解，难以获得全局最优解。但是种群过大导致了一次遗传操作要进行的循环过多，大大加大了机器开销，算法效率低下。一般的10个点城市，初始种群取50到100为好。

（2）变异率取值过小，就会导致算法容易陷入局部收敛。从而降低了其抑制早熟的能力。但也不能过大，否则会破坏群体中的优秀个体，导致算法效率低下，甚至有时可能找不到最优值。在本算法中变异率因取0.01到0.1为宜。

（3）交叉概率过小会导致产生新个体的速度变慢，而导致收敛速度降低。但也不能过大，过大可能会破坏种群中的优秀个体。本算法中交叉率取0.7到0.9为宜。

3.3 程序计算过程截图

程序主模块：供用户选择初始种群的两种大小：10和100。

本科毕业设计说明书（论文）

第 26 页 共 32 页

图3.2程序主界面图

初始种群为10的模块。遗传代数为200，交叉率为0.9、变异率为0.01的运行图。

图3.2 初始种群为10的算法运行图

初始种群为10的模块。遗传代数为200、交叉率为0.9、变异率为0.01结果图。

图3.3 初始种群为10的算法运行结果图

本科毕业设计说明书（论文）

图。

第 27 页 共 32 页

初始种群为100的模块。遗传代数为200，交叉率为0.9、变异率为0.01的运行

图3.4初始种群为100的算法运行图

初始种群为100的模块。遗传代数为200，交叉率为0.9、变异率为0.01获得最优解得截图。

图3.5 初始种群为100算法运行结果图

本科毕业设计说明书（论文）

4 混合遗传算法的展望

第 28 页 共 32 页

随着遗传算法的发展，为了提高遗传算法的质量和效率，人们把它与其他算法相结合，产生许多混合遗传算法。大大提高了算法质量和效率。更好的解决了许多实际问题。

（1）模拟退火遗传算法：

模拟退火算法的基本思路就是通过模拟高温物体退火过程的方式来找到优化问题的全局最优解。从统计物理学的观点看，随着物体温度的不断降低，物质的能量将不断的接近一个很低的状态，最后达到某种平衡状态。遗传算法的局部搜索能力并不是很好，但是整体的搜索能力比较突出；而模拟退火算法却相反，它具有出色的局部搜索能力，并能防止陷入局部最优解，但它却对整个搜索空间的了解不多，不便于使搜索过程进入最有希望的搜索区域，从而使得模拟退火算法的运算效率不高。但如果将遗传算法和模拟退火算法相结合，互相取长补短，则有可能开发出性能优良的新的全局搜索算法。

（2）免疫遗传算法：

人工免疫算法受生物免疫系统原理的启发，针对求解问题特征进行人工疫苗接种，可充分利用问题本身的信息，和遗传算法结合时，遗传算法的全局搜索能力及免疫算法的局部优化相配合，可大大提高搜索效率。我们可以通过注射疫苗的方法来减少遗传操作的盲目性，加强遗传算法收敛性能，多次的测试结果证明了该改进方法的有效性。

（3）小生境遗传算法：

生物学上，小生境指在特定环境中的一种组织功能，它将每一代个体划分为若干类，每个类中选出若干适应度较大的个体作为一个类的优秀代表，组成一个新种群，再在同一种群中以及不同种群之间进行杂交、变异，产生新一代个体群，同时采用“预选择”机制或排挤机制或共享机制完成选择操作。“解空间”中峰周围的子空间中的个体具有相对独立生长繁衍的特性。常用的小生境遗传算法大多在对群体进行选择操作前，计算个体之间的海明距离，如小于事先设定值，则对“适应值”低的个体处以罚函数，降低其适应值。这样可以保护解的多样性，也可以避免大量重复的解充斥整个解空间。用小生境思想来实现遗传算法的选择操作，使遗传算法的全局寻优能力得到了明显提高。

本科毕业设计说明书（论文）

（4）模糊遗传算法：

第 29 页 共 32 页

模糊遗传算法，即融合模糊优化设计思想的遗传算法，它把模糊优化和遗传算法优化结合起来，构成一种混合优化的设计方法。其目的是利用模糊优化设计的优点，克服一般遗传算法优化设计存在的不足，从而使得系统的优化设计更灵活、方便，取得好的设计效果。首先，在模糊遗传算法中引入“论域”的概念。在这里，“论域”即指用隶属函数来表示遗传算法的优化过程中所采用的约束条件的区间范围。用隶属函数来表示遗传算法的约束条件，以使约束条件能够更容易得到表达，又能够保证遗传子代的选择中能够拥有更广泛的群体组成。其次，在模糊遗传算法中，采用权变理论中的以变应变的思想。模糊遗传算法运用模糊控制的思想来自适应改变遗传算法的种群规模、交叉概率、变异概率、适应度函数以及控制策略等。

（5）混沌遗传算法：

混沌是自然界广泛存在的一种非线性现象，它充分体现了系统的复杂性。混沌运动具有类似随机变量的杂乱表现，具有随机性；“混沌”能在一定范围内按其自身特性不重复地历经所有状态，具有遍历性；初值条件极其微弱的变化会引起混沌系统行为的巨大变化，具有对初始条件的极度敏感性。混沌运动的上述性质作为避免陷入局部极小的优化搜索机制，恰好可以弥补遗传算法易陷入局部最优、收敛速度慢的缺陷。可以利用混沌的遍历性产生初始种群，也可以运用混沌的遍历性对优良个体进行变异操作，混沌遗传算法增强了遗传算法的全局寻优能力。

（6）量子遗传算法：

量子遗传算法是量子计算思想与遗传算法结合的产物。与遗传算法类似，它也是一个产生—检验的过程，但其实现同标准遗传算法不一样。在表达方式上，量子遗传算法将量子的态矢量表述引入染色体编码；在演化机制上，它利用量子门实现染色体演化。这些区别，使得量子遗传算法表现出比标准遗传算法更好的种群多样性、更强的全局搜索能力和更快的收敛速度。还有其他的算法已被引入到遗传算法中来（如禁忌—并行 ，分层），在此，就不再过多介绍。遗传算法与其他算法和理论的结合已经成为改进遗传算法的一个非常有效的手段。

随着人们对遗传算法研究的不断深入，可以预见，会有更多更好的理论和方法被引入到遗传算法中来。相信通过遗传算法与其他算法的结合以及自身实现方式的不断改进，在不久的未来，遗传算法的质量和效率都会有一个飞的提高。

本科毕业设计说明书（论文）

第 30 页 共 32 页

结 论

本文通过遗传算法求解TSP问题，成功获得了全局最优解。综上所述，在求解的过程中遗传算法能够收敛到某一稳定的“最优解”。在求解的质量和优化效率上都表现出了比较突出的能力。

针对具体TSP问题，遗传算法的几个关键参数都有它自己的适合值，种群大小、交叉率、变异率、遗传代数都从一定程度上影响着算法的效率和质量。如种群大小影响了种群的多样性，过少会导致算法陷入局部最优，而找不到全局最优解，过多大大的增加算法的计算量，增大机器开销，算法效率低下，针对10个城市的例子，初始种群应选50到200。交叉操作是产生新个体的主要操作，交叉率决定了算法的收敛速度，过大可能会破坏种群中较优的个体，过小怎会降低产生新个体的速度从而导致算法效率低下。本算法中应取0.7到0.9为宜。变异操作时产生新一代种群的辅助操作，它主要用来改善遗传算法的局部搜索能力，维持群体多样性防止局部收敛。取值较大，虽然能帮助群体产生较多的新个体，但同时也可能破坏较好的个体，所以要配合最优保存策略，但是也会增加机器开销。取值过小的话，变异操作产生新个体的能力和抑制局部收敛的能力都会降低，本算法应取0.01到0.1为宜。

在整个编写过程中，我认为一个最大的问题是：很难保证个体的完整结构。从父代到子代的交叉过程中，保留了部分父代的绝对访问顺序，但是它更多地产生了父代巡回路线中所没有的本分新路线，从而致使整个算法的遗传性状不是好很。也许以后会找到更好的交叉和变异规则，帮助遗传算在性状遗传上获得更好的效果。

本科毕业设计说明书（论文）

第 31 页 共 32 页

致 谢

大学四年的学习即将结束，在此首先感谢所有曾经教导过我的老师。 同时本文能成功完成，要感谢我的导师：朱保平老师。在整个毕业设计的过程中给了我巨大的帮助。是在他的帮助下，我的论文才得以良好的完成。在此，再次感谢,所有南京理工大学的老师,感谢他们这四年来给予了我巨大帮助。

本科毕业设计说明书（论文）

参 考 文 献

第 32 页 共 32 页

[1] Garey MR, Johnson Ds. A guide to the Theory of NP Completeness[J].

Computers and Intractability,1979,3(5):23-26

[2] 高经维,张煦,李峰,赵晖.求解TSP 问题的遗传算法实现[J].计算机时代,2004 ,2:19-21.

[3] 邓娟,陈莘萌.一种基于最大相似性的TSP 问题求解算法[J].计算机工

程,2004,30(17):1-2,11.

[4] 谢胜利,张燕姑,李广. 基于遗传算法的旅行商问题求解[J ].温州师范学院

学报(自然科学版),2002,,23 (3):7-10.

[5] 李华昌,谢淑兰,易忠胜. 遗传算法的原理与应用[J]. 矿冶,北京矿冶研究

总院1005-7854(2005)01-0087–04

[6] Holland J H. Adaptation in Natural and artificial Systems[M]. Ann

Arbor: The University of Michigan Press ,1975. [7] Cong Peisheng, Li Tonghua.Numeric genetic algorithm [J]. Anal , Chem. Acta,1994,293:191-203.

[8] 王辉.用遗传算法求解TSP问题[J].计算机与现代化,2009,7:12-16 [9] 周明,孙树栋.遗传算法原理及应用[M].国防工业出版社.1999. [10] 张文修,梁怡.遗传算法数学基础[M].西安交通大学出版社.2003.

[11] 张辉,赵正德,杨立朝,赵郁亮.TSP问题的算法与应用的研究[J].计算机应

用与软件,2009,26(4):274-276.

[12] 陈国良,等.遗传算法及其应用.北京:人民邮电出版社,1995

[13] 刘勇等.非数值并行算法（二）--遗传算法[M].北京:科学出版社，1995. [14] Sushil J.Louis.Genetic Algorithm for TSP[OL]. http://www.cs. unr .edu/～sushil/ papers/ conference/

[15] 谢胜利,等.求解TSP问题的一种改进的遗传算法[J].计算机工程与应

用,2002(8):58-245

本文来源：https://www.bwwdw.com/article/bn5v.html