Angle modulation differential evolution with dual population for high dimension 0-1 knapsack problem

doi:10.3778/j.issn.1002-8331.2010.24.014

Computer Engineering and Applications ›› 2010, Vol. 46 ›› Issue (24): 45-47.DOI: 10.3778/j.issn.1002-8331.2010.24.014

• 研究、探讨 • Previous Articles Next Articles

Angle modulation differential evolution with dual population for high dimension 0-1 knapsack problem

DENG Chang-shou^1，2

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

Received:2009-12-08 Revised:2010-06-10 Online:2010-08-21 Published:2010-08-21
Contact: DENG Chang-shou

高维0-1背包问题的双种群角度调制DE算法

邓长寿^1，2

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

通讯作者: 邓长寿

Abstract

Abstract: A novel differential evolution algorithm with dual population is proposed to solve the zero-one knapsack problems with high dimension.In the new algorithm，two populations are used during the evolution，with one float coding population and the other binary coding population.The angle modulation in the field of communication engineering is imported to generate high dimensional binary population with the low dimensional float coding population.In this way，the optimization problem with high dimension can be transformed into the low dimension space.Additionally，a new discarding operator is defined to fix up the infeasible solution.The results of two numerical experiments with different size show it is an effective way for the high dimension zero-one knapsack problems.

Key words: high dimension zero-one knapsack problems, differential evolution algorithm, dual population, angle modulation

摘要： 针对高维0-1背包问题，提出一种双种群新型DE算法。该算法采用双种群编码机制，其中一个为低维的实数编码种群，另一个为高维的二进制编码种群。借鉴通信领域的角度调制原理，通过低维种群中的个体，生成高维种群个体，实现将高维优化问题转换到低维空间进行优化求解。此外，新定义丢弃算子对演化过程中的不可行解实时进行修正。仿真实验结果表明了该算法求解高维0-1背包问题的有效性。

关键词: 高维0-1背包问题, 差异演化算法, 双种群, 角度调制

CLC Number:

TP18

DENG Chang-shou^1，2. Angle modulation differential evolution with dual population for high dimension 0-1 knapsack problem[J]. Computer Engineering and Applications, 2010, 46(24): 45-47.

邓长寿^1，2. 高维0-1背包问题的双种群角度调制DE算法[J]. 计算机工程与应用, 2010, 46(24): 45-47.

[1]	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.
[2]	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.
[3]	SHEN Xiaoning, SUN Yi, XUE Yunyong. Differential evolution algorithm for many-objective using relaxed dominance relation [J]. Computer Engineering and Applications, 2018, 54(18): 161-167.
[4]	LIU Libin1，2, LONG Guangqing1，2, SHANGGUAN Zhenping1. Differential evolution and rational spectral methods for singularly perturbed problems [J]. Computer Engineering and Applications, 2018, 54(17): 225-230.
[5]	LOU Gaoxiang, CAI Zongyan, LIU Qingtao. Application of new hybrid algorithm in mixed model assembly scheduling [J]. Computer Engineering and Applications, 2018, 54(16): 254-259.
[6]	SUN Jiazheng, GUO Jun. Improved dual population genetic algorithm for rectangle packing [J]. Computer Engineering and Applications, 2018, 54(15): 139-146.
[7]	QIAN Wuwen, CHAI Junrui, ZHANG Ziying, TAN Ran. Adaptive differential evolution algorithm based on reflective mutation strategy [J]. Computer Engineering and Applications, 2018, 54(15): 161-168.
[8]	ZHANG Jinhua1, SONG Laisuo2, ZHANG Yuanhua3, LI Fuchang4. Dynamic differential evolution algorithm with weighted mutation strategy [J]. Computer Engineering and Applications, 2017, 53(4): 156-162.
[9]	LI Xun1, LIU Li2, HONG Liang1, WANG Xiaohua1. Localization method and implementation for indoor robot based on RFID [J]. Computer Engineering and Applications, 2017, 53(16): 230-236.
[10]	LIU Libin1, KONG Xiangsheng2, OUYANG Aijia3，4. Differential evolution algorithm to solve singularly perturbed problem with two small parameters [J]. Computer Engineering and Applications, 2016, 52(4): 19-23.
[11]	WANG Zhenchao. Integration of DEA and Taguchi method of multi-task scheduling scheme in cloud computing [J]. Computer Engineering and Applications, 2015, 51(2): 140-145.
[12]	LIANG Yujie1, XU Feng2. Adaptive hybrid multi-objective estimation of distribution evolutionary algorithm [J]. Computer Engineering and Applications, 2014, 50(5): 46-50.
[13]	YIN Yuping1, LIU Wanjun2. Fault diagnosis method of wind turbine gearbox based on Ant Colony and Differential Evolution algorithm [J]. Computer Engineering and Applications, 2014, 50(13): 10-14.
[14]	LI Ming, CAO Dexin. Hybrid optimization algorithm of Cuckoo Search and DE [J]. Computer Engineering and Applications, 2013, 49(9): 57-60.
[15]	LI Kewei1, LI Xiaoqian1, XU Zhengxi1, LEI Gang2. Optimization design of electromagnetic devices based on combination of compactly supported radial basis function and differential evolution algorithm [J]. Computer Engineering and Applications, 2013, 49(22): 219-222.

Angle modulation differential evolution with dual population for high dimension 0-1 knapsack problem

高维0-1背包问题的双种群角度调制DE算法

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics