蜜蜂进化型遗传算法 7页

第7期电子学报Vol.34No.72006年7月ACTAELECTRONICASINICAJuly2006蜜蜂进化型遗传算法123孟伟,韩学东,洪炳(1.北京林业大学信息学院,北京100083;2.中国航天科工集团七○六所,北京100854;3.哈尔滨工业大学计算机科学与技术学院,黑龙江哈尔滨150001)摘要:本文提出了一种蜜蜂进化型遗传算法.在该算法中,种群的最优个体作为蜂王与被选的每个个体(雄蜂)以概率进行交叉操作,增强了对种群最优个体所包含信息的开采能力.为了避免算法过早收敛,在代进化过程中引入了一个随机种群,提高了算法的勘探能力.通过将该算法建模为齐次有限Markov链,证明了它的全局收敛性.实验结果表明,蜜蜂进化型遗传算法是一种提高遗传算法性能的有效改进算法.关键词:遗传算法;最优保留;全局收敛性;Markov链中图分类号:TP18文献标识码:A文章编号:037222112(2006)0721294207BeeEvolutionaryGeneticAlgorithm123MENGWei,HANXue2dong,HONGBing2rong(1.InformationSchoolofBeijingForestryUniversity,Beijing100083,China;2.No.706InstituteofChinaAerospaceScienceandIndustryCorporation,Beijing100854,China;3.SchoolofComputerScienceandTechnology,HarbinInstituteofTechnology,Harbin,Heilongjiang150001,China)Abstract:ThispaperproposesaBeeEvolutionaryGeneticAlgorithm(BEGA).InBEGA,optimumindividualbeingaqueen2beeinpopulationcrossoverwitheachselectedindividual(drone).Asaresult,itreinforcestheexploita2tionofgeneticalgorithm.Inordertoavoidprematureconvergence,BEGAintroducesarandompopulationthatextendssearcharea.Consequentiallyitenhancestheexplorationofgeneticalgorithm.BytreatingthecollectionofindividualsineachgenerationasastateandmodelingthealgorithmasahomogeneousfiniteMarkovchain,itisproventhatBEGAcanguaranteetheconvergencetowardstheglobaloptimumoftheproblem.ExperimentsresultsshowBEGAisaneffi2cientandeffectiveimprovedgeneticalgorithm.Keywords:geneticalgorithm;elitistpreserved;globalconvergence;Markovchain函数没有可微性要求而在组合优化、神经网络、智能控制、1引言系统仿真、人工智能等诸多领域得到了广泛的应用.在人工智能领域中,有不少问题需要在复杂而庞大的目前,GA本身在理论和应用方法上仍有许多亟待完搜索空间中寻找最优解.在求解此类问题时,如果不能利善之处,一个突出问题是收敛速度和全局收敛性之间的矛用问题的固有知识来缩小搜索空间,则可能产生搜索的组盾.研究发现,GA可以用极快的速度达到最优解的90%[4]合爆炸.因此,研究能在搜索过程中自动获取和积累有关左右,但要达到真正的最优解则要花费很长的时间.为搜索空间的知识,并自适应地控制搜索过程从而得到最优了提高遗传算法的性能,研究人员从各个方面对其进行了解的通用搜索算法一直是令人注目的课题.遗传算法(简改进,例如,从算子的角度,文献[5]采用二元变异算子(变[1]称GA)就是这类算法之一.GA以达尔文的生物进化论异操作需要两个个体)替代传统的变异算子,从算法结构“适者生存、优胜劣汰”和孟德尔的遗传变异理论“生物遗的角度,文献[6]把一代种群分成了三部分:保留种群、繁传进化主要在染色体上,子代是父代遗传基因在染色体上殖种群和随机种群,通过调整它们各自的规模来协调开采的有序排列”为基础,模拟生物界进化过程.它是由美国密(exploitation)和勘探(exploration),从借鉴其他机制的角[2]执安大学的Holland教授于1975年首先提出的,Gold2度,文献[7]将病毒机制引入遗传算法,文献[8]将免疫原[3]berg的工作使遗传算法获得巨大发展.由于GA简单、对理引入遗传算法,针对简单遗传算法局部搜索能力差的缺收稿日期:2004202216;修回日期:2005212225基金项目:国家863高科技发展计划(No.2001AA422270);国家自然科学基金(No.69985002) 第7期孟伟:蜜蜂进化型遗传算法1295点,文献[9]将局部搜索算法与遗传算法结合,也有研究人不担任何其他工作;工蜂由受精卵发育而来,个体最小,生员针对初始种群、交叉和变异概率对算法收敛速度的影殖器官发育不完全,无生殖能力,是蜂巢内外一切繁重劳[10]响,提出了相应的改进措施,等等.这些方法都在一定动的承担者.程度上提高了遗传算法的搜索效率,加快了收敛的速度.蜂王性成熟后,出巢飞舞,一群雄蜂追随其后.它们在众所周知,利用遗传算法求解问题的根本目标是在尽空中旋转飞翔,越飞越快,体弱的雄蜂相继掉落地面.只留可能短的时间内找到问题的全局最优解.因此,在算法结最强壮的一只雄蜂在空中与蜂王交配,随后双双落地,旋束时,我们最关心的往往是种群中最优个体的性能.从概即分开.雄蜂由于分开时交接器拔断而死去,蜂王则满纳率上来说,群体中的优秀个体和全局最优解之间的亲和精子飞归巢中.蜂王交尾后开始产卵,产卵蜂王不再离开[11]度要大于群体中其他个体和全局最优解之间的亲和蜂巢.有时,为了避免近亲繁殖,蜂王会飞出,寻找其他蜂度,而且,与优秀个体有较大亲和度的个体也应有较高的群,与之交配.适应度.所以,优秀个体所体现的特征信息能否被充分利一般情况下,同一个蜂巢中不允许两只蜂王,否则相[12]用将是决定该算法的优化能力的一个重要因素.Eiben遇就要互相斗杀,直到剩一只蜂王为止.等用Markov链证明了保留最优个体(elitist)的遗传算法从上述过程可以看出,蜂王在蜂群的繁殖进化中发挥[13]的概率全局收敛性,Rudolph用齐次有限Markov链证明着主导作用,雄蜂通过竞争获得与蜂王的交配机会,而工了带有选择、交叉、变异操作的经典遗传算法收敛不到全蜂对蜜蜂繁殖不产生实质性作用.局最优解.但是,若在遗传算法中保留每一代的最优个体,212蜜蜂进化过程的抽象模型则算法将收敛到全局最优解.可以说,Eiben和Rudolph的在遗传算法中引入蜜蜂繁殖进化机制,目的是提高遗上述工作,表明了种群最优个体对算法的重要意义.随后传算法的性能,因此有必要对蜜蜂的繁殖进化机制进行取许多研究人员对保留最优个体算法进行了研究和应舍.[14～19]用.其中,文献[17]在对最优保留遗传算法较为深入关于种群的构成:由于工蜂不对繁殖产生实质性影分析的基础上指出,在加入最优保留操作之前,具有各态响,种群中只保留蜂王和雄峰即可.遍历性的遗传算法在加入最优保留操作后,若不改变(或关于雄蜂的选择:通过某种选择算法从种群中选择若影响)遍历性,则得到的遗传算是全局收敛的.由此可见,干个体作为雄蜂,而不是仅仅一个.研究人员采取最优保留策略的主要目的是保证算法的全关于外来雄蜂:采取随机产生新个体的方式来实现.局收敛性.因此,如何利用保留下来的最优个体值得进一关于蜂王和雄蜂交配:作为蜂王的最优个体,以概率步研究.与每个被选出的雄蜂个体和随机产生的雄蜂个体交配.本文从蜜蜂的繁殖进化过程获得启示,蜜蜂的繁殖方关于蜂王相斗(即争式是有性生殖,但它具有独特的方式,即子代具有共同的夺蜂王):失败者不是消亡母亲———蜂王.蜂王在蜂群个体最大,它唯一的职能是产(死亡或逃走),而是被视卵繁殖后代.而作为子代父亲的雄蜂通过竞争获得与蜂王为普通的雄蜂.的交配机会.这些特征对进一步改进遗传算法,开发设计综上所述,我们得到新的计算智能模型,具有重要的现实意义和发展前景.蜜蜂进化机制在GA中的本文以遗传算法为基础,从蜜蜂的繁殖进化过程中抽抽象模型,如图1所示.取出适合改进遗传算法的一些机制并加以改进,提出了一3蜜蜂进化型遗传算法种蜜蜂进化型遗传算法(BEGA).该算法充分利用了种群中的最优个体对种群的进化作用,同时,为维持个体的多311算法结构与算法描述样性,引入了蜜蜂繁殖过程中“外来种群”的思想.本文通本文只考虑种群规模N恒定的遗传算法,并以适应度过把BEGA建模为齐次有限Markov链,证明了该算法具最大化为求解目的.给定初始种群A(0),则遗传算法的整有全局收敛性.最后,实验结果表明,BEGA通过增强算法个进化过程便生成一个种群序列{A(0),A(1),⋯,A(t),的勘探和开采能力,提高了遗传算法的性能.A(t+1),⋯},目的是使其最终包含全局最优个体.由于资源的限制,在实际应用遗传算法时,我们不可能让其无限2蜜蜂进化机制抽象模型地运行下去,总要设计某种停止准则来终止算法的运行,[20]211蜜蜂繁殖进化过程简介得到该无穷序列的一段{A(0),A(1),⋯,A(t)}.在遗传算蜜蜂是一种社会群居性昆虫,蜂群由蜂王(后蜂)、工法中,这是一个迭代过程,关键是如何从t时刻的种群蜂和雄蜂组成.蜂王由受精卵发育而来,个体最大,体重约A(t)得到t+1时刻的种群A(t+1),这就是代进化策[6]有工蜂的2倍,它唯一的职能是产卵繁殖后代;雄蜂由不略.本文提出的BEGA,其基本思想是:找出种群A(t)中受精的卵发育而成,除了在繁殖季节与处女蜂王交尾外,的最优个体,与上一代蜂王比较,优胜者作为第t代蜂王, 1296电子学报2006年记为Queen,通过选择算法(本文采用比例选择)从种群A大的个体记为Queen-New.NNStep10如果f(Queen-New)>f(Queen),Queen∶=(t)选出γ(0≤γ≤1)个个体,并随机产生(1-γ)个新22Queen-New,C(t)即为第t代种群A(t);否则,用Queen中NN个体,然后,Queen分别与上述个个体(γ个被选个体的个体替代C(t)中的最差个体,得到种群A(t).22Step11转Step3.NN和(1-γ)个随机个体)配对,这对个体经交叉、变异[3]与简单遗传算法(简称SGA)相比,BEGA具有两22个主要的特征:后,得到子代种群C(t+1),找出C(t+1)中的最优个体,(1)每对父本均包含蜂王(种群的最优个体).记为Queen-New,如果Queen-New的适应度大于或等于(2)在代进化过程中引入一个随机种群,该种群的规Queen的适应度,则C(t+1)中的个体全部进入A(t+1),并且Queen-New成为第t+1代蜂王,否则,Queen替换模由参数γ确定.C(t+1)中的最差个体,得到种群A(t+1),Queen成为第第一个特征加强了遗传算法的开采能力,后代主要依t+1代蜂王.算法的代进化过程如图2所示.赖交叉操作和种群的最优个体.当然,这也增加了算法过早收敛的可能性.第二个特征帮助遗传算法搜索新的空间,它通过引入随机种群提高了遗传算法的勘探能力.这两个特征使算法进化加快,并保持优良的解.因此,BEGA有可能使遗传算法更快地接近全局最优解,同时防止过早收敛.312算法的收敛性分析本小节讨论二进制编码时BEGA的收敛性问题.此时个体为定义在集合{0,1}上长度为L的串,这样的串共有L2个,其全体组成集合X.f(·)为定义在X上的适应度函数,满足Px∈X,f(x)>0.设所有个体的适应度集合为LY={yy=f(x),x∈X},容易得到Y≤X=2,记b=Y.将集合Y中的元素按降序排列,可得到有序集合{y1,y2,⋯,yb},其中,y1>y2>⋯>yb.N在图2所示的代进化过程中,参数γ具有调节算法勘记S=X为所有规模为N的种群组成的集合.由于种探和开采的重要作用,本文第4节将进一步分析γ对算法群中允许个体相同,因而,式(1)成立.L性能的影响.X+N-12+N-1S==(1)在上述代进化策略的基础上,BEGA整个过程可描述NN如下:L2+N-1具体证明可参考文献[21].记M=.Step1随机生成初始种群A(0),t∶=0,分别对γ、交N叉概率Pc和变异概率Pm赋值.为了比较种群的优劣,定义种群的适应度如下:Step2计算种群A(0)中个体的适应度,将最优个体定义1s∈S是规模为N的种群,s的适应度根据(即第0代蜂王)保存到Queen中.式(2)计算:Step3如果满足停止准则,算法输出结果并停止运f(s)=Max{f(x)}(2)x∈s行;否则,继续.定义1表明,种群的适应度就是该种群中最优个体的Step4t∶=t+1.适应度.因此,种群适应度集合与个体适应度集合相同,从NStep5利用比例选择方式,从A(t-1)中选出γ个而有Ps∈S,yb≤f(s)≤y1.根据适应度将种群集合S划分2b个非空子集Si,Si={sf(s)=yi,s∈S},记qi=Si,个体.i=1,2,⋯,b.显然,种群集合S1包含所有适应度最高的种NStep6随机生成(1-γ)个个体.b2群,并且,∑qi=M.Ni=1Step7Queen分别与Step5和Step6得到的2个个为了便于描述,对符号作如下约定:Pr(·)表示事件发体进行交叉运算,得到子代种群,记为B(t).生的概率,si,j表示种群集合Si中的第j个种群,在遗传算Step8对B(t)执行变异操作,得到种群C(t).子的作用下,si,j→sk,l表示种群si,j直接转变为种群sk,l,其Step9计算种群C(t)中个体的适应度,将适应度最状态转移概率用Pr(si,j→sk,l)表示,si,j→Sk表示种群si,j直 第7期孟伟:蜜蜂进化型遗传算法1297接转变到种群集合Sk中的某一种群,其状态转移概率用定理2BEGA具有全局收敛性.Pr(si,j→Sk)表示,Si→Sk表示种群集合Si直接转变到集合证明根据定理1,可以认为每一个种群集合Si(i=Sk,其状态转移概率用Pr(Si→Sk)表示.根据上述约定,容1,2,⋯,b),都是齐次有限Markov链上的一个状态.设i易证明下列各式成立:为处于状态Si的概率,易知,Pi∈{1,2,⋯,b},i>0,且qbk①Pr(si,j→Sk)=∑Pr(si,j→sk,t);∑i=1.i=1t=1b根据引理3,可以写出该Markov链的状态转移矩阵为②∑Pr(si,j→St)=1;p00⋯0t=11,1③P(si,j→Sk)≥P(si,j→sk,l).p2,1p2,20⋯0C0其中,j=1,2,⋯,qi,i=1,2,⋯,b,l=1,2,⋯,qk,k=1,P=p3,1p3,2p3,3⋯0=RT2,⋯,b.………w…定义2如果对于任意的初始种群A(0)pb,1pb,2pb,3⋯pb,btl→im∞Pr(f(A(t))=y1)=1(3)显然,R=(p2,p,⋯,p)′>0,T≠0,C=p=1,,13,1b,11,1则称算法全局收敛,其中,y1为前述的全局最大适应因此根据引理1,可得度.kC0∞∞kC0定义2表明,全局收敛是指算法经过无数次迭代后,P=limP=limk-1=k→∞k→∞ik2ik∞∑TRCTR0种群中包含全局最优个体的概率为1,即通常所说的以概i=0率1收敛.其中,C∞=1,R∞=(1,1,⋯,1)′,从而P∞是一个稳定以下证明BEGA具有定义2给出的全局收敛性,如不随机矩阵,并且特殊说明,均认为1>Pm>0.100⋯0[13]引理1设P是可约化随机矩阵,其中,C是m阶100⋯0∞随机正矩阵,且R,T≠0,则P=100⋯0k………w…C0∞∞kC0P=limP=limk-1=(4)100⋯0k→∞k→∞ik-ik∞∑TRCTR0i=0这说明,当迭代次数足够多时,算法的种群将必定属是一个稳态随机矩阵.于适应度最高的种群集合,此时,种群的适应度为y1,即式(3)成立,因而BEGA具有全局收敛性.引理2BEGA中,Pi,k∈{1,2,⋯,b},Pj∈{1,2,⋯,qi},下式成立:4实验结果与分析>0,k≤iPr(si,j→Sk)(5)411参数γ对算法性能的影响=0,k>i遗传算法中存在大量的随机操作,因此,对其评估应引理3BEGA中,Pi,k∈{1,2,⋯,b},下式成立:建立在统计规律的基础上.本小节采用平均进化代数和平>0,k≤iPr(Si→Sk)(6)均最大适应度作为算法的两个性能指标,以便考察参数γ=0,k>i对算法性能的影响.引理2表明,适应度较低的种群可以转移到适应度相定义3算法对同一目标函数重复做K次实验,每次同或更高的种群,而适应度较高的种群不可能转移到适应K1度较低的种群.引理3表明,当算法处于适应度较低的种实验结束时的进化代数为tk,k=1,2,⋯,K,则∑tk称为Kk=1群集合时,它可以转移到适应度相同或更高的种群集合,平均进化代数.反之却不然.定义4算法对同一目标函数重复做K次实验,每次定理1BEGA的运行过程是一齐次有限Markov链.K1证明由算法的代进化过程可以看出,t实验结束时种群的适应度为fk,k=1,2,⋯,K,则∑fk称+1时刻的种Kk=1群A(t+1)只与t时刻的种群A(t)有关,而与种群A(0),为平均最大适应度.A(1),⋯,A(t-1)无关,因而,BEGA的运行过程满足平均进化代数是体现算法效率(efficiency)的一个指Markov性.由算法的整个进化过程可以看出,各种遗传算标.平均进化代数越少,说明算法的优化效率越高,反之,子均不随时间发生变化,因而,BEGA的运行过程满足时优化效率越低.平均最大适应度是体现算法效果(effec2间齐次性.由式(1)可知,种群集合是有限的,因此,BEGAtiveness)的一个指标,平均最大适应度越大,说明算法的优的运行过程是一齐次有限Markov链.化效果越好,反之,优化效果越差. 1298电子学报2006年为了计算平均进化代数和平均最大适应度,应首先设计一个停止准则.为遗传算法设计一个良好的停止准则是[22]一个困难的任务,但往往被忽视.目前,常用的停止准则主要有以下几种:适应度边界法、时间边界法、个体数目边界法、适应度数目边界法、增长概率边界法以及基于Bayes方法的最小损失法等.本文针对种群最优个体的进T化能力,采用了如下停止准则:给定整数T≥1,如果∑i=1ft+i-ft+i-1=0,则算法停止.其中,ft+i和ft+i-1分别表示第t+i代和第t+i-1代种群的适应度.为了测试参数γ对算法的影响,将f1作为测试函数.222minf1=100×(x2-x1)+(1-x1)s.t.-5≤x1,x2≤5f1是Rosenbrock函数的特例(n=2),也是DeJong五2个测试函数之一.由于该函数本身的特殊性,利用传统的maxf2=(1-x)×x×sin(200x)s.t.0≤x≤122函数优化方法很难得到满意解.文献[23]在对f1深入研maxf3=(-1)×(x+2y-0.3×cos(3x)-0.4究的基础上利用简单遗传算法对其进行求解,并探索了求×cos(3y))+4s.t.-1≤x,y≤1解该函数合理的遗传操作.222sinx+y-0.5maxf4=0.5-222s.t.-2≤x,y≤21[1+0.01×(x+y)]实验中,适应度函数取为,交叉概率Pc=0.85,1+f221x1+x2minf5=-cos(2x1)cos(2x2)s.t.-10≤x1,变异概率Pm=0.01,γ由0变到1,步长为0.01,T=50,对2同一个γ值,算法独立进行1000次,计算其平均进化代x2≤10数,结果如图4所示,计算其平均最大适应度,结果如图51其中,f1、f2、f3、f4、f5的适应度函数分别是、f2、所示.1+f11f3、f4、.2+f5实验中,均采用二进制编码,除f2中个体长度为20,其余均为40.种群规模N=50,Pc=0.85,Pm=0.01,BEGA中,γ=0.2.针对411小节的两个性能指标,本小节做了两个实验.实验一:收敛准则设为种群适应度与全局最大适应度的差小于等于01001,为了保证各种算法均在有限迭代次数内停止,设最大迭代次数为2000,若算法在迭代2000次后,仍然不收敛,则认为该次实验失败,否则认为成功.SGA、EGA和BEGA分别对每个函数进行独立求解1000次,计算他们的平均进化代数(成功实验的平均进化代数)和成功率,结果如表1所示.从图4和图5可以看出,随着γ的增大,平均进化代实验二:算法的停止准则设为算法运行400毫秒,数和平均最大适应度都呈下降趋势,这是因为随着γ的增SGA、EGA和BEGA分别对每个函数进行独立求解1000大,从上一代种群中选择的个体增多,而随机生成的个体次,计算其平均最大适应度,实验结果如表2所示.减少,从而算法的开采能力提高,算法的勘探能力降低,算表2实验结果法加快了收敛的速度,但算法的优化效果却降低了.综合f1f2f3f4f5考虑γ对平均进化代数和平均最大适应度的影响,γ在0.2平均最大平均最大平均最大平均最大平均最大附近效果比较理想.适应度适应度适应度适应度适应度412BEGA与其他遗传算法的比较SGA0.7375570.1467024.6986240.9929720.847256为了验证BEGA的有效性,选择了五个比较典型的函EGA0.7691900.1478684.6999960.9998520.885756数)进行性能测试,并与简单遗传算法BEGA0.9973810.1481374.7000001.0000000.998723(包括411小节的f1[3](SGA)和最优保持遗传算法(EGA)进行了比较. 第7期孟伟:蜜蜂进化型遗传算法1299表1实验结果f1f2f3f4f5平均进化代数成功率平均进化代数成功率平均进化代数成功率平均进化代数成功率平均进化代数成功率SGA—1.6%6.490.8%30.799.9%24.594.2%204.037.5%EGA—2.1%6.194.2%19.5100%20.699.6%173.350.1%BEGA559.891.4%2.3100%6.9100%4.2100%125.4100%注:在求解f1,由于SGA和EGA成功率太低,因此计算其平均进化代数意义不大,故没有给出实验一中的成功率本质上是对算法在规定时间内找optimizationspeedforgeneticalgorithms[J].Journalof到满意解的概率的估计.从表1不难看出,在给定解的精Software,2001,12(2):270-275.(inChinese)度要求下,BEGA的收敛速度(指平均进化代数)得到了成[6]江瑞,罗予频,胡东成,司徒国业.一种协调勘探和开采的倍的提高.因此,BEGA的优化效率比SGA和EGA高.遗传算法:收敛性及性能分析[J].计算机学报.2001,24与SGA相比,EGA和BEGA增加了寻找最佳个体和(12):1233-1241.替换最佳个体操作,BEGA还增加了随机生成新个体操作,JiangRui,LuoYupin,HuDongcheng,SzetoKworkyip.A因此三种算法平均每次迭代所花费的时间不同,为了比较geneticalgorithmbycoordinatingexplorationandexploita2的合理性,实验二中设定算法的运行时间.表2的结果表tion:convergencepropertiesandperformanceanalyses[J].ChineseJournalofComputer,2001,24(12):1233-1241.明,在规定的时间内,BEGA得到的解优于SGA和EGA所(inChinese)得的解,因此,BEGA的优化效果比SGA和EGA好.[7]KubotaN,ShimojimaK,FukudaT.Theroleofvirusinfec2根据表1和表2的结果,我们可以看出,不论是优化tioninvirus2evolutionarygeneticalgorithmenvolutonary效率还是优化效果,BEGA均优于SGA和EGA.computation[A].1996ProceedingofIEEEInternational5结论Conference[C].Nagoya,Japan:IEEE,1996.182-187.[8]王磊,潘进,焦李成.免疫算法.电子学报[J].2000,28受蜜蜂繁殖进化方式的启发,本文提出了一种新型的(7):74-78.遗传算法———蜜蜂进化型遗传算法(BEGA).BEGA通过WangLei,PanJin,JiaoLicheng.Theimmunealgorithm蜂王(最佳个体)与每个雄蜂(被选个体和随机个体)交[J].ActaElectronicaSinica,2000,28(7):74-78.(in配,提高了算法的开采能力,通过引入外来蜂群(随机种Chinese)群)提高了算法的勘探能力.实验结果表明,BEGA提高了[9]彭伟,卢锡城.一种函数优化问题的混合遗传算法[J].软遗传算法的优化效率和优化效果,因此BEGA是一种提高件学报.1999,(10)8:819-823.遗传算法性能的有效改进算法.PengWei,LuXicheng.Ahybridgeneticalgorithmforfunctionoptimization[J].JournalofSoftware,1999,10参考文献:(8):819-823.(inChinese)[1]陈国良,王煦法,庄镇泉,王东生.遗传算法及其应用[10]唐世浩,朱启疆.遗传算法中初始种群与交叉、变异率对[M].北京:人民邮电出版社,1996.解的影响及其解决方案[J].科技通报,2001,17(3):1ChenGuoliang,WangXufa,ZhuangZhenquan,Wang-7.Dongsheng.GeneticAlgorithmandItsApplication[M].TangShihao,ZhuQijiang.Effectsoftheinitialpopula2Beijing:People"sPostandTelecommunicationsPublishingtion,crossoverandmutationratetotheresultsofgeneticHouse,1996.(inChinese)algorithmsandapossiblesolutionscheme[J].Bulletinof[2]HollandJH.AdaptationinNaturalandArtificialSystemScienceandTechnology,2001,17(3):1-7.(inChi2[M].USA:UniversityofMichiganPress,1975.nese)[3]GoldbergDE.GeneticAlgorithmsinSearch,Optimization[11]王煦法,张显俊,曹先彬,张军,冯雷.一种基于免疫原理andMachineLearning[M].NewYork:Addison2Wesley,的遗传算法[J].小型微型计算机系统,1999,20(2):1989.117-120.[4]KitanoH.EmpiricalstudiesonthespeedofconvergenceofWangXufa,ZhangXianjun,CaoXianbin,ZhangJun,theneuralnetworktrainingbygeneticalalgorithm[A].FengLei.Animprovedgeneticalgorithmbasedonim2ProcofAAAI90[C].MenloPark,USA:TheAAAIPress,muneprinciple[J].Mini2MicroSystems,1999,20(2):1990.881-890.117-120.(inChinese)[5]杨启文,蒋静坪,张国宏.遗传算法优化速度的改进[J].[12]EibenAE,AartsEH,VanHeeKM.Globalconvergence软件学报.2001,12(2):270-275.ofgeneticalgorithm:aninfinitemarkovchainanalysisYangQiwen,JiangJingping,ZhangGuohong.Improving[A].In:SchwefelHP,MannerR.Eds.Parallelproblem 1300电子学报2006年SolvingfromNature[C].Heidelberg,Berlin:Springer2[20]刘凌云,郑光美.普通动物学(第三版)[M].北京:高等verlag,1991.4-12.教育出版社,1997.[13]RudolphG.Convergenceanalysisofcanonicalgenetical2LiuLingyun,Zhengguangmei.GeneralZoology(3rd)gorithms[J].IEEETransactionNeuralNetworks,1994,5[M].Beijing:HigherEducationPress,1997.(inChi2(1):96-101.nese)[14]DinabandhuB,MurthyCA.Geneticalgorithmwithelitist[21]MelanieMitchell.AnIntroductiontoGeneticAlgorithmmodelanditsconvergence[J].IntJofPatternRecogni2[M].Cambridge,MA:TheMITPress,1996.tionandArtificialIntelligence,1996,10(6):990-995.[22]王正志,薄涛.进化计算[M].长沙:国防科技大学出版[15]彭宏,王兴华.具有Elitist选择的遗传算法的收敛速度社,2000.估计[J].科学通报,1997,42(2):144-147.WangZhengzhi,BoTao.EvolutionaryComputation[M].PengHong,WangXinghua.ConvergencespeedestimateChangsha:NationalUniversityofDefenseTechnologyofgeneticalgorithmwithelitistselection[J].ChineseSci2Press,2000.(inChinese)enceBulletin,1997,42(2):144-147.(inChinese)[23]梁艳春,周春光,李寿范.基于遗传算法的Rosenbrock[16]王宏刚,曾建潮,徐玉斌.优良模式自学习遗传算法[J].函数优化问题的研究[J].软件学报.1997,8(9):701-自动化学报.1999,25(3):375-379.708.WangHonggang,ZengJianchao,XuYUbin.AnexcellentLiangYanchun,ZhouChunguang,LiShoufan.Optimiza2schemeasself2learninggeneticalgorithm[J].ActaAuto2tionofRosenbrock"sfunctionbasedongeneticalgorithmsmaticaSinica,1999,25(3):375-379.(inChinese)[J].JournalofSoftware,1997,8(9):701-708.(inChi2[17]何琳,王科俊,李国斌,金鸿章.最优保留遗传算法及其nese)收敛性分析[J].控制与决策.2000,15(1):63-66.HeLin,WangKejun,LiGuobin,JinHongzhang.Elitist作者简介:preservedgeneticalgorithmanditsconvergenceanalysis孟伟女,1974年10月出生于山东德州,2005年毕业于哈尔[J].ControlandDecision,2000,15(1):63-66.(inChi2滨工业大学计算机科学与技术学院,获工学博士学位,研究领域为智nese)能机器人、信息融合技术,已发表论文10余篇.[18]KalyanmoyDeb,AmritPratap,SameerAgarwal,TMe2韩学东男,1973年6月出生于山东泰安,2004年毕业于哈尔yarivan.Afastandelitistmultiobjectivegeneticalgo2滨工业大学计算机科学与技术学院,获工学博士学位,主要研究方向rithm:NSGA2II[J].IEEETransactiononevolutionary为嵌入式系统、智能机器人、多智能体系统、机器学习,已发表论文20computation,2002,6(2):182-197.余篇.E2mail:xdhm@263.net[19]ChangWookAhn,RSRamakrishna.Elitism2basedcom2pactgeneticalgorithms[J].IEEETransactiononevolu2洪炳男,1937年8月出生于吉林延边,教授,博士生导师,主tionarycomputation,2003,7(4):367-385.要研究方向为空间机器人、智能机器人、虚拟现实等.