《计算机科学与技术毕业论文doc()》由会员分享，可在线阅读，更多相关《计算机科学与技术毕业论文doc()（17页珍藏版）》请在金锄头文库上搜索。
1、毕业论文题目基于遗传算法的tsp问题研究学 院计算机与科学技术专 业计算机科学与技术学 号学生姓名张 三指导教师李 四日 期二八年六月摘 要TSP问题又称为货郎担问题。TSP是一个典型的优化组合问题，它需要求出旅行商从某一城市出发经过所有城市所走路程的最短路径，其可能的路径数与城市个数成指数关系增长。找出有效的近似求解算法具有重要的意义。选择用遗传算法去解决TSP问题。本论文对各个算子分别选择的是基于序的评估函数、轮盘赌选择法、两点交叉法、两点区间随机排序变异法，并且通过30个城市的实际的例子来验证，结果求出最短路径为421.5977，优于二叉树描述法的结果428.90，启发式搜索法的结果43
2、6.01，表明遗传算法在求解TSP问题上是有效的。关键词：组合优化 ；TSP问题 ；遗传算法 ；最短路径AbstractTSP problem is also known as the traveling salesman problem. TSP is a typical portfolio optimization problem and needs to calculate the shortest path that a traveling salesman goes through all cities. The number of the possible paths may gr
3、ow with index of the number of cities. It is of great significance to find out an effective approximate algorithm.It is used genetic algorithms to solve the TSP problem. In this paper, the operators are fitness function based on sequence choice, selection with the law of roulette gambling, two- poin
4、t crossover, two- point random interval mutation. An actual example through 30 cities is got. The result is 421.5977 of the shortest path, which is better than binary tree description with the result of 428.90, heuristic search with the result of 436.01, and shows that the genetic algorithm for TSP
5、is effective.Key words: Combinatorial Optimization ; TSP ; Genetic Algorithm ; the Shortest Path目 录目 录4绪论51 遗传算法的设计思想82 系统实现93 程序的运行演示124 测试运行134.1 模块测试134.2 整体测试134.2.1 在测试过程中使用到的调试技术：134.2.2 评估运行的可靠性问题：134.3 测试结论14结论15参考文献16绪论一、遗传算法概述和发展背景（1）遗传算法简介遗传算法（Genetic Algorithm，简称GA）是模拟达尔文的遗传选择和自然淘汰的生物进化过
6、程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法，它是由美国Michigan大学J.Holland教授于1975年首先提出来的，并出版了颇有影响的专著Adaptation in Natural and Artificial Systems，GA这个名称才逐渐为人所知，J.Hilland教授所提出的GA通常为简单遗传算法（SGA）。遗传算法是从代表问题可能潜在的解集的一个种群（population）开始的，而一个种群则由经过基因（gene）编码的一定数目的个体(individual)组成。每个个体实际上是染色体(chromosome)带有特征的实体。染色体作为遗传物质的主要载体，即多个基
7、因的集合，其内部表现（即基因型）是某种基因组合，它决定了个体的形状的外部表现，如黑头发的特征是由染色体中控制这一特征的某种基因组合决定的。这个过程将导致种群像自然进化一样，后生代种群比前代更加适应于环境，末代种群中的最优个体经过解码（decoding），可以作为问题近似最优解1。（2）遗传算法特点遗传算法是一类可用于复杂系统优化的具有鲁棒性的搜索算法，与传统的优化算法相比，主要有以下特点：（1）遗传算法以决策变量的编码作为运算对象。传统的优化算法往往直接决策变量的实际植本身，而遗传算法处理决策变量的某种编码形式，使得我们可以借鉴生物学中的染色体和基因的概念，可以模仿自然界生物的遗传和进化机理，
8、也使得我们能够方便地应用遗传操作算子。（2）遗传算法直接以适应度作为搜索信息，无需导数等其它辅助信息。二、关于TSP问题的简介TSP（Traveling Salesman Problem）2问题又称为货郎担问题、旅行商问题，是出现在许多应用中的一个组合优化问题。该问题可简单的描述为：已知n个城市各城市间的相对距离，某一旅行商从某个城市出发访问每个城市一次且仅一次，最后回到出发城市，怎样安排才使其所走路线最短。TSP是一个典型的优化组合问题，它需要求出旅行商从某一城市出发经过所有城市所走路程的最短路径，其可能的路径数与城市个数成指数关系增长3。用图论的术语来说，假设有一个图G=(V,E)，其中V
9、是顶点集，E是边集，设D(dij)是由顶点 i与顶点j间的距离所组成的距离矩阵，TSP就是求出一条通过所有顶点且每个顶点通过一次的最短路径的哈密尔顿回路4。通常说的 TSP都指对称型的 TSP。若对于n个城市 VV1，V2，V的一个访问顺序为 T(t1，t2，tn)，其中 tV（i1，2，n），且记 t n+1t1。则数学模型可以描述为公式（1.1）。Pi=Fi/i=1NFj(i=1,N)（1.2）三、本论文的研究内容本次设计的研究内容包括：（1）用C+ 写出基于遗传算法解决TSP问题的核心程序，本系统用的是两点交叉法和两点区间随机排序的变异法；（2）用C+ 写出一个界面来调用所写的遗传算法程
10、序解决给定的数据；1 遗传算法的设计思想以遗传算法的思想去解决TSP问题，即要在众多的城市路径中找到一个最短的，我们模拟生物进化的程序，即遗传的方式，我们先以一定的方式生成一个初始化群体，为每个染色体计算评价函数，然后群体竞争选择，种群交叉种群变异，如此迭代下去直到迭代代数达到要求找到最短的路径。下面从遗传算法的具体方面来进行设计思想的分析：一、算法设计目前，求解TSP问题的较为常用的方法有二叉树描述法、启发式搜索法、最近邻法、神经网络法、模拟退火法、遗传算法等。遗传算法是模拟生物在自然界中的遗传和进化过程而形成的一种自适应全局概率搜索算法，具有良好的全局寻优能力，成为解决TSP问题的有效方法
11、之一。二、遗传编码遗传算法的编码时将待求问题的解的形式变换成遗传算法所面对的基本编码窜对象，以便于遗传运算。对于最短路径问题，其可行解的形式一般为结点下标联结成的数字串，因此在遗传算法中的编码方式一般为符号编码。具体可以分为以下几种：近邻编码、序编码(Grefenstette 编码)、边编码、自然编码等。在本设计中用到的是自然编码。2 系统实现本系统使用vc+编写，将遗传算法和界面程序分开编写，这样修改起来就比较方便，并且程序的结构看起来也很清晰，理解也很容易。在本程序中有一个功能模块，通过这个模块我们可以读取已经保存好在文件中的城市坐标文件，然后可以通过运行遗传算法来计算给出的数据并得出所要
12、求的结果。本论文通过调用OpenDataFile（）函数读取城市坐标信息。该函数输入参数是strFileName，表示文件名称字符串引用，函数返回值是文件中所含城市个数。其中，城市坐标文件的格式要求为：城市名称 X轴坐标 Y轴坐标读取城市坐标文件的内容到一个容器名为vecCity的结构中，主要代码如图2.1所示。if( FileType = 1 )int ncityindex = 1;while( DataFile.ReadString(strReadString) )strReadString.TrimLeft();strReadString.TrimRight();CString city
13、Name, citycodx, citycody;int nspace = 0;nspace = strReadString.Find( );/ 将得到文件串的左边子串传给cityName作为城市名；if( nspace 0 )cityName = strReadString.Left( nspace );strReadString = strReadString.Mid( nspace+1 );nspace = strReadString.Find( );/ 将读到的字符串的左边串传给citycodx作为x坐标；if( nspace 0 )citycodx = strReadString.L
14、eft( nspace );/ 将读到的字符串的右边串传给citycody作为y坐标；strReadString = strReadString.Mid( nspace+1 );citycody = strReadString;SYCity tmpCity;/ 得到城市名；tmpCity.m_strName = 城市 +cityName;tmpCity.m_nIndex = ncityindex;/ 得到城市的x轴坐标；tmpCity.m_Coordinate.m_fcodx = atof( citycodx );/ 得到城市的y轴坐标；tmpCity.m_Coordinate.m_fcody
15、 = atof( citycody );/ 将得到的城市放在城市列表中；vecCitys.push_back( tmpCity );/ 城市的索引号往后移一位；ncityindex+;图2.1读取城市坐标代码轮盘赌方式竞争选择染色体的模型如图2.2所示。图2.2 一个表现轮盘赌游戏选择的图标，在这个轮盘中可以被选择的数m是6。圆弧中的那些数字对应的是事物被选择中的可能性。3 程序的运行演示（1） 运行GAApp.exe，界面如图3.1所示。 图3.1 程序运行界面（2） 选择“城市坐标文件”，界面如图3.2所示。 图3.2 打开“打开文件”对话框4 测试运行测试在程序设计阶段有两个时期，通常在编写每个模块后做单元测试，另一个时期是对程序的综合测试。4.1 模块测
