多蜂群进化遗传算法

《多蜂群进化遗传算法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、多蜂群进化遗传算法呈灏:多蜂群进化遗传算法多蜂群进化遗传算法程灏(陕西师范大学计算机学院陕西西安710062)摘要:提出一种多蜂群进化型遗传算法.在该算法中,种群的最优个体作为蜂王与被选的每个个体(雄蜂),以概率进行交叉操作,增强了对种群最优个体所包含信息的开采能力.为避免算法早熟,被选雄蜂部分来自于其他蜂群,同时引入蜂王对其他蜜蜂的抑制机制,以提高蜂群的生物多样性.实验结果表明,多蜂群进化遗传算法是一种提高遗传算法性能的有效改进算法.关键词:遗传算法;最优保留;蜜蜂进化型遗传算法;抑制算子;生物多样性中图分类号:TP18文献标识码

2、:A文章编号:1004—373X(2009)23—142—04MultipleBeesEvolutionaryGeneticAlgorithmCHENGHao(CollegeofComputerScience,ShaanxiNormalUniversity,Xian,710062,China)Abstract:AMultipleBeesEvolutionaryGeneticAlgorithm(MBEGA)isproposed.InMBEGA,optimumindividualbeingaqueen—beeinpopulationcr

3、ossoverwitheachselectedindividual(drone).Asaresult,itreinforcestheexploitationofgenetical—gorithm.Inordertoavoidprematureconvergence,partofdronesareselectedfromotherswarm,atthesametime,inhibitionoperationthatextendsbiodiversityoftheswarmiSintroduced.Experimentalresults

4、showMBEGAiSanefficientandeffectivealgorithmtoimproveGA.Keywords:geneticalgorithm;elitistpreserved;beeevolutionarygeneticalgorithms;inhibitionoperator;biodiversity0引言遗传算法(GA)是一种借鉴生物界自然选择和自然遗传机制的高度并行,随机,自适应搜索算法.它是模仿自然界生物进化过程中"物竞天择,适者生存"的原理而进行的一种多参数,多群体的并行优化方法,其应用优势在于处理传统

5、搜索方法难于解决的复杂的非线性问题.经过20多年的发展,遗传算法已经在组合优化,生产调度,函数优化,机器学习,图象处理等许多领域得到成功的应用,并显示出其良好的性能.通过遗传算法求解问题时,人们总是期望在尽量短的时间内达到或尽可能接近问题的全局最优解.当遗传算法停止时,往往只是取出种群中最优个体作为遗传算法的结果.这是因为,群体中最优个体和全局最优解之间的亲和度[1要大于群体中其他个体和全局最优解之间的亲和度.因此,在遗传算法中如何利用每一代的最优个体所包含的特征信息去产生下一代更优秀个体是其必须考虑的问题.Eiben等用Marko

6、v链证明了保留最优个体(ElitistPreserved)遗传算法的概率全局收敛性[2;Rudolph用齐次有限Markov链证明了带有选收稿日期:2009—06—30142择,交叉,变异操作的经典遗传算法收敛不到全局最优解_3].但是,若在遗传算法中保留每一代的最优个体,则算法将收敛到全局最优解.这些都表明种群最优个体对算法的重要意义.在遗传算法中采用最优保留策略可以保证算法的全局收敛性.因此,对保留下来的最优个体如何利用,以提高算法性能则需要进一步研究.蜜蜂进化型遗传算法(BEGA)[4]从蜜蜂的繁殖进化过程中抽取出适合遗传算法

7、的一些机制并融入算法之中.BEGA充分利用种群中最优个体对种群的进化作用,同时,为维持个体的多样性,引入了蜜蜂繁殖过程中"外来种群"的思想,在算法性能上较标准遗传算法有了很大提高.本文受到启发,提出一种多蜂群进化型遗传算法(MBEGA),算法中保持多个蜂群同时进化,蜂王可以选择同一蜂群或其他蜂群中的雄蜂进行交配,蜂王在其所处蜂群中采用相似性判断,以抑制其中产生过于接近蜂王的个体,最后选取多个蜂群中最优的蜂王作为问题的解.这样,既提高了种群的多样性,又避免了进化过程中的"早熟"现象,通过对函数优化问题的求解表明,这种MBEGA算法能够

8、有效提高遗传算法的性能.2009年第23期总第3101多蜂群遗传的抽象模型关于蜂群的数量:蜂群数量设为M(2～50),以模拟自然界中的多个不同蜜蜂群体,在并行计算中可以将M理解为并行的处理机个数.关于种群的构成:为降低算法复杂度,将工