量子遗传算法的改进及在货物配装问题中的应用

摘要

量子遗传算法是将量子算法和遗传算法相结合起来的一种高效的智能优化算法，除具有遗传算法的优点外，还具有全局寻优能力强、收敛速度快、种群规模小等优点。对于复杂优化问题的求解，量子遗传算法是一种有效的解决方法。但是量子遗传算法在复杂函数优化问题上存在迭代次数多、收敛速度慢、较易陷入局部最优解的不足。为此本文对传统的量子遗传算法作改进，主要研究工作如下:
　　一是提出了一种改进的量子遗传算法(IQGA)，采用动态策略调整量子旋转角，加快量子搜索的收敛速度;在量子旋转策略中动态嵌入变异算子，增加种群的多样性，并通过灾变算子使算法及时跳出局部最优点，避免早熟收敛。二是在IQGA的基础上提出了一种基于多种群的改进量子遗传算法(MPIQGA)，使用多种群替代单种群，同时在种群初始化过程中采用小生境协同策略来均匀划分量子位空间，使各子种群均匀分布到解空间，有利于保持种群的多样性，各种群之间通过全局最优个体来更新进化目标的形式联系。多种群的并行搜索可以加快搜索速度，缩短迭代次数。实验首先通过若干个复杂连续函数验证改进量子遗传算法的可行性和有效性。
　　物流配送中的货物配装问题属于工程领域的约束优化问题，本文利用IQGA和MPIQGA对一种多车型多货物配装问题模型进行求解，其中对该模型的约束条件进行变形，转化成惩罚函数添加到适应度函数里，并加入整车合并思想，能够有效的减少所需配装车辆的数量。实验结果说明新算法用于解货物配装问题是可行的、有效的，新算法具有一定应用价值。

目录

声明

摘要

第一章 绪论

1．1 研究背景及意义

1．2 研究现状

1．2．1 货物配装问题的研究现状

1．2．2 遗传算法研究现状

1．2．3 量子遗传算法研究现状

1．3 主要研究内容

1．4 论文结构

第二章 量子遗传算法的原理

2．1 量子计算

2．1．1 量子比特

2．1．2 量子逻辑门

2．2 遗传算法

2．2．1 个体编码

2．2．2 适应度函数

2．2．3 遗传操作

2．2．4 算法流程

2．3 量子遗传算法

2．3．1 量子比特编码

2．3．2 量子旋转门

2．3．3 量子交叉与变异

2．3．4 量子遗传算法流程

2．4 本章总结

第三章 量子遗传算法的改进

3．1 一种改进的量子遗传算法

3．1．1 量子旋转门

3．1．2 量子灾变

3．1．3 算法流程

3．1．4 仿真实验

3．2 基于多种群的改进量子遗传算法

3．2．1 小生境协同初始化种群

3．2．2 多种群量子遗传算法

3．2．3 算法流程

3．2．4 仿真实验

3．3 本章总结

第四章 基于改进量子遗传算法的多车型多货物配装问题

4．1 货物配装问题的一般描述

4．2 货物配装问题的构成要素

4．3 配装问题的分类

4．4 基于改进量子遗传算法的多车型多货物配装问题

4．4．1 问题描述及数学模型

4．4．2 适应度函数

4．4．3 量子比特编码

4．4．4 整车合并策略

4．4．5 仿真实验

4．5 本章结论

第五章 总结与展望

5．1 总结

5．2 展望

参考文献

致谢

攻读硕士学位期间发表论文情况