Abstract: When solving the optimal solutions of 0-1 Knapsack Problems (KPs), the traditional Genetic Algorithm (GA) has insufficient local refinement ability and the simple local search algorithm has limited global exploration ability. Aiming at these problems, two algorithms were integrated to the Hybrid Greedy Genetic Algorithm (HGGA). Under the GA global search framework, local search module was added, and the traditional repair operator based only on item value density was improved, the greedy hybrid option based on item value was added, so as to accelerate the optimization process. In HGGA, the population was led to carry out fine search in the excellent solution space of evolution, and the classical operators of GA were relied on to expand the global search space, so as to achieve a good balance between the refinement ability and the development ability of the algorithm. HGGA was tested on three sets of data. The results show that in the first set of 15 test cases, HGGA is able to find the optimal solution on 12 cases, with a success rate of 80%; on the second small-scale dataset, the performance of HGGA is obviously better than those of other similar GA and other meta-heuristic algorithms; on the third large-scale dataset, HGGA is more stable and efficient than other meta-heuristic algorithms.

Key words: 0-1 Knapsack Problem (KP), Hybrid Greedy Genetic Algorithm (HGGA), refinement ability, generalization ability, hybrid greedy operator, local search

摘要： 求解0-1背包问题（KP）的最优解的时候，传统遗传算法（GA）的局部求精能力不足而简单局部搜索算法的全局探索能力有限，针对上述问题，将这两个算法整合并提出了混合贪婪遗传算法（HGGA）。在GA全局搜索框架下增加局部搜索模块，并改进传统仅基于物品价值密度的修复算子，增加基于物品价值的贪婪混合选项，从而加速寻优过程。HGGA一方面引导种群在进化的优质解空间中展开精细搜索，另一方面依靠GA的经典操作算子开拓全局搜索空间，从而达到算法求精能力和开拓能力的良好平衡。HGGA分别在三组数据上做了测试，结果表明在第一组15个测试用例中的12个上，HGGA能够百分百找到最优解，成功率达到80%；在第二组小规模数据集上，HGGA的性能明显好于其他同类GA和其他元启发算法；在第三组大规模数据集上，HGGA较其他元启发式算法具有更好的稳定性和高效性。

关键词: 0-1背包问题, 混合贪婪遗传算法, 求精能力, 求泛能力, 混合贪婪算子, 局部搜索