遗传算法简介总论课件

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,遗传算法,遗传算法的基本思想是基于,Darwin,进化论和,Mendel,的遗传学说的。,Darwin,进化论最重要的是适者生存原理。它认为每一物种在发展中越来越适应环境。物种每个个体的基本特征由后代所继承，但后代又会产生一些异于父代的新变化。在环境变化时，只有那些,能,适应环境的个体特征方能保留下来。,Mendel,遗传学说最重要的是基因遗传原理。它认为遗传以基因形式包含在染色体内。每个基因有特殊的位置并控制某种特殊性质；所以，每个基因产生的个体对环境具有某种适应性。基因突变和基因杂交可产生更适应于环境的后代。经过存优去劣的自然淘汰，适应性高的基因结构得以保存下来。,遗传与进化的系统观,生物的所有遗传信息都包含在染色体中，染色体决定生物的性状。,染色体是由基因及其有规律的排列构成，遗传进化过程发生在染色体上。,生物的繁衍由基因的复制过程完成。,通过同源染色体之间的交叉或染色体的变异会产生新物种，使生物呈现新性状。,对环境适应性好的基因比适应性差的基因有更多机会遗传到下一代。,遗传算法的基本概念,由于遗传算法是由进化论和遗传学机理而产生的直接搜索优化方法，故而在这个算法中要用到各种进化和遗传学的概念。这些概念如下：,串(,String),它是个体(,Individual),的形式，在算法中为二进制串，并且对应于遗传学中的染色体(,Chromosome)。,群体(,Population),个体的集合称为群体，串是群体的元素。,群体大小(,Population Size),在群体中个体的数量称为群体的大小。,遗传算法的基本概念,基因(,Gene),基因是串中的元素，用于表示个体的特征。例如有一个串,S1011，,则其中的1，0，1，1这4个元素分别称为基因。它们的值称为等位基因(,Alletes,)。,基因位置(,Gene Position),一个基因在串中的位置称为基因位置，有时也简称基因位。基因位置由串的左向右计算，例如在串,S1101,中，0的基因位置是3。基因位置对应于遗传学中的地点(,Locus)。,基因特征值(,Gene Feature),在用串表示整数时，基因的特征值与二进制数的权一致；例如在串,S=1011,中，基因位置3中的1，它的基因特征值为2；基因位置1中的1，它的基因特征值为8。,遗传算法的基本概念,串结构空间,S,S,在串中，基因任意组合所构成的串的集合。基因操作是在结构空间中进行的。串结构空间对应于遗传学中的基因型(,Genotype),的集合。,参数空间,S,P,这是串空间在物理系统中的映射，它对应于遗传学中的表现型(,Phenotype),的集合。,非线性,它对应遗传学中的异位显性(,Epistasis,),适应度(,Fitness),表示某一个体对于环境的适应程度。,遗传算法的基本实现,编码：,GA,在进行搜索之前先将解空间的解数据表示成遗传空间的基因型数据，这些数据的不同组合便构成了不同的点。,初始群体的生成：随机产生,N,个初始串结构数据，每个串结构数据称为一个个体，,N,个个体构成了一个群体。,GA,以这,N,个串结构数据作为初始点开始迭代。,适应性值评估检测：适应性函数表明个体或解的优劣性。不同的问题，适应性函数的定义方式也不同。,遗传算法的基本实现,选择：选择的目的是为了从当前群体中选出优良的个体，使它们有机会作为父代为下一代繁殖子孙。遗传算法通过选择过程体现这一思想，进行选择的原则是适应性强的个体为下一代贡献一个或多个后代的概率大。选择实现了达尔文的适者生存原则。,交换：交换操作是遗传算法中最主要的遗传操作。通过交换操作可以得到新一代个体，新个体组合了其父辈个体的特性。交换体现了信息交换的思想。,变异：变异首先在群体中随机选择一个个体，对于选中的个体以一定的概率随机地改变串结构数据中某个串的值。同生物界一样，,GA,中变异发生的概率很低，通常取值在0.0010.01之间。变异为新个体的产生提供了机会。,遗传算法的基本实现,GA,的计算过程为：,选择编码方式；,产生初始群体；,计算初始群体的适应性值；,如果不满足条件 选择 交换 变异 计算新一代群体的适应性值,一、遗传算法的描述,例子,：,为四个连锁饭店寻找最好的经营决策，其中一个经营饭店的决策包括要做出以下三项决定：,（1）价格,汉堡包的价格应该定在50美分还是1美元？,（2）饮料,和汉堡包一起供应的应该是酒还是可乐？,（3）服务速度,饭店应该提供慢的还是快的服务？,目的：,找到这三个决定的组合以产生最高的利润。,共有8种表示方案。,用遗传算法解这个问题的第一步就是选取一个适当的表示方案。,。,饭店编号,价 格,饮 料,速 度,二进制表示,1,高,可乐,快,011,2,高,酒,快,001,3,低,可乐,慢,110,4,高,可乐,慢,010,表1 饭店问题的表示方案（其中的4个）,群体规模,N4,第0代,i,串,x,i,适应值,f（,x,i,）,1,011,3,2,001,1,3,110,6,4,010,2,总和,12,最小值,1,平均值,3.00,最大值,6,表2 初始群体中经营决策的适应值,一个简单的遗传算法由选择、交叉、变异三个算子组成。,第0代,交叉池,i,串,x,i,适应值,f（,x,i,）,f（,x,i,）/,f（,x,i,）,串,f（,x,i,）,1,011,3,0.25,011,3,2,001,1,0.08,110,6,3,110,6,0.50,110,6,4,010,2,0.17,010,2,总和,12,17,最小值,1,2,平均值,3.00,4.25,最大值,6,6,表3 使用,选择算子,后产生的交叉池,1.,选择算子,：比例选择,2.,交叉算子,：采用单点交叉,作用过程：,a）,产生一个在1到,l,1,之间的随机数,i,b）,配对的两个串相互对应的交换从,i1,到,l,的位段,例如：从交叉池中选择编号为1和2的串进行交叉，且交叉点选在2（用分隔符,|,表示），交叉算子作用的结果为：,01,|,1 010,11,|,0 111,对交叉池中指定百分比的个体应用交叉算子，假设交叉概率,p,c,50，,交叉池中余下的50个体仅进行复制运算，即复制概率,p,r,50。,第 0 代,交叉,池,第 1 代,i,串,x,i,适应值,f（,x,i,）,f（,x,i,）/,f（,x,i,）,串,f（,x,i,）,交叉,点,x,i,f（,x,i,）,1,011,3,0.25,011,3,2,010,2,2,001,1,0.08,110,6,2,111,7,3,110,6,0.50,110,6,110,6,4,010,2,0.17,010,2,010,2,总和,12,17,17,最小值,1,2,2,平均值,3.00,4.25,4.25,最大值,6,6,7,表4 使用,复制和交叉算子,的作用结果,遗传算法利用复制和交叉算子可以产生具有更高平均适应值和更好个体的群体,3.,变异算子,：,以一个很小的概率,p,m,随机改变染色体串上的某些位。,对于二进制串，就是将相应位上的0变为1或将1变为0。,例如：选交叉池中编号为4的串进行变异，且变异点在2，则,010 000,变异算子相对而言，是次要算子，但在恢复群体中失去的多样性方面具有潜在的作用。,小结,上述遗传算法描述了从第0代产生第1代的过程，然后遗传算法迭代地执行这个过程，直到满足某个停止准则。在每一代中，算法首先计算群体中每个个体的适应值，然后利用适应值信息，遗传算法分别以概率,p,c,、,p,r,和,p,m,执行交叉、复制和变异操作，从而产生新的群体。,应用遗传算法求解问题需完成四个主要步骤：,1.确定表示方案；,2.确定适应值度量；,3.确定控制算法的参数和变量；,4.确定指定结果的方法和停止运行的准则。,基本遗传算法的构成要素,1.染色体编码方法,最常用的是二进制编码，对于离散性变量直接编码，对于连续性变量先离散化后再编码。,2.适应度函数,评估函数用来评估一个染色体的优劣的绝对值。,适应度函数评估一个染色体相对整个群体的优劣的相对值的大小。,3.遗传算子,复制算子、交叉算子、变异算子。,4.基本遗传算法运行参数,N：,群体大小，即群体中所含个体的数量，一般取20100,T：,遗传算法的终止进化代数，一般取100500,p,c,：,交叉概率，一般取0.250.75,p,m,：,变异概率，一般取0.010.2,p,r,：,复制概率,三、基本遗传算法的一般框架,算法过程：,1.随机产生一个由确定长度的特征串组成的初始群体；,2.对串群体迭代地执行下面的步（,i）,和步（,ii），,直到满足停止准则：,（i）,计算群体中每个个体的适应值；,（,ii）,应用复制、杂交和变异算子产生下一代群体。,3.把在任一代中出现地最好的个体串指定为遗传算法的执行结果，这个结果可以表示问题的一个解（或近似解）。,GEN0,产生初始群体,是否满足停止准则,指定结果,结 束,计算每个个体的适应值,i0,iN？,以概率选择遗传算子,GENGEN1,选择一个个体,选择两个个体,选择一个个体,执行复制,ii1,执行变异,复制到新群体,执行交叉,插入到新群体,将两个子代串插入到新群体,ii1,是,否,是,否,p,r,p,c,p,m,GEN,当前代数,N,群体规模,定理（收敛性定理）,：如果在代的演化过程中，遗传算法保留最好的解，并且算法以交叉和变异作为随机化算子，则对于一个全局优化问题，随着演化代数趋向于无穷，遗传算法将以概率1找到全局最优解。,遗传算法极限特性的分析表明算法能够对搜索空间进行持续的搜索，因此遗传算法特别适合于在全局优化问题中应用。,遗传算法的特点,1.搜索过程不直接作用在变量上，而是在参数集进行了编码的个体。此编码操作，使得遗传算法可直接对结构对象（集合、序列、矩阵、树、图、链和表）进行操作，不存在求导和函数连续性的限定；,2.遗传算法不是从单个点，而是从一个点的群体开始搜索，同时利用了多个搜索点的信息；,3.,具有内在的隐并行性和较好的全局寻优能力；,4.采用概率寻优方法，能自动获取搜索过程中的有关知识并用于指导优化，自适应地调整搜索方向，不需要确定的规则；,5.鲁棒性。,数据挖掘,数据挖掘的概念,网络之后的下一个技术热点是什么？,让我们来看一些身边俯拾即是的现象：纽约时报由60年代的1020版扩张至现在的100200版，最高曾达1572版；然而在现实社会中，人均日阅读时间通常为3045分钟，只能浏览一份24版的报纸。,大量信息在给人们带来方便的同时也带来了一大堆问题：第一是信息过量，难以消化；第二是信息真假难以辨识；第三是信息安全难以保证；第四是信息形式不一致，难以统一处理。,人们开始提出一个新的口号：“要学会抛弃信息”。人们开始考虑：“如何才能不被信息淹没，而是从中及时发现有用的知识、提高信息利用率？”,数据挖掘的概念,数据爆炸但知识贫乏,另一方面，随着数据库技术的迅速发展以及数据库管理系统的广泛应用，人们积累的数据越来越多。激增的数据背后隐藏着许多重要的信息，人们希望能够对其进行更高层次的分析，以便更好地利用这些数据。,目前的数据库系统可以高效地实现数据的录入、查询、统计等功能，但无法发现数据中存在的关系和规则，无法根据现有的数据预测未来的发展趋势。缺乏挖掘数据背后隐藏的知识的手段，导致了“数据爆炸但知识贫乏”的现象。,数据挖掘的概念,数据挖掘就是从大量的数据中挖掘出有用的信息。,它是根据人们的特定要求，从浩如烟海的数据中找出所需的信息来，供人们的特定需求使用。,据国外专家预测，随着数据量的日益积累和计算机的广泛应用，在今后的510年内，数据挖掘将在中国形成一个新型的产业。,数据挖掘的进化历史,进化阶段,商业问题,支持技术,产品厂家,产品特点,数据搜集,(60,年代,),“过去五年中我的总收入是多少？,”,计算机、磁带和磁盘,IBM,CDC,提供历史性的、静态的数据信息,数据访问,(80,