sect;94 遗传算法.pptVIP

跳转到第一页 跳转到第一页 §9.4 遗传算法 遗传算法(Genetic Algorithms—GAs)是上个世纪70年代初兴起的一门新兴学科，它是一种基于对生物界自然选择和自然遗传机制的模拟来解决实际问题的高度并行、随机、自适应有哪些信誉好的足球投注网站方法。它主要用在处理最优化问题和机器学习。 模拟进化方法(simulated evolution method) 进化计算方法(evolutionary computation) 遗传算法的发展及特点 遗传算法起源于上世纪60年代(Michigen大学的John Holland)、兴起于70年代，但它的广泛应用始于80年代后期。 第一届遗传算法国际会议于1985年举行 第一本教科书出版于1989年。 遗传算法的特点： (1)有哪些信誉好的足球投注网站效率高( ) (2)有哪些信誉好的足球投注网站具有稳健性(Robust) (3)可有效地避免局部优化( ) (4)适于多变量、非线性优化 (5)有哪些信誉好的足球投注网站具有探索性或启发性(Heuristics) §9.4.1 自然进化与遗传算法 Darwin进化论： 设计精美的生物是从由机遇而存在的、足够简单的、最原始的实体一步一步地进化而来的。在进化过程中，每一步由随机产生的前辈到自身的产生都足够简单。但当你考虑从初始点到最终产物的整个过程的复杂性时，一步一步的演变过程构成的决非是一个纯机遇过程。 演变过程是受到每一步的幸存者所控制的。 大多数生物体是通过自然选择和有性生殖这两个基本过程进行演化的。自然选择决定了群体中哪些个体能够存活并繁殖；有性生殖保证了后代基因中的混合和重组。 遗传算法的基本思想 首先，随机产生进化的原始对象（问题的解），然后这些原始对象经过竞争选择父辈，通过染色体上的基因重组和变异产生新的进化对象，并取代已达寿命年龄的原始对象。产生新的进化对象是给前辈的对象以半随机的变化（基因重组和变异），使新的进化对象更适于生存（更接近真实解）。 遗传算法与遗传学的对应关系 §9.4.2 遗传算法的基本过程 (1)群体的初始化； (2)依据一定的函数对群体中每一个个体进行评价； (3)根据群体中每个个体的评价结果进行选择，确定可参加进化的对象； (4)被选择的对象间基因交换产生下一代群体； (5)对某些基因进行变异操作。 注：(3)又称为利用(exploitation)， (4),(5)两个过程称为开发(exploration)。 开始 群体的初始化 评价 Y N 利用：选择 开发：基因交换 变异操作 结束 结束 ? 基因交换（crossover） (a)单点式，1X；(b)两点式，2X；(c)均匀式，UX；(d)环式 变异（mutation） 举 例 求函数的极大值。 (1)初始化： 参数的表示方式 — 8位二进制串 群体的大小 — Np=30 参数的随机初始化 — 30个8×2的串(数组)赋值 (2)评价： 解码 — 将30个串分别转换为整数并换算为实数, 有时还要对评价值进行调整。 计算评价值 — 将x, y代入上述函数计算函数值。 判断是否结束 — 根据评价值或循环次数判断。 (3)选择： 根据30个串的评价值确定哪些串参与下一步的基因交换和变异操作。评价值高者被选中的可能性大，最终选中的个数为30(Np)。 (4)基因交换： 将30个被选的串随机配对，并由随机数与参数Pc确定是否进行基因交换。 (5)变异： 根据参数Pm确定变异的次数(个数)，再由随机数确定变异的位置(哪一个串的哪一位)。 (6)换代： 新产生的30个串取代原来的串，并转向(2)。 §9.4.3 遗传算法的程序实现 (1) 初始化： 群体的初始化 (2) 评价： 解码 计算评价函数值 (3) 选择： 根据评价值大小选择 (4) 基因交换 (5) 变异 function pop = initialize ( popsize, genelen ) pop = [ ( rand ( popsize, genelen ) 0.5 ) ]; 群体的初始化 popsize：群体的大小，根据复杂度在30~100之间选择； genelen：基因串的长度，等于问题的参数个数乘以每个参数所需要的位数； pop：所产生的群体，大小为popsize×genelen function vars = decode (pop, nvar, maxval, minval) [popsize, genelen] = size (pop); sublen = genelen/nvar; pow_two =