基于量子遗传算法背包问题研究答辩(1)

1、基于量子遗传算法的0-1背包问题研究n 问题描述n 算法描述n 实验测试与结果分析n GUI界面设计n 总结与展望12 ,.,nS SS ()iC SiSkS0-1背包问题数学描述121max( ,.,)1,2,.,nnjjjf x xxp xjn1. .1,2,., ;0,1njjjjstxC jnx 是背包中各物品的价值， 是要放入背包中物品的体积， 是背包的容积， 是决策函数。 jpjC()fx量子遗传算法流程量子旋转门的数学描述cossincoscos()sincossinsin()RcossinsincosG 通过对量子比特的相位旋转 之后得到新的量子位，实现种群的更新操作。 量子旋

2、转门选择策略 ， 分别代表旋转方向和旋转角度，旋转角。该策略是将个体当前的测量值的适应度 与该个体当前的目标值的适应度 进行比较，通过两个值的比较进行坐标平面角度的旋转使两个值进行靠近。 (,)iis i( )if x( )if b 其中，value表示物品的价值，weight表示物品的重量，C表示背包的最大容量。并且，在接下来的算法测试中，比较两个量子旋转角0.01pi和0.005pi的结果进行分析测试算例120次循环结果仿真图进化曲线图结果数据 旋转角为0.01pi时的20次循环结果 旋转角为0.005pi时的20次循环结果024681012141618202850290029503000

3、30503100315020次 循 环 结 果循 环 次 数每次循环的适应度最 优 值最 差 值平 均 值024681012141618202800285029002950300030503100315020次 循 环 结 果循 环 次 数每次循环的适应度最 优 值最 差 值平 均 值0501001502002503003504004505002000220024002600280030003200进 化 曲 线进 化 代 数适应度最 优 值最 差 值平 均 值0501001502002503003504004505002000220024002600280030003200进 化 曲 线进

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

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

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

7、次循环结果 旋转角为0.005pi时的20次循环结果0246810121416182060060260460660861061261461661862020次 循 环 结 果循 环 次 数每次循环的适应度最 优 值最 差 值平 均 值0246810121416182058559059560060561061562062520次 循 环 结 果循 环 次 数每次循环的适应度最 优 值最 差 值平 均 值GUI界面总结与展望n设置了两个常用了量子旋转角 0.01pi 和 0.005pi 并且通过结果比较分析，发现在旋转角为 0.005pi时，仿真结果的稳定性，命中最优解和改进最大值方面相对于前者都更为优秀。而且在第二个测试算例中，当旋转角为0.005pi 时，只要物品数量足够大，则0-1背包问题的解在最大值，平均值和最差值上的表现都更为优秀。n 通过0-1背包的量子遗传算法的不断修改和设计，最终得到了比