基本信息
- 项目名称：
- 遗传算法解决走遍全中国问题
- 来源：
- 第十二届“挑战杯”省赛作品
- 小类：
- 数理
- 大类：
- 自然科学类学术论文
- 简介：
- 现如今旅游是人们缓解压力，放松身心的主要途径之一。本文以走遍全中国34个省会城市为例，通过建立湮灭遗传算法模型，并经过多次实验，最终得到最优的出行路径，再通过权重计算、最大最小值定理和模糊矩阵，综合各方面因素（出行费用、时间、舒适度和方便性等），得出目前最佳的旅行路径和出行方式。为方便人们出行，提供了优良的理论依据。
- 详细介绍：
- 本文首先通过引入湮灭的思想来改进遗传算法，建立了湮灭遗传算法模型。湮灭的本质就是杀死遗传算法在一定时间和空间内产生的局部最优值，从而让搜索跳出局部极值，让远离局部最优的个体有充分的进化空间，从而搜索出更多的最优解。然后根据湮灭思想编写C语言源程序，并用mapgis软件将全国34城市的经纬度转换为距离坐标，带入VC++6.0运行求解，最后得到全国34城市TSP问题的近似最优路线和总里程长度。 模型2运用C++编程，求得34个城市中每两个城市之间的距离，再通过费用与里程的已知关系，求得每两个城市间乘坐飞机、动车和快车卧铺的实际费用，建立一个线性规划模型，从而比较出每个区间段内的最经济乘坐方式，得到最经济的网上订票方案。 模型3 中全面了考虑费用、时间、舒适度和方便性对旅途的影响，联系题目要求，根据变量系数法，求得各个指标的权重。综合考虑，引进“顾客接受度”这一概念来体现并比较各旅行方式的优越性。并通过最大最小值定理和模糊矩阵来简化计算。同时，本论文还结合我国现阶段铁路、航班未全面覆盖，个别城市间不满足评定关系等因素，对于特殊的地区，额外制定特殊的旅行路线和旅行方式，最终制定出最佳的旅行路线和旅行方式。 对两城市间各种出行方式用时的定量分析需要大量的数据，文中使用的相关数据有较好的准确性，而在文中还利用所查数据进行了模型检验。因此，文中最后确定出的旅行路线标准具有一定的可靠性，对有关部门在制定最短旅行路线和旅客环游全国时起到一定的参考作用。在模型的修正过程中，引用了轮船这一出行方式，使整个旅程更加方便，快捷。
作品专业信息
撰写目的和基本思路
- 走遍全中国是现在许多人的梦想。现如今旅游是人们缓解压力，放松身心的主要途径之一。本文以走遍全中国34个省会城市为例，通过建立湮灭遗传算法模型，并经过多次实验，最终得到最优的出行路径，再通过权重计算、最大最小值定理和模糊矩阵，综合各方面因素（出行费用、时间、舒适度和方便性等），得出目前最佳的旅行路径和出行方式。为方便人们出行，提供了优良的理论依据。
科学性、先进性及独特之处
- 本文合理运用湮灭遗传算法，对问题进行了科学的分析与鉴定。全面考虑费用、时间、舒适度和方便性对旅游的影响，综合考虑，引进“顾客接受度”这一概念来体现并比较各旅行方式的优越性。同时，本文还结合我国现阶段铁路、航班未全面覆盖，个别城市间不满足评定关系等因素，对特殊地区，额外制定特殊的路线和方式，最终制定出最佳的旅行路线和旅行方式。与部分实际数据比较，有良好的依据和实际应用价值。
应用价值和现实意义
- 本文所涉及的问题实际上是旅行商（traveling salesman problem 即TSP）问题，是一个NP（non-deterministic poly-nominal）难问题，即不能求出问题的最优确切解。但本文在已知数据的基础上，的除了最优的出行路径和出行方式。对人们的出行，有良好的指引作用。同时本文也可以应用于一些NP难问题，对许多世界上不能解决的问题，给予最合理的解决方案。
学术论文摘要
- 1、本文首先通过引入湮灭的思想来改进遗传算法，建立了湮灭遗传算法模型。湮灭的本质就是杀死遗传算法在一定时间和空间内产生的局部最优值，从而搜索出更多的最优解。然后根据湮灭思想编写C语言源程序，最后得到全国34城市TSP问题的近似最优路线和总里程长度。 2、运用C++编程，求得34个城市中每两个城市之间的距离，再通过费用与里程的已知关系，求得每两个城市间乘坐飞机、动车和快车卧铺的实际费用，建立一个线性规划模型，从而比较出每个区间段内的最经济乘坐方式，得到最经济的网上订票方案。 3、 中全面了考虑费用、时间、舒适度和方便性对旅途的影响，联系题目要求，根据变量系数法，求得各个指标的权重。综合考虑，引进“顾客接受度”这一概念来体现并比较各旅行方式的优越性。并通过最大最小值定理和模糊矩阵来简化计算。同时，本论文还结合我国现阶段铁路、航班未全面覆盖，个别城市间不满足评定关系等因素，对于特殊的地区，额外制定特殊的旅行路线和旅行方式，最终制定出最佳的旅行路线和旅行方式。
获奖情况
- 2009年于沈阳农业大学，荣获东三省数学建模二等奖。 2009年于沈阳农业大学，荣获沈阳农业大学数学建模比赛一等奖。
鉴定结果
- 申报类别：自然科学类（数理） 论文题目：遗传算法解决走遍全中国问题 鉴定结果：内容真实，分析合理。优
参考文献
- 1. 2009年中国统计年鉴 [J].中国统计出版社 2. 旅客票价旅程区段 民用资源网 3. 全国主要城市经纬度表 新浪网 4. 旅游的快捷性 中国民航网 5.刘青凤，李 敏。基于遗传算法的TSP问题优化求解，(安阳工学院, 河南安阳455000) 6计算机与现代化杂志，文章编号: 100622475 (2008) 0220043202，2008年第2期 7.刘青凤，李敏。基于遗传算法的TSP问题优化求解，(安阳工学院, 河南安阳455000)，计算机与现代化杂志，文章编号: 100622475 (2008) 0220043202，2008年第2期 8.遗传算法_百度百科,百度网站，网址： 9.用遗传算法解决旅行商问题，简单代码的网易博客，网址： 10.中国TSP问题，简单代码的网易博客，网址：
同类课题研究水平概述
- 旅行商问题（Traveling Salesman Problem，TSP）长期活跃于数学规划领域，是组合优化问题的典型代表。旅行商问题作为NP难问题的典型代表，下哦那个诞生以来一直都是计算机算法理论研究的热点话题，各种针对该问题的算法层出不穷。理论与应用方面的双重意义使得人们对它的研究兴趣持续不减。TSP所具有的数学、计算机科学和运筹学特点使得其求解算法的发展推动着众多领域的进步和发展。迄今为止，TSP的求解以取得了一些突破性的成果，然而作为NP难问题，围绕着TSP还有很多问题没有解决，还没有通过的有效算法，计算规模也很有限。目前，求解TSP的主要方法包括近似算法、精确算法个针对特殊问题的求解算法。TSP问题是一个典型的组合优化问题，一般很难精确地求出其最优解，因而寻找出有效的近似求解算法就具有中有的意义。 以往对旅行商问题的解决，基本是单人或多人的旅行商问题，对单人多因素问题的研究先对较少。本文一用的遗传算法在近年来逐渐引起了研究者的注意，由于随着在交叉操作中多父辈的引入，降低了一些个体将自身复制到子代中的可能性，这就意味着多父辈交叉有利于提高遗传算法的性能。 旅行商问题是一个典型的组合优化问题，易于描述却难于求解。对于大规模TSP问题，目前扔唯有非常有效的方法，如何快速有效的求解TSP问题，有着重要的理论价值和实际意义。
