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

基于遗传算法的基于遗传算法的 0-10-1 背包问题研究背包问题研究 专业年级专业年级: : 自动化 第 I页 摘要摘要 本文介绍了 0-1 背包问题的基本概念，综述了求解 0-1 背包问题的传统方法； 对遗传算法进行了理论研究，详细的阐述了遗传算法的基本原理、研究趋势和在 0- 1 背包问题中的应用；利用 Matlab 仿真平台对 2 个算例进行了测试，证明了遗传算 法求解背包问题的有效性；通过实例分析了种群规模、迭代次数以及变异概率对算 法结果的影响；设计了图形用户界面（GUI） ，实现了参数的输入与仿真结果显示。 关键词：0-1 背包问题；遗传算法；种群规模；Matlab；GUI 第 II页 Abstract This paper introduces the basic concept of 0-1 knapsack problem, solving 0-1 knapsack problem, the paper summarized the traditional methods; Genetic algorithm for the theoretical research, elaborated the basic principle of genetic algorithm in detail, the research trend and application in the 0-1 knapsack problem; Using Matlab simulation platform for 2 example was tested and proved the effectiveness of the genetic algorithm for solving knapsack problem; Analyzes the population size, number of iterations, and the influence of the mutation probability on the algorithm results; Design a graphical user interface (GUI), realize the input parameters and the simulation results show Key Words：0-1 knapsack problem；Genetic algorithm；Popsize；Matlab；GUI 第 III页 目录目录 摘要摘要 .I ABSTRACTII 目录目录 III 前言前言V 第一章第一章 绪绪 论论.1 1.1 背包问题简介背包问题简介1 1.1.1 0-1 背包问题背景.1 1.1.2 背包问题的研究现状.1 1.21.2 遗传算法简介遗传算法简介2 1.2.1 遗传算法的研究现状与发展趋势 3 1.2.2 遗传算法的特点 5 1.2.3 遗传算法分类 6 1.2.4 遗传算法的应用.7 1.31.3 本文主要工作本文主要工作7 第二章第二章 基于遗传算法的基于遗传算法的 0-10-1 背包问题研究背包问题研究.9 2.12.1 遗传算法的思想遗传算法的思想9 2.1.1 遗传算法的数学基础10 2.1.2 遗传算法基本原理12 2.1.3 遗传算法的实现过程13 2.22.2 使用遗传算法求解使用遗传算法求解 0-10-1 背包问题背包问题16 2.32.3 数值试验以及结果分析数值试验以及结果分析.20 2.3.1 算例 1 21 2.3.2 算例 2 24 第三章第三章 GUI 界面设计界面设计 29 3.13.1 概述概述29 3.23.2 GUIGUI 界面设计界面设计29 3.2.1GUI 界面设计步骤.29 3.2.2 界面运行结果33 第四章第四章 结论与展望结论与展望.36 4.1 结论结论.36 4.24.2 展望展望36 总结与体会总结与体会.38 致谢致谢.40 参考文献参考文献.41 附录一附录一 源程序源程序.43 第 IV页 MATLAB 主程序.43 GUI 界面设计程序51 附录二附录二 外文文献翻译外文文献翻译.60 附录三附录三 外文文献原文外文文献原文.71 第 V页 前言前言 背包问题(Knapsack Problem)是一种组合优化NP完全问题，相似的问题经常出 现在商业、组合数学，计算复杂性理论、密码学和应用数学等领域中。背包问题可 分为一维背包，二维背包问题，完全背包问题，多重背包问题、分组背包问题等等。 0-1背包问题作为最基础背包问题，它包含了背包问题的设计状态，方程的最基本思 想，因此，其他背包问题也可以转化成为0-1背包问题进行求解。 遗传算法（Genetic Algorithm）是一类借鉴生物界的进化规律（适者生存，优 胜劣汰遗传机制）演化而来的随机化搜索方法。它是由美国的J.Holland教授1975年 首先提出，其主要特点是直接对结构对象进行操作，不存在求导和函数连续性的限 定；具有内在的并行性和更好的全局寻优能力；采用概率化的寻优方法，能自动获 取和指导优化的搜索空间，自适应地调整搜索方向，不需要确定的规则。遗传算法 的这些性质，已被人们广泛地应用于组合优化、机器学习、信号处理、自适应控制 和人工生命等领域。它是现代有关智能计算中的关键技术。 在论文首先详细介绍了遗传算法的数学基础、基本原理、实现过程，以及使用 遗传算法求解 0-1 背包问题的 2 个算例并得到相关仿真结果，并对仿真结果进行分 析。接着通过设置不同的种群规模、交叉概率和迭代次数来探讨这些算子对于遗传 算法求解背包问题性能的影响。最后在 matlab 环境中进行 GUI 界面设计，通过 GUI 界面可以直观的看到 0-1 背包问题的 2 个算例在不同参数设置下仿真曲线的变化情 况。 1 第一章第一章 绪绪 论论 1.1 背包问题简介背包问题简介 1.1.1 0-1 背包问题背景 背包问题（Knapsack Problem）是由 Markel 和 Hellman1提出的一类具有实际 应用背景的经典 NP 问题。背包问题主要思路是假定一个人拥有大量物品，物品的重 量各不相同，他要选择一些物品放入背包中。物品的重量是已知的，所有可能的物 品也是已知的，但是背包中的物品是保密的，此外还附加了背包的重量限制。对于 大规模的背包问题要列出所有可能的物品在计算上是不可能实现的。在多种背包问 题类型中，0-1 背包问题是最基本的背包问题，其他背包问题往往也可以转化成 0-1 背包问题求解。 在我们的现实生活中许多问题都可以用背包问题来描述，例如工厂中的下料问 题、管理中的资源分配问题、装箱问题、资金预算问题等等都可以建模为背包问题。 此外背包问题还常常作为其他复杂组合优化问题的一个子问题出现，对于由简单结 构组合而成的复杂结构体而言，对简单问题的深入探索往往可以使复杂的问题迎刃 而解。所以在前人研究经验的基础上开展对背包问题的研究具有重要意义。 1.1.2 背包问题的研究现状 Dantzing 在上世纪 50 年代首先进行了开创性的研究，利用贪婪算法2求得了 0-1 背包问题的最优解上界。此后 20 几年背包问题没有较大的发展，直到 1974 年， hoeowitz 和 salmi 利用分支节点法3解答背包问题，他们提出背包问题的可分性， 为该问题的求解指出了一条新型道路。随后 balas 和 zemel 提出了背包问题的“核” 思想使得背包问题的研究获得了较大的发展。上世纪九十年代以后，随着生物仿生 技术和网络技术的飞速发展，各种模拟生物物理规律的并行近似算法不断涌现，例 如：遗传算法已经在 0-1 背包问题上得到了较好的应用，蚂蚁算法等仿生算法也很 好的应用到了组合优化问题中。近几年还出现了许多将几种算法结合起来的混合算 法用来解决背包问题并取得了不错的效果。 2 传统求解背包问题的方法可以概括为精确算法和近似算法，其中精确算法有动 态规划法，回溯法和分支限界法，近似算法有遗传算法，贪婪算法和蚁群算法，由 于精确算法的时间复杂性和空间复杂性等缺点，近年来利用近似算法求解背包问题 已成为重点。 前人已经对背包问题做了一些深入的研究，得到了一些经典的方法，有些方法 对于解决背包问题虽然能得到不错的结果，但是也存在着很多不足之处。首先，很 多算法的计算量都很大，迭代的时间很长。例如：穷举法和动态规划法简单易行,但 是效率很低、鲁棒性不强,只能用于较小规模的问题求解，但在现实问题中有时面对 的问题搜索空间可能非常大，慢慢求解效率就会很低。第二，贪婪算法速度快，爬 坡能力强，但是它适用于搜索局部最优解,可能会陷入局部极值而得不到全局最优解。 第三，蚁群算法可以得到近似最优解,但是当数据规模较大的时候收敛太慢；第四， 新出现的知识进化算法和 DNA 计算等方法也可以有效的解决背包问题，但这些理论 还不太完善，背包问题属于组合最优化问题，在严格意义上求取最优解非常困难， 所以研究高速近似的算法是一个重要的发展方向。与以上几种算法相比遗传算法具 有一定的优势。首先，遗传算法对所求解的优化问题没有太多的数学要求，由于他 的进化特性，搜素过程中不需要问题的内在性质，对于任意形式的目标函数和约束， 无论是线性的还是非线性的，离散的还是连续的都可处理。其次，进化算子的各态 历经性使得遗传算法能够非常有效地进行概率意义的全局搜索。最后，遗传算法对 于各种特殊问题可以提供极大的灵活性来混合构造领域独立的启发式，从而保证算 法的有效性。 本文将对遗传算法做进一步研究并结合应用于背包问题的求解，并通过实验证 明遗传算法对求解背包问题是比较有效的。 1.21.2 遗传算法遗传算法简介简介 遗传算法(Genetic Algorithms)是计算数学中用于解决最优化的搜索算法，是 进化算法的一种。进化算法最初是借鉴了进化生物学中的一些现象而发展起来的， 这些现象包括遗传、突变、自然选择以及杂交等。 遗传算法是模仿自然界生物进化机制发展起来的随机全局搜索和优化方法，它 借鉴了达尔文的进化论和孟德尔的遗传学说。其本质是一种高效、并行、全局搜索 3 的方法，它能在搜索过程中自动获取和积累有关搜索空间的知识，并自适应地控制 搜索过程以求得最优的方法。在遗传法操作使用适者生存的原则，在潜在的解决方 案种群中逐次产生一个近似的最优方案。在遗传算法的每一代中，根据个体在问题 领域中的适应度值和从自然遗传学中借鉴来的再造方法进行选择，产生一个新的近 似解。这个过程导致种群中个体的进化，得到新的个体比原来的个体更能适应环境， 就像自然界中的改造一样。 1.2.1 遗传算法的研究现状与发展趋势 查克斯达尔文的自然选择学说认为生物进化的动力和机制在于自然选择，生 物通过生存斗争，其中具有有利变异的个体容易存活下来，并有更多的机会将这种 变异遗传给后代，而具有不利变异的个体将被淘汰且产生后代的机会也会少。凡是 在生存斗争中获胜的个体对环境的适应性都比较强，因此生物进化的过程就是这种 “物竞天择，适者生存”的过程，这种过程是一个缓慢的、连续和长期的过程。遗 传和变异是决定生物进化的内在因素，推动生物的进化和发展。 基于生物进化理论，从 20 世纪 60 年代起科学家们就尝试用计算的方法模拟生 物遗传和选择进化过程。美国的 Holland 教授于 1975 年出版了关于遗传算法的开创 性著作Adaptation in Natural and Artificial Systems4，开创性的提出了 遗传算法的概念，系统性的阐述了遗传算法的理论，奠定了遗传算法理论的数学基 础，并将其应用到了优化和机器学习的领域中。他将遗传算法定义为适应算法，可 以广泛的应用于系统最优化的研究，1975 年 DeJone 做了大量实验，建立了著名的 DeJone 的测试函数5。1989 年 Goldberg 博士出版本了专著Genetic algorithm in search，optimization and machine learning 6，这是第一本关于遗传算法 的教科书，全面论述了遗传算法的原理与应用，并与实例结合给出了大量的可用的 源程序，使技术专家可以借鉴参考并进行实际应用。在此之后世界范围内掀起了关 于遗传算法研究与应用的高潮。从 1985 年开始关于遗传算法及其应用的国际会议两 年举办一次，很多人工智能领域的专家开始发表有关遗传算法的论文。1991 年 Davis 在他的Hand book of genetic algorithm7一书中介绍了大量的实例。 遗传算法由于能有效解决 NP 类型的组合优化问题和多目标函数优化问题，得到很多 学科的高度重视。在国内，武汉大学成立了一个软件工程国家重点实验室。以进化 4 计算作为一个重要的研究方向，他们的研究成果目前在国内处于领先水平；中国科 技大学的陈国良出版本了关于遗传算法的专著；此外，太原理工大学的谢克明教授 模拟人类思维进化过程提出的思维进化算法也成为进化计算领域的一个重要分支。 遗传算法在应用方面取得的丰硕成果,使人们对它的发展前景充满信心。认识 到这一点,遗传算法的奠基人之一,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 的程序设计环境,使遗 传算法的应用更加方便和快捷。国家组建的工程研究中心应该在这方面发挥更大的 作用。工科数学教育也应有所调整,以适应高新技术发展的需要。例如,工科运筹学 和最优化方法的课程应该适当加入有关遗传算法等方面的内容,以开阔学生的视野, 同时也有利于加快传统课程内容的更新。 1.2.2 遗传算法的特点 a. 算法从问题解的串集开始搜索，而不是从单一解开始。 这是遗传算法与传统算法的极大区别。传统优化算法是从单个初值迭代求最优 解的，容易误入局部最优解。遗传算法从串集开始搜索，覆盖面大，利于全局择优。 b. 求解时使用特定问题的信息极少，容易形成通用算法程序。 由于遗传算法使用时应值这一信息进行搜索，并不需要问题导数等与问题直接 相关的信息。遗产算法只需自适应值和串编码等通用信息，故几乎可以处理任何问 题。 c. 算法有极强的容错能力。 遗传算法的初始串集本身就带有大量与最优解甚远的信息。通过选择、交叉、 变异操作能迅速排除与最优解相差极大的串。这就是一个强烈的过滤过程，并且是 一个并行滤波机制。故而，遗传算法有很高的容错能力。 d. 算法中的选择、交叉、和变异都是随机操作，而不是确定的精确规则。 这说明遗传算法是采用随机方法进行最优解搜索，选择体现了向最优解迫近， 交叉体现了最优解的产生，变异体现了全局最优解的覆盖。 1.2.3 遗传算法分类 （1）混合遗传算法 单用简单的遗传算法在许多情况下不是十分有效，容易产生早熟现象以及局部 寻优能力较差等问题，于是提出了多种混合算法。例如，Ackley 推荐的遗传爬山法； Mathefoud 提出的遗传模拟退火算法；采用遗传算法中增加局部改善运算等等。混 合遗传算法的基本思想是：对于每个新产生的后代在其进入下一代群体之前应用局 6 部优化技术(如爬山法、模拟退火算法等)，使之移动到最近的局部最优点。在混合 遗传算法中，运用启发式方法作局部优化，采用遗传算法作全局最优点的探索。由 于遗传算法与传统优化方法的互补性，混合遗传算法通常比单一算法优越。 （2）并行遗传算法 遗传算法在解决一些实际问题时，由于它一般具有较大的群体规模，需要对较 多的个体进行大量的遗传和进化操作，特别是要对大量的个体进行适应度计算或评 价，从而使得算法的进化运算过程进展缓慢，难以达到计算速度的要求，因而遗传 算法的并行计算问题受到重视。并行遗传算法主要从下列四个方面对其进行改进和 发展。 a.个体适应度评价的并行性。个体适应度的评价或计算在遗传算法的运行过程 中所占用的运行时间比较长。通过对个体适应度并行计算方法的研究可找到并行评 价个体适应度的算法。 b.整个群体中各个个体的适应度评价和并行性群体中各个个体适应度之间无相 互依赖关系，这样各个个体的适应度计算过程就可以相互独立、并行地进行。即不 同个体的适应度计算可以在不同的处理机上同时进行。 c.群体产生过程的并行性。在父代群体产生下一代群体过程中，选择操作只与 个体的适应度有关，而交叉和变异操作只与参加运算的个体编码有关。这样，产生 群体过程中的选择、交叉、变异操作就可以相互独立地并行进行。 d.基于群体分组的并行性。可以对群体按一定的方式进行分组，分组后各组的 个体遗传进化过程可以在不同的处理机上相互独立地进行，在适当的时候，各处理 机之间相互交换信息。 1.2.4 遗传算法的应用 目前，遗传算法在很多科学、工程领域得到广泛的应用。其典型应用领域如下。 a.组合优化。随着组合优化问题规模的增加，其搜索空间也急剧增加，在计算 机上用穷举法不可能求出其最优解，而遗传算法可以在此类问题上寻求问题的满意 解。目前，GA 已经在旅行商问题（TSP）10、背包问题11、网络路由、货仓装载12等 具有 NP 难度的组合优化等方面取得了成功的应用。 7 b.函数优化。函数优化是 GA 的经典应用领域。学者构造了各种复杂的测试函数， 既有连续函数也有离散函数，有高维的也有低维的，有凹的也有凸的，有多峰的也 有单峰的，遗传算法较其他优化方法便于得到较好的结果。函数优化也是对遗传算 法进行评价的常用工具。 c.自动控制，遗传算法在自动控制领域的应用日益增加并取得了较好的成果。 目前 GA 进行系统辨识、模糊控制器设计、航空系统的优化等方面取得了一定的成就。 d.图像处理。遗传算法在图像的处理的图像恢复、图像边缘特征提取方面得到 了成功应用。 e.机器学习。目前基于 GA 的机器学习在很多领域得到了应用。例如：利用 GA 的机器学习来调整人工神经网络的权值等；利用 GA 学习模糊控制的奴隶度函数以改 进模糊控制系统的性能。 f.数据挖掘。数据挖掘就是大型数据库中提取人们感兴趣的、隐含的、有潜在 应用价值的知识。数据挖掘问题可以看做是搜索问题，把数据库看作是搜索空间， 而把挖掘算法看作搜索策略，这样就可以使用遗传算法对数据库中的数据进行搜索， 对于随机产生的一组规则进行进化，直至数据库能被该规则覆盖，进而挖掘出大型 数据库中的隐含的规则。 1.31.3 本文主要工作本文主要工作 a. 介绍了 0-1 背包问题的概念，接着论述求解该问题的各种传统算法，并对 0-1 背包问题进行数学描述。 b. 对遗传算法进行了理论研究。介绍了进化算法的基本理论，对典型的几种进化 算法进行了简要说明，并对遗传算法的基本理论、应用情况和研究趋势做了较 为详细的论述。 c. 应用遗传算法解决 0-1 背包问题，通过设置不同参数探究遗传算法求解背包问 题的可行性并将算法在 Matlab 仿真平台上进行实现。 d. 在 matlab 环境中进行 GUI 界面设计，运行界面中遗传算法主要的参数可通过手 动输入自行修改，同时通过 GUI 界面可以直接观察到仿真曲线的变化情况。 8 第二章第二章 基于遗传算法的基于遗传算法的 0-10-1 背包问题研究背包问题研究 2.12.1 遗传算法遗传算法的思想的思想 遗传算法是模拟生物在自然界中的遗产进化过程而形成的一种自适应全局优化 概率搜索算法。它最早是有没过密歇根大学的 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) 遗传算子：使用比例选择算子、单点交叉算子、基本位变异算子或均匀变异 算子。 9 d) 运行参数：群体大小 M；遗传运算的终止进化代数 T 乃一般取为 100-500； 交叉概率 Pc，一般取为 0.4-0.99；变异概率 Pm，一般取为 0.001-0.1。 对一个需要进行优化计算的实际应用问题，一般可按下述步骤来构造求解该问 题的遗传算法： 第一步：确定决策变量及其各种约束条件，即确定出个体的表现型 X 和问题的 解空间； 第二步：建立优化模型，即确定出目标函数的类型(是求目标函数的最大值。还 是求目标函数的最小值)及其数学描述形式或量化方法； 第三步：确定表示可行解的染色体编码方法，即确定出个体的基因型 X 及遗传 算法的搜索空间； 第四步：确定解码方法，即确定出由个体基因型 x 和个体表现型 X 的对应关系 或转换方法； 第五步：确定个体适应度的量化评价方法，即确定出由目标函数值 f(x)个体适 应度 F(X)的转换规则； 第六步：设计遗传算子，即确定出选择运算、交叉运算、变异运算等遗传算子 的具体操作方法； 第七步：确定遗传算法的有关运行参数，即确定出遗传算法的 M，Pc，Pm 等参 数。 2.1.1 遗传算法的数学基础 遗传算法在机理方面具有搜索过程和优化机制等属性，数学方面的性质可通过 模式定理和积木块假设等分析加以讨论，Markov 链也是分析遗传算法的一个有效工 具。遗传算法的执行过程包括了大量的随机性操作，因此有必要对其数学机理进行 分析。 模式定理151617是由 John Holland 在 1971 年提出的，它是 GA 的基本定理。 它将 GA 的运算过程理解为模式运算过程，并从模式运算的角度解释 GA 的性能特点。 定义 2.1 模式(schema)是一个描述字符串集的模板，该字符串集中的串的某 些位置上存在相似性。因此模式也可解释为相同的构形。 10 定义 2.2 模式阶(schema order)模式 H 中确定位置的个数称为该模式的阶， 记作 o(H)。例如：o(011*1*)=4。 模式阶用来反映不同模式问确定性的差异，模式阶数越高，模式的确定性就越 高，所匹配的样本个数就越少。 定义 2.3 定义距(defining length)模式 H 中的第一个确定位置和最后一个确 定位置之间的距离称为该模式的定义距，记作 (H)。例如：（011*1*）=4。 在遗传操作中，即使阶数相同的模式，也会有不同的性质，而模式的定义距就 反映了这种性质的差异。 模式定理在遗传算子选择、交叉和变异的作用下，具有低阶、短定义距以及平 均适应度高于种群平均适应度的模式在子代中呈指数增长。模式定理可以用数学形 式表示为：(,1)(, ) ( ()/) 1( ()/(1)() cm m H tm H tf HfPHlo HP 式中，m（H,t+1）辨识在 t+1 代种群中存在模式 H 的个数 f(H)表示在 t 代种群包含模式 H 的个体平均适应度 表示个体长度 Pc 表示交叉概率 Pm 表示变异概率 (H) 表示模式 H 的定义距； o（H）表示模式 H 的阶。 模式定理是遗传算法的基本理论，保证了较优的模式(遗传算法的较优解)的数 目呈指数增长，为解释遗传算法机理提供了一种数学工具。 定义 2.4 积木块(building block)在模式定理中所指的具有低阶、短定义距 以及平均适应度高于种群平均适应度的模式被定义为积木块。 积木块假设(Building block hypothesis)18低阶、短定义距、高平均适应度 的基因块 通过选择、交叉和变异等遗传算子的作用，能够互相拼接在一起，形成高阶、 长定义距、高平均适应度的模式，最终接近全局最优解。 满足这个假设的条件比较简单，包括两方面： a) 表现型相近的个体，其基因型相近； b) 遗传因子间相关性低。 11 目前大量的实践支持积木块假设，它在许多领域内都取得了成功，例如平滑多 峰问题、带干扰多峰问题以及组合优化问题等。模式定理保证了较优模式的样本数 呈指数增长，从而满足求最优解的必要条件，即遗传算法存在找到全局最优解的可 能性；而积木块假设指出，遗传算法具备寻找全局最优解的能力，即积木块在遗传 算子的作用下，能生成低阶、短距、高平均适应度的模式，最终生成全局最优解。 虽然模式定理在一定意义上解决了基本遗传算法的有效性，但它仍有以下的缺 点： a) 模式定理只对二进制编码适用，对其他编码方案尚没有相应的结论成立； b) 模式定理只给出了在下世代包含模式 H 的个体数的下限。我们无法据此推断 算法的收敛性； c) 模式定理没有解决算法设计中控制参数选取等问题。 2.1.2 遗传算法基本原理 典型的遗传算法 CGA19 (Canonical Genetic Algorithm)通常用于解决下面这 一类的静态最优化问题：考虑对于一群长度为 L 的二进制编码 bi，i=1，2，n； 有 bi0，lL 给定目标函数 f，有 f(bi)0 同时 f(bi)f(bi+1)，求满足式 maxf(bi)bi0，1L的 bi；。很明显，遗传算法是一种最优化方法，它通过进化 和遗传机理，从给出的原始解群中，不断进化产生新的解，最后收敛到一个特定的 串 bi处，即求出最优解。 长度为 L 的 n 个二进制串 bi(i=1，2，n)组成了遗传算法的初解群，也称为 初始群体。在每个串中，每个二进制位就是个体染色体的基因。根据进化术语，对 群体执行的操作有三种： a) 选择(Selection)：这是从群体中选择出较适应环境的个体。这些选中的个 体用于繁殖下一代。故有时也称这一操作为再生(Reproduction)。由于在 选择用于繁殖下一代的个体时，是根据个体对环境的适应度而决定其繁殖 量的，故而有时也称为非均匀再生(differential reproduction)。 b) 交叉(Crossover)：这是在选中用于繁殖下一代的个体中，对两个不同的个 体的相同位置的基因进行交换，从而产生新的个体。 c) 变异(Mutation)：这是在选中的个体中，对个体中的某些基因执行异向转化。 12 在串 bi中，如果某位基因为 l，产生变异时就是把它变成 0；反之亦然。 遗传算法的原理可以简要给出如下：选择初始值，确定合适的值，完成选择； 进行交叉，变异；重复直到得到最优解这里所指的某种结束准则一般是指个体的适 应度达到给定的阀值；或者个体的适应度的变化率为零。 2.1.3 遗传算法的实现过程 遗传算法是模拟达尔文的生物自然选择学说和自然界的生物进化过程的一种自 适应全局概率搜索算法。在解决具体问题时先大致确定问题的潜在解的一个集合， 这个集合就是算法的初始种群。种群由计算机生成(一般是随机生成)的一定数目的 个体组成，个体就是潜在解的计算机编码，那么我们最后要求的解就由这些初始生 成的个体进化而来的。每个个体具有其自的特征，我们根据这些个体的不同的特征 来确定其存活到下一代的可能性高低，按照优胜劣汰的法则，我们由父代来产生子 代，如此来繁衍。当然在具体的进化过程中为了保持种群多样性防止过早收敛，还 要在其中使个体以一定小概率发生变异。这样在最后满足收敛条件后的种群最优个 体就是问题的近似最优解。 遗传算法的实现过程主要包括编码、产生群体、计算适应度、复制、交换、变 异等操作。概括地讲，遗传算法求解组合优化问题的具体步骤可描述如下： (1)初始化：选择一个群体，即选择一个串或个体的集合 bi，i=l，2，n。这 个初始的群体也就是问题假设解的集合。一般取 n=301-60。通常以随机方法产生串 或个体的集合 bi，i=1，2，n。问题的最优解将通过这些初始假设解进化而求出。 (2)选择：根据适者生存原则选择下一代的个体。在选择时，以适应度为选择原 则。适应度准则体现了适者生存，不适应者淘汰的自然法则。给出目标函数 f，则 f(bi)称为个体 bi的适应度。以选中 bi为下一代个体的次数。 a) 适应度较高的个体，繁殖下一代的数目较多。 b) 适应度较小的个体，繁殖下一代的数目较少；甚至被淘汰。 这样，就产生了对环境适应能力较强的后代。对于问题求解角度来讲，就是选 择出和最优解较接近的中间解。 (3)交叉：对于选中用于繁殖下一代的个体，随机地选择两个个体的相同位置， 按交叉概率 pc。在选中的位置实行交换。这个过程反映了随机信息交换；目的在于 13 产生新的基因组合，也即产生新的个体。交叉时，可实行单点交叉或多点交叉。 例如有个体：S1=100101； S2=010111 选择它们的左边 3 位进行交叉操作，则有： S1=010101；S2=l00111 一般而言，交叉概率取值为 0.25-0.75。 (4)变异：根据生物遗传中基因变异的原理，以变异概率 Pm 对某些个体的某些 位执行变异。在变异时，对执行变异的串的对应位求反，即把 1 变为 0，把 0 变为 1。变异概率 Pm 与生物变异极小的情况一致，所以，Pm 的取值较小，一般取 0.01- 0.2。例如有个体 S=101011。对其的第 l、4 位置的基因进行变异，则有 S1=001111。 单靠变异不能在求解中得到好处。但是，它能保证算法过程不会产生无法进化 的单一群体。因为在所有的个体一样时，交叉是无法产生新的个体的，这时只能靠 变异产生新的个体。也就是说，变异增加了全局优化的特质。 (5)全局最优收敛(Convergence to the global opt imum)当最优个体的适应度 达到给定的阀值，或者最优个体的适应度和群体适应度不再上升时，则算法的迭代 过程收敛，算法结束。否则，用经过选择、交叉、变异所得到的新一代群体取代上 一代群体，并返回到第 2 步即选择操作处继续循环执行。 遗传算法流程图如图 2-1 所示： 随机选择种群数 计算适应度 变异 交叉 停止 满足条件？ 是 否 图 2-1 遗传算法流程图 一个简单的遗传算法被 Goldberg 用来进行轮廓描述并用来举例说明遗传算法的 基本组成。T 代种群用变量 P(t)表示，初始种群 P(o)是随机设计的，简单遗传算法 14 的伪代码描述如下： Procedure GA begin t=0； initialize P(t)； evaluate P(t)； while not finished do begin t=t+l； select P(t) from P(t-1)； reproduce pairs in P(t)； evaluate P(t)； end end 2.22.2 使用遗传算法求解使用遗传算法求解 0-10-1 背包问题背包问题 遗传算法己经在背包问题的求解上取得了一定的成果。运用简单遗传算法求解 背包问题时，若问题的规模不大时能够得到最优解或近似最优解。对于 0-1 背包问 题利用简单遗传算法求解的基本步骤如下： (1)群体的初始化：确定种群规模M、交叉概率Pc、变异概率pm染色体长度N及最 大进化代数maxgen。随机初始化染色体，给出物品体积、物品价值和背包容量C。 (2)产生遗传编码：采用二进制 n 维矢量解 X 作为解空间参数的遗传编码，串 T 的长度等于 n，xi=1 表示该物件装入背包，xi=0 表示该物件没有被装入背包。例如 x=0，1，0，1，0，0，1)表示第 2、4、7 这三个物品被选入背包中。而其他的没有 被选中。也就是说，现在这个背包里只有 2、4、7 这三个物件。这个遗传编码也需 要随机地产生，随机地产生数字 0 或 l，就构成一个染色体串，也就是一个遗传编 码。每产生一个染色体，就对它进行一次检验，如果不满足约束条件，则拒绝接受。 重新产生一个新的染色体；如果产生的染色体满足条件，则接受它作为种群的一名 成员，经过有限次抽样后，得到 M 个可行的染色体。 15 具体说来，最终会产生 M 条染色体，而每条染色体又有 N 个基因，也就是每条 染色长度是 N。所以，初始化后的种群应该是一个 M*N 的二维矩阵。如果 M=5、N=IO，那么初始化后的种群可以看作一个 5 行 10 列的矩阵。比如，初始化后 的种群可以是如下所示： 0 1 1 0 0 0 1 0 1 1 1 1 1 1 0 1 0 0 0 1 1 0 0 1 1 0 1 0 0 0 0 0 0 1 1 0 0 1 1 1 0 0 1 0 1 1 0 0 1 0 （3）适应度函数构造：适应度函数的建立是解决背包问题的关键，首先背包问 题的目标函数和约束条件可表示为：目标函数：，约束条件： 1 ( ) n ii i J xX P 。由于我们之前定义当物件 i 被选入背包时，设定变量 Xi=1，否则是 Xi=0。 1 n ii i X WC 考虑 n 个物件的选择与否，背包内物件的总体积，物件总价值为，如何决定变 1 n ii i X W 1 n ii i X P 量 Xi (i=l，2，n)的值(即确定一个物件组合)使背包内物件总价值为最大。这个问题解的总 组合数有 2 个，其数学模型表示为：时，使得大，Xi=1 或 0（ 1 n ii i X WC 1 n ii i X P i=1，2，n)。 通过对这个问题的具体分析，它的适应度函数应该定义为每次装入背包中的物 品的之和，现在构造它的适应度函数如下：，Xi=1 或 0 1 n ii i FX P （i=1，2，n)。 把所有的物品都放到背包里，那么就可能就会大于背包容量，如果大于的话， 根据价值密度的排序，把价值密度低对应的背包去除，一直到满足设定的背包容量 为止。 适应度计算程序如下： temp_sum=vol*samp_arr; 16 rate=val./vol; %计算每个物体单位体积的价值量，即价值密度 for i=1:POP_NUM j=0; if temp_sum(i) MAX_CAP temp, index=sort(rate, ascend); while temp_sum(i) MAX_CAP j=j+1; if samp_arr(i,index(j)=1 samp_arr(i,index(j)=0; temp_sum(i)=temp_sum(i)- vol(index(j); end end end end (4)选择操作：根据选择概率选择染色体，将上述的个体作为第 1 代，这里采 用以正比于适应度的赌轮随机选择方式，每个体适应度值为 fi，则 i 被选中的概率 psi为：；对于初始化后的种群，先计算出每条染色体的适应度值， 1 / n siii i pff 再计算出其被选择的概率，将它们进行比较，把选择概率最小的一条染色体淘汰掉， 并把选择概率最大的一条染色体进行复制，用这条复制的来替代淘汰的染色体位置。 这样，就完成了对种群的选择操作。相应程序如下： % 选择操作（轮盘赌） fit_sum=sum(fit_arr); rtable=fit_arr./fit_sum; %轮盘，rotary table %生成轮盘，类似于概率分布 For i=2:POP_NUM rtable(i)=rtable(i-1)+rtable(i); end for i=1:POP_NUM 17 p=rand(1); index=1; while p rtable(index) index=index+1; end winner_index(i)=index; end 以上程序是把所有个体的适应度值求和，然后计算每个个体的适应度值占总和 中的比例，比例越大，该个体对应的适应度的范围越大。 (5)交叉操作：判断染色体是否为活的染色体，若为活的染色体，则将染色体进 行交叉，一般采用一点交叉方式，交叉概率为Pc，具体操作是在个体串中随机设定 一个交叉点，实行交叉时，该点前或后的两个个体的部分结构进行互换，并生成两 个新个体。这里尝试用“与或“交叉方法，这一交叉方法使子代继承了双亲的同型 基因，对于双亲的杂型基因， “与或“交叉方法采取了两种不同的“支配“方式， “与”运算是一种0支配l的方式，而“或“运算是一种1支配0的方式，采用“与或” 交叉策略能使优化过程更加迅速的达到全局最优解，获得全局最优解的时间仅为 “一点交叉“策略的19到13。 % 交叉操作 cross_index=1:POP_NUM; %参与交叉的样本的索引 for i=1:POP_NUM temp=unidrnd(POP_NUM-i+1);%在1到POP_NUM-i+1之间取随机数 temp_pos=i+temp-1; temp_val=cross_index(temp_pos); cross_index(temp_pos)=cross_index(i); cross_index(i)=temp_val; end 选择个体中的两个位置，把这两个位置对应的值进行交换，交叉操作先对可能要经行交 叉的样本进行索引，随机得到一个数若这个数小于交叉概率的话进行相邻交叉否则不交叉。 for i=1:2:POP_NUM %相邻两个进行交叉 %随机得到一个数，小于交叉概率的话，进行交叉 18 if rand(1) MAX_CAP temp, index=sort(rate, ascend); while temp_sum(i) MAX_CAP j=j+1; if samp_arr(i,index(j) )=1 samp_arr(i,index(j) = 0; temp_sum(i)=temp_sum(i)-vol(index(j); end end end end % 更新最优值 fit_arr = val*samp_arr; %同上方法一样，采用计算每个个体的总价值 max_val_new, max_index_new= max(fit_arr); fit_worst(count)=min(fit_arr); fit_mean(count)=mean(fit_arr); %如果比上一次的小，用上一次的替换 if max_val_new =MAX_GEN break; end % 选择操作（轮盘赌） fit_sum=sum(fit_arr); rtable=fit_arr./fit_sum; %轮盘，rotary table %生成轮盘，类似于概率分布 for i=2:POP_NUM rtable(i)=rtable(i-1) + rtable(i); end for i=1:POP_NUM p=rand(1); index=1; while p rtable(index) index= index + 1; end winner_index(i)=index; end % 更新样本集 samp_arr=samp_arr(winner_index, :); % 交叉操作 cross_index=1:POP_NUM; %参与交叉的样本的索引 for i=1:POP_NUM temp=unidrnd(POP_NUM - i + 1);%在1到POP_NUM - i + 1之间取随机数 temp_pos=i+temp - 1; temp_val=cross_index(temp_pos); cross_index(temp_pos)= cross_index(i); cross_index(i)=temp_val; end % 交叉操作 for i = 1:2:POP_NUM %相邻两个进行交叉 44 %随机得到一个数，小于交叉概率的话，进行交叉 if rand(1) MAX_CAP temp, index=sort(rate, ascend); while temp_sum(i) MAX_CAP j=j+1; if samp_arr(i,index(j