遗传算法基础幻灯片.ppt

《遗传算法基础幻灯片.ppt》由会员分享，可在线阅读，更多相关《遗传算法基础幻灯片.ppt（44页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、遗传算法基础第1页，共44页，编辑于2022年，星期三遗传算法的产生遗传算法的产生 50，60年代 Holland 提出遗传算法 60年代中期 Holland的学生J.D.Bagley 提出“遗传算法”一词 70年代 Holland 模式定理 Adaptation in Natural and Artificial Systems发表Holland的学生De Jong 将遗传算法用于最优化问题 Grefenstette 开发了第一个遗传算法软件 第2页，共44页，编辑于2022年，星期三遗传算法的发展遗传算法的发展 Evolutionary Computationcomputational i

2、ntelligence 第3页，共44页，编辑于2022年，星期三遗传算法的生物学基础 生物进化理论与遗传学 达尔文的进化论 达尔文（1858）的自然选择学说包括：1遗传2变异3生存斗争和适者生存遗传学1866孟德尔提出的分离律和自由组合律，奠定了现代遗传学的基础 摩尔根进一步确立了染色体的遗传学说，认为遗传性状是由基因决定第4页，共44页，编辑于2022年，星期三遗传算法的生物学基础遗传学的基本结论生物的所有遗传信息都包含在其染色体中,染色体决定了生物的性状染色体是由基因及其由规律的排列所构成.遗传和进化过程发生在染色体上生物的繁殖过程是由基因的复制过程来完成的通过同源染色体间的交叉和变异会

3、产生新的物种,使生物呈现新的性状对环境适应性好的基因或染色体比适应性差的基因或染色体有更多的机会遗传到下一代第5页，共44页，编辑于2022年，星期三遗传算法的生物学基础 生物进化理论与遗传学现代综合进化论 没有所谓生存斗争的问题，单是个体繁殖机会的差异也没有所谓生存斗争的问题，单是个体繁殖机会的差异也能造成后代基因库组成的改变，自然选择也能够进行能造成后代基因库组成的改变，自然选择也能够进行生物的进化实际上是种群的进化每一代个体基因型的改变会影响种群基因库的组成种群基因库的进化就是种群的进化基因库+适者繁殖=群体进化第6页，共44页，编辑于2022年，星期三遗传算法的生物学基础 生物进化理论

4、与遗传学非达尔文式进化理论 1.分子进化中性理论 2.跳跃进化理论 3.间断平衡进化理论非渐变进化理论的核心基础仍然是自然选择第7页，共44页，编辑于2022年，星期三遗传算法的生物进化模型现代综合进化论选择优胜劣汰遗传保持优良特性变异产生新特性第8页，共44页，编辑于2022年，星期三遗传算法的基本术语编码：从问题域到遗传域的映射。即性状与基因的DNA序列的映射 解码：从遗传域到问题域的映射。即将DNA序列解释成个体的性状适应度：种群的某个个体对生存环境的适应程度。适应度高的个体可以获得更多的繁殖机会，而适应度低的个体，其繁殖机会就会比较少，甚至逐渐灭绝 选择：以一定概率从种群中选择若干个体

5、的操作。一般而言，选择就是基于适应度的优胜劣汰的过程 交叉：有性生殖生物在繁殖下一时两个同源染色体之间通过交叉而重组，即在两个染色体的相同位置处DNA被切断，前后两串分别交叉组合形成新的染色体 第9页，共44页，编辑于2022年，星期三遗传算法的基本思想第10页，共44页，编辑于2022年，星期三遗传算法的流程图编码解码第11页，共44页，编辑于2022年，星期三遗传算法基本要素与实现技术编码与解码问题域（解空间）优化变量 遗传域（基因空间）优化变量的代码表示映射二进制编码浮点数编码符号编码第12页，共44页，编辑于2022年，星期三编码与解码二进制编码二进制编码是遗传算法中最常用、最原始的一

