《遗传算法》PPT课件.ppt

1、遗传算法,2021/1/1,华中农业大学理学院,2,2021/1/1,华中农业大学理学院,3,第1章 人工智能概述 1.1 什么是人工智能 1.2 人工智能的研究意义、目标和策略 1.3 人工智能的学科范畴 1.4 人工智能的研究内容 1.5 人工智能的研究途径与方法 1.6 人工智能的基本技术 1.7 人工智能的应用 1.8 人工智能的分支领域与研究方向 1.9 人工智能的发展概况,2021/1/1,华中农业大学理学院,4,1.1 什么是人工智能 人工智能（Artificial Intelligence”，AI） 1.1.1 人工智能概念的一般描述 部分学者对人工智能概念的描述： 人工智能是

2、那些与人的思维相关的活动，诸如决策、问题求解和学习等的自动化（Bellman, 1978）； 人工智能是一种计算机能够思维，使机器具有智力的激动人心的新尝试（Haugeland, 1985）； 人工智能是研究如何让计算机做现阶段只有人才能做得好的事情（Rich Knight,1991）；,2021/1/1,华中农业大学理学院,5, 人工智能是那些使知觉、推理和行为成为可能的计算的研究（Winston, 1992）； 广义地讲，人工智能是关于人造物的智能行为，而智能行为包括知觉、推理、学习、交流和在复杂环境中的行为（Nilsson，1998）。 Stuart Russell和Peter Norv

3、ig则把已有的一些人工智能定义分为4类：像人一样思考的系统、像人一样行动的系统、理性地思考的系统、理性地行动的系统（2003）。,2021/1/1,华中农业大学理学院,6,1.1.2 图灵测试和中文屋子 图灵测试”（Turing Test）,2021/1/1,华中农业大学理学院,7,约翰.西尔勒(John Searle)的 “中文屋子”,2021/1/1,华中农业大学理学院,8,1.1.3 脑智能和群智能 脑（主要指人脑）的宏观心理层次的智能表现称为脑智能（Brain Intelligence, BI）。 由群体行为所表现出的智能称为群智能（Swarm Intelligence, SI）。 脑

4、智能和群智能是属于不同层次的智能： 脑智能是一种个体智能（Individual Intelligence, II）； 群智能是一种社会智能（Social Intelligence, SI）， 或者说系统智能（System Intelligence, SI）。,2021/1/1,华中农业大学理学院,9,1.1.4 符号智能和计算智能 1. 符号智能 符号智能就是符号人工智能，它是模拟脑智能的人工智能，也就是所说的传统人工智能或经典人工智能。符号智能以符号形式的知识和信息为基础，主要通过逻辑推理，运用知识进行问题求解。符号智能的主要内容包括知识获取（knowledge acquisition）、知

5、识表示（knowledge representation）、知识组织与管理和知识运用等技术（这些构成了所谓的知识工程（Knowledge Engineering, KE）以及基于知识的智能系统等。,2021/1/1,华中农业大学理学院,10,2. 计算智能 计算智能就是计算人工智能，它是模拟群智能的人工智能。计算智能以数值数据为基础，主要通过数值计算，运用算法进行问题求解。计算智能的主要内容包括：神经计算（Neural Computation， NC）、进化计算（亦称演化计算，Evolutionary Computation，EC，包括遗传算法（Genetic Algorithm，GA）、进化

6、规划（Evolutionary Planning，EP）、进化策略（Evolutionary Strategies，ES）等）、免疫计算（immune computation）、粒群计算（Particle Swarm Algorithm，PSA）、蚁群算法（Ant Colony Algorithm，ACA）、自然计算（Natural Computation，NC）以及人工生命（Artificial Life，AL）等。,2021/1/1,华中农业大学理学院,11,1.2 人工智能的研究意义、目标和策略 1.2.1 为什么要研究人工智能 使当前的电脑更好用，更有用，以扩大和延伸人类智能； 信息化

7、社会的迫切要求； 自动化发展的必然趋势； 有益于探索人类自身智能的奥秘。,2021/1/1,华中农业大学理学院,12,1.2.2 人工智能的研究目标和策略 研究目标就是制造智能机器和智能系统，实现智能化社会。具体来讲，就是要使计算机不仅具有脑智能和群智能，还要具有看、听、说、写等感知和交流能力。 研究策略则是先部分地或某种程度地实现机器的智能，并运用智能技术解决各种实际问题特别是工程问题，从而使现有的计算机更灵活、更好用和更有用，成为人类的智能化信息处理工具，而逐步扩展和不断延伸人的智能，逐步实现智能化。,2021/1/1,华中农业大学理学院,13,1.3 人工智能的学科范畴 人工智能已构成信

