遗传算法理论（经典实用）

1、数学建模工作室数学建模工作室 2021-5-4 遗传算法理论 第1页 数学建模工作室数学建模工作室 2021-5-4 遗传算法理论 第2页 非线性规划的基本概念非线性规划的基本概念 定义定义 如果目标函数或约束条件中至少有一个是非线性函数 时的最优化问题就叫做非线性规划问题非线性规划问题 一般形式一般形式: （1） 其中 ， 是定义在 En 上的实值函数， 简记: Xfmin .,.,2 , 1 0 m;1,2,., 0 . . ljXh iXg ts j i nT n ExxxX, 21 ji hgf, 1n j 1n i 1n E :h ,E :g ,E :EEEf 其它情况其它情况: 求

2、目标函数的最大值或约束条件为小于等于零 的情况，都可通过取其相反数化为上述一般形式 数学建模工作室数学建模工作室 2021-5-4 遗传算法理论 第3页 非线性规划的求解一般要比线性规划的求解困难 的多，不像线性规划那样有适应于一般情况的单 纯形法。 我们知道线性规划的可行域一般是个凸集，其最 优解在可行域的边界上达到；而非线性规划问题 的可行域一般不是凸集，最优解也不一定在边界 上达到。 现在的各种各样的算法都是针对各自特定的适用 范围的，这也是正处在研究发展中的学科领域。 数学建模工作室数学建模工作室 2021-5-4 遗传算法理论 第4页 罚函数法罚函数法 罚函数法罚函数法基本思想是通过

