还剩13页未读,继续阅读
本资源只提供10页预览,全部文档请下载后查看!喜欢就下载吧,查找使用更方便
文本内容:
其次章遗传算法的基本原理
2.1遗传算法的基本描述全局优化问题全局优化问题的定义给定非空集合S作为搜寻空间,f S-R为目标函数,全局优化问题作为任务max/a)给出,即在搜寻空间中找到至少一个使目标函数最大化的点xgS全局最大值(点)的定义函数值/*=/(/)”称为一个全局最大值,当且仅当X/x£S=/(X)/(X*)成立时,/GS被称为一个全局最大值点(全局最大解)局部极大值与局部极大值点(解)的定义假设在S上给定了某个距离度量0假如对XES3^0使得对WxwSp(xx)£=/(x)f(x)则称X为一个局部极大值点,F(x)为一个局部极大值当目标函数有多个局部极大点时,被称为多峰或多模态函数(multi-modalityfunction)o主要考虑两类搜寻空间伪布尔优化问题当S为离散空间1};即全部长度为L且取值为0或1的二进制位串的集合时,相应的优化问题在进化计算领域称为伪布尔优化问题连续参数优化问题当取S伪n维实数空间力中的有界集合5=口3[《4]其中q2,片12…n时,相应的具有连续变量的优化问题称为连续参数优化问题对S为口二{01}1常采纳的度量时海明距离,当s=n*a*]时,常采纳的度量就是欧氏距离遗传算法的基本流程遗传算法的基本步骤如下1)选择编码策略,把参数集合X和域转换为位串结构空间S;2)定义适应度函数F⑴;3)确定遗传策略,包括群体规模,选择、交叉、变异算子及其概率4)生成初始种群P;5)计算群体中各个体的适应度值;6)依据遗传策略,将遗传算子作用于种群,产生下一代种群;7)迭代终止判定遗传算法涉及六大要素参数编码,初始群体的设定,适应度函数的设计,遗传操作的设计,掌握参数的设定,迭代终止条件遗传编码由于GA计算过程的鲁棒性,它对编码的要求并不苛刻原则上任何形式的编码都可以,只要存在合适的对其进行操作的遗传算子,使得它满足模式定理和积木块假设异(高位、低位),变异概率自适应调整、面对领域学问的位变异等,使得遗传算法的应用范围和应用效果得到较好的改善在很多组合优化问题中,往往存在着多个最优解或者最优解往往被环绕在大量的局部最优解之中,应用GA求解该类问题很简洁形成模式哄骗问题,此时可以采纳补算算子(Comp1ementaryoperator)增加群体多样性或者克服模式哄骗性基于{
1.0}字符集表示的二进制染色体位串s=q补算算子详细操作形式如下O{coms)k1一2£对于位串上每一个基因位,若等位基由于0则变为1否则变为0从而形成新得位串例如s==01000100o循环终止条件关于GA迭代过程如何终止,一般采纳设定最大代数的方法该方法简洁易行但不精确其次,可以依据群体的收敛程度来推断,通过计算种群中的基因多样性测度,即全部基因位的相像性程度来进行掌握第三,依据算法的离线性能和在线性能的变化进行判定最终,在采纳精英保留选择策略的状况下,按每代最佳个体的适应值的变化状况确定一般循环终止条件表示为T(P(t))=trueo标准GA的流程1)设代数t=02)初始化种群3)适应性评价whileT(P(t))*truedoa)选择b)交叉c)变异d)新一代种群e)适应性评价cnddo掌握参数在遗传算法的运行过程中,存在着对其性能产生重大影响的一组参数这组参数在初始阶段或群体进化过程中需要合理的选择和掌握,以使GA以最佳的搜寻轨迹达到最优解主要参数包括染色体位串长度群体规模),交叉概率1以及变异概率为很多学者进行了大量试验讨论,给出了最优参数建议1)位串长度L位串长度L的选择取决于特定问题解的精度要求的精度越高,位串越长,但需要更多的计算时间为提高运算效率,变长度位串或者在当前所达到的较小可行域内重新编码是一种可行的方法,并显示了良好性能2)群体规模n大群体含有较多模式,为遗传算法供应了足够的模式采样容量,可以改进GA搜寻的质量,防止成熟前收敛但大群体增加了个体适应性评价的计算量,从而使收敛速度降低一般状况下专家建议n=20〜2003)交叉概率Pc交叉概率掌握着交叉算子的应用频率,在每一代新的群体中,需要对PcXn个个体的染色体结构进行交叉操作交叉概率越高,群体中新结构的引人愈快,已获得的优良基因结构的丢失速度也相应上升而交叉概率太低则可能导致搜寻阻滞一般取Pc=
0.60〜
1.004)变异概率Pm变异操作是保持群体多样性的有效手段,交叉结束后,交配池中的全部个体位串上的每位等位基因按变异率Pm随机转变,因此每代中大约发生PmXnXL次变异变异概率太小,可能使某些基因位过早丢失的信息无法恢复;而变异概率过高,则遗传搜寻将变成随机搜寻一般取Pm=O.005^
0.01o实际上,上述参数与问题的类型有着直接的关系问题的目标函数越简单,参数选择就越困难从理论上来讲,不存在一组适用于全部问题的最佳参数值,随着问题特征的变化,有效参数的差异往往特别显着如何设定遗传算法的掌握参数以使遗传算法的性能得到改善,还需要结合实际问题深人讨论,以及有赖于遗传算法理论讨论的新进展6A的性能评估GA的运行性能与很多因素有关针对求解同一优化问题,不同参数设置的两个或者多个GA或者GA与其他启发式搜寻算法,如何进行性能比较呢?关于搜寻类算法的性能评估,一般可以归纳为算法的求解效率和求解质量两个方面算法的求解效率是比较获得同样的可行解所需要的计算时间算法的求解质量是在规定的时间内或者时间相关指标所获得的可行解的优劣这里主要介绍常用和通用的两个指标.适应值函数计算次数该指标是指发觉同样适应性的个体,或者找到同样质量的可行解,所需要的关于个体评价的适应值函数的计算次数functionevaluations明显,该值越小说明相应GA的搜寻效率越高同样,在预定的适应值函数计算次数的状况下,比较所发觉的最佳个体或者找到的可行解的质量,也可以推断不同GA的搜寻力量该指标不仅可以用于不同参数设置GA的性能比较,也可以用于GA与其他搜寻算法的比较适应值函数的计算次数一般采纳群体规模与进化代数的乘积,其中往往不考虑代沟大小的影响.在线和离线性能函数DeJona在将GA用于一组优化函数求解的比较分析时,提出了GA的在线评价指标和离线评价指标两个函数1线性能函数on-1ineperformance设GA的遗传策略为s包括{LnPcPm}算子形式等,该策略的在线性能即在线性能反映了群体平均适应值经平滑处理后的变化状况,描述了群体的整体性状和进化力量2离线性能函数off—lineperformance对于GA遗传策略s其离线性能其中,fa*t=max{faitfa2t…,fant}即当前群体中最佳个体的适应值该指标反映了群体中最佳个体适应值经平滑处理后的变化状况,描述了个体的进化力量和GA的搜寻力量关于上述适应值的平滑处理,也可以通过赐予进化过程中各代不同的权重,转变为适应值的加权平均计算,以消退初始群体带来的误差.最优解搜寻性能GA用于函数优化的目的就是发觉问题的全局最优解,所以通常采纳当前群体发觉的最佳可行解的改善状况作为度量GA搜寻力量的基本指标对于GA遗传策略S性能函数为PbeStst=fa*t其中,P可以反映GA搜寻到全局最优解的过程、速度、早熟等状况,也是适应性参数调整的此外,结合详细的应用实例,还可以设计一系列具有不同物理含义的性能评价函数和指标
2.2遗传算法的模式理论虽然GA计算过程和形式简洁,但是其运行机理特别简单随着GA在简单优化问题求解和实际工程设计中的应用,人们对GA的理论基础赐予了越来越多的关注主要问题包括1采纳怎样的规律和模型来描述GA的宏观行为,GA进化过程中如何猜测适应值的变化,以及特定GA形式下的群体结构的进化动力行为2如何评价GA性能的优劣,采纳怎样的评价标准GA适用于哪些问题的求解,即对于哪些问题求解GA性能表现优异,或者GA性能表现低劣4在什么条件下问题性质、GA形式等,GA能够超越其他启发式搜寻方法关于以上问题的讨论就形成了GA的基本理论Holand在早期讨论中提出了模式scnema概念以及模式定理scnernalneorem试图赐予法律规范严格的理论分析
2.1模式与模式空间遗传算法将实际问题表示成位串空间,以群体为基础,依据适者生存的原则,从中选择出高适应值的位串进行遗传操作,产生出下一代适应性好的位串集合,从而将整个群体不断转移到位串空间中适应值高的子集上,直到获得问题的最优解在这一过程中,群体中是由哪些信息来指导和记忆寻优过程呢?Holland发觉,位串上的某些等位基因的联结与适应值函数之间存在着某种联系,这种联系供应了寻优过程的指导信息,引导着群体在位串空间中的移动方向遗传算法在工作过程中,建立并管理着问题参数空间、位串空间或称为编码空间、模式空间和适应值空间等四个空间及其之间的转换关系采纳字符集K二{01}对问题参数进行二进制编码,位串空间表示为SL={1OF该空间的基数为|S“=2扩展字符集K={01*}其中*是通配符或无关符wildcardsor“dontcares即可和0或1匹配扩展位串空间表示为SX
1.0*1-该空间的基数为IS|=3则称SJ为的模式空间明显,包含个位串的位串空间,对应于31个模式位串的模式空间定义扩展位串空间SJ={01*y中的任何一个点,称为对应于位串空间SL={1O}L的一个模式Schema其中a=a],a2a.H=H”H”…,Hjate{01H.te{01*}i=l2…,L;aeSLtH模式是由小中具有共同特征的位串所组成的集合,它描述了该集合中位串上共同的基因特征Goldberg将模式称为“超平面”hype^lane指出了模式在编码空间上的几何意义,模式包含的位串是编码空间相应超平面上的点例如模式00**表示位串长度为4两个高位基由于00的位串集合,即{0000000100100011}o定义模式的阶schemaorder是指模式中所含有
0、1确定基因位的个数,记作H定义模式的定义距defininglength是指模式中从左到右第一个非*位和最终一位非*位之间的距离记作出定义模式的维数schemadimension是指模式中所包含的位串的个数,也称为模式的容量,记作DHDH=2ihho定义令t为模式H在第t代群体中所含位串数量,模式在t代群体中包含的个体位串为{a1a2…aj称为模式H在群体中的生存数■survivals或者采样样本samplesa}eHj=l2m则模式H在第t代群体中的适应值估量为即模式的适应值估量简称模式的适应值是群体中其所包含的全部个体的适应值的平均值从编码空间来看,mIIt是当前群体中包含于模式II的个体数量,反映了所对应的模式空间的分布状况,该数量越大说明群体搜寻越集中于模式H代表的子空间从模式空间来看,mHt是模式H在当前群体中的个体采样数量,反映了所对应的编码空间的分布状况该数量越大说明群体中的个体越趋向相像和全都,在编码空间的搜寻范围越小比如:模式0H=3t77=2DH=22=4O可见,一个模式H由位串长度L、阶0H、定义距5”、容量DH和适应值fHt等五个指标来描述模式的引入为在一个有限字符集上定义的有限长度的位串之间的相像性度量和理论分析供应了有力的工具.
2.2模式定理和积木块假设在选择算子作用下,对于平均适应度高于群体平均适应度的模式,其样本数将呈指数级增长而对于平均适应度低于群体平均适应度的模式,其样本数将呈指数级削减在选择和交叉算子作用下,模式定义距越小,则群体中该模式个体数量越简洁呈指数级增长;模式定义距越大,则群体中该模式个体数量越不简洁呈指数级增长在变异算子作用下,阶数越小.模式H越易于生存;阶数越大,模式H越易于放破坏定理[模式定理]在遗传算子选择、交叉、变异的作用下,那些低阶、定义距短的、超过群体平均适应度值的模式的生存数量,将随着迭代次数的增加以指数规律增长理论基础统计决策中的双臂赌机问题表明按指数规律提高将硬币投往平均支付高的赌机的概率,可以获得最大的累积支付应用到优化问题则是要获得最优的可行解,则必需保证较优解的样本数呈指数级增长而模式定理保证了较优的模式遗传算法的较优解的样本数呈指数级增长,从而给出了遗传算法的理论基础由模式定理可知,具有低阶、短定义距以及平均适应度高于群体平均适应度的模式在子代中将以指数级增长这类模式在遗传算法中特别重要,我们给它们一个特殊的名字一一积木块buildingblocko定义
2.4具有低阶、短定义距以及高适应度的模式称作积木块正如搭积木一样,这些“好”的模式在遗传操作下相互拼搭、结合,产生适应度更高的串,从而找到更优的可行解,这正是积木块假设所揭示的内容假设2・1[积木块假设buildingblockhypothesis]低阶、短距、高平均适应度的模式积木块在遗传算于作用下,相互结合,能生成高阶、长距、高平均适应度的模式可最终生成全局最优解上一节的模式定理保证了较优的模式遗传算法的较优解的样本数呈指数级增长,从而满足了查找最优解的必要条件,即遗传算法存在着查找到全局最优解的可能性而本节的积木块假设则指出,遗传算法具备查找到全局最优解的力量,即积木块在遗传算子作用下,能生成高阶、长距、高平均适应度的模式,最终生成全局最优解然而,圆满的是上述结论并没有得到证明,正由于如此才被称为假设,而非定理目前已经有大量的实践证据支持这一假设,从20多年前Bagley和Rosenberg的两篇开创性的文章到最近大量的遗传算法应用实例都表明,积木块假设在很多领域都获得了胜利,例如平滑多峰问题,带干扰多峰问题以及组合优化问题等等尽管大量的证据并不等于理论证明,但至少可以确定,对多数常常遇到的问题,遗传算法都是适用的模式定理和建筑模块假设比较精确地模拟了自然界的物种竞争和遗传法则,其中模式定理描述了GA群体中模式之间的竞争关系,建筑模块假设说明白有效基因之间的继承与重组因此,模式定理和建筑模块假设构成了关于GA进化过程能够发觉最优解的一个充分条件,被认为是解释遗传算法寻优原理的较系统的理论,统称为模式理论schernatheoryo它们也是GA进化动力学的基本理论,尽管还存在着不完善之处,但是它为深化讨论遗传算法的运行机理奠定了基础虽然模式定理在肯定意义上解决了基本遗传算法SGA的有效性,但它仍有以下的缺点1模式定理只对二进制编码适用,对其他编码方案尚没有相应的结论成立2模式定理只结出了在下世代包含模式H的个体数的下限我们无法据此推断算法的收敛性3模式定理没有解决算法设计中掌握参数选取等问题最近,Bethke的讨论好像为这个问题的解决带来了盼望Bethkc采纳Walsh函数和一种奇妙的模式变换,提出了一种采纳Walsh系数计算模式平均适应度的有效分析方法,这使得在一些特定的适应度函数和编码方式下,可以判定积木块通过相互组合是否会产生最优解或接近最优解Holland把Bethke的方法推广到了当群体非匀称分布时的模式平均适应度分析上可以用Walsh系数描述遗传算法操作遗传算法渐近地估量Walsh系数,并且引导搜寻朝着Walsh系数较大的分割中使Walsh函数取正值的模式进行,就是说,遗传算法是Walsh系数求和过程中的贪心Bethke指出,假如一个函数的Walsh系数随着j相应分割的序号的阶和长度的增长而快速降低,即重要的Walsh系数是与短的低阶分割相联系的,则这个函数简洁用遗传算法求解,称为GA-易GA—easy这时,通过估量低阶模式的平均值就可以发觉全局最优点这样的模式在群体中所占比例比高阶长模式更简洁增长“低阶”意味着它的样本较多,“短”使得它不简洁被破坏对遗传算法而言,估量它们的平均值要比估量高阶长模式简洁得多因此,Bethke得出结论,由于遗传算法难于对高阶分割中的高阶模式做出好的估量,在其它条件都相同的状况下,假如一个函数的Walsh分解中高阶分割对应了较重要数值较大的Walsh系数,则该函数难于用遗传算法求解,并称之为GA—难GA-hard从模式理论的角度来看,高阶系数小,意味着低阶模式所给出的估量误差小,信息精确,低阶积木块组合即可得到高阶积木块,满足积木块假设,所以,Walsh模式分析和模式理论在划分GA—难、GA—易时,实际上是殊途同归的对于判定一个函数是否GA-难,Bethke的结论并不适用,由于大部分遗传算法应用中的目标函数都不简洁表示成Walsh多项式;即使简洁表示,计算Walsh系数需要对搜寻空间的每个点计算Fx这对大多数函数是不行能的,而且,假如计算了Fx的全部值,就知道了其最优解,而没必要再用遗传算法求解了,分析就失去了意义但是Walsh分析是一个强有力的理论工具Bethke采纳此方法已经产生了一些会使简洁三算子遗传算法误入歧途的测试状况,我们称这些编码函数的组合是GA一骗的GA-deceptive这些结果告知我们,GA—骗的函数和编码有包含孤立的最佳点的倾向,即最好的点可能被最坏点所包围但我们真正遇到的很多函数均不含此状况实际的状况是,函数编码组合中常存在着某种规章性,它们都可由重组积木块进行开拓之重要的是,我们要记住,简洁遗传算法依靠于为查找最佳解点的积木块的组合,假如这些积木块组合因所使用的编码和函数本身而被弄错,那么问题欲达到最佳解可能需要很长的时间2・3骗问题我们已经知道,遗传算法适用于大多数常常遇到的问题,但也存在着一些遗传算法难以解决的问题,即最终的搜寻往往偏离全局最优解,这类问题被称作GA一难的这一节我们研讨所谓的骗问题deceptiveProblem即构造一个问题,给定一些带哄骗性质的初始条件,“迷惑”遗传算法,使其偏离全局最优解为此,要最大限度地违反积木块假设,即使得低阶、短距、高于平均适应度的模式生成局部最优点由模式理论,一个问题能否用遗传算法有效地求解,取决于问题编码是否满足积木块假设,满足者用遗传算法求解效率较高,不满足者效率较低、甚至找不到满足解然而,尽管我们试图“迷惑”遗传算法,但这类骗问题却往往不是GA—难的,即通常不会偏离全局最优解在遗传算法中,将全部阻碍评价值高的个体生成从而影响遗传算法正常工作的问题统称为哄骗问题遗传算法运行过程具有将高于平均适应度、低阶和短定义距的模式重组成高阶模式的趋势假如在低阶模式中包含了最优解的话,则遗传算法就可能找出它来但是低阶、高适应度的模式可能没有包含最优串的详细取值,于是遗传算法就会收敛到一个次优的结果下面给出有关期骗性的概念定义竞争模式若模式H与H*的位置完全全都;但任一确定位的编码均不同,则称H与H互为竞争模式定义哄骗性假设fx的最大值对应的x集合为《,II为一包含父的小阶模式H的竞争模式为H而且fHfH则f为m阶哄骗在上述定义中,当m=/时,由于模式中不包含*自然不存在哄骗性问题以下描述最小骗问题minimaldeceptiveProblemo这里所谓“最小”是指为了造成骗局所需设置的最小的问题规模即阶数假设有一个由4个阶数为
2、有2个确定位置的模式构成的集合,各模式具有如下的适应度其中f00f01f10fll是各模式的平均适应度,并假定为常值我们不妨假定fll是全局最优值,即有fllf01fllfOlfllf10现在,设法引入迷惑遗传算法的条件考虑4个一阶模式的适应度,3遗传算法与组合优化组合优化combinatorialoPtimization是遗传算法最基本的也是最重要的讨论和应用领域之一所谓组合优化是指在离散的、有限的数学结构上,查找一个满足给定约束条件并使其目标函数值达到最大或最小的解一般来说,组合优化问题通常带有大量的局部极值点,往往是不行微的、不连续的、多维的、有约束条件的、高度非线性的NP完全问题,因此,精确地求解组合优化问题的全局最优解一般是不行能的由于编码形式打算了交叉算子的操作方式,编码问题往往称作编码-交叉问题对于给定的优化问题,由GA个体的表现型集合做组成的空间称为问题(参数)空间,由GA基因型个体所组成的空间称为GA编码空间遗传算子在GA编码空间中对位串个体进行操作定义由问题空间向GA编码空间的映射称为编码,而有编码空间向问题空间的映射成为译码问题编码一般应满足以下三个原则1)完备性(completeness)问题空间中的全部点都能能成为GA编码空间中的点的表现型即编码应能掩盖整个问题空间2)健全性(soundness)GA编码空间中的染色体位串必需对应问题空间中的某一潜在解即每个编码必需是有意义的3)非冗余性(non-redundancy)染色体和潜在解必需对应在某些状况下,为了提高GA的运行效率,允许生成包含致死基因的编码位串,它们对应于优化问题的非可行解虽然会导致冗余或无效的搜寻,但可能有助于生成全局最优解所对应的个体所需的总计算量可能反而削减依据模式定理,DeJong进一步提出了较为客观明确的编码评估准则,称之为编码原理详细可以概括为两条规章1)有意义积木块编码规章编码应易于生成与所求问题相关的短距和低阶的积木块2)最小字符集编码规章编码应采纳最小字符集,以使问题得到自然、简洁的表示和描述.二进制编码1)连续实函数的二进制编码设一维连续实函数采纳长度维L的二进制字符串进行定长编码,建立位串空间S={12,…}%=(442…,火,W{°,1}A=12-K;7=12-L;K=2l其中个体的向量表示为%=(如*2…,,其字符串形式为Sr=%42…S#称为个体为对应的位串表示精度为Ax=(吁〃)/
(21)将个体又位串空间转换到问题空间的译码函数「{01产的公式定义为对于n维连续函数/(现》=区々…居)七g[wvJ(/=12•••«)各维变量的二进制编码位串的长度为,,那么x的编码从左到右依次构成总长度为L=•的二进制编码位串相应的GA编码i=i空间为SJ{《,生,…,%},K=2l该空间上的个体位串结构为对于给定的二进制编码位串位段译码函数的形式为Xj=「(a%,%)=ui+力:(:以,7)1=12n,-1j=\采纳二进制编码的GA进行数值优化时,可以通过转变编码长度,协调搜寻精度和搜寻效率之间的关系2)组合问题的二进制编码在很多组合优化问题中,目标函数和约束函数均为离散函数,采纳二进制编码往往具有直接的语义,可以将问题空间的特征与位串的基因相对应.其他编码1)大字符集编码2)序列编码3)实数编码4)树编码5)自适应编码6)乱序编码7)二倍体和显性规律LawrenceDavis等学者主见采纳的编码对问题来讲应当时最自然的,并可以据此设计能够处理该编码的遗传算子群体设定遗传算法的两个主要特点之一就是基于群体搜寻的策略,群体的设定,尤其是群体规模的设定对遗传算法性能有着重要的影响这中间包括两个问题1)初始群体如何设定;2)进化过程中各代的规模如何维持?.初始群体的设定遗传算法中初始群体中的个体是按肯定的分布随机产生的,一般来讲,初始群体的设定可以采纳如下的策略1)依据问题固有学问,设法把握最优解所占空间在整个问题空间中的分布范围,然后,在此分布范围内设定初始群体2)先随机生成肯定数目的个体,然后从中挑出最好的个体加入到初始群体中这一过程不断重复,直到初始群体中个体数达到了预定的规模.群体规模的设定依据模式定理,若群体规模为M则遗传操作可从这M个个体中生成和检测仅9个模式,并在此基础上不断形成和优化积木块,直到找到最优解明显M越大,遗传操作处理的模式就越多,生成有意义的积木块并渐渐进化为最优解的机会就越高换句话说,群体规模越大,群体中个体的多样性越高,算法陷入局部最优解的危急就越小此外,群体规模太小,会使遗传算法的搜寻空间分布范围有限,因而搜寻有可能停止在未成熟阶段,引起未成熟收敛(prematureconvergence)现象但是,从计算效率来看,群体规模越大,其适应度评价次数越多,计算量也就越大,从而影响算法的效率讨论表明,在二进制编码的前提下,为了满足隐并行性,群体个体数只要设定为2成即可,L为个体串长度这个数比较大,实际应用中群体规模一般取几十〜几百适应度函数评价函数遗传算法在进化搜寻中基本不用外部信息,仅用目标函数即适应度函数为依据遗传算法的目标函数不受连续可微的约束且定义域可以为任意集合对适应度函数的唯一要求是,针对输入可计算出能加以比较的非负结果比例选择算子需要需要强调的是,适应度函数值是选择操作的依据,适应度函数设计直接影响到遗传算法的性能.目标函数映射成适应度函数对于给定的优化问题,目标函数有正有负,甚至可能是复数值,所以有必要通过建立适应度函数与目标函数的映射关系,保证映射后的适应度值是非负的,而且目标函数的优化方向应对应于适应度值增大的方向1对最小化问题,建立如下适应函数和目标函数的映射关系其中,Cm可以是一个输入值或是理论上的最大值,或者是当前全部大或最近K代中gx的最大值,此时C3随着代数会有变化2对于最大化问题,一般采纳以下映射其中,Gin可以是一个输入值,或者是当前全部代或最近K代中gx的最小值.适应度函数定标在遗传进化的初期,通常会消失一些超常个体,若按比例选择策略,这些特别个体有可能在群体中占据很大的比例,导致未成熟收敛明显,这些特别个体因竞争力太突出,会掌握选择过程从而影响算法的全局优化性能另以方面,在遗传进化过程中,虽然群体中个体多样性尚存在,但往往会消失群体的平均适应度已接近最佳个体适应度,这时,个体间的竞争力相像,最佳个体和其它个体在选择过程中有几乎相等的选择机会,从而使有目标的优化过程趋于无目标大的随机搜寻过程对未成熟收敛现象,应设法降低某些特别个体的竞争力,这可以通过缩小相应的适应度值来实现对于随机漫游现象,应设法提高个体间的竞争力差距,这可以通过放大相应的适应度值来实现这种适应度的缩放调整称为适应度定标1线性定标linearscalingf=af+b2截断sigmatruncation3乘薄标尸4指数定标f=exp~bf遗传算子遗传操作是模拟生物基因遗传的操作包括三个基本遗传算子geneticoperator选择,交叉和变异这三个遗传算子具有一些特点1这三个算子的操作都是在随机扰动状况下进行的换句话说,遗传操作是随机化操作,因此,群体中个体向最优解迁移的规章是随机的需要强调的是,这种随机化操作和传统的随机搜寻方法是有区分的遗传操作进行的是高效有向的搜寻,而不是如一般随机搜寻方法所进行的无向搜寻2遗传操作的效果和所取的操作概率、编码方法、群体大小,以及适应度函数的设定亲密相关3三个基本算子的操作方法和操作策略随详细求解问题的不同而异或者说,是和个体的编码方式直接相关
1、选择selection算子从群体中选择优胜个体,淘汰劣质个体的操作叫选择选择算子有时又称为再生算子reproductionoperatoro选择即从当前群体中选择适应度值高的个体以生成配对池matingpool的过程为了防止由于选择误差,或者交叉和变异的破坏作用而导致当前群体的最佳个体在下一代的丢失,DeJong提出了精英选择elitistselection策略和代沟的概念Holland等提出了稳态选择steady-stateselection策略下面一些概念可以用来比较不同的选择算法1选择压力selectionpressure最佳个体选中的概率与平均选中概率的比值2偏差bias个体正规化适应度与其期望再生概率的确定差值3个体扩展spread单个个体子代个数的范围4多样化损失lossofdivcrsity在选择阶段末选中个体数目占种群的比例5选择强度selectionintensity将正规高斯分布应用于选择方法,期望平均适应度6选择方差selectionvariance将正规高斯分布应用于选择方法,期望种群适应度的方差1适应度比例选择是最基本的选择方法,其中每个个体被选择的期望数量与其适应度值和群体平均适应度值的比例有关,通常采纳轮盘赌roulettewheel方式实现这种方式首先计算每个个体的适应度值,然后计算出此适应度值在群体适应度值总和中所占的比例,表示该个体在选择过程中被选中的概率选择过程体现了生物进化过程中“适者生存,优胜劣汰”的思想对于给定的规模为n的群体P二{4生…,〃”},个体盯£P的适应度值为fcij其选择概率为经过选择操作生成用于繁殖的配对池,其中父代种群中个体生存的期望数目为当群体中个体适应度值的差异特别大时,最佳个体与最差个体被选择的概率之比选择压力业将按指数增长最佳个体在下一代的生存机会将显着增加,而最差个体的生存机会将被剥夺当前群体中的最佳个体将快速布满整个群体,导致群体的多样性快速降低,GA也就过早地丢失了进化力量这是适应度比例选择简洁消失地问题2Boltzmann选择在群体进化过程中,不同阶段需要不同地选择压力早期阶段选择压力较小,我们盼望较差地个体也又肯定地生存机会,使得群体保持较高地多样性;后期阶段,选择压力较大,我们盼望GA缩小搜寻邻域,加快当前最优解的改善速度为了动态调整群体进化过程中的选择压力,Goldberg设计了Boltzmann选择方法个体选择概率为其中,T0是退火温度T随着迭代地进行渐渐缩小,选择压力将随之上升T是掌握群体进化过程中选择压力的关键,一般T的选择需要考虑估计最大进化代数3排序选择排序选择方法是将群体中个体按其适应度值由大到小的挨次排成一个序列,然后将事先设计好的序列概率安排给每个个体明显,排序选择域个体的适应度值的确定值之间无直接关系,仅仅与个体之间适应度值的相对大小有关排序选择不采用个体适应度值确定值的信息,可以避开群体进化过程中的适应度标度变换由于排序选择概率比较简洁掌握,所以在实际计算过程中常常采纳,特殊是适用于动态调整选择概率,依据进化效果适时转变群体的选择压力最常用的排序选择方法是采纳线性函数将队列序号映射为期望的选择概率,即线性排序选择(linea门ankingselection)对于给定的规模为n的群体…,/},并且满足个体适应度值降序排列(生)之…之/(勺)假设当前群体最佳个体
④在选择操作后的期望数量为始,即;7+=nxA;最差个体围在选择操作后的期望数量为丁其它个体的期望数量按等差序列计算,==~——乙则77/=7--1)=+———(J-1)故现在排序选择概率n-1n-\为由£%=〃可以导出〃=2o要求Pj20〃0故1W〃Y2当球=2l=0时,即最差个体在下一代生存的期望数量为0群体选择压力最大;当〃+=7=1时,选择方式为按匀称分布的随机选择,群体选择压力最小4)联赛选择(tournamentselection)联赛选择的基本思想是从当前群体中随机选择肯定数量的个体(放回或者不放回),将其中适应值最大的个体放入配对池中反复执行这一过程,直到配对池中的个体数量达到设定的值联赛规模用q表示,也称q-联赛选择联赛选择与个体的适应度值由间接关系,注意适应度值大小的比较依据大量试验总结,联赛规模一般取q=2联赛选择的选择概率也是比较简洁掌握的,实际计算中也常常采纳,适用于在GA迭代过程中动态调整选择概率,将进化效果与群体选择压力联系起来讨论证明,当群体规模比较大时,联赛选择与排序选择的个体选择概率基本相同5)精英选择从GA的整个选择策略来讲,精英选择时群体收敛导优化问题全局最优解的一种基本保障假如下一代群体的最佳个体适应度值小于当前群体最佳个体的适应度值,则将当前群体最佳个体或者适应度值大于下一代最佳个体适应度值的多个个体直接复制到下一代,随机替代和替代最差的下一代群体中的相应数量的个体6)稳态选择DeJong将下一代群体中生成的与上一代不同的新个体所占的比例称为“代沟”(generationgap)o代沟越大,说明新个体的生成比例越高,群体正在搜寻新的编码空间稳态选择操作中,仅有少量个体按适应度值比例选择方法被选择,通过遗传操作生成新的个体新个体放回到群体中时,随机替代等量的旧个体,或者替代等量的最差的旧个体Holland将稳态选择方法应用于分类器规章学习中,最大程度继承已获得的规章,实现增量学习
2、交叉(crossover)算子交叉操作时进化算法中遗传算法具有的原始性的独有特征GA交叉算子时仿照自然界有性繁殖的基因重组过程,其作用在于将已有的优良基因遗传给下一代个体,并生成包含更简单基因结构的新个体交叉操作一般分为以下几个步骤1)从配对池中随机取出要交配的一对个体;2依据位串长度L对要交叉的一对个体,随机选取[1L7]中一个或多个整数k作为交叉位置;3依据交叉概率实施交叉操作,配对个体在交叉位置处,相互交换各自的部分内容,从而形成新的一对个体实现个体结构重组的交叉算子的设计一般与所求解的详细问题有关,任何交叉算子需满足交叉算子的评估准则,即交叉算子需保证前一代中优秀个体的性状能在下一代的新个体中尽可能得到遗传何继承此外,交叉算子设计和编码设计需协调操作1一点交叉one-pointcrossover一点交叉是由Holland提出的最基础的一种交叉方式一点交叉操作的信息量比较小,交叉点位置的选择可能带来较大的偏差positionbiaso依据Holland的思想,一点交叉算子不利于长距模式的保留和重组,而且位串末尾的重要基因总是被交换尾点效应,end-pointeffect故实际应用中采纳较多的是两点交叉位串A110111010位串B101110101位串A11010101位串B101110102两点交叉two-pointcrossover位串A111011|010位串B10|110|101位串A UlllOlOlO位串B lOlOlillOl3多点交叉multi--pointcrossover多点交叉是上述两种交叉的推广,有时又被称为广义交叉一般来讲,多点交叉较少采纳,由于它影响遗传算法的在线和离线性能多点交叉不利于有效保存重要的模式位串A11|01|10|10位串B10|11|01|01位串A11|11|10|01位串B10|01|01|104全都交叉全都交叉即染色体位串上的每一位按相同概率进行随机匀称交叉全都交叉算子生成的新个体位s\=ana\2---a\Ls]=21心2…心工,操作描述如下x是取值为[01]上符合匀称分布的随机变量Spears和DeJong认为全都交叉算子优于多点交叉算子,并提出一种带偏置概率的全都交叉
0.8%
0.5不存在多点交叉算子操作引起的位置偏差,任意基因位的重要基因在全都交叉作用下均可以重组,并遗传给下一代个体
3、逆转算子在自然遗传学中有一种称作倒位的现象,在染色体中有两个倒位点,在这两点之间的基因位置倒换,使得那些在父代中离得很远得基因位在后代中紧靠在一起在GA中相当于重新定义基因块使染色体位串上得重要基因更加紧凑,更不易被交叉算子所分裂仿照此现象,Holland提出了逆转算子逆转操作首先在个体位串上随机地选择两个点,位串染色体被这两个点分成三段,将中间段的左右挨次倒转过来与另两段相连,形成新的个体位串比如长度为10的二进制位串,其中下划线标示的等位基由于重要基因包」1101了01,是倒位位置)经倒位后变为11011101新的位串中重要基因更为靠近,被单点交叉算子分别的可能性大大降低了逆转算子一般要求采纳类似于乱序编码的带基因位标号的染色体结构比如,长度为10的位串位串1011101101依据上述方法实施逆转操作后,编号也随之翻转位串1011011101这样倒位操作就不会影响个体位串的适应值计算但是,逆转算子对交叉算子有肯定影响考虑下列AB位串之间的单点交叉位串A1011101101位串B1011011101若简洁地将第4个基因位以右的部分位串进行交换,得到位串A1011011101位串B1011101101两个子代位串中第
3、4和
7、8位基因在A、B中重复或遗漏,导致子代个体中包含冗余或不完整的遗传信息为解决此问题,一般遵循五种交换规章1)严格同序交换,只允许同序位串才能交换2)生存性交换,允许不同序位串进行交换,假如子代码串不包含完整的遗传信息,则不把它们放入新一代群体中3)任选方案交换,随便选择两个位串,并将其中任何一个指定为主序位申,另一个位串则按主序位串的次序映射,然后再进行通常的交换,这样保证了交换结果的合法性4)最佳方案交换,与任选方案交换基本相同,只是将两个位串中适应值高的位串作为主序位串5)结构修复,对于两个子代位串中重复或短缺的基因,随机将重复的基因转变为缺省的基因,形成完整的位串结构目前,这五种原则在基于二进制编码的参数优化问题的GA求解中还很少采纳对于某些问题要求采纳具有显着物理含义的特殊编码方式,可以依据GA进化的困难程度适当应用
4、变异(mutation)算子变异操作模拟自然界生物体进化中染色体上某位基因发生的突变现象,从而转变染色体的结构和物理性状在遗传算法中,变异算子通过按变异概率p随机反转某位等位基因的二进制字符值来实现对于给定的染色体位串s=q生…%详细如下:生成新的个体s=%…4其中,Xi是对应于每一个基因位产生的匀称随机变量,e
[10]o变异操作作用于个体位串的等位基因上,由于变异概率比较小,在实施过程中一些个体可能根本不发生一次变异,造成大量计算资源的铺张因此,在GA详细应用中,我们可以采纳一种变通措施,首先进行个体层次的变异发生的概率推断,然后再实施基因层次上的变异操作一般包括两个基本步骤1)计算个体发生变异的概率以原始的变异概率P为基础,可以计算出群体中个体发生变异的概率给定匀称随机变量为若]2(%)则对该个体进行变异,否则表示不发生变异2)计算发生变异的个体上基因变异的概率由于变异操作方式发生了转变,被选择变异的个体上基因的变异概率也需要相应修改,以保证整个群体上基因发生变异的期望次数相等传统变异方式下整个群体基因变异的期望次数为nxLxp设新的基因变异概率为〃;,新的变异方式下整个群体基因变异的期望次数为(77X/7wi(«.))X(Lx^w)0要求两者相等,即可以导出p^n=-^-=位串越短,越比大当位串长度趋PmSj)1-(1-〃切)于无穷大时,两者相等,即传统变异方式下的计算量为nXL新的变异方式下的计算量nXp;XZ计算量差异为nXL义(1一口(电)),明显新的变异方式比传统方式计算量降低了,且随着位串长度的增大而下降但是这种新变异方式也在肯定程度上偏离了原来的变异基因位在全部群体个体基因位中的匀称分布的状况,当群体比较小时,可能会带来肯定的变异误差从第t代群体中由选择、交叉所生成的交配池中,依次选择个体进行随机变异操作的一般形式表示为P-,(t)『(P-(t)Pm)变异操作按肯定的概率以对位串上的某些基因位的值进行变异,即1变为0或0变成1为了保证个体变异后不会与其父体产生太大的差异,变异概率一般取值较小,以保证种群进展的稳定性当交叉操作产生的后代个体的适应值不再比它们的前辈更好,但又未达到全局最优解时,就会发生成熟前收敛或早熟收敛(Prematureconvergence)这时引入变异算子往往能产生很好的效果一方面,变异算子可以使群体进化过程中丢失的等位基因信息得以恢复,以保持群体中的个体差异性,防止发生成熟前收敛;另一方面,当种群规模较大时,在交叉操作基础上引人适度的变异,也能够提高遗传算法的局部搜寻效率在群体进化的整个过程中,交叉操作是主要的基因重组和群体更迭的手段,变异操作的作用是其次位的,变异算子仅仅充当背景性的角色(backgroundrole)o针对详细问题以及为了便于对进化过程实施掌握,在标准变异算子的基础上,又引人了其他类型的变异算子,比如特定有效位变1***o*****o*f002***0*****1*f013***1*****0*f104***]*****1*fll。