8、息技术领域的一个重要学科。当前的人工智能既属于计算机科学技术的一个前沿领域，也属于信息处理和自动化技术的一个前沿领域。还涉及到智能科学、认知科学、心理科学、脑及神经科学、生命科学、语言学、逻辑学、行为科学、教育科学、系统科学、数理科学以及控制论、科学方法论、哲学甚至经济学等众多学科领域。人工智能实际上是一门综合性的交叉学科和边缘学科。,2021/1/1,华中农业大学理学院,14,1.4 人工智能的研究内容 1.5.1 搜索与求解 1.5.2 学习与发现 1.5.3 知识与推理 1.5.4 发明与创造 1.5.5 感知与交流 1.5.6 记忆与联想 1.5.7 系统与建造 1.5.8 应用与工程

9、,2021/1/1,华中农业大学理学院,15,1.5 人工智能的研究途径与方法 1.5.1 心理模拟，符号推演 1.5.2 生理模拟，神经计算 1.5.3 行为模拟，控制进化 1.5.4 群体模拟，仿生计算 1.5.5 博采广鉴，自然计算 1.5.6 原理分析，数学建模,2021/1/1,华中农业大学理学院,16,1.6 人工智能的基本技术 表示 运算 搜索,2021/1/1,华中农业大学理学院,17,1.7 人工智能的应用 1.7.1 难题求解 1.7.2 自动规划、调度与配置 1.7.3 机器定理证明 1.7.4 自动程序设计 1.7.5 机器翻译 1.7.6 智能控制 1.7.7 智能管

10、理 1.7.8 智能决策 1.7.9 智能通信 1.7.10 智能仿真,2021/1/1,华中农业大学理学院,18,1.7.11 智能CAD 1.7.12 智能制造 1.7.13 智能CAI 1.7.14 智能人机接口 1.7.15 模式识别 1.7.16 数据挖掘与数据库中的知识发现 1.7.17 计算机辅助创新 1.7.18 计算机文艺创作 1.7.19 机器博弈 1.7.20 智能机器人,2021/1/1,华中农业大学理学院,19,1.8 人工智能的分支领域与研究方向 从模拟的层次和所用的方法来看，人工智能可分为符号智能和计算智能两大主要分支领域。而这两大领域各自又有一些子领域和研究方向

11、。如符号智能中又有图搜索、自动推理、不确定性推理、知识工程、符号学习等。计算智能中又有神经计算、进化计算、免疫计算、蚁群计算、粒群计算、自然计算等。另外，智能Agent也是人工智能的一个新兴的重要领域。智能Agent或者说Agent智能则是以符号智能和计算智能为基础的更高一级的人工智能。 从模拟的脑智能或脑功能来看，AI中有机器学习、机器感知、机器联想、机器推理、机器行为等分支领域。而机器学习又可分为符号学习、连接学习、统计学习等许多研究领域和方向。机器感知又可分为计算机视觉、计算机听觉、模式识别、图像识别与理解、语音识别、自然语言处理等领域和方向。,2021/1/1,华中农业大学理学院,20

12、,从应用角度看，如1.7节所述，AI中有难题求解等数十种分支领域和研究方向。 从系统角度看，有智能计算机系统和智能应用系统两大类。智能计算机系统又可分为：智能硬件平台、智能操作系统、智能网络系统等。智能应用系统又可分为：基于知识的智能系统、基于算法的智能系统和兼有知识和算法的智能系统等。另外，还有分布式人工智能系统。 从基础理论看，AI中有数理逻辑和多种非标准逻辑、图论、人工神经网络、模糊集、粗糙集、概率统计（贝叶斯统计决策理论）和贝叶斯网络、统计学习理论与支持向量机、形式语言与自动机等领域和方向。,2021/1/1,华中农业大学理学院,21,1.9 人工智能学科的发展概况 1.9.1 人工智

13、能学科的产生 1.9.2 符号主义途径发展概况 1.9.3 连接主义途径发展概况 1.9.4 计算智能异军突起 1.9.5 智能Agent方兴未艾,2021/1/1,华中农业大学理学院,22,1.9.6 现状与发展趋势 多种途径齐头并进，多种方法协作互补。 新思想、新技术不断涌现，新领域、新方向不断开拓。 理论研究更加深入，应用研究愈加广泛。 研究队伍日益壮大，社会影响越来越大。,2021/1/1,华中农业大学理学院,23,虽然在通向人工智能最终目标的道路上，还有不少困难、问题和挑战，但前进和发展毕竟是大势所趋。,2021/1/1,华中农业大学理学院,24,智能交通,2021/1/1,华中农业

