遗传算法2011课件.ppt

遗传算法原理与应用
赵 鹏
******@
1
精选可编辑ppt

《自然界和人工系统的适应性》中首先提出的，它是一类借鉴生物界自然选择和自然遗传机制的随机化搜索算法。
一、基本原理
2
精选可编辑ppt
生物进化循环图
3
精选可编辑ppt
生物遗传概念在遗传算法中的对应关系
生物遗传概念
遗传算法中的作用
适者生存
在算法停止时，最优目标值的解有最大的可能被保留
个体(individual)
解
染色体(chromosome)
解的编码（字符串，向量等）
基因(gene)
解中每一分量的特征（如各分量的值）
适应性(fitness)
适应函数值
群体(population)
选定的一组解（其中解的个数为群体的规模）
种群(reproduction)
根据适应函数值选取的一组解
交配(crossover)
通过交配原则产生一组新解的过程
变异(mutation)
编码的某一个分量发生变化的过程
4
精选可编辑ppt
遗传算法的主要特征：
进化发生在解的编码上，这些编码按生物学的术语称为染色体。由于对解进行了编码，优化问题的一切性质都通过编码来研究。编码和解码是遗传算法的一个主题。
自然选择规律决定哪些染色体产生超过平均数的后代。遗传算法中，通过优化问题的目标而人为地构造适应函数以达到好的染色体产生超过平均数的后代。
当染色体结合时，双亲的遗传基因的结合使得子女保持父母的特征。
当染色体结合后，随机的变异会造成子代同父代的不同。
5
精选可编辑ppt
遗传算法主要处理步骤
首先是对优化问题的解进行编码，称一个解的编码为一个染色体，组成编码的元素称为基因。编码的目的主要是用于优化问题解的表现形式和利于之后遗传算法中的计算。
第二是适应函数的构造和应用。适应函数基本上依据优化问题的目标函数而定。当适应函数确定以后，自然选择规律是以适应函数值的大小决定的概率分布来确定哪些染色体适应生存，哪些被淘汰。生存下来的染色体组成种群，形成一个可以繁衍下一代的群体。
第三是染色体的结合。双亲的遗传基因结合是通过编码之间的交配达到下一代的产生。新一代的产生是一个生殖过程，它产生了一个新解。
最后是变异。新解产生过程中可能发生基因变异，变异使某些解的编码发生变化，使解有更大的遍历性。
6
精选可编辑ppt
2、基本遗传算法
基本遗传算法（Simple Genetic Algorithms，简称SGA，又称简单遗传算法或标准遗传算法），是由Goldberg总结出的一种最基本的遗传算法，其遗传进化操作过程简单，容易理解，是其它一些遗传算法的雏形和基础。
基本遗传算法的组成
（1）编码（产生初始种群）
（2）适应度函数
（3）遗传算子（选择、交叉、变异）
（4）运行参数
7
精选可编辑ppt
函数优化示例
求下列一元函数的最大值：
x∈[-1,2] ，求解结果精确到6位小数。
GA是通过某种编码机制把对象抽象为由特定符号按一定顺序排成的串。正如研究生物遗传是从染色体着手，而染色体则是由基因排成的串。SGA使用二进制串进行编码。
编码
8
精选可编辑ppt
SGA对于本例的编码
由于区间长度为3，求解结果精确到6位小数，因此可将自变量定义区间划分为3×106等份。又因为221 < 3×106 < 222 ，所以本例的二进制编码长度至少需要22位，本例的编码过程实质上是将区间[-1，2]内对应的实数值转化为一个二进制串（b21b20…b0）。
9
精选可编辑ppt
几个术语
基因型：10001011101**********
表现型：
编码
解码
个体（染色体）
基因
10
精选可编辑ppt