经典遗传算法原理与应用

1、遗传算法原理与应用SN:SNO:主要内容遗传算法基本原理2遗传算法概述1 遗传算法的应用及一些问题31、优化方法遗传算法概述传统的优化方法局部优化 共轭梯度法、拟牛顿法、单纯形方法全局优化方法 GA、漫步法Random Walk、模拟退火法 2、遗传算法优点 遗传算法GA模拟自然选择和自然遗传过程中发生的繁殖、交叉和基因突变现象，在每次迭代中都保存一组候选解，并按某种指标从解群中选取较优的个体，利用遗传算子(选择、交叉和变异)对这些个体进行组合，产生新一代的候选解群，重复此过程，直到满足某种收敛指标为止。其遗传进化操作过程简单，容易理解。 遗传算法根本原理1、根本思想 模拟自然界优胜劣汰的进化

2、现象，把搜索空间映射为遗传空间，把可能的解编码成一个向量染色体，向量的每个元素称为基因。 通过不断计算各染色体的适应值，选择最好的染色体，获得最优解。2、遗传算法的根本运算 选择运算 交换操作 变异选择运算 从旧的种群中选择适应度高的染色体，放入匹配集缓冲区，为以后染色体交换、变异，产生新的染色体作准备。选择方法适应度比例法转轮法某染色体被选的概率：Pcxi 为种群中第i个染色体，f(xi )为第i个染色体的适应度值。具体步骤1计算各染色体适应度值2累计所有染色体适应度值，记录中间累加值S - mid 和最后累加值 sum = f(xi)3产生一个随机数 N，0 N sum4选择对应中间累加值

3、S - mid 的第一个染色体进入交换集5 重复3和4，直到获得足够的染色体。举例：具有6个染色体的二进制编码、适应度值、Pc累计值。 染色体的适应度和所占的比例用转轮方法进行选择染色体被选的概率染色体编号 1 2 3 4 5 6 7 8 910适应度 8 217 7 212117 3 7被选概率0.10.020.220.090.020.160.140.090.030.09适应度累计 8 10 27 34 36485966 6976被选的染色体个数随机数23497613 1 2757所选染色体号码 3 710 3 1 3 7交换操作 方法:随机选择二个染色体(双亲染色体),随机指定一点或多点,

4、 进行交换,可得二个新的染色体(子辈染色体).新的子辈染色体: A 11010001 B 01011110变异 模拟生物在自然界环境变化,引起基因的突变.在染色体二进制编码中,1变成0;或0变成1.突变产生染色体的多样性,防止进化中早期成熟,陷入局部极值点,突变的概率很低.GA流程简单遗传算法GA的根本参数种群规模 P: 参与进化的染色体总数.代沟G: 二代之间不相同的染色体数目,无重叠G = 1;有重叠 0 G 1选择方法: 转轮法,精英选择法,竞争法.交换率: Pc 一般为60100%.变异率: Pm 一般为0.110%实例1、产生初始种群0001100000 0101111001 000

5、0000101 1001110100 10101010108 5 2 10 7 1110010110 1001011011 1100000001 1001110100 000101001 12 5 19 10 142、计算适应度3、选择个体染色体适应度选择概率累积概率100011000008201011110015300000001012410011101001051010101010761110010110127100101101158110000000119910011101001010000101001114885210712519101458521071251910143、选择个体染色

6、体适应度选择概率累积概率1000110000082010111100153000000010124100111010010510101010107611100101101271001011011581100000001199100111010010100001010011143、选择在01之间产生一个随机数：个体染色体适应度选择概率累积概率100011000008201011110015300000001012410011101001051010101010761110010110127100101101158110000000119910011101001010000101001114淘淘汰

7、4、交叉 0001100000 1110010110 1100000001 1001110100 10101010101110010110 1001011011 1001110100 1100000001 00010100110001100000 1110010110 1100000001 1001110100 00011110100000010110111100001011010110111100001001110100000110011101001100000001101010100010100100115、变异0001100000 1110010110 1100000001 100111

8、0100 10101010101110010110 1001011011 1100000001 1001110100 000101001100011110100000010110111100001011010110111100001001110100000110011101001100000001101010100010100100110001100000 1110010110 1100000001 1001110100 10101010101110010110 1001011011 1100000001 1001110100 000101001100011110100000010110111100001011010110111100001001010100000110011101001100000001101010100010100100116、至下一代，适应度计算选择交叉变异，直至满足终止条件。遗传算法的应用及一些问题1、遗传算法的应用领域1组合优化 2函数优化 3自动控制 4生产调度 5图像处理 6机器学习 7人工生命 8数据挖掘 2、遗传算法在应用中的一些问题1知识的编