计算机基础知识细讲

遗传算法及其在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

巢湖学院计算机系2009届毕业设计（论文）

第二章 遗传算法概述

2.1、遗传算法的发展简介

遗传算法是基于Darwin的进化论和Mendel的遗传学说，在计算机上模拟生命进化机制而发展起来的一门新学科[4]

Darwin进化论最重要的是适者生存原理，认为每一物种在发展中越来越适应环境。目中的每个个体的基本特征由后代所继承，但后一代又会产生一些异于附带的新变化。在环境变化时，只有那些适应环境的个体特征方能保留下来。Mendel 遗传学说最重要的是基因遗传原理，认为遗传以密码方式存在细胞中，并以基因的形式包含在染色体内。每个基因有特殊的位置并控制某种特殊性质。所以，每个基因产生的个体对环境的某种适应性。基因突变和基因杂交可产生适应环境的后代，经过存优去劣的自然淘汰，适应性高的基因结构得以保存下来。

把计算机科学与进化论结合起来的尝试开始于20世纪50年代末。但当时缺乏一种通用的编码方案，使得人们只能依赖变异而不是依赖交配来产生新的基因结构，故而收效甚微。到了60年代中期，美国Michigan大学的John Holland在Fraser和Bremermann等人的工作基础上提出了位串编码技术。这种编码既适合于变异又适合于交配（杂交，交叉）操作，并强调交配最为主要的遗传操作。随后，Holland将该算法用于自然和人工系统的自适应行文的研究之中，并于1975年出版其开创性的著作Adaptation in Natural and Artificial Systems.后来Holland与他的学生们将该算法加以推广并应用到优化及机器学习等问题之中，并正式定名为遗传算法。GA的通用编码技术及其简单有效的遗传操作作为其广泛的应用和成功奠定了基础。

美国 De.Jong 博士首先将遗传算法应用于函数优化，为这一技术的应用奠定了基础。1980年，Smith教授首次将遗传算法应用于机器学习领域，并研制出一种称作分类器(Classifier)的系统。1989年，Goldberg撰写了《遗传算法在搜索优化和机器学习中的应用》一书，对GA的原理及应用作了比较详细、全面地论述。该书至今仍是遗传算法研究中广泛适用的经典之作。此后，许多学者对原来的遗传算法(或称简单遗传算法)进行了大量改进和发展，提出了许多成功的遗传算法模型，从而使遗传算法应用于更广泛的领域。进入90年代后，遗传算法作为一种实用、高效、鲁棒性(robustness)强的优化技术，发展极为迅速，在各种不同领域(如机器学习、模式识别、神经网络、控制系统优化及社会科学等)中得到广泛应用，引起了许多学者的关注，在最近兴起的人工生命、遗传编程、进化策略、进化计一算等领域中，研究人员将遗传算法于计算机科学相结合，试图模拟自然界的自适应、自组织和再生能力，设计出具有“生命”的人工系统。

3

巢湖学院计算机系2009届毕业设计（论文）

2.2、遗传算法的特点

近几年来，遗传算法主要在复杂优化问题求解和工业工程领域应用，取得了一些令人信服的结果，所以引起了很多人的关注，而且在发展过程中，进化策略、进化规划和遗传算法之间差异越来越小。遗传算法成功的应用包括:作业调度与排序、可靠性设计、车辆路径选择与调度、成组技术、设备布置与分配、交通问题等等。由于遗传算法与传统方法截然不同的思想，使得遗传算法有着自己独有的特点[1]: (1) 智能性

遗传算法的智能性包括自组织，自适应和自学习性等。遗传算法的这种自组织，自适应特征同时也赋予了它根据环境的变化自动发现环境的特征和规律的能力。 (2) 本质并行性

GA的本质并行性表现在两个方面。一方面，GA是内在并行的，它本身非常适合于

大规模并行计算。另外一方面，GA内涵并行性。GA采用种群方式组织搜索，因而它可以同时搜素空间内的多个领域，并相互交流信息。这种搜索方式使得它虽然每次只执行与种群规模N成比例的计算，而实质上进行了大约O(N2)次有效搜索，能以较少的计算获得较大的收益。 (3) 过程性

遗传算法通过自然选择和遗传操作等自组织行为来增强群体的适应性。算法模拟的

是一个过程，算法实施的也是一个过程。在这个过程中，算法本身无法判定个体在解空间的位置，因此需要人为干预才能终止。 (4) 多解性

遗传算法的另一个基本特征是采用群体的方式组织搜索。它从多个点出发，通过这些点内部结构的调整和重组来形成新的点。Inertia每次都将提供多个近似解，对多目标搜索或有需要多个近似解作为参照的情况下是非常有用的。 (5) 不确定性

遗传算法的不确定性伴随其随机性而来的。GA的主要步骤都含有随机因素，从而算法的进化过程中，事件的发生与否带有很大的不确定性。 (6) 非定向性

自然选择和生殖过程这种非定向机制是遗传算法的关键。它没有确定的迭代方程，

也不依靠梯度下降法似的爬山策略，而是调整群体的内部结构的方法来增强对环境的适应度，以使得问题得到解决。 (7)内在学习性

学习是进化过程自身所具有的不可与其分割的行为方式。与自然进化过程类似，生物体为了生存就必须进行学习，通过不断地实践来积累知识和经验，以增强自身的适

4

巢湖学院计算机系2009届毕业设计（论文）

应性，遗传算法的个体学习方式是通过改变个体的基因结构来提高自己的适应度。 (8) 统计性

遗传算法的种群方式决定了它是一个统计过程。在每一进化代，都要进行统计，以确定个体的优劣并推动进化的进行。 (9) 稳健性

由于遗传算法利用个体的适应值推动种群的进化，而不管求解问题本身的结构特征，因而遗传算法在求解不同问题时，只需要设计相应的适应性评价函数，而无需修改算法的其他部分。 (10) 整体优化

传统的优化方法一般采用的梯度下降的爬山策略，从而使得对于多峰函数的情况往往容易陷入局部最优。遗传算法能同时在解空间的多个区域内进行搜索，并且能以较大的概率跳出局部最优，以找出整体最优解。 2.3、遗传算法的研究内容：

遗传算法的研究工作[5]主要集中在以下几个方面: 2.3.1、性能分析

遗传算法的性能分析一直是遗传算法研究领域中最重要的主题之一。在遗传算法中，群体规模、杂交和变异算子的概率等控制参数的选择是非常困难的。遗传算法还存在一个过早收敛问题，也就是说遗传算法的最后结果并不总是达到最优解，怎样阻止过早收敛也是人们感兴趣的问题之一。 2.3.2、并行遗传算法

遗传算法在操作上具有高度的并行性，探索在并行计算机上高效执行遗传算法的策略是研究人员感兴趣的领域之一。对于并行遗传算法的研究表明，只要通过保持多个种群和恰当地保持种群间的相互作用来模拟并行执行过程，即使不使用并行计算机，我们也可以提高算法的执行效率。 2.3.3、分类系统

分类系统属于基于遗传算法的机器学习中的一类，它包括一个简单的基于串规则的并行生成子系统、规则评价子系统和遗传算法子系统。分类系统正在被人们越来越多地应用在科学、工程和经济领域。目前分类系统是遗传算法研究中的一个非常活跃的领域。

2.4、遗传算法的发展

GA在应用方面[5]取得的丰硕成果，使人们对它的发展前景充满信心。最近几 年，有关遗传算法的研究大都集中于GA的改进和应用方面。

(1) 控制参数的选择，原始GA中种群大小、交叉概率、变异概率等控制参数是人

5

巢湖学院计算机系2009届毕业设计（论文）

为事先给出，或者通过实验来调整，而一些改进的GA把这些参数也看作是优化的目标来考虑；

(2) 针对特殊问题来设计交叉和变异这两类最重要的算子，使之适应该问题而获得较好的效果；

(3) 将数理统计中假设检验等方法应用于GA，这为GA设计引入新的思想； (4) 并行GA和分布式GA的研究；

(5) 其他类型生物机制的模仿，如多种群进化、免疫、病毒、寄生等，以丰富GA的内容；

(6) 模糊逻辑、神经网络、模拟退火都是近几年来新兴的技术，而把这些技术和传统的GA融合在一起也必然是未来发展的趋势.相对于GA的改进和应用，而其相关的基础理论研究远落后于算法的发展。虽然近年来有关GA的渐进行为分析受到愈来愈广泛的注意，但到目前为止，还没有一套完整的理论可以准确、全面地阐述GA的收敛性，也没有找到一个恰当的度量与论证方法精确地刻画GA在不同实现下的收敛速度，从而对GA的各种改进做出统一、公正的评判。这种一般数学理论基础的缺乏限制着GA的进一步推广、改进和应用。 2.5、遗传算法的应用

(1) 数值优化

数值优化是GA的经典应用领域，也是GA进行性能评价的常用案例。例如旅行商问题(TSP)是经典的组合优化问题之一，已成为一种衡量算法优劣的标准。它是采用非标准编码GA求解最成功的一例，用推销员顺序经历的城市序号表示基因编码。由于使用标准交叉产生后代可能成为又重复或者丢失基因而成为非可行解，从而提出了非标准的交叉和变异方法。交叉主要采用重排方法——部分匹配重排序(PMC)，顺序交叉（OX），循环交叉(CX)等，变异主要采用位反转，对换和插入等方法。

(2) 自动控制

在自动控制领域中许多与优化相关的问题需要求解，GA的应用日益增加并显示了良好的效果，如基于GA的模糊控制器优化设计，基于GA的参数辨识，利用GA进行神经网络的结构优化设计和权值学习，基于ＧＡ的控制参数在线优化，ＧＡ滑模控制系统设计中的应用等。

(3) 机器学习

基于GA的机器学习，特别是分类器系统，在许多领域中得到了应用。例如，GA被应用于模糊控制规则的学习，基于GA的机器学习可用于调整神经网络的连接权和优化设计神经网络结构，分类器系统在多机器人路径规划中的应用等。

6

巢湖学院计算机系2009届毕业设计（论文）

(4) 经济学

应用遗传算法对经济创新的过程建立模型，可以研究投标的策略，还可以建立市场竞争的模型。

(5) 人工生命

人工生命是用计算机等人工媒体模拟或构造出具有自然生物系统特有行为的人工系统。自组织和自学习是人工生命的两大主要特征。基于ＧＡ的进化模型是研究人工生命现象的重要理论依据。

(6) 图像处理和模式识别

如何使误差最小是使计算机视觉达到实用化的重要要求，GA在图像处理中的优化计算方面是完全胜任的，目前已在图像恢复，图像边缘特征提取，几何形状识别，模糊模式识别等方面得到了应用

(7) 数据搜索与挖掘

用GA可完成Internet上的信息搜索，找出相关的链接，挖掘相关的链接和信息。

7

巢湖学院计算机系2009届毕业设计（论文）

第三章 简单遗传算法

3.1、什么是简单遗传算法

Holland的GA常被称为简单遗传算法(SGA)，操作对象是一群二进制串（称为染色体，个体）即种群（population）。这里的每个染色体对应于问题的一个解。从初始种群出发，采用基于是适应度比例的选择策略在当前种群中选择个体，使用交叉和变异操作来产生下一代种群。如此一代代进化下去，直到满足期望的终止条件。

