计算机应用

作者：陈桢, 钟一文, 林娟

单位：1. 福建农林大学 计算机与信息学院, 福州 350002;2. 智慧农林福建省高等学校重点实验室(福建农林大学), 福州 350002

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

基金：福建省自然科学基金资助项目（2019J01401，2019J01661）；福建省教育厅中青年教师教育科研项目（KLA19027A）。

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

来源：2021年第1期

《计算机应用》期刊编辑部

查看计算机应用杂志2021年第1期