Improved differential evolution algorithm for knapsack problem

doi:10.3778/j.issn.1002-8331.2008.32.004

Computer Engineering and Applications ›› 2008, Vol. 44 ›› Issue (32): 12-14.DOI: 10.3778/j.issn.1002-8331.2008.32.004

• 博士论坛 • Previous Articles Next Articles

Improved differential evolution algorithm for knapsack problem

DENG Chang-shou^1,2,LIANG Chang-yong¹

1.Institute of Computer Network System，Hefei University of Technology，Hefei 230009，China
2.School of Information Science and Technology，Jiujiang University，Jiujiang，Jiangxi 332005，China

Received:2008-07-29 Revised:2008-08-18 Online:2008-11-11 Published:2008-11-11
Contact: DENG Chang-shou

求解背包问题的改进差异演化算法

邓长寿^1,2,梁昌勇¹

1.合肥工业大学计算机网络系统研究所，合肥 230009
2.九江学院信息科学与技术学院，江西九江 332005

通讯作者: 邓长寿

Abstract

Abstract: An improved differential evolution algorithm was proposed to solve the classical knapsack problem.The selection operation in original differential evolution was adapted to deal with constraints directly.Using a new range encoding mapping，the differential evolution algorithm can be used to deal with discrete optimization problem.The simulation results of the improved differential evolution algorithm show，compared with other evolution algorithm，the improved differential evolution is effective in solving 0-1 Knapsack Problems.

Key words: knapsack problem, differential evolution, range encoding mapping, selection operation

摘要： 提出一种求解0-1背包问题的改进差异演化算法。首先对差异演化算法的选择操作进行修改，得到的改进差异演化算法可以直接有效地处理约束优化问题。其次，利用一种新的区间编码映射机制，将差异演化算法扩展到求解离散领域优化问题。仿真实验结果表明，与其他进化算法相比，改进差异演化算法求解经典背包问题时，求解精度高，收敛速度快，是求解经典背包问题的一种高效算法。

关键词: 背包问题, 差异演化, 区间编码映射, 选择操作

DENG Chang-shou^1,2,LIANG Chang-yong¹. Improved differential evolution algorithm for knapsack problem[J]. Computer Engineering and Applications, 2008, 44(32): 12-14.

邓长寿^1,2,梁昌勇¹. 求解背包问题的改进差异演化算法[J]. 计算机工程与应用, 2008, 44(32): 12-14.

[1]	ZOU Jie, LI Jun. Multi-strategy Covariance Matrix Learning Differential Evolution Algorithm [J]. Computer Engineering and Applications, 2021, 57(7): 78-87.
[2]	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.
[3]	QIAN Zhengyuan, ZENG Guosun. Differential Evolution Algorithm Guided by Elite Island Population [J]. Computer Engineering and Applications, 2021, 57(20): 73-81.
[4]	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.
[5]	CUI Caixia, BI Chaochao, FAN Qinqin. Self-Adaptive MODE Based on Hidden Markov Chain and Application [J]. Computer Engineering and Applications, 2021, 57(14): 83-94.
[6]	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.
[7]	LI Rong, HE Xingshi, YANG Xinshe. Application of Moth Algorithm Based on Differential Evolution in Power Dispatch [J]. Computer Engineering and Applications, 2021, 57(13): 258-268.
[8]	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.
[9]	SHEN Xin, ZOU Dexuan, ZHANG Qiang. Adaptive Differential Evolution Algorithm Using Double Mutation Strategies and Its Application [J]. Computer Engineering and Applications, 2020, 56(4): 146-157.
[10]	ZHANG Menglin, JIANG Feibo, DONG Li, GAO Ying. Joint Optimization of Intelligent UAV Trajectory and Task Offload [J]. Computer Engineering and Applications, 2020, 56(21): 38-46.
[11]	WANG Hao, LI Jun, ZHOU Rong. Adaptive Combine and Split Multi-population Differential Evolution Algorithm [J]. Computer Engineering and Applications, 2020, 56(15): 162-171.
[12]	WANG Yadong, SHI Quan, YOU Zhifeng, SONG Weixing. Differential Evolutionary Quasi-Oppositional Multi-objective Ant Lion Optimizer [J]. Computer Engineering and Applications, 2020, 56(13): 156-163.
[13]	GENG Huantong, ZHOU Lifa, DING Yangyang, ZHOU Shansheng. Improved MOEA/D Algorithm Based on New Differential Evolution Model [J]. Computer Engineering and Applications, 2019, 55(8): 138-146.
[14]	CHI Zongzheng, DONG Shaozheng, GUO Tong, REN Zhilei, ZHOU Kuanjiu, GUO He. Research on Wind Farm Layout Based on Hyper-Heuristic [J]. Computer Engineering and Applications, 2019, 55(7): 220-225.
[15]	LIU Xi1, MAO Li1, YANG Hong2. Fireworks Optimization Algorithm Based on Leading Differential Evolution Chemotaxis Operator [J]. Computer Engineering and Applications, 2019, 55(3): 140-146.

Improved differential evolution algorithm for knapsack problem

求解背包问题的改进差异演化算法

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics