Quantum-inspired ant algorithm for solving 0-1 knapsack problem

Computer Engineering and Applications ›› 2011, Vol. 47 ›› Issue (16): 29-31.

• 研究、探讨 • Previous Articles Next Articles

Quantum-inspired ant algorithm for solving 0-1 knapsack problem

HE Xiaofeng，MA Liang

School of Management，University of Shanghai for Science and Technology，Shanghai 200093，China

Received:1900-01-01 Revised:1900-01-01 Online:2011-06-01 Published:2011-06-01

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

何小锋，马良

上海理工大学管理学院，上海 200093

Abstract

Abstract: 0-1 knapsack problem is a typical NP-hard problem in combinatorial optimization.A quantum-inspired ant colony algorithm for solving the 0-1 knapsack problem is proposed which is based on the combination of ant colony optimization and quantum computing.In the algorithm，the pheromone is expressed by quantum bits，and quantum rotation gates are used to update the ant pheromone.Series of test instances validate the effectiveness of the algorithm.The proposed algorithm can reduce the searching time and has better performance in reaching the global optimum.

Key words: ant colony algorithm, quantum computing, 0-1 knapsack problem

摘要： 0-1背包问题是组合优化中经典的NP难题，在蚁群算法的基础上结合量子计算提出一种求解0-1背包问题的量子蚁群算法。算法采用量子比特表示信息素，用量子旋转门来更新信息素。大量数据实例的比较测试表明，算法可有效提高蚂蚁算法的性能，减少搜索时间，具有更好的全局寻优能力。

关键词: 蚁群算法, 量子计算, 0-1背包问题

HE Xiaofeng，MA Liang. Quantum-inspired ant algorithm for solving 0-1 knapsack problem[J]. Computer Engineering and Applications, 2011, 47(16): 29-31.

何小锋，马良. 求解0-1背包问题的量子蚁群算法[J]. 计算机工程与应用, 2011, 47(16): 29-31.

[1]	SHI Chuntian, ZENG Yanyang, HOU Shouming. Summary of Application of Swarm Intelligence Algorithms in Image Segmentation [J]. Computer Engineering and Applications, 2021, 57(8): 36-47.
[2]	ZHANG Songcan, PU Jiexin, SI Yanna, SUN Lifan. Adaptive Improved Ant Colony Algorithm Based on Population Similarity and Its Application [J]. Computer Engineering and Applications, 2021, 57(8): 70-77.
[3]	HOU Xuan, XUE Fei, CHEN Tao. UAV Target Detection on Quantum Multi-pattern Recognition Optimization Algorithm [J]. Computer Engineering and Applications, 2021, 57(7): 228-236.
[4]	BU Guannan, LIU Jianhua, JIANG Lei, ZHANG Dongyang. Ant Colony Algorithm with Adaptive Grouping [J]. Computer Engineering and Applications, 2021, 57(6): 67-73.
[5]	MA Xianghua, ZHANG Qian. Research on Improved Ant Colony Algorithm in Robots Path Planning [J]. Computer Engineering and Applications, 2021, 57(5): 210-215.
[6]	WANG Xiaoguang, YANG Peibei. Design and Effect Analysis of Digital Transformation of Shipping Logistics Enterprises [J]. Computer Engineering and Applications, 2021, 57(21): 241-247.
[7]	ZHANG Ziran, HUANG Weihua, CHEN Yang, ZHANG Zheng, LI Ziyuan. Improved Ant Colony Path Planning Algorithm Based on Bidirectional Search [J]. Computer Engineering and Applications, 2021, 57(21): 270-277.
[8]	ZHOU Lin, GUO Bing. Design of Improved TR Gate Cascade Quantum Comparator [J]. Computer Engineering and Applications, 2021, 57(19): 112-115.
[9]	LI Erchao, QI Kuankuan. Improved Bidirectional Ant Colony Algorithm Mobile Robot Path Planning [J]. Computer Engineering and Applications, 2021, 57(18): 281-288.
[10]	FU Zhaohui, LIU Changshi. Research on Multi-depot Vehicle Routing Problem Based on Joint Distribution Mode [J]. Computer Engineering and Applications, 2021, 57(16): 291-298.
[11]	ZHANG Suying, GUO Baoliang, CHEN Lingzhi, LIU Huixian. Path Planning of Intelligent Fire Evacuation Map Based on Bidirectional Ant Colony Algorithm [J]. Computer Engineering and Applications, 2021, 57(14): 259-266.
[12]	FU Zhaohui, LIU Changshi. Research on Open Time-Dependent Vehicle Routing Problem of Fresh Food E-commerce Distribution [J]. Computer Engineering and Applications, 2021, 57(1): 271-278.
[13]	ZHANG Songcan, PU Jiexin, SI Yanna, SUN Lifan. Survey on Application of Ant Colony Algorithm in Path Planning of Mobile Robot [J]. Computer Engineering and Applications, 2020, 56(8): 10-19.
[14]	CHEN Xi, GAO Junwei, GUAN Sheng. Path Planning for Wave Glider Based on Artificial Pathfinder Ant [J]. Computer Engineering and Applications, 2020, 56(4): 241-246.
[15]	XU Chuanglai, HU Jiankun, HUANG Youfang. Robust Optimization of Express Delivery Network with Uncertain Demand [J]. Computer Engineering and Applications, 2020, 56(3): 272-278.

Quantum-inspired ant algorithm for solving 0-1 knapsack problem

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

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics