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

基于量子进化算法的机器人联盟编组优化研究

作　者: 许波
导　师: 李智勇
学　校: 湖南大学
专　业: 计算机科学与技术
关键词: 机器人联盟组合优化量子计算量子进化算法联盟问题
分类号: TP242
类　型: 硕士论文
年　份: 2009年
下　载: 111次
引　用: 1次
阅　读: 论文下载

内容摘要

机器人联盟问题属于NP完全的复杂的组合优化问题。基于量子衍生机制的量子信息表达方式与量子门干涉推理方法是一种潜在的可行解决办法。量子概率编码的表达多样性和量子进化算法的并行搜索能力,使得量子进化算法很适合于求解组合优化问题。量子进化算法在求解典型的组合优化问题上的成功,启发了我们将其应用到机器人联盟问题。本文分析了机器人单个联盟以及联盟结构生成问题的特点,对当前机器人联盟生成算法进行了总结和分类,并分析各自算法的优点和不足,指出启发式算法与进化算法的结合是解决机器人联盟生成问题的有效途径。并将量子进化算法应用到机器人单个联盟以及联盟结构生成问题,运用编码的映射将资源配置和任务分配合并为一个过程,降低了问题的复杂性。实验结果表明了本文算法对解决单个联盟问题以及联盟结构生成问题的有效性与先进性。本文的主要的研究内容和成果如下:(1)对机器人联盟及其相关问题进行了探讨,包括联盟问题的提出,机器人联盟问题和联盟环境的形式化描述,单个联盟问题以及联盟结构问题的数学模型以及联盟问题解空间复杂性的分析。(2)针对单个联盟问题,提出了基于量子进化算法的单个联盟算法。并针对基本的量子进化算法引入“基于信息正反馈的岛屿模型”对其改进,采用进化方程对量子门进行更新,使其具有更快的收敛速度和不再易于陷入局部极值。对比实验结果表明,算法不但保持了量子进化算法并行性、鲁棒性强等优点,而且提高了解的质量,加快了收敛速度,不易陷入局部极值,收敛稳定性较高。同时算法基于岛屿模型的信息反馈机制和采用进化方程对量子门进行更新比基本的量子进化算法机制更灵活、更有效、有更高的鲁棒性,可以有效减少联盟生成的搜索时间和计算量,可实现性较好。(3)针对联盟结构问题,提出了基于量子进化算法的联盟结构生成算法。运用编码的映射,将资源组合和任务分配合并为一个过程,降低了问题的复杂性,根据联盟结构生成问题的特点,在采用量子进化算法求解的时候,对量子进化算法中的相关部分(量子编码、适应度函数等)重新进行了设计。对比实验结果表明,算法在联盟结构生成问题中同样能保证解的质量,加快了收敛速度,不易陷入局部极值,收敛稳定性较高,可以有效减少联盟结构生成的搜索时间和计算量。

全文目录

摘要  5-6
ABSTRACT  6-13
第1章绪论  13-20
  1.1 研究的背景与意义  13-15
  1.2 国内外研究现状及应用  15-18
    1.2.1 国内外研究现状  15-16
    1.2.2 应用前景  16-18
  1.3 本文工作与论文结构  18-20
    1.3.1 研究的主要内容  18-19
    1.3.2 论文结构  19-20
第2章多机器人任务协作联盟问题  20-26
  2.1 联盟问题及环境的形式化描述  20-22
    2.1.1 问题的提出与问题的实例  20-21
    2.1.2 相关定义  21-22
    2.1.3 联盟环境的描述  22
  2.2 联盟问题的数学模型及分析  22-23
    2.2.1 单个联盟问题的数学模型  22-23
    2.2.2 联盟结构问题的数学模型  23
  2.3 问题的复杂性分析  23-24
  2.4 本章小结  24-26
第3章量子进化算法  26-35
  3.1 量子计算基本原理与概念  26-29
    3.1.1 量子计算  26-28
    3.1.2 量子位  28-29
    3.1.3 量子门  29
  3.2 量子进化算法  29-32
    3.2.1 量子染色体的表示  30
    3.2.2 量子门的更新  30-31
    3.2.3 算法实现步骤  31-32
  3.3 量子进化算法未来研究展望  32-34
    3.3.1 基础理论  32-33
    3.3.2 算法研究  33
    3.3.3 面向组合优化问题.  33
    3.3.4 面向不确定优化问题  33
    3.3.5 面向多目标优化问题  33-34
    3.3.6 应用研究  34
  3.4 小结  34-35
第4章基于量子进化算法的单个联盟问题求解  35-45
  4.1 引入量子进化算法的可行性分析  35-36
  4.2 求解单个联盟问题的量子进化算法设计  36-39
    4.2.1 基于信息正反馈的岛屿模型  36
    4.2.2 算法设计  36-38
    4.2.3 算法具体流程  38
    4.2.4 算法收敛性说明  38-39
  4.3 仿真实验与分析  39-44
    4.3.1 仿真实验  39-40
    4.3.2 比较与分析  40-44
  4.4 小结  44-45
第5章基于量子进化算法的联盟结构生成  45-53
  5.1 联盟结构生成问题的特点  45
  5.2 求解联盟结构问题的量子进化算法设计  45-48
    5.2.1 量子比特编码  45-46
    5.2.2 适应度函数设计  46
    5.2.3 量子概率编码变异算子  46-47
    5.2.4 量子门更新策略  47
    5.2.5 算法实现流程  47-48
  5.3 仿真实验与分析  48-52
    5.3.1 仿真实验  48
    5.3.2 比较与分析  48-52
  5.4 小结  52-53
总结与展望  53-55
参考文献  55-60
附录 A (攻读学位期间所发表的学术论文)  60-61
致谢  61

基于量子进化算法的机器人联盟编组优化研究

内容摘要

全文目录

相似论文