遗传算法(GeneticAlgorithm)教学课件

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

2、传算法(SGA)智能是自然界进化的某种延伸SGA思路人工模拟适者生存遗传算法8SGA编码与解码编码(Encoding)：将问题解的结构转化为计算机可处理的类似生物染色体的位串形式。解码(Decoding)：编码过程的反过程。遗传算法9 exampleMax F(x) = x2Subject to: : 0 x 27, xInteger X Xcode 5 00101编码解码SGA相关概念染色体(chromosome)：问题的一个可行（候选）解的编码形式。遗传算法10SGA相关概念染色体(chromosome)：问题的一个可行（候选）解的编码形式。种群(Population)：染色体的集合。遗传

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

4、57611000 x F(x)随机选择交叉点SGA交叉(crossover)典型的交叉概率Pc (0.6, 0.9) x F(x) 遗传算法15001105252457615225214410111110110随机选择配对001105252457611000 x F(x)1100041625625SGA交叉(crossover)典型的交叉概率Pc (0.6, 0.9) x F(x) 遗传算法161522521441随机选择配对001004162562511010 x F(x)5250011001111101102457611000SGA变异(mutation)以概率Pm对染色体的每一位独立进行

5、异向转化典型的Pm 介于(popsize)-1和 (chrosize)-1之间 遗传算法1715225214414160010001111101102562511010 x F(x)2144110110 x F(x)SGA变异(mutation)以概率Pm对染色体的每一位独立进行异向转化典型的Pm 介于(popsize)-1和 (chrosize)-1之间 遗传算法181522541600100011112562511010 x F(x)2352910111x F(x)2144110110SGA选择(selection)原则：更好的染色体有更多的机会方法：轮盘赌等方法遗传算法19SGA选择(selection)原则：更好的染色体有更多的机会方法：轮盘赌等方法遗传算法20染色体适应度选择率累积概率A160.010.00 0.01B2250.160.01 0.17C5290.380.17 0.55D6250.450.55 1.0013951.00轮盘赌模型与实现遗传算法21染色体选择率累积概率A0.010.00 0.01B0.160.01 0.17C0.380