遗传算法基本理论与matlab实现

数学建模工作室2020/1/20数学建模培训讲义第1页[e-mail]遗传算法简介张军数学建模工作室2020/1/20数学建模培训讲义第2页[e-mail]非线性规划的基本概念定义如果目标函数或约束条件中至少有一个是非线性函数时的最优化问题就叫做非线性规划问题．一般形式:（1）其中，是定义在En上的实值函数，简记:Xfmin.,...,2,10m;1,2,...,0..ljXhiXgtsjinTnExxxX,,,21jihgf,,1nj1ni1nE:h,E:g,E:EEEf其它情况:求目标函数的最大值或约束条件为小于等于零的情况，都可通过取其相反数化为上述一般形式．数学建模工作室2020/1/20数学建模培训讲义第3页[e-mail]评注•非线性规划的求解一般要比线性规划的求解困难的多，不像线性规划那样有适应于一般情况的单纯形法。•我们知道线性规划的可行域一般是个凸集，其最优解在可行域的边界上达到；而非线性规划问题的可行域一般不是凸集，最优解也不一定在边界上达到。•现在的各种各样的算法都是针对各自特定的适用范围的，这也是正处在研究发展中的学科领域。数学建模工作室2020/1/20数学建模培训讲义第4页[e-mail]罚函数法罚函数法基本思想是通过构造罚函数把约束问题转化为一系列无约束最优化问题，进而用无约束最优化方法去求解．这类方法称为序列无约束最小化方法．简称为SUMT法．其一为SUMT外点法，其二为SUMT内点法．数学建模工作室2020/1/20数学建模培训讲义第5页[e-mail])2(,0min,1212ljjmiiXhMXgMXfMXT可设：)3(,min1MXTnEX）转化为无约束问题：将问题（其中T(X,M)称为罚函数，M称为罚因子，带M的项称为罚项，这里的罚函数只对不满足约束条件的点实行惩罚：当时，满足各，故罚项=0，不受惩罚．当时，必有的约束条件，故罚项0，要受惩罚．DX0,0XhXgiiDX00XhXgii或SUTM外点法)1(.,...,2,10m;1,2,...,0..minljXhiXgtsXfji对一般的非线性规划：数学建模工作室2020/1/20数学建模培训讲义第6页[e-mail])1(,...,2,10..minimXgtsXfi考虑问题：所有严格内点的集合。是可行域中，设集合00,,2,1,0|DmiXgXDi为障碍因子为障碍项，或其中称或：构造障碍函数rXgrXgrXgrXfrXIXgrXfrXIrXImiimiimiimii11111ln1)(),(ln,,）（得值问题：）就转化为求一系列极这样问题（kkkDXrXrXI,min10SUTM内点法（障碍函数法）数学建模工作室2020/1/20数学建模培训讲义第7页[e-mail]遗传算法传统的优化方法（局部优化）共轭梯度法、拟牛顿法、单纯形方法全局优化方法漫步法（RandomWalk）、模拟退火法、GA关于优化问题比较：传统的优化方法1）依赖于初始条件。2）与求解空间有紧密关系，促使较快地收敛到局部解，但同时对解域有约束，如可微或连续。利用这些约束，收敛快。3）有些方法，如Davison-Fletcher-Powell直接依赖于至少一阶导数；共轭梯度法隐含地依赖于梯度。数学建模工作室2020/1/20数学建模培训讲义第8页[e-mail]全局优化方法1）不依赖于初始条件；2）不与求解空间有紧密关系，对解域，无可微或连续的要求。求解稳健，但收敛速度慢。能获得全局最优。适合于求解空间不知的情况数学建模工作室2020/1/20数学建模培训讲义第9页[e-mail]⑴选择运算⑵交换操作⑶变异遗传算法的基本运算遗传算法基本原理模拟自然界优胜劣汰的进化现象，把搜索空间映射为遗传空间，把可能的解编码成一个向量——染色体，向量的每个元素称为基因。通过不断计算各染色体的适应值，选择最好的染色体，获得最优解。数学建模工作室2020/1/20数学建模培训讲义第10页[e-mail]●选择运算——从旧的种群中选择适应度高的染色体，放入匹配集（缓冲区），为以后染色体交换、变异，产生新的染色体作准备。选择方法——适应度比例法（转轮法）按各染色体适应度大小比例来决定其被选择数目的多少。某染色体被选的概率：Pc)()(iicxfxfPxi为种群中第i个染色体，数学建模工作室2020/1/20数学建模培训讲义第11页[e-mail]具体步骤1）计算各染色体适应度值2）累计所有染色体适应度值，记录中间累加值S-mid和最后累加值sum=∑f(xi)3）产生一个随机数N，0〈N〈sum4）选择对应中间累加值S-mid的第一个染色体进入交换集5）重复（3）和（4），直到获得足够的染色体。举例：⒈具有6个染色体的二进制编码、适应度值、Pc累计值。数学建模工作室2020/1/20数学建模培训讲义第12页[e-mail]染色体的适应度和所占的比例用转轮方法进行选择数学建模工作室2020/1/20数学建模培训讲义第13页[e-mail]染色体编号12345678910适应度8217721211737被选概率0.10.020.220.090.020.160.140.090.030.09适应度累计8102734364859666976随机数2349761312757所选染色体号码37103137染色体被选的概率被选的染色体个数⒉10个染色体种群按比例的选择过程数学建模工作室2020/1/20数学建模培训讲义第14页[e-mail]●交换操作方法:随机选择二个染色体(双亲染色体),随机指定一点或多点,进行交换,可得二个新的染色体(子辈染色体).新的子辈染色体:A’11010001B’01011110模拟生物在自然界环境变化,引起基因的突变.在染色体二进制编码中,1变成0;或0变成1.突变产生染色体的多样性,避免进化中早期成熟,陷入局部极值点,突变的概率很低.●变异复制不能创新,交换解决染色体的创新数学建模工作室2020/1/20数学建模培训讲义第15页[e-mail]的流程数学建模工作室2020/1/20数学建模培训讲义第16页[e-mail]简单遗传算法（GA）的基本参数①种群规模P:参与进化的染色体总数.②代沟G:二代之间不相同的染色体数目,无重叠G=1;有重叠0G1③选择方法:转轮法,精英选择法,竞争法.④交换率:Pc一般为60~100%.⑤变异率:Pm一般为0.1~10%举例:变异概率取0.001数学建模工作室2020/1/20数学建模培训讲义第17页[e-mail]初始种群和它的适应度值染色体的交换操纵数学建模工作室2020/1/20数学建模培训讲义第18页[e-mail]举例：数学建模工作室2020/1/20数学建模培训讲义第19页[e-mail]步骤1）编码：确定二进制的位数；组成个体（染色体）位的二进制的值，的第是相应于。和分别为和的最大值和最小值。是和或是，精度二进制位数取决于运算nqbqqqqqyxqqbqqqqqnNnnnnn08,21212minmaxminmax10minminmaxminmax步骤2）选择种群数P和初始个体，计算适应度值，P=20；数学建模工作室2020/1/20数学建模培训讲义第20页[e-mail]遗传算法工具箱数学建模工作室2020/1/20数学建模培训讲义第21页[e-mail]主要函数•GAGeneticalgorithmsolver.•X=GA(FITNESSFCN,NVARS)findstheminimumofFITNESSFCNusing•GA.NVARSisthedimension(numberofdesignvariables)ofthe•FITNESSFCN.FITNESSFCNacceptsavectorXofsize1-by-NAVRS,•andreturnsascalarevaluatedatX.••X=GA(FITNESSFCN,NAVRS,OPTIONS)findstheminimumfor•FITNESSFCNwiththedefaultoptimizationparametersreplacedbyvalues•inthestructureOPTIONS.OPTIONScanbecreatedwiththeGAOPTIMSET•function.数学建模工作室2020/1/20数学建模培训讲义第22页[e-mail]•X=GA(PROBLEM)findstheminimumforPROBLEM.PROBLEMisastructure•thathasthefollowingfields:•fitnessfcn:FitnessFunction•nvars:Numberofdesignvariables•options:OptionsstructurecreatedwithGAOPTIMSET•randstate:Optionalfieldtoresetrandstate•randnstate:Optionalfieldtoresetrandnstate••[X,FVAL]=GA(FITNESSFCN,...)returnsFVAL,thevalueofthefitness•functionFITNESSFCNatthesolutionX.•[X,FVAL,REASON]=GA(FITNESSFCN,...)returnstheREASONforstopping.数学建模工作室2020/1/20数学建模培训讲义第23页[e-mail]•[X,FVAL,REASON,OUTPUT]=GA(FITNESSFCN,...)returnsa•structureOUTPUTwiththefollowinginformation:•randstate:StateofthefunctionRANDusedbeforeGAstarted•randnstate:StateofthefunctionRANDNusedbeforeGAstarted•generations:Totalgenerations,excludingHybridFcniterations•funccount:Totalfunctionevaluations•message:GAterminationmessage•[X,FVAL,REASON,OUTPUT,POPULATION]=GA(FITNESSFCN,...)returnsthefinal•POPULATIONattermination.•[X,FVAL,REASON,OUTPUT,POPULATION,SCORES]=GA(FITNESSFCN,...)returnsthe•SCORESofthefinalPOPULATION.数学建模工作室2020/1/20数学建模培训讲义第24页[e-mail]例子（寻找最小值）•函数：•functiony=two_min(x)•ifx20•y=-exp(-(x/20).^2);•else•y=-exp(-1)+(x-20)*(x-22);•end数学建模工作室2020/1/20数学建模培训讲义第25页[e-mail]数