求解0/1背包问题的离散差分进化算法  被引量:15

Discrete Differential Evolution Algorithm for Solving 0/1 Knapsack Problem

在线阅读下载全文

作  者:苗世清[1] 高岳林[2] 

机构地区:[1]宁夏大学数学计算机学院,宁夏银川750021 [2]北方民族大学信息与系统科学研究所,宁夏银川750021

出  处:《小型微型计算机系统》2009年第9期1828-1830,共3页Journal of Chinese Computer Systems

基  金:国家社会科学基金项目(07XJY038)资助;国家教育部社科规划项目(06JA630056)资助;国家博士后基金项目(20060401001)资助;宁夏自然科学基金项目(NZ0848)资助

摘  要:0/1背包问题是实际中经常遇到的一类经典NP难组合优化问题.针对0/1背包问题,提出一种融合贪婪变换的离散差分进化算法.该算法中通过模2运算来实现变异操作;为了满足约束上限,融合了贪婪变换;为了防止早熟,采用了在进化若干代后重新初始化种群的策略.经数值实验表明,该算法在求解0/1背包问题时是可行的,有效的,比单纯的贪婪算法,融合贪婪变换的粒子群优化算法及融合贪婪变换的遗传算法更加稳健,良好.The 0/1 knapsack problem is a classic NP-hard problem in the combinational optimization. It is often encountered in practice. This paper presents a discrete differential evolution algorithm with greedy transform. In the algorithm, the mold 2 operation is adopted to improve the variation operation, and using the greedy transformation satisfies the stipulation upper limit, as well as retrieve the population to prevent from precocious. It is show by the numerical test that the proposed algorithm is better than greedy algorithm, and particle swarm optffnization with greedy transform , as well as genetic algorithm with greedy transform for solving 0/1 knapsack problem.

关 键 词:0/1背包问题 差分进化算法 遗传算法 粒子群优化 贪婪变换 

分 类 号:TP301.6[自动化与计算机技术—计算机系统结构]

 

参考文献:

正在载入数据...

 

二级参考文献:

正在载入数据...

 

耦合文献:

正在载入数据...

 

引证文献:

正在载入数据...

 

二级引证文献:

正在载入数据...

 

同被引文献:

正在载入数据...

 

相关期刊文献:

正在载入数据...

相关的主题
相关的作者对象
相关的机构对象