6、种编码方法，它将原问题的解空间映射到二进制空间上，然后进行遗传操作。找到最优个体后再通过解码过程还原原始的数据形式进行适应度评价二进制编码的串长度 取决于求解的精度 编码公式解码公式第13页，共44页，编辑于2022年，星期三编码与解码浮点编码个体的基因值用某一范围内决策变量的一个浮点数来表示，个体的编码长度等于其决策变量的个数。浮点编码使用的是决策变量的真实值2.50 9.54 3.25 0.25 4.25 7.00X:某个优化问题含有6个变量，则它的一个基因表达为对应的表现型为 x=2.50,9.54,3.25,0.25,4.25,7.00第14页，共44页，编辑于2022年，星期三编码与

7、解码符号编码个体基因值取自一个无数值含意，而只有代码含义的符号集。符号集可以是字母，也可以是数字序号。如血型A，B，AB，O可以分别用a,b,c,d表示，或者a1,a2,a3,a4,也可表示为1，2，3，4第15页，共44页，编辑于2022年，星期三遗传算法基本要素与实现技术最小与最大的转化个体适应度评价 为正确计算个体的遗传概率，个体的适应度必须为正数或者为零，不能为负数而目标函数在寻优区间有一下三种状态：第16页，共44页，编辑于2022年，星期三个体适应度评价F（x）f（x）CF（x）F（x）F（x）第17页，共44页，编辑于2022年，星期三遗传算法基本要素与实现技术选择算子适应度较高

8、的个体被遗传到下一代群体中的概率较大，适应度较低的个体被遗传到下一代群体中的概率较小。选择方法 比例选择法（轮盘赌）锦标赛选择法 第18页，共44页，编辑于2022年，星期三比例选择法（轮盘赌）基本思想 各个个体被选中的概率与其适应度大小成正比。设群体大小为 ，个体 的适应度大小为 ，则 个体 被选中的概率为 第19页，共44页，编辑于2022年，星期三比例选择法（轮盘赌）具体步骤 1）计算各基因适应度值和选择概率 2）累计所有基因选择概率值，记录中间累 加值S-mid 和最后累加值 sum=3）产生一个随机数 N，0 N 1 4）选择对应中间累加值S-mid 的基因进入交换集 5）重复（3）

9、和（4），直到获得足够的基因。第20页，共44页，编辑于2022年，星期三比例选择法（轮盘赌）举例染色体的适应度和所占的比例第21页，共44页，编辑于2022年，星期三锦标赛选择法基本思想 每次随机选取n个个体，比较之后选择其中适应度最高的个体做为下一代种群的父本第22页，共44页，编辑于2022年，星期三遗传算法基本要素与实现技术交叉算子 选择是对优秀个体的复制，不能产生新个体，交叉对相互配对的染色体按某种方式相互交换其部分基因，从而形成两个新的个体。交叉操作是产生新个体的主要方法主要问题 如何对染色体进行配对 如果确定交叉点的位置 如何进行部分基因交换第23页，共44页，编辑于2022年，

10、星期三随机配对将选择出的种群中的M个个体以随即的方式组成M/2对配对个体组，交叉操作就是在这些配对个体组中的两个个体之间进行第24页，共44页，编辑于2022年，星期三二进制编码染色体的交叉单点交叉 基因位数为 ，交叉点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第25页，共44页，编辑于2022年，星期三二进制编码染色体的交叉多点交叉多点交叉的破坏性可以促进解空间的搜索第26页，共44页，编辑于2022年，星期三二进制编码染色体的交叉均匀交叉 两个配对个体的染色体每个基因位以相同的交

11、叉概率进行交换具体步骤随机产生一个与个体编码串长度等长的屏蔽字W按下列规则交叉两个父本的基因若 =0，则父代第i个基因相互交换若 =1，则父代第i个基因不相互交换第27页，共44页，编辑于2022年，星期三均匀交叉例如第28页，共44页，编辑于2022年，星期三浮点编码染色体的交叉线性交叉交叉公式子个体父个体1F(父个体2-父个体1)F为0,1间的均匀分布随机数第29页，共44页，编辑于2022年，星期三浮点编码染色体的交叉中间交叉交叉公式子个体i父个体1iF(父个体2i-父个体1i)第30页，共44页，编辑于2022年，星期三遗传算法基本要素与实现技术变异算子 将个体染色体编码串中的某些基因

