-
题名求解0-1背包问题的混合贪婪遗传算法
被引量:11
- 1
-
-
作者
陈桢
钟一文
林娟
-
机构
福建农林大学计算机与信息学院
智慧农林福建省高等学校重点实验室(福建农林大学)
-
出处
《计算机应用》
CSCD
北大核心
2021年第1期87-94,共8页
-
基金
福建省自然科学基金资助项目(2019J01401,2019J01661)
福建省教育厅中青年教师教育科研项目(KLA19027A)。
-
文摘
求解0-1背包问题(KP)的最优解的时候,传统遗传算法(GA)的局部求精能力不足而简单局部搜索算法的全局探索能力有限,针对上述问题,将这两个算法整合并提出了混合贪婪遗传算法(HGGA)。在GA全局搜索框架下增加局部搜索模块,并改进传统仅基于物品价值密度的修复算子,增加基于物品价值的贪婪混合选项,从而加速寻优过程。HGGA一方面引导种群在进化的优质解空间中展开精细搜索,另一方面依靠GA的经典操作算子开拓全局搜索空间,从而达到算法求精能力和开拓能力的良好平衡。HGGA分别在三组数据上做了测试,结果表明在第一组15个测试用例中的12个上,HGGA能够百分百找到最优解,成功率达到80%;在第二组小规模数据集上,HGGA的性能明显好于其他同类GA和其他元启发算法;在第三组大规模数据集上,HGGA较其他元启发式算法具有更好的稳定性和高效性。
-
关键词
0-1背包问题
混合贪婪遗传算法
求精能力
求泛能力
混合贪婪算子
局部搜索
-
Keywords
0-1 Knapsack Problem(KP)
Hybrid Greedy Genetic Algorithm(HGGA)
refinement ability
generalization ability
hybrid greedy operator
local search
-
分类号
TP18
[自动化与计算机技术—控制理论与控制工程]
-