蜂群遗传算法的研究(硕士学位论文)

xbbg

贡献于2013-11-26

字数:0 关键词:

分类号⋯TP3.fll石⋯⋯⋯⋯UDC密级学号200301305延边大学硕士掌位论文蜂群遗传算法的研究研究生姓名吴迪培养单位延边大学指导教师姓名、职称崔荣一教授掌科专业计算机应用技术研究方向智能信息处理论文提交日期2006年5月25日 延边大学工学硕士学位论文摘要遗传算法(GeneticAlgorithm,简称GA)是20世纪70年代由Holland提出的一种模仿生物进化过程的有效的优化方法,能根据已有的知识积累,按照概率寻优机制进行全局搜索未知空间,而且还可以根据问题的不同进行变通,所以得到了广泛的应用。但是,传统遗传算法存在着早熟收敛和收敛速度慢的缺点,这是由算法的两个主要因素“选择压力”和“种群多样性”造成的。所以国内外的学者们通过各种改进研究来平衡它们之间的矛盾,虽然各种改进的遗传算法取得了一定的成就,但多是局限在某一个方面,没有从总体上进行把握。而且,它们偏重于应用,缺乏收敛性和有效性方面的理论证明。本文针对传统遗传算法存在“种群多样性”和“选择压力"之间矛盾的问题,提出一种基于自然界蜂群繁殖原理的改进遗传算法一蜂群遗传算法(Bee.SwarmGeneticAlgorithm,简称BSGA)。蜂群是由蜂后、雄蜂和工蜂组成的,BSGA主要操作算子包括蜂后和雄蜂的绝对交配权,蜂后和工蜂的相似性抑制,蜂后的模拟退火局部寻优机制,雄蜂和蜂后的自适应交叉算子以及工蜂的自适应变异算子。其次,通过对马尔科夫链模型和遗传机制的分析,证明了蜂群遗传算法的收敛性和有效性。最后通过对几个经典函数的优化以及Ⅳ皇后问题(ⅣP难)的组合优化实验验证了该算法具有较好的搜索性能和较少的计算量。关键词遗传算法:绝对交配权;自适应交叉;自适应变异 ABSTRACTGeneticAlgorithmwasproposedin1970sbyprofessorHolland·It1Sane舵ctiveoptimizationmethodtostimulatetheevolutionofnature·BasedontheaccUlTIulatedknowledge,GAcannotonlygloballysearchtheunkrlownspacebYprobabilitysearchingmechanism,butalsochangebythedifferentproblem,soitiswidelyapplied.However,thetraditionalGAhasthedisadvantageofdealingwiththeslowerrateandprematureconvergence,causingbythecontradlctlonbetweenpopulationdiversityandpressureofselection.Somanydifferentmethodsareproposedtobalancetheircontradiction.AlthoughalotofimproVedGAsmakeprogress,itstillhassomelimitations·Bee-Swarmgeneticalgorithmbasedonreproducingofswarm1sproposed1nthisthesis,tosolvethecontradictionbetweenpopulationdiversityandpressureofselection.Thesw砌iscomposedofqueenbee,dronesandworkerbees,tnemainoperatorsofthealgorithmincludetheabsolutematingrightbetweenqueenbeeanddrones,thesimulatedsuppressionbetweenqueenbeeandworkerbees,localoptimizationofqueenbeebasedonsimulatedannealing,adaptivecrossoVerbetween.dronesandqueenbee,adaptivemutationofworkerbee·ThentheconVergenceandvalidityareprovedbytheanalysisofMarkovmodeandgenetlcmechanism.Finally,thesimulationresultsabouttheoptimizationoftimetlonsandcombinationaloptimizationaboutN—queenproblemshowthatithasbothvalidityandlesscomputationalmagnitude.KeywordsGeneticalgorithm;Absolutematingright;AdaptiVecrossoVer;Adaptivemutation—II— 延边大学工学硕士学位论文第1章绪论1.1研究的目的和意义在自然界中,很多的自然演化现象给了人们启示:生物和自然界以自己的方式经过演化,解决了人们认为很难实现的优化问题。近年来,对自然界演化现象的研究与应用已经成为了人工智能领域的一大热点。通过对生物自然选择的进化过程、对蚂蚁群寻找食物的路径寻优、对鸟群飞行的研究、对人类的免疫系统的研究以及对生物的神经网络的研究,计算机学者们分别提出了遗传算法、蚁群算法、粒子群算法、免疫算法以及人工神经网络等人工智能新的研究领域。搜索是数字计算机解题的基本思路,各种搜索算法的研究构成了计算机科学的理论基础。遗传算法的另一个特点是算法简单而又具有全局优化的趋势,可以自动克服一般搜索中陷入局部极值的困难问题,因而遗传算法己成为人工智能中的基本方法。因此,遗传算法的发展(包括各种新型的遗传算法)具有更加突出的科学意义和使用价值。自Holland创立遗传算法以来,除了早期的GA研究工作n叫3在模式定理、积木块假设理论和并行性理论上有所进展外,文献中绝大多数是GA的各种应用文章。GA应用的方向很多,几乎无所不包。最近10多年来,各种改进的遗传算法层出不穷。但是各种改进算法大多是局限于某一个方面的改进,而且缺乏理论证明。因此本课题在遗传算法的改进和理论证明以及应用上开展了深入的研究,对遗传算法的进一步发展具有重要的意义。1.2研究的现状和内容遗传算"法(GeneticAlgorithm,简称GA)是20世纪70年代由美国的Holland提出的模拟生物进化过程的优化方法,它的主要思想是基于C.R.Darwin的生物进化论矛I:IG.Mendel的遗传学。遗传算法结合TDarwin的适者生存理论和随机交换理论。适者生存消除了解中的不适应因素,随机交换理论利用了原有解中的 延边大学工学硕士学位论文已有知识,从而加速了对优化解的搜索过程。遗传算法经历了如下的发展阶段:(1)遗传算法萌芽期。早在20世纪50年代和60年代,就有计算机科学家进行了“人工智能优化系统”的研究,早期的研究形成了现在遗传算法的雏形。1967年,Bagley发表了关于遗传算法应用的第一篇论文,首次提到了“遗传算法”这个名称。(2)遗传算法发展期。20世纪60年代中期之后,Holland于1975年出版了其开创性著作《自然界和人工系统的适应性》(AdaptationinNaturalandArtificialSystems),该书提出了遗传算法的基本定理一模式定理,为遗传算法奠定了理论基础,也标志着遗传算法的正式诞生。1989年,David.Goldberg/出版了《搜索、优化和机器学习中的遗传算法》(GeneticAlgorithmsinSearchOptimizationandMachineLearning),该书全面系统地总结了当时关于遗传算法的研究成果,奠定了现代遗传算法的基础。f3)20世纪90年代以后,遗传算法更是向着广度和深度的方向发展,不论在算法设计、算法应用以及基础理论方面都有了长足的发展。1992年,Michalewicz出版了一本很有影响力的著作《遗传算法+数据结构=进化程序》(GeneticAlgorithms+DataStructures=EvolutionPrograms),深入的讨论了遗传算法的专门问题,对遗传算法应用于最优化问题起到了推波助澜的作用。同时,很多的学者们都开始重新研究遗传算法的基本问题,DeJong称为“重访基本的假设"。由于遗传算法在应用研究方面的长处主要得益于其求解的有效性、现有仿真环境下易于实现、可扩充性和易于与其他方法相结合,因此可以预料在不远的将来,随着理论研究的不断深入和应用领域的不断拓广,遗传算法将取得长足的发展。遗传算法的研究主要包括3个领域:遗传算法的理论和技术;用遗传算法进行优化;用遗传算法进行分类系统的机器学习∞1。遗传算法广泛应用于很多学科。下面是遗传算法的一些主要应用领域。(1)函数优化问题:遗传算法的经典应用领域,也是对各种遗传算法性能评测的常用算例阳·71。很多人构造出了各种各样的复杂形式的测试函数,有连续函数也有离散函数,有凸函数也有凹函数,有低维函数也有高维函数,有单峰函数也有多峰函数等。而对于这些函数优化问题,用其他优化方法较难求解,遗传算法却可以方便地得到较好的结果。(2)组合优化问题:随着问题规模的扩大,组合优化问题的搜索空间急剧扩大,有时在目前的计算机上用枚举法很难或者甚至不可能得到其精确最优解。 延边大学工学硕士学位论文对于这类复杂问题,人们已意识到应把精力放在寻求其满意解上,而遗传算法则是寻求这种满意解的最佳工具之一。例如,遗传算法已经在求解旅行商问题∞·9l、背包问题、装箱问题、图形划分问题等方面得到成功的应用。(3)数据挖掘问题:数据挖掘数据库技术,能够从大型数据库中提取隐含的、先前未知的、有潜在应用价值的知识和规则。许多数据挖掘问题可看成是搜索问题,数据库看作是搜索空间,挖掘算法看作是搜索策略。因此,应用遗传算法在数据库中进行搜索,对随机产生的一组规则进行进化从而挖掘出隐含在数据库中的规则n们。(4)机器学习:学习能力是高级自适应系统所具备的能力之一,基于遗传算法的机器学>--j口1,特别是分类器系统,在很多领域中都得到了应用。例如,遗传算法被用于学习模糊控制规则,利用遗传算法来学习隶属度函数,从而更好地改进了模糊系统的性能。(5)图像处理和模式识别问题:图象处理和模式识别是计算机视觉中的一个重要研究领域。目前己在图像压缩n¨、图象恢复、图象分割n引、几何形状识别u副等方面得到了应用。(6)人工生命问题:’人工生命是用计算机等人工媒体模拟或构造出具有自然生物系统特有行为的人造系统。人工生命与遗传算法有着密切的关系,基于遗传算法的进化模型是研究人工生命现象的重要理论基础。虽然人工生命的研究尚处于启蒙阶段,但遗传算法己在其进化模型、学习模型、行为模型等方面显示了初步的应用能力。本学位论文主要是研究遗传算法的前两个领域,首先我们修改算法的某些元素以得到算法的理想形式,提高遗传算法的性能;然后使用修改过的遗传算法来解决不同的问题,同时修改遗传算法的参数状态使之对该问题有针对性。本课题仿照自然界生物进化规律和繁殖现象,结合以上种种改进遗传算法的优点,针对遗传算法的不足之处,研究一种优化的混合遗传算法一蜂群遗传算法(Bee.SwarmGeneticAlgorithm,简称BSGA)。蜂群遗传算法仿生原理简单,通过两个不同性别种群之间的互利共生,弥补各自的缺陷,能够产生个体单独进化时很难获得的特性。引入其他的优化算法以增强遗传算法的寻优能力,而且通过改进的遗传算子解决了“选择压力"和“种群多样性”之间的矛盾。收敛性是指算法能够收敛到最优解,有效性是指算法能够迅速找到最优解,本文在理论上证明了所提出算法的收敛性和有效性,并且估计蜂群遗传算法的时间复杂度和空间复杂度。最后通过函数优化实验和组合优化实验,证明了算法的正确性。. 延边大学工学硕士学位论文1.3主要创新点本文的主要创新点在于:(1)基于自然界的蜂群繁殖原理,群体按照性别分开,只有不同性别的个体才可以交叉。而且只有雌蜂群中的最优个体一蜂后拥有和雄蜂群交配的权利。(2)算法的交叉率随着个体的适应度动态变化,并且增加了交叉次数算子,以提高迭代速度,既保证迭代速度又可以保证种群的多样性。(3)算法采用自适应变异率和动态变化的变异范围,既能保证较好的解,在局部进行精细搜索;又可以及时跳出局部最优解的范围,找到全局最优解的可能性较大。(4)给出蜂群遗传算法的理论证明,证明了该算法的收敛性。并通过遗传机制的分析,证明了该算法的有效性。最后简要说明了算法的复杂度。1.4章节安排本文的后续章节安排如下:第二章介绍了经典遗传算法的基本原理和分析了理论基础。并总结了前人对遗传算法所做出的种种改进,分析了与传统遗传算法的不同,在一定程度上提高了遗传算法的性能,并指出了他们的不足之处。第三章对本文提出的蜂群遗传算法作了详细的说明,阐述了其生物学基础,并分析了蜂群遗传算法的运行过程,指出了改进之处。第四章首先对蜂群遗传算法作了理论证明,证明了蜂群遗传算法的收敛性,并分析了蜂群遗传算法的遗传机制。接着通过matlab编程,用4个经典的函数优化实例,验证了算法的有效性和合理性。最后,用蜂群遗传算法解决了传统的组合优化问题一八皇后问题。最后是本文的结论。归纳了本文的工作,指出了蜂群遗传算法的优缺点,并指明了进一步努力的方向。“’ 延边大学工学硕士学位论文2.1引言第2章遗传算法本章首先介绍经典遗传算法的定义,从遗传算法的编码方式、群体规模、终止条件、性能指标、遗传算子和适应度函数方面对经典遗传算法进行了描述。然后介绍了遗传算法的三大理论基础:模式定理、积木块假设和隐含并行性定理。最后从三个方面总结了从20世纪90年代以来人们对经典遗传算法的种种改进:结合其它优化算法的改进遗传算法,如结合免疫算法、模拟退火算法等等;模拟自然现象的改进遗传算法,如由随机杂交改为按性别杂交、有目的的控制高适应度个体和其它个体配对等等;修改内部元素的改进遗传算法,如针对不同的问题修改编码方式、修改遗传算子、群体模式、交叉变异率、并行进化方式等等。2.2经典遗传算法“,、%I、”,“2.2.1遗传算法的描述简单遗传算法(SimpleGeneticAlgorithm,简称SGA),种群采用二进制编码方式,通过轮盘式选择算子、随机交叉算子、变异算子的不断进化,通过适应值函数来评价个体,最终可以得到较优解或最优解。2.2.1.1编码方式个体编码格式不仅决定遗传算法的求解精度和搜索空间,而且决定着对原问题的翻译和理解。‘I遗传算法一般不直接处理待优化问题的参数,而是将它们转换成由基因按一定结构组成的染色体或个体,即转化为对参数编码的处理。由于目前还没有一套完整的指导理论及评价标准能够帮助我们设计编码方案。作为参考,DeJong曾提出两条操作性强的实用编码原则:l(有意义积木块编码原则):应使用能易于产生与所求问题相关的具有低阶、短定义距模式的编码方案; 延边大学工学硕士学位论文2(最小字符集编码原则):应使用能使问题得到自然表示或描述的具有最小编码字符集的编码方案。简单遗传算法编码采用二进制的0/1字符编码。编码串长度的选取和求问题的精度有关。问题简单时,每一位0/1变量代表某个性质。问题性质要用数值描述时,涉及二进制与十进制的转换。对长度(位数)为,的0/1字符串,十进制数与二进制数有如下关系:-y一-yx=‰i。+垒浮×Dec(y)(2-1)Z—l其中,Xmi。,X。。为变量的范围,Y为对应X的二进制数,Dec表示把二进制数转化为十进制数。2.2.1.2种群规模群体规模是影响遗传算法性能的重要因素之一,群体大小I"l应该较大。这样,遗传操作所处理的模式较多,生成有意义的基因块并且逐步进化为最优解的机会就会高,算法陷入局部解的危险就小。但是,群体规模大,算法计算量就会增加。2.2.1.3终止条件由于遗传算法不利用目标函数的梯度信息,因此遗传算法无法自己确定算法是否收敛,或什么时候得到最优解。最简单的办法就是确定运行代数或达到两代之间的精度要求。2.2.1.4性能指标算法性能指标,1全局收敛率。用以反映收敛效率,即算法成功找到全局最优解的的次数;2收敛代数及收敛时间。分别表示算法收敛时种群进化代数的平均值及算法收敛所用时间的平均值,用以反映收敛的快慢。2.2.1.5遗传算子经典遗传算法主要包括以下三个遗传算子:选择算子、交叉算子和变异算子。遗传操作是决定遗传算法性态的核心,特别是选择操作决定算法的演化速度,交叉算子、变异算子和初始群体既决定着算法的搜索空间,又决定着算法的全局优化性态。轮盘选择算子(RouletteWheelSelectionOperator):某个体被选择的概率与其适应值成正比,计算公式如下:,B=寻L(2—2)∑Zi=1这种方法显然适应值大的串入选的概率大,是一种放回去的选择,即大的 延边大学工学硕士学位论文个体可以再次选中进行交叉’、变异操作,将其中的优质基因遗传给子代。但是选择算子只是在一个固定的种群中进行选择,选择的结果不可能跑到种群之外,选择的结果依赖于初始种群。交叉算子(CrossoverOperator)是指把两个父代个体的部分结构加以替换重组而生成新个体的操作,适应度有可能比父代还高。交叉被认为是遗传算法中起核心作用的遗传算子。交叉算子的结果可能在种群之中,也可能在种群之外,交叉算子扩大了搜索空间。变异算子(MutationOperator)是个体空间到个体空间的随机映射,其作用方式为独立的以概率P。改变个体分量取值。‰称为变异概率,指染色体某位基因突变,从而改变该个体的结构和物理性质。变异算子可以变换搜索空间,扩大种群多样性。2.2.1.6适应度函数对于一个体产生的效益称为适应值。遗传算法使用适应度函数来评估和引导搜索,通常对适应度函数进行适当的变换可以有利于搜索。适应度函数如下:(1)原始适应值函数:直接将所要优化的目标函数fix)作为适应值函数F(X)。(2)标准适应值函数:对于求最大值问题,作下列转化为聃∥峨iI:笋您嚣劣p3,对于求最小值问题,作下列转换为肿仔√@≯j;!:笔髦p4,(3)线性尺度变换,公式如下:F。=aF+b(2.5)总之,适应值函数这一性质是演化计算得以正常进行的关键因素,计算方法可以根据问题的不同性质进行设计和完善。在设计过程中既要考虑到它表征群体中不同个体对环境的适应能力,决定着复制结果,又要考虑多样性群体演化对于问题解决的不可忽视作用。●tLr■,,-■【■■■■【Ir■r-■■■r-■r●■I『■●■r■■■■■■■■L■I 延边大学工学硕士学位论文2.2.2遗传算法的理论基础遗传算法提供了一种求解复杂系统优化问题的通用框架,隐含并行性和全局搜索特性是它的两大显著特征,而且这是一个以适应度函数(或目标函数)为依据,通过对群体个体施加遗传操作实现群体内个体结构重组的迭代处理过程。本节介绍了遗传算法的基本定理,这些主要原理是以后各章研究的理论基础。2.2.2.1模式定理Holland在1975年引入模式(Schema)的概念,在遗传算法的理论分析中有很重要的意义。定义2-1设q∈{0,1),1≤ik0step2:进行随机热扰动生成解/∈N(i),计算△F=F(/)一F(i),依Metropolis准则接受(或舍弃),。即若△,>0,则f-.,,否则若exp(一△F/T)>rcl挖d时,则持J(其中Ⅳ(f)cS为f的邻域)。Step3:若在此温度T迭代过程已经稳定,即已达到热平衡,则转Step4:否则,转Step2。Step4:若满足算法终止准则,即退火过程结束,则输出最优解i,:f,算法.on终止:否则,按一定方式降低温度,即T=T一△T/,T>0,转Step2。很多文献心o,2门都是直接利用模拟退火算法的局部寻优能力强的特点对遗传算法得出的解进行进一步的优化。2.3.2模拟自然现象的改进遗传算法模拟自然界现象,来改进遗传算法。下面介绍几个主要的的改进算法。根据“鹰和鸽子策略”中强者和弱者的搭配符合一定比例,能达到进化的稳定性的结果,文献【15】引入新的遗传算子一在稳定参数下的突变算子,使得每一代优秀个体的比例维持在一个稳定值,既减轻了选择压力保持了种群多样性,同时又扩大了搜索空间。但是该算法需要根据问题的不同,通过实验确定不同的稳定参数,通用性较差。根据猴子群体中,猴王享有绝对交配权的现象,文献[22】提出了一种猴王遗传算法。其实遗传算法在交叉过程中,随机选择个体进行配对难以控制,如果能控制选择适应度高的个体和其它适应度的个体配对,则在每一代演化过程中都能充分发挥不同基因配合的作用。自然界的生物进化过程中,生物由无性繁殖发展到了今天大多数生物的有性繁殖,这种现象说明基因互补比完全的克隆选择拥有更强的生命力∽3’241。生物学上,小生境是指特定环境下的一种组织结构。在自然界中,往往特征、形状相似的物种相聚在一起,并在同类中交配繁衍后代。基于这种小生境的遗传算法(NichedGeneticAlgorithms,NGA),可以更好的保持解的fIl}r;:-●,●。l}●l,●}0,;●f●●●;●●●,0●●--.1●●,▲--rI-●--I 延边大学工学硕士学位论文多样性,同时具有很高的全局寻优能力和收敛速度,特别适合于复杂多峰函数的优化问题心引。Goldberg等在1987年提出了基于共享机制(Sharing)的小生境实现方法。这种实现方法的基本思想是:通过反映个体之间的相似程度的共享函数来调节群体中各个个体的适应度,从而在这以后的群体进化过程中,算法能够依据这个调整后的新适应度来进行选择运算,以维持群体的多样性,创造出小生境的进化环境。2.3.3修改内部元素的改进遗传算法遗传算法内部元素的调整以达到算法的理想形式,满足问题的本质乜引。许多研究者从针对实际问题修改编码、修改遗传算子、群体模式、并行进化等方面对遗传算法进行了改进。如文献[27]中介绍了Schraudolph等提出的动态编码策略,即动态的改变特征变量的定义域。对早熟现象有一定的抑制作用;还有DeJong乜1提出的对轮盘式选择算子的几种变体;Whitly瞳田等人提出的基于“排名”的选择算子以及其它学者对交叉算子和变异算子进行的改进;还有根据进化的时间,来决定染色体变异的位置,可以达到算法执行初期较大的变异率和初始基因位的变异,全局搜索的目的,算法末期较小的变异率和编码后面的基因位较大的变异率,算法进行精细搜索的目的;对适应度函数进行尺度变换堙引,通过设计对个体的不同评价方法,调整控制群体结构和演化速度等等。具体说来,在遗传算法内部元素有如下改进:2.3.3.1选择算子(1)轮盘操作(RouletteWheel):某个体被选择的概率与其适应值成正比,计算公式如下:易:#(2-7)∑,i=1这种方法显然适应值大的串入选的概率大,是一种放回去的选择,即大的个体可以再次选中进行交叉、变异操作,将其中的优质基因遗传给子代。(2)最优保存策略(ElitistModel):思想是群体中适应值最高的个体不进行配对交叉直接复制到下一代中取代适应值最低的一个,前提是下一代中不存在该个体。这种方法的优点是进化过程的某一代最优解可以不被交叉或是变异破坏掉。但是,可能局部最优解的遗传基因会迅速增加而使进化陷入局 延边大学工学硕士学位论文部解,该方法全局搜索能力弱。(3)无回放余数随机选择(RemainderStochasticSamplingWithReplacement):先计算群体中每个个体在下一代中的期望生存数目Ni:FⅣ=M水音L(i=l,2,....M)(2-8)∑F,=l取[Ni】为对应个体在下一代中的生存数目,这样可以确定出下一代群体中MM∑[Ⅳ『】个个体。以F-tN,lE鼻/M为各个个体的新的适应度,然后用比例选i=1f=lM择的方法确定下一代中还没有确定的M一∑[Ⅳf]个个体。这样可以确保适应i=1度比平均适应度高的一些个体一定能够遗传到下一代中,选择误差小。2.3.3.2交叉算子(1)单点交叉(One.PointCrossover):随机选择两个父代个体,随机选择某一交叉点,把两个个体进行交叉,从而生成两个新的子代个体。(2)均匀交叉(UniformCrossover):均匀交叉是通过设置模块来决定子代的基因如何继承父代个体中的相应基因。设置的模块与父代串有相同的长度,其中0表示不交换,1表示交换,根据模块对两个父代串进行杂交产生后代。(3)算术交叉(ArithmeticCrossover):由两个个体线性组合而产生出两个新的个体。为了进行线性组合,算术交叉操作一般是由浮点数编码所表示的个体。首先生成m个随机数珥∈(O,1),f-l,2,...,m,执行杂交操作后产生子代为:xo=(爿,以,...,屯),xb=(订,以,...,《)∥=ql+(1-a,)#,订=ajx2,+(1一q)爿,i=l,2,...,聊(2—9)2.3.3.3变异算子(1)基本位变异(SimpleMutation):基本过程是对于后代个体的每个基因非常简单,基本过程是对后代的每一个基因产生一个随机数rand,如果rand厂(《))then%k=Xelse/f(exp(一1/t.)>rand)thenx:=xelsexkb2xkb其中,乙为退火温度,k是一定温度下的迭代次数。3.3.4工蜂群的自适应变异过程3.3.4.1工蜂群和蜂后的相似性抑制首先,蜂后要按照小生境技术中的排挤机制对工蜂群中的潜在蜂后进行相似性抑制。在自然界中,往往特征、形状相似的物种相聚在一起,并在同类中交配繁衍后代。Goldberg等在1987年提出了基于共享机制(Sharing)的小生境实现方法。这里把蜂后与工蜂群个体之间的海明距离作为一种共享函数,个体之间的密切程度主要表现为个体基因类型的相似性。工蜂群个体按照和蜂后的海明距离进行相似抑制,抑制阈值为丁。对于二进制编码的蜂群遗传算法,使用海明距离取代欧式距离计算两个个体之间的相似度,减少了计算的复杂度。具体抑制方法是,若是工蜂群中的个体和蜂后的海明距离D小于等于丁,那么对该个体突变。突变就是不保留母体的任何性质,产生一个新的个体,用来扩大搜索空间。海明距离公式为:。=痧(3-3)其中,,是染色体即个体的长度,彳匆是蜂后第f位的基因,B匆是工蜂的第i位基因。另外,若是算法采用二进制编码,那么使用海明距离作为衡量相似性的 延边大学工学硕士学位论文标准,简单易行;若是算法采用浮点数编码,那么用信息熵表示个体之间相似度的评价标准,可以比海明距离更能有效的表达解所包含的信息。假设染色体的每个基因表示的范围是离散的,每位基因共有s个字母:盔,如,...,缸。则两个染色体的信息熵为:/4(2)=÷∑q(2)(3—4)‘j=l其中:/4,(2)=∑-pf,logp口,Hj(2)为2个染色体第/位的信息熵,所为2个染色体中的第,位为字母砖的概率。因此,两个染色体之间的相似度为:11%2丽(3-5)3.3.4.2工蜂群个体的自适应变异最后,没有被抑制的个体按照和蜂后适应度的距离关系来动态确定其变异率和变异位置。原则是,适应度越大的个体,其变异率越低,变异的位置处于染色体的后面基因,反之,适应度越小,变异率越高,变异位置处于染色体的初始基因。因为适应度越大的个体越需要精细搜索,所以搜索范围限制在局部最优解附近,适应度越小的个体越是要跳离这个劣解范围,所以搜索范围扩大到整个区域。工蜂群主要是为了保持种群的多样性,避免早熟收敛。工蜂群当前个体变异概率P。。。m。公式如下:Pmwoman:1一掣+b(3-6)JqueenZ。。。为当前蜂后的适应度,b代表着最小变异概率。变异位置m公式如下:fm=P+rand宰,.,/f(md(2)一0)Im=P-rand宰,,/f(md(2)一1)(3-7)P=,木(1一P。。。。。)其中,r为变异半径。 延边大学工学硕士学位论文因为此时工蜂群体已经变化,所以按照3.3.2节的方法重新选择蜂后。重复上述过程,直到算法循环终止条件得到满足(如达到了预定的进化代数)为止。最后的蜂后即是最佳解。3.4蜂群遗传算法的描述综上所述,蜂群遗传算法描述为:Stepl:在函数定义域内,随机产生两个群体,雄蜂群和工蜂群,各有Ⅳ和M个个体。Step2:在工蜂群中选出适应度最大的为蜂后。Step3:雄性群体轮盘式选择,按照自适应交叉率,交叉次数和蜂后交叉,变异。Step4:工蜂群按照联赛选择的方法,把雌性后代和原工蜂群选择重组为M个个体的新工蜂群,重新选择蜂后。Step5:在蜂后的邻域内采用模拟退火机制进行寻优,直到达到平衡状态。Step6:对这个新的工蜂群体,实施蜂后排挤机制。对群体中的个体和蜂后的海明距离D在一定阈值之内的,个体突变。Step7:剩下的工蜂个体,按照适应度来确定染色体变异率和基因变异位置。然后重新选择蜂后。Step8:若算法终止条件不满足,转到Step2;否则,输出蜂后作为全局最优解。Step9:算法结束。3.5本章小结总之,本章主要采用了以下策略对算法进行了改进:、(1)最优保存策略。每一代的最优解不经过选择、交叉和变异操作直接保留到下一代,这就保证了算法的全局收敛性,而没有最优保存策略的遗传算法是不收敛的,在下一章中将得到证明。(2)绝对交配策略。通过最优个体即蜂后和其它雄峰的交叉操作,保证了在蜂后子空间的精细搜索,有利于及早找到最优解。(3)粗粒度并行策略。通过两个种群的相互促进,一个种群集中局部搜索, 延边大学工学硕士学位论文加速搜索进度,另一个种群集中全局搜索,扩大种群的多样性,通过蜂后两个种群相互联系。(4)局部搜索策略。通过搜索最优解效果比较好而且速度比较快的模拟退火算法来对蜂后进行进一步优化,找到蜂后邻域范围的局部最优解,加快算法的搜索速度。(5)小生境策略。通过小生境技术,保证蜂后的唯一性和扩大种群多样性。(6)自适应遗传算子策略。通过对遗传算法的交叉算子、变异算子、交叉率和变异率的自适应动态调整,既有利于保护优良模式,得到较高精度的解,也很好的解决了算法的过早收敛和震荡现象。 延边大学工学硕士学位论文第4章蜂群遗传算法的理论分析与算例4.1引言相对于遗传算法鲜明的生物学基础,其数学理论基础远远落后于算法的实际发展。模式定理和隐含并行性被看作是遗传算法的理论基石,后来又有了积木块假设。模式定理和积木块假设说明了遗传算法的寻优可能性和能力,但是遗传算法的早熟收敛现象,模式的度量以及遗传算法的欺骗问题等等都是无法解释的。隐含并行性还存在着严重的证明漏洞n4。。本章将在遗传算法理论的基础上,证明了蜂群遗传算法的搜索过程是有限时齐遍历马尔科夫链,具有全局收敛性;同时,讨论了择优交叉算子和自适应变异算子等对算法的作用;对算法的时间复杂性进行了估计。最后,本章对算法进行函数优化和组合优化实验证明,效果提高明显。4.2蜂群遗传算法的理论研究4.2.1预备知识定义4-1(个体和个体空间)所谓个体彳,即长度为z的0和1组成的字符串,简称个体;,称为个体的链长;个体的全体记作S={O,1)7,称为个体空间。定义4—2(基因和基因型)个体X=(Xl,X2,...,而)中占有一定位置的基本单位称为基因。个体中的该基因的其它基因称为互补基因,两个个体中位置相同的基因称为等位基因,基因的类型称为基因型。定义4.3(种群和种群空间)所谓种群是Ⅳ个个体组成的集合,简称种群。N称为种群规模,称S。Ⅳ={叉=(五,置,...,瓦),置∈S(f≤Ⅳ))为N种群空间。定义4-4(齐次种群)称N种群是齐次种群,若对于任意f,歹≤Ⅳ有墨=一, 延边大学工学硕士学位论文用∥“表不齐次种群的全体。定义4-5如果状态空间SN是有限集,则对于一切以,乃∈SⅣ马尔柯夫链一步转移概率0(尼,尼+1)与时间k无关,称这样的马尔柯夫链为齐次有限马尔科夫链。定义4-6一个以×力的方阵彳=【%]。(1)若对于所有的f,/,aU>0,称爿为严格正矩阵,记为4>0。(2)若对于所有的f,/,%≥0且至少有一个元素%>0,称A为正矩阵,记为A≥0。(3)若A≥0,3m∈N(自然数集合),使得彳”>0,则彳是正则的。(4)若么≥o,对于所有的i,∑吩--1,则么是随机的。(5)若彳通过行(或列)变换形成I≤;l的矩阵,其中c,丁都是方阵,则称彳是可约的,否则不可约的。(6)若么有相同的行,则么是稳定的。(7)若彳每一列至少有一个正的元素,则彳是列可容的。定理4-1么是n阶随机方阵口们(1)当且仅当.41=I,I是n阶全l方阵。(2)若B是n阶随机方阵,则么B也是随机方阵。定义4—7设{以;,z>=0)为有限齐次马尔科夫链,∥为,2步转移概率,若存在刀≥1,使得群>0,称状态i可达状态/,记i专/。否则f称不达/。若有两者互相到达,称为f和歹互通,记为iH歹【91。所有状态互达的马尔科夫链称为可约的。而一个可约的马尔科夫链状态转移矩阵P具有形式:I姜;I,其中c,丁都是方阵。 延边大学丁学硕士学位论文定义4-8称兀为状态i到-,的首达概率,PJ,=1称为i是常返的。若岛0所有n(n≥1)的最大公约数为1,则称状态i为非周期的。定义4.10~个正常返非周期的状态称为遍历状态。引理4-1若一个正则的齐次马尔科夫链随机转移矩阵P,则有极限概率矩阵limP。=P,其中P是”×疗的稳定的随机矩阵。“。4.2.2蜂群遗传算法的收敛性研究在遗传算法的进化过程中,群体空间中状态的转移概率是由复制、交叉和变异三种操作引起的,三种作用分别由概率矩阵S,C,M来描述,即遗传算法的马尔科夫链转移概率矩阵用P=SCM来表示。定理4-2简单遗传算法SGA的转移矩阵P是正则的,而且是遍历的。证明:令P=SCM。先证明是正则的。对状态丑,l∈∥,从状态^每个个体按比例复制到状态一,勺≥o,∑SO.=1,所以s是随机矩阵;状态丑通过交叉操作映射到状态■,丑^∈S“中个体交叉概率P。,不交叉的概率是卜p。,所以勺≥o,∑cF=P。+1一P。=1,所以c是随机矩阵:状态丑与乃之间的海明距离日(丑,■),于是变异概率矩阵为mlj=《(1一砖)>0,所以M为严格正矩阵。令A=SC,P=一M由定理r4-1得知,P是随机矩阵,且助=∑‰%>0,所以P>0,从而P是严格正k=l矩阵,自然也是正则矩阵。由于P是严格正的有限齐次马尔科夫链随机转移矩阵,所以P是常返的:且P是正则的,对任意的k≥1时,砖>0都成立, 延边大学工学硕士学位论文每个状态都是非周期的:所以每个状态都是遍历的。由以上分析得知,SGA不论初始分布如何,由引理4—1得存在唯一极限户,且由P>0斗P>0,SGA可以遍历所有的状态,但所有的状态的极限概率均小于l,所以SGA能发现最优解,但不能保留最优解。定理4.3BSGA是收敛的。证明:在SGA中每一代的最优个体,即蜂后是被保留下来的,所以当代群体中的蜂后以概率l复制到下一代中。设概率矩阵尸各个状态按照降序排列:第一个状态为全局最优解;第二个状态为全局次优解,⋯⋯,第Ⅳ个状态为全局最差解。于是P可以变为:P:Fcol:LAljlO⋯Onljk2⋯0pMpN2⋯PNN,R,T≠0,由P的分析可知,BSGA是可约随机矩阵,C=[1】1是一阶严格正的随机矩阵。则rC0],,{imPk=熙l芝丁,Rct一。丁。l2[≤:。0](。一·)由于C”=1,也就是一旦状态进入最优状态,将以概率1处在其中,不能跳出来。所以,BSGA不仅具有发现最优解的能力,还能够把最优解保留下来,可见是全局收敛的。4.2.3择优交叉算子分析虽然BSGA可以收敛到全局最优解,所达到的结果,实际运算中是不可行的。蜂群遗传算法采用轮盘选择算子。但从理论上是进化代数趋于无限时所以算法必须在有限代内结束。定义4-11(选择算子)选择算子即是在一个种群中选择一个个体,它是随机映射五:S”斗s特别的,按照概率规则P{芽(叉):墨):{盟,选∑f。(五)k=l择个体的方式称为适应值选择算子。其中,,(Z)表示种群叉中的个体XI的 延边大学工学硕士学位论文适应值,0

下载文档,方便阅读与编辑

文档的实际排版效果,会与网站的显示效果略有不同!!

需要 8 金币 [ 分享文档获得金币 ] 0 人已下载

下载文档

相关文档