严雅榕, 项华春, 聂飞, 李京峰. 求解0-1背包问题的量子狼群算法[J]. 微电子学与计算机, 2018, 35(7): 1-5, 12.
引用本文: 严雅榕, 项华春, 聂飞, 李京峰. 求解0-1背包问题的量子狼群算法[J]. 微电子学与计算机, 2018, 35(7): 1-5, 12.
YAN Ya-rong, XIANG Hua-chun, NIE Fei, LI Jing-feng. A Quantum Wolf Pack Algorithm for Solving 0-1 Knapsack Problem[J]. Microelectronics & Computer, 2018, 35(7): 1-5, 12.
Citation: YAN Ya-rong, XIANG Hua-chun, NIE Fei, LI Jing-feng. A Quantum Wolf Pack Algorithm for Solving 0-1 Knapsack Problem[J]. Microelectronics & Computer, 2018, 35(7): 1-5, 12.

求解0-1背包问题的量子狼群算法

A Quantum Wolf Pack Algorithm for Solving 0-1 Knapsack Problem

  • 摘要: 针对0-1背包问题, 在基本狼群算法的基础上, 提出了量子狼群算法.借鉴量子编码方式, 定义了种群中粒子的概率位置和准确位置, 通过量子旋转门控制人工狼概率位置向全局最好位置逼近, 然后以量子塌缩实现了概率位置向准确位置的映射, 兼顾了算法的导向性与随机性.选取了8个经典0-1背包问题与3个高维背包问题进行了测试, 并与其他算法进行比较, 实验结果表明, 量子狼群算法能够有效搜索全局最优解, 特别是在高维背包问题中具有较好性能.

     

    Abstract: A quantum wolf pack algorithm is proposed to solve 0-1knapsack 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 are 8 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.

     

/

返回文章
返回