3、构造罚函数把 约束问题转化为一系列无约束最优化问题， 进而用无约束最优化方法去求解这类方法 称为序列无约束最小化方法序列无约束最小化方法简称为SUMTSUMT 法法 其一为SUMTSUMT外点法外点法，其二为SUMTSUMT内点法内点法 数学建模工作室数学建模工作室 2021-5-4 遗传算法理论 第5页 )2( , 0min, 1 2 1 2 l j j m i i XhMXgMXfMXT可设： )3( ,min 1MXT n EX ）转化为无约束问题：将问题（ 其中T(X,M)称为罚函数罚函数，M称为罚因子罚因子，带M的项称为罚项罚项，这 里的罚函数只对不满足约束条件的点实行惩罚：当 时，

4、满 足各 ，故罚项=0，不受惩罚当 时， 必有 的约束条件，故罚项0，要受惩罚 DX 0, 0XhXg ii DX 00XhXg ii 或 SUTMSUTM外点法外点法 ) 1 ( .,.,2 , 1 0 m;1,2,., 0 . . min ljXh iXg ts Xf j i 对一般的非线性规划： 数学建模工作室数学建模工作室 2021-5-4 遗传算法理论 第6页 ) 1 ( ,.,2 , 10. . min i mXgts Xf i 考虑问题： 所有严格内点的集合。 是可行域中，设集合 00 , 2 , 1, 0|DmiXgXD i 为障碍因子为障碍项，或其中称 或： 构造障碍函数 r

5、 Xg rXgr Xg rXfrXIXgrXfrXIrXI m i i m i i m i i m i i 11 11 1 ln 1 )(),( ln, ）（得 值问题：）就转化为求一系列极这样问题（ k k k DX rXrXI ,min 1 0 SUTMSUTM内点法（内点法（障碍函数法） 数学建模工作室数学建模工作室 2021-5-4 遗传算法理论 第7页 遗传算法 传统的优化方法（局部优化） 共轭梯度法、拟牛顿法、单纯形方法 全局优化方法 漫步法（Random Walk）、模拟退火法、GA 关于优化问题 比较：传统的优化方法 1）依赖于初始条件。 2）与求解空间有紧密关系，促使较快地收

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

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

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

9、 3 4 5 6 7 8 9 10 适应度 8 217 7 212117 3 7 被选概率 0.10.02 0.2 2 0.0 9 0.0 2 0.1 6 0.1 4 0.0 9 0.0 3 0.09 适应度累计 8 10 27 34 36 48 59 66 6976 随机数 23497613 1 2757 所选染色 体号码 3 710 3 1 3 7 染色体被选的概率 被选的染色体个数 10个染色体种群按比例的选择过程 数学建模工作室数学建模工作室 2021-5-4 遗传算法理论 第14页 交换操作 方法:随机选择二个染色体(双亲染色体),随机指定一点或多 点, 进行交换,可得二个新的染色体

10、(子辈染色体). 新的子辈染色体: A 11010|001 B 01011|110 模拟生物在自然界环境变化,引起基因的突变.在染 色体二进制编码中,1变成0;或0变成1.突变产生染色 体的多样性,避免进化中早期成熟,陷入局部极值点, 突变的概率很低. 变异 复制不能创新,交换解决染色体的创新 数学建模工作室数学建模工作室 2021-5-4 遗传算法理论 第15页 GA的流程 数学建模工作室数学建模工作室 2021-5-4 遗传算法理论 第16页 简单遗传算法（GA）的基本参数 种群规模 P: 参与进化的染色体总数. 代沟G: 二代之间不相同的染色体数目,无重叠G = 1; 有重叠 0 G 1

11、 选择方法: 转轮法,精英选择法,竞争法. 交换率: Pc 一般为60100%. 变异率: Pm 一般为0.110% 举例: 变异概率取0.001 数学建模工作室数学建模工作室 2021-5-4 遗传算法理论 第17页 初始种群和它的适应度值 染色体的交换操纵 数学建模工作室数学建模工作室 2021-5-4 遗传算法理论 第18页 举例： 数学建模工作室数学建模工作室 2021-5-4 遗传算法理论 第19页 步骤1）编码：确定二进制的位数；组成个体（染色体） 位的二进制的值，的第是相应于 。和分别为和的最大值和最小值。是和或是 ，精度二进制位数取决于运算 nqb qqqqqyxq qb qq

12、 q qq n N n n n nn 08 , 2 12 12 minmaxminmax 1 0 min minmaxminmax 步骤2）选择种群数P 和初始个体，计算适应度值， P = 20； 数学建模工作室数学建模工作室 2021-5-4 遗传算法理论 第20页 数学建模工作室数学建模工作室 2021-5-4 遗传算法理论 第21页 GA Genetic algorithm solver. X = GA(FITNESSFCN,NVARS) finds the minimum of FITNESSFCN using GA. NVARS is the dimension (number of

13、 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

14、 with the GAOPTIMSET function. 数学建模工作室数学建模工作室 2021-5-4 遗传算法理论 第22页 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 fitness function FITNE

15、SSFCN at the solution X. X,FVAL,REASON = GA(FITNESSFCN, .) returns the REASON for stopping. 数学建模工作室数学建模工作室 2021-5-4 遗传算法理论 第23页 X,FVAL,REASON,OUTPUT = GA(FITNESSFCN, .) returns a structure OUTPUT with the following information: randstate: randnstate: generations: funccount: message: X,FVAL,REASON,OU

16、TPUT,POPULATION = GA(FITNESSFCN, .) returns the final POPULATION at termination. X,FVAL,REASON,OUTPUT,POPULATION,SCORES = GA(FITNESSFCN, .) returns the SCORES of the final POPULATION. 数学建模工作室数学建模工作室 2021-5-4 遗传算法理论 第24页 函数： function y = two_min(x) if x20 y = -exp(-(x/20).2); else y = -exp(-1)+(x-20)

17、*(x-22); end 数学建模工作室数学建模工作室 2021-5-4 遗传算法理论 第25页 数学建模工作室数学建模工作室 2021-5-4 遗传算法理论 第26页 options = gaoptimset; options. PopulationType=doubleVector; options. PopulationSize=100; options.StallGenLimit=inf; options.StallTimeLimit=inf; options.PlotFcns=gaplotbestf; options.Generations=50; x, fval, reason=g

18、a(two_min, 1, options) 数学建模工作室数学建模工作室 2021-5-4 遗传算法理论 第27页 x = -0.0014 fval = -1.0000 reason = Optimization terminated: maximum number of generations exceeded. 数学建模工作室数学建模工作室 2021-5-4 遗传算法理论 第28页 数学建模工作室数学建模工作室 2021-5-4 遗传算法理论 第29页 数学建模工作室数学建模工作室 2021-5-4 遗传算法理论 第30页 options = PopulationType: double

19、Vector 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: PlotInter

20、val: 1 CreationFcn: gacreationuniform FitnessScalingFcn: fitscalingrank SelectionFcn: selectionstochunif CrossoverFcn: crossoverscattered MutationFcn: mutationgaussian HybridFcn: Display: final PlotFcns: gaplotbestf OutputFcns: Vectorized: off 数学建模工作室数学建模工作室 2021-5-4 遗传算法理论 第31页 options.PopInitRange=-11;26 options. PopulationSize=300;扩大人口 x, fval, reason=ga(two_min, 1, options) 数学建模工作室数学建模工作室 2021-5-4 遗传算法理论 第32页 数学建模工作室数学建模工作室 2021-5-4 遗传算法理论 第33页 数学建模工作室数学建模工作室 2021-5-4 遗传算法理论 第34页 GATOOL Genetic Algorithm Tool. GATOOL starts a graphi