摘要背包问题的应用领域非常广泛，在商业、投资组合优化、计算复杂性理论、组合 数学、应用数学和密码学中经常使用背包问题进行建模。但背包问题很难求解，传统 的方法如枚举法等都无法满足求解背包问题的要求，需要设计更加强大的算法对其进 行求解。遗传算法借鉴了自然界中生物进化的规则，模拟生物的遗传过程，通过选择、 交叉、变异等操作，对问题的解进行遗传进化筛选，并最终获得问题的最优解。84422

在设计遗传算法的过程中，我们需要完成以下工作，即对遗传基因的编码、控制 参数的确定、遗传算子的选择、设计适合的适应度函数并解决约束问题等。在设计出 适合的遗传算子后，通过了测试函数的检验。使用 Matlab 程序仿真在不同参数的设 定下的求解结果，对比分析并寻找出最优的一组参数，并以此进行更加复杂的背包问 题计算，观察算法对不同背包问题的求解程度。总结实验结果，并对后续的研究提出 一些设想与展望。

毕业论文关键词：遗传算法；遗传算子；控制参数；背包问题；二进制编码。

Abstract Knapsack problem has been widely used in various fields, in business, portfolio optimization, computational complexity theory, combinatorial mathematics, applied mathematics and cryptography is often used to model the knapsack problem。 But it is very difficult to solve knapsack problem, the traditional methods such as enumeration method and so can not meet the requirements for knapsack problem, we need to design more powerful algorithms to solve them。 GA draws nature of biological evolution  rules, simulated biological genetic processes, by selection, crossover and mutation operation, screening the solution of the problem by the evolution of genetic, and, ultimately, to obtain the optimal solution of the problem。

In designing genetic algorithms, we need to do the following, namely genetic code, to determine the control parameters, genetic operators of selection, design the appropriate fitness function and constraint solving problems。 In the design of a suitable genetic operators, we adopted Testing functions。 Use Matlab simulation program get the solution results in a different set of parameters, and comparative analysis to find the optimal set of parameters, then calculate more complex knapsack problem, to observe the extent of different algorithm knapsack problem。 Summarizes the experimental results and  put forward some suggestions and prospects for the follow-up study。

Keywords:GA;   genetic   operators;   control   parameters;   knapsack     problem;binary encoding。

目 录

第一章 绪论 1

1。1 本研究课题的目的及意义 1

1。2 国内外研究现状及存在的问题 1

1。2。1 国外研究历程 2

1。2。2 国内研究历程 3

1。3 本文的主要内容 3

第二章 遗传算法的基本思想 4

2。1 遗传算法的产生与发展 4

2。2 遗传算法的基本思想 4

2。3 遗传算法的特点 7

2。4 遗传算法的基本操作 8

2。4。1 选择 8

2。4。2 交叉 8

2。4。3 变异 9

2。5 遗传算法的流程