基于遗传算法的0-1背包问题研究_学士学位论文(编辑修改稿)

基于遗传算法的0-1背包问题研究_学士学位论文(编辑修改稿)内容摘要：

法也成为进化计算领域的一个重要分支。 遗传算法在应用方面取得的丰硕成果 ,使人们对它的发展前景充满信心。 认识到这一点 ,遗传算法的奠基人之一 ,Goldsberg D 戏言 :“ 已不再需要水晶球 ”。 今 后几年 ,可以预期 ,拓广更加多样的应用领域 ,其中包括各种 遗传算法 程序设计环境的 开发仍将是遗传算法发展的主流。 事实上这也是本世纪高新技术迅速发展带有规律性的特点 ,即面向应用。 与此同时 ,这并不意味着理论研究会被忽视 , 这方面同样有大量工作要做。 例如 : 控制参数的选择 ； 交换和突变这两类最重要的算子的确切作用 ； 并行遗传算法和分布式遗传算法的研究 ； 其他类型生物机制的模仿 ,如免疫、 病毒、寄生等 ,以丰富遗传算法的内容 ,等等。 自然 ,不论从理论还是应用的角度看 ,最紧迫的应是关于算法收敛性问题的研究 ,特别是过早收敛的防止。 这对遗传算法的实际应用关系重大。 当前一个特别值得重视的趋势是一些面向对象 的智能技术 ,其中主要是模糊逻辑 [8](Fuzzy Logic, FL ),神经网络 [9](Neural Network, NN )以及遗传算法等的综合应用。 众所周知 ,FL 有较强的知识表达能力 ,NN 的长处在于自学习 ,它们与遗传算法相结合形成新的集成化技术 ,即所谓的混合智能系统 (Hybrid Intellectual System )。 这一思想在 90 年代初逐步形成 ,而由模糊集论的创始人 ,美国 Zadeh LA在 1993 年于汉城召开的国际模糊系统协会 ( IFSA )第五届世界会议首先明确提出随后在许多有关的国际学 术会议上得到充分体现。 应该指出 ,我国学者对这一趋势的认识较早。 例如 ,清华大学李衍达院士领导的研究集体在几乎同一时期开展了这一重要方向的研究 1995年 , Zadeh 在 IFSA 的第六届世界会议上再次强调了这一方向的重要 设计（论文）专用纸 5 性 ,并且认为上述所谓的混合智能系统的应用将覆盖从消费品生产到核反应堆设计以至证券管理 ,而 “ 在未来几年中可能无处不在 ”。 就遗传算法本身的研究而言 ,应该说 ,我国起步较晚 ,近几年才陆续看到一些介绍性的文章、不多于两三部的专著以及初步的研究报告 ，与 国外工作比较 ,一个显著区别是 ,国内工作多只停留在论文这一层 次 ,几乎没有看到具体实际应用 ,与研究成果商品化的差距就更远。 理论研究与实际应用不够紧密 ,阻碍了我国高新技术的迅速发展 ,几乎已经成为顽症。 因此 ,在我国发展遗传算法 ,当前应该特别重视它的应用和推广普及。 学术界要主动和企业界连手开发遗传算法的应用 ,要重视引进或自行研制类似 于 SP licer 的程序设计环境 ,使遗传算法的应用更加方便和快捷。 国家组建的工程研究中心应该在这方面发挥更大的作用。 工科数学教育也应有所调整 ,以适应高新技术发展的需要。 例如 ,工科运筹学和最优化方法的课程应该适当加入有关遗传算法等方面的内容 ,以开阔 学生的视野 ,同时也有利于加快传统课程内容的更新。 遗传算法的特点 a. 算法从问题解的串集开始搜索，而不是从单一解开始。 这是遗传算法与传统算法的极大区别。 传统优化算法是从单个初值迭代求最优解的，容易误入局部最优解。 遗传算法从串集开始搜索，覆盖面大，利于全局择优。 b. 求解时使用特定问题的信息极少，容易形成通用算法程序。 由于遗传算法使用时应值这一信息进行搜索，并不需要问题导数等与问题直接相关的信息。 遗产算法只需自适应值和串编码等通用信息，故几乎可以处理任何问题。 c. 算法有极强的容错能力。 遗传算法的初始串 集本身就带有大量与最优解甚远的信息。 通过选择、交叉、变异操作能迅速排除与最优解相差极大的串。 这就是一个强烈的过滤过程，并且是一个并行滤波机制。 故而，遗传算法有很高的容错能力。 d. 算法中的选择、交叉、和变异都是随机操作，而不是确定的精确规则。 这说明遗传算法是采用随机方法进行最优解搜索，选择体现了向最优解迫近，交叉体现了最优解的产生，变异体现了全局最优解的覆盖。 设计（论文）专用纸 6 遗传算法分类 （ 1） 混合遗传算法 单用简单的遗传算法在许多情况下不是十分有效，容易产生早熟现象以及局部寻优能力较差等问题，于是提出了多种混 合算法。 例如， Ackley 推荐的遗传爬山法；Mathefoud 提出的遗传模拟退火算法；采用遗传算法中增加局部改善运算等等。 混合遗传算法的基本思想是：对于每个新产生的后代在其进入下一代群体之前应用局部优化技术 (如爬山法、模拟退火算法等 )，使之移动到最近的局部最优点。 在混合遗传算法中，运用启发式方法作局部优化，采用遗传算法作全局最优点的探索。 由于遗传算法与传统优化方法的互补性，混合遗传算法通常比单一算法优越。 （ 2） 并行遗传算法 遗传算法在 解 决一些实际问题时，由于它一般具有较大的群体规模，需要对较多的个体进 行大量的遗传和进化操作，特别是要对大量的个体进行适应度计算或评价，从而使得算法的进化运算过程进展缓慢，难以达到计算速度的要求，因而遗传算法的并行计算问题受到重视。 并行遗传算法主要从下列四个方面对其进行改进和发展。 个体适应度的评价 或计算在遗传算法的运行过程中所占用的运行时间比较长。 通过对个体适应度并行计算方法的研究可找到并行评价个体适应度的算法。 互依赖关系，这样各个个体的适应度计算过程就可以相互独立、并行地进 行。 即不同个体的适应度计算可以在不同的处理机上同时进行。 在父代 群体产生下一代群体过程中，选择操作只与个体的适应度有关，而交叉和变异操作只与参加运算的个体编码有关。 这样，产生群体过程中的选择、交叉、变异操作就可以相互独立地并行进行。 可以对群体按一定的方式进行分组，分组后各组的个体遗传进化过程可以在不同的处理机上相互独立地进行，在适当的时候，各处理机之间相互交换信息。 设计（论文）专用纸 7 遗传算法的应用 目前，遗传算法在很多科学、工程领域得到广泛的应用。 其典型应用领 域如下。 随着组合优化问题规模的增加，其搜索空间也急剧增加，在计算机上用穷举法不可能求出其最优解，而遗传算法可以在此类问题上寻求问题的满意解。 目前， GA 已经在旅行商问题（ TSP） [10]、背包问题 [11]、网络路由、货仓装载 [12]等具有NP 难度的组合优化等方面取得了成功的应用。 函数优化是 GA的经典应用领域。 学者构造了各种复杂的测试函数，既有连续函数也有离散函数，有高维的也有低维的，有凹的也有凸的，有多峰的也有单峰的，遗传算法较其他优化方法便于得到较好的结果。 函数优化也是对遗传 算法进行评价的常用工具。 ，遗传算法在自动控制领域的应用日益增加并取得了较好的成果。 目前 GA 进行系统辨识、模糊控制器设计、航空系统的优化等方面取得了一定的成就。 遗传算法在图像的处理的图像恢复、图像边缘特征提取方面得到了成功应用。 目前基于 GA 的机器学习在很多领域得到了应用。 例如：利用 GA的机器学习来调整人工神经网络的权值等；利用 GA学习模糊控制的奴隶度函数以改进模糊控制系统的性能。 数据挖掘就是大型数据库中提取人们感兴趣的、隐含的、有潜在应用价值的知识。 数据挖掘问题可以看做是搜索问题，把数据库看作是搜索空间，而把挖掘算法看作搜索策略，这样就可以使用遗传算法对数据库中的数据进行搜索，对于随机产生的一组规则进行进化，直至数据库能被该规则覆盖，进而挖掘出大型数据库中的隐含的规则。 本文主要工作 a. 介绍了 01 背包问题的概念，接着论述求解该问题的各种传统算法，并对 01背包问题进行数学描述。 设计（论文）专用纸 8 b. 对遗传算法进行了理论研究。 介绍了进化算法的基本理论，对典型的几种进化算法进行了简要说明，并对遗传算法的基本理论、应用情况和研究趋势做了较为详细的论述。 c. 应用遗传算法解决 01背包问题，通过设置不同参数探究遗传算法求解背包问题的可行性并将算法在 Matlab 仿真平台上进行实现。 d. 在 matlab 环境中进行 GUI 界面设计， 运行界面中遗传算法主要的参数可通过手动输入自行修改，同时通过 GUI 界面可以直接观察到仿真曲线的变化情况。 设计（论文）专用纸 9 第二章 基于遗传算法的 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，一般取为。 对一个需要进行优化计算的实际应用问题，一般可按下述步骤来构造求解该问题的遗传算法： 设计（论文）专用纸 10 第一步：确定决策变量及其各种约束条件，即确定出个体的表现型 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。 模式阶用 来反映不同模式问确定性的差异，模式阶数越高，模式的确定性就越高，所匹配的样本个数就越少。 设计（论文）专用纸 11 定义 定义距 (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的个体平均适应度 ｌ表示个体长度。