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

基于蚁群优化的约束求解算法研究

作　者: 薛秋实
导　师: 张永刚
学　校: 吉林大学
专　业: 计算机软件与理论
关键词: 约束满足问题蚁群优化算法弧相容参数调节
分类号: TP18
类　型: 硕士论文
年　份: 2013年
下　载: 48次
引　用: 0次
阅　读: 论文下载

内容摘要

约束满足问题（Constraint Satisfaction Problems，CSPs）是人工智能领域研究的重要问题，也是当前研究的热点。CSPs的应用非常广泛，与我们的日常生活息息相关，如日程安排、资源配置、模式识别和机器视觉等。对CSPs的研究历史悠久，事实上，早在计算机诞生的一百年前，就有人提出了经典的8-皇后问题，拉开了CSPs研究的序幕。随着计算机技术的发展，CSPs逐渐从纯学术研究走向现实应用，并在解决许多重要问题中大显身手。我们现在所看到的CSPs框架起源于1963年Ivan Sutherland的博士论文“Sketchpad:Aman-machine graphical communication system”。CSPs研究的两大领域分别是表示和推理。约束网络是CSPs的一种重要表示方法，能够将各种CSPs实例统一为一种可以公式化表示的数学范式。这种表示方法有两个优点：一是简洁规范，研究人员不需要了解具体的问题，从约束网络就可以知道问题的所有信息，从而可以集中精力研究问题的求解，统一的平台也方便了人们的交流；二是容易实现，开发人员可以轻松地在计算机中实现约束网络的数据结构，为实验和实际应用带来了很大便利。CSPs的推理主要分为两大类：约束传播和搜索。约束传播的目的是简化问题；搜索技术的核心是回溯，理论上可以完备性求解所有CSPs。本文考察了约束满足问题在组合优化问题（Combinatorial Optimization Problems，COPs）上的应用。COPs与我们的日常生活联系更加紧密，如车间调度等。实际上，任何有限资源条件下的分配问题都是组合优化问题，如最近几年越来越突出的资源短缺、环境恶化问题，本质上就是地球上有限的资源与人类无止境的需求间的矛盾。绝大多数COPs都可以用约束网络显式表示，很大程度上求解CSPs的方法和求解COPs的方法可以通用。当CSPs实例比较复杂，且规模较大时，回溯方法的效率很低，人们提出了很多改进方法，主要方向是提高约束传播的效率和回溯搜索的智能性，并在一些问题上取得了良好的效果。可惜的是，仍然没有一种方法能够在所有问题上表现出良好的性能。本文研究用蚁群优化算法求解CSPs。蚁群优化算法（Ant Colony Optimization，ACO）由Dorigo于1994年提出，最初是用来求解组合优化问题的。其优异的性能吸引人们把它应用于求解CSPs。ACO最大的特点是通用性，在很多问题上都取得了良好的效果。不过对于特定问题，它的效率与专用算法还有一定的差距。本文研究的目的是提高ACO求解CSPs的效率，设计和实现一种基于ACO的高效CSPs通用求解器。弧相容（Arc Consistency，AC）算法是一种重要的约束传播方法，能够有效删除搜索空间的冗余部分，用较小的代价化简复杂CSPs实例。参数调节是ACO的重要组成部分，对ACO的性能与鲁棒性有重大影响，本文详细分析了参数调节对ACO的作用机制，提出了一种比较实用的参数调节方案—预定参数调节。本文首先介绍了ACO和CSPs的基本概念与方法，分析了基于ACO求解CSPs的求解器Ant-Solver；在此基础上结合弧相容预处理和预定参数调节方法，提出了改进算法AC-AS；最后应用AC-AS求解了大量COPs的CSPs实例，证明AC-AS在大多数问题上表现良好。AC-AS在很大程度上克服了ACO最主要的缺陷—早熟收敛问题，然而对于极个别问题，算法陷入局部最优陷阱的现象仍然存在。本文作者相信AC-AS还有很大提升的空间，通过开发其他方法和改进现有方法（如设计一种自适应参数调节方法）能够进一步提高算法的性能并最终解决早熟收敛问题。总之，AC-AS在求解未知类型CSPs实例和专用求解器效率不够突出时能够发挥积极的作用，满足鲁棒性且对用户友好，在高效通用求解器设计方面中表现出广阔的前景。

全文目录

摘要  4-6
Abstract  6-12
第1章绪论  12-15
  1.1 研究背景  12
  1.2 研究现状  12-13
  1.3 本文工作  13-15
第2章蚁群优化算法求解随机约束满足问题  15-37
  2.1 引言  15-17
    2.1.1 蚁群优化  15-16
    2.1.2 约束满足问题  16-17
  2.2 概念  17-27
    2.2.1 双桥实验  17-19
    2.2.2 简单蚁群优化  19-21
    2.2.3 最大最小蚂蚁系统  21-22
    2.2.4 约束满足问题  22-23
    2.2.5 推理  23
    2.2.6 回溯搜索  23-24
    2.2.7 随机约束满足问题  24-27
  2.3 蚁群优化算法  27-32
    2.3.1 算法概述  27-28
    2.3.2 约束图和信息素浓度初始化  28-29
    2.3.3 蚂蚁赋值的过程  29-30
    2.3.4 更新信息素浓度  30-31
    2.3.5 参数设置与局部搜索  31-32
  2.4 Ant-Solver 求解随机约束满足问题  32-36
    2.4.1 实验结果  32-35
    2.4.2 数据分析  35-36
  2.5 本章小结  36-37
第3章弧相容与参数调节  37-56
  3.1 弧相容算法  37-46
    3.1.1 约束传播  37-38
    3.1.2 一般弧相容定义  38-40
    3.1.3 一般弧相容算法  40-45
    3.1.4 弧相容与蚁群算法  45-46
  3.2 参数调节  46-52
    3.2.1 参数调节方法概述  46-47
    3.2.2 蚁群算法中的参数调节  47-51
    3.2.3 预定参数调节  51-52
  3.3 AC-AS 求解随机约束满足问题  52-55
    3.3.1 实验结果  52-55
    3.3.2 数据分析  55
  3.4 本章小结  55-56
第4章组合优化问题应用  56-65
  4.1 引言  56-57
  4.2 概念  57
    4.2.1 组合优化问题  57
  4.3 Benchmarks  57-60
  4.4 AC-AS 求解组合优化问题  60-64
    4.4.1 实验结果  60-64
    4.4.2 数据分析  64
  4.5 本章小结  64-65
第5章结束语  65-67
  5.1 工作总结  65
  5.2 工作展望  65-67
参考文献  67-70
作者简介  70-71
致谢  71

基于蚁群优化的约束求解算法研究

内容摘要

全文目录

相似论文