关键词: 背包问题, 遗传算法, 极贪婪, 多位贪婪变异

Abstract: Crossover and mutation operators are the core operations of genetic algorithm.Efficient mutation operator not only plays an important role to enhance local search ability and keep population diverse,but also optimizes the offspring individuals with targeted amending strategy to correct the present trajectory.Thus,it enhances the efficiency of optimizing.Firstly,this paper proposes an even better extremely greedy algorithm on the basis of the very greedy algorithm.Then,a multiple bits greedy mutation operator is designed to deal with the multiple consecutive or discontinuous genes with extremely greedy mutation operation.Experimental results on classic knapsack instances show that multiple bits greedy mutation-based genetic algorithm (MBGGA) has efficient,effective and steady performance when comparing with the existing methods.

Key words: knapsack problem, genetic algorithm, extremely greedy, multiple bit greedy mutation