简单遗传算法用于优化问题时，其最主要特征就是:它不在单点上寻优，而是从整个种群(population)中选择生命力强的个体产生新的种群;它使用随机转换原理而不是确定性规则来工作。遗传算法中常用的遗传操作包括三个基本算子:选择(selection )、交叉(crossover)、变异(mutation)，其中，选择算子用于从旧种群生成新种群，交叉算子用于从父代生成子代，变异算子用于对子代做某种变异，使其跳出局优解。简单遗传算法只使用选择算子、交叉算子和变异算子这三种基本遗传算子，其遗传进化操作过程简单，容易理解，是其它一些遗传算法的雏形和基础。

遗传算法所得结果的好坏，主要依赖于遗传代数和解的规模，在实际应用中只能根据具体要求，在合理的时间内对问题进行求解，若所得解不能令人满意，可增大解组规模或遗传代数，但这是以延长计算时间为代价的。 3.2、遗传算法的基本概念

由于遗传算法的基本思想是基于进化论和遗传学说的，故要用到一些相关的进

化和遗传的概念[5]。其介绍如下：

(1) 串(string)

它是个体 (Individual)的形式，在算法中为二进制串，并且对应于遗传学中的染色体(chromosome).表示待求解问题的一个可能解，由若干基因组成，是GA操作的基本对象。

(2) 种群（population）

个体的集合称为种群，串是种群的组成元素，种群是GA的搜索空间。 (3) 种群大小(population size) 种群中个体的数量称为种群大小。 (4) 基因(Gene)

基因是串中的元素，基因用于表示个体的特征。可以表示为一个二进制位，一个整数或一个字符等。例如有一个串S=1011，则其中的1, 0, 1, 1这4个元素分别称为基因。

8

巢湖学院计算机系2009届毕业设计（论文）

(5) 基因位置(gene position)

一个基因在串中的位置称为基因位置，有时也简称基因位。基因位置从串左向右计算，例如在串S= 1101中，0的基因位置是3。基因位置对应于遗传学中的地点(Locus)。

(6) 适应度(Fitness)

表示某一个体对于环境的适应程度。通常由适应度函数表示。 (8) 选择(selection)

从种群中选择出较适应环境的个体，这些选中的个体用于繁殖下一代，故有时也称这一操作为再生(reproduction)。选择用于繁殖下一代的个体时时根据个体环境的适应度而决定其繁殖量的，故而有时也称为非均匀再生(differential reproduction)。

(8) 交叉(crossover)

在选中用于繁殖下一代的个体中，对两个不同个体的相同位置的基因进行交换，从而产生新的个体。

(9) 变异(mutation)

在选中的个体中，对个体中的某些基因执行异向转化。在串中，如果某位基因为1，产生变异时就把它变成0；反之则由0变成1. 3.3、遗传算法的组成要素

遗传算法主要由六大部分组成：染色体编码设计，初始种群的产生，适应度函数的设计，算法参数的设置，遗传操作，算法终止条件。

(1) 染色体编码设计

GA进化过程是建立在编码机制上的，编码对于算法的性能如搜索能力和种群多样性等的影响很大。常见的编码方式有二进制编码，浮点数编码和混合编码。针对TSP问题，我们采用二进制编码方式，对于某些特殊的问题，编码采用图或树的形式;对于非线性规划问题，我们常用的是浮点数编码。下面就简单介绍一下二进制编码。二进制编码就是采用二进制符号0和1来表现个体的遗传基因型。其优点在于，编码，解码操作简单，交叉，变异等遗传操作便于实现。其缺点在于，不便于反应所求问题的特定知识，对于一些连续函数的优化问题，也由于GA的随机特性而使得其局部搜索能力很差。

(2)初始群体的产生

初始化过程有很多种。在研究遗传算法时，常常随机产生初始群体，这样做的好处是产生方式不依赖于问题，也就是对于任何问题，我们都可以采用这种方式来生成初始群体，因此从随机初始群体出发能更清楚地考察算法的行为和性能。

9

巢湖学院计算机系2009届毕业设计（论文）

(3) 适应度函数

适应度函数是遗传算法与问题的接口，对遗传算法的收敛速度和结果影响很大。根据问题的特点而设计合适的评价函数，能产生适宜于遗传算法处理的状态空间，能使算法快速有效地收敛。评价函数的规范化方法是根据搜索空间中点的原始优劣情况计算其评价函数值。评价函数对遗传算法的性能影响很大:如果过分强调当前的较优个体，就会使较优个体过分繁殖，很快降低群体中的结构的多样性，使算法过早收敛到局部最优值;而如果对当前较优个体强调得不够，算法就很容易丢失当前群体中较优个体的结构信息，不能在合理的时间内收敛到较好的个体。

遗传算法只通过评价函数与问题相联系，既有优点又有缺点。遗传算法通常是使用评价函数的数值来确定遗传选择概率。只依赖数值而不关心评价函数的计算方式，使得遗传算法很稳定，对于不同问题的不同要求，只需设计相应的评价函数，而无需修改遗传算法的其它部分。

基本遗传算法按与个体适应度成正比的概率来决定当前群体中每个个体遗传到下一代种群中的机会多少。为了正确计算这个概率，这里要求所有个体的适应度必须为正数或零。这样，根据不同种类的问题，必须预先确定好由目标函数值到个体适应度之间的转换规则。

(4) 简单遗传算法的参数