14、大学理学院,25,图像识别系统,2021/1/1,华中农业大学理学院,26,云松 銮仙玉骨寒， 松虬雪友繁。 大千收眼底， 斯调不同凡。,2021/1/1,华中农业大学理学院,27,（无题） 白沙平舟夜涛声， 春日晓露路相逢。 朱楼寒雨离歌泪， 不堪肠断雨乘风。,2021/1/1,华中农业大学理学院,28,2021/1/1,华中农业大学理学院,29,2021/1/1,华中农业大学理学院,30,2021/1/1,华中农业大学理学院,31,2021/1/1,华中农业大学理学院,32,遗传算法主要内容,一、遗传算法入门 二、遗传算法的主要特征 三、遗传算法的运行步骤 四、基本遗传算法的构成要素 五、

15、遗传算法的数学理论 六、遗传算法的基本实现技术 七、遗传算法的特点 八、遗传算法的应用,2021/1/1,华中农业大学理学院,33,遗传算法(Genetic Algorithm, GA)是近几年发展起来的一种崭新的全局优化算法，它借用了生物遗传学的观点，通过自然选择、遗传、变异等作用机制，实现各个个体的适应性的提高。这一点体现了自然界中“物竞天择、适者生存”进化过程。1962年Holland教授首次 提出了GA算法的思想，从而吸引了大批的研究者，迅速推广到优化、搜索、机器学习等方 面，并奠定了坚实的理论基础。 遗传算法是 John Holland大脑的产物，早在上个世纪60年代，他已提出了这种

16、想法。但不可思议的是，他没有感到需要在计算机上实际试验出结果，而宁愿利用笔和纸来作修修补补的工作！ 直到后来他的一名学生编写出程序并在一台个人计算机上运行后，才使人们终于看到在软件中利用他的思想能够得到什么。,一、遗传算法入门,2021/1/1,华中农业大学理学院,34,一、遗传算法入门,生物只有经过许多世代的不断演化（evolution），才能更好地完成生存与繁衍的任务。 遗传算法也遵循同样的方式，需要随着时间的推移不断成长、演化，最后才能收敛，得到针对某类特定问题的一个或多个解。 因此，了解一些有关有生命的机体如何演化的知识，对理解遗传算法的演化机制是是有帮助的。我们将扼要阐述自然演化的机

17、制（通常称为“湿”演化算法），以及与之相关的术语。理解自然演化的基本机制。我想，你也会和我一样，深深叹服自然母亲的令人着迷！,2021/1/1,华中农业大学理学院,35,本质上说，任何生物机体就是一大堆细胞的集合。每个细胞都包含若干组相同的DNA链，人们一般称之为染色体（chromosome）。染色体中包含的DNA分为两股，这两股DNA链以螺旋状绞合在一起，如下面图所示那样，这就是我们所熟悉的DNA双螺旋结构模型。,DNA双螺旋结构,一、遗传算法入门,2021/1/1,华中农业大学理学院,36,单个染色体是由称作基因（gene）的更小的结构模块组成，而基因则又由称作核苷酸（nucleotide

18、）的物质组成。 核苷酸一共只有四种类型，即：腺嘌呤(thymine)、鸟嘌呤(adenine)、胞嘧啶(cytocine)、胸腺嘧啶(guanine)。常简写为T、A、C、G。这些核苷酸相互连接起来，形成若干很长的基因链，而每个基因编码了生物机体的某种特征，如头发的颜色，耳朵的样子，等。一个基因可能具有的不同设置（如头发的黑色、棕色或金黄色），称为等位基因（allele），它们沿染色体纵向所处的物理部位称为基因的座位（locus）。,一、遗传算法入门,2021/1/1,华中农业大学理学院,37,二进制数速成（A Quick Lesson in Binary Numbers）,数字15,如果要把

19、15写成8位的二进制，则要写成下面这样的形式，其中高位都是，但也要把前面写出来，以使整个长度达到： 00001111,2021/1/1,华中农业大学理学院,38,计算机内的进化 （ Evolution Inside Your Computer ）,遗传算法工作过程本质上就是模拟生物的进化过程。 首先，要规定一种编码方法，使得你的问题的任何一个潜在可行解都能表示成为一个“数字”染色体。 然后，创建一个由随机的染色体组成的初始群体（每个染色体代表了一个不同的候选解），并在一段时期中，以培育适应性最强的个体的办法，让它们进化，在此期间，染色体的某些位置上要加入少量的变异。 经过许多代后，运气好一点，

