基于量子遗传算法的0-1背包问题研究答辩-PPT2

1、基于量子遗传算法的0-1背包问题研究作者： 牟旷林班级 自动化093学号： 200910401346指导教师： 郭宁论文工作 在整个毕业设计论文的撰写过程中，我主要做了以下的工作：n 问题描述n 算法描述n 实验测试与结果分析n GUI界面设计n 总结与展望0-1背包问题 0-1背包问题其实是一个组合优化问题。组合优化问题通常可以这样描述，假设存在一个由所有状态解空间 ， 为状态 对应的目标函数值，根据目标函数寻找状态为 的最优解。 而在许多实际问题中存在着大量在有限资源条件下求解最优选择的问题，所以，研究组合优化问题也有着很大的实际意义。所以，我选择典型的组合优化问题：0-1背包问题作为我的

2、毕业设计课题。 0-1背包问题大体上可以这样描述：存在一个固定容量的背包，以及具有相应价值量的固定数量的物品，很显然，我们的目的就是如何在不超过背包容量下选择物品能够达到最大价值。12 ,.,nS SS ()iC SiSkS0-1背包问题数学描述121max( ,.,)1,2,.,nnjjjf x xxp xjn1. .1,2,., ;0,1njjjjstxC jnx 是背包中各物品的价值， 是要放入背包中物品的体积， 是背包的容积， 是决策函数。 jpjC()fx基于量子遗传算法求解0-1背包问题 遗传算法是一种很基本的进化算法，即模拟生物的选择进化来进行种群的寻优。量子遗传算法则是量子计算

3、和遗传算法的结合，它将遗传中的进化过程用量子逻辑门取而代之，目的是为了发挥量子计算的并行特性来提高算法的寻优效率。 在本篇论文中，我使用的是量子遗传算法来进行0-1背包问题的求解。量子遗传算法流程量子旋转门的数学描述cossincoscos()sincossinsin()RcossinsincosG 通过对量子比特的相位旋转 之后得到新的量子位，实现种群的更新操作。 量子旋转门选择策略 ， 分别代表旋转方向和旋转角度，旋转角。该策略是将个体当前的测量值的适应度 与该个体当前的目标值的适应度 进行比较，通过两个值的比较进行坐标平面角度的旋转使两个值进行靠近。 (,)iis i( )if x( )

4、if b算例1参数设置 其中，value表示物品的价值，weight表示物品的重量，C表示背包的最大容量。并且，在接下来的算法测试中，比较两个量子旋转角0.01pi和0.005pi的结果进行分析测试算例120次循环结果仿真图进化曲线图结果数据 旋转角为0.01pi时的20次循环结果 旋转角为0.005pi时的20次循环结果02468101214161820285029002950300030503100315020次 循 环 结 果循 环 次 数每次循环的适应度最 优 值最 差 值平 均 值024681012141618202800285029002950300030503100315020次

5、 循 环 结 果循 环 次 数每次循环的适应度最 优 值最 差 值平 均 值0501001502002503003504004505002000220024002600280030003200进 化 曲 线进 化 代 数适应度最 优 值最 差 值平 均 值0501001502002503003504004505002000220024002600280030003200进 化 曲 线进 化 代 数适应度最 优 值最 差 值平 均 值 旋转角为0.01pi时的进化曲线 旋转角为0.005pi时的进化曲线算例2参数设置 在这一个算例中，Value表示物品价值，weight表示物品重量，并且两者都是

6、不确定的。在公式中设物品价值为Pi，物品重量为Wi，由（1,10）的随机数产生,背包容量为c。同上一个算例一样，同样比较两个量子旋转角0.01pi和0.005pi的结果进行分析。测试算例250个物品结果仿真图结果数据1 旋转角为0.01pi时的20次循环结果 旋转角为0.005pi时的20次循环结果0246810121416182029229429629830030230430630831031220次 循 环 结 果循 环 次 数每次循环的适应度最 优 值最 差 值平 均 值0246810121416182028529029530030531031520次 循 环 结 果循 环 次 数每次循

7、环的适应度最 优 值最 差 值平 均 值100个物品结果仿真图结果数据2150个物品结果仿真图结果数据3200个物品结果仿真图结果数据4 旋转角为0.01pi时的20次循环结果 旋转角为0.005pi时的20次循环结果0246810121416182084085086087088089090020次 循 环 结 果循 环 次 数每次循环的适应度最 优 值最 差 值平 均 值0246810121416182089590090591091592020次 循 环 结 果循 环 次 数每次循环的适应度最 优 值最 差 值平 均 值024681012141618201195120012051210121

8、5122012251230123520次 循 环 结 果循 环 次 数每次循环的适应度 最 优 值最 差 值平 均 值02468101214161820117011801190120012101220123020次 循 环 结 果循 环 次 数每次循环的适应度 最 大 值最 差 值平 均 值 旋转角为0.01pi时的20次循环结果 旋转角为0.005pi时的20次循环结果 旋转角为0.01pi时的20次循环结果 旋转角为0.005pi时的20次循环结果0246810121416182060060260460660861061261461661862020次 循 环 结 果循 环 次 数每次循环

9、的适应度最 优 值最 差 值平 均 值0246810121416182058559059560060561061562062520次 循 环 结 果循 环 次 数每次循环的适应度最 优 值最 差 值平 均 值GUI界面总结与展望n设置了两个常用了量子旋转角 0.01pi 和 0.005pi 并且通过结果比较分析，发现在旋转角为 0.005pi时，仿真结果的稳定性，命中最优解和改进最大值方面相对于前者都更为优秀。而且在第二个测试算例中，当旋转角为0.005pi 时，只要物品数量足够大，则0-1背包问题的解在最大值，平均值和最差值上的表现都更为优秀。n 通过0-1背包的量子遗传算法的不断修改和设计，最终得到了比较令人满意的结果。但是，在进行论文写作时，也发现了设计中存在的不足，那就是加入交叉或者变异后结果没有改善，甚至有倒退。并且，运行时间相较于其他量子遗传算法要长得多。 因此，我认为可以从以下几个方面进行改进：n单独在量子遗传算法中加入交叉或者变异操作，而不是同