遗传算法理论ppt课件

数学建模工作室2020/5/26,.,第1页mecca_zj,遗传算法简介,数学建模工作室2020/5/26,.,第2页mecca_zj,非线性规划的基本概念,定义如果目标函数或约束条件中至少有一个是非线性函数时的最优化问题就叫做非线性规划问题,一般形式:（1）其中，是定义在En上的实值函数，简记:,其它情况:求目标函数的最大值或约束条件为小于等于零的情况，都可通过取其相反数化为上述一般形式,数学建模工作室2020/5/26,.,第3页mecca_zj,评注,非线性规划的求解一般要比线性规划的求解困难的多，不像线性规划那样有适应于一般情况的单纯形法。我们知道线性规划的可行域一般是个凸集，其最优解在可行域的边界上达到；而非线性规划问题的可行域一般不是凸集，最优解也不一定在边界上达到。现在的各种各样的算法都是针对各自特定的适用范围的，这也是正处在研究发展中的学科领域。,数学建模工作室2020/5/26,.,第4页mecca_zj,罚函数法,罚函数法基本思想是通过构造罚函数把约束问题转化为一系列无约束最优化问题，进而用无约束最优化方法去求解这类方法称为序列无约束最小化方法简称为SUMT法其一为SUMT外点法，其二为SUMT内点法,数学建模工作室2020/5/26,.,第5页mecca_zj,其中T(X,M)称为罚函数，M称为罚因子，带M的项称为罚项，这里的罚函数只对不满足约束条件的点实行惩罚：当时，满足各，故罚项=0，不受惩罚当时，必有的约束条件，故罚项0，要受惩罚,SUTM外点法,数学建模工作室2020/5/26,.,第6页mecca_zj,SUTM内点法（障碍函数法）,数学建模工作室2020/5/26,.,第7页mecca_zj,遗传算法,传统的优化方法（局部优化）共轭梯度法、拟牛顿法、单纯形方法全局优化方法漫步法（RandomWalk）、模拟退火法、GA,关于优化问题,比较：,传统的优化方法,1）依赖于初始条件。2）与求解空间有紧密关系，促使较快地收敛到局部解，但同时对解域有约束，如可微或连续。利用这些约束，收敛快。3）有些方法，如Davison-Fletcher-Powell直接依赖于至少一阶导数；共轭梯度法隐含地依赖于梯度。,数学建模工作室2020/5/26,.,第8页mecca_zj,全局优化方法,1）不依赖于初始条件；2）不与求解空间有紧密关系，对解域，无可微或连续的要求。求解稳健，但收敛速度慢。能获得全局最优。适合于求解空间不知的情况,数学建模工作室2020/5/26,.,第9页mecca_zj,选择运算交换操作变异,遗传算法的基本运算,遗传算法基本原理,模拟自然界优胜劣汰的进化现象，把搜索空间映射为遗传空间，把可能的解编码成一个向量染色体，向量的每个元素称为基因。通过不断计算各染色体的适应值，选择最好的染色体，获得最优解。,数学建模工作室2020/5/26,.,第10页mecca_zj,选择运算从旧的种群中选择适应度高的染色体，放入匹配集（缓冲区），为以后染色体交换、变异，产生新的染色体作准备。,选择方法适应度比例法（转轮法）按各染色体适应度大小比例来决定其被选择数目的多少。某染色体被选的概率：Pc,xi为种群中第i个染色体，,数学建模工作室2020/5/26,.,第11页mecca_zj,具体步骤,1）计算各染色体适应度值2）累计所有染色体适应度值，记录中间累加值S-mid和最后累加值sum=f(xi)3）产生一个随机数N，0Nsum4）选择对应中间累加值S-mid的第一个染色体进入交换集5）重复（3）和（4），直到获得足够的染色体。(首个=N的S-mid所对应的染色体被选中),举例：具有6个染色体的二进制编码、适应度值、Pc累计值。,数学建模工作室2020/5/26,.,第12页mecca_zj,染色体的适应度和所占的比例,用转轮方法进行选择,数学建模工作室2020/5/26,.,第13页mecca_zj,染色体被选的概率,被选的染色体个数,10个染色体种群按比例的选择过程,数学建模工作室2020/5/26,.,第14页mecca_zj,交换操作,方法:随机选择二个染色体(双亲染色体),随机指定一点或多点,进行交换,可得二个新的染色体(子辈染色体).,新的子辈染色体:A11010|001B01011|110,模拟生物在自然界环境变化,引起基因的突变.在染色体二进制编码中,1变成0;或0变成1.突变产生染色体的多样性,避免进化中早期成熟,陷入局部极值点,突变的概率很低.,变异,复制不能创新,交换解决染色体的创新,数学建模工作室2020/5/26,.,第15页mecca_zj,GA的流程,数学建模工作室2020/5/26,.,第16页mecca_zj,简单遗传算法（GA）的基本参数,种群规模P:参与进化的染色体总数.代沟G:二代之间不相同的染色体数目,无重叠G=1;有重叠0G1选择方法:转轮法,精英选择法,竞争法.交换率:Pc一般为60100%.变异率:Pm一般为0.110%,举例:,变异概率取0.001,数学建模工作室2020/5/26,.,第17页mecca_zj,初始种群和它的适应度值,染色体的交换操纵,数学建模工作室2020/5/26,.,第18页mecca_zj,举例：,数学建模工作室2020/5/26,.,第19页mecca_zj,步骤1）编码：确定二进制的位数；组成个体（染色体）,步骤2）选择种群数P和初始个体，计算适应度值，P=20；,数学建模工作室2020/5/26,.,第20页mecca_zj,遗传算法工具箱,数学建模工作室2020/5/26,.,第21页mecca_zj,主要函数,GAGeneticalgorithmsolver.X=GA(FITNESSFCN,NVARS)findstheminimumofFITNESSFCNusingGA.NVARSisthedimension(numberofdesignvariables)oftheFITNESSFCN.FITNESSFCNacceptsavectorXofsize1-by-NAVRS,andreturnsascalarevaluatedatX.X=GA(FITNESSFCN,NAVRS,OPTIONS)findstheminimumforFITNESSFCNwiththedefaultoptimizationparametersreplacedbyvaluesinthestructureOPTIONS.OPTIONScanbecreatedwiththeGAOPTIMSETfunction.,数学建模工作室2020/5/26,.,第22页mecca_zj,GA,X=GA(PROBLEM)findstheminimumforPROBLEM.PROBLEMisastructurethathasthefollowingfields:fitnessfcn:nvars:options:randstate:randnstate:X,FVAL=GA(FITNESSFCN,.)returnsFVAL,thevalueofthefitnessfunctionFITNESSFCNatthesolutionX.X,FVAL,REASON=GA(FITNESSFCN,.)returnstheREASONforstopping.,数学建模工作室2020/5/26,.,第23页mecca_zj,GA,X,FVAL,REASON,OUTPUT=GA(FITNESSFCN,.)returnsastructureOUTPUTwiththefollowinginformation:randstate:randnstate:generations:funccount:message:X,FVAL,REASON,OUTPUT,POPULATION=GA(FITNESSFCN,.)returnsthefinalPOPULATIONattermination.X,FVAL,REASON,OUTPUT,POPULATION,SCORES=GA(FITNESSFCN,.)returnstheSCORESofthefinalPOPULATION.,数学建模工作室2020/5/26,.,第24页mecca_zj,例子（寻找最小值）,函数：functiony=two_min(x)ifx20y=-exp(-(x/20).2);elsey=-exp(-1)+(x-20)*(x-22);end,数学建模工作室2020/5/26,.,第25页mecca_zj,数学建模工作室2020/5/26,.,第26页mecca_zj,求解最小值程序,options=gaoptimset;options.PopulationType=doubleVector;options.PopulationSize=100;options.StallGenLimit=inf;options.StallTimeLimit=inf;options.PlotFcns=gaplotbestf;options.Generations=50;x,fval,reason=ga(two_min,1,options),数学建模工作室2020/5/26,.,第27页mecca_zj,计算结果,x=-0.0014fval=-1.0000reason=Optimizationterminated:maximumnumberofgenerationsexceeded.,数学建模工作室2020/5/26,.,第28页mecca_zj,数学建模工作室2020/5/26,.,第29页mecca_zj,数学建模工作室2020/5/26,.,第30页mecca_zj,进一步分析,options=PopulationType:doubleVectorPopInitRange:2x1doublePopulationSize:100EliteCount:2CrossoverFraction:0.8000MigrationDirection:forwardMigrationInterval:20MigrationFraction:0.2000Generations:50TimeLimit:Inf,FitnessLimit:-InfStallGenLimit:InfStallTimeLimit:InfInitialPopulation:InitialScores:PlotInterval:1CreationFcn:gacreationuniformFitnessScalingFcn:fitscalingrankSelectionFcn:selectionstochunifCrossoverFcn:crossoverscatteredMutationFcn:mutationgaussianHybridFcn:Display:finalPlotFcns:gaplotbestfOutputFcns:Vectorized:off,数学建模工作室2020/5/26,.,第31页mecca_zj,指定变量的上、下界,options.PopInitRange=-11;26options.PopulationSize=300;扩大人口x,fval,reason=ga(two_min,1,options),数学建模工作室2020/5/26,.,第32页mecca_zj,数学建模工作室2020/5/26,.,第33页mecca_zj,数学建模工作室2020/5/26,.,第34页mecca_zj,遗传算法工具菜单,GATOOLGeneticAlgorithmTool.GATOOLstartsagraphicaluserinterfacewindowforeditingthedefaultGeneticAlgorithmopt