Journal of Computer Applications ›› 2021, Vol. 41 ›› Issue (1): 87-94.DOI: 10.11772/j.issn.1001-9081.2020060981

Special Issue: 第八届中国数据挖掘会议(CCDM 2020)

• China Conference on Data Mining 2020 (CCDM 2020) • Previous Articles     Next Articles

Hybrid greedy genetic algorithm for solving 0-1 knapsack problem

CHEN Zhen1, ZHONG Yiwen2, LIN Juan1   

  1. 1. College of Computer and Information Sciences, Fujian Agriculture and Forestry University, Fuzhou Fujian 350002, China;
    2. Key Laboratory of Smart Agriculture and Forestry(Fujian Agriculture and Forestry University), Fujian Province University, Fuzhou Fujian 350002, China
  • Received:2020-05-30 Revised:2020-07-29 Online:2021-01-10 Published:2020-08-21
  • Supported by:
    This work is partially supported by the Natural Science Foundation of Fujian Province (2019J01401, 2019J01661), the Young and Middle-Aged Teachers Education Research Project of Fujian Provincial Department of Education (KLA19027A).

求解0-1背包问题的混合贪婪遗传算法

陈桢1, 钟一文2, 林娟1   

  1. 1. 福建农林大学 计算机与信息学院, 福州 350002;
    2. 智慧农林福建省高等学校重点实验室(福建农林大学), 福州 350002
  • 通讯作者: 陈桢
  • 作者简介:陈桢(1982-),女,福建仙游人,讲师,硕士,主要研究方向:计算智能;钟一文(1968-),男,福建上杭人,教授,博士,主要研究方向:计算智能、生物信息学、科学数据可视化;林娟(1980-),女,福建福州人,副教授,硕士,主要研究方向:生物信息学、科学数据可视化。
  • 基金资助:
    福建省自然科学基金资助项目(2019J01401,2019J01661);福建省教育厅中青年教师教育科研项目(KLA19027A)。

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背包问题, 混合贪婪遗传算法, 求精能力, 求泛能力, 混合贪婪算子, 局部搜索

CLC Number: