文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > 自然科学 > 数学 > 遗传算法及其在TSP问题中的应用
侵权投诉

遗传算法及其在TSP问题中的应用

遗传算法及其在TSP问题中的应用

遗传算法及其在TSP问题中的应用

摘要:本文首先介绍了遗传算法的基本理论与方法,从应用的角度对遗传算法做了认真的分析和研究,总结了用遗传算法提出求解组合优化问题中的典型问题——TSP问题的最优近似解的算法。 其次,本文在深入分析和研究了遗传算法基本理论与方法的基础上,针对旅行商问题的具体问题,设计了基于TSP的遗传算法的选择、交叉和变异算子等遗传算子,提出了求解旅行商问题的一种遗传算法,并用Matlab语言编程实现其算法,最后绘出算法的仿真结果,并对不同结果作出相应的分析。 然后,本文还针对遗传算法求解TSP时存在的一些问题对该算法进行了适当的改进。如针对初始群体、遗传算子作出适当改进,或者将遗传算法与其他方法相结合,以及在编程过程中对算法流程的改进。 本人在用计算机模拟遗传算法求解TSP问题时,首先分析了用Matlab语言设计遗传算法程序的优越性,接着以遗传算法求解TSP问题为例,深入讨论了各个遗传算子的程序实现,并通过分析实验数据,得到各个遗传算子在搜索寻优过程中所起的作用,最后指出了用Matlab语言编程同用其它高级程序语言编程的差异所在,以及运用Matlab编写遗传算法程序的一些注意事项。 最后,本文提出将遗传算法与其它算法相结合来求解一般问题的想法;并将遗传算法的应用范围扩展,提出可以运用遗传算法求解由TSP衍生出的各类TSP扩展问题,如求解配送/收集旅行商问题的遗传算法(TSPD)、遗传算法在货物配送问题中的应用(ST-TSP)、多旅行商问题(MTSP)等。

引言:优化问题可以自然地分为两类:一类是连续变量的优化问题;另一类是离散变量的优化问题,即所谓组合优化问题。对于连续变量的优化问题,一般是求一组实数或一个函数;而在组合优化问题中,一般是从一个无限集或有限的几个无限集中寻找一个对象——它可以是一个整数,一个集合,一个排列或者一个图,也即是从可行解中求出最优解的问题。TSP问题就是其中的典型例子,就本质上而言它可抽象为数学上的组合优化,它描述的是旅行商经N个城市的最短路径问题,因而对TSP问题的求解是数学上,同时也是优化问题中普遍关注的。 旅行商问题(Traveling Salesman Problem,简称TSP)也称为货担郎问题,是一个较古的问题,最早可以追溯到1759年Euler提出的骑士旅行问题[9]。旅行商问题可以解释为,一位推销员从自己所在城市出发,必须邀访所有城市且每个城市只能访问一次之后又返回到原来的城市,求使其旅行费用最小(和旅行距离最短)的路径。 TSP是一个典型的组合优化问题,并且是一个NP难题,所以一般很难精确地求出其最优解,因而寻找出其有效的近似求解算法就具有重要的理论意义。另一方面,很多实际应用问题,如公安执勤人员的最优巡回路线、流水作业生产线的顺序问题、车辆调度问题、网络问题、切割问题以至机组人员的轮班安排、教师任课班级负荷分配等问题,经过简化处理后,都可建模为TSP问题,因而对旅行商问题求解方法的研究也具有重要的应用价值。再者,在各种遗传算法应用实例中,其个体编码方法大多都是采用二进制编码方法或浮点数编码方法,而TSP问题是一种典型的需要使用符号编码方法的实际问题,所以,研究求解TSP问题的遗传算法,对促进遗传算法本身的发展也具有重要意义。 在过去的20年里,在求解旅行商问题的最优解方面取得了极大的进展。尽管有这些成就,但旅行商问题还远未解决,问题的许多方面还要研究,很多问题还在期待满意的回答。

另外,遗传算法就其本质来说,主要是解决复杂问题的一种鲁棒性强的启发式随机

第1页

你可能喜欢

  • GPS在物流中的应用
  • PPT在教学中的应用
  • 遗传算法的应用
  • GPS在地籍测量中的应用
  • 导数在实际问题中的应用
  • 守恒法在化学计算中的应用

热门文档

相关文档

  • 遗传算法在TSP问题中的应用

    如要投诉违规内容,请到百度文库投诉中心;如要提出功能问题或意见建议,请点击此处进行反馈。 加入会员!获取文档下载券 遗传算法在TSP问题中的应用 文章首先介绍TSP问...

  • 遗传算法在TSP问题上的应用

    中南民族大学 硕士学位论文 遗传算法在TSP问题上的应用 姓名:彭丹平 申请学位级别:硕士 专业:计算机应用技术 指导教师:王江晴 20060520 中南民族大学硕士学位论文 ...

  • 【论文】遗传算法在TSP问题中的应用

    遗传算法在TSP问题中的应用_专业资料。遗传算法是借鉴生物界自然选择和进化机制发展起来的全局的概率搜索算法,旅行商问题(TSP)是著名的NP问题,也是组合优化、计算机科...

  • 遗传算法及其在TSP问题中的应用

    遗传算法及其在TSP问题中的应用_IT/计算机_专业资料。MATLAB 遗传算法维普资讯 http://www.cqvip.com 第2 4卷Vo.412 第1 期 JOURNALOFSCAN OLE DUC IHUCLGEOFEA...

  • 【论文】遗传算法在TSP问题中的应用及改进

    遗传算法在TSP问题中的应用及改进_专业资料。旅行商问题(TSP)是研究算法性能的典型算法,遗传算法GA(Genetic Algorithm)是由遗传进化理论指导的随机搜索寻优算法。但传...

  • 遗传算法及其在TSP问题中的应用研究

    贵州大学 硕士学位论文 遗传算法及其在TSP问题中的应用研究 姓名:李薇 申请学位级别:硕士 专业:计算机应用技术 指导教师:王力 20080401 贵州大学2008届硕士毕业论文 ...

  • 遗传算法及其在TSP问题求解中的应用

    遗传算法及其在TSP问题求解中的应用_IT/计算机_专业资料。遗传算法及其在TSP问题求解中的应用第30卷 第1 I期 四川兵工学报 2009年11月 遗传算法及其在TSP问题求解...

  • 改进的单亲遗传算法在TSP问题中的应用

    改进的单亲遗传算法在TSP问题中的应用_设计/艺术_人文社科_专业资料。改进的单亲遗传算法在 TSP 问题中的应用 摘要 : 本文提出了求解旅行商问题 (TSP) 的一个改...

  • 遗传算法在TSP问题求解中的应用

    遗传算法在 TSP 问题求解中的应用课题组长:汪一宁 指导教师:苏俊霞 组员:姚尧 严圣培 王鑫 杨彦芃 王汇 摘要:本文分析了 TSP 问题和用于解决 TSP 问题的多种...

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email