求解背包问题的多位极贪婪遗传算法

Multiple Bits Greedy Mutation-based Genetic Algorithm for Knapsack Problem

交叉和变异运算是遗传算法的核心操作,高效的变异算子不但起到改善遗传算法局部搜索能力和维持多样性的作用,还能基于针对性的修改策略在变异运算过程中实现对子代个体的优化处理,修正当前的搜索路径,进而提高算法的寻优效率。本文首先在更贪心算法的基础上提出了效果更佳的极贪婪变异算法,设计了一种多位贪婪变异算子,对遗传算法染色体(装包方案)的连续或间断的几位等位基因进行极贪婪变异处理。对经典背包算例的仿真结果表明,多位极贪婪变异遗传算法(MBGGA)同文献新近提出的多种算法相比具有快速、高效、稳定的性能表现。

Crossover and mutation operators are the core operations of genetic algorithm. Efficient muta- tion 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 ex- tremely greedy algorithm on the basis of the very greedy algorithm. Then,a multiple bits greedy muta- tion 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.