解决0-1背包问题的遗传分布估计算法

摘要：

0-1背包问题是典型的NP难问题，针对0-1背包问题提出分布估计算法（EDA）与遗传算法（GA）相结合的算法（E-GA）。该算法在每一次迭代中由二者共同产生种群，并行搜索，两种方法产生的个体数目动态变化，将EDA的全局搜索与GA的局部搜索能力、EDA的快速收敛性与GA的种群多样性结合，实现优势互补。通过三个背包问题算例进行算法验证，与以往文献相比，结果显示该算法所获最优值优于文献最优值，运行时间短且收敛速度快。

关键词：遗传算法、分布估计算法、并行搜索、0-1背包问题

分类号：TP18(自动化基础理论)

资助基金：国家自然科学基金No.61271143，No.60871080。

在线出版日期：2014-05-24（万方平台首次上网日期，不代表论文的发表时间）

页数：共6页

页码：12-16,31