计算机应用与软件2013，Vol.30Issue(2)：33-37,57,6.DOI:10.3969/j.issn.1000-386x.2013.02.009
一种求解0-1背包问题的启发式遗传算法
A HEURISTIC GENETIC ALGORITHM FOR SOLVING 0-1 KNAPSACK PROBLEM
摘要
Abstract
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.关键词
背包问题/遗传算法/贪婪策略/分治策略Key words
Knapsack problem/Genetic algorithm/Greedy strategy/Divide-and-conquer strategyq分类
信息技术与安全科学引用本文复制引用
王秋芬,梁道雷..一种求解0-1背包问题的启发式遗传算法[J].计算机应用与软件,2013,30(2):33-37,57,6.基金项目
国家自然科学基金项目(90818013) （90818013）
华东师范大学211重点项目(521B0108) （521B0108）
浙江理工大学基金项目(yb07002). （yb07002）