① 种群大小M，即种群中个体的数量。群体规模影响遗传优化的最终结果，以及遗传算法的执行效率，当群体规模太小时，遗传算法的优化性能一般不会太好，而采用较大的群体规模可以减少遗传算法陷入局部最优解的机会，但较大规模，意味着计算机复杂度提高。

② 交叉概率Pc，交叉概率Pc控制着交叉操作被使用的频度，较大的交叉概率可增强遗传算法开辟新的搜索区域的能力，但高性能的模式遭破坏的可能性较大;若选用交叉概率太低，遗传算法搜索可能陷入迟钝状态，一般选取概率是从0.25-1.00之间。

③变异概率Pm，变异在遗传算法中属于辅助性搜索操作，其主要目的是维持群体多样性，一般低频度的变异可防止群体中重要的单一的基因可能丢失，高频度变异将使遗传算法趋于纯粹的随机搜索。

④ 遗传算法的终止进化代数T。

运行参数对遗传算法的求解结果和求解效率都有一定的影响，合理的运行参数往往是通过多次试算后确定的

(5) 遗传操作

10

巢湖学院计算机系2009届毕业设计（论文）

遗传操作包括选择、交叉、变异，这三个操作在进化过程中起着非常重要的作用。 ① 选择算子

选择的目的是为了从当前群体中选出优良的个体，使他们有机会作为父代为下一代繁殖子孙。GA通过选择过程体现这一思想，进行选择的原则是适应性强的个体为下一代贡献一个或多个后代的概率大。选择实现了达尔文的适者生存的原则。选择方法一般是比例选择，轮盘赌选择。

采用轮盘赌选择 (roulette wheel selection)是最简单的一种选择方法。表3.1表示了11个个体适应度、选择概率和累积概率。为了选择交配个体，需要进行多轮选择。每一轮产生一个[0, 1]均匀随机数，将该随机数作为选择指针来确定被选个体。如表3.1所示，第一轮随机数为0.81则第六个个体被选中，第二轮随机数为0.32，则第二个个体被选中;依此类推，第3,4,5，6轮随机数为0.96, 0.01, 0.65, 0.42，则第9, 1, 5, 3个个体依次被选。显然适应度高的个体被选中的概率大，而且很有可能被选中，而适应度低的个体则很有可能被淘汰。

个体 适应度 选择概率 累计概率 表3.1 轮盘赌选择法的选择概率计算 1 2 3 4 5 6 7 8 9 2.0 1.8 1.6 1.4 1.2 1.0 0.8 0.6 0.4 0.18 0.16 0.15 0.13 0.11 0.09 0.07 0.06 0.03 0.18 0.38 0.49 0.62 0.73 0.82 0.89 0.95 0.98 10 0.2 0.02 1.00 11 0.1 0.0 1.00 从统计意义讲，适应度大的个体被选中的机会也大。当然，适应度小的个体尽管被选择的概率小，但仍有可能被“破格”复制。这样就增加了个体的多样性，便于执行交叉及变异。所以轮盘赌选择方法既体现“适者生存”原则，又保持个体性态多种多样。

②交叉算子(Crossover)

在遗传算法中，交叉是产生新个体的主要手段，它仿照生物学中杂交的原理，将两个个体(染色体)的部分字符的基因互相交换。执行交换的个体是随机选择的。首先，要确定交叉的概率Pc，大致为0.5-0.8左右。这就是说，大概有50%-80%的个体要执行交叉，然后，采用上述轮盘赌选择的方法，按适应度大小选择被交叉的个体，依次两两进行交叉。交叉点的选择也是随机的，假设字符串长度为L，则在[0,L]区间内产生随机整数，该整数便是交叉点的位置，注意，交叉点不能选在左数第一位字符上，因为其交叉结果仍是原来的两个字符串。因此，长度为L的字符串，可供选择的交叉点为(L-1)个。根据交叉点的数目不同，分一点交叉和两点交叉。前者只选一个交叉点，该点之后的字符全部参加交换;后者选取两个交叉点，只有两点间的字符才参加交换。当字符串长度大时，常采用两点交叉，此外还有多点交叉，即对长字符串实行多段交叉。通过交叉，子代的字符串不同于亲代。正是有了交叉操作，群体的性态才多种多

11

巢湖学院计算机系2009届毕业设计（论文）

样。传统的优化算法，例如动态规划法，个体性态不能增添，只能在原有的个体群体中择优，从而限制了搜索寻优的范围。因此，有人认为假若没有交叉，遗传算法就失去优越性。

遗传算法的有效性主要来自选择和交叉操作，尤其是交叉，在遗传算法中起着核心作用。

这里介绍单点交叉算法。任意挑选经过选择操作后种群中两个个体作为交叉对象，即两个父个体经过染色体交叉重组产生两个子个体，如图3.1所 示。随机产生一个交叉点位置，父个体1和父个体2在交叉点位置之右的部分基因码互换，形成子个体和子个体2。类似地完成其它个体的交叉操作。

③ 变异算子(Mutation)

如果只考虑交叉操作实现进化机制，在多数情况下是不行的，这与生物近亲繁殖影响进化历程是类似的。因为，种群的个体数是有限的，.经过若干代交叉操作，因为源于一个较好祖先的子个体逐渐充斥整个种群的现象，问题会过早收敛，当然，最后获得的个体不能代表问题的最优解。为避免过早收敛，有必要在进化过程中加入具有新遗传基因的个体。解决办法之一是效法自然界生物变异。生物性状的变异实际上是控制该性状的基因码发生了突变，这对于保持生物多样性是非常重要的。模仿生物变异的遗传操作，对于二进制的基因码组成的个体种群，实现基因码的小概率翻转，即达到变异的目的。

