基于遗传算法的tsp问题研究(一)

本论文在电子商务毕业论文栏目，由论文格式网整理,转载请注明来源www.lwgsw.com,更多论文,请点论文格式范文查看

基于遗传算法的tsp问题研究

一、论文观点来源

TSP问题又称为货郎担问题。TSP是一个典型的优化组合问题，它需要求出旅行商从某一城市出发经过所有城市所走路程的最短路径，其可能的路径数与城市个数成指数关系增长。找出有效的近似求解算法具有重要的意义。

选择用遗传算法去解决TSP问题。本论文对各个算子分别选择的是基于序的评估函数、轮盘赌选择法、两点交叉法、两点区间随机排序变异法，并且通过30个城市的实际的例子来验证，结果求出最短路径为421.5977，优于二叉树描述法的结果428.90，启发式搜索法的结果436.01，表明遗传算法在求解TSP问题上是有效的。

二、论文基本观点

以遗传算法的思想去解决TSP问题，即要在众多的城市路径中找到一个最短的，我们模拟生物进化的程序，即遗传的方式，我们先以一定的方式生成一个初始化群体，为每个染色体计算评价函数，然后群体竞争选择，种群交叉种群变异，如此迭代下去直到迭代代数达到要求找到最短的路径。

三、论文主要内容结构

1、算法设计

目前，求解TSP问题的较为常用的方法有二叉树描述法、启发式搜索法、最近邻法、神经网络法、模拟退火法、遗传算法等。遗传算法是模拟生物在自然界中的遗传和进化过程而形成的一种自适应全局概率搜索算法，具有良好的全局寻优能力，成为解决TSP问题的有效方法之一。

2、遗传编码

遗传算法的编码时将待求问题的解的形式变换成遗传算法所面对的基本编码窜对象，以便于遗传运算。对于最短路径问题，其可行解的形式一般为结点下标联结成的数字串，因此在遗传算法中的编码方式一般为符号编码。具体可以分为以下几种：近邻编码、序编码(Grefenstette 编码)、边编码、自然编码等。在本设计中用到的是自然编码。

本系统使用vc++编写，将遗传算法和界面程序分开编写，这样修改起来就比较方便，并且程序的结构看起来也很清晰，理解也很容易。在本程序中有一个功能模块，通过这个模块我们可以读取已经保存好在文件中的城市坐标文件，然后可以通过运行遗传算法来计算给出的数据并得出所要求的结果。

本论文通过调用OpenDataFile（）函数读取城市坐标信息。该函数输入参数是strFileName，表示文件名称字符串引用，函数返回值是文件中所含城市个数。其中，城市坐标文件的格式要求为：

城市名称 X轴坐标 Y轴坐标

读取城市坐标文件的内容到一个容器名为vecCity的结构中，主要代码如图2.1所示。

首页上一页 1 2 下一页尾页 1/2/2


上一篇：中国网络视频行业经营状况研究 (2)	下一篇：社交网络中的个人隐私保护问题和..

Tags：基于遗传算法 tsp 问题研究

【收藏】【返回顶部】