《遗传算法基础.ppt》由会员分享，可在线阅读，更多相关《遗传算法基础.ppt（44页珍藏版）》请在三一办公上搜索。
1、遗传算法基础,遗传算法的产生,50，60年代 Holland 提出遗传算法,60年代中期 Holland的学生J.D.Bagley 提出“遗传算法”一词,70年代 Holland 模式定理 Adaptation in Natural and Artificial Systems发表,Holland的学生De Jong 将遗传算法用于最优化问题 Grefenstette 开发了第一个遗传算法软件,遗传算法的发展,Evolutionary Computation,computational intelligence,遗传算法的生物学基础 生物进化理论与遗传学,达尔文的进化论 达尔文（1858）的自
2、然选择学说包括：1遗传2变异3生存斗争和适者生存遗传学1866孟德尔提出的分离律和自由组合律，奠定了现代遗传学的基础 摩尔根进一步确立了染色体的遗传学说，认为遗传性状是由基因决定,遗传算法的生物学基础,遗传学的基本结论,生物的所有遗传信息都包含在其染色体中,染色体决定了生物的性状染色体是由基因及其由规律的排列所构成.遗传和进化过程发生在染色体上生物的繁殖过程是由基因的复制过程来完成的通过同源染色体间的交叉和变异会产生新的物种,使生物呈现新的性状对环境适应性好的基因或染色体比适应性差的基因或染色体有更多的机会遗传到下一代,遗传算法的生物学基础 生物进化理论与遗传学,现代综合进化论,没有所谓生存斗
3、争的问题，单是个体繁殖机会的差异也能造成后代基因库组成的改变，自然选择也能够进行,生物的进化实际上是种群的进化每一代个体基因型的改变会影响种群基因库的组成种群基因库的进化就是种群的进化,基因库+适者繁殖=群体进化,遗传算法的生物学基础 生物进化理论与遗传学,非达尔文式进化理论 1.分子进化中性理论 2.跳跃进化理论 3.间断平衡进化理论非渐变进化理论的核心基础仍然是自然选择,遗传算法的生物进化模型,现代综合进化论,选择,优胜劣汰,遗传,保持优良特性,变异,产生新特性,遗传算法的基本术语,编码：从问题域到遗传域的映射。即性状与基因的DNA序列的映射 解码：从遗传域到问题域的映射。即将DNA序列解
4、释成个体的性状适应度：种群的某个个体对生存环境的适应程度。适应度高的个体可以获得更多的繁殖机会，而适应度低的个体，其繁殖机会就会比较少，甚至逐渐灭绝 选择：以一定概率从种群中选择若干个体的操作。一般而言，选择就是基于适应度的优胜劣汰的过程 交叉：有性生殖生物在繁殖下一时两个同源染色体之间通过交叉而重组，即在两个染色体的相同位置处DNA被切断，前后两串分别交叉组合形成新的染色体,遗传算法的基本思想,遗传算法的流程图,编码,解码,遗传算法基本要素与实现技术,编码与解码,问题域（解空间）优化变量,遗传域（基因空间）优化变量的代码表示,映射,二进制编码浮点数编码符号编码,编码与解码,二进制编码二进制编
5、码是遗传算法中最常用、最原始的一种编码方法，它将原问题的解空间映射到二进制空间上，然后进行遗传操作。找到最优个体后再通过解码过程还原原始的数据形式进行适应度评价二进制编码的串长度 取决于求解的精度,编码公式,解码公式,编码与解码,浮点编码个体的基因值用某一范围内决策变量的一个浮点数来表示，个体的编码长度等于其决策变量的个数。浮点编码使用的是决策变量的真实值,X:,某个优化问题含有6个变量，则它的一个基因表达为,对应的表现型为 x=2.50,9.54,3.25,0.25,4.25,7.00,编码与解码,符号编码个体基因值取自一个无数值含意，而只有代码含义的符号集。符号集可以是字母，也可以是数字序
6、号。,如血型A，B，AB，O可以分别用a,b,c,d表示，或者a1,a2,a3,a4,也可表示为1，2，3，4,遗传算法基本要素与实现技术,最小与最大的转化个体适应度评价 为正确计算个体的遗传概率，个体的适应度必须为正数或者为零，不能为负数,而目标函数在寻优区间有一下三种状态：,个体适应度评价,F（x）f（x）C,F（x）,F（x）,F（x）,遗传算法基本要素与实现技术,选择算子适应度较高的个体被遗传到下一代群体中的概率较大，适应度较低的个体被遗传到下一代群体中的概率较小。选择方法 比例选择法（轮盘赌）锦标赛选择法,比例选择法（轮盘赌）,基本思想 各个个体被选中的概率与其适应度大小成正比。,设
7、群体大小为，个体 的适应度大小为，则 个体 被选中的概率为,比例选择法（轮盘赌）,具体步骤 1）计算各基因适应度值和选择概率 2）累计所有基因选择概率值，记录中间累 加值S-mid 和最后累加值 sum=3）产生一个随机数 N，0 N 1 4）选择对应中间累加值S-mid 的基因进入交换集 5）重复（3）和（4），直到获得足够的基因。,比例选择法（轮盘赌）,举例,染色体的适应度和所占的比例,锦标赛选择法,基本思想 每次随机选取n个个体，比较之后选择其中适应度最高的个体做为下一代种群的父本,遗传算法基本要素与实现技术,交叉算子 选择是对优秀个体的复制，不能产生新个体，交叉对相互配对的染色体按某种
8、方式相互交换其部分基因，从而形成两个新的个体。交叉操作是产生新个体的主要方法主要问题 如何对染色体进行配对 如果确定交叉点的位置 如何进行部分基因交换,随机配对,将选择出的种群中的M个个体以随即的方式组成M/2对配对个体组，交叉操作就是在这些配对个体组中的两个个体之间进行,二进制编码染色体的交叉,单点交叉 基因位数为，交叉点k的范围为1,-1,在该点为分界相互交换变量,例如：,子个体1 0 1 1 1 0 1 0 0 1 0 1子个体2 1 0 1 0 1 0 1 1 0 1 0,二进制编码染色体的交叉,多点交叉,多点交叉的破坏性可以促进解空间的搜索,二进制编码染色体的交叉,均匀交叉 两个配对
9、个体的染色体每个基因位以相同的交叉概率进行交换具体步骤随机产生一个与个体编码串长度等长的屏蔽字W按下列规则交叉两个父本的基因,若=0，则父代第i个基因相互交换,若=1，则父代第i个基因不相互交换,均匀交叉,例如,浮点编码染色体的交叉,线性交叉,交叉公式,子个体父个体1F(父个体2-父个体1),F为0,1间的均匀分布随机数,浮点编码染色体的交叉,中间交叉,交叉公式,子个体i父个体1iF(父个体2i-父个体1i),遗传算法基本要素与实现技术,变异算子 将个体染色体编码串中的某些基因位编码字符集的其它字符替换二进制编码染色体的变异 编码字符集为0,1,变异操作就是将变异点上的基因取反 变异点是按概率
10、Pm在染色体基因位上指定的,二进制编码染色体的变异,具体步骤随机产生一个与个体编码串长度等长的屏蔽字W 为0,1间的随机数按下列规则对基因进行变异,若 Pm，则父代基因第i位变异,若 Pm，则父代基因第i位不变异,浮点编码染色体的变异,浮点编码变异,遗传算法的数学基础模式定理,模式 定义：种群中的个体即基因串中相同的结构,例如：(以二进制编码为例)假设编码基因串长度为5,模式H1 1*0描述了在基因位1，2取值为“1”，在基因位5取值为“0”的所有个体的集合11000，11010，11100，11110,模式定理,结论1,定义在长度为 的二进制编码基因串上的模式共有,证明：,在长为 的基因串中
11、任选定k位作为模式中的确定位，则这样的模式共有 有二项式定理,模式定理,模式阶 定义：在模式H中具有确定基因值的位置数目称为该模式的模式阶，记为,例如：,基因长度固定时，模式阶越高，能与该模式匹配的样本基因就越少,模式定理,模式定义长度定义：模式H中第一个确定基因值的位置和最后一个确定基因值的位置之间的距离，称为该模式的模式定义长度，记为,例如：,模式定理,引入模式的概念后，我们将遗传算法看作是对模式的一种运算。某一模式H的各个样本经过选择，交叉，变异运算后，得到一些新的样本和新的模式。符号说明假定在给定的时刻t，一个特定的模式H有m个代表串包含在种群 中，记为m(H,t)。种群个体 的适应度
12、为，个体总数记为n，模式H的平均适应度记为，种群的平均适应度为,模式定理,选择算子的作用,若 1，m（H，t）增加若 1，m（H，t）减少,在选择算子的作用下，对于平均适用度高于群体平均适应度的模式，其样本数将增长，对于平均适用度低于群体平均适应度的模式，其样本数将减少,模式定理,交叉算子的作用（单点交叉）,模式H1被破坏的几率大于模式H2,一般地，模式H被破坏的几率小于，考虑到交叉操作是按照交叉概率Pc进行的，所以模式H的生存概率大于,模式定理,变异算子的作用此时若某一模式被破坏，则必然是模式描述形式中的确定位发生了改变，破坏发生概率为 当 有,则模式生存概率为,模式定理,综合选择，交叉，变
13、异操作下，种群中模式H的子代样本数目为结论二：模式定理,遗传算法中，在选择，交叉和变异算子的作用下，具有低阶，短的定义长度，并且平均适应度高于群体平均适应度的模式将逐代增加,遗传算法的数学基础收敛性分析,遗传算法的收敛性定义定义一：种群状态空间 所有可能的种群状态的集合称为种群状态空间，它的元素 代表一个种群，这个种群的个体就用 描述定义二：渐进收敛,若算法在t时刻的种群满足则成算法渐进收敛到,经典的遗传算法不具备渐进收敛性,遗传算法收敛性定义,Markov收敛性 1.有限Markov链的基本知识,设随机过程 只能取可列值，并且满足条件：对任意t,如果,必有 则称 为时间离散状态离散的Markov链,
