基于贪婪随机自适应灰狼优化算法求解TSP的研究与应用

发布时间：2020-10-12 03:54

　　 随着现代生活中的科技和工业的进步,组合优化问题作为一组经典又实用的问题越发被广泛关注。旅行商问题(Traveling Salesman Problem,TSP)是组合优化中一个经典的问题,也是一个NP-Hard问题,在计算机、数学和运筹学等领域中是热点研究领域,且TSP具有极高的理论和应用价值。在问题规模随着城市规模扩大时,时间和空间复杂度会呈现出指数级的增长,大多数算法都不能够求出一个令人满意的解,所以成为在此专业领域中被研究者们特重视的问题之一。TSP因时代的发展,类似技术的不断进步,如人工智能、计算机技术等,为该问题带来越拉越多的解决方法。启发式算法用于求解TSP时,运行时间较短,但普遍结果不够精确。如今在求解TSP时,多用混合算法,各取其长,提高求解TSP的效率。在本文中,通过对多种求解TSP的算法进行分析后,着重研究了贪婪随机自适应搜索算法(Greedy Randomized Adaptive Search Procedures,GRASP),并将其与其他算法相结合为混合算法。GRASP算法是一个经常用于求解组合优化问题的算法,它是一个二次迭代的过程,该算法在求解TSP时,若所得解陷入了局部最优的情况,是由于其构造阶段的贪婪随机性。针对该算法在求解TSP时对其进行改进,根据其二次迭代的特性,在第一阶段构造通过控制候选表的长度,构造一个可行的贪婪随机初始解。在第二阶段引入群智能算法灰狼优化算法(GreyWolf Optimizer,GWO),对其进行重新编码,能够用于求解TSP这类离散型问题。然而原始的GWO的初始解是随机生成的,它的好坏极大程度上影响了整体的求解,故将构造阶段所得解作为GWO的初始解,利用GWO较强的全局搜索特性,对其进行逼近搜索,从而避免陷入局部最优的情况。对TSPLIB中的多个数据运用改进的算法对其进行大规模的算法性能实验测试,分别对多个参数进行多次调整,多方面对结果进行分析。混合算法在第二阶段搜索后能改善初始解,并且几乎达到全局最优,验证了该算法解的质量有大幅度的提升。大多数实例能够求得最优解,规模较大的实例所求解误差较小,较其他算法在规模较大的实例下仍然能对其进行求解。最后本文将生活中常见的物流配送路径规划问题作为应用场景,该问题可以抽象为TSP的拓展问题,多旅行商问题。物流配送要求多位司机以尽短的路程快速完成配送,首先用K-means对各车辆配送的站点进行划分,再通过使用改进的算法优化配送路径。验证该算法能够运用在实际问题中,提高司机的配送效率,简短配送路程,节省所需时间,从而保证及时完成任务,减少对公司造成的损失。
【学位单位】：太原理工大学
【学位级别】：硕士
【学位年份】：2019
【中图分类】：TP18
【文章目录】：
摘要
abstract
第一章 绪论
    1.1 课题背景与研究意义
    1.2 旅行商问题研究现状
    1.3 论文的研究内容
    1.4 论文章节安排
第二章 相关理论方法
    2.1 Hamilton回路
    2.2 旅行商问题
    2.3 旅行商问题的求解
        2.3.1 完全算法
        2.3.2 近似算法
        2.3.3 启发式算法
    2.4 本章小结
第三章 基于GRASP算法对求解TSP的改进
    3.1 GRASP算法初始化种群
    3.2 改进灰狼优化算法
        3.2.1 灰狼优化算法简介
        3.2.2 构造狼群的编码方式
    3.3 改进策略的优化算法
        3.3.1 基本原理
        3.3.2 算法流程
    3.4 本章小结
第四章 实验及结果分析
    4.1 TSPLIB经典数据
    4.2 参数设置
        4.2.1 RCL长度设置
        4.2.2 狼群数量设置
        4.2.3 局部搜索
    4.3 实验结果
    4.4 实验对比
    4.5 本章小结
第五章 TSP相关拓展研究
    5.1 物流配送路径规划问题研究
    5.2 算法设计
    5.3 实验及结果
        5.3.1 实验数据
        5.3.2 实验结果
    5.4 本章小结
第六章 总结与展望
    6.1 总结
    6.2 展望
参考文献
致谢
攻读学位期间发表的学术论文

【相似文献】

相关期刊论文 前10条

1 黄逸;;算法结构与设计教学中的若干思考[J];中学数学杂志;2008年05期

2 何永生;;算法结构考查“三角度”[J];中学生数理化(高一);2017年01期

3 丁忒;;“算法的概念”教学设计[J];中国数学教育;2017年Z2期

4 王靖亚;;算法结构对其性能的影响研究[J];计算机教育;2005年10期

5 裴承鸣;黎中伟;;ARMA过程的递推线性估计及其应用[J];西北工业大学学报;1987年02期

6 胡平;;试论滤波器的算法结构[J];河北机电学院学报;1987年01期

7 黄继进;;快速DFT计算——基于递归割圆因式分解的新算法[J];计算机应用与软件;1988年05期

8 郑容;;时域加权FFT算法(WTTA)[J];信号处理;1988年04期

9 乞敬换;王秀峰;;具有阻塞的串行生产线“线性”状态方程描述及扰动分析新算法[J];系统工程学报;1989年02期

10 王靖亚;;算法结构对其性能的影响研究[J];中国人民公安大学学报(自然科学版);2005年04期

相关博士学位论文 前5条

1 钟轶君;分片稀疏恢复理论及算法[D];大连理工大学;2018年

2 张慧君;三元M/B/Si功能化合物的第一性原理计算方法研究[D];燕山大学;2017年

3 熊丙章;高中生的算法理解水平及其教学策略研究[D];西南大学;2013年

4 杨乐婵;基于GEP算法和高光谱数据的植物主要理化参数估算研究[D];南京大学;2017年

5 张超;混合群智能优化算法研究及应用[D];北京科技大学;2018年

相关硕士学位论文 前10条

1 高珊;基于贪婪随机自适应灰狼优化算法求解TSP的研究与应用[D];太原理工大学;2019年

2 杨忠保;复杂网络中社区发现算法研究与应用[D];武汉理工大学;2018年

3 崔利娟;基于深度森林的交通标志识别算法研究[D];北方工业大学;2019年

4 王一捷;柔性直流输电技术数模混合仿真功率接口算法研究[D];东北电力大学;2019年

5 吴亚桐;北斗B1频点信号捕获算法研究与实现[D];哈尔滨工程大学;2018年

6 吴琼;基于SSD算法的车辆和行人的检测[D];华中师范大学;2018年

7 丁宗元;基于度量学习的行人重识别若干算法研究[D];常州大学;2018年

8 涂亮杰;基于改进蚁群算法的果园移动机器人路径规划研究[D];南华大学;2018年

9 陈志国;基于OpenCL的多曝光融合算法并行优化[D];西安电子科技大学;2018年

10 郭章建;高动态扩频接收机的捕获与跟踪算法研究[D];华中科技大学;2017年

本文编号：2837598