第8章 遗传算法.doc

第8章遗传算法1引言遗传算法(GeneticAlgorithms简称GA)是由美国Michigan大学的JohnHolland教授创建的。它来源于达尔文的进化论、魏茨曼的物种选择学说和孟德尔的群体遗传学说。其基本思想是模拟自然界遗传机制和生物进化论而形成的一种过程搜索最优解的算法。其特点是几乎不需要所求问题的任何信息而仅需要目标函数的信息，不受搜索空间是否连续或可微的限制就可找到最优解。依据它的并行性，非常适用于大规模并行计算机。因此，遗传算法广泛的应用于自动控制、计算科学、模式识别、工程设计、智能故障诊断、管理科学和社会科学领域，适用于解决复杂的非线性和多维空间寻优问题。2遗传算法的发展1)20世纪60年代，John Holland教授和他的数位博士受到生物模拟技术的启发，认识到自然遗传可以转化为人工遗传算法。1962年John Holland提出了利用群体进化模拟适应性系统的思想，引进了群体、适应值、选择，变异、交叉等基本概念。2)1967年，J.D.Bagely在其博士论文中首次提出了“遗传算法”的概念。3)1975年，Holland出版了自然与人工系统中的适应性行为（Adaptation in Natural and Artificial System）。该书系统地阐述了遗传算法的基本理论和方法，提出了遗传算法的基本定理模式定理，从而奠定了遗传算法的理论基础。同年，De Jong在其博士论文中首次把遗传算法应用于函数优化问题，对遗传算法的机理与参数进行了较为系统地研究，并建立了著名的五函数测试平台。4)20世纪80年代初，Holland教授实现了第一个基于遗传算法的机器学习系统分类器系统（Classifier System简称CS），开创了基于遗传算法的机器学习的新概念。5)1989年，David Goldberg出版了搜索、优化和机器学习中的遗传算法（Genetic Algorithms in Search Optimization and Machine Learning）。该书全面系统地总结了当时关于遗传算法的研究成果，结合大量的实例，完整的论述了遗传算法的基本原理及应用，奠定了现代遗传算法的基础。6)1992年，John R.Koza出版了专著遗传编程（GeneticProgramming），提出了遗传编程的概念，并成功地把遗传编程的方法应用于人工智能、机器学习、符号处理等方面。随着遗传算法的不断深入和发展，关于遗传算法的国际学术活动越来越多，遗传算法已成为一个多学科、多领域的重要研究方向。3遗传算法的特点1)直接处理的对象是决策变量的编码集而不是决策变量的实际值本身，搜索过程既不受优化函数的连续性约束，也没有优化函数导数必须存在的要求。3)遗传算法是一种自适应搜索技术，其选择、交叉、变异等运算都是以一种概率方式来进行，从而增加了搜索过程的灵活性，同时能以很大的概率收敛于最优解，具有较好的全局优化求解能力。4)遗传算法直接以目标函数值为搜索信息，对函数的性态无要求，具有较好的普适性和易扩充性；同时，我们可以把搜索范围集中到适应度较高的部分搜索空间中，从而提高了搜索效率。1遗传算法从问题解的串集开始嫂索，而不是从单个解开始。这是遗传算法与传统优化算法的极大区别。传统优化算法是从单个初始值迭代求最优解的；容易误入局部最优解。遗传算法从串集开始搜索，复盖面大，利于全局择优。2遗传算法求解时使用特定问题的信息极少，容易形成通用算法程序。由于遗传算法使用适应值这一信息进行搜索，并不需要问题导数等与问题直接相关的信息。遗传算法只需适应值和串编码等通用信息，故几乎可处理任何问题。遗传算法的基本思想简单，运行方式和实现步骤规范，便于具体使用。3遗传算法有极强的容错能力遗传算法的初始串集本身就带有大量与最优解甚远的信息；通过选择、交叉、变异操作能迅速排除与最优解相差极大的串；这是一个强烈的滤波过程；并且是一个并行滤波机制。故而，遗传算法有很高的容错能力。4遗传算法中的选择、交叉和变异都是随机操作，而不是确定的精确规则。这说明遗传算法是采用随机方法进行最优解搜索，选择体现了向最优解迫近，交叉体现了最优解的产生，变异体现了全局最优解的复盖。5遗传算法采用多点搜索或者说是群体搜索，具有很高的隐含并行性。术语说明 遗传算法的基本思想是基于Darwin进化论和Mendel的遗传学说的。Darwin进化论最重要的是适者生存原理。它认为每一物种在发展中越来越适应环境。物种每个个体的基本特征由后代所继承，但后代又会产生一些异于父代的新变化。在环境变化时，只有那些熊适应环境的个体特征方能保留下来。Mendel遗传学说最重要的是基因遗传原理。它认为遗传以密码方式存在细胞中，并以基因形式包含在染色体内。每个基因有特殊的位置并控制某种特殊性质；所以，每个基因产生的个体对环境具有某种适应性。基因突变和基因杂交可产生更适应于环境的后代。经过存优去劣的自然淘汰，适应性高的基因结构得以保存下来。由于遗传算法是由进化论和遗传学机理而产生的直接搜索优化方法；故而在这个算法中要用到各种进化和遗传学的概念。这些概念如下：一、串(String)它是个体(Individual)的形式，在算法中为二进制串，并且对应于遗传学中的染色体(Chromosome)。二、群体(Population)个体的集合称为群体，串是群体的元素三、群体大小(Population Size)在群体中个体的数量称为群体的大小。一、染色体(Chronmosome) 染色体又可以叫做基因型个体(individuals),一定数量的个体组成了群体(population),群体中个体的数量叫做群体大小。 二、基因(Gene) 基因是串中的元素，基因用于表示个体的特征。例如有一个串S1011，则其中的1，0，1，1这4个元素分别称为基因。它们的值称为等位基因(Alletes)。 三、基因地点(Locus) 基因地点在算法中表示一个基因在串中的位置称为基因位置(Gene Position)，有时也简称基因位。基因位置由串的左向右计算，例如在串 S1101 中，0的基因位置是3。 四、基因特征值(Gene Feature) 在用串表示整数时，基因的特征值与二进制数的权一致；例如在串 S=1011 中，基因位置3中的1，它的基因特征值为2；基因位置1中的1，它的基因特征值为8。 五、适应度(Fitness) 各个个体对环境的适应程度叫做适应度(fitness)。为了体现染色体的适应能力，引入了对问题中的每一个染色体都能进行度量的函数，叫适应度函数. 这个函数是计算个体在群体中被使用的概率。七、串结构空间SS在串中，基因任意组合所构成的串的集合。基因操作是在结构空间中进行的。串结构空间对应于遗传学中的基因型(Genotype)的集合。八、参数空间SP这是串空间在物理系统中的映射，它对应于遗传学中的表现型(Phenotype)的集合。九、非线性它对应遗传学中的异位显性(Epistasis)遗传算法的目的典型的遗传算法CGA(Canonical Genetic Algorithm)通常用于解决下面这一类的静态最优化问题：考虑对于一群长度为L的二进制编码bi，i1，2，n；有bi0,1L给定目标函数f，有f(bi)，并且0f(bi)同时f(bi)f(bi+1)求满足下式maxf(bi)|bi0,1L的bi。遗传算法的基础理论是图式定理。它的有关内容如下：(1)图式(Schema)概念一个基因串用符号集0，1，*表示，则称为一个因式；其中*可以是0或1。例如：H=1x x 0 x x是一个图式。(2)图式的阶和长度图式中0和1的个数称为图式的阶，并用0(H)表示。图式中第1位数字和最后位数字间的距离称为图式的长度，并用(H)表示。对于图式H1x x0x x，有0(H)2，(H)4。型式*000的阶是3,定义长度是5 - 3 = 2,型式10*0*的阶的3,定义长度是4 - 1 = 3(3)Holland图式定理低阶，短长度的图式在群体遗传过程中将会按指数规律增加。当群体的大小为n时，每代处理的图式数目为0(n3)。遗传算法这种处理能力称为隐含并行性(Implicit Parallelism)。它说明遗传算法其内在具有并行处理的特质。4遗传算法的基本原理遗传算法是建立在自然选择和群体遗传学机理基础上的随机迭代和进化，具有广泛适用性的搜索方法，具有很强的全局优化搜索能力。它模拟了自然选择和自然遗传过程中发生的繁殖、交配和变异现象，根据适者生存、优胜劣汰的自然法则，利用遗传算子(选择、交叉和变异)逐代产生优选个体(即候选解)，最终搜索到较优的个体。经典遗传算法的计算流程如图1所示。从图中可以看出，遗传算法是一种种群型操作，该操作以种群中的所有个体为对象。具体求解步骤如下：1)参数编码：遗传算法一般不直接处理问题空间的参数而是将待优化的参数集进行编码，一般总是用二进制将参数集编码成由0或1组成的有限长度的字符串。2)初始种群的生成：随机地产生n个个体组成一个群体，该群体代表一些可能解的集合。GA的任务是从这些群体出发，模拟进化过程进行择优汰劣，最后得出优秀的群体和个体，满足优化的要求。3)适应度函数的设计：遗传算法在运行中基本上不需要外部信息，只需依据适应度函数来控制种群的更新。根据适应度函数对群体中的每个个体计算其适应度，为群体进化的选择提供依据。设计适应度函数的主要方法是把问题的目标函数转换成合适的适应度函数。4)选择(复制)：按一定概率从群体中选择M对个体，作为双亲用于繁殖后代，产生新的个体加入下一代群体。即适应于生存环境的优良个体将有更多繁殖后代的机会，从而使优良特性得以遗传。选择是遗传算法的关键，它体现了自然界中适者生存的思想。选择操作也叫复制操作，从群体中按个体的适应度函数值选择出较适应环境的个体。一般地说，选择将使适应度高的个体繁殖下一代的数目较多，而适应度较小的个体，繁殖下一代的数目较少,甚至被淘汰。最通常的实现方法是轮盘赌(roulette wheel)模型。令fi表示群体的适应度值之总和，fi表示种群中第i个染色体的适应度值，它被选择的概率正好为其适应度值所占份额fifi。如下图表中的数据适应值总和fi=6650,适应度为2200变选择的可能为fifi=2200/6650=0.394.图2. 轮盘赌模型Fitness 值：220018001200950400100选择概率：0.33310.2710.180.1430.060.015分级选择方法（Rank Selection） 前面这中选择方法很简单，但是当适应度变化比较大时就会有问题。比如说，当前种群中最好的基因（适应度最大）的适应度占S的90的时候，那么其它基因就很少有机会被选择到。分级选择方法首先把种群分几个等级。然后，每一个基因收到各自等级中的适应度。我们定义最差的等级的适应度为1；次差的为2等等，最好的那个级适应度定义为N（N就是种群中基因的个数）。 这样，所有的基因都有机会被选择到。但是这样又会导致算法的收敛速度变慢，因为最好的基因与其它基因的差别被缩小了。稳定状态选择方法（Steady State Selection） 其实，这并不是选择父代的特殊方法。这种方法的主要思想是有很多的基因要保留到下一代中！ 于是遗传算法将按照如下的方式进行： 在每一代中选择一少部分基因（与适应度相符合）来构造子代。接着，父代中一部分基因（与适应度不符合的）被新产生的子代所代替，父代中其它的人基因被保留到新的一代中。精英主义 （Elitism） 仅仅从产生的子代中选择基因去构造新的种群可能会丢失掉上一代种群中的很多信息。也就是说当利用交叉和变异产生新的一代时，我们有很大的可能把在某个中间步骤中得到的最优解丢失。在此我们使用精英主义（Elitism）方法，在每一次产生新的一代时，我们首先把当前最优解原封不动的复制到新的一代中，其他步骤不变。这样任何时刻产生的一个最优解都可以存活到遗传算法结束。 上述各种算子的实现是多种多样的，而且许多新的算子正在不断地提出，以改进GA某些性能。比如选择算法还有分级均衡选择等等。5)杂交(交叉)：对于选中的用于繁殖的每一对个体，随机地选择同一整数n，将双亲的基因码链在此位置相互交换。交叉体现了自然界中信息交换的思想。交叉算子将被选中的两个个体的基因链按一定概率pc进行交叉，从而生成两个新的个体，交叉位置pc是随机的。其中Pc是一个系统参数。根据问题的不同，交叉又为了单点交叉算子（Single Point Crossover）、双点交叉算子（Two Point Crossover）、均匀交叉算子 (Uniform Crossover)，在此我们只讨论单点交叉的情况。 单点交叉操作的简单方式是将被选择出的两个个体S1和S2作为父母个体，将两者的部分基因码值进行交换。假设如下两个8位的个体： S11000 1111 S21110 1100产生一个在1到7之间的随机数c，假如现在产生的是2，将S1和S2的低二位交换：S1的高六位与S2的低六位组成数串10001100，这就是S1和S2的一个后代P1个体；S2的高六位与S1的低二位组成数串11101111，这就是S1和S2的一个后代P2个体。其交换过程如下图所示： Crossover11110000Crossover11110000S11000 1111S21110 1100P11000 1100P21110 1111双交叉点交叉算子（Two Point Crossover）: 选择两个交叉点,子代基因在两个交叉点间部分来自一个父代基因,其余部分来自于另外一个父代基因. 均匀交叉算子 (Uniform Crossover):子代基因的每一个位点是随机地来自于两个父代基因中的一个的; 算术交叉算子（Arithmetic Crossover）:对父代基因做一个代数运算从而产生一个新的基因。下面就是使用和运算（AND）实现的： 6)变异：按一定的概率从群体中选择若干个个体。对于选中的个体，随机选择某一位进行取反操作。这是在选中的个体中，将新个体的基因链的各位按概率pm进行异向转化，最简单方式是改变串上某个位置数值。对二进制编码来说将0与1互换：0变异为1，1变异为0。 如下8位二进制编码： 11101100随机产生一个1至8之间的数i，假如现在k=6，对从右往左的第6位进行变异操作，将原来的1变为0，得到如下串： 11001100变异模拟了生物进化过程中的偶然基因突变现象。对产生的新一代群体进行重新评价、选择、杂交和变异。如此循环往复，使群体中最优个体的适应度和平均适应度不断提高，直至最优个体的适应度达到某一界限或最优个体的适应度和平均适应度值不再提高，则迭代过程收敛，算法结束。GA的搜索能力主要是由选择和杂交赋予的，变异算子则保证了算法能搜索到问题解空间的每一点，从而使算法达到全局最优。整个交叉变异过程如下图： 图3. 交叉变异过程遗传算法的所需参数 说简单点遗传算法就是遍历搜索空间或连接池，从中找出最优的解。搜索空间中全部都是个体，而群体为搜索空间的一个子集。并不是所有被选择了的染色体都要进行交叉操作和变异操作，而是以一定的概率进行，一般在程序设计中交叉发生的概率要比变异发生的概率选取得大若干个数量级。大部分遗传算法的步骤都很类似，常使用如下参数： Fitness函数：见上文介绍。 Fitnessthreshold（适应度阀值）：适合度中的设定的阀值，当最优个体的适应度达到给定的阀值，或者最优个体的适应度和群体适应度不再上升时(变化率为零)，则算法的迭代过程收敛、算法结束。否则，用经过选择、交叉、变异所得到的新一代群体取代上一代群体，并返回到选择操作处继续循环执行。 P：种群的染色体总数叫种群规模，它对算法的效率有明显的影响，其长度等于它包含的个体数量。太小时难以求出最优解，太大则增长收敛时间导致程序运行时间长。对不同的问题可能有各自适合的种群规模，通常种群规模为 30 至 160。 pc：在循环中进行交叉操作所用到的概率。交叉概率（Pc）一般取0.6至0.95之间的值，Pc太小时难以向前搜索，太大则容易破坏高适应值的结构。 Pm：变异概率，从个体群中产生变异的概率，变异概率一般取0.01至0.03之间的值变异概率Pm太小时难以产生新的基因结构，太大使遗传算法成了单纯的随机搜索。 另一个系统参数是个体的长度，有定长和变长两种。它对算法的性能也有影响。由于GA是一个概率过程，所以每次迭代的情况是不一样的,系统参数不同，迭代情况也不同。遗传步骤 了解了上面的基本参数，下面我们来看看遗传算法的基本步骤。 基本过程为： 1. 对待解决问题进行编码,我们将问题结构变换为位串形式编码表示的过程叫编码；而相反将位串形式编码表示变换为原问题结构的过程叫译码。 2. 随机初始化群体P(0)：=(p1, p2, pn)； 3. 计算群体上每个个体的适应度值(Fitness) 4. 评估适应度,对当前群体P(t)中每个个体Pi计算其适应度F(Pi)，适应度表示了该个体的性能好坏 5. 按由个体适应度值所决定的某个规则应用选择算子产生中间代Pr(t) 6. 依照Pc选择个体进行交叉操作 7. 仿照Pm对繁殖个体进行变异操作 8. 没有满足某种停止条件，则转第3步，否则进入9 9. 输出种群中适应度值最优的个体 程序的停止条件最简单的有如下二种：完成了预先给定的进化代数则停止；种群中的最优个体在连续若干代没有改进或平均适应度在连续若干代基本没有改进时停止。下面伪代码简单说明了遗传算法操作过程：choose an intial populationFor each h in population,compute Fitness(h)While(max Fitness(h) Fitnessthreshold)do selection do crossoverdo mutation update populationFor each h in population,compute Fitness(h)Return best Fitness遗传算法的执行过程24编码问题编码是遗传算法要解决的首要问题。Holland的编码方法是二进制编码,但对于许多遗传算法的应用,特别是在工业工程中的应用,这种简单的编码方法很难直接描述问题的性质。近十年来,针对特殊问题,人们提出了其它编码方法。例如:(1)二进制编码1它是遗传算法中最常用的一种编码方法。它具有下列一些优点:编码、解码操作简单易行;交叉、变异操作便于实现;符合最小字符集编码原则;便于利用模式定理对算法进行理论分析。(2)格雷码编码3对于一些连续优化问题,二进制编码由于遗传算法的随机特性而使其局部搜索能力较差。为改进这一特性,人们提出用格雷码进行编码。格雷码编码方法是二进制编码方法的一种变形。它是这样的一种编码方法,其连续的两个整数所对应的编码值之间仅仅只有一个码位是不相同的,其余码位都完全相同。假设有一个二进制编码为B=bmbm-1b2b1,其对应的格雷码为G=gmgm-1g2g1,则:gm=bmgi=bi+1 bii=m-1,m-2,1格雷码有这样一个特点:任意两个整数的差是这两个整数所对应的格雷码之间的海明距离。这一特点是遗传算法中使用格雷码来进行个体编码的主要原因。格雷码除了具有二进制编码的优点外,还能提高遗传算法的局部搜索能力。(3)实数编码3对于一些多维、高精度要求的连续函数优化问题,使用二进制编码来表示个体将会带来一些不利,例如,二进制编码存在着连续函数离散化时的映射误差,同时不便于反映所求问题的特定知识。为了克服这些缺点,人们提出实数编码方法,即个体的每个基因值用实数表示。实数编码方法的优点如下:适合于遗传算法中表示范围较大的数;便于较大空间的遗传搜索;提高了遗传算法的精度要求;改善了遗传算法的计算复杂性,提高了运算效率;便于算法与经典优化方法的混合作用;便于设计专门问题的遗传算子。(4)符号编码方法2是指染色体编码串中的基因值取自一个无数值含义、而只有代码含义的符号集。这些符号可以是字符,也可以是数字。例如,对于旅行商问题,假设有n个城市分别记为C1,C2,Cn,则C1,C2,Cn就可构成一个表示旅行路线的个体。符号编码的主要优点是便于在遗传算法中利用所求问题的专门知识及相关算法。对于非二进制编码,染色体编码与问题的解之间有三个主要问题:染色体的可行性;染色体的合法性;映射的唯一性。可行性是指染色体编码成为解之后是否在给定问题的可行域内。染色体的可行性概念源于约束优化问题,无论是传统方法还是遗传算法都必须满足约束。对于许多优化问题,可行域是用等式或不等式组来表达的。在这种情况下,许多有效的惩罚法可用来消除不可行的染色体。在约束优化问题中,最优点通常位于可行域的边界上,惩罚法将迫使遗传搜索从可行域和不可行域两边同时逼近最优点。合法性是指染色体编码是否代表给定问题的一个解。染色体的合法性概念源于编码技术。许多组合优化问题采用了问题专用的编码方法,这些编码方法采用单断点交叉可能会获得非法的后代。由于非法的染色体不能成为解,这样的染色体不能进行评估,因此惩罚法就无法适用。这种情况下,通常采用修复方法,将非法染色体转换为合法染色体。例如,著名的PMX算子5就是为解决单断点交叉的非法性而提出的一种将替代编码和修复技术结合起来的双断点交叉方法。25交叉运算13所谓交叉运算,是指对两个相互配对的染色体按某种方式相互交换其部分基因,从而形成两个新的个体。交叉运算是遗传算法区别于其他进化算法的重要特征,它在遗传算法中起关键作用,是产生新个体的主要方法。遗传算法中,在交叉运算之前还必须对群体中的个体进行配对,目前常用的配对策略是随机配对。交叉算子的设计包括两个方面的内容:如何确定交叉点的位置?如何进行部分基因的交换?下面介绍几种适用于二进制编码或实数编码的交叉算子。(1)单点交叉又称为简单交叉,它是指在个体编码串中随机设置一个交叉点,然后在该点相互交换两个配对个体的部分基因。(2)双点交叉它的具体操作过程是:在相互配对的两个个体编码串中随机设置两个交叉点;交换两个交叉点之间的部分基因。(3)均匀交叉它是指两个配对个体的每一位基因都以相同的概率进行交换,从而形成两个新个体。具体操作过程如下:随机产生一个与个体编码长度相同的二进制屏蔽字W=w1w2w1;按下列规则从A、B两个父代个体中产生两个新个体X、Y:若wi=0,则X的第i个基因继承A的对应基因,Y的第i个基因继承B的对应基因;若wi=1,则A、B的第i个基因相互交换,从而生成X、Y的第i个基因。(4)算术交叉它是指由两个个体的线性组合而产生出新的个体。设在两个个体A、B之间进行算术交叉,则交叉运算后生成的两个新个体X、Y为:X=A+(1-)BY=B+(1-)A26变异运算1-3所谓变异运算,是指将个体编码串中的某些基因值用其它基因值来替换,从而形成一个新的个体。遗传算法中的变异运算是产生新个体的辅助方法,但它是必不可少的一个运算步骤,因为它决定了遗传算法的局部搜索能力。交叉运算和变异运算的相互配合,共同完成对搜索空间的全局搜索和局部搜索。变异运算的设计包括两方面:如何确定变异点的位置?如何进行基因值替换?下面介绍几种常用的变异操作方法。它们适用于二进制编码和实数编码的个体。(1)基本位变异它是指对个体编码串以变异概率p随机指定某一位或某几位基因作变异运算。(2)均匀变异它是指分别用符合某一范围内均匀分布的随机数,以某一较小的概率来替换个体中每个基因。(3)高斯变异它是指进行变异操作时,用均值为,方差为2的正态分布的一个随机数来替换原有基因值。具体操作过程与均匀变异类似。(4)二元变异6它的操作需要两条染色体参与,两条染色体通过二元变异操作后生成两条新个体。新个体中的各个基因分别取原染色体对应基因值的同或/异或。例如:0110101111010001变异01000101“同或”运算10111010“异或”运算二元变异算子改进了传统的变异方式,有效地克服了早熟收敛,提高了遗传算法的优化速度6。27选择运算1-3遗传算法使用选择运算(或称复制运算)来实现对群体中的个体进行优胜劣汰操作:适应度高的个体被遗传到下一代群体中的概率大;适应度低的个体,被遗传到下一代群体中的概率小。选择操作的任务就是按某种方法从父代群体中选取一些个体,遗传到下一代群体。下面介绍几种选择方法。271赌盘选择又称比例选择方法。其基本思想是:各个个体被选中的概率与其适应度大小成正比。具体操作如下:(1)计算出群体中每个个体的适应度Fi,i=1,2,M,M为群体大小;(2)计算出每个个体被遗传到下一代群体中的概率;(3)计算出每个个体的累积概率;(4)在0,1区间内产生一个均匀分布的伪随机数r;(5)若r q1,则选择个体1;否则,选择个体k,使得:qk-1 (在0,31范围内随机选取4个整数就可以,编码) 4)计算适应度Fi(由于是最小值,可以选取一个大的基准线1000,Fi = 1000 - (x-10)2) 5)计算每个个体的选择概率.选择概率要能够反映个体的优秀程度.这里用一个很简单的方法来确定选择概率 P=Fi / TOTAL(Fi). 6)选择. 根据所有个体的选择概率进行淘汰选择.这里使用的是一个赌轮的方式进行淘汰选择.先按照每个个体的选择概率创建一个赌轮,然后选取4次,每次先产生一个0-1的随机小数,然后判断该随机数落在那个段内就选取相对应的个体.这个过程中,选取概率P高的个体将可能被多次选择,而概率低的就可能被淘汰.下面是一个简单的赌轮的例子 13% 35% 15% 37%-|-|-|-*-| 个体1 个体2 个体30.67 个体4 随机数为0.67落在了个体4的端内.本次选择了个体4.被选中的个体将进入配对库(mating pool,配对集团)准备开始繁殖. 7)简单交叉 先对配对库中的个体进行随机配对.然后在配对的2个个体中设置交叉点,交换2个个体的信息后产生下一代. 比如( | 代表简单串的交叉位置) ( 0110|1, 1100|0 ) -交叉- (01100,11001) ( 01|000, 11|011 ) -交叉- (01011,11000) 2个父代的个体在交叉后繁殖出了下一代的同样数量的个体. 复杂的交叉在交叉的位置,交叉的方法,双亲的数量上都可以选择.其目的都在于尽可能的培育出更优秀的后代 8)变异 变异操作时按照基因座来的.比如说没计算2万个基因座就发生一个变异(我们现在的每个个体有5个基因座.也就是说要进化1000代后才会在其中的某个基因座发生一次变异.)变异的结果是基因座上的等位基因发生了变化.我们这里的例子就是把0变成1或则1变成0. 至此,我们已经产生了一个新的(下一代)集团.然后回到第4步,周而复始,生生不息下去例 求函数f(x) =x2的最大值,变量x在0与31之间的整数取值。解 为用SGA解此问题,容易想到将决策变量x取的值以二进位数表示从而得到一种自然的编码;每一个体均为长度是5的二进制位串。初始群体的容量取4。于是,从总体中随机抽取4个个体组成第一代群体,即初始群体。具体操作可通过掷硬币确定。例如,将一枚硬币连续掷20次,或指定了顺序的5枚硬币各掷4次,正面为1,反面为0,得4个5位二进制字符串,不妨记为(01101)、(11000)、(01000)、(10011)。SGA采取按适应度大小比例进行选择的机制,则可用专门设计的简易轮盘来决定第一代群体中哪个个体能被保留。结果如表1所示。交换率取为1,即肯定施行交换算子。同样,可通过掷硬币的方法将复制出的4个串配成两对并随机确定交叉点进行交换,结果如表2。突变率取为0.001,这意味着每1000位平均有一位产生突变。本例的群体只包含4个5位的字符串共20位,平均只有0.02个位产生突变,可认为实际上不产生突变。于是,经过选择、交换完成了一代的遗传。事实证明,第二代群体的质量有了明显的提高,平均适应度由293增加为439,最大适应度由576增加到7295基于遗传算法的应用遗传算法提供了一种求解复杂系统优化问题的通用框架,它不依赖于问题具体的领域,对问题的种类有很强的鲁棒性,所以广泛应用于许多学科.51函数优化函数优化是遗传算法的经典应用领域,也是对遗传算法进行性能评价的常用算例,可以用各种各样的函数来验证遗传算法的性能,对一些非线形、多模型、多目标的函数优化问题,使用遗传算法可得到较好的结果.5.2组合优化随着问题规模的增大,组合优化问题的搜索空间也急剧扩大,有时在目前的计算机上用枚举法很难甚至不能求出问题的最优解,对这类问题,人们已意识到应把主要精力放在寻求其满意解上,而遗传算法是寻求这种满意解的最佳工具之一.实践证明,遗传算法对于组合优化种的NP完全问题非常有效.53生产调度问题生产调度问题在很多情况下所建立起来的数学模型难以求解,主要靠一些经验来进行调度,目前可采用遗传算法解决复杂的调度问题,在单件生产车间调度,流水线生产车间调度、生产规划、任务分配等方面,遗传算法都得到了有效的应用.54自动控制在自动控制领域中有很多与优化相关的问题需要求解,遗传算法已在其中得到了初步应用,并显示出了良好得效果.例如用遗传算法进行航空控制系统的优化,使用遗传算法设计空间交会控制器等.55机器人学机器人是一类复杂的难以精确建模的人工系统,而遗传算法的起源来自于对人工自适应系统的研究,所以机器人学理所当然地成为遗传算法的一个重要领域.例如,遗传算法已经在移动机器人路径规划、机器人逆运动学求解等方面得到很好的应用.56图象处理图象处理是计算机视觉中的一个重要领域,在图象处理过程中,如扫描、特征提取、图象分割等不可避免地会存在一些误差,这些误差会影响图象处理的效果,如何使这些误差最小是使计算机视觉达到实用化的重要要求,遗传算法在这些图象处理的优始计算方面找到了用武之地.5.7遗传编程基于对一种树型结构所进行的遗传操作来自动生成计算机程序.5.8机器学习基于遗传算法的机器学习,特别是分类器系统,在很多领域中都得到了应用.例如,遗传算法被用于学习模糊控制规则,利用遗传算法来学习隶属函数等.59数据挖掘数据挖掘(Data Mining)是指从大型数据库或数据仓库中提取隐含的、未知的、非平凡的及有潜在应用价值的信息或模式,它是数据库研究中的一个很有应用价值的新领域,由于遗传算法的特点,遗传算法可用于数据挖掘中的规则开采.5遗传算法存在的问题及相应的改进措施1)编码表示Holland在运