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

改进蚁群算法的理论及方法研究

作　者: 肇勇
导　师: 张鹏
学　校: 西南石油学院
专　业: 机械设计及理论
关键词: 工程优化全局优化方法启发式算法元启发式算法连续优化问题多极值优化问题蚁群算法改进蚁群算法模拟退火法混合优化算法遗传算法禁忌搜索算法混沌优化算法
分类号: O224
类　型: 硕士论文
年　份: 2004年
下　载: 1132次
引　用: 18次
阅　读: 论文下载

内容摘要

优化技术是一种以数学为基础，用于求解各种工程问题优化解的应用技术。作为一个重要的科学分支，它一直受到人们的广泛重视，并在工业生产、经济等领域得到迅速推广和应用。鉴于实际工程优化问题的复杂性、大型化、多极值、建模困难等特点，寻求一种适于大规模并行且具有智能特性的通用性较强的全局优化方法已成为有关科学的一个主要研究目标和引人注目的研究方向。全局优化方法一般分为确定型和随机型方法，确定型方法在数学理论上较为完善，但难以应用，传统的随机型方法对于大型复杂型全局优化问题又难以解决，启发式算法(heuristics algorithms)的引入使得随机型方法和整个全局优化方法得到了新的发展，尤其是元启发式算法(metaheuristic algorithms)。 20世纪80年代以来，通过模拟或揭示某些自然现象或过程而产生了一些新颖的启发式算法一元启发式算法，如蚁群算法，模拟退火法、遗传算法，禁忌搜索算法等。这些算法独特的优点和机制，引起了国内外学者的广泛重视并掀起了全局优化领域的研究热潮，尤其是近十年来发展起来的蚁群算法。蚁群算法是本文研究的主要内容。由于蚁群算法原理简单、鲁棒性较强、具有并行性等特点，吸引了越来越多的人进行研究，并已成功地应用于诸如生产调度、布线等生产问题。目前，蚁群算法的研究成果较为分散，且理论发展不成熟，本文总结了国内外蚁群算法的研究成果，并提出了新的改进蚁群算法。蚁群算法在组合优化问题的成功应用，使得人们开始将焦点又集中在其在连续优化问题上的应用。目前国内外对于蚁群算法在连续优化问题的应用研究成果还很少，但初步研究已显示出蚁群算法较好的性能。多极值全局优化问题是本文研究的重点，通过使用一种新的蚁群算法—基于网格法的蚁群算法进行多个算例的测试，证明了该算法的性能较好。可以预见随着蚁群算法理论的不断完善，蚁群算法将越来越成功地用于连续优化问题。本文的主要研究内容及成果如下： (1) 对全局优化方法的基本框架和研究进展进行了系统的综述，分别从全局优化问题的特点，全局优化方法的构造原理和分类，以及现有全局优化方法的不足等几个方面进行了系统的阐述。 (2) 针对近几年来发展较快的启发式搜索算法的理论和方法进行了系统的研究。详细研究了启发式搜索算法的产生、构造方法、基本类型等几个方面。并概述了几种元启发式算法：蚁群算法、模拟退火法、遗传算法、禁忌搜索法、混沌优化算法等。 (3) 详细系统的研究了蚁群算法的发展现状，对于各种改进蚁群算法的特点进行了分析和对比，在此基础之上提出了新的改进蚁群算法，并经过程序调试，其结果显示新的改进蚁群算法的有较好的性能。在研究用于组合优化问题的蚁群算法的基础上，详细地阐述了一种用于连续优化问题的蚁群算法一基于网格的改进蚁群算法，通过测试多个算例发现该方法能够较好地解决一些多极值函数的优化问题。· (4)对广义邻域搜索算法及其统一结构进行了详细.的阐述和分析，并提出了一种新的混合优化算法一ACOSA，即基于蚁群算法和模拟退火法的混合算法。对于ACOSA混合算法的结构和性能进行了分析，经过测试证明ACOSA混合算法优于单纯蚁群算法和模拟退火法等元启发式算法。关键词:工程优化，全局优化方法，启发式算法，元启发式算法，连续优化问题，多极值优化问题，蚁群算法，改进蚁群算法，模拟退火法，棍合优化算法，遗传算法，禁忌搜索算法，混沌优化算法。

全文目录

1 绪论  12-17
  1．1 本文的选题背景及研究意义  12
  1．2 全局优化方法的研究进展  12-14
  1．3 启发式搜索算法的研究进展  14
  1．4 蚁群算法的研究进展  14-16
  1．5 本文研究的构思与设想  16-17
2 全局优化问题及方法  17-25
  2．1 全局优化问题  17-18
  2．2 全局优化方法概述  18-22
    2．2．1 方法的构造原理  19
    2．2．2 不同的分类法  19-20
    2．2．3 现有全局优化方法的不足  20-22
  2．3 蚁群算法概述  22-25
    2．3．1 全局组合优化问题  22-23
    2．3．2 蚁群算法  23-25
3 启发式搜索法  25-36
  3．1 启发式搜索算法概述  25
  3．2 启发式搜索算法的产生  25-26
  3．3 启发式方法的构造与基本类型  26-29
    3．3．1 启发式方法的构造  26
    3．3．2 启发式方法的基本类  26-29
  3．4 元启发式算法  29-36
    3．3．1 计算复杂性与NP完全问题  29-31
    3．3．2 元启发式算法概述  31-36
4 蚁群算法  36-64
  4．1 真实蚁群行为  36-37
    4．1．1 真实蚂蚁行为  36-37
    4．1．2 蚂蚁行为的特点  37
  4．2 蚁群算法的基本原理  37-44
    4．2．1 TSP问题  38
    4．2．2 蚁群算法的基本描述  38-41
    4．2．3 收敛性  41-44
  4．3 改进蚁群算法  44-51
    4．3．1 蚁群算法的特点  44
    4．3．2 现有改进蚁群算法  44-47
    4．3．3 新的改进蚁群算法  47-49
    4．3．4 算法测试  49-51
  4．4 蚁群算法在连续优化问题中的应用  51-64
    4．4．1 用于连续优化问题的蚁群算法概述  51-54
    4．4．2 基于网格法的改进蚁群算法  54-64
5 广义邻域搜索算法及其统一结构  64-71
  5．1 广义邻域搜索算法  64-65
  5．2 广义邻域搜索算法的要素  65-66
  5．3 广义邻域搜索算法的统一结构  66-69
  5．4 优化算法的性能评价指标  69-71
6 ACOSA 混合优化策略  71-82
  6．1 模拟退火算法  71-75
    6．1．1 基本原理  71-73
    6．1．2 模拟退火算法  73-75
  6．2 基于统一结构设计混合优化策略的关键问题  75-76
  6．3 ACOSA混合优化策略  76-82
    6．3．1 ACOSA混合优化策略的构造出发点  76-77
    6．3．2 ACOSA混合优化策略的流程和特点  77-79
    6．3．3 ACOSA混合优化策略的效率定性分析  79-80
    6．3．4 ACOSA混合优化策略的测试  80-82
7 结论与展望  82-84
  7．1 本文的主要工作及成果  82-83
  7．2 结论与展望  83-84
致谢  84-85
附录  85-87
作者简介  87-88
参考文献  88-91

改进蚁群算法的理论及方法研究

内容摘要

全文目录

相似论文