基于遗传算法的0-1背包问题研究

基于遗传算法的0-1背包问题研究内容摘要：

( IFSA )第五届世界会议首先明确提出随后在许多有关的国际学术会议上得到充分体现。 应该指出 ,我国学者对这一趋势的认识较早。 例如 ,清华大学李衍达院士领导的研究集体在几乎同一时期开展了这一重要方向的研究 1995年 , Zadeh 在 IFSA 的第六届世界会议上再次强调了这一方向的重要性 ,并且认为上述所谓的混合智能系统的应用将覆盖从消 费品生产到核反应堆设计以至证券管理 ,而 “ 在未来几年中可能无处不在 ”。 就遗传算法本身的研究而言 ,应该说 ,我国起步较晚 ,近几年才陆续看到一些介绍性的文章、不多于两三部的专著以及初步的研究报告 ，与 国外工作比较 ,一个显著区别是 ,国内工作多只停留在论文这一层次 ,几乎没有看到具体实际应用 ,与研究成果商品化的差距就更远。 理论研究与实际应用不够紧密 ,阻碍了我国高新技术的迅速发展 ,几乎已经成为顽症。 因此 ,在我国发展遗传算法 ,当前应该特别重视它的应用和推广普及。 学术界要主动和企业界连手开发遗传算法的应用 ,要重视引进或自行研制类 似 于 SP licer 的程序设计环境 ,使遗传算法的 . 应用更加方便和快捷。 国家组建的工程研究中心应该在这方面发挥更大的作用。 工科数学教育也应有所调整 ,以适应高新技术发展的需要。 例如 ,工科运筹学和最优化方法的课程应该适当加入有关遗传算法等方面的内容 ,以开阔学生的视野 ,同时也有利于加快传统课程内容的更新。 遗传算法的特点 a. 算法从问题解的串集开始搜索，而不是从单一解开始。 这是遗传算法与传统算法的极大区别。 传统优化算法是从单个初值迭代求最优解的，容易误入局部最优解。 遗传算法从串集开始搜索，覆盖面大，利于全局 择优。 b. 求解时使用特定问题的信息极少，容易形成通用算法程序。 由于遗传算法使用时应值这一信息进行搜索，并不需要问题导数等与问题直接相关的信息。 遗产算法只需自适应值和串编码等通用信息，故几乎可以处理任何问题。 c. 算法有极强的容错能力。 遗传算法的初始串集本身就带有大量与最优解甚远的信息。 通过选择、交叉、变异操作能迅速排除与最优解相差极大的串。 这就是一个强烈的过滤过程，并且是一个并行滤波机制。 故而，遗传算法有很高的容错能力。 d. 算法中的选择、交叉、和变异都是随机操作，而不是确定的精确规则。 这说明遗传算法是采用随机 方法进行最优解搜索，选择体现了向最优解迫近，交叉体现了最优解的产生，变异体现了全局最优解的覆盖。 遗传算法分类 （ 1） 混合遗传算法 单用简单的遗传算法在许多情况下不是十分有效，容易产生早熟现象以及局部寻优能力较差等问题，于是提出了多种混合算法。 例如， Ackley 推荐的遗传爬山法；Mathefoud 提出的遗传模拟退火算法；采用遗传算法中增加局部改善运算等等。 混合遗传算法的基本思想是：对于每个新产生的后代在其进入下一代群体之前应用局部优化技术 (如爬山法、模拟退火算法等 )，使之移动到最近的局部最优 点。 在混合遗传算法中，运用启发式方法作局部优化，采用遗传算法作全局最优点的探索。 由于遗传算法与传统优化方法的互补性，混合遗传算法通常比单一算法优越。 . （ 2） 并行遗传算法 遗传算法在 解 决一些实际问题时，由于它一般具有较大的群体规模，需要对较多的个体进行大量的遗传和进化操作，特别是要对大量的个体进行适应度计算或评价，从而使得算法的进化运算过程进展缓慢，难以达到计算速度的要求，因而遗传算法的并行计算问题受到重视。 并行遗传算法主要从下列四个方面对其进行改进和发展。 个体适应度的评价 或计算 在遗传算法的运行过程中所占用的运行时间比较长。 通过对个体适应度并行计算方法的研究可找到并行评价个体适应度的算法。 互依赖关系，这样各个个体的适应度计算过程就可以相互独立、并行地进行。 即不同个体的适应度计算可以在不同的处理机上同时进行。 在父代 群体产生下一代群体过程中，选择操作只与个体的适应度有关，而交叉和变异操作只与参加运算的个体编码有关。 这样，产生群体过程中的选择、交叉、变异操作就可以相互独立地并行进行。 可以对群体按一定的方式进行分组，分组后各组的个体遗传进化过程可以在不同的处理机上相互独立地进行，在适当的时候，各处理机之间相互交换信息。 遗传算法的应用 目前，遗传算法在很多科学、工程领域得到广泛的应用。 其典型应用领域如下。 随着组合优化问题规模的增加，其搜索空间也急剧增加，在计算机上用穷举法不可能求出其最优解，而遗传算法可以在此类问题上寻求问题的满意解。 目前， GA 已经在旅行商问题（ TSP） [10]、背包问题 [11]、网络路由、货仓装载 [12]等具有NP难度的组 合优化等方面取得了成功的应用。 函数优化是 GA 的经典应用领域。 学者构造了各种复杂的测试函数，既有连续函数也有离散函数，有高维的也有低维的，有凹的也有凸的，有多峰的也有单峰的，遗传算法较其他优化方法便于得到较好的结果。 函数优化也是对遗传算法进行评价的常用工具。 ，遗传算法在自动控制领域的应用日益增加并取得了较好的成果。 目 . 前 GA 进行系统辨识、模糊控制器设计、航空系统的优化等方面取得了一定的成就。 遗传算法在图像的处理的图像恢复、图像边缘特征提取方面得到了成功应用。 器学习。 目前基于 GA的机器学习在很多领域得到了应用。 例如：利用 GA的机器学习来调整人工神经网络的权值等；利用 GA 学习模糊控制的奴隶度函数以改进模糊控制系统的性能。 数据挖掘就是大型数据库中提取人们感兴趣的、隐含的、有潜在应用价值的知识。 数据挖掘问题可以看做是搜索问题，把数据库看作是搜索空间，而把挖掘算法看作搜索策略，这样就可以使用遗传算法对数据库中的数据进行搜索，对于随机产生的一组规则进行进化，直至数据库能被该规则覆盖，进而挖掘出大型数据库中的隐含的规则。 a. 介绍了 01 背包 问题的概念，接着论述求解该问题的各种传统算法，并对 01 背包问题进行数学描述。 b. 对遗传算法进行了理论研究。 介绍了进化算法的基本理论，对典型的几种进化算法进行了简要说明，并对遗传算法的基本理论、应用情况和研究趋势做了较为详细的论述。 c. 应用遗传算法解决 01背包问题，通过设置不同参数探究遗传算法求解背包问题的可行性并将算法在 Matlab 仿真平台上进行实现。 d. 在 matlab 环境中进行 GUI 界面设计， 运行界面中遗传算法主要的参数可通过手动输入自行修改，同时通过 GUI 界面可以直接观察到仿真曲线的变化情况。 . . 第二章 基于遗传算法的 01 背包问题研究 遗传算法是模拟生物在自然界中的遗产进化过程而形成的一种自适应全局优化概率搜索算法。 它最早是有没过密歇根大学的 Holland 教授提出的，起源于 60 年代对自然和人工自适应系统的研究 [13]。 70 年代 Dc Jong 基于遗传算法的思想在计算机上进行了大量纯数值函数优化计算实验 [14]。 在一系列研究工作基础上。 80 年代有Goldberg 进行归纳总结，形成了遗传算法的基本框架。 生物进化是以集团为主体的，与此相适应的，遗传算法的运算对象 是由 M个个体所组成的集合，成为群体。 与生物一代一代的自然进化过程相似，遗传算法也是一个反复迭代的过程，第 t 代群体记作 P（ t）经过一代遗传和进化之后，得到第 t+1 代群体，它们是由多个个体组成的集合记作 P（ t+1）。 这个群体不断的经过遗传和进化操作，并且每次都按照优胜劣汰的规则将适应度较高的个体更多的遗传到下一代，这样最终在种群中将会得到一个优良的个体 X，它所对应的的表现型 X将达到或接近问题的最优解 X*。 遗传算法有四个构成要素： a) 染色体编码方法：使用固定长度的二进制符号串来表示群体中的个体，其等位基因是由二值 符号集 {0， l}所组成的。 b) 个体适应度评价：基本遗传算法按与个体适应度成正比的概率来决定当前群体中每个个体遗传到下一代群体中的机会多少。 c) 遗传算子：使用比例选择算子、单点交叉算子、基本位变异算子或均匀变异算子。 d) 运行参数：群体大小 M；遗传运算的终止进化代数 T乃一般取为 100500；交叉概率 Pc，一般取为 ；变异概率 Pm，一般取为。 对一个需要进行优化计算的实际应用问题，一般可按下述步骤来构造求解该问题的遗传算法： 第一步：确定决策变量及其各种约束条件，即确定出个体的表现型 X 和问题的解空间； . 第二步：建立优化模型，即确定出目标函数的类型 (是求目标函数的最大值。 还是求目标函数的最小值 )及其数学描述形式或量化方法； 第三步：确定表示可行解的染色体编码方法，即确定出个体的基因型 X 及遗传算法的搜索空间； 第四步：确定解码方法，即确定出由个体基因型 x和个体表现型 X 的对应关系或转换方法； 第五步：确定个体适应度的量化评价方法，即确定出由目标函数值 f(x)个体适应度 F(X)的转换规则； 第六步：设计遗传算子，即确定出选择运算、交叉运算、变异运算等遗传算子的具体操作方法； 第七步：确定遗传算法 的有关运行参数，即确定出遗传算法的 M， Pc， Pm 等参数。 遗传算法的数学基础 遗传算法在机理方面具有搜索过程和优化机制等属性，数学方面的性质可通过模式定理和积木块假设等分析加以讨论， Markov 链也是分析遗传算法的一个有效工具。 遗传算法的执行过程包括了大量的随机性操作，因此有必要对其数学机理进行分析。 模式定理 [15’ 16’ 17]是由 John Holland 在 1971 年提出的，它是 GA的基本定理。 它将 GA 的运算过程理解为模式运算过程，并从模式运算的角度解释 GA的性能特点。 定义 模式 (schema)是一个描述字符串集的模板，该字符串集中的串的某些位置上存在相似性。 因此模式也可解释为相同的构形。 定义 模式阶 (schema order)模式 H中确定位置的个数称为该模式的阶，记作 o(H)。 例如： o(011*1*)=4。 模式阶用来反映不同模式问确定性的差异，模式阶数越高，模式的确定性就越高，所匹配的样本个数就越少。 定义 定义距 (defining length)模式 H 中的第一个确定位置和最后一个确定位置之间的距离称为该模式的定义距，记作δ (H)。 例如：δ（ 011*1**） =4。 在遗传操作中，即使阶数相同的模式，也会有不同的性质，而模式的定义距就反映了这种性质的差异。 模式定理在遗传算子选择、交叉和变异的作用下，具有低阶、短定义距以及平均 . 适应度高于种群平均适应度的模式在子代中呈指数增长。 模式定理可以用数学形式表示为： ( , 1 ) ( , ) ( ( ) / ) [ 1 ( ( ) / ( 1 ) ) ( ) ]cmm H t m H t f H f P H l o H P         式中， m（ H,t+1）辨识在 t+1 代种群中存在模式 H的个数 f(H)表示在 t代种群包含模式 H的个体平均适应度 ｌ表示个体长度 Pc表示交叉概率 Pm表示变异概率 δ (H) 表示模式 H的定义距； o（ H）表示模式 H的 阶。 模式定理是遗传算法的基本理论，保证了较优的模式 (遗传算法的较优解 )的数目呈指数增长，为解释遗传算法机理提供了一种数学工具。 定义 积木块 (building block)在模式定理中所指的具有低阶、短定义距以及平均适应度高于种群平均适应度的模式被定义为积木块。 积木块假设 (Building block hypothesis)[18]低阶、短定义距、高平均适应度的基因块 通过选择、交叉和变异等遗传算子的作用，能够互相拼接在一起，形成高阶、长定义距、高平均适应度的模式，最终接近全局最优解。 满足这个 假设的条件比较简单，包括两方面： a) 表现型相近的个体，其基因型相近； b) 遗传因子间相关性低。 目前大量的实践支持积木块假设，它在许多领域内都取得了成功，例如平滑多峰问题、带干扰多峰问题以及组合优化问题等。 模式定理保证了较优模式的样本数呈指数增长，从而满足求最优解的必要条件，即遗传算法存在找到全局最优解的可能性；而积木块假设指出，遗传算法具备寻找全局最优解的能力，即积木块在遗传算子的作用下，能生成低阶、短距、高平均适应度的模式，最终生成全局最优解。 虽然模式定理在一定意义上解决了基本遗传算法的有效性，但它仍有以下 的缺点： a) 模式定理只对二进制编码适用，对其他编码方案尚没有相应的结论成立； b) 模式定理只给出了在下世代包含模式 H 的个体数的下限。 我们无法据此推断 . 算法的收敛性； c) 模式定理没有解决算法设计中控制参数选取等问题。 遗传算法基本原理 典型的遗传算法 CGA[19] (Canonical Geic Algorithm)通常用于解决下面这一类的静态最优化问题：考虑对于一群长度为 L 的二进制编码 bi， i=1， 2，„， n；有bi{0， l}L 给定目标函数 f，有 f(bi)0 同时 f(bi)≠ f(bi+1)，求满足式 max{f(bi)｜bi{0， 1}L}的 bi；。 很明显，遗传算法是一。