变异是遗传算法中产生新个体的另一种方法，它是将某一个体的某一位字符进行补运算，即将0变为1，或将1变为0.如图3.2所示，第四位经过变异操作。

变异个体的选择以及变异位置的确定，都是采用随机的方法产生。首先，确定变异概率Pm, Pm通常较小，约为0.001-0.01，也就是说，1000个字符中有1-10个发生变异。然后，针对每个字符在[0, 1]之间产生三位有效数的均匀分布随机数。针对对应的字符，决定是否将实行变异。

随机确定变异的位置后，执行变异的方法有两种。一种是直接产生变异，另一种

12

巢湖学院计算机系2009届毕业设计（论文）

满足上述约束的解构成了一条Hamilton回路。通常一个组合优化问题的解可能不是唯一的，即可以同时存在着多个满足条件的赋值使得目标函数达到最大(或最小)值，但目标函数所达到的最大(或最小)值总是唯一的[6]。 4.3、TSP问题的数学分类:

4.3.1、从问题对应到图的类型，TSP可以分为两类:

(1) 任意两个城市间的距离都是对称的，它对应的是图论中的无向图； (2) 两个城市间的距离是非对称的，它对应的是图论中的有向图； 4.3.2、从问题本身的限制条件的强弱，主要有三类:

(1) 不做任何限制(但是一般都要求城市间的费用不为负数)，只是给出距离矩阵，求最小回路；

(2) 要求距离间要满足三角不等式;任意两个城市距离满足dij < dik + djk； (3) 定义在欧式平面上的TSP即Euclid TSP，它给出每个点在欧式平面上的坐标，而城市间的距离就是以它们的欧式距离来定义。

4.3.3、从问题的多项式可解性上分，TSP可以分为两类:

(1) 目前己经知道有多项式时间算法可解的，比如其距离矩阵满足特定的条件(Demidenko条件、Kalmanson条件、Supnick条件)等；

(2) 目前尚没有发现多项式时间算法可解的，而研究热点是如何寻找更多的多项式时间可解的情形。 4.3.4、其他

TSP的研究经过几十年的发展，还引申出其它扩展形式:多旅行商问题(Multi-Salesman Problem),多目标旅行商问题(Multi-Objective TSP) [7]。 4.3、TSP问题的应用和价值:

组合优化 (combinational optimization)是遗传算法最基本的也是最重要的研究和应用领域之一。所谓组合优化是指在离散的、有限的数学结构上，寻找一个满足给定约束条件并使其目标函数值达到最大或最小的解。一般来说，组合优化问题通常带有大量的局部极值点，往往是不可微的、不连续的、多维的、有约束条件的、高度非线性的NP完全问题，因此，精确地求解组合优化问题的全局最优解一般是不可能的。遗传算法作为一种新型的、模拟生物进化过程的随机化搜索、优化方法，近十几年来在组合优化领域得到了相当广泛的研究和应用，并已在解决诸多典型组合优化问题中显示了良好的性能和效果。

TSP问题是一个具有广泛的实用背景与重要的理论价值的组合优化难题。许多关于TSP的工作并不是由应用直接推动的，而是因为TSP为其它一般的各类算法提供了思想方法平台，而这些算法广泛地应用于各种离散优化问题。其次，TSP大量的直接应用给研

18

巢湖学院计算机系2009届毕业设计（论文）

究领域带来了生机，并引导了未来的工作。

虽然运输问题是TSP最自然的应用，但由于其模型的简单性，使得TSP在其他领域都有着有趣的应用。一个经典的例子是如何安排机器在一块电路板或其他物体上钻孔，其中需要钻的孔可以看成是各个城市，而旅行的费用就是钻头从一个孔移到下一个孔所花的时间。虽然钻孔的技术不断发展，但无论何时，只要钻机设备的移动时间在所有制造业的过程中占据显著的地位，TSP在减少费用上就扮演了一个非常重要的角色。 4.4、TSP问题的计算复杂性:

在考虑算法的复杂性时，我们往往指的是它的渐进时间复杂性。也就是R，我们关心的是算法随着输入规模的增长，其所需计算步数的增长速度。关于这个问题，计算机科学家们有一个共识:即当输入规模n表示的算法复杂性函数f(n)是以多项式为界的，算法才被认为是有效的。对于组合优化问题，我们关心的一般不是最优解的存在性和唯一性，而是如何找到有效的算法求得一个最优解。有的最优化问题可以有许多方法加以解决，大们需要根据求得最优解的效率对它们进行分类;也有的最优化问题可能根本难以解决，因而不存在有效地寻求最优解的方法。计算复杂性理论就是用于研究算法有效性和问题难度的手段。 4.4.1、复杂性分类:

从本质上讲，所有的计算问题又可以归结为判定问题，如果说:一个算法解决了某一判定问题，则算法输出“是”，否则输出“非”。而从输入到输出，算法所需要运行的步骤即为算法的时间复杂性。

很多优化问题，诸如旅行商问题、最小覆盖问题、多处理器任务调度问题背包问题等都被发现可以多项式约化为NP中最难的问题，即NP完全问题,普遍认为多项式时间的算法是“好的算法” 、“有效的算法”，而所有的NP问题目前都没有找到多项式时间的算法，未得到最优解，它们需要耗费时间复杂性函数的数量级往往是指数级甚至更高，所以单单依靠提高计算机的速度对问题的解决是非常有限的。 4.4.2、TSP问题的时间复杂度

著名的Cook定理告诉我们:可满足性问题是NP完全的。这一定理奠定了NP完全问题的体系基础。随后，许多被证明是NP完全的问题归根到底都是通过证明可满足问题可以在多项式时间内变换到该问题的方法来实现的。到目前为止，所有的NP完全问题还没有多项式时间算法[8]。

