ga算法).ppt

* 遗传算法 传统的优化方法（局部优化） 共轭梯度法、拟牛顿法、单纯形方法 全局优化方法 漫步法（Random Walk）、模拟退火法、GA 关于优化问题 比较： 传统的优化方法 ? 1）依赖于初始条件。 2）与求解空间有紧密关系，促使较快地收敛到局部 解，但同时对解域有约束，如可微或连续。利用这些约束，收敛快。 3）有些方法，如Davison-Fletcher-Powell直接依赖于至少一阶导数； 共轭梯度法隐含地依赖于梯度。 全局优化方法 1）不依赖于初始条件； 2）不与求解空间有紧密关系，对解域，无可微或连续的要求。求 解稳健，但收敛速度慢。能获得全局最优。适合于求解空间不知的情况 ⑴ 选择运算 ⑵ 交换操作 ⑶ 变异 遗传算法的基本运算 遗传算法基本原理 模拟自然界优胜劣汰的进化现象，把搜索空间映射为遗传 空间，把可能的解编码成一个向量——染色体，向量的每个 元素称为基因。 通过不断计算各染色体的适应值，选择最好的染色体，获 得最优解。 ●选择运算 ——从旧的种群中选择适应度高的染色体，放入匹配集（缓冲 区），为以后染色体交换、变异，产生新的染色体作准备。 选择方法——适应度比例法（转轮法） 按各染色体适应度大小比例来决定其被选择数目的多少。 某染色体被选的概率：Pc xi 为种群中第i个染色体， 具体步骤 1）计算各染色体适应度值 2）累计所有染色体适应度值，记录中间累加值S - mid 和最 后累加值 sum = ∑f(xi) 3） 产生一个随机数 N，0〈 N 〈 sum 4） 选择对应中间累加值S - mid 的第一个染色体进入交换集 5） 重复（3）和（4），直到获得足够的染色体。 举例： ⒈具有6个染色体的二进制编码、适应度值、Pc累计 值。 染色体的 适应度和所占的比例 用转轮方法进行选择 76 69 66 59 48 36 34 27 10 8 适应度累计 0.09 0.03 0.09 0.14 0.16 0.02 0.09 0.22 0.02 0.1 被选概率 7 3 7 11 12 2 7 17 2 8 适应度 10 9 8 7 6 5 4 3 2 1 染色体编号 7 3 1 3 10 7 3 所选染色体号码 57 27 1 13 76 49 23 随机数 染色体被选的概率 被选的染色体个数 ⒉10个染色体种群按比例的选择过程 ●交换操作 方法:随机选择二个染色体(双亲染色体),随机指定一点或多点, 进行交换,可得二个新的染色体(子辈染色体). 新的子辈染色体: A’ B’ 模拟生物在自然界环境变化,引起基因的突变.在染色体二进制编码中,1变成0;或0变成1.突变产生染色体的多样性,避免进化中早期成熟,陷入局部极值点,突变的概率很低. ●变异 复制不能创新,交换解决染色体的创新 GA的流程 简单遗传算法（GA）的基本参数 ①种群规模 P: 参与进化的染色体总数. ②代沟G: 二代之间不相同的染色体数目,无重叠G = 1; 有重叠 0 G 1 ③选择方法: 转轮法,精英选择法,竞争法. ④交换率: Pc 一般为60~100%. ⑤变异率: Pm 一般为0.1~10% 举例: 变异概率取0.001 初始种群和它的适应度值 染色体的交换操纵 举例： 14 步骤1）编码：确定二进制的位数；组成个体（染色体） 步骤2）选择种群数P 和初始个体，计算适应度值， P = 20； 步骤3）确定选择方法；交换率PC；变异率Pm。 选择方法用竞争法； PC = 0.7, Pm = 0.05 计算结果：① 8代后，f(x,y) =0.998757, ② 41代后，f(x,y) =1.00000, x =3.000290, y =2.999924. ③160次适应度计算，达到最优值。 遗传算法的基本数学问题 一个重要的定理——图式定理 什么叫图式？ ——描述种群中染色体相似性的字符串。 （插入演示） 演示 12 ? （*为通配符） 图式的描述： ⑴ 定义长度?（H)——H左右二端有定义位置之间的距离； ⑵ 图式的阶次(或固定长度)O(H）——H中非*位（有定义位）