遗传算法 关于优化问题 传统的优化方法(局部优化) 共轭梯度法、拟牛顿法、单纯形方法 全局优化方法 漫步法( Random walk)、模拟退火法、GA 比较:传统的优化方法 1)依赖于初始条件。 2)与求解空间有紧密关系,促使较快地收敛到局部 解,但同时对解域有约束,如可微或连续。利用 这些约束,收敛快。 3)有些方法,如 Davison- Fletcher-Powe接依赖 于至少一阶导数;共轭梯度法隐含地依赖于梯度
遗传算法 传统的优化方法（局部优化） 共轭梯度法、拟牛顿法、单纯形方法 全局优化方法 漫步法（Random Walk）、模拟退火法、GA 关于优化问题 比较：传统的优化方法 1）依赖于初始条件。 2）与求解空间有紧密关系，促使较快地收敛到局部 解，但同时对解域有约束，如可微或连续。利用 这些约束，收敛快。 3）有些方法，如Davison-Fletcher-Powell直接依赖 于至少一阶导数； 共轭梯度法隐含地依赖于梯度
全局优化方法 1)不依赖于初始条件; 2)不与求解空间有紧密关系,对解域,无可微或连 续的要求。求解稳健,但收敛速度慢。能获得全 局最优。适合于求解空间不知的情况
全局优化方法 1）不依赖于初始条件； 2）不与求解空间有紧密关系，对解域，无可微或连 续的要求。求 解稳健，但收敛速度慢。能获得全 局最优。适合于求解空间不知的情况
遗传算法基本原理 模拟自然界优胜劣汰的进化现象,把搜索空间映射为遗传 空间,把可能的解编码成一个向量—染色体,向量的每个 元素称为基因。 通过不断计算各染色体的适应值,选择最好的染色体,获 得最优解。 遗传算法的基本运算 (1)选择运算 (2)交换操作 (3)变异
⑴ 选择运算 ⑵ 交换操作 ⑶ 变异 遗传算法的基本运算 遗传算法基本原理 模拟自然界优胜劣汰的进化现象，把搜索空间映射为遗传 空间，把可能的解编码成一个向量——染色体，向量的每个 元素称为基因。 通过不断计算各染色体的适应值，选择最好的染色体，获 得最优解
●选择运算 从旧的种群中选择适应度高的染色体,放入匹配集(缓冲 区),为以后染色体交换、变异,产生新的染色体作准备。 选择方法—适应度比例法(转轮法) 按各染色体适应度大小比例来决定其被选择数目的多少。 某染色体被选的概率:P。 p=f(xi) f(x1) x;为种群中第个染色体 f(x)第个染色体的适应度值 ∑f(x)种群中所有染色休适应度值之和
●选择运算 ——从旧的种群中选择适应度高的染色体，放入匹配集（缓冲 区），为以后染色体交换、变异，产生新的染色体作准备。 选择方法——适应度比例法（转轮法） 按各染色体适应度大小比例来决定其被选择数目的多少。 某染色体被选的概率：Pc = ( ) ( ) i i c f x f x P xi 为种群中第i个染色体
具体步骤 )计算各染色体适应度值 2)累计所有染色体适应度值,记录中间累加值S-md和最 后累加值sum=∑x) 3)产生一个随机数N,0(N(sm 4)选择对应中间累加值S-mid的第一个染色体进入交换集 5)重复(3)和(4),直到获得足够的染色体。 举例 1.具有6个染色体的二进制编码、适应度值、P累计 值
具体步骤 1）计算各染色体适应度值 2）累计所有染色体适应度值，记录中间累加值S - mid 和最 后累加值 sum = ∑f(xi ) 3） 产生一个随机数 N，0〈 N 〈 sum 4） 选择对应中间累加值S - mid 的第一个染色体进入交换集 5） 重复（3）和（4），直到获得足够的染色体。 举例： ⒈具有6个染色体的二进制编码、适应度值、Pc累计 值
染色体的适应度和所占的比例 序号染色体适应度值所占比例|累计 0l110 8 16 8 11000 15 30 23 2345 00100 25 10010 10 30 01100 12 24 42 用转轮方法进行选择6001 50
染色体的 适应度和所占的比例 用转轮方法进行选择
2.10个染色体种群按比例的选择过程 染色体被选的概率 染色体编号1 345678910 适应度 22 17721211737 被选概率0102|022009002016014090300 适应度累计8 02734364859666976 被选的染色体个数 随机数2349761312757 所选染色 体号码 37 3137
染色体编号 1 2 3 4 5 6 7 8 9 10 适应度 8 2 17 7 2 12 11 7 3 7 被选概率 0.1 0.02 0.22 0.09 0.02 0.16 0.14 0.09 0.03 0.09 适应度累计 8 10 27 34 36 48 59 66 69 76 随机数 23 49 76 13 1 27 57 所选染色 体号码 3 7 10 3 1 3 7 染色体被选的概率 被选的染色体个数 ⒉10个染色体种群按比例的选择过程
●交换操作 复制不能创新交换解决染色体的创新 方法随机选择二个染色体(双亲染色体)随机指定一点或多 点,进行交换可得二个新的染色体(子辈染色体 双亲染色体:染色体A11010110 交换点 染色体B01011001 新的子辈染色体:A11010001 B01011110 ●变异 模拟生物在自然界环境变化引起基因的突变在染 色体二进制编码中,1变成0,或0变成1.突变产生染色 体的多样性避免进化中早期成熟,陷入局部极值点, 突变的概率很低
●交换操作 方法:随机选择二个染色体(双亲染色体),随机指定一点或多 点, 进行交换,可得二个新的染色体(子辈染色体). 新的子辈染色体: A’ 11010001 B’ 01011110 模拟生物在自然界环境变化,引起基因的突变.在染 色体二进制编码中,1变成0;或0变成1.突变产生染色 体的多样性,避免进化中早期成熟,陷入局部极值点, 突变的概率很低. ●变异 复制不能创新,交换解决染色体的创新
GA的流程 问题的初始(候选)解 编码成染色体(向量) 确定种群P(t) 计算各染色体的适应度 复制 种群P(t种群P(t+1) 交换 通过遗传运算存优去劣 变异 种群P(t1 种群满足预定指标 解码染色体 问题解答空间
GA的流程
简单遗传算法(GA)的基本参数 ①种群规模P:参与进化的染色体总数 ②代沟G:二代之间不相同的染色体数目,无重叠G=1 有重叠0<G<1 ③选择方法:转轮法精英选择法,竞争法 ④交换率P一般为60~100% ⑤变异率:Pn-般为0.1~10% 举例设函数f(x)=x求其在区间國31的最大值 变异概率取0.001
简单遗传算法（GA）的基本参数 ①种群规模 P: 参与进化的染色体总数. ②代沟G: 二代之间不相同的染色体数目,无重叠G = 1; 有重叠 0 < G <1 ③选择方法: 转轮法,精英选择法,竞争法. ④交换率: Pc 一般为60~100%. ⑤变异率: Pm 一般为0.1~10% 举例: 变异概率取0.001