[1]钟培华,吴志远,胡建根,等.基于区域分割的差分进化算法求解0-1背包问题[J].江西师范大学学报(自然科学版),2012,(04):364-369.
　ZHONG Pei-hua,WU Zhi-yuan,HU Jian-gen,et al.The Differential Evolution Algorithm Based on Domain Partition for Solving 0-1 Knapsack Proble[J].Journal of Jiangxi Normal University:Natural Science Edition,2012,(04):364-369.
点击复制

基于区域分割的差分进化算法求解0-1背包问题()
分享到：

《江西师范大学学报》（自然科学版）[ISSN:1006-6977/CN:61-1281/TN]

卷:
期数:
2012年04期
页码:
364-369
栏目:
出版日期:
2012-08-01

文章信息/Info

Title:
The Differential Evolution Algorithm Based on Domain Partition for Solving 0-1 Knapsack Proble
作者:
钟培华;吴志远;胡建根;朱丽
江西农业大学理学院, 江西 南昌 330045
Author(s):
ZHONG Pei-hua;  WU Zhi-yuan;  HU Jian-gen;  ZHU Li
关键词:
背包问题; 差分进化算法; 分割
Keywords:
knapsack problem;  differential evolution;  partition
分类号:
TP18
文献标志码:
A
摘要:
为了更有效地求解0-1背包问题,提出了基于区域分割的差分进化算法(PDE).为保证变异算子的封闭性,对传统差分进化算法(DE)的变异算子进行了修改.引入区域分割算法以后,解空间中一些没有希望的点被移除,缩小了最优解的搜索范围,增加了找到最优解的概率.将区域分割和贪婪算法相结合,用搜索到的最好解替换了种群中目标函数值最差的个体,保证了种群的多样性.数值实验表明:该算法比文献中的DE算法更稳健,全局搜索能力更强,能以更大的概率找到背包问题的最优解.
Abstract:
In order to solve the 0-1 knapsack problems more effectively, a new differential evolution algorithm based on domain partition method is proposed. The mutation operator of traditional differential evolution algorithm (DE) is modified to guarantee the closure of mutation operation. With the domain partition method introduced in and some hopeless points removed off, the searching field of the optimal solution is reduced. Accordingly, the probability of finding the optimal solution is improved. To ensure the diversity of population, the solution with the least object function value is replaced by the best feasible solution found by the domain partition method combined with greedy method. Numerical experiments show that the new algorithm is of more robustness, of better global searching ability, and of greater probability to find the optimal solution of knapsack problem than those algorithms mentioned in the literatures.

参考文献/References:

[1] 邓长寿, 赵秉岩, 梁昌勇. 基于混合编码的差异演化算法解0-1背包问题[J]. 计算机应用研究, 2010, 27(6): 2031 2033.
[2] 蔡鸿英, 郝志峰, 王志刚, 等. 解0-1背包问题的二进制差异演化算法[J]. 计算机工程与设计, 2009, 30(7): 1716 1721.
[3] 苗世清, 高岳林. 求解0/1背包问题的离散差分进化算法[J]. 小微型计算机系统, 2009, 30(9): 1828-1830.
[4] 赵新超, 杨婷婷. 求背包问题的更贪心粒子群算法[J]. 计算机工程与应用, 2009, 45(36): 32 34.
[5] 李康顺, 贾玉珍, 张文生. 一种基于模式替代的遗传算法解0/1背包问题[J]. 计算机应用研究, 2009, 26(2): 470 471.
[6] 樊小毛, 马良. 0 1背包问题的蜂群优化算法[J]. 数学的实践与认识, 2010, 40(6): 155 160.
[7] Stom R, Price K. Differential evolution: a simple and efficient adaptive scheme for global optimization over continuous space [R]. Berkeley: University of California, 2006.
[8] Ali M M, Kajee-Bagdadi Z. A local exploration-based differential evolution algorithm for constrained global optimization [J]. Applied Mathematics and Computation, 2009, 208(1): 31-48.
[9] Mallipeddi R, Suganthan P N, Ensemble of constraint handling techniques [J]. IEEE Trans on Evolutionary Computation, 2010, 10(4): 311-338.
[10] 刘若辰, 焦李成, 雷峰, 等. 一种新的差分进化约束优化算法 [J]. 西安电子科技大学学报: 自然科学版, 2011, 38(1): 47-53.
[11] Ruan Ning, Sun Xiaoling. An exact Algorithm for cost minimization in series reliability systems with multiple component choices[J]. Applied Mathematics and Computation, 2006,181(1): 732 741.

更新日期/Last Update: 1900-01-01