遗传算法PPT课件

遗传算法GeneticAlgorithm组织结构王海军（数学与统计学院）2遗传算法1.生物原型2.理论模型3.算法示例生物原型王海军（数学与统计学院）遗传算法3CharlesDarwin，英，1809—1882《物种起源》，1859观点：物竞天择，适者生存进化—交叉(crossover)王海军（数学与统计学院）遗传算法4染色体1染色体2染色体1’染色体2’进化—变异(mutation)王海军（数学与统计学院）遗传算法5染色体1染色体1’进化—选择(selection)遗传算法6第i代第i+1代理论模型遗传算法7JohnHolland，美，1929—《自然与人工系统中的适应》，1975简单遗传算法(SGA)智能是自然界进化的某种延伸SGA思路人工模拟适者生存遗传算法8SGA—编码与解码•编码(Encoding)：将问题解的结构转化为计算机可处理的类似生物染色体的位串形式。•解码(Decoding)：编码过程的反过程。遗传算法9exampleMaxF(x)=x2Subjectto::0≤x≤27,x∈IntegerXXcode500101编码解码SGA—相关概念•染色体(chromosome)：问题的一个可行（候选）解的编码形式。遗传算法10SGA—相关概念•染色体(chromosome)：问题的一个可行（候选）解的编码形式。•种群(Population)：染色体的集合。遗传算法基于种群进行“进化”。遗传算法11SGA—相关概念•染色体(chromosome)：问题的一个可行（候选）解的编码形式。•种群(Population)：染色体的集合。遗传算法基于种群进行“进化”。•适应度函数(FitnessFunction)：染色体适应问题环境的度量。适应度越大，越符合问题要求。遗传算法12SGA—交叉(crossover)•典型的交叉概率Pc∈(0.6,0.9)遗传算法13SGA—交叉(crossover)•典型的交叉概率Pc∈(0.6,0.9)xF(x)遗传算法1400110525245761522521441110000111110110随机选择配对001105252457611000xF(x)随机选择交叉点SGA—交叉(crossover)•典型的交叉概率Pc∈(0.6,0.9)xF(x)遗传算法15001105252457615225214410111110110随机选择配对001105252457611000xF(x)1100041625625SGA—交叉(crossover)•典型的交叉概率Pc∈(0.6,0.9)xF(x)遗传算法161522521441随机选择配对001004162562511010xF(x)5250011001111101102457611000SGA—变异(mutation)•以概率Pm对染色体的每一位独立进行异向转化•典型的Pm介于(popsize)-1和(chrosize)-1之间遗传算法1715225214414160010001111101102562511010xF(x)2144110110xF(x)SGA—变异(mutation)•以概率Pm对染色体的每一位独立进行异向转化•典型的Pm介于(popsize)-1和(chrosize)-1之间遗传算法181522541600100011112562511010xF(x)2352910111xF(x)2144110110SGA—选择(selection)•原则：更好的染色体有更多的机会•方法：轮盘赌等方法遗传算法19SGA—选择(selection)•原则：更好的染色体有更多的机会•方法：轮盘赌等方法遗传算法20染色体适应度选择率累积概率A160.010.00~0.01B2250.160.01~0.17C5290.380.17~0.55D6250.450.55~1.00∑13951.00轮盘赌模型与实现遗传算法21染色体选择率累积概率A0.010.00~0.01B0.160.01~0.17C0.380.17~0.55D0.450.55~1.00∑1.00SGA流程遗传算法22满足终止条件？开始初始化种群计算适应度依次进行交叉、变异和选择操作计算适应度结束否是遗传算法23谢谢！