Hopfield神经网络在TSP问题中的应用

论文摘要

旅行商问题是组合优化领域中的一个典型问题,该问题的核心就是要求出一个包含所有n个城市的具有最短路程的环路。虽然它陈述起来很简单,但求解却很困难,并且已经被证明是NP完全问题。但它确实广泛存在,且是诸多领域内出现的多种复杂问题的集中概括和简化形式。因此提出一种有效地解决TSP问题的算法有着较高的理论意义和实际应用价值。本文首先从现有求解TSP的算法入手,通过研究大量的参考文献,了解了各种算法的主要思想,并对各种算法进行了整理和分类。研究发现遗传算法、模拟退火算法和蚁群算法这三种算法在解决TSP问题中表现出了一定的优势,并且在实际的问题的求解中得到了广泛的应用。接下来本文就对这三种算法进行了深入的研究,并进行了编程实现。文中分别用这三种算法解决了48个城市的TSP问题。从结果中作者发现模拟退火算法的优化过程较长;蚁群算法同样是搜索时间比较长,也容易陷于局部最优解,使搜索停滞。遗传算法实际应用时易出现早熟收敛和收敛性差等缺点。如何快速准确的解决TSP问题成为了现在TSP算法研究中的一个难点。作者提出了一种基于Hopfield神经网络的算法,由于神经网络是并行计算的,其计算量不随维数的增加而发生指数性“爆炸”,因而对于优化问题的高速计算特别有效。在实际的实验过程中作者发现该算法从在一个致命的缺点就是网络极不稳定,经常得不到结果。为此,作者在对现有算法进行了改进。经过研究发现最终结果的准确性很大程度上取决于初始参数的设置。在认识到这一点后,对每个参数对结果的影响进行了分析,最后给出了参数的合理设置方法。本文还对能量函数进行了改进,使得问题的求解更加快速准确。对‘出现重复解的问题’进行了解决采用了一种从固定起点出发的办法。最后应用该算法解决了西安旅游问题,首先结合西安旅游地图,根据具体的旅游问题给出了网络的能量函数,进而构建了一个Hopfield神经网络。选取了西安的著名旅游景点,对景点进行了变换和归一化,对算法编程进行实验。实验结果表明,该方法对10个景点和15个景点的迭代次数大都集中在250～350之间,说明该方法对于处理旅游路线的选择问题是行之有效的。

论文目录

• 摘要
• Abstract
• 第一章 绪论
• 1.1 问题的提出
• 1.2 TSP的应用和价值
• 1.3 TSP问题的研究现状
• 1.3.1 模拟退火算法
• 1.3.2 遗传算法
• 1.3.3 人工神经网络算法
• 1.3.4 蚁群算法
• 1.3.5 其他算法
• 1.3.6 未来可研究的问题
• 1.4 本文的主要安排
• 第二章 对旅行商问题的分析和一些经典算法的介绍
• 2.1 TSP问题的描述及数学模型
• 2.2 TSP问题的分类
• 2.3 解TSP的算法综述
• 2.4 精确算法
• 2.4.1 可解情形（特例）
• 2.4.2 穷举搜索法
• 2.4.3 贪婪算法
• 2.4.4 线性规划算法
• 2.4.5 动态规划算法
• 2.4.6 分支定界算法
• 2.5 近似算法
• 2.5.1 插入算法
• 2.5.2 最近邻算法
• 2.5.3 Clark&Wright算法
• 2.5.4 双生成树算法
• 2.5.5 Christofides算法
• 2.5.6 r-opt算法
• 2.5.7 混合优化策略方法
• 2.5.8 概率算法
• 2.5.9 模拟退火算法
• 2.5.10 蚁群算法
• 2.5.11 遗传算法
• 2.5.12 神经网络算法
• 2.6 本章小结
• 第三章 一些典型算法在TSP问题中的应用
• 3.1 模拟退火算法
• 3.1.1 模拟退火算法的模型
• 3.1.2 参数设置
• 3.1.3 实验结果
• 3.2 蚁群算法
• 3.2.1 蚁群算法的基本原理
• 3.2.2 基本蚁群系统模型
• 3.2.3 应用蚁群算法要注意的问题
• 3.2.4 算法的实现
• 3.2.5 实验结果
• 3.3 遗传算法
• 3.3.1 GA基木概念和基本操作
• 3.3.2 遗传算法描述
• 3.3.5 求解TSP的遗传操作方法
• 3.3.6 实验结果
• 3.4 本章小结
• 第四章 人工神经网络求解TSP问题
• 4.1 人工神经网络简介
• 4.2 Hopfield神经网络
• 4.2.1 离散型Hopfield神经网络
• 4.2.2 连续型Hopfield神经网络
• 4.2.3 采用连续Hopfield网络求解TSP问题
• 4.2.4 算法的实现
• 4.3 对现有算法的改进
• 4.3.1 对参数的分析和改进
• 4.3.2 对能量函数的改进
• 4.3.3 对上述算法的进一步改进
• 4.4 实验结果
• 4.5 本章小结
• 第五章 应用HOPFIELD神经网络解决西安市旅游问题
• 5.1 旅游景点向量矩阵
• 5.2 景点的选取
• 5.2.1 游客对景点的评价
• 5.2.2 景点坐标的确定
• 5.3 实验结果
• 第六章 总结与展望
• 6.1 总结
• 6.2 展望
• 参考文献
• 致谢
• 攻读硕士学位期间发表的论文及所取得的研究成果