求解0-1背包问题的量子狼群算法
|
摘要
针对0-1背包问题,在基本狼群算法的基础上,提出了量子狼群算法.借鉴量子编码方式,定义了种群中粒子的概率位置和准确位置,通过量子旋转门控制人工狼概率位置向全局最好位置逼近,然后以量子塌缩实现了概率位置向准确位置的映射,兼顾了算法的导向性与随机性.选取了8个经典0-1背包问题与3个高维背包问题进行了测试,并与其他算法进行比较,实验结果表明,量子狼群算法能够有效搜索全局最优解,特别是在高维背包问题中具有较好性能.
A quantum wolf pack algorithm is proposed to solve 0-1 knapsack problems.Defining probability positions and accurate positions of particles in population refer to quantum encoding.Quantum rotation is used to orient probability positions of wolves to the global optimal position,and then completing the mapping from probability position to accurate position by quantum collapse,these operators reconcile the orientation and randomness.There are8 classical and 3 high-dimensional knapsack problems employed to test the proposed algorithm,and then compared the performance of this algorithm with other algorithm.The statistical results demonstrate the effectiveness and global search capability on knapsack problems especially for high level cases.
A quantum wolf pack algorithm is proposed to solve 0-1 knapsack problems.Defining probability positions and accurate positions of particles in population refer to quantum encoding.Quantum rotation is used to orient probability positions of wolves to the global optimal position,and then completing the mapping from probability position to accurate position by quantum collapse,these operators reconcile the orientation and randomness.There are8 classical and 3 high-dimensional knapsack problems employed to test the proposed algorithm,and then compared the performance of this algorithm with other algorithm.The statistical results demonstrate the effectiveness and global search capability on knapsack problems especially for high level cases.
引文
[1]Kellerer H,Pferschy U,Pisinger D.Knapsack problems[M].Berlin:SpringerVerlag,2004.
[2]王熙照,贺毅朝.求解背包问题的演化算法[J].软件学报,2017,27(1):1-16.
[3]Zou D X,Gao L Q,Wu J H,et al.Solving 0-1knapsack problem by a novel global harmony search algorithm[J].Applied Soft Computing,2011,11(2):155-1564.
[4]Chen G L,Wang X F,Zhuang Z Q,et al.Genetic algorithm and its applications[M].Beijing:The posts and Telecommunications Press,2003.1-192.
[5]Poli R,Kennedy J,Blackwell T.Particle swarm optimization[J].Swarm Intelligence,2007,1(1):33-57.[doi:10.1109/ICCN.1995.488968].
[6]Dorigo M,Stutzle T.Ant colony optimization[M].Cambridge:MIT Press,2004:1-103.
[7]Karaboga D,Basturk B.A powerful and efficient algorithm for numerical function optimization:Artificial bee colony(ABC)algorithm[J].Journal of Global Optimization,2007,39(3):459-471.[doi:10.1007/s10898-007-9149-x].
[8]Yang X S,Deb S.Cuckoo search via levy flights[C]//Proceedings of World Congress nature&Biologically Inspired Computing.India,IEEE Publications,2009:210-214.
[9]吴虎胜,张凤鸣,吴庐山.一种新的群体智能算法--狼群算法[J].系统工程与电子技术,2013,34(11):2430-2438.
[10]吴虎胜,张凤鸣,战仁军,等.求解0-1背包问题的二进制狼群算法[J].系统工程与电子技术,2014,35(8):1660-1667.
[11]陈汉武,李科,赵生妹.基于相位匹配的量子行走搜索算法及电路实现[J].物理学报,2015,82(24):29-39.
[12]李国亮.狼群算法的研究与应用[D].江西:东华理工大学,2016.
[13]李娟,方平,周明.一种求解背包问题的混合遗传算法[J].南昌航空工业学院学报,1998,11(3):35-39.
[2]王熙照,贺毅朝.求解背包问题的演化算法[J].软件学报,2017,27(1):1-16.
[3]Zou D X,Gao L Q,Wu J H,et al.Solving 0-1knapsack problem by a novel global harmony search algorithm[J].Applied Soft Computing,2011,11(2):155-1564.
[4]Chen G L,Wang X F,Zhuang Z Q,et al.Genetic algorithm and its applications[M].Beijing:The posts and Telecommunications Press,2003.1-192.
[5]Poli R,Kennedy J,Blackwell T.Particle swarm optimization[J].Swarm Intelligence,2007,1(1):33-57.[doi:10.1109/ICCN.1995.488968].
[6]Dorigo M,Stutzle T.Ant colony optimization[M].Cambridge:MIT Press,2004:1-103.
[7]Karaboga D,Basturk B.A powerful and efficient algorithm for numerical function optimization:Artificial bee colony(ABC)algorithm[J].Journal of Global Optimization,2007,39(3):459-471.[doi:10.1007/s10898-007-9149-x].
[8]Yang X S,Deb S.Cuckoo search via levy flights[C]//Proceedings of World Congress nature&Biologically Inspired Computing.India,IEEE Publications,2009:210-214.
[9]吴虎胜,张凤鸣,吴庐山.一种新的群体智能算法--狼群算法[J].系统工程与电子技术,2013,34(11):2430-2438.
[10]吴虎胜,张凤鸣,战仁军,等.求解0-1背包问题的二进制狼群算法[J].系统工程与电子技术,2014,35(8):1660-1667.
[11]陈汉武,李科,赵生妹.基于相位匹配的量子行走搜索算法及电路实现[J].物理学报,2015,82(24):29-39.
[12]李国亮.狼群算法的研究与应用[D].江西:东华理工大学,2016.
[13]李娟,方平,周明.一种求解背包问题的混合遗传算法[J].南昌航空工业学院学报,1998,11(3):35-39.