首先，TSP问题属于NP是显然的。又因为TSP问题可以间接的规约为可满足问题SAT，所以很显然TSP问题是一个NP完全问题。TSP搜索空间随着城市数n的增大而增大，所有的旅程路线组合数为(n-1)!/2。5个城市的情形对应120/10=12条路线，10个城市的情景对应3628800/20=181440条路线，100个城市的情景对应有4.666E155

19

巢湖学院计算机系2009届毕业设计（论文）

条路线。所以对于输入规模为n个城市的TSP找到最优解的时间复杂性函数的数量级是O (n!)，当n比较大时，耗费的时间已经是个天文数字。表4.1是在假定所用计算机每秒可以执行10亿次运算的前提下，对不同的时间复杂性函数所耗费时间的比较。

表4.1 不同的时间复杂性函数所耗费时间的比较

4.5、TSP问题的研究现状

目前针对TSP的算法主要分为两类:完全算法(精确计算)和不完全算法(近似算法)。

4.5.1、TSP问题的精确计算:

完全算法能保证完全搜索问题的整个解空间，从而找到最有巡回，但需要消耗O(n!)级的运算时间;有些完全算法虽然运用一些精巧的技术来减少搜索空间，但其本质上还是进行全局搜索，并没有降低运算时间复杂度。如线性规划，动态规划，分支限界。 4.5.2、TSP问题的近似计算:

不完全算法不能保证搜索问题的全部解空间，所以也不能保证能够找到最优解，甚至在某些实例上连解都得不到，但它们与完全算法相比却具有运算时间上的优势，即它们的运算时间复杂度都只是多项式，并不会随着输入规模的扩大产生“组合爆炸”;这类算法采用的是启发式策略来指导搜索，普遍比完全算法要快。对TSP不完全算法(近似算法)的研究是本文的重点。由于 精 确 式算法所能求解的问题规模非常有限，实际中使用的往往都是多项式阶的近似算法或启发式算法(heuristics)。几十年来，出现了很多近似优化算法，如近邻法、贪心算法(greedy algorithm)、最近插入法(nearest insertion)、最远插入法(farthest insertion)、双极小生成树法(double minimum spanning tree)等等。近年来，有很多解决该问题的较为有效的算法不断被推出，例如Hopfield神经网络方法、模拟退火方法以及遗传算法方法。

20

巢湖学院计算机系2009届毕业设计（论文）

第五章 利用遗传算法求解TSP问题

TSP问题的搜索空间非常庞大，在这庞大的搜索空间寻求最优解，对于常规方法和现有的计算工具而言，存在着诸多的计算困难。借助遗传算法的搜索能力解决TSP问题，是很自然地想法。由于其全局搜索的特性，遗传算法在解决TSP问题中存在着其他算法没有的优势。接下来，就根据TSP问题，来讨论遗传算法的应用方法。 5.1、针对TSP问题的遗传算法设计： 5.1.1、一个假设

我们用正整数1~n来表示城市，n表示城市的个数。 5.1.2、输入文件的格式：

输入文件存储TSP问题的城市距离矩阵，本例中的TSP问题是的城市之间距离是对称的，文件中存储的是上三角阵，不包括对角线元素。 5.1.3、个体的编码方法：

用遗传算法解决TSP，一个周游方案很自然地表示为n个城市的排列，但基于二进制编码的交叉和变异操作不能适用，所以需要重新设计遗传操作，以适应这类遗传基因表示问题。目前为止针对TSP提出的编码方法主要有:顺序表示(ordinal representation );路径表示(path representation)。路径表示是表示旅程对应的基因编码的最自然、简单和符合逻辑的表示方法。然而，除非初始基因是固定的，否则这种编码方式不具备唯一性。例如:旅程(5-1-7-8-9-4-6-2-3)与(1-7-8-9-4-6-2-3-5)表示的是同一条路径[9]。 5.1.3、初始种群的产生

考虑到初始群体的多样性，在解空间中随机产生初始群体，并使其均匀分布于解空间。考虑到城市的数目大小，一般s取300-500。初始化方法：首先初始化染色体，每个个体的初始化，就是随机产生一个城市序列，将该个体加入种群当中，不应有重复，直到种群规模达到s。 5.1.4、种群进化

种群进化采用代进化的方案，将最优的个体直接传入下一代种群中。然后依照交叉，变异的概率对种群进行交叉，变异操作。在种群进化到新的一代时，要保证种群数目不变，

通常有两种类型的种群进化。一种是代进化(Generational evolution):即每一代中产生新的种群替代目前的种群。因为遗传算法固有的随机性而产生的弱收敛性，一种好的解决方法是将最优秀的个体直接传入下一代种群中。代进化存在的问题是在开始计算被产生的新的染色体的适应度时，整个的新种群必须已经产生。另一种进化是稳定状态的进化(Steady state evolution):将产生的某一染色体直接加入到目前的种

21

巢湖学院计算机系2009届毕业设计（论文）

群中。在稳定状态的进化中被替换掉的染色体是随机选出来的。 5.1.5、适应度函数的设计

在TSP问题中，用所产生的路径长度总和作为适应度函数，来衡量得到的解是否最优。

5.1.6、选择操作

从种群中选择适应度最高的个体，直接放入下一代种群之中即精英策略，对于选择用于交叉和变异的个体，则采用赌轮选择。 5.1.3、交叉操作

1987年Suh和Gucht发现遗传算法的收敛性在利用交叉操作的情况下要远远快于不利用交叉操作的情况。

