遗传算法理论.ppt

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