《遗传算法2017-7精编版》由会员分享，可在线阅读，更多相关《遗传算法2017-7精编版（62页珍藏版）》请在金锄头文库上搜索。
1、遗传算法 GeneticAlgorithms 太原理工大学数学学院刘晓峰 数学建模一般的步骤和方法 层次分析法量纲分析法图论法微分方程蒙特卡洛法差值拟合法回归分析法数学规划 2020 5 4 2 概率统计数值分析 运筹学机器学习 GA与计算机其余相关学科的关系 2020 5 4 3 生物在自然界中的生存繁衍 显示出了其对自然环境的自适应能力 受其启发 学者致力于对生物各种生存特性的机理研究和行为进行模拟 遗传算法 GeneticAlgorithms GA 就是这种生物行为的计算机模拟中令人瞩目的重要成果 人工免疫 人工神经网络 基于对生物遗传和进化过程的计算机模拟 遗传算法使得各种人工系统具有
2、优良的自适应能力和优化能力 它是模拟达尔文生物进化论的自然选择和孟德尔遗传学机理的生物进化过程的计算模型 是一种通过模拟自然进化过程搜索最优解的方法 遗传算法所借鉴的生物学基础就是生物的遗传和进化 遗传算法的起源 最早由美国密西根大学的J Holland教授提出 起源于60年代对自然和人工自适应系统的研究1967年 Bagley发表了关于遗传算法应用的论文 在其论文中首次使用 遗传算法 GeneticAlgorithm 一词70年代DeJong基于遗传算法的思想在计算机上进行了大量的纯数值函数优化计算实验在一系列研究工作的基础上 80年代由Goldberg进行归纳总结 形成了遗传算法的基本框架
3、 遗传算法发展 1 复制生物的主要遗传方式是复制 遗传过程中 父代的遗传物质DNA被复制到子代 即细胞在分裂时 遗传物质DNA通过复制而转移到新生的细胞中 新细胞就继承了旧细胞的基因 2 交叉有性生殖生物在繁殖下一代时 两个同源染色体之间通过交叉 Crossover 而重组 即在两个染色体的某一相同位置处DNA被切断 其前后两串分别交叉组合而形成两个新的染色体 3 变异在进行细胞复制时 虽然概率很小 仅仅有可能产生某些复制差错 从而使DNA发生某种变异 Mutation 产生出新的染色体 这些新的染色体表现出新的性状 如此这般 遗传基因 或染色体 在遗传的过程中由于各种各样的原因而发生变化 生
4、物的遗传方式 遗传算法的进化形式和单位 生物的进化是以集团的形式共同进行的 这样的一个团体称为群体 种群 Population 组成群体的单个生物体称为个体 Individual 染色体 Chromosome 每一个个体对其生存环境都有不同的适应能力 这种适应能力称为个体的适应度 Fitness 物竞天择个体的基因 Gene 是遗传的基本单位遗传基因在染色体中所占据的位置称为基因座同一基因座可能有的全部基因称为等位基因 Allele 2020 5 4 遗传算法的简单原理 遗传算法将问题域中的可能解看做是群体的一个个体或染色体 并将所有个体编码成符号串形式模拟达尔文的遗传选择和自然淘汰的生物进化
5、过程 对群体反复进行基于遗传学的操作 选择 交叉和变异 根据预定的目标适应度函数对每个个体进行评价依据适者生存 优胜劣汰的进化规则 不断得到更优的群体 同时以全局并行搜索方式来搜索优化群体中的最优个体 求得满足要求的最优解 2020 5 4 8 遗传算法是模拟生物在自然环境下的遗传和进化过程而形成的一种自适应全局优化概率搜索方法 袋鼠与珠穆朗玛峰的假想实验 在遗传算法中 假设将很多只袋鼠降落到喜马拉雅山脉的任意地方 这些袋鼠并不知道它们被设想寻找珠穆朗玛峰 休闲地活着 但每过几年 就在海拔较低的一些地方射杀一些袋鼠 并希望存活下来的那些是多产的 并在那里生儿育女 这个实验进行N年之后 2020
6、 5 4 9 2020 5 4 10 对求函数最大值的优化问题 或最小值 可描述为下述数学规划模型 maxf X 1 1 s t X R 1 2 R U 1 3 其中 X x1 x2 xn T为决策变量 f X 为目标函数 式 1 2 1 3 为约束条件 U是基本空间 R是U的一个子集 满足约束条件的解X称为可行解 集合R表示由所有满足约束条件的解所组成的一个集合 叫做可行解集合 优化问题 遗传算法在函数优化中的应用 例 利用遗传算法求解区间 0 31 上的二次函数y x2的最大值 x为自然数 将每一个自然数看成一个生命体 通过进化 看谁能生存下来 谁就是所寻找的数字 即问题的解 y x2 3
7、1X Y 0 2020 5 4 12 求解过程 将每一个数作为一个生命体 就必须给其赋予一定的基因 这个过程叫做编码 可以将变量x编码成5位长的二进制无符号整数表达形式 例如 x 13 01101 即数13的基因为01101 编码 1 2 2020 5 4 13 解的编码 2020 5 4 14 求解过程 将每一个数作为一个生命体 就必须给其赋予一定的基因 这个过程叫做编码 可以将变量x编码成5位长的二进制无符号整数表达形式 例如 x 13 01101 即数13的基因为01101 由于遗传的需要 必须设定一些初始的生物群体 让其作为生物繁殖的第一代 为了保证生物的多样性和竞争的公平性 初始种群
8、的所有个体都是通过随机方法产生的 编码 1 2 初始种群的生成 2020 5 4 15 2020 5 4 16 生物的进化服从适者生存 优胜劣汰的规则 因此必须规定什么样的基因是 优 的 什么样的基因是 劣 的 称为适应度函数 显然 定义为适应度函数 然后计算所有个体的适应度值 适应度计算 3 4 2020 5 4 17 解码 计算适应度 2020 5 4 18 生物的进化服从适者生存 优胜劣汰的规则 因此必须规定什么样的基因是 优 的 什么样的基因是 劣 的 称为适应度函数 显然 定义为适应度函数 然后计算所有个体的适应度值 选择运算就是优胜劣汰的过程 把当前群体中适应度较高的个体按某种规则
9、或模型遗传到下一代群体中 一般适应度较高的个体将有更多的机会遗传到下一代群体中 选择是一个概率选择的过程 基因差的不一定会被淘汰 适应度计算 选择 3 4 2020 5 4 19 为了产生新的个体 种群中进行交叉繁殖 以某一概率选出两个个体 相互交换一部分基因 就形成了两个新的个体 交叉 5 2020 5 4 20 交叉位 Pcross cross 父代个体 子代个体 交叉概率 连续改变个体多个基因位上的遗传信息 1 2 1 2 2020 5 4 21 为了产生新的个体 种群中进行交叉繁殖 以某一概率选出两个个体 相互交换一部分基因 就形成了两个新的个体 变异运算是将个体基因中的某一位以一定的
10、小概率发生变化 也可以产生新的个体 交叉 5 6 变异 2020 5 4 22 变异位 Pmutate mutate 父代个体 子代个体 变异概率 2020 5 4 23 为了产生新的个体 种群中进行交叉繁殖 以某一概率选出两个个体 相互交换一部分基因 就形成了两个新的个体 变异运算是将个体基因中的某一位以一定的小概率发生变化 也可以产生新的个体 交叉 5 6 变异 这样就经过了一代进化 通过上述步骤不断地循环进化 种群中的个体基因便逐渐地趋向最优 2020 5 4 24 Y 2020 5 4 25 遗传算法流程图 2020 5 4 26 步1在搜索空间U上定义一个适应度函数f x 给定种群规
11、模N 交叉率Pc和变异率Pm 代数T 基本遗传算法步骤 步2随机产生U中的N个个体s1 s2 sN 组成初始种群S s1 s2 sN 置代数计数器t 1 步3计算S中每个个体的适应度f 步4若终止条件满足 则取S中适应度最大的个体作为所求结果 算法结束 步5否则 按选择概率P xi 所决定的选中机会 每次从S中随机选定1个个体并将其染色体复制 共做N次 然后将复制所得的N个染色体组成群体S1 步7按变异率Pm所决定的变异次数m 从S2中随机确定m个染色体 分别进行变异操作 并用产生的新染色体代替原染色体 得群体S3 步8将群体S3作为新一代种群 即用S3代替S t t 1 转步3 步6按交叉率
12、Pc所决定的参加交叉的染色体数c 从S1中随机确定c个染色体 配对进行交叉操作 并用产生的新染色体代替原染色体 得群体S2 基本遗传算法步骤 基本遗传算法的运行参数 M 群体大小 群体规模POP 即群体中所含个体的数量 一般取为20 100T 遗传运算的终止进化代数 一般取为100 500pc 交叉概率 crossoverrate 就是参加交叉运算的染色体个数占全体染色体总数的比例 记为Pc 一般取为0 5 0 9pm 变异概率 mutationrate 是指发生变异的基因位数所占全体染色体的基因总位数的比例 记为Pm 一般取为0 0001 0 1 说明 这4个运行参数对遗传算法的求解结果和求
13、解效率都有一定的影响 但目前尚无合理选择它们的理论依据 在遗传算法的实际应用中 往往需要经过多次试算后才能确定出这些参数合理的取值大小或取值范围 适应度收敛曲线 遗传算法工具箱 遗传算法的工具箱有很多种 GeneticAlgorithmTool简称GATOOL GADSGeneticAlgorithmOptimizationTool简称GAOTGeneticAlgorithmToolbox简称GATBXSimpleGeneticAlgorithm1002简称SGA1002 MainfunctionComparationOfGeneticAlgorithmToolboxbaseMatlab ga
14、tbx工具箱版本查看 v ver gatbx v Name GeneticAlgorithmToolbox Version 1 2 Release Date 15 Apr 94 遗传算法与直接搜索工具箱GADS GADS工具箱是一系列函数的集合 它们扩展了优化工具箱和MATLAB数值计算环境的性能 使得用户能够求解那些标准优化工具箱范围之外的各种优化问题 所有的工具箱函数都是m文件 可以使用typefunctionname查看函数代码也可以通过编写自己的m文件来实现和扩展GADS工具箱的性能 遗传算法 直接搜索工具箱和优化工具箱是紧密结合在一起的 用户可以用GADS工具箱来寻找最佳起始点 然后
15、利用优化工具箱或其它程序来进一步寻找最优解 Matlab自带遗传算法工具箱GADS 工具箱具有两种使用方式 1 以命令行方式调用遗传算法函数ga 2 通过图形用户界面使用遗传算法工具箱 命令行方式 xfval ga fitnessfun nvars options fitnessfun是求最小值的适应度函数句柄 nvars是适应度函数的独立变量的个数 options是一个包含遗传算法选项设置 属性参数的结构 如果没有特别改写 则ga使用它本身的默认选项值 可以通过函数gaoptimset修改设置 x 最终值到达的点 fval 适应度函数的最终值 Rastrigin函数 测试函数 Rastrig
16、in定义为 Ras x 20 x1 x1 x2 x2 10 cos 2 pi x1 cos 2 pi x2 5 12 x1 x2 5 12 图形显示具有多个局部最小值和一个全局最小值 出现在点 0 0 处 函数值为0 在任何不同于 0 0 的局部最小点处 Rastrigin函数的值均大于0 局部最小处距原点越远 该点处Rastrigin函数的值越大 之所以选它为测试函数 因为它有许多局部最小点 具有很强的欺骗性 使得用标准的 基于梯度的查找全局最小的方法十分困难 命令行方式调用遗传算法函数ga 句柄为 rastriginsfcn有2个变量 xfval ga rastriginsfcn 2 Optimizationterminated averagechangeinthefitnessvaluelessthanoptions FunctionTolerance x 0 0015 0 0166fval 0 0553 遗传算法求解函数ga的一般用法 函数gaoptimset的语法格式为options gaoptimset PropertyName1 PropertyValue1 Proper