路径表示(path representation)是表示旅程对应的基因编码的最自然、最简单的表示方法。例如，旅程5-1-7-8-9-4-6-2-3可以直接表示为(517894623)，基于路径表示的编码方法，要求一个个体(即一条旅程)的染色体编码中不允许有重复的基因码，也就是说要满足任一个城市必须而且只能访问一次的约束。这样，基本遗传算法的交叉操作生成的个体一般不能满足这一约束条件，如：9个城市的例子，

个体1：1-2-4-5-6-8-7-9-3 个体2：2-1-4-3-9-6-7-5-8

从第5个位置进行交叉得到的结果如下： 个体1：1-2-4-5-9-6-7-5-8 个体2：2-1-4-3-6-8-7-9-3

个体1，2显然对于TSP问题而言，没有意义。

基于以上原因1985年 ，Grefenstette等针对TSP提出了一种遗传基因编码方法。这种编码的思想是，对于一个给定的个体，即一个周游方案，对于一个城市，计算出它在该城市之后的所有城市中的顺序，把该顺序作为城市的编码，也可以理解为在该城市之后的城市中，小于该城市的城市数目,然后需要加一（城市本身）。为了更好的理解，给出下面的例子：

(1) 我们有9个城市，城市的原来编码为1~9，假设有一个个体（周游方案）为1-2-4-5-6-8-7-9-3则相应的编码过程如表5.1，按照Grefenstette编码则编码后的为1-1-2-2-2-3-2-2-1，得到的城市周游方案为：1-2-4-5-6-8-7-9-3

表5.1 Grefenstette编码过程 当前城市 1 2 4 5 6 当前城市之后的城市 2-4-5-6-8-7-9-3 4-5-6-8-7-9-3 5-6-8-7-9-3 6-8-7-9-3 8-7-9-3 22

排序（Grefenstette编码） 1 1 2 2 2

巢湖学院计算机系2009届毕业设计（论文） 8 7 9 3 7-9-3 9-3 3 null 3 2 2 1 (2) 解码过程，从最后一个码字开始，每当遇到在该码字之前的不大于该码字的码，则将当前码字加一，则可实现解码，如表5.2，

表5.2 Grefenstette解码过程

排序（Grefenstette码逆序） 1 2 2 3 2 2 2 1 1

当前码字之前的码字 1-1-2-2-2-3-2-2 1-1-2-2-2-3-2 1-1-2-2-2-3 1-1-2-2-2 1-1-2-2 1-1-2 1-1 1 null 当前城市 3 9 7 8 6 5 4 2 1 由于采用这种顺序表示技术，可以采用基本遗传算法的交叉操作，例如， 单点交叉的情形，交叉前，父个体1和父个体2分别为: p1: (1 1 2 2 | 2 3 2 2 1) p2: (2 1 2 2 | 5 2 2 1 1) 它们代表旅程分别为: 1-2-4-5-6-8-7-9-3 2-1-4-3-9-6-7-5-8

两个个体在交叉点处进行基因重组，生成子个体1和子个体2，分别为 p1: (1 1 2 2 5 2 2 1 1) p2: (2 1 2 2 2 3 2 2 1) 它们代表旅程分别为: 1-2-4-5-9-6-7-3-8 2-1-4-5-6-8-7-9-3

从上述的单点交叉来看，Grefenstette编码可以有效地解决传统交叉导致的无意义的解带来的问题。 5.1.4、变异操作，

本系统设计使用互换变异，随机选择染色体中的两个位置，并将这两个城市的位置互换对于基于路径表示的TSP问题的遗传算法，在同一染色体的上随机选择两个位置进行翻转和交换其值似乎是最有效的方法。1986年Grefenstette测试到，随机的选择

23

巢湖学院计算机系2009届毕业设计（论文）

两个点并将这两个点中的子路径翻转的变异操作是很有效的。1987年Grefenstette采用了2-opt局部提高操作作为一种变异操作，这种变异操作在作业调度问题中得到了很好的解【19】. 5.2、程序设计具体细节：

5.2.1、编码方式：采用路径表示，结合Grefenstette编码。 5.2.2、种群进化方式：采用代进化。

5.2.3、选择算子：赌轮式选择以及经营策略。

5.2.4、交叉算子：对路径表示进行Grefenstette编码，然后进行传统的单点交叉，然后解码。

5.2.5、变异算子：随机选择两个城市互换位置

5.2.6、适应度函数设计：对每个体，采用染色体长度*MAX-个体路径总和，其中MAX表示城市之间距离允许的最大值。

5.2.7、参数设置：种群大小，交叉概率，变异概率，进化代数都有用户通过界面提供，如图5.1所示。

5.2.8、一点改进：为了防止遗传算法出现局部最优(早熟)，我们独立的调用遗传算法m次，选取其中最优的个体。M由用户通过界面提供。 5.3、界面设计：

利用java很容易进行程序设计，本系统利用Visual editor进行界面程序设计，通过该界面用户可以提交遗传算法的参数，提供输入文件，当遗传算法运行结束时，界面反馈给用户。界面如图5.1

图5.1 用户界面

5.4、程序的总体架构设计

遗传算法程序，界面程序相对独立的设计，界面程序负责与用于交互，并调用遗传算法。遗传算法根据界面程序提供的参数设置，给出TSP问题的最优解，返回界面，然后在反馈到用户[10]。如图5.2所示。

24

巢湖学院计算机系2009届毕业设计（论文）

5.5、程序的进一步处理

程序利用java程序设计，需要运行在java虚拟机上，有很大的不便，我利用java提供的jar命令，将程序打包成jar文件，由于程序运用了SWT技术，这时得到的jar文件并不能直接运行。经过一系列的调研，发现可以利用工具exe4j，该工具是利用jar文件生成.exe文件的一个工具，该工具很容易使用，具体过程如图5.3——5.7所示。程序需要动态链接库文件swt-win32-3236.dll，放在相同目录下，最终生成一个可执行文件，不需要java虚拟机环境。

