《机器学习课件p3 遗传算法eb》由会员分享，可在线阅读，更多相关《机器学习课件p3 遗传算法eb（95页珍藏版）》请在金锄头文库上搜索。
1、第三部分,遗传算法,参考书目,王晓平，曹立明 遗传算法-理论、应用与软件实现 西安交通大学出版社 孙增忻 智能控制理论与技术 清华大学出版社 李人厚 智能控制理论和方法 西安电子科技大学出版社,1 遗传算法简介,John Henry Holland,1975 Adaptation in Natural and Artificial Systems David E. Goldberg,1989 Genetic Algorithms,遗传算法简介,模拟自然界的进化现象：适者生存 优胜劣汰 把搜索空间映射为遗传空间 把每一个可能的解编码为一个向量 向量：染色体、个体 元素：基因 向量的表示：二进制或
2、十进制的串,遗传算法简介,多个染色体组成种群、群体或集团 按预定的目标函数对每个染色体进行评价 根据结果给出其适应度 新一代的个体不断地在总体性能胜过旧的一代,遗传算法的特点,适者生存、优胜劣汰 鲁棒性 在各种不同的环境中通过效率与功能之间的平衡以求生存的能力。 启发式搜索，适用于复杂问题的优化 常规的优化方法 解析法 枚举法 随机法,2 遗传算法的工作原理及操作步骤,问题： 在整数论域0,31内，求解如下函数的极大值。,问题的表述与参数的编码,将待寻优的参数编码为有限长度的串 5位二进制编码 定义目标函数 极大值,确定初始种群 step0,初始种群的数量 4 随机生成初始种群 01101 1
3、1000 01000 10011 染色体与基因,复制（Selection） step1,计算个体的适配值（Fitness） 适配值 适配值占整体的比例 适配值累加 根据适配值确定复制概率 复制（选择）策略 轮盘赌 轮转法、比例选择法,轮盘赌示意图,复制操作前的有关数据,交叉（Crossover） step2,复制后产生的个体随机两两匹配 交叉繁殖 长度为l的串数字之间的空隙标记为 随机产生位置整数 从位置k到串尾的子串互相交换，形成新串,复制操作后的有关数据,变异（Mutation） step3,以极小的概率随机地改变基因 一个串位的值 P=0.001: 20 0.001=0.02 无变异 满
4、足预定指标退出，否则转 step1,标准遗传算法流程,3 遗传算法的数学依据,图式、模式 定义长度 确定位数、图式的阶次 图式定理,图式,描述种群中任意染色体之间相似性的一组符号串 由符号0，1和通配符 定义 0、1序列组成图式的固定部分， 表示其变化部分 整个图式表示有意义的匹配模式,图式 例,图式 0 1 可匹配的串 0 1 0 0 0 1 0 1 0 1 1 0 0 1 1 1,图式数,二进制 最大图式数： 其他进制 最大图式数： 图式数大于串的数量,图式的意义,GA利用种群中包含的众多的图式及染色体符号串之间的相似性信息进行启发式搜索和问题求解。 在产生新一代的过程中，GA完成了正比于
5、种群长度的计算量，而处理的图式却正比于种群长度的三次方。,图式的定义长度与阶次,定义长度 H左右两端有定义的位置之间的距离 1 1：5-1=4 确定位数、阶次 H中有定义的位的个数 1 1：2,组块,种群中定义长度短、确定位数少和适应度高的图式 GA的运算实际上是对组块的操作,复制对图式的影响,设m(H,t)表示在第t代种群中存在的图式H的数量，f(H)为在t时刻包含H的染色体的平均适应度。对于有n个染色体的种群，经复制操作，在t+1时刻，图式H的数量表示为m(H,t+1) 。,复制对图式的影响,在复制运算中，下一代种群中的数量正比于种群中染色体平均适应度与种群平均适应度的比值。,交叉对图式的
6、影响,图式因交叉而被破坏的概率,交叉的概率,染色体的长度,变异对图式的影响,图式因变异而被破坏的概率,变异的概率,图式定理,在复制、交叉和变异运算的作用下，确定位数少、定义长度短和适应度高的图式（组块）将按指数的规律，一代一代地增长。,4 遗传算法的有关问题,知识的表示 适应度函数 全局收敛与最优性 早期收敛早熟,4.1 知识的表示-编码,编码的基本原理 David E. Goldberg 所选编码方式应使确定位数少、定义长度短的图式与所求解的问题相关，而同其他固定位的图式与求解问题关系少一些。 所选的编码方式应具有最小的字符集，自然地表达欲求解的问题。,二进制编码与非二进制编码,相同的解的数
7、量 提供的图式数量,多参数优化问题的编码,已编码整数的线性映射 映射的精度,构造多参数的编码,按要求将单参数编码连接起来即可，每一个码可以有自己的子长度和取值范围。,4.2 适应度函数,适应度函数值非负 待优化问题表述为最大化问题,目标函数最小化,可以当作输入参数、所观测到的最大值、当前或前k代种群中的最大值。,目标函数最大化,可以当作输入参数、当前或前k代种群中的最小值的绝对值。,超级染色体,4.3 全局收敛与早熟,已经证明，当采用轮转法时，简单的GA都不会以1的概率收敛到全局的最优点。只有采用精英选择法和改进的GA可以收敛到全局的最优点。 在进化的初期，按照轮转法，少数具有相对高的适应度的
8、“超常”染色体会获得较多的后代，抑制了具有优秀图式的普通染色体的生长，造成成熟前收敛。,全局收敛与早熟,5 遗传算法的有关问题,5.1 复制(Selection)方法,精英选择法 确定性选择法 置换式余数随机选择法 非置换式余数随机选择法 Rank-based Roulette wheel selection,复制(Selection)方法,Stochastic universal sampling Local selection Truncation selection Tournament selection,复制的评价指标,Selective pressure probability o
9、f the best individual being selected compared to the average probability of selection of all individuals Bias absolute difference between an individuals normalized fitness and its expected probability of reproduction,复制的评价指标,Spread range of possible values for the number of offspring of an individua
10、l Loss of diversity proportion of individuals of a population that is not selected during the selection phase,复制的评价指标,Selection intensity expected average fitness value of the population after applying a selection method to the normalized Gaussian distribution Selection variance expected variance of
11、 the fitness distribution of the population after applying a selection method to the normalized Gaussian distribution,精英选择法,把种群中最优秀的个体直接复制到下一代 提高优秀个体对种群的控制速度 改善局部搜索和GA特性 损坏了全局的搜索能力,确定性选择法,选择概率按常规计算 计算期望的后代数目 按整数部分分配后代数目 染色体按余数降序排列 种群其余部分按排序表由高到低依次选择填充,置换式余数随机选择法,开始部分同确定性选择法 余数部分用来计算轮转法中的权值,置换式余数随机选择
12、法,开始部分同确定性选择法 余数部分按概率来处理,Rank-based Selection,Rank fitness assignment Linear ranking Non-linear ranking,Linear Ranking,SP: 选择压力 Nind: 种群规模,Non-linear Ranking,Linear and Non-linear Ranking,Roulette Wheel Selection,Stochastic Universal Sampling,0, 1/NPointer,Local Selection,The first step is the selec
13、tion of the first half of the mating population uniform at random. Inside this neighborhood the mating partner is selected.,Local Selection,Local Selection,Local Selection,Truncation Selection,Be used by breeders for large populations/mass selection Individuals are sorted according to their fitness.
14、 Only the best individuals are selected for parents. The parameter for truncation selection is the truncation threshold.,Truncation Selection,Tournament Selection,Tour : number of individuals be chosen randomly from the population. Nind : number of individuals in population. Tour takes values rangin
15、g from 2 to Nind .,Tournament Selection,5.3 Recombination(Crossover),Discrete Recombination,Can be applied to all variable representations.,Discrete Recombination,Discrete Recombination,individual 1 12 25 5 individual 2 123 4 34 sample 1 2 2 1 sample 2 1 2 1 offspring 1 123 4 5 offspring 2 12 4 5,In
16、termediate Recombination,Intermediate Recombination,Intermediate Recombination,Intermediate Recombination,individual 1 12 25 5 individual 2 123 4 34 sample 1 0.5 1.1 -0.1 sample 2 0.1 0.8 0.5 offspring 1 67.5 1.9 2.1 offspring 2 23.1 8.2 19.5,Line Recombination,Line Recombination,Single-point Rrossover,Multi-point crossover,Multi-point Crossover,C1: 1011|0001|100 C2: 0010|1101|001 C1: 1011|1101|100 C2: 0010|0001|001,Uniform Crossover,掩码交换 父辈1 01100111 父辈211
