人工智能第三章遗传算法、蚁群算法、粒子群算法.ppt

2023/6/13,1,第 三 章遗传算法、蚁群算法与粒子群算法,2023/6/13,2,3.1 遗传算法,2023/6/13,3,生物在自然界中的生存繁衍，显示出了其对自然环境的优异自适应能力。受其启发，人们致力于对生物各种生存特性的机理研究和行为模拟，为人工自适应系统的设计和开发提供了广阔的前景。,遗传算法(Genetic Algorithm，简称GA)就是这种生物行为的计算机模拟中令人瞩目的重要成果。,基于对生物遗传和进化过程的计算机模拟，遗传算法使得各种人工系统具有优良的自适应能力和优化能力。,遗传算法所借鉴的生物学基础就是生物的遗传和进化。,2023/6/13,4,虽然人们还未完全揭开遗传与进化的奥秘，既没有完全掌握其机制，也不完全清楚染色体编码和译码过程的细节，更不完全了解其控制方式，但遗传与进化的以下几个特点却为人们所共识：,(1)生物的所有遗传信息都包含在其染色休中，染色体决定了生物的性状。,(2)染色体是由基因及其有规律的排列所构成的，遗传和进化过程发生在染色体上。,(3)生物的繁殖过程是由其基因的复制过程来完成的：,(4)通过同源染色体之间的交叉或染色体的变异会产生新的物种，使生物呈现新的性状。,(5)对环境适应性好的基因或染色体经常比适应性差的基因或染色体有更多的机会遗传到下一代。,2023/6/13,5,遗传算法是模拟生物在自然环境力的遗传和进化过程而形成的一种自适应全局优化概率搜索算法。,它最早由美国密执安大学的Holland教授提出，起源于60年代对自然和人工自适应系统的研究。,70年代De Jong基于遗传算法的思想在计算机上进行了大量的纯数值函数优化计算实验。,在系列研究工作的基础上，80年代由Goldberg进行归纳总结，形成了遗传算法的基本框架。,2023/6/13,6,一、遗传算法概要,式中，为决策变量，f(X)为目标函数，后两个式子为约束条件，U是基本空间，R是U的一个子集。,对于一个求函数最大值的优化问题(求函数最小值也类同)，般可描述为下述数学规划模型：,满足约束条件的解X称为可行解，集合R表示由所有满足约束条件的解所组成的一个集合，叫做可行解集合。它们之间的关系如图所示。,2023/6/13,7,2023/6/13,8,对于上述最优化问题，目标函数和约束条件种类繁多，有的是线性的，有的是非线性的；有的是连续的，有的是离散的；有的是单峰值的，有的是多峰值的。,随着研究的深入，人们逐渐认识到在很多复杂情况下要想完全精确地求出其最优解既不可能，也不现实，因而求出其近似最优解或满意解是人们的主要着眼点之。,2023/6/13,9,求最优解或近似最优解的方法,(1)枚举法。枚举出可行解集合内的所有可行解，以求出精确最优解。对于连续函数，该方法要求先对其进行离散化处理，这样就有可能产生离散误差而永远达不到最优解。另外，当枚举空间比较大时，该方法的求解效率比较低，有时甚至在目前最先进的计算工具上都无法求解。,(2)启发式算法。寻求一种能产生可行解的启发式规则，以找到一个最优解或近似最优解。该方法的求解效率虽然比较高，但对每个需要求解的问题都必须找出其特有的启发式规则，这个启发式规则无通用性，不适合于其他问题。,2023/6/13,10,(3)搜索算法。寻求一种搜索算法，该算法在可行解集合的一个子集内进行搜索操作，以找到问题的最优解或近似最优解。该方法虽然保证不了一定能够得到问题的最优解，但若适当地利用一些启发知识，就可在近似解的质量和求解效率上达到种较好的平衡。,而遗传算法为解决这类问题提供了一个有效的途径和通用框架，开创了一种新的全局优化搜索算法。,2023/6/13,11,遗传算法中，将n维决策向量 用n个记号Xi(nl，2，n)所组成的符号串X来表示：,把每一个Xi看作一个遗传基因，它的所有可能取值称为等位基因，这样，X就可看做是由n个遗传基因所组成的一个染色体。,般情况下，染色体的长度n是固定的，但对一些问题n也可以是变化的。,根据不同的情况，这里的等位基因可以是一组整数，也可以是某一范围内的实数值，或者是纯粹的一个记号。,最简单的等位基因是由0和l这两个整数组成的。相应的染色体就可表示为一个二进制符号串。,2023/6/13,12,这种编码所形成的排列形式X是个体的基因型，与它对应的x值是个体的表现型。,通常个体的表现型和其基因型是一一对应的，但有时也允许基因型和表现型是多对一的关系。,染色休X也称为个体X。,对于每一个个体X，要按照一定的规则确定出其适应度；个体的适应度与其对应的个体表现型X的目标函数值相关联，X越接近于目标函数的最优点，其适应度越大；反之，其适应度越小。,遗传算法中，决策变量X组成了问题的解空间。对问题最优解的搜索是通过对染色体X的搜索过程来进行的，从而由所有的染色体X就组成了问题的搜索空间。,2023/6/13,13,生物的进化是以集团为主体的。与此相对应，遗传算法的运算对象是由M个个体所组成的集合，称为群体。,与生物一代一代的自然进化过程相类似，遗传算法的运算过程也是一个反复迭代的过程，第t代群体记做P(t)，经过一代遗传和进化后，得到第t+l代群体，它们也是由多个个体组成的集合，记做P(t+1)。,这个群体不断地经过遗传和进化操作，并且每次都按照优胜劣汰的规则将适应度较高的个体更多地遗传到下一代，这样最终在群体中将会得到一个优良的个体X，它所对应的表现型X将达到或接近于问题的最优解X*。,生物的进化过程主要是通过染色体之间的交叉和变异来完成的，遗传算法中最优解的搜索过程也模仿生物的这个进化过程，使用所谓的遗传算子(genetic operators)作用于群体P(t)中，进行下述遗传操作，从而得到新一代群体P(t+1)。,2023/6/13,14,选择(selection)：根据各个个体的适应度，按照一定的规则或方法，从第t代群体P(t)中选择出一些优良的个体遗传到下一代群体P(t+1)中。,交叉(crossover)：将群体P(t)内的各个个体随机搭配成对，对每对个体，以某个概率(称为交叉概率，crossover rate)交换它们之间的部分染色体。,变异(mutation)：对群体P(t)中的每一个个体，以某一概率(称为变异概率，mutation rate)改变某一个或某一些基因座上的基因值为其他的等位基因。,2023/6/13,15,二、遗传算法的运算过程,使用上述三种遗传算子(选择算子、交叉算子、变异算子)的遗传算法的主要运算过程如下所述：,步骤一：初始化。设置进化代数计数器t0；设置最大进化代数T；随机生成M个个体作为初始群体P(0)。,步骤二：个体评价。计算群体P(t)中各个个体的适应度。,步骤三：选择运算。将选择算子作用于群体。,2023/6/13,16,步骤四：交叉运算。将交叉算子作用于群体。,步骤五：变异运算。将变异算于作用于群体。群体P(t)经过选择、交叉、变异运算之后得到下一代群体P(t+1)。,步骤六：终止条件判断。若tT，则：tt+1，转到步骤二。若tT，则以进化过程中所得到的具有最大适应度的个体作为最优解输出，终止计算。,2023/6/13,17,三、遗传算法的特点,(1)遗传算法以决策变量的编码作为运算对象。,传统的优化算法往往直接利用决策变量的实际值本身来进行优化计算，但遗传算法不是直接以决策变量的值，而是以决策变量的某种形式的编码为运算对象。,这种对决策变量的编码处理方式，使得我们在优化计算过程中可以借鉴生物学中染色体和基因等概念，可以模仿自然界中生物的遗传和进化等机理，也使得我们可以方便地应用遗传操作算子。特别是对一些无数值概念或很难有数值概念，而只有代码概念的优化问题，编码处理方式更显示出了其独持的优越性。,2023/6/13,18,(2)遗传算法直接以目标函数值作为搜索信息。,传统的优化算法不仅需要利用目标函数值，而且往往需要目标函数的导数值等其他一些辅助信息才能确定搜索方向。,而遗传算法仅使用由目标函数值变换来的适应度函数值，就可确定进一步的搜索方向和搜索范围，无需目标函数的导数值等其他一些辅助信息。,这个特性对很多目标函数无法或是很难求导数的函数，或导数不存在的函数的优化问题，以及组合优化问题等，应用遗传算法时就显得比较方便，因为它避开了函数求导这个障碍。,再者，直接利用目标函数值或个体适应度，也可使得我们可以把搜索范围集中到适应度较高的部分搜索空间中，从而提高了搜索效率。,2023/6/13,19,(3)遗传算法同时使用多个搜索点的搜索信息。,传统的优化算法往往是从解空间个的一个初始点开始最优解的这代搜索过程，单个搜索点所提供的搜索信息毕竟不多，所以搜索效率不高，有时其至使搜索过程陷入局部最优解而停滞不前。,遗传算法从很多个体所组成的一个初始群体开始最优解的搜索过程，而不是从个单一的个体开始搜索。对这个群体所进行的选择、交叉、变异等运算，产生出的乃是新一代的群体，在这之中包括了很多群体信息。,这些信息可以避免搜索一些不必搜索的点，所以实际上相当于搜索了更多的点，这是遗传算法所特有的一种隐含并行性。,2023/6/13,20,(4)遗传算法使用概率搜索技术。,传统的优化算法往往使用的是确定性的搜索方法，一个搜索点到另一个搜索点的转移有确定的转移方法和转移关系，这种确定性往往也有可能使得搜索永远达不到最优点，因而也限制了算法的应用范围。,遗传算法属于一种自适应概率搜索技术，其选择、交叉、变异等运算都是以一种概率的方式来进行的，从而增加了其搜索过程的灵活性。,虽然这种概率特性也会使群体中产生些适应度不高的个体，但随着进化过程的进行，新的群体中总会更多地产生出许多优良的个体，实践和理论都已证明了在定条件下遗传算法总是以概率1收敛于问题的最优解。,当然，交叉概率和变异概率等参数也会影响算法的搜索效果和搜索效率，所以如何选择遗传算法的参数在其应用中是一个比较重要的问题。而另一方面，与其他一些算法相比遗传算法的鲁棒性又会使得参数对其搜索效果的影响会尽可能地低。,2023/6/13,21,四、遗传算法的发展,遗传算法起源于对生物系统所进行的计算机模拟研究。,早在上世纪40年代，就有学者开始研究如何利用计算机进行生物模拟的技术，他们从生物学的角度进行了生物的进化过程模拟、遗传过程模拟等研究工作。,进入60年代后，美国密执安大学的Ho11and教授及其学生们受到这种生物模拟技术的启发，创造出了一种基于生物遗传和进化机制的适合于复杂系统优化计算的自适应概率优化技术遗传算法。,下面是在遗传算法的发展进程中一些关键人物所做出的一些主要贡献。,2023/6/13,22,1、JHHolland60年代，Ho11and提出在研究和设计人工自适应系统时，可以借鉴生物遗传的机制，以群体的方法进行自适应搜索，并且充分认识到了交叉、变异等运算策略在自适应系统中的重要性。70年代初，Ho11and教授提出了遗传算法的基本定理模式定理(schema Theorem)，从而奠定了遗传算法的理论基础。模式定理揭示出了群体中的优良个体(较好的模式)的样本数将以指数级规律增长，因而从理论上保证了遗传算法是一个可以用来寻求最优可行解的优化过程。1975年，Ho11and出版了第一本系统论述遗传算法和人工自适应系统的专著自然系统和人工系统的自适应性(Adaptation in natural and artificial system)。80年代，Holland教授实现了第一个基于遗传算法的机器学习系统分类器系统(C1assifier system，简称CS)，开创了基于遗传算法的机器学习的新概念，为分类器系统构造出了一个完整的框架。,2023/6/13,23,2、JDBagley1967年，Ho11and的学生Bagley在其博士论文中首次提出“遗传算法”一词，并发表了遗传算法应用方面的第一篇论文。他发展了复制、交叉、变异、显性、倒位等遗传算子，在个体编码上使用了双倍体的编码方法。这些都与目前遗传算法中所使用的算子和方法相类似。他还敏锐地意识到在遗传算法执行的不向阶段可以使用不同的选择率，这将有利于防止遗传算法的早熟现象，从而创立了自适应遗传算法的概念。,2023/6/13,24,3、KADe Jong l975年，De Jong在其博士论文中结合模式定理进行了大量的纯数值函数优化计算实验，树立了遗传算法的工作框架，得到了一些重要且具有指导意义的结论。例如，对于规模在50100的群体，经过l020代的进化，遗传算法都能以很高的概率找到最优或近似最优解。他推荐了在大多数优化问题中都较适用的遗传算法的参数，还建立了著名的De Jong五函数测试平台，定义了评价遗传算法性能的在线指标和离线指标。4、DJDe Jong1989年，De Jong出版了专著搜索、优化和机器学习中的遗传冲法(Genetic Algorithms in Search，Optimization and Machine Learning)。该书系统总结了遗传算法的主要研究成果，全面而完整地论述了遗传算法的基本原理及其应用。可以说这本书奠定了现代遗传算法的科学基础，为众多研究和发展遗传算法的学者所瞩目。,2023/6/13,25,5、LDavis1991年，Davis编辑出版了遗传算法手册(Handbook of Genetic Algorithms)书，书中包括了遗传算法在科学计算、工程技术和社会经济中的大量应用实例。这本书为推广和普及遗传算法的应用起到了重要的指导作用。6JRKoza1992年，Koza将遗传算法应用于计算机程序的优化设计及自动生成，提出了遗传编程(Genetic Programming，简称GP)的概念。他将一段LISP语言程序作为个体的基因型，把问题的解编码作为一棵树，基于遗传和进化的概念，对由树组成的群体进行遗传运算，最终自动生成性能较好的计算机程序。Koza成功地把他提出的遗传编程的方法应用于人工智能、机器学习、符号处理等方面。,2023/6/13,26,五、遗传算法的应用,(1)函数优化。,函数优化是遗传算法的经典应用领域，也是对遗传算法进行性能评价的常用算例。,很多人构造出了各种各样的复杂形式的测试函数，有连续函数也有离散函数，有凸函数也有凹函数，有低维函数也有高维函数，有确定函数也有随机函数，有单峰值函数也有多峰值函数等。,用这些几何特性各具特色的函数来评价遗传算法的性能，更能反映算法的本质效果。,而对于一些非线性、多模型、多目标的函数优化问题，用其他优化方法较难求解，而遗传算法却可以方便地得到较好的结果。,2023/6/13,27,(2)组合优化。,随着问题规模的增大，组合优化问题的搜索空间也急剧扩大，有时在目前的计算机上用枚举法很难或甚至不可能求出其精确最优解。对这类复杂问题，人们已意识到应把主要精力放在寻求其满意解上，而遗传算法是寻求这种满意解的最佳工具之一。,实践证明，遗传算法对于组合优化中的NP完全问题非常有效。,例如，遗传算法已经在求解旅行商问题、背包问题、装箱问题、图形划分问题等方面得到成功的应用。,2023/6/13,28,(3)生产调度问题。,生产调度问题在很多情况下所建立起来的数学模型难以精确求解，即使经过一些简化之后可以进行求解，也会因简化得太多而使得求解结果与实际相差甚远。目前在现实生产中也主要是靠一些经验来进行调度。,现在遗传算法已成为解决复杂调度问题的有效工具，在单件生产车间调度、流水线生产车间调度、生产规划、任务分配等方面遗传算法都得到了有效的应用。,2023/6/13,29,(4)自动控制。,在自动控制领域中有很多与优化相关的问题需要求解，遗传算法已在其中得到了初步的应用，并显示出了良好的效果。,例如用遗传算法进行航空控制系统的优化、使用遗传算法设计空间交会控制器、基于遗传算法的模糊控制器的优化设计、基于遗传算法的参数辨识、基于遗传算法的模糊控制规则的学习、利用遗传算法进行人工种经网络的结构优化设计和权值学习等，都显示出了遗传算法在这些领域中应用的可能性。,2023/6/13,30,(5)机器人学。,机器人是一类复杂的难以精确建模的人工系统，而遗传算法的起源就来自于对人工自适应系统的研究，所以机器人学理所当然地成为遗传算法的一个重要应用领域。,例如，遗传算法已经在移动机器人路径规划、关节机器人运动轨迹规划、机器人逆运动学求解、细胞机器人的结构优化和行为协调等方面得到研究和应用。,2023/6/13,31,(6)图像处理。,图像处理是计算机视觉中的一个重要研究领域。在图像处理过程中，如扫描、持征提取、图像分割等不可避免地会存在一些误差，这些误差会影响图像处理的效果。如何使这些误差最小是使机器视觉达到实用化的重要要求。,遗传算法在这些图像处理中的优化计算方面找到了用武之地。目前已在模式识别、图像恢复、图像边缘特征提取等方面得到了应用。,2023/6/13,32,人工生命与遗传算法有着密切的关系，基于遗传算法的进化模型是研究人工生命现象的重要基础理论。虽然人工生命的研究尚处于启蒙阶段，但遗传算法已在其进化模型、学习模型、行为模型、自组织模型等方面显示出了初步的应用能力，并且必将得到更为深入的应用和发展。人工生命与遗传算法相辅相成，遗传算法为人工生命的研究提供了一个有效的工具，人工生命的研究也必将促进遗传算法的进一步发展。,(7)人工生命。,人工生命是用计算机、机械等人工媒体模拟或构造出的具有自然生物系统特有行为的人造系统。自织织能力和自学习能力是人工生命的两大主要特征。,2023/6/13,33,(8)遗传编程。,Koza发展了遗传编程的概念，他使用了以LISP语言所表示的编码方法，基于对一种树型结构所进行的遗传操作来自动生成计算机程序。虽然遗传编程的理论尚未成熟，应用也有一些限制，但它已成功地应用于人工智能、机器学习等领域。,2023/6/13,34,(9)机器学习。,学习能力是高级自适应系统所应具备的能力之一。基于遗传算法的机器学习，特别是分类器系统，在很多领域中都得到了应用。,例如，遗传算法被用于学习模糊控制规则，利用遗传算法来学习隶属度函数，从而更好地改进了模糊系统的性能；,基于遗传算法的机器学习可用来调整人工神经网络的连接权，也可用于人工神经网络的网络结构优化设计；,分类器系统也在学习式多机器人路径规划系统中得到了成功的应用。,2023/6/13,35,3.2 基本遗传算法,2023/6/13,36,一、基本遗传算法的构成要素,基于对自然界中生物遗传与进化机理的模仿，针对不向的问题，很多学者设计了许多不同的编码方法来表示问题的可行解，开发出了许多种不同的遗传算子来模仿不同环境下的生物遗传特。这样，由不同的编码方法和不同的遗传算子就构成了各种不同的遗传算法。,但这些遗传算法都有共同的特点，即通过对生物遗传和进化过程中选择、交叉、变异机理的模仿，来完成对问题最优解的自适应搜索过程。,2023/6/13,37,基于这个共同特点，Goldberg总结出了一种统一的最基本的遗传算法基本遗传算法(Simple Genetic Algorithms，简称SGA)。,基本遗传算法只使用选择算子、交叉算子和变异算子这三种基本遗传算子，其遗传进化操作过程简单，容易理解，是其他一些遗传算法的雏形和基础，它不仅给各种遗传算法提供了一个基本框架，同时也具有一定的应用价值。,2023/6/13,38,1、染色体编码方法,基本遗传算法使用固定长度的二进制符号串来表示群体中的个体，其等位基因是由二值符号集0，1所组成的。初始群体中各个个体的基因值可用均匀分布的随机数来生成，如：,X,就可表示一个个体，该个体的染色体长度是n18。,2023/6/13,39,2、个体适应度评价,基本遗传算法按与个体适应度成正比的概率来决定当前群体中每个个体遗传到下一代群体中的机会多少。,为正确计算这个概率，这里要求所有个体的适应度必须为正数或零。,这样，根据不同种类的问题，必须预先确定好由目标函数值到个体适应度之间的转换规则，特别是要领先确定好当目标函数值为负数时的处理方法。,2023/6/13,40,3、遗传算子,选择运算使用比例选则算子；,交叉运算使用单点交叉算子；,变异运算使用基本位变异算子或均匀变异算子。,2023/6/13,41,4、基本遗传算法的运行参数,基本遗传算法有下述4个运行参数需要提前设定：,M：群体大小，即群体中所含个体的数量，一般取为201000,T：遗传运算的终止进化代数，一般取为100500,Pc：交叉概率，般取为0.40.99。,Pm：变异概率，一般取为0.00010.1,这4个运行参数对遗传算法的求解结果和求解效率都有一定的影响，但目前尚无合理选择它们的理论依据。,2023/6/13,42,在遗传算法的实际应用中，往往需要经过多次试算后才能确定出这些参数合理的取值大小或取值范围。,一般来说，选择较大数目的初始种群可以同时处理更多的解，因而容易找到全局的最优解，其缺点使增加了每次迭代所需要的时间。,交叉概率的选择决定了交叉操作的频率。频率越高，可以越快收敛到最有希望的最优解区域；但是太高的频率也可能导致收敛于一个解。,变异概率通常只取较小的数值。若选取高的变异率，一方面可以增加样本的多样性，另一方面可能引起不稳定。但是若选取太小的变异概率，则可能难于找到全局的最优解。,2023/6/13,43,Procedure SGAbegininitialize P(0);t=0;while(tT)dofor i=1 to M doEvaluate fitness of P(t);end for,二、基本遗传算法的伪代码描述,2023/6/13,44,for i=1 to M doSelect operation of P(t);end forfor i=1 to M/2 doCrossover operation of P(t);end forfor i=1 to M doMutation operation of P(t);end for,2023/6/13,45,for i=1 to M doP(t+1)=P(t);end fort=t+1;end whileend,2023/6/13,46,三、基本遗传算法的实现,1、个体适应度评价,在遗传算法中，以个体适应度的大小来确定该个体被遗传到下一代群体中的概率。个体的适应度越大，该个体被遗传到下一代的概率也越大；反之，个体的适应度越小，该个体被遗传到下一代的概率也越小。,基本遗传算法使用比例选择算子来确定群体中各个个体遗传到下一代群体中的数量。,为正确计算不同情况下各个个体的遗传概率，要求所有个体的适应度必须为正数或零，不能是负数。,2023/6/13,47,对于求目标函数最小值的优化问题，理论上只需简单地对其增加一个负号就可将其转化为求目标函数最大值的优化问题，即：minf(X)max(f(X),当优化目标是求函数最大值，并且目标函数总取正值时，可以直接设定个体的适应度F(x)就等于相应的目标函数值f(X)，即：F(X)f(X),但实际优化问题中的目标函数值有正也有负，优化目标有求函数最大值，也有求函数最小值。,上面两式保证不了所有情况下个体的适应度都是非负数这个要求。所以必须寻求出一种通用且有效的由目标函数值到个体适应度之间的转换关系，由它来保证个体适应度总取非负值。,2023/6/13,48,为满足适应度取非负值的要求，基本遗传算法一般采用下面两种方法之一将目标函数值f(X)变换为个体的适应度F(x)。,式中，Cmin为一个适当地相对比较小的数，它可以用下面几种方法之一来选择：,方法一：对于求目标函数最大值的优化问题，变换方法为：,预先指定的一个较小的数。,进化到当前代为止的最小目标函数值。,当前代或最近几代群体中的最小目标函数值。,2023/6/13,49,方法二：对于求目标函数最小值的优化问题，变换方法为：,式中，Cmax为一个适当地相对比较大的数，它可以用下面几种方法之一来选择：,预先指定的个较大的数。,进化到当前代为止的最大目标函数值。,前代或最近几代群体中的最大目标函数值。,2023/6/13,50,2、比例选择算子,选择算子或复制算子的作用是从当前代群体中选择出一些比较优良的个体，并将其复制到下一代群体中。最常用和最基本的选择算子是比例选择算子。,比例选择实际上是一种有退还随机选择，也叫做赌盘(Roulette wheel)选择，因为这种选择方式与赌博中的赌盘操作原理颇为相似。,所谓比例选择算了，是指个体被选中并遗传到下一代群体中的概率与该个体的适应度大小成正比。,2023/6/13,51,如图所示为一赌盘示意图。,整个赌盘被分为大小不同的一些扇面，分别对应着价值各不相同的一些赌博物品。当旋转着的赌盘自然停下来时，其指针所指扇面上的物品就归赌博者所有。,虽然赌盘的指针具体停止在哪一个扇面是无法预测的，但指针指向各个扇面的概率却是可以估计的，它与各个扇面的圆心角大小成正比：圆心角越大，停在该扇面的可能性也越大；圆心角越小，停在该扇面的可能性也越小。,与此类似，在遗传算法中，整个群体被各个个体所分割，各个个体的适应度在全部个体的适应度之和中所占比例也大小不一，这个比例值瓜分了整个赌盘盘面，它们也决定了各个个体被遗传到下一代群体中的概率。,2023/6/13,52,2023/6/13,53,比例选择算子的具体执行过程是：,(1)先计算出群体中所有个体的适应度的总和。,(2)其次计算出每个个体的相对适应度的大小，它即为各个个体被遗传到下一代群体中的概率。,(3)最后再使用模拟赌盘操作(即0到1之间的随机数)来确定各个个体被选中的次数。,2023/6/13,54,3、单点交叉算子,单点交叉算子是最常用和最基本的交叉操作算子。,算子的具体执行过程如下：,(1)对群体中的个体进行两两随机配对。若群体的大小为M，则共有M/2对相互配对的个体组。其中x表示不大于x的最大整数。,(2)对每一对相互配对的个体，随机设置某一基因座之后的位置为交叉点。若染色体的长度为n，则共有(n-1)个可能的交叉点位置。,(3)对每一对相互配对的个体，依设定的交叉概率pc在其交叉点处相互交换两个个体的部分染色体，从而产生出两个新的个体。,2023/6/13,55,单点交叉示意如下所示：,2023/6/13,56,4、基本位变异算子,对于基本遗传算法中用二进制编码符号串所表示的个体，若需要进行变异操作的某一基因座上的原有基因值为0，则变异操作将该基因值变为1；反之，若原有基因值为l，则变异操作将其变为0。,(1)对个体的每一个基因座，依变异概率pm指定其为变异点。,(2)对每一个指定的变异点，对其基因值做取反运算或用其它等位基因值来代替，从而产生出一个新的个体。,2023/6/13,57,四、基本遗传算法应用举例,1、遗传算法的应用步骤,第一步：确定决策变量及其各种约束条件，即确定出个体的表现型X和问题的解空间。,第二步：建立优化模型，即确定出目标函数的类型(是求目标函数的最大值还是求目标函数的最小值)及其数学描述形式或量化方法。,第三步：确定表示可行解的染色体编码方法，也即确定出个体的基因型X及遗传算法的搜索空间。,第四步：确定解码方法，即确定出由个体基因型X到个体表现型X的对应关系或转换方法。,2023/6/13,58,若参数a的变化范围为amin，amax，用m位二进制数b来表示，则二者之间满足：,第五步：确定个体适应度的量化评价方法，即确定出由目标函数值f(X)到个体适应度F(X)的转换规则。,第六步：设计遗传算子，即确定出选择运算、交叉运算、变异运算等遗传算子的具体操作方法。,第七步：确定遗传算法的有关运行参数，即确定出遗传算法的M、T、pc、pm等参数。,2023/6/13,59,2、遗传算法的手工模拟计算示例,例：求下述二元函数的最大值：,2023/6/13,60,(1)个体编码,遗传算法的运算对象是表示个体的符号串，所以必须把变量xl、x2编码为一种符号串。,该例题中，xl和x2取07之间的整数，可分别用3位无符号二进制整数来表示，将它们连接在一起所组成的6位无符号二进制整数就形成了个体的基因型，表示一个可行解。,例如，基因型X=10l110所对应的表现型是：X5，6T。,个体的表现型和基因型之间可通过编码和解码程序相互转换。,2023/6/13,61,(2)初始群体的产生,遗传算法是对群体进行的进化操作，需要给其准备一些表示起始搜索点的初姑群体数据。,本例中，群体规模的大小取为4，即群体由4个个体组成，每个个体可通过随机方法产生。,一个随机产生的初始群体如表中第1栏所示。,2023/6/13,62,(3)适应度计算,遗传算法中以个体适应度的大小来评定各个个体的优劣程度，从而决定其遗传机会的大小。,本例中，目标函数总取非负值，并且是以求函数最大值为优化目标，故可直接利用目标函数值作为个体的适应度。,为计算函数的目标值，需先对个体基因型X进行解码。,表中第2、3栏所示为初始群体中各个个体的解码结果，第4栏所示为各个个体所对应的目标函数值，它也是个体的适应度，第4栏中还给出了群体中适应度的最大值和平均值。,2023/6/13,63,2023/6/13,64,(4)选择运算,选择运算(或称为复制运算)把当前群体中适应度较高的个体按某种规则或模型遗传到下代群体中。一般要求适应度较高的个体将有更多的机会遗传到下一代群体中。,本例中，采用与适应度成正比的概率来确定各个个体复制到下一代群体中的数量。其具体操作过程是：,先计算出群体中所有个体的适应度的总和；,其次计算出每个个体的相对适应度的大小，如表中第5栏所示，它即为每个个体被遗传到下一代群体中的概率，每个概率值组成一个区域，全部概率值之代为l。,最后产生一个0到1之间的随机数，依据该随机数出现在上述哪一个概率区域内来确定各个个体被选中的次数。如表中第6、7栏所示为一随机产生的选样结果。,2023/6/13,65,2023/6/13,66,(5)交叉运算,交叉运算是遗传算法中产生新个体的主要操作过程，它以某一概率相互交换某两个个体之间的部分染色体。,本例采用单点交叉的方法，其具体操作过程是：,先对群体进行随机配对，表中第8栏所示为一种随机配对情况；,其次随机设置交叉点位置，如表第9栏所示为一随机产生的交叉点位置，其中的数字表示交叉点设置在该基因座之后；,最后再相互交换配对染色体之间的部分基因。表中第10栏所示为交叉运算的结果。,2023/6/13,67,2023/6/13,68,可以看出，其中新产生的个体“111011”的适应度较原来两个个体的适应度都要高。,2023/6/13,69,(6)变异运算,变异运算是对个体的某一个或某一些基因座上的基因值按某一较小的概率进行改变，它也是产生新个体的一种操作方法。,本例中，我们采用基本位变异的方法来进行变异运算，其具体操作过程是：,首先确定出各个个体的基因变异位置，如表中第11栏所示为随机产生的变异点位置，其中的数字表示变异点设置在该基因座处；,然后依照某概率将变异点的原有基因值取反。表中第12栏所示为变异运算结果。,2023/6/13,70,例如，若第3号个体的第2个基因座需要进行变异运算，则可产生出个新的个体：,第3号个体：1 0 1 0 0 1,1 1 1 0 0 1,第二位变异,对群体P(t)进行轮选择、交叉、变异运算之后可得到新一代的群体P(t+1)。如表第13栏所示。,表中第14、15、16、17栏还分别表示出了新群体的解码值、适应度和相对适应度，并给出了适应度的最大值和平均值等。,从表中可以看出，群体经过一代进化之后，其适应度的最大值、平均值都得到了明显的改进。事实上，这里已经找到了最佳个体“111111”。,2023/6/13,71,需要说明的是，表中第1、6、8、9、11栏的数据是随机产生的。这里为了更好地说明问题，特意选择了一些较好的数值以便能够得到较好的结果。,在实际运算过程中有可能需要一定的循环次数才能达到这个最优结果。,2023/6/13,72,3、基本遗传算法在函数优化中的应用,该函数有两个局部极大值，分别是f(2.048,-2.048)=3905.7324和f(-2.048,-2.048)=3905.9262，其中后者为全局最大值。,下面介绍求解该问题的遗传算法的构造过程。,第一步：确定决策变量和约束条件。,第二步：建立优化模型。,例：Rosenbrock函数的全局最大值计算。,2023/6/13,73,用长度为l0位的二进制编码串来分别表示二个决策变量x1，x2。,10位二进制编码串可以表示从0到1023之间的1024个不同的数，故将x1，x2的定义域离散化为1023个均等的区域，包括两个端点在内共有1024个不同的离散点。,第三步：确定编码方法。,从离散点2.048到离散点2.048，依次让它们分别对应于从0000000000(0)到1111111111(1023)之间的二进制编码。,再将分别表示x1，x2的二个10位长的二进制编码串连接在一起，组成一个20位长的二进制编码串，它就构成了这个函数优化问题的染色体编码方法。,使用这种编码方法解空间和遗传算法的搜索空间具有一一对应的关系。,例如X：000011011l 1101110001就表示一个个体的基因型，其中前l0位表示x1，后10为表示x2。,2023/6/13,74,第四步：确定解码方法。解码时需先将20位长的二进制编码串切断为二个10位长的二进制编码串，然后分别将它们转换为对应的十进制整数代码，分别记为y1和y2。,例如，对于前述个体 X：000011011l 1101110001它由这样的两个代码所组成：y155 y2881经解码处理后，可得到：x1=1.828 x2=1.476,依据前述个体编码方法和对定义域的离散化方法可知，将代码yi转换为变量xi的解码公式为：,2023/6/13,75,第五步：确定个体评价方法。,第六步：设计遗传算子。,可知，Rosenbrock函数的值域总是非负的，并且优化目标是求函数的最大值，故这里可将个体的适应度直接取为对应的目标函数值，即有：F(X)=f(x1，x2),选择运算使用比例选择算子；,交叉运算使用单点交叉算子；,变异运算使用基本位变异算子。,2023/6/13,76,第七步：确定遗传算法的运行参数。,对于本例，设定基本遗传算法的运行参数如下：,群体大小：M80,终止代数：T200,交叉概率：pc0.6,变异概率：pm0.001,通过上述七个步骤就可构成用于Rosenbrock函数优化计算的基本遗传算法。,2023/6/13,77,1、自适应变异,如果双亲的基因非常相近，所产生的后代相对于双亲也必然比较接近。这样所期待的性能改善也必然较小。类似于“近亲繁殖”。,所以基因模式的单一性不仅减慢进化历程，而且可能导致进化停滞，过早地收敛于局部的极值解。,Darrel Wnitly提出了一种如下的自适应变异的方法：在交叉前，以海明(Hamming)距离测定双亲基因码的差异，根据测定值决定后代的变异概率pm。,若双亲的差异较小，则选取较大的变异概率。,当群体中的个体过于趋于一致时，通过变异的增加来提高群体的多样性，即增强了算法维持全局搜索的能力；反之，当群体已具备较强的多样性时，减小变异率，从而不破坏优良的个体。,五、遗传算法的改进,2023/6/13,78,2、部分替代法,设PG为上一代进化到下一代时被替换的个体的比例，则按此比例，部分个体被新的个体所取代，而其他部分的个体则直接进入下一代。,PG越大，进化得越快，但算法的稳定性和收敛性将受到影响；而PG越小，算法的稳定性越好，但进化速度将变慢。可见，应该寻求运行速度与稳定性、收敛性之间的谐调平衡。,2023/6/13,79,3、优秀个体保护法,这种方法对于每代中一定数量的最优个体，使之直接进入下一代。,这样可以防止优秀个体由于复制、交叉或变异中的偶然因素而被破坏掉。,这是增强算法稳定性和收敛性的有效方法。,但同时也可能使遗传算法陷入局部的极值范围。,2023/6/13,80,4、分布式遗传算法,该方法将一个总的群体分为若干个子群，各子群将具有略微不同的基因模式