学位论文 > 优秀研究生学位论文题录展示

基于节约算法和移动方向的禁忌搜索算法

作　者: 郭娜
导　师: 曹晓东
学　校: 大连理工大学
专　业: 计算机应用技术
关键词: 禁忌搜索 c-w节约算法多样性搜索
分类号: TP301.6
类　型: 硕士论文
年　份: 2009年
下　载: 247次
引　用: 3次
阅　读: 论文下载

内容摘要

随着优化算法和启发式算法的提出,国内外掀起了研究智能优化算法的热潮。禁忌搜索是一种新的智能优化算法,是由美国科学家Glover教授于1986年正式提出。禁忌搜索(TS)在智能算法中独树一帜,成为一个研究热点,受到了国内外学者的广泛关注,并应用到组合优化和函数优化问题中。本文基于原禁忌搜索的思想提出一种改进的禁忌搜索算法,并把这种改进算法应用到实际问题中。在前期工作的基础上,本文主要的工作包括针对禁忌搜索算法对初始解依赖性强的缺点,利用c-w节约算法得到初始解。禁忌搜索算法设计的框架中初始解尤为关键,初始解的好坏制约着搜索的收敛速度。通过c-w节约算法得到高质量解,构造算法新的搜索起点,加强了集中性搜索力度。在仿真实验中验证了其有效性。同时针对禁忌搜索算法中集中性与多样性搜索并重的情况下,多样性不足的缺点,从下面两个方面改进算法,拓宽搜索领域,加强多样性搜索,增加灵活性。通过改进禁忌表存储结构,定义优质解和劣质解的出现次数这两个概念,不只利用禁忌表禁忌最近的搜索,还记录这些移动是否有所改进,记录下改进的信息,表明新解的改变程度,在搜索决策中并入这些信息,使得搜索往利于改进的方向进行。T S中确定性的搜索过程制约了它的灵活性,所以在禁忌搜索原则确定的基础上,根据搜索中的移动信息,增加概率性因素,在评价函数中增加一个概率函数,把确定性选择过程变为概率性的,从而改进搜索方向,拓宽搜索领域,使得更好的解有更大的被选中的机会。旅行商问题(TSP)是典型的组合优化难题,但由于TSP有着广泛的实际应用工程背景,有效地解决TSP问题一直受到人们的重视,已有多种方法成功求解TSP问题。根据本文改进的禁忌搜索算法提出一种解决TSP问题有效形式。

全文目录

摘要  4-5
Abstract  5-8
1 绪论  8-14
  1.1 禁忌搜索算法的提出  9-10
  1.2 禁忌搜索算法的研究现状  10-12
    1.2.1 实际应用  10
    1.2.2 理论研究  10-12
  1.3 研究意义  12
  1.4 本文的具体工作和内容安排  12-14
2 禁忌搜索算法理论研究  14-27
  2.1 最优化问题  14-16
    2.1.1 启发式算法  14-15
    2.1.2 邻域函数与局部搜索  15-16
  2.2 禁忌搜索  16-27
    2.2.1 禁忌搜索原理  16-25
    2.2.2 禁忌搜索的收敛性  25-27
3 禁忌搜索的改进  27-37
  3.1 算法改进的提出  27-28
  3.2 算法改进  28-37
    3.2.1 改进集中性搜索  29-31
    3.2.2 改进多样性搜索  31-34
    3.2.3 算法流程  34-37
4 TSP问题的禁忌搜索实现  37-48
  4.1 TSP问题  37-38
  4.2 TSP问题的禁忌搜索算法框架  38-45
    4.2.1 初始解  40
    4.2.2 邻域搜索  40-41
    4.2.3 禁忌表  41-43
    4.2.4 评价函数  43
    4.2.5 选择策略  43
    4.2.6 特赦准则  43-45
    4.2.7 终止准则  45
  4.3 TSP问题的禁忌搜索算法流程  45-48
5 算法测试  48-52
  5.1 算法有效性  48-50
    5.1.1 本文算法测试结果  48-50
    5.1.2 与其他算法的对比  50
  5.2 收敛速度的影响  50-52
结论  52-53
参考文献  53-55
附录 A 中国旅行商问题的31城市距离表  55-58
攻读硕士学位期间发表学术论文情况  58-59
致谢  59-60

基于节约算法和移动方向的禁忌搜索算法

内容摘要

全文目录

相似论文