遗传算法GeneticAlgorithm课件

1、遗 传 算 法Genetic Algorithm,王海军 （数学与统计学院）,遗传算法,2,组织结构,1. 生物原型,2. 理论模型,3. 算法示例,王海军 （数学与统计学院）,遗传算法,3,生物原型,Charles Darwin， 英，18091882,物种起源，1859,观点：物竞天择，适者生存,王海军 （数学与统计学院）,遗传算法,4,进化交叉(crossover),染色体1,染色体2,染色体1,染色体2,王海军 （数学与统计学院）,遗传算法,5,进化变异(mutation),染色体1,染色体1,遗传算法,6,进化选择(selection),第i代,第i+1代,遗传算法,7,理论模型,J

2、ohn Holland，美，1929,自然与人工系统中的适应，1975,简单遗传算法(SGA),智能是自然界进化的某种延伸,遗传算法,8,SGA思路,人工模拟适者生存,遗传算法,9,SGA编码与解码,编码(Encoding)：将问题解的结构转化为计算机可处理的类似生物染色体的位串形式。 解码(Decoding)：编码过程的反过程。,遗传算法,10,SGA相关概念,染色体(chromosome)：问题的一个可行（候选）解的编码形式。,遗传算法,11,SGA相关概念,染色体(chromosome)：问题的一个可行（候选）解的编码形式。 种群(Population)：染色体的集合。遗传算法基于种群进

3、行“进化”。,遗传算法,12,SGA相关概念,染色体(chromosome)：问题的一个可行（候选）解的编码形式。 种群(Population)：染色体的集合。遗传算法基于种群进行“进化”。 适应度函数(Fitness Function)：染色体适应问题环境的度量。适应度越大，越符合问题要求。,遗传算法,13,SGA交叉(crossover),典型的交叉概率Pc (0.6, 0.9),遗传算法,14,SGA交叉(crossover),典型的交叉概率Pc (0.6, 0.9) x F(x),5,25,24,576,15,225,21,441,随 机 选 择 配 对,遗传算法,15,SGA交叉(c

4、rossover),典型的交叉概率Pc (0.6, 0.9) x F(x),5,25,24,576,15,225,21,441,随 机 选 择 配 对,x F(x),遗传算法,16,SGA交叉(crossover),典型的交叉概率Pc (0.6, 0.9) x F(x),15,225,21,441,x F(x),遗传算法,17,SGA变异(mutation),以概率Pm对染色体的每一位独立进行异向转化 典型的Pm 介于(popsize)-1和 (chrosize)-1之间,遗传算法,18,SGA变异(mutation),以概率Pm对染色体的每一位独立进行异向转化 典型的Pm 介于(popsize)-1和 (chrosize)-1之间,15,225,x F(x),x F(x),遗传算法,19,SGA选择(selection),原则：更好的染色体有更多的机会 方法：轮盘赌等方法,遗传算法,20,SGA选择(selection),原则：更好的染色体有更多的机会 方法：轮盘赌等方法,遗传算法,21,轮盘赌模型与实现,遗传算法,2