摘要：0/1背包问题是一个典型的NP完全问题，它能应用到生活的各个方面，具有很重要的研究意义。 遗传算法是一种效法物竞天择、适者生存的生物进化论的随机方法。 本文介绍了基于遗传算法对0/1背包问题的求解，首先介绍了用简单遗传算法求解0/1背包问题，经过研究分析，发现其存在的一些不足，进而得出了一种简单遗传算法和贪心算法结合的混合遗传算法求解的思想，经实验分析证明，改进后的混合遗传算法能够更好地解决0/1背包问题。84017

毕业论文关键词：遗传算法；0/1背包问题；贪心算法；混合遗传算法

Based on Genetic Algorithm 0/1 Knapsack Problem

Abstract： 0/1 knapsack problem is a typical NP-complete problems, which specifically applied to all aspects of life, has very important significance。 Genetic algorithms mimic natural selection, survival of the fittest biological evolution is a biological follow evolution of stochastic methods。 in this paper based on genetic algorithms 0/1 knapsack problem solving, first introduces the solving 0/1 knapsack problem with a simple genetic algorithm, through research and analysis, we found that some of its shortcomings, then come to the a simple genetic algorithm and greedy algorithm combines hybrid genetic algorithm ideas, experiment analysis shows that the improved hybrid genetic algorithm can better solve the 0/1 knapsack problem。

Keywords：Genetic algorithm; 0/1 knapsack problem; Greedy algorithm; Hybrid genetic algorithm

目    录

摘  要 1

Abstract 1

引言 2

1。 0/1背包问题和遗传算法 3

1。1 0/1背包问题 3

1。2 算法遗传 3

2。用遗传算法求解0/1背包问题 4

2。1简单遗传算法 4

2。1。1简单遗传算法的描述 4

2。1。2遗传算法的流程图 5

2。1。3遗传算法步骤 5

2。2基本遗传算法求解0/1背包问题的不足 7

3。改进的遗传算法求解0/1背包问题 8

3。1贪心算法对于0/1背包问题的求解 8

3。2混合遗传算法 9

4。案例及结果分析 11

5。结束语 11

参考文献 13

附录 14

致谢 23

基于遗传算法求解0/1背包问题

引言

 0/1背包问题属于一类典型的组合优化问题，也是众多背包问题中最基本和最原始的类型，并且0/1背包问题是NP完全问题，对0/1背包进行求解的过程可以被视作在很多可行解中求解一个最优解，具有非常重要的研究意义。

文献[1]-[8]介绍了0/1背包问题的研究现状与分析。近年来，背包问题吸引了许多理论工作者和实际工作者来对此进行深入地分析和研究。在实际应用中，许多工业方面的问题都可以用背包问题来描述和求解，比如存储分配，货舱装载，资金运算，材料切割等都是其中较为典型的应用实例。 如何将0/1背包问题应用于实践中，并且能够很好地解决实际问题，这是众多工作者不断思考和研究的一个领域。文献[9]-[12]也介绍了关于0/1问题的解决方法。围绕0/1背包问题的求解方法有很多，例如动态规划法、贪心算法、分支限界法、回溯法、枚举法、遗传算法等等。尽管背包问题的描述简单，但它却具有组合爆炸的性质，这也就使得在问题规模增大的情况下，如分支限界法、回溯法、枚举法等精确算法的时间呈指数增长，从而使求解变得不太现实。而遗传算法、贪心算法等近似算法虽然不一定能得到问题的最优解，但可以在较短的时间内得到问题的有效解和满意解。论文网