遗传算法在背包问题上的应用_信息与计算科学.doc

摘要:背包问题(Knapsack problem)是一种组合优化的NP完全问题,本文讲述了遗传算法的基本原理、特点及其基本实现技术，然后针对背包问题，论述了遗传编码表示和遗传算子（例如选择算子、交叉算子，变异算子）等方面的应用情况。并且结合背包问题实例，给出了具体的编码方法，群体大小，运行参数，最大迭代次数，以及合适的遗传算子。最后，说明了遗传算法在背包问题中的应用并对遗传算法求解背包问题的前景提出了展望。

关键词：背包问题；遗传算法；遗传算子；编码

Abstract:Knapsack problem (Knapsack problem) is NP-complete problem to a combinatorial optimization, the article describes the basic principles of genetic algorithms,characteristics and basic technology, and then for the knapsack problem, discusses thegenetic algorithm in the coded representation and genetic operators (such asselection operator, crossover operator, mutation operator) and other aspects of the application.And combination of the knapsack problem instance, given a specific encoding method,population size, operating parameters, the maximum number of iterations, and the appropriate genetic operators. Finally, the prospects of a genetic algorithm in theknapsack problem and genetic algorithm for knapsack problem raised outlook.

Key Words: knapsack problem; genetic algorithm; genetic operators; coding

　　　现代科学理论研究与实践中存在着许多与优化相关的问题，但除了一些简单的情况之外，人们对于大型复杂系统的优化问题仍然无能为力。然而，自然界中的生物却在这方面有着出人意料的能力，它们能以适者生存、优胜劣汰的进化规则生存，并逐步转变成对其生存环境适应性很高的物种。遗传算法就是一种随机化的搜索算法，他就是通过借鉴生物界自然选择和自然遗传机制来实现的。

　　　遗传算法用的是群体搜索技术，它利用对群体进行一系列操作，其中包括选择、交叉、变异等等，通过这种操作产生一系列新的群体，重复这种操作，直到使群体达到最接近最优解便可以了。由于遗传算法具有实现起来简单方便、实现后的效果显著易懂，并且其算法思想易于理解等优点，它的应用领域也非常的广泛，遗传算法的本质实质上就是一种具有很强鲁棒性的启发式的随机算法。

　　　背包问题（Knapsack problem）是一种组合优化的NP完全问题，目前针对这个问题已经有了很多解法，其中除了遗传算法还包括回溯法、蚁群算法、动态规划算法、分支限界法等等。这些算法多多少少都有着一些小问题和缺陷，例如算法的精度不够精准或算法的复杂度过高等。

　　　就其他这些优化算法来说，遗传算法相对比较包括以下几点优点：1）遗传算法搜多从群体出发，在同一时刻可以同时对多个子树进行搜索，具有并行性，并且对初始值没有特殊要求；2）利用概率机制进行迭代，具有随机性；3）扩展性很强，更易与其他算法相结合来使用；4）鲁棒性很强，计算时间较短。

　　　因此遗传算法在背包问题的应用上的研究，对于构建适合的遗传算法框架、有效地解决背包问题等方面有着重要意义。