遗传算法2010.ppt

1、遗传算法,Genetic Algorithm,丁建立 中国民航大学计算机学院,遗传算法（GA）,早在50年代，一些生物学家开始研究运用数字计算机模拟生物的自然遗传与自然进化过程； 60年代中期，美国Michigan大学的J. H. Holland教授提出借鉴生物自然遗传的基本原理用于自然和人工系统的自适应行为研究和串编码技术； 1967年，他的学生J. D. Bagley在博士论文中首次提出“遗传算法(Genetic Algorithms)”一词； 1975年，Holland出版了著名的 “Adaptation in Natural and Artificial Systems”，标志遗传算法

2、的诞生。,遗传算法（GA）,遗传算法是一种抽象于生物进化过程的基于自然选择和生物遗传机制的优化技术。 以达尔文的生物进化论“适者生存、优胜劣汰” 以孟德尔的遗传变异理论 模拟生物界进化过程。,遗传算法（GA）,达尔文的自然选择说 遗传（heredity）：子代和父代具有相同或相似的性状，保证物种的稳定性； 变异（variation）：子代与父代，子代不同个体之间总有差异，是生命多样性的根源； 生存斗争和适者生存：具有适应性变异的个体被保留，不具适应性变异的个体被淘汰。然选择过程是长期的、缓慢的、连续的过程。,遗传算法（GA）,生物进化循环图,遗传算法（GA）,孟德尔的遗传变异理论 生物遗传进化

3、主要在染色体上，子代是父代遗传基因在染色体上的有序排列.,遗传算法（GA）,遗传算法的基本原理,遗传算法（GA）,遗传算法的基本原理,遗传算法（GA）,基本概念 初始种群：原始个体的集合。 编码：问题参数按某种形式编制的代码。 染色体：编码后的串。也叫个体。 基因：染色体编码中的位。 适应度：个体适应环境的能力，常用适应度函数值表示，是区分群体中个体优劣的标准。 遗传算子：产生新一代群体方法。有选择、交叉和变异。 复制：通过遗传算子，选择适应值高的作为下一代。,遗传算法（GA）,遗传算法的基本思路,种群 # 位串 适应值 排序 1011011011 38.3 3 1100011100 43.7

4、 2 0111010101 54.5 1 0110010010 34.6 4,交叉位 1100011100 0111010101,变异位 1100010101 0111011100,新后代 1100010101 0111001100,选择,交叉,变异,新后代,遗传算法（GA）,遗传算法的基本操作 选择 适应度计算： 按比例的适应度函数（proportional fitness assignment） 基于排序的适应度计算（Rank-based fitness assignment） 选择算法： 轮盘赌选择（roulette wheel selection） 随机遍历抽样（stochastic

5、universal selection） 局部选择（local selection） 截断选择（truncation selection） 锦标赛选择（tournament selection）,遗传算法（GA）,遗传算法的基本操作 交叉或基因重组 二进制交叉（binary valued crossover）： 单点交叉（single-point crossover） 多点交叉（multiple-point crossover） 均匀交叉（uniform crossover） 洗牌交叉（shuffle crossover） 变异 实值变异 二进制变异,遗传算法（GA）,位交叉 随机选择一对个体

6、的一个或多个位进行基因互换。以TSP为例，交叉操作如下图：,R1=011001101110111100010110 R2=110011010001011100110001,R3=011011101101111100010010 R4=110001010010011100110101,遗传算法（GA）,R1=011|001|101|110|111|100|010|110 R2=110|011|010|001|011|100|110|001,R3=011|001|010|110|111|100|010|001 R4=110|011|101|001|011|100|110|110, 段交叉 将一个个

7、体中的一段与另一个体相应段互换。,遗传算法（GA）, 部分匹配交叉 两个染色体互换一个基因段，并将染色体其他段中与交换段中相同的基因反交换为被交换段中相应位的基因。示例如下：,遗传算法（GA）,至下一代，适应度计算选择交叉变异，直至满足终止条件。,特点：具有大范围全局搜索的能力，潜在的并行性、随机性，鲁棒性强，过程简单。缺点是不能很好的利用系统反馈信息，冗余迭代多，影响求优化解效率。,适应度函数 GA淘汰个体的原则是适应能力的强弱。个体的适应能力以适应度函数f(x)的值来判别的，这个值称为适应值（fitness）。 f(x)的构成与目标函数有关，往往是目标函数的变种。 适应度函数的处理有：目标

8、函数的确定、目标函数到适应度函数的映射、适应值调整等。,遗传算法（GA）,终止条件,终止条件是指決定何时终止遗传算法，并以运算过程中所获最佳解作为此次运算之解，一般而言，遗传算法之终止条件有以下几种： （1）已达最大的演化代数。 （2）所求之解已达可接受之范围。 （3）连续几代间的最佳解变化非常微小或无改变。 （4）已达最大的运算时间。 （5） 设定算法达到迭代次数即停止。 （6） 当符合设定范围时，运算即停止。这种方法的条件不可超国最优解，否則运算便永远无法停止。,GA的流程,遗传算法（GA）,遗传算法的基本操作 简单实例 产生初始种群 计算适应度,0001100000 0101111001

9、 0000000101 1001110100 1010101010 1110010110 1001011011 1100000001 1001110100 0001010011,（8） （5） （2） （10） （7） （12） （5） （19） （10） （14）,遗传算法（GA）,简单实例 选择,0.086957,0.054348,0.021739 0.108696 0.076087 0.130435 0.054348 0.206522 0.108696 0.152174,遗传算法（GA）,简单实例 选择,0.086957,0.054348,0.021739 0.108696 0.0760

10、87 0.130435 0.054348 0.206522 0.108696 0.152174,0.086957,0.141304,0.163043,0.271739 0.347826 0.478261 0.532609 0.739130 0.847826 1.000000,遗传算法（GA）,0001100000 1110010110 1100000001 1001110100 1010101010 1110010110 1001011011 1100000001 1001110100 0001010011,简单实例 交叉,0001100000 1110010110 1100000001 10

11、01110100 1010101010 1110010110 1001011011 1001110100 1100000001 0001010011,0001,1110,100000,010110,111,100,0010110,1011011,110000,100111,0100,0001,1001110100,1100000001,1010101,0001010,010,011,遗传算法（GA）,简单实例 变异,染色体的 适应度和所占的比例,用转轮方法进行选择,遗传算法（GA）,染色体被选的概率,被选的染色体个数,10个染色体种群按比例的选择过程,简单遗传算法（GA）的基本参数,种群规模

12、P: 参与进化的染色体总数. 代沟G: 二代之间不相同的染色体数目,无重叠G = 1; 有重叠 0 G 1 选择方法: 转轮法,精英选择法,竞争法. 交换率: Pc 一般为60100%. 变异率: Pm 一般为0.110%,举例:,变异概率取0.001,染色体的交叉操作,初始种群和它的适应度值,举例：,步骤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次适应度计算，达到最优值。, 高级GA算法,1）操作的改进,2）算法的改进,选择方法改进：精英法（竞赛法）、置换式和非置换式 随机选择法，排序法。,交换方法的改进：多点交换；重组运算,微种群遗传算法（GA）,双种群遗传