遗传算法遗传算法 人工智能导论7/26/20242华中农业大学理学院 第1章 人工智能概述 1.1 什么是人工智能 1.2 人工智能的研究意义、目标和策略 1.3 人工智能的学科范畴 1.4 人工智能的研究内容 1.5 人工智能的研究途径与方法 1.6 人工智能的基本技术 1.7 人工智能的应用 1.8 人工智能的分支领域与研究方向 1.9 人工智能的发展概况 7/26/20243华中农业大学理学院 1.1 什么是人工智能人工智能（Artificial Intelligence”，AI）1.1.1 人工智能概念的一般描述 部分学者对人工智能概念的描述： 人工智能是那些与人的思维相关的活动，诸如决策、问题求解和学习等的自动化（Bellman, 1978）； 人工智能是一种计算机能够思维，使机器具有智力的激动人心的新尝试（Haugeland, 1985）；人工智能是研究如何让计算机做现阶段只有人才能做得好的事情（Rich Knight,1991）；7/26/20244华中农业大学理学院 人工智能是那些使知觉、推理和行为成为可能的计算的研究（Winston, 1992）； 广义地讲，人工智能是关于人造物的智能行为，而智能行为包括知觉、推理、学习、交流和在复杂环境中的行为（Nilsson，1998）。 Stuart Russell和Peter Norvig则把已有的一些人工智能定义分为4类：像人一样思考的系统、像人一样行动的系统、理性地思考的系统、理性地行动的系统（2003）。7/26/20245华中农业大学理学院1.1.2 图灵测试和中文屋子图灵测试”（TuringTest）7/26/20246华中农业大学理学院约翰.西尔勒(JohnSearle)的“中文屋子中文屋子”7/26/20247华中农业大学理学院1.1.3 脑智能和群智能脑（主要指人脑）的宏观心理层次的智能表现称为脑智能脑智能（Brain Intelligence, BI）。由群体行为所表现出的智能称为群群智智能能（Swarm Intelligence, SI）。脑智能和群智能是属于不同层次的智能： 脑智能是一种个个体体智智能能（Individual Intelligence, II）； 群智能是一种社社会会智智能能（Social Intelligence, SI）， 或者说系统智能系统智能（System Intelligence, SI）。7/26/20248华中农业大学理学院1.1.4 符号智能和计算智能1. 符号智能符号智能符号智能就是符号人工智能，它是模拟脑智能的人工智能，也就是所说的传统人工智能或经典人工智能。符号智能以符号形式的知识和信息为基础，主要通过逻辑推理，运用知识进行问题求解。符号智能的主要内容包括知识获取（knowledge acquisition）、知识表示（knowledge representation）、知识组织与管理和知识 运 用 等 技 术 （ 这 些 构 成 了 所 谓 的 知 识 工 程（Knowledge Engineering, KE）以及基于知识的智能系统等。7/26/20249华中农业大学理学院 2. 计算智能计算智能计算智能就是计算人工智能，它是模拟群智能的人工智能。计算智能以数值数据为基础，主要通过数值计算，运用算法进行问题求解。计算智能的主要内容包括：神经计算（Neural Computation， NC）、进化计算（亦称演化计算，Evolutionary Computation，EC，包括遗传算法（Genetic Algorithm，GA）、进化规划（ Evolutionary Planning， EP） 、 进 化 策 略（Evolutionary Strategies，ES）等）、免疫计算（immune computation）、粒群计算（Particle Swarm Algorithm，PSA）、蚁群算法（Ant Colony Algorithm，ACA）、自然计算（Natural Computation，NC）以及人工生命（Artificial Life，AL）等。7/26/202410华中农业大学理学院1.2 人工智能的研究意义、目标和策略1.2.1 为什么要研究人工智能使当前的电脑更好用，更有用，以扩大和延伸人类智能；信息化社会的迫切要求；自动化发展的必然趋势；有益于探索人类自身智能的奥秘。7/26/202411华中农业大学理学院1.2.2 人工智能的研究目标和策略研究目标就是制造智能机器和智能系统，实现智能化社会。具体来讲，就是要使计算机不仅具有脑智能和群智能，还要具有看、听、说、写等感知和交流能力。研究策略则是先部分地或某种程度地实现机器的智能，并运用智能技术解决各种实际问题特别是工程问题，从而使现有的计算机更灵活、更好用和更有用，成为人类的智能化信息处理工具，而逐步扩展和不断延伸人的智能，逐步实现智能化。7/26/202412华中农业大学理学院 1.3 人工智能的学科范畴人工智能已构成信息技术领域的一个重要学科。当前的人工智能既属于计算机科学技术的一个前沿领域，也属于信息处理和自动化技术的一个前沿领域。还涉及到智能科学、认知科学、心理科学、脑及神经科学、生命科学、语言学、逻辑学、行为科学、教育科学、系统科学、数理科学以及控制论、科学方法论、哲学甚至经济学等众多学科领域。人工智能实际上是一门综合性的交叉学科和边缘学科。7/26/202413华中农业大学理学院 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 应用与工程7/26/202414华中农业大学理学院 1.5 人工智能的研究途径与方法1.5.1 心理模拟，符号推演1.5.2 生理模拟，神经计算1.5.3 行为模拟，控制进化1.5.4 群体模拟，仿生计算1.5.5 博采广鉴，自然计算1.5.6 原理分析，数学建模7/26/202415华中农业大学理学院 1.6 人工智能的基本技术表示运算搜索7/26/202416华中农业大学理学院 1.7 人工智能的应用1.7.1 难题求解1.7.2 自动规划、调度与配置1.7.3 机器定理证明1.7.4 自动程序设计1.7.5 机器翻译1.7.6 智能控制1.7.7 智能管理1.7.8 智能决策1.7.9 智能通信1.7.10 智能仿真7/26/202417华中农业大学理学院1.7.11 智能CAD1.7.12 智能制造1.7.13 智能CAI1.7.14 智能人机接口1.7.15 模式识别1.7.16 数据挖掘与数据库中的知识发现1.7.17 计算机辅助创新1.7.18 计算机文艺创作1.7.19 机器博弈1.7.20 智能机器人7/26/202418华中农业大学理学院 1.8 人工智能的分支领域与研究方向从模拟的层次和所用的方法来看，人工智能可分为符号智能和计算智能两大主要分支领域。而这两大领域各自又有一些子领域和研究方向。如符号智能中又有图搜索、自动推理、不确定性推理、知识工程、符号学习等。计算智能中又有神经计算、进化计算、免疫计算、蚁群计算、粒群计算、自然计算等。另外，智能Agent也是人工智能的一个新兴的重要领域。智能Agent或者说Agent智能则是以符号智能和计算智能为基础的更高一级的人工智能。从模拟的脑智能或脑功能来看，AI中有机器学习、机器感知、机器联想、机器推理、机器行为等分支领域。而机器学习又可分为符号学习、连接学习、统计学习等许多研究领域和方向。机器感知又可分为计算机视觉、计算机听觉、模式识别、图像识别与理解、语音识别、自然语言处理等领域和方向。7/26/202419华中农业大学理学院从应用角度看，如1.7节所述，AI中有难题求解等数十种分支领域和研究方向。从系统角度看，有智能计算机系统和智能应用系统两大类。智能计算机系统又可分为：智能硬件平台、智能操作系统、智能网络系统等。智能应用系统又可分为：基于知识的智能系统、基于算法的智能系统和兼有知识和算法的智能系统等。另外，还有分布式人工智能系统。从基础理论看，AI中有数理逻辑和多种非标准逻辑、图论、人工神经网络、模糊集、粗糙集、概率统计（贝叶斯统计决策理论）和贝叶斯网络、统计学习理论与支持向量机、形式语言与自动机等领域和方向。7/26/202420华中农业大学理学院 1.9 人工智能学科的发展概况1.9.1 人工智能学科的产生1.9.2 符号主义途径发展概况1.9.3 连接主义途径发展概况1.9.4 计算智能异军突起1.9.5 智能Agent方兴未艾7/26/202421华中农业大学理学院1.9.6 现状与发展趋势多种途径齐头并进，多种方法协作互补。新思想、新技术不断涌现，新领域、新方向不断开拓。理论研究更加深入，应用研究愈加广泛。研究队伍日益壮大，社会影响越来越大。7/26/202422华中农业大学理学院虽然在通向人工智能最终目标的道路上，还有不少困难、问题和挑战，但前进和发展毕竟是大势所趋。 7/26/202423华中农业大学理学院智能交通7/26/202424华中农业大学理学院图像识别系统7/26/202425华中农业大学理学院 云松 銮仙玉骨寒， 松虬雪友繁。 大千收眼底， 斯调不同凡。 7/26/202426华中农业大学理学院 （无题） 白沙平舟夜涛声， 春日晓露路相逢。 朱楼寒雨离歌泪， 不堪肠断雨乘风。 7/26/202427华中农业大学理学院7/26/202428华中农业大学理学院7/26/202429华中农业大学理学院7/26/202430华中农业大学理学院7/26/202431华中农业大学理学院遗传算法遗传算法主要内容主要内容一、遗传算法入门一、遗传算法入门二、遗传算法的主要特征二、遗传算法的主要特征三、遗传算法的运行步骤三、遗传算法的运行步骤四、基本遗传算法的构成要素四、基本遗传算法的构成要素五、遗传算法的数学理论五、遗传算法的数学理论六、遗传算法的基本实现技术六、遗传算法的基本实现技术七、遗传算法的特点七、遗传算法的特点八、遗传算法的应用八、遗传算法的应用7/26/202432华中农业大学理学院遗遗传传算算法法(Genetic (Genetic Algorithm, Algorithm, GA)GA)是是近近几几年年发发展展起起来来的的一一种种崭崭新新的的全全局局优优化化算算法法，它它借借用用了了生生物物遗遗传传学学的的观观点点，通通过过自自然然选选择择、遗遗传传、变变异异等等作作用用机机制制，实实现现各各个个个个体体的的适适应应性性的的提提高高。这这一一点点体体现现了了自自然然界界中中“物物竞竞天天择择、适适者者生生存存”进进化化过过程程。19621962年年HollandHolland教教授授首首次次 提提出出了了GAGA算算法法的的思思想想，从从而而吸吸引引了了大大批批的的研研究究者者，迅迅速速推推广广到到优优化化、搜搜索索、机机器器学学习习等等方方 面面，并并奠奠定定了了坚实的理论基础。坚实的理论基础。遗遗传传算算法法是是 John John HollandHolland大大脑脑的的产产物物，早早在在上上个个世世纪纪6060年年代代，他他已已提提出出了了这这种种想想法法。但但不不可可思思议议的的是是，他他没没有有感感到到需需要要在在计计算算机机上上实实际际试试验验出出结结果果，而而宁宁愿愿利利用用笔笔和和纸纸来来作作修修修修补补补补的的工工作作！ 直直到到后后来来他他的的一一名名学学生生编编写写出出程程序序并并在在一一台台个个人人计计算算机机上上运运行行后后，才才使使人人们终于看到在软件中利用他的思想能够得到什么。们终于看到在软件中利用他的思想能够得到什么。 一、遗传算法入门7/26/202433华中农业大学理学院一、遗传算法入门生物只有经过许多世代的不断演化（evolution），才能更好地完成生存与繁衍的任务。遗传算法也遵循同样的方式，需要随着时间的推移不断成长、演化，最后才能收敛，得到针对某类特定问题的一个或多个解。因此，了解一些有关有生命的机体如何演化的知识，对理解遗传算法的演化机制是是有帮助的。我们将扼要阐述自然演化的机制（通常称为“湿”演化算法），以及与之相关的术语。理解自然演化的基本机制。我想，你也会和我一样，深深叹服自然母亲的令人着迷！7/26/202434华中农业大学理学院本质上说，任何生物机体就是一大堆细胞的集合。每个细胞都包含若干组相同的DNA链，人们一般称之为染色体（chromosome）。染色体中包含的DNA分为两股，这两股DNA链以螺旋状绞合在一起，如下面图所示那样，这就是我们所熟悉的DNA双螺旋结构模型。DNA双螺旋结构双螺旋结构一、遗传算法入门7/26/202435华中农业大学理学院单个染色体是由称作基因（gene）的更小的结构模块组成，而基因则又由称作核苷酸（nucleotide）的物质组成。核苷酸一共只有四种类型，即：腺嘌呤(thymine)、鸟嘌 呤 (adenine)、 胞 嘧 啶 (cytocine)、 胸 腺 嘧 啶(guanine)。常简写为T、A、C、G。这些核苷酸相互连接起来，形成若干很长的基因链，而每个基因编码了生物机体的某种特征，如头发的颜色，耳朵的样子，等。一个基因可能具有的不同设置（如头发的黑色、棕色或金黄色），称为等位基因（allele），它们沿染色体纵向所处的物理部位称为基因的座位（locus）。一、遗传算法入门7/26/202436华中农业大学理学院二进制数速成（AQuickLessoninBinaryNumbers）16842个位1111数字15如果要把15写成8位的二进制，则要写成下面这样的形式，其中高位都是，但也要把前面写出来，以使整个长度达到：000011117/26/202437华中农业大学理学院计算机内的进化（EvolutionInsideYourComputer）遗传算法工作过程本质上就是模拟生物的进化过程。遗传算法工作过程本质上就是模拟生物的进化过程。首首先先，要要规规定定一一种种编编码码方方法法，使使得得你你的的问问题题的的任任何何一一个个潜潜在可行解都能表示成为一个在可行解都能表示成为一个“数字数字”染色体。染色体。然然后后，创创建建一一个个由由随随机机的的染染色色体体组组成成的的初初始始群群体体（每每个个染染色色体体代代表表了了一一个个不不同同的的候候选选解解），并并在在一一段段时时期期中中，以以培培育育适适应应性性最最强强的的个个体体的的办办法法，让让它它们们进进化化，在在此此期期间间，染染色体的某些位置上要加入少量的变异。色体的某些位置上要加入少量的变异。经过许多代后，运气好一点，遗传算法会收敛到一个解。经过许多代后，运气好一点，遗传算法会收敛到一个解。遗遗传传算算法法不不保保证证一一定定能能得得到到解解，也也不不保保证证找找到到的的是是最最优优解解，但但只只要要采采用用的的方方法法正正确确，通通常常都都能能为为遗遗传传算算法法编编出出一一个个能能够很好运行的程序。够很好运行的程序。遗遗传传算算法法的的最最大大优优点点就就是是， 你你不不需需知知道道怎怎么么去去解解决决一一个个问问题题; ; 需需要要知知道道的的仅仅是是，用用怎怎么么方方式式对对可可行行解解进进行行编编码码，使得它能能被遗传算法机制所利用。使得它能能被遗传算法机制所利用。7/26/202438华中农业大学理学院通通常常，代代表表可可行行解解的的染染色色体体采采用用一一系系列列的的二二进进制制位位作作为为编编码码。在在运运行行开开始始时时，创创建建一一个个染染色色体体的的群群体体，每每个个染染色色体体都都是是一一组组随随机机的的进进制制位位。进进制制位位（即即染染色体）的长度在整个群体中都是一样的。色体）的长度在整个群体中都是一样的。作为一个例子，长度为作为一个例子，长度为 2020的染色体的形状如下的染色体的形状如下: : 01010010100101001111重重要要的的事事情情是是，每每个个染染色色体体都都用用这这样样的的方方式式编编码码成成为为由由0和和1组组成成的的字字符符串串，而而它它们们通通过过译译码码就就能能用用来来表表示示你你手手头头问问题题的的一一个个解解。这这可可能能是是一一个个很很差差的的解解，也也可可能能是是一一个个十十分分完完美美的的解解，但但每每一一个个单单个个的的染染色色体体都都代代表表了了一一个个可可行行解解。初初始始群群体体通通常常都都是是较较糟糟的的，有有点点中中国国男男足足球球队队。但但，一一个个初初始始的的群群体体已已经经创创建建完完成成（对对这这一一例例子子，不不妨妨设设共共有有100个个成成员员），这这样样，就就可以开始做下面列出的一系列工作。可以开始做下面列出的一系列工作。7/26/202439华中农业大学理学院不断进行下列循环，直到寻找出一个解:1.检查每个染色体，看它解决问题的性能怎样，并相应地为它分配一个适应性分数。2.从当前群体中选出2个成员。被选出的概率正比于染色体的适应性，适应性分数愈高，被选中的可能性也就愈大。常用的方法就是采用所谓的轮盘赌选择法或赌轮选择法(Roulettewheelselection)。3.按照预先设定的杂交率（CrossoverRate），从每个选中染色体的一个随机的点上进行杂交（crossover）。4.按照预定的变异率（mutationrate），通过对被选染色体的位的循环，把相应的位实行翻转（flip）。5.重复步骤2，3，4，直到100个成员的新群体被创建出来。结束循环以上算法中步骤1到步骤5的一次循环称为一个代（或世代，generation）。而我把这整个的循环称作一个时代（epoch）。7/26/202440华中农业大学理学院什么是轮盘赌选择？(WhatstheRouletteWheelSelection)轮盘赌选择是从染色体群体中选择一些成员的方法，被选中的机率和它们的适应性分数成比例，染色体的适应性分数愈高，被选中的概率也愈多。这不保证适应性分数最高的成员一定能选入下一代，仅仅说明它有最大的概率被选中。其工作过程是这样的：设想群体全体成员的适当性分数由一张饼图来代表(见下图)，这一饼图就和用于赌博的转轮形状一样。我们要为群体中每一染色体指定饼图中一个小块。块的大小与染色体的适应性分数成比例，适应性分数愈高，它在饼图中对应的小块所占面积也愈大。为了选取一个染色体，你要做的，就是旋转这个轮子，并把一个小球抛入其中，让它翻来翻去地跳动，直到轮盘停止时，看小球停止在哪一块上，就选中与它对应的那个染色体。染色体的轮盘赌式选择7/26/202441华中农业大学理学院轮盘赌选择轮盘赌选择SGenome&CgaBob:RouletteWheelSelection()doublefSlice=RandFloat()*m_dTotalFitnessScore;我们从零到整个适应分范围内随机选取了一实数fSlice。把此数看作整个适应性分数饼图中的一块。doublecfTotal=O;intSelectedGenome=0;for(inti=O;ifSlice)SelectedGenome=i;break;returnm_vecGenomesSelectedGenome;程序通过循环来考察各基因组，把它们相应的适应性分数程序通过循环来考察各基因组，把它们相应的适应性分数一个一个累加起来，直到这一一个一个累加起来，直到这一部分累加和部分累加和大于大于fSlice值时，值时，就返回该基因组。就返回该基因组。7/26/202442华中农业大学理学院什么是杂交率？(WhatstheCrossoverRate)杂交率就是用来确定2个染色体进行局部的位（bit）的互换以产生2个新的子代的概率。实验表明这一数值通常取为0.7左右是理想的，尽管某些问题领域可能需要更高一些或较低一些的值。每次，从群体中选择2个染色体，同时生成其值在0到1之间一个随机数，然后根据此数据的值来确定两个染色体是否要进行杂交。如果数值低于杂交率(O.7)就进行杂交，就沿着染色体的长度随机选择一个位置，并把此位置后面所有的位进行互换。例如，设给定的2个染色体为:1000100111001001001010001001000011沿着它们的长度你随机选择一个位置，比如说10，然后互换第10位之后所有位。这样两个染色体就变成了：10001001101000011010100010100100107/26/202443华中农业大学理学院杂交操作杂交操作（CrossoverRevisited）这一函数要求个染色体在同一随机位置上断裂开，然后将它们在断开点这一函数要求个染色体在同一随机位置上断裂开，然后将它们在断开点以后部分进行互换，以形成以后部分进行互换，以形成2个新的染色体个新的染色体(子代子代)。voidCgaBob:Crossover(constvector&mum,constvector&dad,vector&baby1,vector&baby2)这一函数共传入这一函数共传入4个参数，参数传递均采用引用个参数，参数传递均采用引用reference方式，其中前方式，其中前2个传入父辈个传入父辈parent的染色体（染色体只是一个整数型的矢量的染色体（染色体只是一个整数型的矢量std:vector），），后后2个是用来个是用来copy子代染色体的空矢量。子代染色体的空矢量。if(RandFloat()m-dCrossoverRate)|(mum=dad)baby1=mum;baby2=dad;return;这里，首先是进行检测，看这里，首先是进行检测，看mum和和dad两个上辈是否需要进行杂交。两个上辈是否需要进行杂交。杂杂交发生的概率是由参数交发生的概率是由参数m_dCrossoverRate确定。确定。如果不发生杂交，则如果不发生杂交，则个上辈染色体就直接复制为子代，函数立即返回。个上辈染色体就直接复制为子代，函数立即返回。intcp=RandInt(0,m_iChromoLength-1)；沿染色体的长度随机沿染色体的长度随机选择一个点来裂开染色体。选择一个点来裂开染色体。for(inti=0;icp;i+)baby1.push_back(mumi);baby2.push_back(dadi);for(i=cp;imum.size();i+)baby1.push_back(dadi);baby2.push_back(mumi);这这两两循循环环把把2个个parent染染色色体体在在杂杂交交点点（CP,crossoverpoint）以以后后的的所有位进行了互换，并把新染色体赋给了所有位进行了互换，并把新染色体赋给了2个子代个子代:baby1和和baby2。7/26/202444华中农业大学理学院什么是变异率？(WhatstheMutationRate?)变异率（突变率）就是在一个染色体中将位实行翻转（flip，即0变1，1变0）的几率。这对于二进制编码的基因来说通常都是很低的值，比如0.001。因此，无论你从群体中怎样选择染色体，你首先是检查是否要杂交，然后再从头到尾检查子代染色体的各个位，并按所规定的几率对其中的某些位实行突变（翻转）。7/26/202445华中农业大学理学院变异操作变异操作（MutationRevisited）这一函数所做的工作，不过就是沿着一个染色体的长度，一bit一bit地进行考察，并按m_dMutationRate给定的几率，将其中某些bit实行翻转。voidCgaBob:Mutate(vector&vecBits)for(intcurBit=0;curBitvecBits.size();curBit+)/是否要翻转此bit?if(RandFloat()m_dMutationRate)/是，就翻转此bitvecBitscurBit=!vecBitscurBit;/移到下一个bit遗传算法程序也就这样完成了！遗传算法程序也就这样完成了！7/26/202446华中农业大学理学院用遗传算法解决问题时，首先要对待解决问题的模型结构和参数进行编码，一般用字符串表示，这个过程就将问题符号化、离散化了。也有在连续空间定义的GA(GeneticAlgorithminContinuousSpace,GACS)，暂不讨论。： 7/26/202447华中农业大学理学院一个串行运算的遗传算法(Seguential Genetic Algoritm, SGA)按如下过程进行(1)对待解决问题进行编码； (2)随机初始化群体X(0):=(x1, x2, xn)； (3)对当前群体X(t)中每个个体xi计算其适应度F(xi)，适应度表示了该个体的性能好 坏； (4)应用选择算子产生中间代Xr(t)； (5)对Xr(t)应用其它的算子，产生新一代群体X(t+1)，这些算子的目的在于扩展有限个体的覆盖面，体现全局搜索的思想； (6)t:=t+1；如果不满足终止条件继续(3) 7/26/202448华中农业大学理学院GA中最常用的算子(1)选择算子(selection/reproduction): 选择算子从群体中按某一概率成对选择个体，某个体xi被选择的概率Pi与其适应度值成正比。最通常的实现方法是轮盘赌(roulett e wheel)模型。 (2)交叉算子(Crossover): 交叉算子将被选中的两个个体的基因链按概率pc进行交叉，生成两个新的个体，交叉位置是随机的。其中Pc是一个系统参数。 (3)变异算子(Mutation): 变异算子将新个体的基因链的各位按概率pm进行变异，对二值基因链(0,1编码)来说即是取反。 上述各种算子的实现是多种多样的，而且许多新的算子正不断提出，以改进GA的某些性能。系统参数(个体数n,基因链长度l,交叉概率Pc,变异概率Pm等)对算法的收敛速度及结果有很大的影响，应视具体问题选取不同的值。7/26/202449华中农业大学理学院TPopulation类包含两个重要过程： FillFitness:评 价 函 数 ， 对 每 个 个 体 进 行 解 码(decode)并计算出其适应度值，具体操作在用户类中实现。 Statistic:对当前群体进行统计，如求总适应度sumfitness、平均适应度average、最好个体fmax、最坏个体fmin等。TSGA类在TPopulation类的基础上派生，以GA的系统参数为构造函数的参数，它有4个重要的成员函数： Select:选择算子，基本选择策略采用轮盘赌模型。轮盘经任意旋转停止后指针所指向区域被选中，所以fi值大的被选中的概率就大。 Crossover:交叉算子，以概率Pc在两基因链上的随机位置交换子串。 Mutation:变异算子，以概率Pm对基因链上每一个基因进行随机干扰(取反)。 Generate: 产生下代，包括了评价、统计、选择、交叉、变异等全部过程，每运行一 次，产生新的一代。7/26/202450华中农业大学理学院二、遗传算法的主要特征二、遗传算法的主要特征遗遗传传算算法法目目的的是是获获得得“最最好好解解”，可可以以把把这这种种任任务务看看成是一个优化过程。成是一个优化过程。对于小空间，经典的穷举法就足够了；对于小空间，经典的穷举法就足够了；而对大空间，则需要使用特殊的人工智能技术。而对大空间，则需要使用特殊的人工智能技术。遗遗传传算算法法(Genetic (Genetic Algorithm)Algorithm)是是人人工工智智能能技技术术中中的的一一种种，是是一一类类模模拟拟生生物物进进化化过过程程而而产产生生的的, ,由由选选择择算算子子、杂杂交交算算子子和和变变异异算算子子三三个个基基本本算算子子组组成成的的全全局局寻寻优优算算法。法。过程：过程：它它从从一一个个初初始始族族出出发发，由由选选择择算算子子选选出出性性状状好好的的父父本本，由由杂杂交交算算子子进进行行杂杂交交运运算算，变变异异算算子子进进行行少少许许变变异异，在在一一定定概概率率规规则则控控制制下下随随机机搜搜索索模模型型空空间间。一一代代代代进进化，直到最终解族对应的误差泛函值达到设定的要求。化，直到最终解族对应的误差泛函值达到设定的要求。 7/26/202451华中农业大学理学院遗传算法的结构遗传算法的结构：ProcedureGeneticAlgorithmbegint=0initializep(t)evaluatep(t)while(nottermination-condition)dobegint=t+1selectp(t)fromp(t-1)alterp(t)evaluatep(t)endend二、遗传算法的主要特征：二、遗传算法的主要特征：图1遗传算法的结构遗传算法的结构：7/26/202452华中农业大学理学院在第次迭代，遗传算法维持一个潜在解的群体每个解用其“适应值”评价。然后通过选择更合适个体（t+1次迭代）形成一个新的群体。新的群体的成员通过杂交和变异进行变换，形成新的解。杂交组合了两个亲体染色体（即待求参数的二进制编码串）的特征，通过交换父代相应的片断形成了两个相似的后代。例如父代染色体为和在第二个基因后杂交，产生的后代为和二、遗传算法的主要特征：二、遗传算法的主要特征：7/26/202453华中农业大学理学院杂交算子的目的是在不同潜在解之间进行信息交换。变异是通过用一个等于变异率的概率随机地改变被选择染色体上的一个或多个基因（染色体中的一个二进制位）。变异算子的意图是向群体引入一些额外的变化性。二、遗传算法的主要特征：二、遗传算法的主要特征：7/26/202454华中农业大学理学院遗传算法的特点遗传算法的特点：(1).它不是直接作用于参变量集上，而是作用于参变量的某种编码形成的数字串上。(2).它不是从单个点，而是从一个解族开始搜索解空间，与传统“点对点”式的搜索方法不同。(3).它仅仅利用适应值信息评估个体的优劣，无须求导数或其它辅助信息。(4).它利用概率转移规则，而非确定性规则。优势优势：(1).不容易陷入局部极值，能以很大的概率找到全局最优解。(2).由于其固有的并行性，适合于大规模并行计算。7/26/202455华中农业大学理学院三、遗传算法的运行步骤：三、遗传算法的运行步骤：1.一般性描述：一般性描述：不失一般性，考虑求最大值的问题。问题：问题：7/26/202456华中农业大学理学院1)编码和解码编码和解码2)产生潜在解初始群体产生潜在解初始群体3)根根据据适适应应值值评评价价解解的的适适应应程程度度并并据据此此生生成成新新群体群体4)杂杂交交(crossover)和和变变异异(mutation)决决定定新新群群体体的的性状性状随随着着选选择择、杂杂交交和和变变异异的的进进行行，新新群群体体就就为为下下一一次次的的评评价价做做好好了了准准备备。该该评评价价是是用用来来为为下下一一次次选选择择过过程程建建立立概概率率分分布布的的，即即建建立立一一个个根根据据当当前前适适应应值值构构造造宽宽距距的的轮轮盘盘。其其它它的的部部分分只只是是上述步骤的循环重复上述步骤的循环重复三、遗传算法的运行步骤：三、遗传算法的运行步骤：7/26/202457华中农业大学理学院1)编码和解码编码和解码7/26/202458华中农业大学理学院2)产生潜在解初始群体产生潜在解初始群体简单地以位的方式随机地设定pop_size个染色体。如果确实有一些关于最优分布的知识，可以使用这些信息来设定初始潜在解的集合。7/26/202459华中农业大学理学院3)3)根据适应值评价解的适应程度并据此生根据适应值评价解的适应程度并据此生成新群体成新群体通常使用一个根据适应值调节刻度宽度的轮盘。按照如下方法构造轮盘（假设这里的适应值时正值，否则可以使用一些比例机制调整）：7/26/202460华中农业大学理学院7/26/202461华中农业大学理学院4)杂杂交交(crossover)和和变变异异(mutation)决定新群体的性状决定新群体的性状7/26/202462华中农业大学理学院随着选择、杂交和变异的进行，新群体就为下一次的评价做好了准备。该评价是用来为下一次选择过程建立概率分布的，即建立一个根据当前适应值构造宽距的轮盘。其它的部分只是上述步骤的循环重复，见图1。7/26/202463华中农业大学理学院例例1：7/26/202464华中农业大学理学院1)解码和解码：解码和解码：变量的定义域长度为15.1，所要求的精度意味 着 区 间 -3.0, 12.1至 少 要 被 分 为15.110000个等距区间。由于，因此染色体的第一部分需要18位。7/26/202465华中农业大学理学院(010001001011010000111110010100010)的前18位010001001011010000表示7/26/202466华中农业大学理学院2)产生潜在解初始群体：产生潜在解初始群体：7/26/202467华中农业大学理学院3)根据适应值评价解的适应程度并据根据适应值评价解的适应程度并据此生成新群体：此生成新群体：7/26/202468华中农业大学理学院3)根据适应值评价解的适应程度并据根据适应值评价解的适应程度并据此生成新群体：此生成新群体：7/26/202469华中农业大学理学院7/26/202470华中农业大学理学院4)杂交杂交(crossover)和变异和变异(mutation)决定新群体的性状：决定新群体的性状：7/26/202471华中农业大学理学院7/26/202472华中农业大学理学院7/26/202473华中农业大学理学院群体的当前版本为：7/26/202474华中农业大学理学院7/26/202475华中农业大学理学院表2.2把染色体中的位号翻译成染色体中的位数：7/26/202476华中农业大学理学院7/26/202477华中农业大学理学院7/26/202478华中农业大学理学院7/26/202479华中农业大学理学院但但是是，仔仔细细检检查查整整个个运运行行过过程程，可可以以发发现现早早期期代代中中的的某某些些染染色色体体的的适适应应值值要要好好于于经经过过1000代代后后的的最最好好染染色色体体值值35.47938。例例如如，第第396代代中中的的最最好好染染色色体体的的值值为为38.827553。这这是是由由于于取取样样的的随随机机误误差差造造成成的的。跟跟踪踪进进化化过过程程中中的的最最好好个个体体是是容容易易的的。在在遗遗传传算算法法的的实实现现中中，通通常常在在一一独独立立出出来来的的位位置置保保存存“曾曾经经最最好好”的的个个体体；用用这这种种方方法法，算算法法将将报报告告整整个个过过程程的的最最好值，而不只是最终群体的最好值。好值，而不只是最终群体的最好值。7/26/202480华中农业大学理学院例2：为四个连锁饭店寻找最好的经营决策，其中一个经营饭店的决为四个连锁饭店寻找最好的经营决策，其中一个经营饭店的决策包括要做出以下三项决定：策包括要做出以下三项决定：（1）价格）价格汉堡包的价格应该定在汉堡包的价格应该定在50美分还是美分还是1美元？美元？（2）饮料）饮料和汉堡包一起供应的应该是酒还是可乐？和汉堡包一起供应的应该是酒还是可乐？（3）服务速度）服务速度饭店应该提供慢的还是快的服务？饭店应该提供慢的还是快的服务？目的：目的：找到这三个决定的组合以产生最高的利润。找到这三个决定的组合以产生最高的利润。上述问题的表示方案：上述问题的表示方案：串长串长( (l3）字母表规模（字母表规模（k2）映射映射共有共有8种表示方案种表示方案遗传算法解这个问题的第一步就是选取一个适当的表示方案。遗传算法解这个问题的第一步就是选取一个适当的表示方案。7/26/202481华中农业大学理学院饭店编号饭店编号价价格格饮饮料料速速度度二进制表示二进制表示1高可乐快0112高酒快0013低可乐慢1104高可乐慢010表表1饭店问题的表示方案（其中的饭店问题的表示方案（其中的4个）个）群体规模N47/26/202482华中农业大学理学院第0代i串xi适应值f（xi）10113200113110640102总和12最小值1平均值3.00最大值6表表2初始群体中经营决策的适应值初始群体中经营决策的适应值一个简单的遗传算法由复制、杂交、变异三个算子组成7/26/202483华中农业大学理学院第0代交配池i串xi适应值适应值f(xi)f（xi）/f（xi）串f(xi)101130.250113200110.081106311060.501106401020.170102总和1217最小值12平均值3.004.25最大值66表表3使用使用复制算子复制算子后产生的交配池后产生的交配池1.复制算子：采用赌盘选择7/26/202484华中农业大学理学院2.杂交算子杂交算子：采用一点杂交：采用一点杂交作用过程：作用过程：a）产生一个在产生一个在1到到l1之间的随机数之间的随机数ib）配对的两个串相互对应的交换从配对的两个串相互对应的交换从i1到到l的位段的位段例例如如：从从交交配配池池中中选选择择编编号号为为1和和2的的串串进进行行配配对对，且且杂杂交交点点选在选在2（用分隔符（用分隔符|表示），杂交算子作用的结果为：表示），杂交算子作用的结果为：01|101011|0111对对交交配配池池中中指指定定百百分分比比的的个个体体应应用用杂杂交交算算子子，假假设设杂杂交交概概率率pc50，交交配配池池中中余余下下的的50个个体体仅仅进进行行复复制制运运算算，即即复复制概率制概率pr50。7/26/202485华中农业大学理学院第0代交配池第1代i串xi适应值f(xi)F(xi)/ f(xi)串f(xi)杂交点xif(xi)101130.25011320102200110.08110621117311060.5011061106401020.1701020102总和121717最小值122平均值3.004.254.25最大值667表表4使用使用复制和杂交算子复制和杂交算子的作用结果的作用结果遗传算法利用复制和杂交算子可以产生具有更高平均适应值和更好个体的群体7/26/202486华中农业大学理学院3.变异算子：以一个很小的概率pm随机改变染色体串上的某些位。对于二进制串，就是将相应位上的0变为1或将1变为0。例如：选交配池中编号为4的串进行变异，且变异点在2，则010000变异算子相对而言，是次要算子，但在恢复群体中失去的多样性方面具有潜在的作用。7/26/202487华中农业大学理学院如图所示：该如图所示：该函数有多个局函数有多个局部极大点。部极大点。7/26/202488华中农业大学理学院构造过程：第一步：确定决策变量及其约束条件。第第三三步步：确确定定编编码码方方法法。用用长长度度为为22位位的的二二进制编码串来分别表示决策变量进制编码串来分别表示决策变量x。7/26/202489华中农业大学理学院22位二进制编码串可以表示从0到4194303之间的4194304个不同的数，故将x的定义域离散化为4194304个均等的区间，包括两个端点在内共有4194304个不同的离散点。从离散点0到离散点9，依次让它们分别对应于从0000000000000000000000(0)到1111111111111111111111(41943043)之间的二进制编码。这就构成了这个函数优化问题的染色体编码方法。例如X：0000000000001101110001就表示一个个体的基因型。7/26/202490华中农业大学理学院第四步：确定解码方法。解码时将22位长的二进制编码转换为对应的十进制整数代码，记为y。依据前述个体编码方法相对定义域的离散化方法可知，将代码y转换为变量x的解码公式为：例如，对前述个体X：00000000001101110001它由这样的下列代码所组成：y=881经上式的解码处理后，得到：x=0.001890421x=7/26/202491华中农业大学理学院第五步：确定个体评价方法。由于目标函数的取值可正可负，并且优化目标是求函数的最大值，故这里可将个体的适应度取为每次迭代的最小值的绝对值加上目标函数值，即有：第六步：设计遗传算子。选择运算使用比例选第六步：设计遗传算子。选择运算使用比例选择算子；交叉运算使用单点交叉算子；变异运择算子；交叉运算使用单点交叉算子；变异运算使用基本位变异算子。算使用基本位变异算子。7/26/202492华中农业大学理学院第七步：确定遗传算法的运行参数。第七步：确定遗传算法的运行参数。对于本例，设定基本遗传算法的运行参数如下：群体大小:N50终止代数:ger100交叉概率：pc0.65变异概率：pm0.057/26/202493华中农业大学理学院7/26/202494华中农业大学理学院7/26/202495华中农业大学理学院由该组图我们可以看出，随着进化过程的进行，群体中适应度较低的一些个体被逐渐淘汰掉，而适应度较高的一些个体会越来越多并且它们都集中在所求问题的最优点附近，从而最终就可搜索到问题的最优解。7/26/202496华中农业大学理学院小结小结遗传算法描述了从第0代产生第1代的过程，然后遗传算法迭代地执行这个过程，直到满足某个停止准则。在每一代中，算法首先计算群体中每个个体地适应值，然后利用适应值信息，遗传算法分别以概率pc、pr和pm执行杂交、复制和变异操作，从而产生新的群体。应用遗传算法求解问题需完成四个主要步骤：1.确定表示方案2.确定适应值度量3.确定控制算法的参数和变量4.确定指定结果的方法和停止运行的准则7/26/202497华中农业大学理学院四、基本遗传算法的构成要素1.染色体编码方法最常用的是二进制编码，对于离散性变量直接编码，对于连续性变量先离散化后再编码2.适应度函数评估函数用来评估一个染色体的优劣的绝对值适应度函数评估一个染色体相对整个群体的优劣的相对值的大小7/26/202498华中农业大学理学院基本遗传算法一般采用下面两种方法之一将目标基本遗传算法一般采用下面两种方法之一将目标函数值函数值f(x)变换为个体的适应度变换为个体的适应度F(x)：7/26/202499华中农业大学理学院其中，Cmax是一个适当地相对比较大的数，它可用下面几种方法求得：预先指定的一个较大的数。进化到当前代为止的最大目标函数值。当前代或最近几代群体中的最大目标函数值。7/26/2024100华中农业大学理学院3.遗传算子复制算子、交叉算子、变异算子7/26/2024101华中农业大学理学院4.基本遗传算法运行参数N：群体大小，即群体中所含个体的数量，一般取20100T：遗传算法的终止进化代数，一般取100500pc：杂交概率，一般取0.40.99pm：变异概率，一般取0.00010.1pr：复制概率7/26/2024102华中农业大学理学院四、基本遗传算法的一般框架算法过程：1.随机产生一个由确定长度的特征串组成的初始群体2.对串群体迭代地执行下面的步（i）和步（ii），直到满足停止准则：（i）计算群体中每个个体的适应值（ii）应用复制、杂交和变异算子产生下一代群体3.把在任一代中出现地最好地个体串指定为遗传算法的执行结果，这个结果可以表示问题的一个解（或近似解）7/26/2024103华中农业大学理学院GEN0产生初始群体是否满足停止准则指定结果结束计算每个个体的适应值i0iN？以概率选择遗传算子GENGEN1选择一个个体 选择两个个体 选择一个个体执行复制ii1执行变异复制到新群体执行杂交插入到新群体将两个子代串插入到新群体ii1是否是否prpcpmGEN当前代数N群体规模7/26/2024104华中农业大学理学院五、遗传算法的数学理论几个相关的定义：几个相关的定义：1、模式是一个相同的构形，它描述的是一个串的子集，这个集合中串之间在某些位上相同。 例如，添加符号例如，添加符号*表示不确定字母，即表示不确定字母，即0或或1，考虑串长为，考虑串长为7的模式的模式H*11*0*，则串则串A0111000是模式是模式H的一个表示，对于基数为的一个表示，对于基数为k的的字母表，每一个串有（字母表，每一个串有（k1）l 个模式。个模式。2、模式的阶出现在模式中确定位置的数目。在二进制中，一个模式的阶就是所有的1或0的数目。例如，模式H*11*0*的阶为33、模式的定义长度模式中第一个确定位置与最后一个确定位置之间的距离例如，模式H*11*0*的定义长度r5237/26/2024105华中农业大学理学院定理1（模式定理）：具有短的定义长度、低阶并且适应值在群体平均适应值以上的模式在遗传算法迭代过程中将按指数增长率被采样。 模式定理揭示了遗传算法为什么有效！定理2（隐并行性）：nsn3,其中ns有效模式数n群体规模 该定理表明，每一代中除了仅对n个串的处理外，遗传算法实际上处理大约O（n3）个模式，从而每代只执行与群体规模成比例的计算量，就可以同时收到并行地对大约O（n3）个模式进行有效处理的目的，并且无须额外的存储。定理3（积木块假设）：低阶、短距、高平均适应值的模式（积木块）在遗传算子的作用下，相互结合，能生成高阶、长距、高平均适应值的模式，可最终生成全局最优解7/26/2024106华中农业大学理学院定理4（收敛性定理）：如果在代的演化过程中，遗传算法保留最好的解，并且算法以杂交和变异作为随机化算子，则对于一个全局优化问题，随着演化代数趋向于无穷，遗传算法将以概率1找到全局最有解遗传算法极限特性的分析表明算法能够对搜索空间进行持续的搜索，因此遗传算法特别适合于在全局优化问题中应用7/26/2024107华中农业大学理学院六、遗传算法的基本实现技术1.编码方法：二进制编码、格雷编码等编码规则：i）应使用能易于产生与所求问题相关的且具有低阶、短定义长度模式的编码方案ii）应使用能使问题得到自然表示或描述的具有最小编码字符集的编码方案2.适应值函数适应值函数必须是正数，出现负数时应进行变换，常用变换方式有三种：线性比例法：g（x）af（x）b(b大于0)指数比例法：g（x）exp(af(x)，(a不等于0)幂指数比例法：g（x）(f(x)a(a为偶数)3.复制算子：赌盘选择、余数随机选择、全局随机选择4.杂交算子：一点杂交、两点杂交、一致杂交5.变异算子7/26/2024108华中农业大学理学院七、遗传算法的特点1.直接对结构对象操作，不存在求导和函数连续性的限定；2.遗传算法不是从单个点，而是从一个点的群体开始搜索；3.具有内在的隐并行性和较好的全局寻优能力；4.采用概率化寻优方法，能自动获取搜索过程中的有关知识并用于指导优化，自适应地调整搜索方向，不需要确定地规则；5.鲁棒性7/26/2024109华中农业大学理学院八、遗传算法的应用1.与模拟退火算法的结合2.利用遗传算法训练已知结构的神经网络，优化网络连接权3.利用遗传算法找出网络的规模、结构和学习参数7/26/2024110华中农业大学理学院遗传算法的困难遗传算法的困难(1).“编码困难编码困难”：“表表达达是是遗遗传传算算法法的的主主要要问问题题。因因为为表表达达方方案案严严重重地地限限制制了系统观察世界的窗口。了系统观察世界的窗口。”(Koza,1990)“我我们们不不能能用用二二进进制制表表达达和和只只由由二二进进制制杂杂交交和和二二进进制制变变异异组成的算子集来处理多数真实世界问题。组成的算子集来处理多数真实世界问题。”(Davis,1989)遗遗传传算算法法传传统统上上使使用用的的二二进进制制编编码码当当用用于于多多维维、高高精精度度数数值问题时会有一些障碍。值问题时会有一些障碍。例例如如，对对于于一一个个有有100个个变变量量、域域区区间间-500,500、精精度度要要求求精精确确到到小小数数点点后后第第6位位的的问问题题，二二进进制制解解向向量量的的长长度度是是3000。这这本本身身会会产产生生一一个个大大约约是是101000的的搜搜索索空空间间。对对这这样样的的问问题题，遗遗传传算算法法执执行行得得很很不不好好。编编码码应应该该具具有有这这样样的的性性质质：在在表表达达空空间间里里相相互互靠靠近近的的两两个个点点也也必必须须在在问问题题空空间间里里靠靠近近，反反之之亦亦然然。而而二二进进制制方方法法并并不不总总是是这这样样。一一个个可可能能的的解解决决途途径径是是采采用用浮浮点点编编码码，目目的的是是使使遗遗传传算算法法更更接接近近问问题题空空间间。通通过过利利用用真真实实空空间间的的一一些些特特征征，这这样样的的移移近近强制算子更与问题的特殊性有关。强制算子更与问题的特殊性有关。7/26/2024111华中农业大学理学院(2).“有限困难有限困难”：遗传算法理论解释了为什么对一个给定的问题表达，能收敛到欲求的最优点。但不幸的是，实际的应用并不总遵循这一理论。主要的原因除了上面的“编码困难”之外，还有“有限困难”，即：理论假定迭代次数是无限的，而实际上有限制；理论上也假定群体规模是无限的，实际上也有限制。这说明遗传算法在某种条件下不能找到最优解：这种失败是由于过早地收敛到局部最优造成的。过早收敛问题是所有优化算法共同的问题。如果收敛发生的太快，包含在群体中的有价值的信息常常会失去。而遗传算法的执行趋向于在找到最优解之前过早地收敛。有一些避免过早收敛的策略，比如：(1) 配对策略(matingstrategy)，又称为近亲预防(incestprevention)；(2)使用均匀杂交(uniformcrossover)；(3).检测群体中的重复串。7/26/2024112华中农业大学理学院Thankyou!7/26/2024113华中农业大学理学院练习1、说说遗传算法的基本思想和算法流程。2、求下面加权有向图中从A到G的最短路：AB1B2C1C2C3C4D1D2D3E1E2E3F1F2G5313687665833384222133355266437/26/2024114华中农业大学理学院1234567891011121314151653136876658333 84222133355266437/26/2024115华中农业大学理学院