基于遗传算法的0-1背包问题研究-学士学位论文.doc

设计（论文）专用纸学士学位论文基于遗传算法的0-1背包问题研究学 院： 信息工程与自动化学院 专业年级: 自动化2009级 起止时间： 2013年3月2013年6月 Kun Ming University of Science and TechnologyBachelors Degree ThesisGenetic Algorithm for 0-1 Knapsack ProblemCollege： Faculty of Information Engineering and Automation Profession： Automation Class Three, Grade 2009 Name： Number： Teacher： Position： Experimentalist Time: March 2013June 2013 毕业设计（论文）任务书 信自 院 自动化 专业 09 级学生姓名： 毕业设计（论文）题目： 基于遗传算法的0-1背包问题研究 毕业设计（论文）内容：1.0-1背包问题的数学描述；2.遗传算法原理与应用；3.运用遗传算法求解0-1背包问题，并在matlab环境中实现仿真；4.在matlab环境中进行GUI界面设计，实现相关参数的输入与进化曲线的输出显示。专题（子课题）题目： 专题（子课题）内容：毕业设计（论文）指导教师（签字）： 主 管 教 学 院 （部） 长（签字）： 年 月 日 摘要本文介绍了0-1背包问题的基本概念，综述了求解0-1背包问题的传统方法；对遗传算法进行了理论研究，详细的阐述了遗传算法的基本原理、研究趋势和在0-1背包问题中的应用；利用Matlab仿真平台对2个算例进行了测试，证明了遗传算法求解背包问题的有效性；通过实例分析了种群规模、迭代次数以及变异概率对算法结果的影响；设计了图形用户界面（GUI），实现了参数的输入与仿真结果显示。关键词：0-1背包问题；遗传算法；种群规模；Matlab；GUI第 I页 AbstractThis 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 showKey Words：0-1 knapsack problem；Genetic algorithm；Popsize；Matlab；GUI第 II页 目录摘要IABSTRACTII目录III前言V第一章 绪 论11.1 背包问题简介11.1.1 0-1背包问题背景11.1.2背包问题的研究现状11.2遗传算法简介21.2.1 遗传算法的研究现状与发展趋势31.2.2 遗传算法的特点51.2.3 遗传算法分类61.2.4遗传算法的应用71.3本文主要工作7第二章 基于遗传算法的0-1背包问题研究92.1遗传算法的思想92.1.1遗传算法的数学基础102.1.2遗传算法基本原理122.1.3遗传算法的实现过程132.2使用遗传算法求解0-1背包问题162.3 数值试验以及结果分析202.3.1算例1212.3.2算例224第三章 GUI界面设计293.1概述293.2 GUI界面设计293.2.1GUI界面设计步骤293.2.2界面运行结果33第四章 结论与展望364.1结论364.2展望36总结与体会38致谢40参考文献41附录一 源程序43MATLAB主程序43GUI界面设计程序51附录二 外文文献翻译60附录三 外文文献原文71前言背包问题(Knapsack Problem)是一种组合优化NP完全问题，相似的问题经常出现在商业、组合数学，计算复杂性理论、密码学和应用数学等领域中。背包问题可分为一维背包，二维背包问题，完全背包问题，多重背包问题、分组背包问题等等。0-1背包问题作为最基础背包问题，它包含了背包问题的设计状态，方程的最基本思想，因此，其他背包问题也可以转化成为0-1背包问题进行求解。遗传算法（GeneticAlgorithm）是一类借鉴生物界的进化规律（适者生存，优胜劣汰遗传机制）演化而来的随机化搜索方法。它是由美国的J.Holland教授1975年首先提出，其主要特点是直接对结构对象进行操作，不存在求导和函数连续性的限定；具有内在的并行性和更好的全局寻优能力；采用概率化的寻优方法，能自动获取和指导优化的搜索空间，自适应地调整搜索方向，不需要确定的规则。遗传算法的这些性质，已被人们广泛地应用于组合优化、机器学习、信号处理、自适应控制和人工生命等领域。它是现代有关智能计算中的关键技术。在论文首先详细介绍了遗传算法的数学基础、基本原理、实现过程，以及使用遗传算法求解0-1背包问题的2个算例并得到相关仿真结果，并对仿真结果进行分析。接着通过设置不同的种群规模、交叉概率和迭代次数来探讨这些算子对于遗传算法求解背包问题性能的影响。最后在matlab环境中进行GUI界面设计，通过GUI界面可以直观的看到0-1背包问题的2个算例在不同参数设置下仿真曲线的变化情况。第 V页 设计（论文）专用纸第一章 绪 论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背包问题上得到了较好的应用，蚂蚁算法等仿生算法也很好的应用到了组合优化问题中。近几年还出现了许多将几种算法结合起来的混合算法用来解决背包问题并取得了不错的效果。传统求解背包问题的方法可以概括为精确算法和近似算法，其中精确算法有动态规划法，回溯法和分支限界法，近似算法有遗传算法，贪婪算法和蚁群算法，由于精确算法的时间复杂性和空间复杂性等缺点，近年来利用近似算法求解背包问题已成为重点。前人已经对背包问题做了一些深入的研究，得到了一些经典的方法，有些方法对于解决背包问题虽然能得到不错的结果，但是也存在着很多不足之处。首先，很多算法的计算量都很大，迭代的时间很长。例如：穷举法和动态规划法简单易行,但是效率很低、鲁棒性不强,只能用于较小规模的问题求解，但在现实问题中有时面对的问题搜索空间可能非常大，慢慢求解效率就会很低。第二，贪婪算法速度快，爬坡能力强，但是它适用于搜索局部最优解,可能会陷入局部极值而得不到全局最优解。第三，蚁群算法可以得到近似最优解,但是当数据规模较大的时候收敛太慢；第四，新出现的知识进化算法和DNA计算等方法也可以有效的解决背包问题，但这些理论还不太完善，背包问题属于组合最优化问题，在严格意义上求取最优解非常困难，所以研究高速近似的算法是一个重要的发展方向。与以上几种算法相比遗传算法具有一定的优势。首先，遗传算法对所求解的优化问题没有太多的数学要求，由于他的进化特性，搜素过程中不需要问题的内在性质，对于任意形式的目标函数和约束，无论是线性的还是非线性的，离散的还是连续的都可处理。其次，进化算子的各态历经性使得遗传算法能够非常有效地进行概率意义的全局搜索。最后，遗传算法对于各种特殊问题可以提供极大的灵活性来混合构造领域独立的启发式，从而保证算法的有效性。本文将对遗传算法做进一步研究并结合应用于背包问题的求解，并通过实验证明遗传算法对求解背包问题是比较有效的。1.2遗传算法简介遗传算法(Genetic Algorithms)是计算数学中用于解决最优化的搜索算法，是进化算法的一种。进化算法最初是借鉴了进化生物学中的一些现象而发展起来的，这些现象包括遗传、突变、自然选择以及杂交等。遗传算法是模仿自然界生物进化机制发展起来的随机全局搜索和优化方法，它借鉴了达尔文的进化论和孟德尔的遗传学说。其本质是一种高效、并行、全局搜索的方法，它能在搜索过程中自动获取和积累有关搜索空间的知识，并自适应地控制搜索过程以求得最优的方法。在遗传法操作使用适者生存的原则，在潜在的解决方案种群中逐次产生一个近似的最优方案。在遗传算法的每一代中，根据个体在问题领域中的适应度值和从自然遗传学中借鉴来的再造方法进行选择，产生一个新的近似解。这个过程导致种群中个体的进化，得到新的个体比原来的个体更能适应环境，就像自然界中的改造一样。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类型的组合优化问题和多目标函数优化问题，得到很多学科的高度重视。在国内，武汉大学成立了一个软件工程国家重点实验室。以进化计算作为一个重要的研究方向，他们的研究成果目前在国内处于领先水平；中国科技大学的陈国良出版本了关于遗传算法的专著；此外，太原理工大学的谢克明教授模拟人类思维进化过程提出的思维进化算法也成为进化计算领域的一个重要分支。 遗传算法在应用方面取得的丰硕成果,使人们对它的发展前景充满信心。认识到这一点,遗传算法的奠基人之一,Goldsberg D戏言:“已不再需要水晶球”。今后几年,可以预期,拓广更加多样的应用领域,其中包括各种遗传算法程序设计环境的开发仍将是遗传算法发展的主流。事实上这也是本世纪高新技术迅速发展带有规律性的特点,即面向应用。与此同时,这并不意味着理论研究会被忽视, 这方面同样有大量工作要做。例如: 控制参数的选择；交换和突变这两类最重要的算子的确切作用；并行遗传算法和分布式遗传算法的研究；其他类型生物机制的模仿,如免疫、 病毒、寄生等,以丰富遗传算法的内容,等等。自然,不论从理论还是应用的角度看,最紧迫的应是关于算法收敛性问题的研究,特别是过早收敛的防止。这对遗传算法的实际应用关系重大。 当前一个特别值得重视的趋势是一些面向对象的智能技术,其中主要是模糊逻辑8(Fuzzy Logic, FL ),神经网络9(Neural Network, NN )以及遗传算法等的综合应用。众所周知,FL有较强的知识表达能力,NN 的长处在于自学习,它们与遗传算法相结合形成新的集成化技术,即所谓的混合智能系统(Hybrid Intellectual System )。这一思想在90年代初逐步形成,而由模糊集论的创始人,美国Zadeh LA在1993年于汉城召开的国际模糊系统协会( IFSA )第五届世界会议首先明确提出随后在许多有关的国际学术会议上得到充分体现。应该指出,我国学者对这一趋势的认识较早。例如,清华大学李衍达院士领导的研究集体在几乎同一时期开展了这一重要方向的研究1995年, Zadeh在IFSA的第六届世界会议上再次强调了这一方向的重要性,并且认为上述所谓的混合智能系统的应用将覆盖从消费品生产到核反应堆设计以至证券管理,而“在未来几年中可能无处不在”。就遗传算法本身的研究而言,应该说,我国起步较晚,近几年才陆续看到一些介绍性的文章、不多于两三部的专著以及初步的研究报告，与国外工作比较,一个显著区别是,国内工作多只停留在论文这一层次,几乎没有看到具体实际应用,与研究成果商品化的差距就更远。理论研究与实际应用不够紧密,阻碍了我国高新技术的迅速发展,几乎已经成为顽症。因此,在我国发展遗传算法,当前应该特别重视它的应用和推广普及。学术界要主动和企业界连手开发遗传算法的应用,要重视引进或自行研制类似于SP licer的程序设计环境,使遗传算法的应用更加方便和快捷。国家组建的工程研究中心应该在这方面发挥更大的作用。工科数学教育也应有所调整,以适应高新技术发展的需要。例如,工科运筹学和最优化方法的课程应该适当加入有关遗传算法等方面的内容,以开阔学生的视野,同时也有利于加快传统课程内容的更新。1.2.2 遗传算法的特点a. 算法从问题解的串集开始搜索，而不是从单一解开始。这是遗传算法与传统算法的极大区别。传统优化算法是从单个初值迭代求最优解的，容易误入局部最优解。遗传算法从串集开始搜索，覆盖面大，利于全局择优。b. 求解时使用特定问题的信息极少，容易形成通用算法程序。由于遗传算法使用时应值这一信息进行搜索，并不需要问题导数等与问题直接相关的信息。遗产算法只需自适应值和串编码等通用信息，故几乎可以处理任何问题。c. 算法有极强的容错能力。遗传算法的初始串集本身就带有大量与最优解甚远的信息。通过选择、交叉、变异操作能迅速排除与最优解相差极大的串。这就是一个强烈的过滤过程，并且是一个并行滤波机制。故而，遗传算法有很高的容错能力。d. 算法中的选择、交叉、和变异都是随机操作，而不是确定的精确规则。这说明遗传算法是采用随机方法进行最优解搜索，选择体现了向最优解迫近，交叉体现了最优解的产生，变异体现了全局最优解的覆盖。1.2.3 遗传算法分类（1）混合遗传算法单用简单的遗传算法在许多情况下不是十分有效，容易产生早熟现象以及局部寻优能力较差等问题，于是提出了多种混合算法。例如，Ackley 推荐的遗传爬山法；Mathefoud 提出的遗传模拟退火算法；采用遗传算法中增加局部改善运算等等。混合遗传算法的基本思想是：对于每个新产生的后代在其进入下一代群体之前应用局部优化技术(如爬山法、模拟退火算法等)，使之移动到最近的局部最优点。在混合遗传算法中，运用启发式方法作局部优化，采用遗传算法作全局最优点的探索。由于遗传算法与传统优化方法的互补性，混合遗传算法通常比单一算法优越。（2）并行遗传算法遗传算法在解决一些实际问题时，由于它一般具有较大的群体规模，需要对较多的个体进行大量的遗传和进化操作，特别是要对大量的个体进行适应度计算或评价，从而使得算法的进化运算过程进展缓慢，难以达到计算速度的要求，因而遗传算法的并行计算问题受到重视。并行遗传算法主要从下列四个方面对其进行改进和发展。a.个体适应度评价的并行性。个体适应度的评价或计算在遗传算法的运行过程中所占用的运行时间比较长。通过对个体适应度并行计算方法的研究可找到并行评价个体适应度的算法。b.整个群体中各个个体的适应度评价和并行性群体中各个个体适应度之间无相互依赖关系，这样各个个体的适应度计算过程就可以相互独立、并行地进行。即不同个体的适应度计算可以在不同的处理机上同时进行。c.群体产生过程的并行性。在父代群体产生下一代群体过程中，选择操作只与个体的适应度有关，而交叉和变异操作只与参加运算的个体编码有关。这样，产生群体过程中的选择、交叉、变异操作就可以相互独立地并行进行。d.基于群体分组的并行性。可以对群体按一定的方式进行分组，分组后各组的个体遗传进化过程可以在不同的处理机上相互独立地进行，在适当的时候，各处理机之间相互交换信息。1.2.4遗传算法的应用目前，遗传算法在很多科学、工程领域得到广泛的应用。其典型应用领域如下。a.组合优化。随着组合优化问题规模的增加，其搜索空间也急剧增加，在计算机上用穷举法不可能求出其最优解，而遗传算法可以在此类问题上寻求问题的满意解。目前，GA已经在旅行商问题（TSP）10、背包问题11、网络路由、货仓装载12等具有NP难度的组合优化等方面取得了成功的应用。b.函数优化。函数优化是GA的经典应用领域。学者构造了各种复杂的测试函数，既有连续函数也有离散函数，有高维的也有低维的，有凹的也有凸的，有多峰的也有单峰的，遗传算法较其他优化方法便于得到较好的结果。函数优化也是对遗传算法进行评价的常用工具。c.自动控制，遗传算法在自动控制领域的应用日益增加并取得了较好的成果。目前GA进行系统辨识、模糊控制器设计、航空系统的优化等方面取得了一定的成就。d.图像处理。遗传算法在图像的处理的图像恢复、图像边缘特征提取方面得到了成功应用。e.机器学习。目前基于GA的机器学习在很多领域得到了应用。例如：利用GA的机器学习来调整人工神经网络的权值等；利用GA学习模糊控制的奴隶度函数以改进模糊控制系统的性能。f.数据挖掘。数据挖掘就是大型数据库中提取人们感兴趣的、隐含的、有潜在应用价值的知识。数据挖掘问题可以看做是搜索问题，把数据库看作是搜索空间，而把挖掘算法看作搜索策略，这样就可以使用遗传算法对数据库中的数据进行搜索，对于随机产生的一组规则进行进化，直至数据库能被该规则覆盖，进而挖掘出大型数据库中的隐含的规则。1.3本文主要工作a. 介绍了0-1背包问题的概念，接着论述求解该问题的各种传统算法，并对0-1背包问题进行数学描述。b. 对遗传算法进行了理论研究。介绍了进化算法的基本理论，对典型的几种进化算法进行了简要说明，并对遗传算法的基本理论、应用情况和研究趋势做了较为详细的论述。c. 应用遗传算法解决0-1背包问题，通过设置不同参数探究遗传算法求解背包问题的可行性并将算法在Matlab仿真平台上进行实现。d. 在matlab环境中进行GUI界面设计，运行界面中遗传算法主要的参数可通过手动输入自行修改，同时通过GUI界面可以直接观察到仿真曲线的变化情况。第二章 基于遗传算法的0-1背包问题研究2.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) 遗传算子：使用比例选择算子、单点交叉算子、基本位变异算子或均匀变异算子。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)是一个描述字符串集的模板，该字符串集中的串的某些位置上存在相似性。因此模式也可解释为相同的构形。定义2.2 模式阶(schema order)模式H中确定位置的个数称为该模式的阶，记作o(H)。例如：o(011*1*)=4。模式阶用来反映不同模式问确定性的差异，模式阶数越高，模式的确定性就越高，所匹配的样本个数就越少。定义2.3 定义距(defining length)模式H中的第一个确定位置和最后一个确定位置之间的距离称为该模式的定义距，记作(H)。例如：（011*1*）=4。在遗传操作中，即使阶数相同的模式，也会有不同的性质，而模式的定义距就反映了这种性质的差异。模式定理在遗传算子选择、交叉和变异的作用下，具有低阶、短定义距以及平均适应度高于种群平均适应度的模式在子代中呈指数增长。模式定理可以用数学形式表示为：式中，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) 遗传因子间相关性低。目前大量的实践支持积木块假设，它在许多领域内都取得了成功，例如平滑多峰问题、带干扰多峰问题以及组合优化问题等。模式定理保证了较优模式的样本数呈指数增长，从而满足求最优解的必要条件，即遗传算法存在找到全局最优解的可能性；而积木块假设指出，遗传算法具备寻找全局最优解的能力，即积木块在遗传算子的作用下，能生成低阶、短距、高平均适应度的模式，最终生成全局最优解。虽然模式定理在一定意义上解决了基本遗传算法的有效性，但它仍有以下的缺点：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)：这是在选中的个体中，对个体中的某些基因执行异向转化。在串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。在选中的位置实行交换。这个过程反映了随机信息交换；目的在于产生新的基因组合，也即产生新的个体。交叉时，可实行单点交叉或多点交叉。例如有个体：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)是随机设计的，简单遗传算法的伪代码描述如下：Procedure GAbegint=0；initialize P(t)；evaluate P(t)；while not finished dobegint=t+l；select P(t) from P(t-1)；reproduce pairs in P(t)；evaluate P(t)；endend2.2使用遗传算法求解0-1背包问题遗传算法己经在背包问题的求解上取得了一定的成果。运用简单遗传算法求解背包问题时，若问题的规模不大时能够得到最优解或近似最优解。对于0-1背包问题利用简单遗传算法求解的基本步骤如下：(1)群体的初始化：确定种群规模M、交叉概率Pc、变异概率pm染色体长度N及最大进化代数maxgen。随机初始化染色体，给出物品体积、物品价值和背包容量C。(2)产生遗传编码：采用二进制n维矢量解X作为解空间参数的遗传编码，串T的长度等于n，xi=1表示该物件装