摘要
分析求解背包问题的多种方法,研究背包问题的贪婪策略及最优值的特点,将贪婪策略融入到遗传算法的种群初始化、交叉算子、变异算子中,将分治策略引入到选择算子中,提出一种启发式遗传算法。实验结果表明:算法无论在求解速度上还是在求解质量上都有明显改进。
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.
出处
《计算机应用与软件》
CSCD
北大核心
2013年第2期33-37,57,共6页
Computer Applications and Software
基金
国家自然科学基金项目(90818013)
华东师范大学211重点项目(521B0108)
浙江理工大学基金项目(yb07002)
关键词
背包问题
遗传算法
贪婪策略
分治策略
Knapsack problem Genetic algorithm Greedy strategy Divide-and-conquer strategy
