Hybrid particle swarm optimization algorithm for solving knapsack problem

Computer Engineering and Applications ›› 2012, Vol. 48 ›› Issue (1): 44-46.

• 研究、探讨 • Previous Articles Next Articles

Hybrid particle swarm optimization algorithm for solving knapsack problem

WANG Xiaohua1，2, MU Aiqin2, LIU Jinbo2

1.School of Computer Science and Technology, China University of Mining and Technology, Xuzhou, Jiangsu 221008, China
2.Department of Fundamental Courses, Xuzhou Air Force College, Xuzhou, Jiangsu 221000, China

Received:1900-01-01 Revised:1900-01-01 Online:2012-01-01 Published:2012-01-01

求解背包问题的混合粒子群优化算法

王晓华1，2，沐爱勤2，刘金波2

1.中国矿业大学计算机学院，江苏徐州 221008
2.徐州空军学院基础部，江苏徐州 221000

Abstract

Abstract: A new genetic idea that offspring’s gene is decided by its parent’s, rather than produced by a simple cross is proposed. According to this idea, two methods of producing offspring with genetic probability are produced and they are combined with the particle swarm optimization respectively. The two hybrid particle swarm optimizations are applied to solving knapsack problem, and their performances are compared by normal numerical experiments. The validity of two hybrid algorithms is verified and the impacts of mutation probability on the algorithms are analyzed.

Key words: particle swarm optimization, knapsack problem, genetic probability

摘要： 提出一种新的遗传思想：父代的基因决定子代继承某一基因的概率，而不是由单纯的交叉产生子代。根据此思想，提出两种利用遗传概率产生子代的方法，并将它们分别与粒子群优化算法相结合得到两种求解背包问题的混合粒子群优化算法。通过数值实验说明了同样的算法采用遗传策略要比交叉策略寻优性更强，分析了变异概率对算法的影响。

关键词: 粒子群优化算法, 背包问题, 遗传概率

WANG Xiaohua1，2, MU Aiqin2, LIU Jinbo2. Hybrid particle swarm optimization algorithm for solving knapsack problem[J]. Computer Engineering and Applications, 2012, 48(1): 44-46.

王晓华1，2，沐爱勤2，刘金波2. 求解背包问题的混合粒子群优化算法[J]. 计算机工程与应用, 2012, 48(1): 44-46.

[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]	LI Jingxing, YANG Youlong. Feature Selection of Markov Blanket for High Dimensional Data [J]. Computer Engineering and Applications, 2021, 57(6): 58-66.
[3]	ZHU Jiaying, GAO Maoting. AUV Path Planning Based on Particle Swarm Optimization and Improved Ant Colony Optimization [J]. Computer Engineering and Applications, 2021, 57(6): 267-273.
[4]	HU Xiaomin, WANG Mingfeng, ZHANG Shourong, LI Min. New Differential Evolution with Particle Swarm Optimization Algorithm for Text Clustering [J]. Computer Engineering and Applications, 2021, 57(4): 61-67.
[5]	WANG Jiayue, SHI Li. Research on Path Optimization and Charging Strategy of Electric Refrigerated Vehicle Considering Cost of Battery Capacity Degradation [J]. Computer Engineering and Applications, 2021, 57(24): 283-289.
[6]	CHEN Wanfen, WANG Yujia, LIN Weixing. Heterogeneous Ensemble Surrogate Assisted Multi-objective Particle Swarm Optimization Algorithm [J]. Computer Engineering and Applications, 2021, 57(23): 71-80.
[7]	DU Shouxin, WU Tao. Study on Application of Double Population Hybrid Genetic Algorithm in Cut Order Planning [J]. Computer Engineering and Applications, 2021, 57(22): 182-189.
[8]	LIN Weixing, WANG Yujia, CHEN Wanfen, LIANG Haina. High-Dimensional Data Feature Selection Algorithm Based on Multifactor Particle Swarm Optimization [J]. Computer Engineering and Applications, 2021, 57(22): 199-207.
[9]	HAO Xiang, HE Yichao, ZHU Xiaobin, ZHAI Qinglei. Discrete Hybrid Multi-verse Optimization Algorithm for Solving Discounted {0-1} Knapsack Problem [J]. Computer Engineering and Applications, 2021, 57(18): 103-113.
[10]	LI Leixiao, DENG Dan, LI Jie, WANG Yongsheng. All-to-All Comparison Computing Data Distribution Strategy Based on Particle Swarm Optimization [J]. Computer Engineering and Applications, 2021, 57(15): 109-117.
[11]	ZHANG Ming, DENG Wenhan, LIN Juan, ZHONG Yiwen. Modified Ant Colony Optimization Algorithm for Discounted {0-1} Knapsack Problem [J]. Computer Engineering and Applications, 2021, 57(13): 85-95.
[12]	YU Guolong, ZHAO Yong, WU Lian, CUI Zhongwei. Improvement of QPSO Algorithm and Its Application in DBN Parameter Optimization [J]. Computer Engineering and Applications, 2021, 57(10): 154-162.
[13]	LIAO Weilin, CHENG Shan, SHANG Dongdong, WEI Zhaobin. Particle Swarm Optimization Algorithm Integrated with Multiple-Strategies [J]. Computer Engineering and Applications, 2021, 57(1): 69-76.
[14]	ZHOU Rong, LI Jun, WANG Hao. Reverse Learning Particle Swarm Optimization Based on Grey Wolf Optimization [J]. Computer Engineering and Applications, 2020, 56(7): 48-56.
[15]	WU Congcong, HE Yichao, ZHAO Jianli. New Genetic Algorithm for Discounted {0-1} Knapsack Problem [J]. Computer Engineering and Applications, 2020, 56(7): 57-66.

Hybrid particle swarm optimization algorithm for solving knapsack problem

求解背包问题的混合粒子群优化算法

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics