《基于遗传算法求解背包问题》由会员分享，可在线阅读，更多相关《基于遗传算法求解背包问题（49页珍藏版）》请在金锄头文库上搜索。
1、本科生毕业设计（论文）( 2010届 ) 题 目： 基于遗传算法求解背包问题 目 录摘要 1英文摘要 11 引言 12 背包问题概述 22.1 背包问题描述 22.2 研究背包问题的意义 23 遗传算法概述 2 3.1 遗传算法的特点 33.2 遗传算法的应用领域 3 4 遗传算法的基本原理 4 4.1 基本流程 4 4.2 编码 54.3 适应度函数 54.4 遗传算子 64.4.1 选择算子 6 4.4.2 交叉算子7 4.4.3 变异算子74.5 参数控制 84.5.1 群体规模 8 4.5.2 交叉概率 8 4.5.3 变异概率 84.6 算法结束条件控制 9 5 实现求解背包问题的遗
2、传算法 95.1 0_1背包问题中染色体的表示95.2 遗传算法求解0_1背包问题时用到的参数 95.3 选择操作 95.4 交叉操作 105.5 精英策略 115.6 变异操作 115.7 代际更新 115.8 算法终止 115.9 仿真结果与测试 125.9.1 不同交叉概率下所得测试结果 135.9.2 极端数据对结果的影响 155.9.3 仿真结果总结 185.10 问题总结 186 展望 18致 19参考文献 20附源程序 21基于遗传算法求解背包问题摘 要背包问题(Knapsack problem)是一种组合优化的NP完全问题,本文首先介绍了基本遗传算法的基本原理、特点及其基本实现
3、技术，接着针对背包问题，论述了遗传算法在编码表示和遗传算子（包括选择算子、交叉算子变异算子这三种算子）等方面的应用情况。并且结合背包问题实例，给出了具体的编码方法，运行参数，群体大小，最大迭代次数，以及合适的遗传算子。最后，简单说明了遗传算法在求解背包问题中的应用并对遗传算法解决背包问题的前景提出了展望。关键词：背包问题；遗传算法；遗传算子；编码Genetic Algorithm for KPJin Tian Tian Director: Prof. DaYong Deng(College of Mathematics Physics And Information Engineering ,
4、Zhejiang Normal University)Abstract:KP (Knapsack Problem) is a combinatorial optimization of NP - complete problem. The primary knowledge, characteristics and the basic techniques of GA are introduced firstly. The encoding model and genetic operators (including selection operation, crossover operati
5、on and mutation operation) solving KP are discussed secondly. Combined with examples of knapsack problem, we have given the specific encoding method, operating parameters, popsize, maxgeneration, and suitable genetic operator. At last, the application of genetic algorithm is simple presented, and th
6、e prospect for the future of genetic algorithm in solving KP has been given.Keywords: KP ,genetic algorithm, genetic operators ,encoding1 引 言 现代科学理论研究与实践中存在着大量与优化、自适应相关的问题，但除了一些简单的情况之外，人们对于大型复杂系统的优化和自适应问题仍然无能为力。然而，自然界中的生物却在这方面表现出了其优异的能力，它们能够以优胜劣汰、适者生存的自然进化规则生存和繁衍，并逐步产生出对其生存环境适应性很高的优良物种。遗传算是借鉴生物的自然选择
7、和遗传进化机制而开发出的一种全局优化自适应概率搜索算法。遗传算法使用群体搜索技术，它通过对当前群体施加选择、交叉、变异等一系列遗传操作，从而产生出新一代的群体，并逐步使群体进化到包含或接近最优解的状态。由于其具有思想简单、易于实现、应用效果明显等优点而被众多应用领域所接受，遗传算法就其本质来说，主要是解决复杂问题的一种鲁棒性强的启发式随机搜索算法。背包问题(Knapsack problem)是一种组合优化的NP完全问题,对这个问题的求解前人己经研究出了不少的经典的方法,例如解析法，穷举法等，但是这些传统的优化方法存在一些缺点，如算法复杂度太高。与传统的优化算法相比，遗传算法具有以下优点:在每一
8、时刻，GA同时在多个子空间进行搜索，对初始值不作要求;基本不用搜索空间的知识或其他辅助信息，而仅用适应度来评估个体优劣;具有很强的鲁棒性。因此遗传算法在背包问题求解方面的应用研究，对于构造合适的遗传算法框架、建立有效的遗传作以及有效地解决背包问题等有着多方面的重要意义5。2 背包问题概述2.1 背包问题的描述背包问题又称子集合问题，最早是由Dantzing 于20 世纪50 年代首次提出的，已成为计算机学科中一个经典的NP 问题，本文讨论的是0-1背包问题，问题描述如下：指定给n件物品和一个背包，物品i 的重量是wi，其价值为vi，背包的容量为C，求从这n 件物品中选取一部分物品且对每件物品,
9、或者选取,或者不选,每种物品只能装入背包一次,且要求满足放入背包中的物品总重量不超过背包容量。求出装入背包中物品价值总和最大的方案。注意：在本题中，所有的重量值均为整数。数学模型限制条件为：所求表达式为：其中，表示物品放入背包，表示物品未放入背包。2.2 研究背包问题的意义背包问题是组合优化领域中的一个典型问题，涉及求多个变量的函数的最大值。虽然它述起来很简单，但求解却很困难，并且已经被证明是NP完全问题。至今尚未找到有效的求解方法，在理论上枚举法可以解这一问题，但是当n较大时，解题的时间消耗会使枚举法显得没有任何实际价值。因此寻求一种求解时间短，能满足实际问题精度要求的解，成为解决该问题的主
10、要途径8。 背包问题的求解，一直以来倍受人们的关注。对于这样一个典型的、易于描述却难以处理的NP难题，有效地解决它在可计算理论上有着重要的理论价值。并且，背包问题是诸多领域出现的多种复杂问题的集中概括和简化形式。背包问题也可描述为决定性问题，相似问题经常出现在商业、投资组合优化、组合数学，计算复杂性理论、密码学和应用数学等领域中，因此具有广泛的实际应用领域。3 遗传算法概述遗传算法（GA）是一类借鉴生物界自然选择和自然遗传机制的随机化的搜索算法，也是一种抽象于生物进化过程的基于自然选择和生物遗传机制的优化技术。它是在1975年首次由美国密西根大学的D. J. Holland教授和他的同事们借鉴
11、生物界自然选择和进化机制基础之上提出的。经过近30年的研究、应用，遗传算法已被广泛地应用于函数优化、机器人系统、神经网络学习过程、模式识别、图象处理、工业优化控制等领域。其主要特点是群体搜索策略、群体中个体之间的信息交换和搜索不依赖于梯度信息19。 遗传算法是将问题的每一个可能性解看作是群体中的一个个体(染色体)，并将每一个染色体编码成串的形式，再根据预定的目标函数对每个个体进行评价，给出一个适应度值。算法将根据适应度值对它进行寻优的过程，遗传算法的寻优过程是通过选择、杂交和变异三个遗传算子来具体实现的，它的搜索能力由选择算子和杂交算子决定，变异算子则保证了算法能够搜索到问题空间的每一个点，从
12、而使其具有搜索全局最优的能力。遗传算法的高效性和强壮性可由Holland提出的模式定理(Schema Theorem)和隐式并行性得以解释。近年来，遗传算法从理论到实际都已经取得了许多重要成果。由于它具有良好的全局搜索能力，是目前解决各种优化问题的最有效的方法，已经成为研究热点。3.1 遗传算法的特点 从整体上来讲，遗传算法是进化算法中产生最早、影响最大、应用也比较广泛的一个研究方向和领域，它不仅包含了进化算法的基本形式和全部优点，同时还具备若干独特的性能。161)在求解问题时，遗传算法首先要选择编码方式，它直接处理的对象是参数的编码集而不是问题参数本身，搜索过程既不受优化函数连续性的约束，也没有优化函数倒数必须存在的要求。通过优良染色体基因的重组，遗传算法可以有效地处理传统上非常复杂的优化函数求解过程；2)若遗传算法在每一代对群体规模为n的个体进行操作，实际上处理了大约个模式,具有很高的并行性，因而具有显著的搜索效率；3
