遗传算法理论

《遗传算法理论》由会员分享，可在线阅读，更多相关《遗传算法理论（40页珍藏版）》请在金锄头文库上搜索。

1、数学建模工作室 2019/4/17,数学建模培训讲义,第1页 mecca_,遗传算法简介,数学建模工作室 2019/4/17,数学建模培训讲义,第2页 mecca_,非线性规划的基本概念,定义 如果目标函数或约束条件中至少有一个是非线性函数时的最优化问题就叫做非线性规划问题,一般形式: （1） 其中 ， 是定义在 En 上的实值函数，简记:,其它情况: 求目标函数的最大值或约束条件为小于等于零的情况，都可通过取其相反数化为上述一般形式,数学建模工作室 2019/4/17,数学建模培训讲义,第3页 mecca_,评注,非线性规划的求解一般要比线性规划的求解困难的多，不像线性规划那样有适应于一般情

2、况的单纯形法。 我们知道线性规划的可行域一般是个凸集，其最优解在可行域的边界上达到；而非线性规划问题的可行域一般不是凸集，最优解也不一定在边界上达到。 现在的各种各样的算法都是针对各自特定的适用范围的，这也是正处在研究发展中的学科领域。,数学建模工作室 2019/4/17,数学建模培训讲义,第4页 mecca_,罚函数法,罚函数法基本思想是通过构造罚函数把约束问题转化为一系列无约束最优化问题，进而用无约束最优化方法去求解这类方法称为序列无约束最小化方法简称为SUMT法 其一为SUMT外点法，其二为SUMT内点法,数学建模工作室 2019/4/17,数学建模培训讲义,第5页 mecca_,其中T

3、(X,M)称为罚函数，M称为罚因子，带M的项称为罚项，这里的罚函数只对不满足约束条件的点实行惩罚：当 时，满足各 ，故罚项=0，不受惩罚当 时，必有 的约束条件，故罚项0，要受惩罚,SUTM外点法,数学建模工作室 2019/4/17,数学建模培训讲义,第6页 mecca_,SUTM内点法（障碍函数法）,数学建模工作室 2019/4/17,数学建模培训讲义,第7页 mecca_,遗传算法,传统的优化方法（局部优化） 共轭梯度法、拟牛顿法、单纯形方法 全局优化方法 漫步法（Random Walk）、模拟退火法、GA,关于优化问题,比较：,传统的优化方法,1）依赖于初始条件。 2）与求解空间有紧密关

4、系，促使较快地收敛到局部 解，但同时对解域有约束，如可微或连续。利用这些约束，收敛快。 3）有些方法，如Davison-Fletcher-Powell直接依赖于至少一阶导数； 共轭梯度法隐含地依赖于梯度。,数学建模工作室 2019/4/17,数学建模培训讲义,第8页 mecca_,全局优化方法,1）不依赖于初始条件； 2）不与求解空间有紧密关系，对解域，无可微或连续的要求。求 解稳健，但收敛速度慢。能获得全局最优。适合于求解空间不知的情况,数学建模工作室 2019/4/17,数学建模培训讲义,第9页 mecca_, 选择运算 交换操作 变异,遗传算法的基本运算,遗传算法基本原理,模拟自然界优胜

5、劣汰的进化现象，把搜索空间映射为遗传 空间，把可能的解编码成一个向量染色体，向量的每个 元素称为基因。 通过不断计算各染色体的适应值，选择最好的染色体，获 得最优解。,数学建模工作室 2019/4/17,数学建模培训讲义,第10页 mecca_,选择运算 从旧的种群中选择适应度高的染色体，放入匹配集（缓冲 区），为以后染色体交换、变异，产生新的染色体作准备。,选择方法适应度比例法（转轮法） 按各染色体适应度大小比例来决定其被选择数目的多少。 某染色体被选的概率：Pc,xi 为种群中第i个染色体，,数学建模工作室 2019/4/17,数学建模培训讲义,第11页 mecca_,具体步骤,1）计算各

