文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > 高等教育 > 理学 > 运用遗传算法求解TSP问题的探讨
侵权投诉

运用遗传算法求解TSP问题的探讨

运用遗传算法求解旅行商问题的探讨,数学建模中的经典问题

第24卷 第5期 天 中 学 刊 Vol. 24 No. 5 2009年10月 Journal of Tianzhong Oct. 2009

运用遗传算法求解TSP问题的探讨

刘会超1, 2,刘 珂2

(1. 武汉大学,湖北 武汉 430072;2. 黄淮学院,河南 驻马店 463000)

摘 要:通过对遗传编码方案的改进,克服了TSP问题中的数据冗余缺陷,使得搜索性能得到提高.将该遗传算法应用于实际TSP问题,计算结果证明了该遗传算法的有效性. 关键词:TSP;遗传算法;杂交;变异 中图分类号:TP18

文献标识码:B

文章编号:1006-5261(2009)05-0036-02

1 TSP问题及其应用

早由美国J.H.Holland教授提出,其主要特点是简单、通用、鲁棒性强,尤其适用于传统搜索算法难以解决的复杂和非线性问题.隐含的并行性和全局搜索性是遗传算法的两大显著特征[2]. 2.1 遗传编码方案及初始种群的产生

TSP问题是组合优化中典型的NP-C问题.TSP

问题可以描述为:某商人要到给定n个城市推销货物,从某城市出发遍历其余各城市一次且仅一次,最后再回到起点,求其最短的行程,即寻找一条巡回路径P=(p1,p2,L,pn),使得

n 1

遗传编码方法有多种,本文采用路径表示法,即:

n个城市的个体表示为(p1,p2,L,pn),其中p1~pn互不

相等;路径(5―9―1―4―7―2―3―8―6―10)可以直f(P)=min(∑d(pi,pi+1)+d(pn,p1)), (1)

i=1接表示为(59147238610).

其中pi为城市号,d(pi,pj)表示城市i与城市j之间的实际上,由于路径实际表达的是一个首尾相连的连接代价.对于对称式TSP,有d(pi,pj) = d(pj,pi);对于非对称式TSP,d(pi,pj) ≠ d(pj,pi).本文仅讨论对称式TSP.

TSP问题涉及网络通讯、车辆调度、管道铺设、

回路,所以存在冗余路径.例如,路径(5―9―1―4―7―2―3―8―6―10)可以写成(10―5―9―1―4―7―2―3―8―6),也可以写成(8―6―10―5―9―1―4―7―2―3)等.也就是说,n个城市间的任意一条路径就

电路布线等优化问题,因此快速、有效地解决TSP问题有着极高的实际应用价值.迄今为止,人们为求解TSP问题提出了大量的搜索算法,如穷举搜索法、贪

对应有另外n 1条冗余路径.

在本文中,消除冗余路径的做法是:把所有个体编码的首位p1强制设为1号城市,这样,参与演化操作的所有个体所表达的路径都是以城市1为首位的,去除冗余,有助于其他n 1条等价路径就不会出现.

缩小搜索范围,缩短搜索时间,提高搜索效率,最终获得更优的解. 2.2 选择机制

婪法、插入算法、r-opt算法、神经网络算法、模拟退火算法、动态规划法、分支定界法、遗传算法及蚁群算法等[1].

2 运用遗传算法求解TSP问题

遗传算法(Genetic Algorithm,简称GA)的基本思想是基于Darwin进化论的Mendel的遗传学说,它将问题的解集看作一个种群,通过不断的选择、交叉、变异等遗传操作,使解的质量越来越好.遗传算法最

收稿日期:2009-02-25

求解TSP问题,常用的选择机制有轮盘赌选择机制、最佳个体选择机制、期望值模型机制、联赛选择机制等[3],本文中采用轮盘赌选择机制.轮盘赌选择机制先定义种群中个体适应度函数

作者简介:刘会超(1982~ ),男,河南驻马店人,黄淮学院计算机科学系助教,武汉大学软件工程国家重点实验室硕士研

究生.

第1页

你可能喜欢

  • 遗传算法解决TSP问题
  • 人工智能导论
  • 旅行商问题算法
  • 车辆路径问题
  • 汉诺塔递归算法
  • 编译原理第二版课后答案
  • 遗传算法应用实例

热门文档

相关文档

  • 【武汉大学】运用遗传算法求解TSP问题的探讨

    【武汉大学】运用遗传算法求解TSP问题的探讨_工学_高等教育_教育专区。遗传算法求解TSP问题第24卷第5期2009年10月 天中学刊JournalofTianzhong 、,01.24 No.5 ...

  • 【浙江大学 综合】遗传算法求解TSP问题的研究进展

    4)遗传算法使用的选择、交叉、变异算子都是随机的; 3对TSP的遗传基因编码方法在遗传算法的应用中,遗传基因的编码是一个很重要的问题.对遗传基因进行编码时,要...

  • 【论文】遗传算法求解TSP问题的改进

    遗传算法求解TSP问题的改进_专业资料。针对遗传算法解决TSP问题的特点,构造出遗传算法需要的初始种群.运用相同算法对改进前后的两种种群进行实验,得出改进方法具有增强...

  • 遗传算法求解TSP问题的研究

    第 7 卷第 26 期 (2011 年 9 月 ) http://www.dnzs.net.cn E-mail: eduf@cccc.net.cn Tel:+86-551-5690963 5690964 遗传算法求解 TSP 问题的研究汪...

  • 用遗传算法求解TSP问题

    具体的适应度函数可以表示为f=i/(Td+ ●t I输山琏庖鹿值t优的十体I 图1求解TSP问题的遗传算法框图 2 TSP遗传算法表示和实现演化计算已被成功地应用于求解...

  • 遗传算法解决TSP问题。C++、MFC界面编程

    (系 学院 系): 专题业: 目: 计算机科学与技术学院 计算机科学与技术 基于遗传算法的 TSP 问题求解方法 的研究与实现 指导者: 指导者: 朱保平 (姓名) 副教授...

  • 基于Matlab的遗传算法解决TSP问题的报告

    基于Matlab的遗传算法解决TSP问题的报告_其它_总结/汇报_应用文书。使用matlab语言对遗传算法进行编程,解决TSP问题,并使用专门测试的tsp进行试验,发现和标准值比较...

  • 求解TSP问题的一种启发式遗传算法

    TSP问题是著名的NPC问题,在组合优化中有许多应用。讨论如何应用启发式遗传算法求解此问题,并设计一种启发式交叉算子和换位变异算子,主要特点是给出算子在程序中的...

  • 【论文】求解TSP问题的一种改进的遗传算法

    求解TSP问题的一种改进的遗传算法_IT/计算机_专业资料。TSP维普资讯 http://www.cqvip.com 求解 T P问题 的一种改进 的遗传算法 S谢胜利 唐敏: 董金祥 (...

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

    遗传算法及其在TSP问题中的应用研究_自然科学_专业资料。用粒子群算法等求解TSP问题的相关论文贵州大学 硕士学位论文 遗传算法及其在TSP问题中的应用研究 姓名:李薇...

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