20、遗传算法会收敛到一个解。 遗传算法不保证一定能得到解，也不保证找到的是最优解，但只要采用的方法正确，通常都能为遗传算法编出一个能够很好运行的程序。 遗传算法的最大优点就是， 你不需知道怎么去解决一个问题; 需要知道的仅是，用怎么方式对可行解进行编码，使得它能能被遗传算法机制所利用。,2021/1/1,华中农业大学理学院,39,通常，代表可行解的染色体采用一系列的二进制位作为编码。在运行开始时，创建一个染色体的群体，每个染色体都是一组随机的进制位。进制位（即染色体）的长度在整个群体中都是一样的。 作为一个例子，长度为 20的染色体的形状如下: 01010010100101001111 重要的事情

21、是，每个染色体都用这样的方式编码成为由 0和1组成的字符串，而它们通过 译码 就能用来表示你手头问题的一个解。这可能是一个很差的解，也可能是一个十分完美的解，但每一个单个的染色体都代表了一个可行解。初始群体通常都是 较糟的 ，有点中国男足球队。但，一个初始的群体已经创建完成（对这一例子，不妨设共有100个成员），这样，就可以开始做下面列出的一系列工作。,2021/1/1,华中农业大学理学院,40,不断进行下列循环，直到寻找出一个解 : 1.检查每个染色体，看它解决问题的性能怎样，并相应地为它分配一个适应性分数。 2. 从当前群体中选出2个成员。被选出的概率正比于染色体的适应性，适应性分数愈高，

22、被选中的可能性也就愈大。常用的方法就是采用所谓的 轮盘赌选择 法 或 赌 轮选择 法 (Roulette wheel selection )。 3.按照预先设定的 杂交率 （Crossover Rate ），从每个选中染色体的一个随机的点上进行杂交（crossover ）。 4.按照预定的 变异率 （ mutation rate ），通过对被选染色体的位的循环，把相应的位实行翻转（ flip ）。 5.重复步骤2，3，4，直到100个成员的新群体被创建出来。 结束循环 以上算法中步骤1 到步骤5 的一次循环称为一个代（或世代，generation）。而我把这整个的循环称作一个时代（epoch）

23、 。,2021/1/1,华中农业大学理学院,41,什么是轮盘赌选择？ ( Whats the Roulette Wheel Selection ),轮盘赌选择是从染色体群体中选择一些成员的方法，被选中的机率和它们的适应性分数成比例，染色体的适应性分数愈高，被选中的概率也愈多。这不保证适应性分数最高的成员一定能选入下一代，仅仅说明它有最大的概率被选中。其工作过程是这样的： 设想群体全体成员的适当性分数由一张饼图来代表 (见下图)，这一饼图就和用于赌博的转轮形状一样。我们要为群体中每一染色体指定饼图中一个小块。块的大小与染色体的适应性分数成比例，适应性分数愈高，它在饼图中对应的小块所占面积也愈大。

24、为了选取一个染色体，你要做的，就是旋转这个轮子，并把一个小球抛入其中，让它翻来翻去地跳动，直到轮盘停止时，看小球停止在哪一块上，就选中与它对应的那个染色体。,染色体的轮盘赌式选择,2021/1/1,华中农业大学理学院,42,轮盘赌选择,SGenome 程序通过循环来考察各基因组，把它们相应的适应性分数一个一个累加起来，直到这一 部分累加和 大于 fSlice 值时，就返回该基因组。,2021/1/1,华中农业大学理学院,43,什么是杂交率？( Whats the Crossover Rate ),杂交率就是用来确定 2个染色体进行局部的位（bit）的互换以产生2个新的子代的概率。 实验表明这一

25、数值通常取为0.7左右是理想的，尽管某些问题领域可能需要更高一些或较低一些的值。 每次，从群体中选择 2个染色体，同时生成其值在0到1之间一个随机数，然后根据此数据的值来确定两个染色体是否要进行杂交。如果数值低于杂交率(O.7)就进行杂交，就沿着染色体的长度随机选择一个位置，并把此位置后面所有的位进行互换。 例如，设给定的 2个染色体为: 10001001110010010 01010001001000011 沿着它们的长度你随机选择一个位置，比如说 10，然后互换第10位之后所有位。这样两个染色体就变成了： 100010011 01000011 010100010 10010010,杂交操作

