基于混合遗传算法的TSP优化问题求解

发布时间：2020-05-12 00:09

【摘要】：旅行商问题是著名的路径规划问题,在现实生活中有着广泛的应用。伴随着城市数目的增多,传统的算法在旅行商问题巨大搜索空间里的寻优能力越来越差,很难达到精确地求出最优解的目的。如何设计出一个性能高效的近似求解算法成了众多学者的研究重点。遗传算法以其优良的性能,擅长全局搜索的优点,成为了研究组合优化问题中常用的算法。但长期的实际应用中,暴露了遗传算法难以对局部空间进行搜索,导致算法进化后期搜索效率偏低,解质量不高的缺点。因此,近年来学者通过结合局部搜索来提升算法的性能。目前,解旅行商问题局部寻优较好的算子有opt的各种形式(2-opt,3-opt等)以及Lin-Kernighan(LK),然而因为LK的复杂性高,通常较少使用。另外,由于opt的固有特性,其各种形式的局部搜索算子都难较精细地对个体邻域进行搜索。综上所述,本文将单点插入算子(Single Insertion,SI)、交换算子(Swap)引入TSP问题的局部搜索,并结合2-opt,组成一种特有的局部搜索算子集合。同时,鉴于遗传算法在全局搜索能力上的优秀表现,将上述算子集合嵌入遗传算法,从而形成混合遗传算法(HGA),并以其对TSP问题求解。通过国际通用的TSPLIB中不同城市规模的数据进行测试,并对比5种算法的解质量,结果证明了该混合遗传算法的有效性。针对基于随机机会约束规划模型的旅行商问题,本文以基于TSPLIB测试算例生成的不确定旅行商问题测试数据对UHGA算法进行性能衡量和算法验证,并给出相应的实验结果分析。
【图文】：

HGA算法得到的Att48最优路径轨迹图

种算法最优解质量对比
【学位授予单位】：安庆师范大学
【学位级别】：硕士
【学位授予年份】：2018
【分类号】：C81

【相似文献】

相关期刊论文 前10条

1 袁群;左弈;;基于改进混合遗传算法的冷链物流配送中心选址优化[J];上海交通大学学报;2016年11期

2 刘蕊蕊;;基于多目标混合遗传算法认知无线电频谱分配[J];鸡西大学学报;2016年12期

3 杨书森;郭顺生;;基于混合遗传算法的生产调度研究[J];机械制造;2017年10期

4 杨亚辉;;基于混合遗传算法的机床夹具夹紧力优化[J];机械设计与制造工程;2016年10期

5 毛政涛;刘新文;;应用双层混合遗传算法优化大规模换热网络[J];宁波工程学院学报;2014年01期

6 朱传伟;童幼堂;董受全;;混合遗传算法在舰空导弹武器系统火力分配中的应用[J];舰船电子工程;2014年07期

7 王威;徐兵;岳晓峰;;基于机器加工时间最短的混合遗传算法[J];长春工业大学学报(自然科学版);2012年03期

8 高光敏;赵亮;何秋月;王凯;孙洪波;;改进混合遗传算法在无功优化的应用研究[J];长春工程学院学报(自然科学版);2011年01期

9 朱小娟;高庆忠;宋福圣;;基于自适应混合遗传算法的协调控制系统[J];自动化与仪器仪表;2009年03期

10 顾晓芬;郝永平;唐健;;一种基于混合遗传算法的车间调度算法[J];自动化技术与应用;2008年11期

相关会议论文 前10条

1 刘琼昕;陈嘉玉;宋晔;苏思悦;;混合遗传算法在云计算任务调度中的应用[A];第十一届全国信号和智能信息处理与应用学术会议专刊[C];2017年

2 张海波;陈行行;;混合遗传算法在智能天线波束成型中的应用[A];重庆市电机工程学会2010年学术会议论文集[C];2010年

3 吴海兵;刘萍;;混合遗传算法在物流配送路径优化问题中的应用[A];'2006系统仿真技术及其应用学术交流会论文集[C];2006年

4 王永生;曹贝;肖立伊;;基于混合遗传算法的测试壳优化[A];第四届中国测试学术会议论文集[C];2006年

5 李平;;客户成套订单配送策略混合遗传算法研究[A];第九届中国青年信息与管理学者大会论文集[C];2007年

6 马倩;左浩毅;;混合遗传算法和高斯牛顿算法分析电荷交换复合谱的数据[A];第十八届全国光散射学术会议摘要文集[C];2015年

7 何大阔;凌君;顾大为;王福利;;基于减聚类的混合遗传算法[A];第三届中国智能计算大会论文集[C];2009年

8 侯志祥;;基于混合遗传算法的连续系统参数辨识[A];第二十六届中国控制会议论文集[C];2007年

9 宋莉波;徐学军;孙延明;查靓;;一种求解flexible job-shop调度问题的混合遗传算法[A];系统工程与和谐管理——第十届全国青年系统科学与管理科学学术会议论文集[C];2009年

10 刘辙;彭亮;崔广才;吴学礼;;混合遗传算法在车间调度中的应用[A];中国自动化学会全国第九届自动化新技术学术交流会论文集[C];2004年

相关博士学位论文 前10条

1 陶泽;基于Petri网和混合遗传算法的JSP优化调度[D];东北大学;2006年

2 程蓉;复杂生产环境下优化调度方法研究与系统实现[D];华中科技大学;2006年

3 仁庆道尔吉;车间作业调度问题的多目标模型建立及其算法[D];西安电子科技大学;2013年

4 霍红卫;遗传算法在图论和优化中的应用[D];西安电子科技大学;2000年

5 朱云飞;一种用进化方法求解鲁棒最优问题的研究[D];中南大学;2011年

6 彭北青;第三方物流配送车辆路径问题模型及算法研究[D];华中科技大学;2009年

7 张相贤;基于极值理论的金融资产配置研究[D];东华大学;2011年

8 童孝忠;大地电磁测深有限单元法正演与混合遗传算法正则化反演研究[D];中南大学;2008年

9 郑加驹;超磁致伸缩换能器滞回非线性模型的研究[D];天津大学;2009年

10 刘晓霞;基于OCTPN和混合遗传算法的JSP多目标优化调度[D];东北大学;2008年

相关硕士学位论文 前10条

1 罗书敏;基于混合遗传算法的可重入混合流水车间调度优化研究[D];郑州大学;2018年

2 梅俊;基于混合遗传算法的TSP优化问题求解[D];安庆师范大学;2018年

3 李文磊;基于混合遗传算法的转运车调度优化研究[D];东北大学;2015年

4 于丰平;基于混合遗传算法的快递车辆路径优化问题的研究[D];青岛科技大学;2017年

5 李小宁;关于混合遗传算法改进的研究[D];西北大学;2008年

6 王俊丽;基于改进的混合遗传算法的排课问题研究[D];大连海事大学;2013年

7 任刚;多种群退火贪婪混合遗传算法的研究与应用[D];郑州大学;2005年

8 薛凌霄;基于共轭梯度法的混合遗传算法研究[D];福建师范大学;2009年

9 陈磊;基于混合遗传算法的车辆调度优化[D];重庆师范大学;2015年

10 刘辉;基于混合遗传算法的有限能力作业车间调度[D];河北工业大学;2006年

，

本文编号：2659290