遗传ga算法课件.ppt

关于遗传GA算法现在学习的是第1页，共54页遗传算法起源 遗传算法是由美国的J.Holland教授于1975年在他的专著自然界和人工系统的适应性中首先提出的，它是一类借鉴生物界自然选择和自然遗传机制的随机化搜索算法。遗传算法介绍现在学习的是第2页，共54页1、智能优化算法 智能优化算法又称为现代启发式算法，是一种具有全局优化性能、通用性强、且适合于并行处理的算法。这种算法一般具有严密的理论依据，而不是单纯凭借专家经验，理论上可以在一定的时间内找到最优解或近似最优解。遗传算法介绍现在学习的是第3页，共54页常用的智能优化算法（1）遗传算法（GeneticAlgorithm，简称GA）（2）模拟退火算法（SimulatedAnnealing，简称SA）（3）禁忌搜索算法（TabuSearch，简称TS）遗传算法介绍现在学习的是第4页，共54页传统的优化方法（局部优化）（1）共轭梯度法（ConjugateGradient，简称CG）（2）拟牛顿法（Quasi-Newton，简称QN）（3）单纯形方法（SimplexMethod）遗传算法介绍现在学习的是第5页，共54页遗传算法介绍比较：传统的优化方法 1）依赖于初始条件。2）与求解空间有紧密关系，促使较快地收敛到局部 解，但同时对解域有约束，如可微或连续。利用这些约束，收敛快。3）有些方法，如Davison-Fletcher-Powell直接依赖于至少一阶导数；共轭梯度法隐含地依赖于梯度。现在学习的是第6页，共54页全局优化方法1）不依赖于初始条件；2）不与求解空间有紧密关系，对解域，无可微或连续的要求。求 解稳健，但收敛速度慢。能获得全局最优。适合于求解空间不知的情况遗传算法介绍现在学习的是第7页，共54页选择运算交换操作变异遗传算法的基本运算遗传算法原理模拟自然界优胜劣汰的进化现象，把搜索空间映射为遗传空间，把可能的解编码成一个向量染色体，向量的每个元素称为基因。通过不断计算各染色体的适应值，选择最好的染色体，获得最优解。现在学习的是第8页，共54页选择运算从旧的种群中选择适应度高的染色体，放入匹配集（缓冲区），为以后染色体交换、变异，产生新的染色体作准备。选择方法适应度比例法（转轮法）按各染色体适应度大小比例来决定其被选择数目的多少。某染色体被选的概率：Pcxi 为种群中第i个染色体，现在学习的是第9页，共54页具体步骤1）计算各染色体适应度值2）累计所有染色体适应度值，记录中间累加值S-mid和最后累加值sum=f(xi)3）产生一个随机数N，0 N sum4）选择对应中间累加值S-mid的第一个染色体进入交换集5）重复（3）和（4），直到获得足够的染色体。举例：具有6个染色体的二进制编码、适应度值、Pc累计值。现在学习的是第10页，共54页染色体的适应度和所占的比例用转轮方法进行选择现在学习的是第11页，共54页染色体编号12345678910适应度8217721211737被选概率0.10.020.22 0.09 0.02 0.16 0.14 0.09 0.03 0.09适应度累计8102734364859666976随机数2349761312757所选染色体号码37103137染色体被选的概率被选的染色体个数例2、10个染色体种群按比例的选择过程现在学习的是第12页，共54页交换操作方法:随机选择二个染色体(双亲染色体),随机指定一点或多点,进行交换,可得二个新的染色体(子辈染色体).新的子辈染色体:A11010001B01011110模拟生物在自然界环境变化,引起基因的突变.在染色体二进制编码中,1变成0;或0变成1.突变产生染色体的多样性,避免进化中早期成熟,陷入局部极值点,突变的概率很低.变异复制不能创新,交换解决染色体的创新现在学习的是第13页，共54页GA的流程现在学习的是第14页，共54页简单遗传算法（GA）的基本参数种群规模P:参与进化的染色体总数.代沟G:二代之间不相同的染色体数目,无重叠G=1;有重叠0G1选择方法:转轮法,精英选择法,竞争法.交换率:Pc 一般为60100%.变异率:Pm 一般为0.110%举例:变异概率取0.001现在学习的是第15页，共54页初始种群和它的适应度值染色体的交换操纵现在学习的是第16页，共54页举例：函数图现在学习的是第17页，共54页步骤1）编码：确定二进制的位数；组成个体（染色体）步骤2）选择种群数P 和初始个体，计算适应度值，P=50；步骤3）确定选择方法；交换率PC；变异率Pm。选择方法用竞争法；PC =0.25,Pm=0.01现在学习的是第18页，共54页现在学习的是第19页，共54页遗传算法数学基础（1）模式定理（2）积木块假设 现在学习的是第20页，共54页模式模式是指种群个体基因串中的相似样板，它用来描述基因串中某些特征位相同的结构。在二进制编码中，模式是基于三个字符集(0,1,*)的字符串，符号*代表任意字符，即0或者1。模式示例：10*1现在学习的是第21页，共54页两个定义定义1：模式H中确定位置的个数称为模式H的阶，记作O(H)。定义2：模式H中第一个确定位置和最后一个确定位置之间的距离称为模式H的定义距，记作(H)。现在学习的是第22页，共54页模式的描述：现在学习的是第23页，共54页模式的阶和定义距的含义模式阶用来反映不同模式间确定性的差异，模式阶数越高，模式的确定性就越高，所匹配的样本数就越少。在遗传操作中，即使阶数相同的模式，也会有不同的性质，而模式的定义距就反映了这种性质的差异。现在学习的是第24页，共54页模式定理模式定理保证了较优的模式（遗传算法的较优解）的数目呈指数增长，为解释遗传算法机理提供了数学基础。模式定理：在选择、交换、变异的作用下，阶次低、定义长度短、适应度高的图式（模块）将按指数增长的规律，一代一代地增长。现在学习的是第25页，共54页模式定理的推导模式式在选择过程中的增加.现在学习的是第26页，共54页经过选择，在t+1代，模式H的数量m(H,t+1)为:现在学习的是第27页，共54页模式在交换中的破坏模式在变异中的破坏经过选择、交换、变异后在t+1中，模式H的数量：现在学习的是第28页，共54页模式定理从模式定理可看出，有高平均适应度、短定义距、低阶的模式，在连续的后代里获得至少以指数增长的串数目，这主要是因为选择使最好的模式有更多的复制，交叉算子不容易破坏高频率出现的、短定义长的模式，而一般突变概率又相当小，因而它对这些重要的模式几乎没有影响。现在学习的是第29页，共54页积木块假设积木块假设：遗传算法通过短定义距、低阶以及高平均适应度的模式（积木块），在遗传操作下相互结合，最终接近全局最优解。模式定理保证了较优模式的样本数呈指数增长，从而使遗传算法找到全局最优解的可能性存在；而积木块假设则指出了在遗传算子的作用下，能生成全局最优解。现在学习的是第30页，共54页2、遗传算法的收敛性分析遗传算法要实现全局收敛，首先要求任意初始种群经有限步都能到达全局最优解，其次算法必须由保优操作来防止最优解的遗失。与算法收敛性有关的因素主要包括种群规模、选择操作、交叉概率和变异概率。现在学习的是第31页，共54页种群规模对收敛性的影响通常，种群太小则不能提供足够的采样点，以致算法性能很差；种群太大，尽管可以增加优化信息，阻止早熟收敛的发生，但无疑会增加计算量，造成收敛时间太长，表现为收敛速度缓慢。现在学习的是第32页，共54页选择操作对收敛性的影响选择操作使高适应度个体能够以更大的概率生存，从而提高了遗传算法的全局收敛性。如果在算法中采用最优保存策略，即将父代群体中最佳个体保留下来，不参加交叉和变异操作，使之直接进入下一代，最终可使遗传算法以概率1收敛于全局最优解。现在学习的是第33页，共54页交叉概率对收敛性的影响交叉操作用于个体对，产生新的个体，实质上是在解空间中进行有效搜索。交叉概率太大时，种群中个体更新很快，会造成高适应度值的个体很快被破坏掉；概率太小时，交叉操作很少进行，从而会使搜索停滞不前，造成算法的不收敛。现在学习的是第34页，共54页变异概率对收敛性的影响变异操作是对种群模式的扰动，有利于增加种群的多样性。但是，变异概率太小则很难产生新模式，变异概率太大则会使遗传算法成为随机搜索算法。现在学习的是第35页，共54页Schaffer建议的最优参数范围是：Population=20-100，Generation=100-500，Pc=0.4-0.9，Pm=0.001-0.01。现在学习的是第36页，共54页遗传算法的应用（1）优化A、函数优化B、组合优化：确定与问题相关的某些项的排列（如资源约束的项目调度问题、车辆路径和调度问题等）确定某些项的组合（如集覆盖问题和群体问题等）确定某些项的排列和组合（如并行机器调度问题等）任何带有约束的上述类型现在学习的是第37页，共54页遗传算法的应用1、总体方案设计方面机械现代设计目标要求为功能-质量-成本的系统化，它包括方案选择、材料选择、结构优化、工艺规划、可靠性分析及成本分析等众多因素与综合知识，将遗传算法与CAD技术结合解决系统的优化问题。2、系列化标准件选取方面应用遗传算法的组合优化来解决机械系统中多种系列化标准的组合选取问题。通常主要靠经验的选取，用这类组合优化来解决，使组合系列化，选取更科学化。现在学习的是第38页，共54页遗传算法的应用3、反求工程方面若要建立原设计产品的数学模型,因一些设计参数和工艺参数往往不易确定,可用遗传算法和计算机仿真技术,把这些参数作为参变量进行编码,在使原设计产品的性能和数学模型的仿真性能之间差异最小的目标下,获得最符合原设计的设计与工艺参数。与此同时,利用遗传算法的优化设计将所建立的原设计的数学模型改进,从而改进原产品设计。4、可靠性分析方面为了使机械系统获得最高可靠性,可以用遗传算法进行系统可靠度分配；在机械维修期望损失最小的前提下，用遗传算法确定机械系统最优维修策略；在原始统计数据基础上,把失效分布模型及其参数作为参变量进行编码，可用遗传算法建立更符合实际的失效分布模型。现在学习的是第39页，共54页遗传算法的应用5、节能设计方面对于汽车、机床等设备的电机类型、电气控制参数、机械传动方案与参数等,以这些参数为参变量编码，把能耗降低到最小目标，在满足功能要求的约束下,利用遗传优化算法进行节能设计,使设备达到最佳效果。6、FMS(柔性制造系统)调度方面使待加工的零件在FMS系统的制造时间最短，将该零件加工次序进行编码，用遗传优化运算实现最短时间加工；针对一个需多工序加工的零件，为确定每道工序所合理分配设备,对每道工序分配设备号编码,在各台设备的负荷可能相等的前提下,用遗传算法实现机床设备的最优分配。现在学习的是第40页，共54页遗传算法的应用7、数控加工误差自适应预报控制方面在获得误差实时检测(或序后测量)数据后,对误差模型结构和参数进行编码，用遗传算法建立最优的误差模型。再根据误差预报的误差修改数控加工次程序,实现加工误差和自适应控制。现在学习的是第41页，共54页遗传算法的应用实例实例1、用衬垫密封的压力容器同盖之间的联接属于紧固螺栓联接现在学习的是第42页，共54页遗传算法的应用实例已知：E和H、D0和p。选择螺栓的直径和个数，使成本更低适应度函数：现在学习的是第43页，共54页遗传算法的应用实例迭代到第30代时最优解为D=17，N=6，参照35号钢。采用正火处理的螺栓许用载荷取整为D=18，N=6。达到设计要求。现在学习的是第44页，共54页遗传算法的应用对大规模控制系统进行综合设计并建立数学模型，在对数学模型的优化上，遗传算法具有其它进化算法无法比拟的优点，已取得一定成绩。例如用遗传算法对自动控制系统数学模型寻优、用遗传算法优化PID控制系统、遗传算法在加工过程智能最优自适应控制的应用、基于遗传算法的模糊控制器的优化设计等。（2）自动控制现在学习的是第45页，共54页遗传算法的应用实例实例2、甘肃工业大学所研制的径向变量柱塞泵控制系统其中G(s)是广义对象，K为控制器；信号w代表所有的外部输入，包括外部扰动、传感器噪声和参考输入量；输出量z为误差信号；Y为可测变量；U为控制变量现在学习的是第46页，共54页遗传算法的应用实例现在学习的是第47页，共54页遗传算法的应用人工生命是用计算机模拟自然界的生命现象，其中生物的自适应、进化和免疫等现象是人工生命的重要研究对象，与遗传算法有密切关系。遗传算法已经在其进化模型、学习模型、行为模型、自组织模型等方面显示出了初步的应用能力。（3）人工生命现在学习的是第48页，共54页遗传算法的应用遗传算法可以对图像进行优化，使图像处理中产生的一些误差达到最小。目前已经在图像恢复、图像边缘特征提取、几何形状识别等方面得到了应用。（4）图像处理和模式识别现在学习的是第49页，共54页遗传算法的应用是遗传算法的一个重要应用领域，已经在移动机器人路径规划、关节机器人运动轨迹规划、机器人逆运动学求解、细胞机器人的结构优化和行为协调等方面得到了应用。（5）机器人智能控制（6）神经网络结构的优化现在学习的是第50页，共54页遗传算法在应用中的一些基本问题1）知识的编码2）适应度函数。a)适应度函数值必须非负。根据情况做适当的处理二进制和十进制的比较：二进制有更多模式和更大的搜索范围；十进制更接近于实际操作。现在学习的是第51页，共54页现在学习的是第52页，共54页3）全局最优和收敛性。根据模式定理，对于具有“欺骗性”函数，GA有可能落入局部最优点。b）为保持种群的多样性，防止“超级”染色体“统治”种群。现在学习的是第53页，共54页感谢大家观看现在学习的是第54页，共54页