文档介绍：该【GA遗传算法 】是由【相惜】上传分享，文档一共【51】页，该文档可以免费在线阅读，需要了解更多关于【GA遗传算法 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。遗传算法(icAlgorithm)Keynote:尤志强精选课件遗传算法与模拟退火算法一样是为解决组合优化问题而提出!人工智能在信息处理和解决组合爆炸方面遇到的困难越来越明显迫使寻求一种适合于大规模问题并具有自组织、自适应、自学习能力的算法,基于生活进化论的遗传算法被提出!精选课件遗传算法遗传算法简称GA〔icAlgorithms〕是1962年由美国Michigan大学的Holland教授提出的模拟自然界遗传机制和生物进化论而成的一种并行随机搜索最优化方法。遗传算法是以达尔文的自然选择学说〔适者生存〕以及Mendel遗传学说〔基因遗传原理〕为根底开展起来的。算法思路:GA将问题的求解表示成“染色体〞的适者生存过程,通过“染色体〞群的一代代不断进化,包括复制、交叉、变异等操作,最终收敛到“最适应环境〞的个体,从而求得问题的最优解或满意解。特点:隐含并行性和全局解空间搜索GA的应用领域:机器学习、模式识别、图像处理、神经网络、优化控制、组合优化等精选课件遗传算法中的自然法那么自然选择学说包括以下三个方面:〔1〕遗传:这是生物的普遍特征,亲代把生物信息交给子代,子代总是和亲代具有相同或相似的性状。生物有了这个特征,物种才能稳定存在。〔2〕变异:亲代和子代之间以及子代的不同个体之间的差异,称为变异。变异是随机发生的,变异的选择和积累是生命多样性的根源。〔3〕生存斗争和适者生存:具有适应性变异的个体被保存下来,不具有适应性变异的个体被淘汰,通过一代代的生存环境的选择作用,性状逐渐逐渐与祖先有所不同,演变为新的物种。Mendel遗传学说遗传以密码方式存在细胞中,并以基因形式包含在染色体内。每个基因有特殊的位置并控制某种特殊性质。所以,每个基因产生的个体对环境具有某种适应性。精选课件遗传算法中的自然法那么遗传算法将“优胜劣汰,适者生存〞的生物进化原理引入优化参数形成的编码串联群体中,按所选择的适应度函数并通过遗传中的复制、交叉及变异对个体进行筛选,使适应度高的个体被保存下来,组成新的群体,新的群体既继承了上一代的信息,又优于上一代。这样周而复始,群体中个体适应度不断提高,直到满足一定的条件。遗传算法的算法简单,可并行处理,并能得到全局最优解。精选课件遗传算法中的相关概念遗传算法用到各种进化和遗传学得概念。以下是一些主要的概念:(1)串(String):它是个体(Individual)的形式,在算法中为二进制串,并且对应于遗传学中的染色体(Chromosome).(2)群体(Population):个体的集合称为群体,串是群体的元素。(3)群体规模(PopulationSize):在群体中个体的数量称为群体规模,又称群体的大小。(4)基因(Gene):基因是串中的元素,基因用于表示个体的特征。例如有一个串S=1011,那么其中1,0,1,1这四个元素分别称为基因,它们的值称为等位基因。(5)基因位置(GenePosition):一个基因在串中的位置称为基因位置,有时也简称基因位。基因位置由串的左边向右计算,例如在串S=1011中,(Locus).(6)适应度(Fitness):表示某一个体对于环境的适应程度。图1解空间与生物空间的对应精选课件遗传算法的根本流程遗传算法是一类随机优化算法,但它不是简单的随机比较搜索,而是通过对染色体的评价和对染色体中基因的作用,有效地利用已有的信息来指导搜索有希望改善优化质量的状态。该算法包括5个根本要素:变量编码、初始群体的设定、适应度函数的设计、遗传操作设计和参数设定。〔1〕编码通过编码将解空间的数据表示成遗传空间的基因型串结构数据。编码一般有二进制编码和实数编码。对于问题解X,X=〔x1,x2,…,xn〕,二进制编码是把X用0,1串表示,而实数编码是把X用一向量表示,即X=〔x1,x2,…,xn〕,xi是实数。编码设计应适合要解决的问题,应考虑完全性、封闭性、可扩展性和复杂性等。完全性是指分布在所有问题域的解都可能被构造出来;封闭性是指每个基因编码对应一个可接受的个体,不产生无效的个体;可扩展性是指对于具体问题,要考虑编码形式与大小影响下的解码时间;复杂性是指整体考虑基因型的结构复杂性、解码复杂性、计算复杂性等。(2)初始群体的生成在遗传算法处理流程中,继编码设计后的任务是初始群体的生成,并以此为起点一代代进化直到满足某种进化停止准那么终止进化过程,初始群体也称为进化的初始代,即第一代。初始群体的个体一般可采用随机产生,一般群体可表示为Z={Xi|Xi=〔xi1,xi2,…..xin〕},i=1,2,…N},即Xi是染色体或个体,xi是基因或位。假设是实数编码,那么xi精选课件遗传算法的根本流程〔3〕适应度函数适应度函数设计是模拟自然选择,进行遗传进化操作的根底,它的评估是遗传操作的依据。适应度函数值即适应度。由于下面定义的选择概率以适应度为根底,因此适应度是非负的。方法一:对于求目标函数最大值的优化问题,变换方法为:其中,Cmin为一个适当地相比照较小的数,它可用下面方法之一来选取:?预先指定的一个较小的数。?进化到当前代为止的最小目标函数值。?当前代或最近几代群体中的最小目标函数值。方法二:对于求目标函数最小值的优化问题,变换方法为:其中,Cmax是一个适当地相比照较大的数,它可用下面几种方法求得:?预先指定的一个较大的数。?进化到当前代为止的最大目标函数值。?当前代或最近几代群体中的最大目标函数值。F(X)=f(X)+Cminiff(X)+Cmin>00iff(X)+Cmin≤0F(X)=Cmax-f(X)iff(X)?Cmax0iff(X)?Cmax精选课件遗传算法的根本流程从群体中选择优胜的个体,淘汰劣质的个体的操作称为选择。它是建立在群体中个体适应值的根底上的,其目的是把优胜的个体遗传到下一代,选择操作的实现是根据适应度大小按照某种策略从父代中挑选个体进入中间群体。选择算子设计依赖选择概率,个体Xi选择概率定义为其中fi是群体中第i个个体的适应值,N是群体的规模。当reli越大时,个体Xi被选择遗传〔复制〕到下一代的可能性越大。目前常用的遗传选择算子主要有以下几种:〔1〕基于赌轮法的选择算子(2)期望值方法精选课件遗传算法的根本流程A、基于赌轮法的选择算子赌轮法是指根据个体被选择概率大小确定相应个体是否被遗传〔复制〕到下一代,其比较判别过程采用了轮盘赌的思想。设种群有n个个体X1,X2,…,Xn,Xi的选择概率P〔Xi〕,每个个体对应P〔Xi〕表示为赌轮上的某个区域,按个体数n转动赌轮n次,根据赌轮停止点区域对应的个体进行选择,个体对应赌轮区域越大被选择的时机越大,计算个体被选择的数量,这些个体将按选择的数量被复制。在计算机辅助实现过程中,模拟赌轮一般采用以下方法:根据个体的排序,按选择概率P〔Xi〕计算累积概率,那么Pi〔Xi〕=qi-qi-1,产生n个随机数rk,对每一个随机数,判断其落在那个概率区间内,那么复制相应的Xi,可以得到选择复制后的n个新一代个体。可以看到适应值越大的染色体被选中〔复制〕的概率也越大。B、期望值方法把每一个体的适应度与平均适应度进行比较,以确定该个体在下一代的复制数,即每个个体在下一代生存的期望数目为Ni=round(p(xi)*N)可以看到适应值越大的染色体被选中〔复制〕的数目也越多。,其中round(x)表示与x距离最小的整数。精选课件