文档介绍：遗传算法传统的优化方法(局部优化) 共轭梯度法、拟牛顿法、单纯形方法全局优化方法漫步法( Random Walk )、模拟退火法、 GA 关于优化问题比较: 传统的优化方法 1)依赖于初始条件。 2 )与求解空间有紧密关系,促使较快地收敛到局部解,但同时对解域有约束,如可微或连续。利用这些约束,收敛快。 3 )有些方法,如 Davison-Fletcher-Powell 直接依赖于至少一阶导数; 共轭梯度法隐含地依赖于梯度。全局优化方法 1)不依赖于初始条件; 2)不与求解空间有紧密关系,对解域,无可微或连续的要求。求解稳健,但收敛速度慢。能获得全局最优。适合于求解空间不知的情况⑴选择运算⑵交换操作⑶变异遗传算法的基本运算遗传算法基本原理模拟自然界优胜劣汰的进化现象,把搜索空间映射为遗传空间,把可能的解编码成一个向量——染色体,向量的每个元素称为基因。通过不断计算各染色体的适应值,选择最好的染色体,获得最优解。●选择运算——从旧的种群中选择适应度高的染色体,放入匹配集(缓冲区),为以后染色体交换、变异,产生新的染色体作准备。选择方法——适应度比例法(转轮法) 按各染色体适应度大小比例来决定其被选择数目的多少。某染色体被选的概率: P c??)( )( i icxf xfPx i 为种群中第 i个染色体, 具体步骤 1)计算各染色体适应度值 2)累计所有染色体适应度值,记录中间累加值 S - mid 和最后累加值 sum = ∑ f(x i)3)产生一个随机数 N,0〈 N 〈 sum 4)选择对应中间累加值 S - mid 的第一个染色体进入交换集 5)重复( 3)和( 4),直到获得足够的染色体。举例: ⒈具有 6个染色体的二进制编码、适应度值、 P c累计值。染色体的适应度和所占的比例用转轮方法进行选择 76 69 66 59 48 36 34 27 10 8 适应度累计被选概率 7 3711 12 2 717 2 8 适应度10 9 8 7 6 5 43 2 1 染色体编号 7 3 1 310 7 3 所选染色体号码57 27 113 76 49 23 随机数染色体被选的概率被选的染色体个数⒉10个染色体种群按比例的选择过程●交换操作方法:随机选择二个染色体(双亲染色体),随机指定一点或多点, 进行交换,可得二个新的染色体(子辈染色体). 新的子辈染色体: A ’ 11010001 B’ 01011110 模拟生物在自然界环境变化,,1变成 0;或0变成 ,避免进化中早期成熟,陷入局部极值点, 突变的概率很低. ●变异复制不能创新,交换解决染色体的创新 GA的流程简单遗传算法( GA )的基本参数①种群规模 P: 参与进化的染色体总数. ②代沟 G: 二代之间不相同的染色体数目,无重叠 G = 1; 有重叠 0 < G <1 ③选择方法: 转轮法,精英选择法,竞争法. ④交换率: P c 一般为 60~100%. ⑤变异率: P m 一般为 ~10% 举例:变异概率取