遗传算法简介遗传算法简介数学建模工作室数学建模工作室2020/11/221非线性规划的基本概念非线性规划的基本概念 定义定义如果目标函数或约束条件中至少有一个是非线性函数时的最优化问题就叫做非线性规划问题非线性规划问题 一般形式一般形式: （1） 其中 ， 是定义在 En 上的实值函数，简记: 其它情况其它情况: 求目标函数的最大值或约束条件为小于等于零的情况，都可通过取其相反数化为上述一般形式数学建模工作室数学建模工作室2020/11/222评注评注非线性规划的求解一般要比线性规划的求解困难的多，不像线性规划那样有适应于一般情况的单纯形法。我们知道线性规划的可行域一般是个凸集，其最优解在可行域的边界上达到；而非线性规划问题的可行域一般不是凸集，最优解也不一定在边界上达到。现在的各种各样的算法都是针对各自特定的适用范围的，这也是正处在研究发展中的学科领域。数学建模工作室数学建模工作室2020/11/223 罚函数法罚函数法 罚函数法罚函数法基本思想是通过构造罚函数把约束问题转化为一系列无约束最优化问题，进而用无约束最优化方法去求解这类方法称为序列无约束最小化方法序列无约束最小化方法简称为SUMTSUMT法法 其一为SUMTSUMT外点法外点法，其二为SUMTSUMT内点法内点法数学建模工作室数学建模工作室2020/11/224 其中T(X,M)称为罚函数罚函数，M称为罚因子罚因子，带M的项称为罚项罚项，这里的罚函数只对不满足约束条件的点实行惩罚：当 时，满足各 ，故罚项=0，不受惩罚当 时，必有 的约束条件，故罚项0，要受惩罚SUTMSUTM外点法外点法数学建模工作室数学建模工作室2020/11/225SUTMSUTM内点法（内点法（障碍函数法）数学建模工作室数学建模工作室2020/11/226遗传算法传统的优化方法（局部优化） 共轭梯度法、拟牛顿法、单纯形方法全局优化方法 漫步法（Random Walk）、模拟退火法、GA关于优化问题比较：传统的优化方法 1）依赖于初始条件。 2）与求解空间有紧密关系，促使较快地收敛到局部 解，但同时对解域有约束，如可微或连续。利用这些约束，收敛快。 3）有些方法，如Davison-Fletcher-Powell直接依赖于至少一阶导数； 共轭梯度法隐含地依赖于梯度。数学建模工作室数学建模工作室2020/11/227全局优化方法1）不依赖于初始条件；2）不与求解空间有紧密关系，对解域，无可微或连续的要求。求 解稳健，但收敛速度慢。能获得全局最优。适合于求解空间不知的情况数学建模工作室数学建模工作室2020/11/228选择运算交换操作变异遗传算法的基本运算遗传算法基本原理模拟自然界优胜劣汰的进化现象，把搜索空间映射为遗传空间，把可能的解编码成一个向量染色体，向量的每个元素称为基因。通过不断计算各染色体的适应值，选择最好的染色体，获得最优解。数学建模工作室数学建模工作室2020/11/229选择运算从旧的种群中选择适应度高的染色体，放入匹配集（缓冲区），为以后染色体交换、变异，产生新的染色体作准备。选择方法适应度比例法（转轮法）按各染色体适应度大小比例来决定其被选择数目的多少。某染色体被选的概率：Pcxi 为种群中第i个染色体，数学建模工作室数学建模工作室2020/11/2210具体步骤1）计算各染色体适应度值2）累计所有染色体适应度值，记录中间累加值S-mid和最后累加值sum=f(xi)3）产生一个随机数N，0 N sum4）选择对应中间累加值S-mid的第一个染色体进入交换集5）重复（3）和（4），直到获得足够的染色体。(首个=N的S-mid所对应的染色体被选中)举例：具有6个染色体的二进制编码、适应度值、Pc累计值。数学建模工作室数学建模工作室2020/11/2211染色体的适应度和所占的比例用转轮方法进行选择数学建模工作室数学建模工作室2020/11/2212染色体编号 1 2 3 4 5 6 7 8 9 10适应度 8 217 7 212117 3 7被选概率0.10.02 0.220.090.020.160.140.090.030.09适应度累计 8 10 27 34 36 48 59 66 6976随机数23497613 1 2757所选染色体号码 3 710 3 1 3 7染色体被选的概率被选的染色体个数10个染色体种群按比例的选择过程数学建模工作室数学建模工作室2020/11/2213交换操作方法:随机选择二个染色体(双亲染色体),随机指定一点或多点,进行交换,可得二个新的染色体(子辈染色体).新的子辈染色体:A11010|001B01011|110模拟生物在自然界环境变化,引起基因的突变.在染色体二进制编码中,1变成0;或0变成1.突变产生染色体的多样性,避免进化中早期成熟,陷入局部极值点,突变的概率很低.变异复制不能创新,交换解决染色体的创新数学建模工作室数学建模工作室2020/11/2214GA的流程数学建模工作室数学建模工作室2020/11/2215简单遗传算法（GA）的基本参数种群规模P:参与进化的染色体总数.代沟G:二代之间不相同的染色体数目,无重叠G=1;有重叠0G1选择方法:转轮法,精英选择法,竞争法.交换率:Pc 一般为60100%.变异率:Pm 一般为0.110%举例:变异概率取0.001数学建模工作室数学建模工作室2020/11/2216初始种群和它的适应度值染色体的交换操纵数学建模工作室数学建模工作室2020/11/2217举例：数学建模工作室数学建模工作室2020/11/2218步骤1）编码：确定二进制的位数；组成个体（染色体）步骤2）选择种群数P 和初始个体，计算适应度值，P=20；数学建模工作室数学建模工作室2020/11/2219遗传算法工具箱遗传算法工具箱数学建模工作室数学建模工作室2020/11/2220主要函数主要函数GA Genetic algorithm solver. X = GA(FITNESSFCN,NVARS) finds the minimum of FITNESSFCN using GA. NVARS is the dimension (number of design variables) of the FITNESSFCN. FITNESSFCN accepts a vector X of size 1-by-NAVRS, and returns a scalar evaluated at X. X = GA(FITNESSFCN,NAVRS,OPTIONS) finds the minimum for FITNESSFCN with the default optimization parameters replaced by values in the structure OPTIONS. OPTIONS can be created with the GAOPTIMSET function.数学建模工作室数学建模工作室2020/11/2221GAX = GA(PROBLEM) finds the minimum for PROBLEM. PROBLEM is a structure that has the following fields: fitnessfcn: nvars: options: randstate: randnstate: X, FVAL = GA(FITNESSFCN, .) returns FVAL, the value of the fitness function FITNESSFCN at the solution X. X,FVAL,REASON = GA(FITNESSFCN, .) returns the REASON for stopping. 数学建模工作室数学建模工作室2020/11/2222GAX,FVAL,REASON,OUTPUT = GA(FITNESSFCN, .) returns a structure OUTPUT with the following information: randstate: randnstate: generations: funccount: message: X,FVAL,REASON,OUTPUT,POPULATION = GA(FITNESSFCN, .) returns the final POPULATION at termination. X,FVAL,REASON,OUTPUT,POPULATION,SCORES = GA(FITNESSFCN, .) returns the SCORES of the final POPULATION.数学建模工作室数学建模工作室2020/11/2223例子（寻找最小值）例子（寻找最小值）函数：function y = two_min(x)if x20 y = -exp(-(x/20).2);else y = -exp(-1)+(x-20)*(x-22);end数学建模工作室数学建模工作室2020/11/2224数学建模工作室数学建模工作室2020/11/2225求解最小值程序求解最小值程序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/11/2226计算结果计算结果x = -0.0014fval = -1.0000reason =Optimization terminated: maximum number of generations exceeded.数学建模工作室数学建模工作室2020/11/2227数学建模工作室数学建模工作室2020/11/2228数学建模工作室数学建模工作室2020/11/2229进一步分析进一步分析options = PopulationType: doubleVector PopInitRange: 2x1 double PopulationSize: 100 EliteCount: 2 CrossoverFraction: 0.8000 MigrationDirection: forward MigrationInterval: 20 MigrationFraction: 0.2000 Generations: 50 TimeLimit: Inf FitnessLimit: -Inf StallGenLimit: Inf StallTimeLimit: Inf InitialPopulation: InitialScores: PlotInterval: 1 CreationFcn: gacreationuniform FitnessScalingFcn: fitscalingrank SelectionFcn: selectionstochunif CrossoverFcn: crossoverscattered MutationFcn: mutationgaussian HybridFcn: Display: final PlotFcns: gaplotbestf OutputFcns: Vectorized: off数学建模工作室数学建模工作室2020/11/2230指定变量的上、下界指定变量的上、下界options.PopInitRange=-11;26options. PopulationSize=300;扩大人口x, fval, reason=ga(two_min, 1, options)数学建模工作室数学建模工作室2020/11/2231数学建模工作室数学建模工作室2020/11/2232数学建模工作室数学建模工作室2020/11/2233遗传算法工具菜单遗传算法工具菜单GATOOL Genetic Algorithm Tool. GATOOL starts a graphical user interface window for editing the default Genetic Algorithm options and running the Genetic Algorithm solver. 数学建模工作室数学建模工作室2020/11/2234数学建模工作室数学建模工作室2020/11/2235数学建模工作室数学建模工作室2020/11/2236DVD在线租赁在线租赁数学建模工作室数学建模工作室2020/11/2237数据数据D001D001D002D002D003D003D004D004D005D005D006D006D007D007D008D008D009D00910 10 40 40 15 15 20 20 20 20 12 12 30 30 33 33 35 35 6 0 0 0 0 0 8 1 0 0 0 0 0 5 1 0 0 0 0 0 0 3 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 9 2 0 0 0 0 10 0 0 0 8 0 0 0 0 0 0 0 0 0 0 数学建模工作室数学建模工作室2020/11/2238将有约束的规划转成将有约束的规划转成无约束规划无约束规划数学建模工作室数学建模工作室2020/11/2239数学建模工作室数学建模工作室2020/11/2240