遗传算法及其在TSP问题中的应用
刘晓如
（巢湖学院 计算机科学与技术系 ，安徽 巢湖 238000）
摘要：本论文对遗传算法的内容进行了综述。给出了遗传算法的基本概念、基本理论，并对其构成要素分别进行了详细介绍，如：染色体的编码方法，初始种群的产生，个体适应度的评价方法，运行参数，并对基本遗传操作中的选择算子，交叉算子，编译算子的概念和具体操作方法进行了说明，以及算法终止条件的判定，如何设计遗传算法的操作步骤。介绍了TSP问题的数学模型，对TSP问题的标准库进行了调研，本论文实现了基于遗传算法的旅行商问题(Traveling Salesman Problem，简称TSP)的求解方法.在应用遗传算法求解旅行商问题时，参数值的不同设定对解的影响，结合旅行商问题具体实例，对参数值的变化对于解的影响进行了观察和分析。最后，本论文通过程序设计验证了遗传算法在解决NP完全问题的领域内具有寻找接近最优解的能力。程序的主要功能规定了TSP问题的输入格式，实现了简单的用户图形界面，由用户决定演化代数，初始种群大小，变异概率，交叉概率，以及为了避免陷入局部最优而运行的次数，从而实现最短路径的选择，另外，利用exe4j工具生成了可执行文件。本系统是利用java程序开发设计。
关键词：遗传算法(GA)；货郎担问题(TSP)；NP完全问题(NPC)
Traveling Salesman Problem Using Genetic Algorithms
Liu xiao ru
(Department of Computer Science and Technology, ChaoHu College, ChaoHu AnHui, 238000)
Abstract: This paper has carried on the summary to the simple genetic algorithms. It expounds the genetic algorithms, includes the basic concept, the basic theory, GA integrant part in detail separately. For example, chromosome code method, initial population, individual fitness function, runtime parameters etc. The introduction of some basic genetic operation, for example selection operator, crossover operator, mutation operator can be found in this paper, as well as how to determine algorithm terminating conditions, and how to design genetic algorithms to solve problems. The mathematic model of TSP has also been introduced in this paper. I also collect some useful information from TSP standard library. I implemented the genetic algorithms to solve TSP problem. Since the performance of GA is dependent on the parameter set, the parameter should be chosen very carefully. I observed the influence of different parameter set on the result. At last, it proved that GA has the ability of solving NP complete problems by designing GA program. The main function of GA procedure includes: proposed the format of TSP input files, a simple user graphics interface is provided used for choosing parameters, generation number, selection probability, mutation probability, the number of run time used for avoiding partial optimization. Otherwise, I made an executable file with exe4j tool. This system was developed under java environment.
Keywords: genetic algorithms (GA); traveling Salesman Problem (TSP);
NP complete Problem (NPC)
目录
前言 .................................................................................................................................................. 1 第一章 引言 .................................................................................................................................... 2 1.1、项目开发的背景 ..................................................................................................................... 2 1.2、项目开发的目标 ..................................................................................................................... 2 1.3、项目开发的意义 ..................................................................................................................... 2 1.4、项目所用工具简介 ................................................................................................................. 2 第二章 遗传算法概述 .................................................................................................................... 3 2.1、遗传算法的发展简介 ............................................................................................................. 3 2.2、遗传算法的特点 ..................................................................................................................... 4 2.3、遗传算法的研究内容： ......................................................................................................... 5 2.4、遗传算法的发展 ..................................................................................................................... 5 2.5、遗传算法的应用 .................................................................................................................... 6 第三章 简单遗传算法 .................................................................................................................... 8 3.1、什么是简单遗传算法 ............................................................................................................. 8 3.2、遗传算法的基本概念 ............................................................................................................. 8 3.3、遗传算法的组成要素 ............................................................................................................. 9 3.4、遗传算法的基本步骤: ......................................................................................................... 13 3.5、编程实现的简单遗传算法的流程图 .................................................................................... 14 3.6、遗传算法的进化过程 ........................................................................................................... 15 第四章 TSP问题 .......................................................................................................................... 17 4.1、TSP (Traveling Salesman Problem)的发展历史 ................................................................... 17 4.2、TSP问题的数学模型............................................................................................................ 17 4.3、TSP问题的数学分类: .......................................................................................................... 18 4.3、TSP问题的应用和价值: ...................................................................................................... 18 4.4、TSP问题的计算复杂性: ...................................................................................................... 19 4.5、TSP问题的研究现状............................................................................................................ 20 第五章 利用遗传算法求解TSP问题 .......................................................................................... 21 5.1、针对TSP问题的遗传算法设计： ....................................................................................... 21 5.2、程序设计具体细节： ........................................................................................................... 24 5.3、界面设计： ........................................................................................................................... 24 5.4、程序的总体架构设计 ........................................................................................................... 24 5.5、程序的进一步处理 ............................................................................................................... 25 5.6、结果分析 ............................................................................................................................... 29 5.7、开发环境简介： ................................................................................................................... 29 5.8、待解决问题 ........................................................................................................................... 29 第六章 总结与展望 ...................................................................................................................... 30 6.1、系统总结 ............................................................................................................................... 30 6.2、前景展望 ............................................................................................................................... 30 致谢 ................................................................................................................................................ 31 参考文献 ........................................................................................................................................ 32
巢湖学院计算机系2009届毕业设计（论文）
前言
遗传算法是模拟自然界生物进化过程的计算模型，它的思想源于生物遗传学和适者生存的自然规律，是具有“生存+检测”的迭代过程的搜索算法。Holland的GA常被称为简单遗传算法(SGA)，又称基本遗传算法，操作对象是一群二进制串（称为染色体，个体）即种群（population）。这里的每个染色体对应于问题的一个解。从初始种群出发，采用基于是适应度比例的选择策略在当前种群中选择个体，使用交叉和变异操作来产生下一代种群。如此一代代进化下去，直到满足期望的终止条件[1]。其中，选择，交叉和变异构成了遗传算法的基本操作；染色体编码，种群初始化，适应度函数的设计，遗传操作设计，控制参数这5个要素组成了遗传算法的核心内容。
TSP问题是数学领域的著名问题之一。假设有一个旅行商要周游n个城市，他必须选择所要走的路径，路径的限制是每个城市只能拜访一次，而且最后要回到原来出发的城市，路径的选择目标是要求的路径为所有路径之中的最小值。TSP问题是一个组合优化问题，已经被证明具有NPC复杂性，最优解的搜索空间非常庞大，运用常规方法和现有的计算工具而言，存在着很大的计算困难。应用遗传算法来解决TSP问题，可以在较短时间内得到问题的近似最优解，本论文实现了利用遗传算法解决TSP问题。
论文的主要内容如下：
文献综述：介绍遗传算法的理论，影响遗传算法稳定性和收敛性的重要因素。对算法的理论基础进行了综述，包括遗传算法的基本内容以及将遗传算法应用于求解问题时各个算子的实现方法。并介绍了TSP问题一些知识。
系统开发：说明系统开发的硬，软件环境和开发工具，并介绍了所用软件的相关内容，应用程序的组成以及各模块的功能。
1
巢湖学院计算机系2009届毕业设计（论文）
第一章 引言
1.1、项目开发的背景
遗传算法是基于Darwin的进化论和Mendel的遗传学说，在计算机上模拟生命进化机制而发展起来的一门新学科。遗传算法作为一种实用、高效、鲁棒性(robustness)强的优化技术，发展极为迅速，在各种不同领域(如机器学习、模式识别、神经网络、控制系统优化及社会科学等)中得到广泛应用。在数学领域有一类组合优化问题，如TSP问题，由于问题解的空间十分庞大，传统的搜索算法都存在着诸多的计算困难。然而遗传算法的特点决定其天生具有强大的搜索能力，可以解决计算复杂度的难题。 1.2、项目开发的目标
本项目计划利用遗传算法来解决组合优化问题——TSP，利用程序设计语言实现遗传算法，并提供简单的用户界面，与用于进行交互。 1.3、项目开发的意义
(1) 通过遗传算法的设计，可以了解一些怎样利用其他领域的知识，解决计算机领域的问题，体会学科交叉的重要性。
(2)可以锻炼我的java程序设计能力，基本的界面程序设计能力 1.4、项目所用工具简介 1.4.1、 Eclipse 3.2
Eclipse[2]是一个开放源代码的、基于 Java 的可扩展开发平台。就其本身而言，它只是一个框架和一组服务，用于通过插件组件构建开发环境。幸运的是，Eclipse 附带了一个标准的插件集，包括 Java 开发工具（Java Development Tools，JDT）。利用Eclipse可以方便的进行java程序设计[3]。 1.4.2 、Eclipse Visual Editor
利用 Eclipse Visual Editor项目构建 GUI，Visual Editor 项目的目标是构建一个用于构建工具（在这里是用于构建图形用户接口的工具）的工具，支持SWT控件,利用Visual Editor可以很方便的进行java界面设计。 1.4.3、Exe4j
Exe4j是一个帮助你集成Java应用程序到Windows操作环境的java可执行文件生成工具，无论这些应用是用于服务器，还是图形用户界面 （GUI）或命令行的应用程序。如果你想在任务管理器中及Windows XP分组的用户友好任务栏里以你的进程名取代java.exe的出现，那么exe4j可以完成这个工作。exe4j帮助你以一种安全的方式启动你的 java应用程序，来显示本地启动画面，检测及发布合适的JRE和JDK，以及进行启动时所发生的错误处理等，以至于更多。
2