26、（Crossover Revisited）,这一函数要求个染色体在同一随机位置上断裂开，然后将它们在断开点以后部分进行互换，以形成 2 个新的染色体 ( 子代 ) 。 void CgaBob:Crossover( const vector 这两循环把 2 个 parent 染色体在杂交点（ CP,crossover point ）以后的所有位进行了互换，并把新染色体赋给了 2 个子代 : baby1 和 baby2 。,2021/1/1,华中农业大学理学院,45,什么是变异率？( Whats the Mutation Rate? ),变异率（突变率） 就是在一个染色体中将位实行翻转（flip，

27、即0 变1，1变 0）的几率。这对于二进制编码的基因来说通常都是很低的值，比如 0.001 。 因此，无论你从群体中怎样选择染色体，你首先是检查是否要杂交，然后再从头到尾检查子代染色体的各个位，并按所规定的几率对其中的某些位实行突变（翻转）。,2021/1/1,华中农业大学理学院,46,变异操作（Mutation Revisited）,这一函数所做的工作，不过就是沿着一个染色体的长度，一bit一bit地进行考察，并按m_dMutationRate给定的几率，将其中某些bit实行翻转。 void CgaBob:Mutate(vector /移到下一个bit 遗传算法程序也就这样完成了！,2021

28、/1/1,华中农业大学理学院,47,用遗传算法解决问题时，首先要对待解决问题的模型结构和参数进行编码，一般用字符串表示，这个过程就将问题符号化、离散化了。也有在连续空间定义的GA(Genetic Algorithm in Continuous Space, GACS)，暂不讨论。：,2021/1/1,华中农业大学理学院,48,一个串行运算的遗传算法(Seguential Genetic Algoritm, SGA)按如下过程进行,(1)对待解决问题进行编码； (2)随机初始化群体X(0):=(x1, x2, xn)； (3)对当前群体X(t)中每个个体xi计算其适应度F(xi)，适应度表示了该

29、个体的性能好 坏； (4)应用选择算子产生中间代Xr(t)； (5)对Xr(t)应用其它的算子，产生新一代群体X(t+1)，这些算子的目的在于扩展有限个体的覆盖面，体现全局搜索的思想； (6)t:=t+1；如果不满足终止条件继续(3),2021/1/1,华中农业大学理学院,49,GA中最常用的算子,(1)选择算子(selection/reproduction): 选择算子从群体中按某一概率成对选择个体，某个体xi被选择的概率Pi与其适应度值成正比。最通常的实现方法是轮盘赌(roulett e wheel)模型。 (2)交叉算子(Crossover): 交叉算子将被选中的两个个体的基因链按概率p

30、c进行交叉，生成两个新的个体，交叉位置是随机的。其中Pc是一个系统参数。 (3)变异算子(Mutation): 变异算子将新个体的基因链的各位按概率pm进行变异，对二值基因链(0,1编码)来说即是取反。 上述各种算子的实现是多种多样的，而且许多新的算子正不断提出，以改进GA的某些性能。系统参数(个体数n,基因链长度l,交叉概率Pc,变异概率Pm等)对算法的收敛速度及结果有很大的影响，应视具体问题选取不同的值。,2021/1/1,华中农业大学理学院,50,TPopulation类包含两个重要过程： FillFitness:评价函数，对每个个体进行解码(decode)并计算出其适应度值，具体操作在

31、用户类中实现。 Statistic:对当前群体进行统计，如求总适应度sumfitness、平均适应度average、最好个体fmax、最坏个体fmin等。 TSGA类在TPopulation类的基础上派生，以GA的系统参数为构造函数的参数，它有4个重要的成员函数： Select:选择算子，基本选择策略采用轮盘赌模型。轮盘经任意旋转停止后指针所指向区域被选中，所以fi值大的被选中的概率就大。 Crossover:交叉算子，以概率Pc在两基因链上的随机位置交换子串。 Mutation:变异算子，以概率Pm对基因链上每一个基因进行随机干扰(取反)。 Generate: 产生下代，包括了评价、统计、选

32、择、交叉、变异等全部过程，每运行一 次，产生新的一代。,2021/1/1,华中农业大学理学院,51,二、遗传算法的主要特征,遗传算法目的是获得“最好解”，可以把这种任务看成是一个优化过程。 对于小空间，经典的穷举法就足够了； 而对大空间，则需要使用特殊的人工智能技术。 遗传算法(Genetic Algorithm)是人工智能技术中的一种，是一类模拟生物进化过程而产生的,由选择算子、杂交算子和变异算子三个基本算子组成的全局寻优算法。 过程： 它从一个初始族出发，由选择算子选出性状好的父本，由杂交算子进行杂交运算，变异算子进行少许变异，在一定概率规则控制下随机搜索模型空间。一代代进化，直到最终解族

33、对应的误差泛函值达到设定的要求。,2021/1/1,华中农业大学理学院,52,遗传算法的结构： Procedure Genetic Algorithm begin t=0 initialize p(t) evaluate p(t) while (not termination-condition) do begin t=t+1 select p(t) from p(t-1) alter p(t) evaluate p(t) end end,二、遗传算法的主要特征：,图1遗传算法的结构：,2021/1/1,华中农业大学理学院,53,在第次迭代，遗传算法维持一个潜在解的群体,每个解,用其“适应值”

34、评价。然后通过选择更合适个体（t+1 次迭代）形成一个新的群体。新的群体的成员通过杂交和变异进行变换，形成新的解。杂交组合了两个亲体染色体（即待求参数的二进制编码串）的特征，通过交换父代相应的片断形成了两个相似的后代。,例如父代染色体为,和,在第二个基因后杂交，产生的后代为,和,二、遗传算法的主要特征：,2021/1/1,华中农业大学理学院,54,杂交算子的目的是在不同潜在解之间进行信息交换。变异是通过用一个等于变异率的概率随机地改变被选择染色体上的一个或多个基因（染色体中的一个二进制位）。变异算子的意图是向群体引入一些额外的变化性。,二、遗传算法的主要特征：,2021/1/1,华中农业大学理

35、学院,55,遗传算法的特点： (1).它不是直接作用于参变量集上，而是作用于参变量的某种编码形成的数字串上。 (2).它不是从单个点，而是从一个解族开始搜索解空间，与传统“点对点”式的搜索方法不同。 (3).它仅仅利用适应值信息评估个体的优劣，无须求导数或其它辅助信息。 (4).它利用概率转移规则，而非确定性规则。,优势： (1). 不容易陷入局部极值，能以很大的概率找到全局最优解。 (2). 由于其固有的并行性，适合于大规模并行计算。,2021/1/1,华中农业大学理学院,56,三、遗传算法的运行步骤：,1. 一般性描述： 不失一般性，考虑求最大值的问题。问题：,2021/1/1,华中农业大

36、学理学院,57,1) 编码和解码 2)产生潜在解初始群体 3)根据适应值评价解的适应程度并据此生成新群体 4)杂交(crossover)和变异(mutation)决定新群体的性状 随着选择、杂交和变异的进行，新群体就为下一次的评价做好了准备。该评价是用来为下一次选择过程建立概率分布的，即建立一个根据当前适应值构造宽距的轮盘。其它的部分只是上述步骤的循环重复,三、遗传算法的运行步骤：,2021/1/1,华中农业大学理学院,58,1) 编码和解码,2021/1/1,华中农业大学理学院,59,2)产生潜在解初始群体,简单地以位的方式随机地设定pop_size个染色体。如果确实有一些关于最优分布的知识

