摘 要

TSP(Traveling Salesman Problem)旅行商问题是一个典型的NP完全问题，遗传算法是解决这类问题一个比较理想的算法。遗传算法是近年来迅速发展起来的一种全新的随机搜索与优化方法。它的基本思想来自于Darwin的进化论和Mendel的遗传学。

论文首先介绍了基本遗传算法的基本原理、特点及其基本实现技术；接着针对TSP 问题，论述了遗传算法在编码表示和遗传算子（包括选择算子、交叉算子变异算子这三种算子）等方面的应用情况，分别指出几种常用的编码方法的优点和缺点，并且结合TSP的运行实例详细分析了基本遗传算法的4个运行参数群体大小、遗传算法的终止进化代数、交叉概率、变异概率，对遗传算法的求解结果和求解效率的影响，经过多次的测试设定出了它们一组比较合理的取值。最后，简单说明了对遗传算法解决TSP问题的前景展望。

关键字： 遗传算法 旅行商问题 遗传算子 编码

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.

The basic theories, characteristics and the basic techniques of GA are first introduced. Then the encoding model and genetic operators (including selection operation, crossover operation and mutation operation) about GA in solving TSP are discussed. The advantages and disadvantages of various encoding method are respectively indicated, and the application of the three basic genetic operators is elaborated. According to the given data, the results and efficiencies are influenced by four parameters in the basic genetic algorithm: the size of population, terminate generation, crosser probability and mutation probability. Adjust the parameters, run and try for better ones. At last, it is pointed out that a better crossover or mutation routine can be found out which retains the structure from the parent chromosomes and still ends up with a legal tour in the child chromosomes, which leads to a better solution than ever before. And the prospect for the future of genetic algorithm in solving TSP is made.

Keywords: genetic algorithm TSP genetic operator coding

目录

引 言 1

第一章 遗传算法介绍 2

1.1遗传算法的产生及发展 2

1.2遗传算法基本原理 3

1.3 遗传算法特点 4

第二章 遗传算法的实现技术 5

2.1 遗传算法应用中的关键问题 5

2.2 遗传算法的应用步骤 7

2.3 遗传算法的流程图 8

第三章 遗传算法在TSP上的应用 10

3.1 TSP问题的建模与描述 10

3.2 算法的实现 10

3.2.1 解决TSP的遗传算法流程图 10

3.2.2编码方法与随机初始群体生成 11

3.2.2城市位置及距离矩阵 11

3.2.3 适应度函数 12

3.2.4 选择操作 12

3.2.5 交叉操作 14

3.2.6 变异操作 16

3.2.7 群体的更新和终止 17

第四章 MATLAB编程测试实例分析 19

4.1 测试环境及工具 19

4.2 测试数据 19

4.3 测试结果 20

4.4 结果分析与优化 24

结 论 27

致 谢 28

参考文献 29

引 言

在当今现代，无论是生活还是工作，我们总会面对各式各样的优化问题，但除了一些简单的情况之外，人们对于大型复杂系统的优化和自适应问题仍然无能为力。然而，自然界中的生物却在这方面表现出了其优异的能力，它们能够以优胜劣汰、适者生存的自然进化规则生存和繁衍，并逐步产生出对其生存环境适应性很高的优良物种。遗传算法就是模拟自然进化的一种高效的算法。其基本思想就是模拟自然界进化机制和生物进化论而形成的一种过程搜索最优解得算法。

遗传算法是新发展起来的一门学科，各种理论、方法尚未成熟，有待于进一步地发展和完善，但它却为我们解决许多复杂问题提供了希望。尽管在遗传算法的研究和应用过程中出现许多难题，同时也会产生许多不同的算法设计观点，然而，目前遗传算法的各种应用实践已经展现出了其优异的性能和巨大的发展潜力，它的发展前景激励着各类专业技术人员把遗传算法的理论和方法运用于自己的工作实践中。我相信，随着研究工作的进一步深入和发展，遗传算法必将在智能计算领域中起到关键作用。

巡回旅行商问题(Traveling Salesman Problem, TSP)，是一个典型的、容易描述但是难以处理的NP完全问题，同时TSP问题也是诸多领域内出现的多种复杂问题的集中概括和简化形式。目前求解TSP问题的主要方法有启发式搜索法、模拟退火算法、遗传算法、Hopfield神经网络算法、二叉树描述算法等。所以，有效解决TSP问题在计算理论上和实际应用上都有很高的价值，遗传算法就其本质来说，主要是解决复杂问题的一种鲁棒性强的启发式随机搜索算法。因此遗传算法在TSP问题求解方面的应用研究，对于构造合适的遗传算法框架、建立有效的遗传操作以及有效地解决TSP问题等有着多方面的重要意义。

本论文主要介绍运用遗传算法对TSP问题进行求解，利用选择、交叉和变异等算子的算法设计，最后在MATLAB软件上进行编程实现。

第一章 遗传算法介绍

1.1遗传算法的产生及发展

最早美国密歇根大学（University of Michigan）的Holland教授提出，起源于60年代对自然和人工自适应系统的研究。70年代De Jong基于遗传算法的思想在计算机上进行了大量纯数值函数优化计算实验。在一系列研究工作的基础上80年代Goldberg进行总结归纳，形成了遗传算的基本框架。