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

YAN Ya-rong; XIANG Hua-chun; NIE Fei; LI Jing-feng

Chinese

您当前的位置：

首页 >

文章列表页 >

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

更新时间：2026-09-04

- A Quantum Wolf Pack Algorithm for Solving 0-1 Knapsack Problem
- Vol. 35, Issue 7, Pages: 1-5(2018)
- 作者机构：
  
  空军工程大学机构装备管理与安全工程学院,陕西,西安,710051
- 作者简介：
- 基金信息：
- DOI：
  CLC：
- Published：2018
- 稿件说明：
移动端阅览
严雅榕, 项华春, 聂飞, 李京峰. 求解0-1背包问题的量子狼群算法[J]. 微电子学与计算机, 2018, 35(7): 1-5, 12.

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

YAN Ya-rong, XIANG Hua-chun, NIE Fei, et al. A Quantum Wolf Pack Algorithm for Solving 0-1 Knapsack Problem[J]. 2018, 35(7): 1-5. DOI：

摘要

针对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.

关键词

Keywords

references

Cambridge Dorigo M, Stutzle T. Ant colony optimization[M]. Cambridge: MIT Press, 2004:1-103. DOI: 1

吴虎胜, 张凤鸣, 吴庐山.一种新的群体智能算法-狼群算法[J].系统工程与电子技术, 2013, 34(11):2430-2438. DOI: 2430

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].

李国亮.狼群算法的研究与应用[D].江西: 东华理工大学, 2016.

Berlin Kellerer H, Pferschy U, Pisinger D. Knapsack problems[M]. Berlin: SpringerVerlag, 2004.

Poli R, Kennedy J, Blackwell T. Particle swarm optimization[J]. Swarm Intelligence, 2007, 1(1): 33-57.[doi:10.1109/ICCN.1995.488968].

Beijing 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. DOI: 1

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.

Zou D X, Gao L Q, Wu J H, et al. Solving 0-1 knapsack problem by a novel global harmony search algorithm[J]. Applied Soft Computing, 2011, 11(2):155-1564. DOI: 155

吴虎胜, 张凤鸣, 战仁军, 等.求解0-1背包问题的二进制狼群算法[J].系统工程与电子技术, 2014, 35(8):1660-1667. DOI: 1660

李娟, 方平, 周明.一种求解背包问题的混合遗传算法[J].南昌航空工业学院学报, 1998, 11(3):35-39. DOI: 35

陈汉武, 李科, 赵生妹.基于相位匹配的量子行走搜索算法及电路实现[J].物理学报, 2015, 82(24): 29-39. DOI: 29

王熙照, 贺毅朝.求解背包问题的演化算法[J].软件学报, 2017, 27(1):1-16. DOI: 1

Views

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

Monte carlo analysis of V-layout trench SiC neutron detector

High gain stability high temperature operational amplifier based on reverse body bias

Implementation and verification of a dual-chain power gating strategy for low power design

Research on the design of blockchain-based AI-generated content traceability framework

A review of large model development: technological evolution from BERT to Deepseek

Related Author

No data

Related Institution

No data

AI问答

Postal code：100079
Tel：（010）53879206 Email：tmw@bjxintong.com.cn
Technical support is provided by Beijing Founder electronics co., LTD 京ICP备09082226号-64 京公网安备11010602201714号
It is recommended to read the content of this site in Chrome&IE9+. Please switch to extreme mode in browser 360.
Cookies We use cookies to help provide and enhance our service and tailor content. By continuing, you agree to the use of cookies.

⁰