| 【中文题名】 | 量子进化算法研究及应用 |
| 【英文题名】 | Research and Application of Quantum Inspired Evolutionary Algorithm |
| 【学科专业】 | 计算机软件与理论 |
| 【论文级别】 | 硕士论文 |
| 【投稿时间】 | 2007-10-19 |
| 【中关键词】 | 量子计算,进化算法,分布估计,多选择多维背包问题,多目标进化算法, |
| 【英关键词】 | Quantum Computing,Evolutionary Algorithms,Estimation of distribution,Multiple Choice Multi-Dimensional Knapsack problem,Multi-Objective Evolutionary Algorithms, |
| 【分类导航】 | 工业技术>自动化技术、计算机技术>自动化基础理论>人工智能理论>> |
| 【论文摘要】 |
量子进化算法是基于量子计算原理的一种进化算法。这种崭新的优化算法，具有很大的生命力和研究价值。它以量子计算的一些概念和原理为基础，用量子位编码，量子门作为更新算子来完成进化搜索。与传统进化算法相比，量子进化算法能够更容易的在探索与开发之间取得平衡，具有种群规模小、收敛速度较快、全局寻优能力强的特点。实验表明量子进化算法在很多问题上比传统进化算法具有更好的性能，但解决一些复杂优化问题的能力不强，容易陷入局部最优。为了使量子进化算法能够更有效的解决实际的优化问题，本文对此做了进一步的研究，使量子进化算法的性能进一步提高，并扩大了它的应用范围。
本文所做的贡献和成果主要有以下几部分：
1．提出了基于分布估计的量子进化算法。在该算法中同时保存两种概率模型，相辅相成，促使算法在保证种群多样性下快速收敛。还提出了自适应调整旋转角度的策略，使旋转角度随演化的过程自动调整。
2．将量子进化算法应用到多选择背包问题和多选择多维背包问题，针对这类特殊问题提出了相应的观测解过程和新的旋转算子。
3．将基于分布估计的量子进化算法扩展到多目标优化，取得了很好的效果。 |
| 【论文题纲】 |
|
摘要 |
3-4 |
|
ABSTRACT |
4-9 |
|
第一章 绪论 |
9-15 |
|
1.1 现代优化方法回顾 |
9-10 |
|
1.2 量子进化算法及研究现状 |
10-11 |
|
1.3 复杂背包问题研究现状 |
11-12 |
|
1.4 多目标进化算法研究现状 |
12-13 |
|
1.5 本文的研究目的内容及结构安排 |
13-15 |
|
第二章 量子计算原理与量子进化算法简介 |
15-25 |
|
2.1 量子计算原理 |
16-18 |
|
2.1.1 状态的叠加 |
16-17 |
|
2.1.2 状态的相干 |
17-18 |
|
2.1.3 状态的纠缠 |
18 |
|
2.2 量子进化算法 |
18-24 |
|
2.2.1 染色体的表示 |
18-19 |
|
2.2.2 更新算子 |
19-21 |
|
2.2.3 算法流程 |
21-24 |
|
2.3 小结 |
24-25 |
|
第三章 基于分布估计的量子进化算法 |
25-37 |
|
3.1 量子染色体的分布估计 |
26-27 |
|
3.2 自适应旋转更新算子 |
27-29 |
|
3.2.1 角度的方向的设定 |
27-28 |
|
3.2.2 自适应调整旋转幅度 |
28-29 |
|
3.3 算法具体实施 |
29-31 |
|
3.4 对比试验分析 |
31-35 |
|
3.4.1 函数优化 |
31-33 |
|
3.4.2 0-1背包问题 |
33-35 |
|
3.5 小结 |
35-37 |
|
第四章 量子进化算法在复杂背包问题中的应用 |
37-51 |
|
4.1 多选择背包问题 |
37-38 |
|
4.2 多选择多维背包问题 |
38-40 |
|
4.3 求解MMKP的量子进化算法 |
40-46 |
|
4.3.1 MMKP解的表示 |
40 |
|
4.3.2 量子种群的表示 |
40-41 |
|
4.3.3 观测解的生成 |
41-42 |
|
4.3.4 更新算子 |
42 |
|
4.3.5 构造基础解 |
42-44 |
|
4.3.6 修补算子 |
44 |
|
4.3.7 局部搜索 |
44-46 |
|
4.3.8 算法具体流程 |
46 |
|
4.4 实验结果 |
46-49 |
|
4.4.1 典型多选择背包问题 |
47 |
|
4.4.2 多选择多维背包问题 |
47-49 |
|
4.5 小结 |
49-51 |
|
第五章 基于分布估计的多目标量子进化算法 |
51-61 |
|
5.1 多目标优化问题描述及相关概念 |
51-54 |
|
5.1.1 目标向量比较 |
52 |
|
5.1.2 PARETO优超(PARETO DOMINACE) |
52 |
|
5.1.3 PARETO最优(PARETO OPTIMALITY） |
52 |
|
5.1.4 PARETO最优集和PARETO最优前沿 |
52 |
|
5.1.5 局部PARETO最优性和全局PARETO最优性 |
52-54 |
|
5.2 基于分布估计的多目标量子进化算法 |
54-59 |
|
5.2.1 快速非优超排序 |
54-55 |
|
5.2.2 排挤排序 |
55-57 |
|
5.2.2.1 排挤距离的计算 |
56 |
|
5.2.2.2 排挤比较算子 |
56-57 |
|
5.2.3 分布估计 |
57 |
|
5.2.4 EQMEA算法流程 |
57-59 |
|
5.3 实验结果比较 |
59-60 |
|
5.4 小结 |
60-61 |
|
第六章 结束语 |
61-63 |
|
参考文献 |
63-67 |
|
附录1 攻读硕士学位期间发表的论文 |
67-69 |
|
附录2 致谢 |
69-71 |
|
| 【DOI】 | LunWen.ID:2.2008.389094 |