37、，可以使用这些信息来设定初始潜在解的集合。,2021/1/1,华中农业大学理学院,60,3)根据适应值评价解的适应程度并据此生成新群体,通常使用一个根据适应值调节刻度宽度的轮盘。按照如下方法构造轮盘（假设这里的适应值时正值，否则可以使用一些比例机制调整）：,2021/1/1,华中农业大学理学院,61,2021/1/1,华中农业大学理学院,62,4)杂交(crossover)和变异(mutation)决定新群体的性状,2021/1/1,华中农业大学理学院,63,随着选择、杂交和变异的进行，新群体就为下一次的评价做好了准备。该评价是用来为下一次选择过程建立概率分布的，即建立一个根据当前适应值构造宽

38、距的轮盘。其它的部分只是上述步骤的循环重复，见图1。,2021/1/1,华中农业大学理学院,64,例1：,2021/1/1,华中农业大学理学院,65,1)解码和解码：,变量的定义域长度为15.1，所要求的精度意味着区间-3.0, 12.1至少要被分为15.110000个等距区间。由于，因此染色体的第一部分需要18位。,2021/1/1,华中农业大学理学院,66,(010001001011010000111110010100010) 的前18位010001001011010000表示,2021/1/1,华中农业大学理学院,67,2) 产生潜在解初始群体：,2021/1/1,华中农业大学理学院,6

39、8,3)根据适应值评价解的适应程度并据此生成新群体：,2021/1/1,华中农业大学理学院,69,3)根据适应值评价解的适应程度并据此生成新群体：,2021/1/1,华中农业大学理学院,70,2021/1/1,华中农业大学理学院,71,4) 杂交(crossover)和变异(mutation)决定新群体的性状：,2021/1/1,华中农业大学理学院,72,2021/1/1,华中农业大学理学院,73,2021/1/1,华中农业大学理学院,74,群体的当前版本为：,2021/1/1,华中农业大学理学院,75,2021/1/1,华中农业大学理学院,76,表2.2把染色体中的位号翻译成染色体中的位数：

