选择算子与遗传算法的计算效率分析

223Vol.22No.320099JOURNALOFNINGBOUNIVERSITY(NSEE)Sept.2009:1001-5132200903-0374-04,315211:.,,..:;;;:TP301.6:A(GeneticAlgorithm)“”,“”,,,“”,.,.,,.,.,,GA“”,,GA.,GA,.1.(RouletteWheel),.,.N,iif,:1/.Nsiiiipff==∑,,,.,2008-11-06.::.E-mail:[e-mail]3:375,N(N).2,2,24,2,2.,,,;,.,.,,3:,,,,.,,GA.,,.,.,,,.:X(),,X1,2,3,X.m/,pmX=1m≤≤.X,,.,,,;,,.,,.2[1],,,i,j,k→∞,(SGA),SGA..1max{([1,])}jikkFjsfn=∈k,()iλ,.nmax{([1,2])}jlFfsj∗=∈GA,lim()1kkPFF∗→∞==,GA.1(SGA).iλkFF∗,ikPSGAkiλ,:11/2nlikP−=,kFF∗m,1m≥,11()/21/2.nlnlkikPFFmP∗−−==≥kFF∗=:(kPF=)1.ikFP∗−≤[1],lim0ikkP→∞.,lim()1lim1.kikkkPFFP∗→∞→∞=−≤,SGA.2kλ∗SGAkkF∗,1kkFF∗+,1kλ∗+=1kλ+,11kkFF∗++=,,SGASGA,OMSGA(OptimumMaintainingSimpleGeneticAlgorithm).37620092(OMSGA)[2].0Λ0FF∗=,P′:010,QPTPTP⎡⎤⎡⎤′==⎢⎥⎢⎥⎣⎦⎣⎦P′Q,0Λ,Q1,,.P,iλΛ,SGA,,iλ0Λ,,,lim()1.kukPFFF∗→∞===,OMSGA.0,.,0,0.,.,0,.0,,,.3,:01(1/)Nprs=−−,s,r,N.rs,N,00p≈,,,,..tN(N)'teNNp=,ep.,t2:12,teNpggN=(1)1gt,2gt.t:(1(1/))tNttprsc=−−,(2):tc.(1)(2):12(1(1/))pggNttPrscε=−−.(3),tp.(3),ep1g2gNtctp,ep1.1g2g,tpNtc,N,N,tc,tc.tc,2,,2,;,tc,.3,,3:377,;2,,.,.GA.,GA[3],GA,,:,,,,,,GA.,,,;;(),,.,,,GA,.:[1],.[J].,1996,13(4):456-460.[2],.[J].,1999,25(1):68-72.[3],,,.[M].:,2002.OperatorSelectionandComputationalEfficiencyAnalysisonGeneticAlgorithmZHANGSong-yan(FacultyofScience,NingboUniversity,Ningbo315211,China)Abstract:Therelationshipbetweentheselectionofgeneticalgorithmanditsglobalconvergenceandconvergencerateisidentified.Itisfoundthatthecommonlyusedselectionoperatorcannotguaranteetheglobalconvergenceinthealgorithm.Theglobalconvergenceisguaranteedusingroulettewheelselectionalgorithmthroughintroducingtheoptimalmaintainingoperation,althoughtheconvergenceisachievedatthecostofslighttimeconsumption.Inaddition,severaltacticsforselectingandrunningthegeneticalgorithmarepresentedinthiswork.Keywords:selectionoperator;geneticalgorithm;computationalefficiency;convergencetheoremCLCnumber:TP301.6Documentcode:A选择算子与遗传算法的计算效率分析作者：张松艳，ZHANGSong-yan作者单位：宁波大学,理学院,浙江,宁波,31521I刊名：宁波大学学报（理工版）英文刊名：JOURNALOFNINGBOUNIVERSITY(NATURALSCIENCE&ENGINEERINGEDITION)年，卷(期)：2009，22(3)被引用次数：0次参考文献(3条)1.恽为民.席裕庚遗传算法的全局收敛性和计算效率分析1996(04)2.李茂军.童谚爿生单亲遗传算法及其全局收敛性分析1999(01)3.李敏强.寇纪淞.林丹遗传算法的基本理论与应用2002相似文献(10条)1.学位论文徐蔡星一种遗传算法选择算子的设计策略2008遗传算法(GeneticAlgorithm,GA)是一种模拟生物进化的智能算法，具有全局优化性，广泛的适应性和显著的隐并行性等特点。遗传算法通过适当的编码方式把实际问题转化成生物种群的进化问题，经过多代的选择、交叉和变异操作得到可接受的问题的解；由于遗传算法只对解本身作操作，从而减弱了对研究人员的背景知识的要求，且避免了复杂的求导操作等，使得遗传算法在实际中得到了广泛的应用。简单遗传算法(SimpleGeneticAlgorithm，SGA)作为一种启发式搜索算法，寻优理论还不完善，因此，在应用中常出现收敛过慢，局部搜索精度不够和早熟收敛现象等问题，而现有的一些改进措施并不能完全解决这些问题。由于简单遗传算法和现有的一些改进算法存在缺陷，论文提出了对遗传算法选择算子的改进方法，即把相似个体分在同一组中，以组为单位进行选择，并通过该组个体的特点进行高斯搜索生成新的群体。这样使得算法在搜索过程中不仅可以很好的保持个体的多样性，并且可以提高解的精确度。通过对11个函数(单峰和多峰)的仿真实验，证明了采用新的选择算子后，遗传算法在求解问题的精确度上有了很大的改善。2.期刊论文郝国生.严玉若.黄永青.胡培亮.章磊.路娟.季君.HAOGuo-sheng.YANYu-ruo.HUANGYong-qing.HUPei-liang.ZHANGLei.LUJuan.JIJun基于三角函数的遗传算法选择算子-江南大学学报（自然科学版）2010,9(2)遗传算法的选择算子对算法的早熟收敛及算法性能有重要的影响.为避免算法早熟收敛和提高算法性能,提出基于三角函数的选择算子,分析基于三角函数选择算子的可行性,并通过实验比较基于三角函数的选择算子与其他选择算子的性能.实验表明,三角选择算子能有效地避免早熟和提高算法性能.3.学位论文顾鹏基于遗传算法的测试用例产生系统关键技术研究2006测试用例的自动产生方法是目前软件测试领域研究的重要内容之一。遗传算法作为一种高效的搜索寻优算法，近年来日益受到国际学术界的重视，由于该算法具有较强的建模能力和自适应性，也越来越受到软件测试界的重视，逐渐成为测试用例产生方法的重要研究内容之一。将遗传算法用于测试用例产生系统时，适应度函数是影响算法效率的关键，选择算子则是决定算法能否同时产生多条路径上的测试用例的主要因素。目前用遗传算法产生多参数程序的测试用例时效率较低，而且无法同时产生多条路径上的测试用例。为了解决这些问题，需要设计高效的适应度函数，寻求能产生多条路径上测试用例的选择算子。为了克服现有遗传算法产生测试用例时效率较低的缺陷，通过分析适应度函数的特点，研究参数个体及其覆盖路径与适应度函数之间的关系，设计了基于海明距离的适应度函数方案，该适应度函数利用路径覆盖状态的决策变量作为参数。在此基础上，用二重结构编码方法对个体进行编码，除变量码表示个体值外，使用附加码表示交叉和变异操作的操作点范围，以提高算法的局部搜索能力。针对基本遗传算法每次只能产生一条路径上测试用例的问题，研究了选择算子对优化目标准则的影响。从多目标优化的角度设计了基于轮盘赌选择方法的加权选择算子，同时考虑所有目标路径对个体选择概率的影响，提高算法产生多条路径上测试用例的能力。将基于适应度函数和选择算子的改进整合，结合基本遗传算法的体系结构，提出改进遗传算法，并应用到测试用例产生问题中。研究结果表明，改进后的算法搜索效率高于基本遗传算法，并且具备了一次处理多条目标路径的功能，具有一定的实用价值。4.期刊论文李晨.宁红云.LIChen.NINGHong-yun改进的遗传算法选择算子-天津理工大学学报2008,24(6)为了进一步提高遗传算法选择算子的选优能力,本文在传统轮盘赌的基础上提出了一种基于排序的多轮轮盘赌选择算子,加入了多轮转盘的思想,并利用对上代种群进行排序增加优秀个体的选择概率,从而在提高了算子的选优能力同时也减少了随机性所产生的误差;随后本文将此算子与最佳个体保存法的思想相结合,进一步提出了无放回的基于排序的多轮轮盘赌选择算子,达到了既能够选出最好个体又能够保证种群多样性的效果.实验表明,与传统轮盘赌算子相比较,新方法能够有效地提高遗传算法的收敛速度.5.期刊论文蒋艳.黎向锋.左敦稳.焦光明.薛善良.JIANGYan.LIXiang-feng.ZUODun-wen.JIAOGuang-ming.XUEShan-liang多种改进选择算子的遗传算法性能比较与应用研究-中国制造业信息化2010,39(11)为了比较针对遗传算法的早熟收敛和后期收敛速度慢而提出的改进选择算子的性能,利用3种权威测试函数对基于排名的轮盘赌选择、基于上限的确定式采样选择、无回放最大值选择以及基于小生境技术的(μ+λ)选择这4种改进的选择算子进行了收敛速度、收敛可靠性和运算成本3方面的测试比较,并对测试结果作了详细的分析.最后,将采用基于小生境技术的(μ+λ)选择算子的遗传算法应用于一个混合装配流水线上最小装配时间协同优化的实际问题中,获得了较优的优化结果.6.期刊论文曹道友.程家兴.CAODao-you.CHENGJia-xing基于改进的选择算子和交叉算子的遗传算法-计算机技术与发展2010,20(2)为了有效解决遗传算法中收敛速度与局部最优解的矛盾,文中提出了一种具有改进的选择算子和改进的交叉算子的遗传算法.使用文中改进的选择算子,能够增加算法收敛于全局最优解的概率,从而不容易陷入局部最优,也就增加了找到最优解的概率,使用文中改进的交叉算子可以加快算法的收敛速度,从而缩短寻找最优解的时间.实验证明,这两种改进算子的结合能以较快速度收敛于全局最优解,因此能很好地解决遗传算法中收敛速度与局部最优解之间的矛盾.7.期刊论文乔家庆.付平.孟升卫.QIAOJia-qing.FUPing.MENGSheng-wei基于个体差异的遗传选择算子设计-电子学报2006,34(z1)本文针对遗传算法采用基于局部竞争机制的选择算子不易跳出局部最优的问题,设计了一种基于个体差异的局部竞争选择算子,局部竞争作用的区域由种群内个体间的差异决定,有利于保持种群的多样性,增强了算法从局部最优中跳出的能力.仿真结果表明,遗传算法采用基于个体差异的选择算子,在全局极大值附近存在剧烈震荡的情况下,有效地保证了算法优化成功率和效率.8.期刊论文陈有青.徐蔡星.钟文亮.张军.CHENYou-qing.XUCai-xing.ZHONGWen-liang.ZHANGJun一种改进选择算子的遗传算法-计算机工程与应用2008,44(2)遗传算法(GeneticAlgorithm,