12、位编码字符集的其它字符替换二进制编码染色体的变异 编码字符集为0,1,变异操作就是将变异点上的基因取反 变异点是按概率Pm在染色体基因位上指定的第31页，共44页，编辑于2022年，星期三二进制编码染色体的变异具体步骤随机产生一个与个体编码串长度等长的屏蔽字W 为0,1间的随机数按下列规则对基因进行变异若 Pm，则父代基因第i位变异若 Pm，则父代基因第i位不变异第32页，共44页，编辑于2022年，星期三浮点编码染色体的变异浮点编码变异第33页，共44页，编辑于2022年，星期三遗传算法的数学基础模式定理模式 定义定义：种群中的个体即基因串中相同的结构种群中的个体即基因串中相同的结构例如：(

13、以二进制编码为例)假设编码基因串长度为5模式H1 1*0描述了在基因位1，2取值为“1”，在基因位5取值为“0”的所有个体的集合11000，11010，11100，11110 第34页，共44页，编辑于2022年，星期三模式定理结论1定义在长度为定义在长度为 的二进制编码基因串上的模式共有的二进制编码基因串上的模式共有证明：在长为 的基因串中任选定k位作为模式中的确定位，则这样的模式共有 有二项式定理第35页，共44页，编辑于2022年，星期三模式定理模式阶 定义：在模式定义：在模式H H中具有确定基因值的位置数中具有确定基因值的位置数目称为该模式的模式阶，记为目称为该模式的模式阶，记为例如：

14、基因长度固定时，模式阶越高，能与该模式匹配的样本基因就越少第36页，共44页，编辑于2022年，星期三模式定理模式定义长度定义：模式定义：模式H中第一个确定基因值的位置和中第一个确定基因值的位置和最后一个确定基因值的位置之间的距离，称最后一个确定基因值的位置之间的距离，称为该模式的模式定义长度，记为为该模式的模式定义长度，记为例如：第37页，共44页，编辑于2022年，星期三模式定理引入模式的概念后，我们将遗传算法看作是对模式的一种运算。某一模式H的各个样本经过选择，交叉，变异运算后，得到一些新的样本和新的模式。符号说明假定在给定的时刻t，一个特定的模式H有m个代表串包含在种群 中，记为m(H

15、,t)。种群个体 的适应度为 ，个体总数记为n，模式H的平均适应度记为 ，种群的平均适应度为第38页，共44页，编辑于2022年，星期三模式定理选择算子的作用若 1，m（H，t）增加若 1，m（H，t）减少在选择算子的作用下，对于平均适用度高于群体平均适应在选择算子的作用下，对于平均适用度高于群体平均适应度的模式，其样本数将增长，对于平均适用度低于群体平度的模式，其样本数将增长，对于平均适用度低于群体平均适应度的模式，其样本数将减少均适应度的模式，其样本数将减少第39页，共44页，编辑于2022年，星期三模式定理交叉算子的作用（单点交叉）模式H1被破坏的几率大于模式H2一般地，模式H被破坏的几

16、率小于 ，考虑到交叉操作是按照交叉概率Pc进行的，所以模式H的生存概率大于第40页，共44页，编辑于2022年，星期三模式定理变异算子的作用此时若某一模式被破坏，则必然是模式描述形式中的确定位发生了改变，破坏发生概率为 当 有则模式生存概率为第41页，共44页，编辑于2022年，星期三模式定理综合选择，交叉，变异操作下，种群中模式H的子代样本数目为结论二：模式定理模式定理遗传算法中，在选择，交叉和变异算子的作用下，具有低阶，短的定义长度，并且平均适应度高于群体平均适应度的模式将逐代增加第42页，共44页，编辑于2022年，星期三遗传算法的数学基础收敛性分析遗传算法的收敛性定义定义一：种群状态空间种群状态空间 所有可能的种群状态的集合称为种群状态空间，它的元所有可能的种群状态的集合称为种群状态空间，它的元素素 代表一个种群，这个种群的个体就用代表一个种群，这个种群的个体就用 描述描述定义二：渐进收敛渐进收敛 若算法在t时刻的种群满足则成算法渐进收敛到 经典的遗传算法不具备渐进收敛性第43页，共44页，编辑于2022年，星期三遗传算法收敛性定义Markov收敛性 1.有限Markov链的基本知识设随机过程 只能取可列值 ，并且满足条件：对任意t,如果必有 则称 为时间离散状态离散的Markov链 第44页，共44页，编辑于2022年，星期三