25

巢湖学院计算机系2009届毕业设计（论文） 系统设计的抽象架构参数SWT界面程序参数遗传算法用户运行结果最优解参数种群大小，进化代数交叉概率，变异概率输入文件路径遗传算法调用次数图5.2 系统的总体架构

26

巢湖学院计算机系2009届毕业设计（论文）

图5.3

图5.4

27

巢湖学院计算机系2009届毕业设计（论文）

图5.5

图5.6

28

巢湖学院计算机系2009届毕业设计（论文）

图5.7

5.6、结果分析

本次实验，能够解决小规模的TSP问题，能够给出最优解。但是随着规模的增大，容易产生局部最优，过早收敛的问题。仍然需要进一步改进。 5.7、开发环境简介：

5.7.1硬件环境：双核CPU 2.53G, 4G内存 5.7.2软件环境：

Windows XP操作系统，开发工具Eclipse 3.2, Eclipse 是一个开放源代码的、基于 Java 的可扩展开发平台。就其本身而言，它只是一个框架和一组服务，用于通过插件组件构建开发环境。Eclipse 附带了一个标准的插件集，包括 Java 开发工具（Java Development Tools，JDT）。 5.8、待解决问题

本系统实现了简单遗传算法，由于简单遗传算法本身的缺点，收敛性问题，容易陷入局部最优，可以根据当前针对遗传算法的最新研究成果，对其进行改进，比如自适应遗传算法，交叉概率，变异概率的选择是影响遗传算法行为和性能的关键所在，直接影响着算法的收敛性。自适应遗传算法能够根据适应度自动调整变异，交叉概率，从能能够得到相对某个解的最佳变异交叉概率。

29

巢湖学院计算机系2009届毕业设计（论文）

第六章 总结与展望

6.1、系统总结

经过了近三个月的毕业设计过程，该系统的功能已经基本得到了实现，并能达到预定目标，可以对输入给出最优解。但是仍然存在着一些不足之处，这是由于简单遗传算法本身的缺陷造成的。通过本次毕业设计过程，使我了解到了理论是需要实验区检验，不能光是纸上谈兵，只有通过不断地实践才能更深的理解理论知识。同时通过这次毕业设计，培养了我独立分析，解决问题的能力，还让我对基本的软件设计有了了解。毕业设计马上就要结束了，我在此要感谢在这大学最后阶段学校给与了我这个机会，让我将来更好的融入社会环境。

通过本次毕业设计，我学会了基本的java程序设计，并了解一些界面设计。

本论文针对简单遗传算法及其在组合优化方面的应用进行了分析。本文具体使用遗传算法来解决NP完全问题，从NP完全问题的特点来说明用遗传算法来解决此类问题的可行性，在TSP问题中，用数学方法，难以完成，但是采用遗传算法来解决取得了很好的效果，并且用此方法可以解决很多类似的问题。说明遗传算在组合优化方面有很大的优越性。 6.2、前景展望

分析程序执行的结果，可以发现简单遗传算法有很多容易出现的问题，如收敛过快，局部收敛，收敛缓慢等。为了提高遗传算法的性能，要有大量的计算，所以要进一步提高计算速度和计算的并行处理。此外，还要注重同其它传统算法的结合使用。要进一步加强交叉和变异概率的自适应研究，使优化方法的自适性进一步加强。

另外对遗传算法的未成熟收敛和局部收敛现象，还需作更深入更系统的研究，以便使遗传算法有更广泛的使用。

30

巢湖学院计算机系2009届毕业设计（论文）

致谢

在巢湖学院的学习生活即将结束的时候，我的激动之情溢于言表。在这里我要感谢巢湖学院，感谢计算机系，感谢我的老师们，感谢我的同学们。

首先，向指导我完成此次本科毕业设计的丁老师表示深切的感谢，本文的研究工作自始自终都得到了导师的亲切关怀和悉心指导。

在学习的过程中，计算机系的各位老师认真严谨的教学使我受益匪浅，衷心的感谢系里各专业老师传道授业解惑！

感谢同窗的各位好友，我会永远记得我们一起学习一起生活的日子。感谢班上的各位好朋友，各位给予我极大帮助的师兄师姐。

最后，感谢我的父母，亲人，你们对我的感情是我最宝贵的财富。我永远爱你们。

31

巢湖学院计算机系2009届毕业设计（论文）

参考文献

[1] 丁永生.计算智能——理论、技术与应用[M].北京：科学出版社.2004 [2] 陈刚.Eclipse从入门到精通[M].北京：清华大学出版社.2007 [3] 朱福喜.Java语言程序设计[M].北京：清华大学出版社.2005

[4] 潘正军，康立山等.演化算法.北京：清华大学出版社.南宁：广西科学技术出版社.1998 [5] 张莉.遗传算法及其在旅行商问题中的应用[D].[学位论文].天津：天津师范大学.2005 [6] 马良.旅行推销员问题的算法综述[J].数学的实践与认识，2000，Vol.30 NO.2

[7] 刘海.旅行商问题优化算法设计及理论研究初步[D].[学位论文].广州：华南理工大学.2002 [8] 王晓东.计算机算法设计与分析[M].北京：电子工业出版社.2001

[9] 王小平，曹立明.遗传算法——理论、应用与软件实现.西安：西安交通大学出版社.2002 [10] 邓良松，刘海岩，陆丽娜.软件工程[M].西安：西安电子科学技术出版社.2004

32

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