一种求解0-1背包问题的启发式遗传算法

摘要

分析求解背包问题的多种方法,研究背包问题的贪婪策略及最优值的特点,将贪婪策略融入到遗传算法的种群初始化、交叉算子、变异算子中,将分治策略引入到选择算子中,提出一种启发式遗传算法.实验结果表明:算法无论在求解速度上还是在求解质量上都有明显改进.%In this paper we analyse various methods for solving the knapsack problem, and study the greedy strategy of knapsack problem and the characteristics of its optimal value. By integrating the greedy strategy into population initialisation, crossover operator and mutation operator of the genetic algorithm, and introducing the divide-and-conquer strategy to selection operator, we propose a heuristic genetic algorithm. Experimental results show that for both the quality of solution and the time consumed in problem solving, this algorithm all makes obvious improvement.