Abstract: 0-1 knapsack problem is a classic NP-hard problem. For the 0-1 knapsack problem, a combined parallel search algorithm（E-GA） is proposed. The population is generated by Genetic Algorithm（GA） and Estimation of Distribution Algorithm（EDA） together. The population proportion caused by two algorithms is changed dynamically, which  combines the global statical information and location information and overcomes the shortcoming of GA and EDA. The algorithm is applied to three widely used knapsack samples, and the results show that proposed E-GA algorithm has better search ability and convergence speed than the other algorithms.

Key words: Genetic Algorithm（GA）, Estimation of Distribution Algorithm（EDA）, parallel search, 0-1 knapsack problem

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

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