量子进化算法改进及应用研究

作     者：王全新 

作者单位：吉林大学 

学位级别：硕士

导师姓名：梁艳春

授予年度：2007年

学科分类：08[工学] 081202[工学-计算机软件与理论] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主      题：量子计算 量子进化算法 可满足性问题 量子组合优化算法 背包问题 函数优化 

摘      要：量子进化算法是量子计算和进化算法相结合的一种新的优化算法,这种算法采用量子比特编码染色体,可以使一个量子染色体同时表征多个态的叠加,利用量子逻辑门对叠加态的作用作为进化操作。由于量子计算的内在并行性,使量子进化算法有比传统进化算法更高的搜索效率,在许多领域的应用都获得了成功。 本文进一步扩展了量子进化算法的应用领域,把量子进化算法用于求解可满足性问题,为可满足性问题设计了一种新的矩阵描述法,把问题转换为求最优值的组合优化问题。在同遗传算法和二进制粒子群算法比较实验中,量子进化算法显示出了更好的性能,可以作为一种新的求解可满足性问题的不确定性算法。本文还将量子进化算法和传统进化算法结合,提出了量子组合优化算法。算法的种群分为量子种群和传统进化种群,在整个计算过程中这两个种群协同进化,使算法同时具有种群多样性好和收敛速度快的优点。在对所提算法有效性的测试中,量子组合优化算法无论对背包问题还是函数优化问题,都取得了较好的效果。模拟试验结果表明,量子组合优化算法求解组合优化问题是有效的和可行的。