6、染色体适应度值 2）累计所有染色体适应度值，记录中间累加值S - mid 和最 后累加值 sum = f(xi) 3） 产生一个随机数 N，0 N sum 4） 选择对应中间累加值S - mid 的第一个染色体进入交换集 5） 重复（3）和（4），直到获得足够的染色体。 (首个=N的S-mid所对应的染色体被选中),举例： 具有6个染色体的二进制编码、适应度值、Pc累计 值。,数学建模工作室 2019/4/17,数学建模培训讲义,第12页 mecca_,染色体的 适应度和所占的比例,用转轮方法进行选择,数学建模工作室 2019/4/17,数学建模培训讲义,第13页 mecca_,染色体被选的概

7、率,被选的染色体个数,10个染色体种群按比例的选择过程,数学建模工作室 2019/4/17,数学建模培训讲义,第14页 mecca_,交换操作,方法:随机选择二个染色体(双亲染色体),随机指定一点或多点, 进行交换,可得二个新的染色体(子辈染色体).,新的子辈染色体: A 11010|001 B 01011|110,模拟生物在自然界环境变化,引起基因的突变.在染色体二进制编码中,1变成0;或0变成1.突变产生染色体的多样性,避免进化中早期成熟,陷入局部极值点,突变的概率很低.,变异,复制不能创新,交换解决染色体的创新,数学建模工作室 2019/4/17,数学建模培训讲义,第15页 mecca_

8、,GA的流程,数学建模工作室 2019/4/17,数学建模培训讲义,第16页 mecca_,简单遗传算法（GA）的基本参数,种群规模 P: 参与进化的染色体总数. 代沟G: 二代之间不相同的染色体数目,无重叠G = 1; 有重叠 0 G 1 选择方法: 转轮法,精英选择法,竞争法. 交换率: Pc 一般为60100%. 变异率: Pm 一般为0.110%,举例:,变异概率取0.001,数学建模工作室 2019/4/17,数学建模培训讲义,第17页 mecca_,初始种群和它的适应度值,染色体的交换操纵,数学建模工作室 2019/4/17,数学建模培训讲义,第18页 mecca_,举例：,数学建

9、模工作室 2019/4/17,数学建模培训讲义,第19页 mecca_,步骤1）编码：确定二进制的位数；组成个体（染色体）,步骤2）选择种群数P 和初始个体，计算适应度值， P = 20；,数学建模工作室 2019/4/17,数学建模培训讲义,第20页 mecca_,遗传算法工具箱,数学建模工作室 2019/4/17,数学建模培训讲义,第21页 mecca_,主要函数,GA Genetic algorithm solver. X = GA(FITNESSFCN,NVARS) finds the minimum of FITNESSFCN using GA. NVARS is the dimen

10、sion (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

11、can be created with the GAOPTIMSET function.,数学建模工作室 2019/4/17,数学建模培训讲义,第22页 mecca_,GA,X = 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 fi

12、tness function FITNESSFCN at the solution X. X,FVAL,REASON = GA(FITNESSFCN, .) returns the REASON for stopping.,数学建模工作室 2019/4/17,数学建模培训讲义,第23页 mecca_,GA,X,FVAL,REASON,OUTPUT = GA(FITNESSFCN, .) returns a structure OUTPUT with the following information: randstate: randnstate: generations: funccount:

13、 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.,数学建模工作室 2019/4/17,数学建模培训讲义,第24页 mecca_,例子（寻找最小值）,函数： function y = two_min(x) if x20 y = -e

14、xp(-(x/20).2); else y = -exp(-1)+(x-20)*(x-22); end,数学建模工作室 2019/4/17,数学建模培训讲义,第25页 mecca_,数学建模工作室 2019/4/17,数学建模培训讲义,第26页 mecca_,求解最小值程序,options = gaoptimset; options. PopulationType=doubleVector; options. PopulationSize=100; options.StallGenLimit=inf; options.StallTimeLimit=inf; options.PlotFcns=g

15、aplotbestf; options.Generations=50; x, fval, reason=ga(two_min, 1, options),数学建模工作室 2019/4/17,数学建模培训讲义,第27页 mecca_,计算结果,x = -0.0014 fval = -1.0000 reason = Optimization terminated: maximum number of generations exceeded.,数学建模工作室 2019/4/17,数学建模培训讲义,第28页 mecca_,数学建模工作室 2019/4/17,数学建模培训讲义,第29页 mecca_,数学建模工作室 2019/4/17,数学建模培训讲义,第30页 mecca_,进一步分析,options = PopulationType: doubleVector PopInitRange