遗传算法设计及其并行实现.doc

编 号： 审定成绩： XXXX大学毕业设计（论文）设计（论文）题目：遗传算法设计及其并行实现学 院 名 称 ：计算机学院学 生 姓 名 ：X X专 业 ：计算机科学与技术班 级 ：学 号 ：指 导 教 师 ：X X X答辩组 负责人 ：填表时间： 2010 年 5 月XXXX大学教务处遗传算法设计及其并行实现摘要遗传算法（Genetic AlgorithmGA），是模拟达尔文的遗传选择和自然淘汰的生物进化过程的计算模型。 传统的遗传算法虽然具有隐含的并行性，但目前大多为串行遗传算法。串行遗传算法在解决一些实际问题时，由于需要较多的个体数量和大量的计算，使得进化过程比较缓慢，难以达到实时的要求。因此并行遗传算法（Parallel Genetic AlogrithmPGA）就受到了较大的重视，并且已经成为目前遗传算法研究的主要课题。遗传算法与并行计算机相结合，能把并行机的高速性和遗传算法固有的并行性两者的长处彼此结合起来。 本论文设计和实现了简单遗传算法（GA），和并行遗传算法（PGA）两个例子。包括：1. Rosenbrock函数。2. TSP问题。关键字：遗传算法 并行遗传算法 TSP问题The Design and Parallel Realization of Genetic AlgorithmAbstractGenetic Algorithm is the computation model which simulating the biological evolution process of Darwins heredity choice and the natural selection. Although the traditional genetic algorithm has the concealment parallelism, but realized the method in essentially still was actually serial. When this kind of serial genetic algorithm solves some actual problems, it will need lots of individuals and computations, and this will causes the evolution process to be so slow that difficult to meets the real-time requirements. Therefore, the Parallel Genetic Algorithm has received a big value, and already becomes the main topic at genetic algorithm research. With the PGA, you can unites the parallel machines high speed with genetic algorithms inherent parallelism. The present paper designed and has realized simple heredity algorithm (GA), and parallel genetic algorithm (PGA) with two examples. Including:1. Rosenbrock function.2. TSP problem.Keywords: Genetic Algorithm GA Parallel Genetic Algorithm PGA TSP目录毕业设计（论文）任务书I摘要VAbstractVI第一章 遗传算法简介1第一节 遗传算法的生物学基础1一、 遗传和变异1二、 进化1三、 遗传与进化的系统观2第二节 遗传算法简介2第三节 遗传算法的特点4第四节 遗传算法的应用情况5第二章 遗传算法的基本原理和实现技术7第一节 模式定理（schemata theorem）7一、 模式7二、 模式定理7第二节 编码方法9一、 编码概念9二、 编码技术9第三节 群体设定10第四节 适应度函数11一、 目标函数到适应度函数的映射11二、适应度尺度变换（适应度函数定标）11第五节 遗传操作12一、选择算子12二、交叉算子12三、变异算子13第六节 遗传算法的性能分析13一、在线性性能评估14二、离线性能评估14第三章 遗传算法的求解构造步骤及应用举例15第一节 遗传算法的求解步骤15一、遗传算法的伪码描述和形式化定义15二、遗传算法的求解步骤及其框图16第二节 遗传算法的构造步骤18第三节 基本遗传算法在函数优化中的应用举例19第四章 并行遗传算法25第一节 遗传算法并行化的目的25第二节 遗传算法在并行实现上的困难25第三节 遗传算法的并行性分析25一、 个体适应度评价的并行性26二、 群体中各个个体适应度评价的并行性26三、 子代群体产生过程的并行26四、 基于群体分组的并行性26第四节 遗传算法的并行化途径26一、 步进模型26二、 粗粒度模型27三、 细粒度模型27第五节 并行程序设计环境MPICH简介28一、 什么是MPI28二、 MPI的语言绑定28三、 MPICH29第五章 用并行遗传算法实现TSP问题30第一节 旅行商问题描述30第二节 编码方法与群体初始化30一、 编码30二、 种群初始化31第三节 解码设计32第四节 个体适应度评价方法设计33第五节 遗传算子设计33一、 选择算子设计33二、 交叉算子设计34三、 变异算子设计34第六节 程序的并行化改造35一、 算法描述35二、 并行化的实现35第七节 运行参数的确定和实验结果分析36一、 运行参数的确定36二、实验结果及分析40结论43参考文献44致谢45英文翻译46英文原文46中文翻译55附录65附录1 求解Rosenbrock函数最大值源码65附录2 TSP问题源码73第一章 遗传算法简介第一节 遗传算法的生物学基础生物在自然界中生存繁衍，显示出其对自然环境的自适应能力。受此启发，人们致力于对生物各种生存特性的研究和行为模拟，为人工自适应系统的设计和开发提供了广阔的前景。遗传算法（Genetic Algorithm，简称GA）就是这种生物行为的计算机模拟中令人瞩目的成果。遗传算法所借鉴的就是被人们所广泛接受的达尔文的自然选择（Natural Selection） 学说。自然选择学说中最重要的三个部分是遗传、变异和进化。 一、 遗传和变异构成生物的基本结构和功能单位是细胞（Cell）。细胞中含有的一种微小的丝状化合物称为染色体（Chromosome），生物的所有遗传信息都包含在这个复杂而又微小的染色体中。遗传信息是由基因（Gene）组成的，生物的各种性状由其相应的基因所控制，基因是遗传的基本单位。细胞通过分裂具有自我复制的能力，在细胞分裂的过程中，其遗传基因也同时被复制到下一代，从而其性状也被下一代所继承。人们已经明白，控制并决定生物遗传性状的染色体主要是由一种叫做脱氧核糖核酸（Deoxyribonucleic Acid，简称DNA）的物质所构成。另外，低等生物中还含有一种叫做核糖核酸（Ribonucleic Acid。简称RNA）的物质，它的作用和结构与DNA相似。基因就是DNA或者RNA长链结构中占有一定位置的基本遗传单位。遗传基因在染色体中所占的位置称为基因座（Locus），基因的所有可能的取值叫做等位基因（Allele）。某种生物所特有的基因及其构成形式称为该生物的基因型（Genotype），而该生物在环境中呈现出的相应性状称为该生物的表现型（Phenotype）。一个细胞核中所有染色体所携带的遗传信息的全体称为一个基因组（Genome）细胞在分列时，遗传物质DNA通过复制（Reproduction）而转移到新产生的细胞中，新细胞就继承了旧细胞的基因。有性生殖生物在繁殖下一代时，两个同源染色体之间通过交叉（Crossover）而重组，即在两个染色体的某一相同位置处DNA被切断，其前后两串分别交叉组合而形成两个新的染色体。除此之外，在进行细胞复制时，虽然概率很小，但是也有可能产生某些复制差错，从而使DNA发生某种变异（Mutation），产生出新的染色体。这些新的染色特表现出新的性状。如此这般，遗传基因或染色体在遗传的过程中由于各种各样的原因而发生着变化。 二、 进化生物在其延续生存的过程中，逐渐适应生存环境，使得其品质不断得到改良，这种生命现象称为进化（Evolution）。生物的进化是以集团的形式共同进行的，这样的一个集团称为群体（Population），组成群体的单个生物体称为个体（Individual），每一个个体对其生存环境都由不同的适应能力，这种适应能力称为个体的适应度（Fitness）。达尔文的自然选择学说是现代进化论的主题。现代进化论认为，通过不同生物间的交配以及其他一些原因，生物的基因有可能发生变异而形成一种新的生物基因，这部分变异了的基因也将遗传到下一代。虽然这种变化的概率是可以预测的，但是具体哪一个个体发生变化却是偶然的。这种新的基因依据其与环境的适应程度决定其增殖能力，适应生存环境的基因逐渐增多，而不适应生存环境的基因逐渐减少。通过这种自然的选择，物种将逐渐的向适应于生存化环境的方向进化，从而产生出优良的物种。 三、 遗传与进化的系统观虽然人们还未完全揭开遗传与进化的奥秘既没有完全掌握其机制，也不完全清楚染色体编码和译码过程的细节，更不完全了解其控制方式，但遗传与进化的以下几个特点4却为人们所共识：1生物的所有遗传信息都包含在其染色体中，染色体决定了生物的性状。2染色体是由基因及其有规律的排列所构成的，遗传和进化过程发生在染色体上。3生物的繁殖过程是由其基因的复制过程来完成的。4通过同源染色体之间的交叉或染色体的变异会产生新的物种使生物呈现新的性状。5对环境适应性好的基因或染色体经常比适应性差的基因或染色体有更多的机会遗传到下一代。第二节 遗传算法简介遗传算法是模仿生物遗传学和自然选择机理，通过人工方式构造的一类优化搜索算法，是对生物进化过程进行的一种数学仿真，是进化计算的最重要的形式。遗传算法用与传统的数学模型截然不同。它模拟自然界优胜劣汰的进化现象，把搜索空间映射为遗传空间，把可能的解编码成一个向量染色体，向量的每个元素称为基因。通过不断计算各染色体的适应值，选择最好的染色体，获得最优解。它为那些难以找到传统数学模型的难题找出了一个解决方法。自从霍兰德（Holland）于1975年在它的著作“Adaptation in Natural and Artificial Systems”9中首次提出遗传算法以来，经过近30年的研究，现在已发展到一个比较成熟的阶段，并且在实际中得到很好的应用。遗传算法是具有“生成+检测”(generateandtest)的迭代过程的搜索算法。它的基本处理流程如图1-1所示。遗传算法是一种群体型操作，该操作以群体中的所有个体为对象。选择(selection)、交叉(crossover)和变异(mutation)是遗传算法的3个主要操作算子，它们构成了遗传操作(genetic operation)，使遗传算法具有了其它传统方法所没有的特性。遗传算法中包含了如下4个基本要素2：1染色体编码方法。在遗传算法中，将 n 维决策向量用 n 个记号所组成的符号串 X 来表示：（1.1）把每个看作一个遗传基因，它的所有可能取值称为等位基因，这样，X 就可以看作由 n 个遗传基因所组成的一个染色体。在一般情况下，染色体长度n是固定的，但是对一些问题 n 也可以是变化的。根据不同的情况，等位基因可以是一组整数，也可以是某一范围内的实数，或者纯粹一个记号。最简单的等位基因是由0和1这两个整数组成的，相应的染色体就可以表示成一个二进制符号串。遗传算法中，决策变量 X 组成了问题的解空间。对问题最优解的搜索是通过对染色体 X 的搜索过程来进行的。图1-1 简单遗传算法框图 2个体适应度评价。基本遗传算法按与个体适应度成正比的概率来决定当前群体中每个个体遗传到下一代群体中的机会多少。为正确计算这个概率，这里要求所有个体的适应度必须为正数或零。这样，根据不同种类的问题，必须预先确定好由目标函数值到个体适应度之间的转换规则，特别是要预先确定好当目标函数值为负数时的处理方法。3遗传算子。基本遗传算法使用下述三种遗传算子：选择算子选择或复制操作的目的是为了从当前的群体中选出优良的个体，使他们有机会作为父代为下一代繁殖子孙。判断个体优良与否的准则就是各自的适应度。这一操作是借用了达尔文适者生存的进化原则。也就是说，个体适应度越高，其被选择的机会就越多。选择操作的实现方式很多，比如有赌轮选择，最佳个体保留选择，等等。交叉算子 简单的交叉（一点交叉）操作可分成两步：首先对配对库中的个体进行随机配对；其次，在配对的个体中随机的设定交叉处，配对个体彼此交换部分信息。具体的操作及图示在下面一章作详细的说明。 需要指出的是，交叉操作是遗传算法中最主要的遗传操作。通过交叉操作得到的新群体，个体适应度的平均值和最大值都有了明显的提高。实际上，对于几十到几百个变量组成的函数，遗传算法照样能够不依靠任何搜索空间的外部知识而仅用适应度函数来指导和优化搜索的方向。变异算子变异操作是按位进行的，即把某一位的内容进行变异。对于二进制编码个体来说，如果某位原来为0，则通过变异操作就变成了1，反之亦然。变异操作同样也是随机进行的。一般而言，变异概率都取得很小。 变异操作是十分微妙的遗传操作，它需要和交叉操作妥善配合使用，目的是挖掘群体中个体的多样性，克服有可能限于局部解的弊病。这一点在下一章会作进一步的讨论。4遗传算法的运行参数。基本遗传算法有下述4个运行参数需要提前设定： M：群体大小 T：遗传运算的终止进化代数 Pc：交叉概率，一般取为0.40.99。 Pm：变异概率，一般取为0.00010.1。需要说明的是，这4个运行参数对遗传算法的求解结果和求解效率都有一定的影响，但目前尚无合理选择它们的理论依据。在遗传算法的实际应用中，往往需要经过多次试算后才能确定出这些参数合理的取值大小或取值范围。第三节 遗传算法的特点随着优化问题种类的不同以及问题规模的扩大，要寻求一种能以有限的代价来解决搜索和优化的通用方法遗传算法为我们提供的一个有效的途径它不同于传统的搜索和优化方法。重要区别在于4：1自组织、自适应和自学习性(智能性)。应用遗传算法求解问题时在编码方案、适应度函数及遗传算子确定后算法将利用进化过程中获得的信息自行组织搜索。由于基于自然的选择策略为“适者生存。不适应者被淘汰”，因而适应度大的个体具有较高的生存概率。通常，适应度大的个体具有更适应环境的基因结构再通过基因重组和基因突变等遗传操作，就可能产生更适应环境的后代进化算法的这种自组织、自适应特征，使它同时具有能根据环境变化来自动发现环境的特性和规律的能力 自然选择消除了算法设计过程中的一个最大障碍，即需要事先描述问题的全部特点并要说明针对问题的不同特点算法应采取的措施。因此，利用遗传算法的方法我们可以解决那些复杂的非结构化问题。2遗传算法的本质并行性遗传算法按并行方式搜索一个种群数目的点，而不是单点。它的并行性表现在两个方面，一是遗传算法是内在并行的(inherent parallelism)即遗传算法本身非常适合大规模并行。最简单的并行方式是让几百甚至数千台计算机各自进行独立种群的演化计算运行过程中甚至不进行任何通信(独立的种群之间若有少量的通信一般会带来更好的结果)等到运算结束时才通信比较选取最佳个体。这种并行处理方式对并行系统结构没有什么限制和要求，可以说，遗传算法适合在目前所有的并行机或分布式系统上进行并行处理而且对并行效率没有太大影响。二是遗传算法的内含并行性(implicit parallelism)。由于遗传算法采用种群的方式组织搜索，因而可同时搜索解空间内的多个区域，并相互交流信息。使用这种搜索方式，虽然每次只执行与种群规模n成比例的计算，但实质上已进行了大约次有效搜索这就使遗传算法能以较少的计算获得较大的收益。3遗传算法不需要求导或其他辅助知识，而只需要影响搜索方向的目标函数和相应的适应度函数。4遗传算法强调概率转换规则，而不是确定的转换规则。5遗传算法可以更加直接地应用。6遗传算法对给定问题，可以产生许多的潜在解，最终选择可以由使用者确定(在某些特殊情况下，如多目标优化问题不止一个解存在，有一组paretic最优解。这种遗传算法对于确认可替代解集而言是特别合适的)。第四节 遗传算法的应用情况 遗传算法提供了一种求解复杂系统优化问题的通用框架它不依赖于问题的具体领域，对问题的种类有很强的鲁棒性，所以广泛应用于很多学科。下面是遗传算法的一些主要应用领域：1函数优化函数优化是遗传算法的经典应用领域，也是对遗传算法进行性能评价的常用算例。很多人构造出了各种各样的复杂形式的测试函数，有连续函数也有离散函数。有凸函数也有凹函数，有低维函数也有高维函数。有确定函数也有随机函数，有单峰函数也有多峰函数等人们用这些几何特性各异的函数来评价遗传算法的性能。而对于一些非线性、多摸型、多目标的函数优化问题，用其他优化方法较难求解，遗传算法却可以方便地得到较好的结果。2组合优化随着问题规模的扩大，组合优化问题的搜索空间急剧扩大，有时在目前的计算机上用枚举法很难或者甚至不可能得到其精确最优解。对于这类复杂问题，人们已意识到应把精力放在寻求其满意解上，而遗传算法则是寻求这种满意解的最佳工具之一。实践证明，遗传算法对于组台优化中的NP完全问题非常有效，例如，遗传算法已经在求解旅行商问题、背包问题、装箱问题、图形划分问题等方面得到成功的应用。3生产调度问题生产调度问题在许多情况下所建立起来的数学模型难以精确求解，即使经过一些简化之后可以进行求解也会因简化太多而使得求解结果与实际相差甚远。因此，目前在现实生产中也主要靠一些经验进行调度，遗传算法已成为解决复杂调度问题的有效工具，在单件生产车间调度、流水线生产车间调度、生产规划、任务分配等方面遗传算法都得到了有效的应用。4自动控制在自动控制领域中许多与优化相关的问题需要求解，遗传算法的应用日益增加并显示了良好的效果。倒如用遗传算法进行航空控制系统的优化、基于遗传算法的模糊控制器优化设计、基于遗传算法的参数辨识、利用遗传算法进行人工神经网络的结构优化设计和权值学习，部显示出了遗传算法在这些领域中应用的可能性。5机器人智能控制机器人是一类复杂的难以精确建模的人工系统而遗传算法的起源就来自于对人工自适应系统的研究所以机器人智能控制理所当然地成为遗传算法的一个重要应用领域。例如遗传算法已经在移动机器人路径规划、关节机器人运动轨迹规划、机器人逆运动学求解、细胞机器人的结构优化和行动协调等方面得到研究和应用。6图像处理和模式识别图像处理和模式识别是计算机视觉中的一个重要研究领域。在图像处理过程中如扫描、特征提取、图像分割等不可避免地会产生一些误差这些误差会影响到图像处理和识别的效果。如何使这些误差最小是使计算机视觉达到实用化的重要要求。遗传算法在图像处理中的优化计算方面是完全胜任的。目前已在图像恢复、图像边缘特征提取、几何形状识别等方面得到了应用7人工生命人工生命是用计算机等人工媒体模拟或构造出具有自然生物系统特有行为的人造系统。自组织能力和自学习能力是人工生命的两大主要特征。人工生命与遗传算法有着密切的关系，基于遗传算法的进化模型是研究人工生命现象的重要理论基础。虽然人工生命的研究尚处于启蒙阶段，但遗传算法已在其进化模型、学习模型、行为模型等方面显示了初步的应用能力。可以预见遗传解法在人工生命及复杂自适应系统的模拟与设计、复杂系统突现性理论研究中，将得到更为深入的发展。8遗传程序设计Koza发展了遗传程序设计的概念，他使用了以LISP语言所表示的编码方法基于对一种树型结构所进行的遗传操作自动生成计算机程序。虽然遗传程序设计的理论尚未成熟，应用也有一些限制，但它已有一些成功的应用。9机器学习学习能力是高级自适应系统所应具备的能力之一、基于遗传算法的机器学习特别是分类器系统，在许多领域得到了应用。例如遗传算法被用于模糊控制规则的学习，利用遗传算法学习隶属度函数，从而更好地改进了模糊系统的性能基于遗传算法的机器学习可用于调整人工神经网络的连接权也可用于神经网络结构的优化设计。分类器系统在多机器人路径规划系统中得到了成功的应用。第二章 遗传算法的基本原理和实现技术遗传算法是一个以适应度函数为依据，通过对群体个体施加遗传操作，实现群体内个体结构重组的迭代处理过程。在这一过程中，群体个体一代代得以优化并逐渐逼近最优解。但是作为一种智能搜索算法，它的本质内涵是什么呢？这一章的开始先在理论上对此作一番分析。第一节 模式定理（schemata theorem）一、 模式模式（schema）是一个描述字符串集的模板，该字符串集中的串的某些位置上存在相似性。例如二值字符集0,1，由此可以产生通常的0,1字符串。现在增加一个通配符“*” ，“*”既可以被当作“0”，又可以被当作“1”。这样二值字符集0,1就可扩展成三值字符集0,1,*。【定义 2.1】基于三值字符集0,1,*所产生的能描述具有某些结构相似性的0、1字符串集的字符串称作模式5。 引入模式概念并不是仅仅为了描述上的方便。在引入模式概念前，我们看到的遗传算法是：在某一代中，N 个互不相同的串在选择、交叉、变异等遗传算子的作用下产生下一代的 N 个新的互不相同的串。那么，两代之间究竟保留了什么性质，破坏了什么性质，我们无从得知，因为我们所看到的串都是相互独立的，互不联系的。在引入模式概念后，我们看到的一个串实际上隐含着多个模式（长度为的串隐含着个模式），一个模式可以隐含在多个串中，不同的串之间通过模式而相互联系。遗传算法中串的运算实质上是模式的运算。因此通过分析模式在遗传操作下的变化，就可以了解什么性质被延续，什么性质被丢弃，从而把握遗传算法的实质，这正是模式定理所要揭示的内容。二、 模式定理首先定义两个重要的概念：模式阶（schema order）和定义长度（schema defining length）。 【定义2.2】模式H 中确定位置的个数称作该模式的模式阶5，记作O(H)。比如模式 011*1*的阶数为 4，而模式 0*为 1。显然，一个模式的阶数越高，其样本数就越少，因而确定性越高。 但是，模式阶并不能反映模式的所有性质。即使具有同阶的模式，在遗传操作下，也会有着不同的性质。为此，再引入定义长度的概念。【定义2.3】模式H 中第一个确定位置和最后一个确定位置之间的距离称作该模式的定义距离或定义长度5，记作(H)。 比如模式011*1*的定义长度为4，而模式0*为0。 有了这两个概念，就可以开始讨论模式在遗传操作下的变化。令 A(t)表示第t代群体，以(j =1,2, ,n)表示一代中的 第j个个体串。第t代中，群体A(t)中模式H 所能匹配的样本数为m，记作m(H, t)。下面对基本遗传算法在选择算子、交叉算子和变异算子的连续作用下，模式m(H, t)的变化情况进行分析。l 选择算子的作用 一个串是以概率进行选择的，其中是个体的适应度。假设一代中群体大小为n，且个体两两互不相同，则模式H 在第t +1代中的样本数m(H, t+1)为 (2.1) 其中 f(H)是模式H 所有样本的平均适应度。令群体平均适应度为则有 (2.2) 可见，模式的增长（减少），即样本数的增加（减少），依赖于模式的平均适应度与群体平均适应度之笔：那些平均适应度高于群体平均适应度的模式将在下一代中得以增长；而那些平均适应度低于群体平均适应度的模式将在下一代中减少。 若再假设模式H 的平均适应度总是高出群体平均适应度的c倍，则式(2.2)可以改写成为 (2.3)由此可见，m(H, t)为一等比级数，其通项公式为 (2.4)从式(2.4)可知： 如果c >0，则m(H, t)呈指数级增长；如果c <0，则m(H,t)呈指数级减少。l 交叉算子的作用这里以常用的单点交叉算子为例进行研究。 当随机设置的交叉点在模式的定义长度之内时，将有可能破坏该模式；而当随机设置的交叉点在模式的定义长度之外时，肯定不会破坏该模式。再考虑到交叉操作本身是以交叉概率 p 发生的，所以模式H 的生存概率下界为： (2.5) 这样，经过选择算子和交叉算子作用之后，模式H 的样本数满足下式： (2.6) 由上式可以看出，在其它值固定的情况下(c >0)， (H)越小，则m(H, t)越容易呈指数级增长； (H)越大，则m(H ,t)越不容易呈指数级增长。l 变异算子的作用 这里以基本位变异算子为例进行研究。 假定串的某一位发生改变的概率为，则该位置不变的概率为1 ，而模式H 在变异算子作用下若要不受破坏，则其中所有的确定位置必须保持不变。因此模式H 保持不变的概率为(1-)O(H)，其中O(H)为模式H 的阶数。当 <<1时，模式H 在变异算子作用下的生存概率为： =(1)O(H) 1*O(H) (2.7） 综上所述，模式H 在遗传算子选择、交叉和变异的共同作用下，其子代的样本数为 (2.8) 由上式，就可以得到模式定理： 【定义2.4】（模式定理） 在遗传算子选择，交叉和变异的作用下，具有低阶、短的定义长度，并且平均适应度高于群体平均适应度的模式将按指数级增长。 模式定理是遗传算法的理论基础。第二节 编码方法一、 编码概念遗传算法主要通过遗传操作对群体中具有某种结构形式的个体施加结构重组处理，从而不断的搜索出群体中个体间的结构相似性。所以遗传算法不能直接处理问题空间的参数，必须把它们转换成遗传空间的由基因按一定结构组成的染色体或个体。这一操作就是编码。更一般性的定义为：由问题空间向遗传算法空间的映射称作编码（Encoding）。反之，由遗传算法空间向问题空间的映射称作译码（Decoding）8。二、 编码技术遗传算法最常用的编码方法是二进制编码，其编码方法如下。假设某一参数的取值范围是A,B, A<B。用长度为的二进制编码串来表示该参数，将A, B等分成个子部分，记每一个等分的长度为，则它能够产生种不同的编码，参数的对应关系如下：00000000000000000> A00000000000000011>A+ 11111111111111112l1>B其中(2.9)假如某一个体的编码是：则上述二进制编码所对应的解码公式为 (2.10)二进制编码的最大缺点是长度较大，对很多问题用其他编码方法可能更有利。其他编码方法主要有：浮点数编码方法、格雷码、符号编码方法、多参数编码方法等。浮点数编码方法是指个体的每个染色体用某一范围内的一个浮点数来表示，个体的编码长度等于其问题变量的个数。因为这种编码方法使用的是变量的真实值，所以浮点数编码方法也叫做真值编码方法。对于一些多维、高精度要求的连续函数优化问题，用浮点数编码来表示个体时将会有一些益处。格雷码是其连续的两个整数所对应的编码值之间只有一个码位是不相同的，其余码位都完全相同。例如十进制数7和8的格雷码分别为0100和1100，而二进制编码分别为0111和1000。符号编码方法是指个体染色体编码串的基因值取自一个无数值含义而只有代码含义的符号集。这个符号集可以是一个字母表，如A,B,C,D,；也可以是一个数字序号表，如1,2,3,4,5,；还可以是一个代码表，如x1, x2, x3, x4, ，等等。第三节 群体设定遗传算法中初始群体中的个体是随机产生的。不失一般性，初始群体的设定可以采取下面的策略：l 根据问题固有知识，设法把握最优解所占空间在整个问题空间的分布范围，然后，在此分布范围内设定初始群体。 l 先随机生成一定数目的个体，然后从中挑出最好的个体加到初始群体中。这种过程不断迭代，直到初始群体中个体数目达到了预先确定的规模。 通过定理证明，在二进制编码的前提下，为了满足隐含的并行性，群体个体数只要设定为即可，其中 n 为个体长度的一半。所以在实际应用中，群体个数的取值范围一般在几十到几百。另外，群体规模的确定受遗传操作中选择操作的影响很大。群体规模越大，群体中个体的多样性越高，算法陷入局部解的危险就小。但是，群体过大，其适应度评估次数增加，所以计算量也增加，从而影响算法效率。另一方面，如果群体规模太小，会使遗传算法的搜索空间分布范围有限，因此搜索有可能停止在未成熟阶段，导致未成熟收敛。第四节 适应度函数遗传算法在进化搜索中基本上不用外部信息，仅仅使用目标函数即适应度函数为依据。遗传算法的目标函数不受连续可微的约束且定义域可以为任意集合。对目标函数的唯一要求是，针对输入可计算出能加以比较的结果，而且结果为非负。一、 目标函数到适应度函数的映射在许多问题中，目标是求费用函数g(x)的最小值。即使某一问题可自然的表示成求最大值形式，也不能保证对于所有的 x,使 f(x)取非负值。但是遗传算法中，适应度函数要进行比较排序并且在此基础上计算选择概率，所以适应度函数的值要取正值。因此必须将目标函数映射成求最大值形式且适应度函数值非负。 在通常情况下，为了把一个最小化问题转化为最大化问题，只需要简单的把原函数乘以-1 即可，但对遗传算法而言，这种方法还不足以保证在各种情况下的非负值。对此，可以采用以下的方法进行转换： 当 其他情况 (2.11)有多种方法来选择系数。可以是一个合适的输入值，也可以采用迄今为止进化过程中g(x)的最大值或当前群体中g(x)的最大值。最好与群体无关。二、适应度尺度变换（适应度函数定标）应用遗传算法时，常常会出现一些不利于优化的现象或结果。在遗传进化的初期，通常出现一些超常的个体，这些异常个体有可能在群体中占据很大的比例，因而可能导致未成熟收敛现象。这是因为这些异常个体竞争力太突出控制了整个选择过程，从而影响了算法的全局优化性能。针对上述情况，可以通过放大或缩小相应的适应度函数值来进行改进。这种对适应度的缩放调整称作适应度定标。通常采用的定标方式为： 线性定标：； (2.12) 截断： (2.13) 乘幂定标： ； (2.14)第五节 遗传操作一、选择算子从群体中选择优胜的个体，淘汰劣质个体的操作叫做选择。选择算子又 叫再生算子（Reproduction Operator）。选择的目的是把优化的解直接遗传到下一代或者通过配对交叉产生新的个体再遗传到下一代。选择操作是建立在群体中个体的适应度评估基础上的，目前常用的选择算子有：1 适应度比例方法（Fitness proportional model）适应度比例方法是目前遗传算法中最基本最常用的选择方法。它也叫赌轮（roulette wheel）或蒙特卡罗（Monte Carlo）选择1。 设群体大小为n,其中个体i的适应度值为,则i被选择的概率为: (2.15)可见反映了个体i的适应度在整个群体的个体适应度总和中所占的比例。个体适应度越大，被选择的概率就越高。2 最佳个体保存方法（Elitist model）此方法的思想是把群体中适应度最高的个体不进行配对交叉而直接复制到下一代中。采用这种选择方法的优点是：进化过程中某一代的最优解可以不被交叉和变异操作所破坏。但是，这是这样可能隐含了一种危机导致早熟，即局部最优个体的遗传基因会急速增加而使进化有可能限于局部解。也就是说，该方法的全局搜索能力不强，它更加适合于单峰性质的搜索空间搜索。一般将这种方法与其它一些选择操作配合起来使用，才能有良好的效果。 另外，最佳个体保存方法还可加以推广，即在每一代的进化过程中保留多个最优个体不参加交叉、变异等遗传操作，而直接将它们复制到下一代群体中。这种选择方法也称为稳态复制。3 排序选择方法（Rank-based）排序选择方法是指在计算每个个体的适应度后，根据适应度大小顺序对群体中个体排序，然后把事先设计好的概率表按顺序分配给个体，作为各自的选择概率。这种方法的不足之处在于选择概率和序号的关系必须事先确定。此外，它和适应度比例方法一样都是一种基于概率的选择，所以仍然有统计误差。此外还有一些比较常用的选择方法如期望值方法（Expected value model）、联赛选择方法（Tournament selection model）等。二、交叉算子1交叉算子的设计 实现个体结构重组的交叉算子设计一般与所求解