40、,2021/1/1,华中农业大学理学院,77,2021/1/1,华中农业大学理学院,78,2021/1/1,华中农业大学理学院,79,2021/1/1,华中农业大学理学院,80,但是，仔细检查整个运行过程，可以发现早期代中的某些染色体的适应值要好于经过1000代后的最好染色体值35.47938。例如，第396代中的最好染色体的值为38.827553。这是由于取样的随机误差造成的。跟踪进化过程中的最好个体是容易的。在遗传算法的实现中，通常在一独立出来的位置保存“曾经最好”的个体；用这种方法，算法将报告整个过程的最好值，而不只是最终群体的最好值。,2021/1/1,华中农业大学理学院,81,例2：

41、,为四个连锁饭店寻找最好的经营决策，其中一个经营饭店的决策包括要做出以下三项决定： （1）价格 汉堡包的价格应该定在50美分还是1美元？ （2）饮料 和汉堡包一起供应的应该是酒还是可乐？ （3）服务速度 饭店应该提供慢的还是快的服务？ 目的：找到这三个决定的组合以产生最高的利润。 上述问题的表示方案： 串长 (l3）字母表规模（ k2） 映射 共有8种表示方案 遗传算法解这个问题的第一步就是选取一个适当的表示方案。,2021/1/1,华中农业大学理学院,82,表1 饭店问题的表示方案（其中的4个）,群体规模N4,2021/1/1,华中农业大学理学院,83,表2 初始群体中经营决策的适应值,一个

42、简单的遗传算法由复制、杂交、变异三个算子组成,2021/1/1,华中农业大学理学院,84,表3 使用复制算子后产生的交配池,1.复制算子：采用赌盘选择,2021/1/1,华中农业大学理学院,85,2.杂交算子：采用一点杂交,作用过程：a）产生一个在1到l1之间的随机数i b）配对的两个串相互对应的交换从i1到l的位段,例如：从交配池中选择编号为1和2的串进行配对，且杂交点选在2（用分隔符|表示），杂交算子作用的结果为： 01 | 1 010 11 | 0 111,对交配池中指定百分比的个体应用杂交算子，假设杂交概率pc50，交配池中余下的50个体仅进行复制运算，即复制概率pr50。,2021/

43、1/1,华中农业大学理学院,86,表4 使用复制和杂交算子的作用结果,遗传算法利用复制和杂交算子可以产生具有更高平均适应值和更好个体的群体,2021/1/1,华中农业大学理学院,87,3.变异算子：以一个很小的概率pm随机改变染色体串上的某些位。 对于二进制串，就是将相应位上的0变为1或将1变为0。,例如：选交配池中编号为4的串进行变异，且变异点在2，则 010 000,变异算子相对而言，是次要算子，但在恢复群体中失去的多样性方面具有潜在的作用。,2021/1/1,华中农业大学理学院,88,如图所示：该函数有多个局部极大点。,2021/1/1,华中农业大学理学院,89,构造过程：第一步：确定决

44、策变量及其约束条件。,第三步：确定编码方法。用长度为22位的二进制编码串来分别表示决策变量x。,2021/1/1,华中农业大学理学院,90,22位二进制编码串可以表示从0到4194303之间的4194304个不同的数，故将x的定义域离散化为4194304个均等的区间，包括两个端点在内共有4194304个不同的离散点。从离散点0到离散点9，依次让它们分别对应于从0000000000000000000000(0)到1111111111111111111111(41943043)之间的二进制编码。这就构成了这个函数优化问题的染色体编码方法。 例如X：0000000000001101110001 就表

45、示一个个体的基因型。,2021/1/1,华中农业大学理学院,91,第四步：确定解码方法。,解码时将22位长的二进制编码转换为对应的十进制整数代码，记为y。依据前述个体编码方法相对定义域的离散化方法可知，将代码y转换为变量x的解码公式为：,例如，对前述个体X：00000000001101110001 它由这样的下列代码所组成：y= 881经上式的解码处理后，得到：x = 0.001890421x=,2021/1/1,华中农业大学理学院,92,第五步：确定个体评价方法。,由于目标函数的取值可正可负，并且优化目标是求函数的最大值，故这里可将个体的适应度取为每次迭代的最小值的绝对值加上目标函数值，即有

46、：,第六步：设计遗传算子。选择运算使用比例选择算子；交叉运算使用单点交叉算子；变异运算使用基本位变异算子。,2021/1/1,华中农业大学理学院,93,第七步：确定遗传算法的运行参数。,对于本例，设定基本遗传算法的运行参数如下： 群体大小: N50 终止代数: ger100 交叉概率：pc0.65 变异概率：pm0.05,2021/1/1,华中农业大学理学院,94,2021/1/1,华中农业大学理学院,95,2021/1/1,华中农业大学理学院,96,由该组图我们可以看出，随着进化过程的进行，群体中适应度较低的一些个体被逐渐淘汰掉，而适应度较高的一些个体会越来越多并且它们都集中在所求问题的最优

47、点附近，从而最终就可搜索到问题的最优解。,2021/1/1,华中农业大学理学院,97,小结,遗传算法描述了从第0代产生第1代的过程，然后遗传算法迭代地执行这个过程，直到满足某个停止准则。在每一代中，算法首先计算群体中每个个体地适应值，然后利用适应值信息，遗传算法分别以概率pc 、 pr 和pm 执行杂交、复制和变异操作，从而产生新的群体。 应用遗传算法求解问题需完成四个主要步骤： 1.确定表示方案 2.确定适应值度量 3.确定控制算法的参数和变量 4.确定指定结果的方法和停止运行的准则,2021/1/1,华中农业大学理学院,98,四、基本遗传算法的构成要素,1.染色体编码方法 最常用的是二进制

48、编码，对于离散性变量直接编码，对于连续性变量先离散化后再编码 2.适应度函数 评估函数用来评估一个染色体的优劣的绝对值 适应度函数评估一个染色体相对整个群体的优劣的相对值的大小,2021/1/1,华中农业大学理学院,99,基本遗传算法一般采用下面两种方法之一将目标函数值f(x)变换为个体的适应度F(x)：,2021/1/1,华中农业大学理学院,100,其中，Cmax是一个适当地相对比较大的数，它可用下面几种方法求得： 预先指定的一个较大的数。 进化到当前代为止的最大目标函数值。 当前代或最近几代群体中的最大目标函数值。,2021/1/1,华中农业大学理学院,101,3.遗传算子复制算子、交叉算

49、子、变异算子,2021/1/1,华中农业大学理学院,102,4.基本遗传算法运行参数 N：群体大小，即群体中所含个体的数量，一般取20100 T：遗传算法的终止进化代数，一般取100500 pc：杂交概率，一般取0.40.99 pm ：变异概率，一般取0.00010.1 pr ：复制概率,2021/1/1,华中农业大学理学院,103,四、基本遗传算法的一般框架,算法过程： 1.随机产生一个由确定长度的特征串组成的初始群体 2.对串群体迭代地执行下面的步（i）和步（ii），直到满足停止准则： （i）计算群体中每个个体的适应值 （ii）应用复制、杂交和变异算子产生下一代群体 3.把在任一代中出现地

50、最好地个体串指定为遗传算法的执行结果，这个结果可以表示问题的一个解（或近似解）,2021/1/1,华中农业大学理学院,104,2021/1/1,华中农业大学理学院,105,五、遗传算法的数学理论,几个相关的定义： 1、模式是一个相同的构形，它描述的是一个串的子集，这个集合中串之间在某些位上相同。 例如，添加符号*表示不确定字母，即0或1，考虑串长为7的模式H*11*0*，则串A0111000是模式H的一个表示，对于基数为k的字母表，每一个串有（k1）l 个模式。 2、模式的阶出现在模式中确定位置的数目。在二进制中，一个模式的阶就是所有的1或0的数目。 例如，模式H*11*0*的阶为3 3、模式

51、的定义长度模式中第一个确定位置与最后一个确定位置之间的距离 例如，模式H*11*0*的定义长度r523,2021/1/1,华中农业大学理学院,106,定理1（模式定理）：具有短的定义长度、低阶并且适应值在群体平均适应值以上的模式在遗传算法迭代过程中将按指数增长率被采样。 模式定理揭示了遗传算法为什么有效！ 定理2（隐并行性）：ns n3, 其中 ns 有效模式数 n群体规模 该定理表明，每一代中除了仅对n个串的处理外，遗传算法实际上处理大约O（n3）个模式，从而每代只执行与群体规模成比例的计算量，就可以同时收到并行地对大约O（n3）个模式进行有效处理的目的，并且无须额外的存储。 定理3（积木块假设）：低阶、短距、高平均适应值的模式（积木块）在遗传算子的作用下，相互结合，能生成高阶、长距、高平均适应值的模式，