带互动界面的遗传算法演示系统文献综述

PAGE10 本科毕业设计文献综述（2012届）论文题目带互动界面的遗传算法演示系统带互动界面的遗传算法演示系统摘要：本文是关于带互动界面的遗传算法演示系统设计与实现的一篇文献综述，先对遗传算法进行简单介绍，然后详述一下国内外相关研究现状以及现阶段存在的技术关键及问题，最后进行简单总结与预测未来的发展趋势。关键词：遗传算法，选择，最优解，发展趋势一、引言遗传算法通过有组织的然而是随机的信息交换来重新结合那些适应性好的称为染色体的二进制数串，在每一代中，利用上一代串结构中适应性好的位和段来生成一个新的串的群体；作为额外增添，偶尔也要在串结构中尝试新的位和段来替代原来的部分[1]。利用二进制编码的方法，初代种群产生之后，按照适者生存和优胜劣汰的原理，逐代演化产生出越来越好的近似解。在每一代，根据问题域中个体的适应度大小选择个体，并借助于自然遗传学的遗传算子进行组合交叉和变异，产生出代表新的解集的种群。二、研究意义遗传算法作为具有系统优化、适应和学习的高性能计算和建模方法的研究，广泛应用于自动控制、计算科学、模式识别、智能故障诊断管理科学和社会科学领域，适用于解决复杂的非线性和多维空间寻优问题[2]。利用遗传算法的搜索过程不受优化函数的连续性约束，也没有优化函数的导数必须存在的要求；遗传算法采用多点搜索或者说是群体搜索，具有很高的隐含并行性，因而可以提高计算速度；遗传算法更适合大规模复杂问题的优化。正因遗传算法有如此多的优点，所以对它的研究将具有重要意义。标准遗传算法的流程如下表所示[3]：GA（Fitness，Fitness＿threshold，p，r，m）Fitness：适应度评分函数，为给定假设赋予一个评估分数Fitness＿threshold：指定终止判据的阈值p：群体中包含的假设数量r：每一步中通过交叉取代群体成员的比例m：变异率初始化群体：P←随机产生的p个假设评估：对于P中的每一个h，计算Fitness（h），当[maxFitness（h）]＜Fitness＿threshold时，产生新的一代Ps：（1）选择：用概率方法选择P的（1－r）p个成员加入Ps从P中选择假设hi的概率Pr（hi）用下面公式计算：（2）交叉：根据上面给出的Pr（hi），从P中按概率r*p／2选择对假设对于每对假设＜h1，h2＞，应用交叉算子产生两个后代,把所有的后代加入Ps（3）变异：使用均匀的概率从Ps中选择成员，对于选出的每个成员，在其表示中随机选择一个位取反（4）更新：P←Ps（5）评估：对于P中h的每个计算Fitness（h）从P中返回适应度最高的假设三、国内外研究现状及难点遗传算法最早是由美国Michigan大学的Holland教授和他的学生们在70年代初提出而创立的。从80年代开始，对遗传算法的研究与应用进入了一个新高潮，国际上有大量关于这方面的论文与研究成果。进入90年代，遗传算法迎来了兴盛发展时期，无论是理论研究还是应用研究都成了十分热门的课题。应用研究尤其活跃，利用遗传算法进行优化和规则学习的能力显著提高。一些新的理论和方法在应用研究中也得到了迅速的发展。理论上,成功地应用齐次有限马尔科夫链理论分析了简单遗传算法、最优保存简单遗传算法和自适应遗传算法的收敛性，从而得到简单遗传算法不是全域收敛,而和是全域收敛的重要结论[5]。此外，有人利用马尔科夫链理论对浮点数编码的遗传算法进行了严密的全域收敛性分析，另有学者也研究了达到全局最优解的遗传算法的时间复杂性问题[6]。这些理论问题的相继解决,为遗传算法获得更好的实际应用奠定了基础。在遗传算法与其他方法的混合研究上较为成功，它既发挥了遗传算法的全局性特点又发挥了某一种方法对于某一特定问题有效收敛性的特长并且能够快速稳定的搜索到问题的全局最优解。主要的混合方法有并行遗传与神经网络混合学习方法，遗传与进化编程混合方法，模拟退火与遗传算法混合方法等[7]。目前遗传算法已被广泛应用于自动控制、机器人学、计算机科学、模式识别、模糊与人工神经网络和工程优化设计等领域。在国外，1975年Holland出版了他的著名专著《自然系统和人工系统的自适应》（AdaptationinNaturalandArtificialSystems），这是第一本系统论述遗传算法的专著，因此有人把1975年作为遗传算法的诞生年。Holland在该书中系统地阐述了遗传算法的基本理论和方法，并提出了对遗传算法的理论研究和发展极其重要的模式理论（schematheory）。该理论首次确认了结构重组遗传操作对于获得隐并行性的重要性[8]。基于领域交叉的交叉算子这一概念是由D.Whitey于1991年在他的论文中提出的，该算子是特别针对用序号表示基因的个体的交叉，并将其应用于TSP问题中，通过实验对其进行验证。常用的交叉操作方法有一点交叉。二点交叉、一致交叉、二维交叉、树结构交叉等等[9]。D.H.Ackley等提出了随机迭代遗传爬山算法（SIGH），采用了一种复杂的概率选举机制，此机制中由m个“投票者”来共同决定新个体的值[10]。总体来讲，SIGH比现存的许多算法在求解速度方面更有竞争力。单一操作的多亲交叉算子是将遗传算法与但单一方法结合起来，它根据两个母体和一个额外的个体产生新个体，其交叉结果与对三个个体用选举交叉产生的结果相同[11]。该算子由H.Bersini和G.Seront提出。就国内来说在遗传算法方面也取得了很大进展。2002年，戴晓明等应用多种群遗传并行进化的思想，对不同种群基于不同的遗传策略，如变异概率，不同的变异算子等来搜索变量空间，并利用种群间迁移算子来进行遗传信息交流，以解决经典遗传算法的收敛到局部最优值问题。2004年，赵宏立等针对简单遗传算法在较大规模组合优化问题上搜索效率不高的现象，提出了一种用基因块编码的并行遗传算法（Building-blockCodedParallelGA，BCPGA）。该方法以粗粒度并行遗传算法为基本框架，在染色体群体中识别出可能的基因块，然后用基因块作为新的基因单位对染色体重新编码，产生长度较短的染色体，在用重新编码的染色体群体作为下一轮以相同方式演化的初始群体。2005年，江雷等针对并行遗传算法求解TSP问题,探讨了使用弹性策略来维持群体的多样性,使得算法跨过局部收敛的障碍,向全局最优解方向进化。尽管这一算法已具有较多的优点,业已在实际中得到了大量应用,但它也存在着许多急待解决的问题。例如，如何进行算法本身的参数优化选择，即对群体的规模N、交换概率Pc和变异概率Pm进行优化选择。因为实践发现这些参数的选取直接关系着GA求解问题的成败。如何避免算法过早收敛的产生，过早收敛是指GA在执行过程中会出现群体中的个体过早地在一个非最优点上达到完全相同或接近完全相同的现象。一旦出现该现象,利用GA就不能求得问题的全域最优解[12]。对于动态数据，用遗传算法求最优解比较困难，因为染色体种群很可能过早地收敛，而对以后变化了的数据不再变化[13]。针对这一问题，研究者提出了一些方法增加基因的多样性，从而防止过早地收敛。其中一种是触发式超级变异，就是当染色体群体的质量下降（彼此区别减少）时增加变异概率；另一种是随机外来染色体，是偶尔加入一些全新的随机生成的染色体个体，从而增加染色体多样性[14]。还有如何改进操作手段或引入新操作手段来提高算法的执行效果，如何将该算法与其它传统优化方法有机结合起来等等问题。以上存在的问题有的已基本获得解决,而有的则正在解决当中。四、总结与展望遗传算法作为具有系统优化、适应和学习的高性能计算和建模方法的研究渐趋成熟。遗传算法具有进化计算的所有特征，同时又具有自身的特点[15]：（1）搜索过程既不受优化函数的连续性约束，也没有优化函数导数必须存在的要求（2）遗传算法采用多点搜索或者说是群体搜索，具有很高的隐含并行性，因而可以提高计算速度（3）遗传算法是一种自适应搜索技术，其选择交叉变异等运算都是以一种概率方式来进行，从而增加了搜索过程的灵活性，具有较好的全局优化求解能力（4）遗传算法直接以目标函数值为搜索信息，对函数的性态无要求，具有较好的普适性和易扩充性（5）遗传算法更适合大规模复杂问题的优化但遗传算法也存在很多问题，如：（1）Holland在运用模式定理分析编码机制时建议使用二进制编码，但二进制编码不能直接反映问题的固有结构、精度不高、个体长度大和占用计算机内存多[16]。解决这个问题的措施有：①动态编码即在保持串长不变的前提下减小搜索区域，当算法收敛到某局部最优时增加搜索的精度，从而使得在全局最优点附近可以进行更精确的搜索[17]。②对于问题的变量是实向量的情形，可以直接采用实数进行编码，便于引入与问题领域相关的启发式信息以增加算法的搜索能力[18]。③复数编码本是为了描述和解决二维问题，还可以推广到多维问题的描述中[19]。（2）适应度函数[20]：适应度函数是用来区分群体中个体好坏的标准，选择的好坏直接影响算法的优劣，选择的不好容易引起两种不利于优化的现象：①异常个体引起早熟收敛，影响求得全局最优解这种现象常出现在小规模群体中。②个体差距不大引起搜索成为随机漫游，特别是平均适应度已接近最佳适应度时，最佳个体与其他许多个体在选择过程中就会有大体相等的选择机会，影响求得最优解。（3）选择策略[21]：优胜劣汰的选择机制使得适应值大的个体有较大的存活机会，不同的选择策略对算法性能有较大的影响轮盘赌法是使用最多的选择策略，但这种策略可能会产生较大的抽样误差，对此提出了很多的改进方法，如繁殖池选择、非线性排名选择、基于局部竞争机制的选择等。（4）控制参数[22]：群体大小、交换概率、变异概率等这些参数对遗传算法性能影响较大，会影响算法的全局最优性和收敛性Davis提出自适应算子概率的方法，用自适应机制把算子概率与算子产生的个体适应性结合，而且高适应性值被分配高算子概率这种方法较好地解决了这一问题。随着应用领域的扩展，遗传算法的研究出现了几个引人注目的新动向：一是基于遗传算法的机器学习，这一新的研究课题把遗传算法从历来离散的搜索空间的优化搜索算法扩展到具有独特的规则生成功能的崭新的机器学习算法。这一新的学习机制对于解决人工智能中知识获取和知识优化精炼的瓶颈难题带来了希望。二是遗传算法正日益和神经网络、模糊推理以及混沌理论等其它智能计算方法相互渗透和结合，这对开拓21世纪中新的智能计算技术将具有重要的意义。三是并行处理的遗传算法的研究十分活跃。这一研究不仅对遗传算法本身的发展，而且对于新一代智能计算机体系结构的研究都是十分重要的。四是遗传算法和另一个称为人工生命的崭新研究领域正不断渗透。所谓人工生命即是用计算机模拟自然界丰富多彩的生命现象，其中生物的自适应、进化和免疫等现象是人工生命的重要研究对象，而遗传算法在这方面将会发挥一定的作用，五是遗传算法和进化规划（EvolutionProgramming,EP）以及进化策略（EvolutionStrategy,ES）等进化计算理论日益结合。EP和ES几乎是和遗传算法同时独立发展起来的，同遗传算法一样，它们也是模拟自然界生物进化机制的智能计算方法，即同遗传算法具有相同之处，也有各自的特点。这三者之间的比较研究和彼此结合的探讨正形成热点。参考文献：李敏强，寇继松，林丹，李书全.遗传算法的基本理论与应用[M].北京：科学出版社，2002.3．L.Davis,HandbookofGeneticAlgorithms,vanNostrandRei－nhold,NewYork，1991．席裕庚，柴天佑，恽为民．遗传算法综述．1996，13（60）:69－7－708．刘勇，等．非数值并行算法（二）遗传算法[M]．北京:科学出版社，1995．陈国良，等．遗传算法及应用．BehaviourofAClassofGeneticAdaptiveSystems[D]．UniversityofMichigan，1975．孙艳丰．王众托．自然数编码遗传算法的最优种群规模[J]．沈阳：信息与控制，1996（5）．陈文清．遗传算法综述[J]．洛阳：洛阳高等专科学校学报，2003．徐清振，肖成林．遗传算法的研究与应用[J]．广州：现代计算机，2006．章晓级，戴冠中，徐乃平．一种新的优化搜索算法-遗传算法[J]．广州：控制理论与应用．1999，12（3）:365－273．TomM．Michell．机器学习[M]．北京：机械工业出版社，2003．(美）卡伦著．人工智能．黄厚宽，等译．北京：电子工业出版社，2004．Goldberg,DavidE．创新的设计:竞争遗传算法课程[M]，Addison-Wesley,Reading，MA.2002.Schmitt，LotharM，遗传算法理论[M]，TheoreticalComputerScience(259)，pp。1-61,2001．Schmitt，LotharM，遗传算法理论(二)[M]，TheoreticalComputerScience(310)，pp.181-231,2004．Vose,MichaelD,简单遗传算法：基础和理论[M].MITPress，Cambridge，MA，1999．PanZJ,KangLS．AnAdaptiveEvolutionaryAlgorithmsforNumericalOptimization．Proc．ofSEAL＇96,Taejon,Korea,1996:53－60．BrawnH.OnSolvingTravelingSalesmanProblemsbyGeneticAlgorithms[J].王小平,曹立明.遗传算法--理论应用与软件实现[M].西安:西安交通大学出版社,2002.PowllD.TongS,SkolnikM.EnGENEous:DomainIndependent,MachineforDesignOptimization[J].ProcofICGA-89,1989.StenderJ(Ed).ParallelGeneticAlgorithms[J].TheoryandApplication.ISOPress,1993.ooker,GoldbergLB,HollandJH.ClassifierSystemsandGeneticAlgorithmIntelligence[J].1989,40:235-282.BosmanPAN,ThierensD.Thebalancebetweenproximityanddiversityinmulti-objectiveevolutionaryalgorithms[J].IEEETransactionsonEvolutionaryComputation,2003,7(2):174-188.基于C8051F单片机直流电动机反馈控制系统的设计与研究基于单片机的嵌入式Web服务器的研究MOTOROLA单片机MC68HC（8）05PV8/A内嵌EEPROM的工艺和制程方法及对良率的影响研究基于模糊控制的电阻钎焊单片机温度控制系统的研制基于MCS-51系列单片机的通用控制模块的研究基于单片机实现的供暖系统最佳启停自校正（STR）调节器单片机控制的二级倒立摆系统的研究基于增强型51系列单片机的TCP/IP协议栈的实现基于单片机的蓄电池自动监测系统基于32位嵌入式单片机系统的图像采集与处理技术的研究基于单片机的作物营养诊断专家系统的研究基于单片机的交流伺服电机运动控制系统研究与开发基于单片机的泵管内壁硬度测试仪的研制基于单片机的自动找平控制系统研究基于C8051F040单片机的嵌入式系统开发基于单片机的液压动力系统状态监测仪开发模糊Smith智能控制方法的研究及其单片机实现一种基于单片机的轴快流CO〈,2〉激光器的手持控制面板的研制基于双单片机冲床数控系统的研究基于CYGNAL单片机的在线间歇式浊度仪的研制基于单片机的喷油泵试验台控制器的研制基于单片机的软起动器的研究和设计基于单片机控制的高速快走丝电火花线切割机床短循环走丝方式研究基于单片机的机电产品控制系统开发基于PIC单片机的智能手机充电器基于单片机的实时内核设计及其应用研究基于单片机的远程抄表系统的设计与研究基于单片机的烟气二氧化硫浓度检测仪的研制基于微型光谱仪的单片机系统单片机系统软件构件开发的技术研究基于单片机的液体点滴速度自动检测仪的研制基于单片机系统的多功能温度测量仪的研制基于PIC单片机的电能采集终端的设计和应用基于单片机的光纤光栅解调仪的研制气压式线性摩擦焊机单片机控制系统的研制基于单片机的数字磁通门传感器基于单片机的旋转变压器-数字转换器的研究基于单片机的光纤Bragg光栅解调系统的研究单片机控制的便携式多功能乳腺治疗仪的研制基于C8051F020单片机的多生理信号检测仪基于单片机的电机运动控制系统设计Pico专用单片机核的可测性设计研究基于MCS-51单片机的热量计基于双单片机的智能遥测微型气象站MCS-51单片机构建机器人的实践研究基于单片机的轮轨力检测基于单片机的GPS定位仪的研究与实现基于单片机的电液伺服控制系统用于单片机系统的MMC卡文件系统研制基于单片机的时控和计数系统性能优化的研究基于单片机和CPLD的粗光栅位移测量系统研究单片机控制的后备式方波UPS提升高职学生单片机应用能力的探究基于单片机控制的自动低频减载装置研究基于单片机控制的水下焊接电源的研究基于单片机的多通道数据采集系统基于uPSD3234单片机的氚表面污染测量仪的研制基于单片机的红外测油仪的研究96系列单片机仿真器研究与设计基于单片机的单晶金刚石刀具刃磨设备的数控改造基于单片机的温度智能控制系统的设计与实现基于MSP430单片机的电梯门机控制器的研制基于单片机的气体测漏仪的研究基于三菱M16C/6N系列单片机的CAN/USB协议转换器基于单片机和DSP的变压器油色谱在线监测技术研究基于单片机的膛壁温度报警系统设计基于AVR单片机的低压无功补偿控制器的设计基于单片机船舶电力推进电机监测系统基于单片机网络的振动信号的采集系统基于单片机的大容量数据存储技术的应用研究基于单片机的叠图机研究与教学方法实践基于单片机嵌入式Web服务器技术的研究及实现基于AT89S52单片机的通用数据采集系统基于单片机的多道脉冲幅度分析仪研究机器人旋转电弧传感角焊缝跟踪单片机控制系统基于单片机的控制系统在PLC虚拟教学实验中的应用研究基于单片机系统的网络通信研究与应用基于PIC16F877单片机的莫尔斯码自动译码系统设计与研究基于单片机的模糊控制器在工业电阻炉上的应用研究基于双单片机冲床数控系统的研究与开发基于Cygnal单片机的μC/OS-Ⅱ的研究基于单片机的一体化智能差示扫描量热仪系统研究基于TCP/IP协议的单片机与Internet互联的研究与实现变频调速液压电梯单片机控制器的研究基于单片机γ-免疫计数器自动换样功能的研究与实现基于单片机的倒立摆控制系统设计与实现单片机嵌入式以太网防盗报警系统基于51单片机的嵌入式Internet系统的设计与实现单片机监测系统在挤压机上的应用MSP430单片机在智能水表系统上的研究与应用基于单片机的嵌入式系统中TCP/IP协议栈的实现与应用单片机在高楼恒压供水系统中的应用基于ATmega16单片机的流量控制器的开发基于MSP430单片机的远程抄表系统及智能网络水表的设计基于MSP430单片机具有数据存储与回放功能的嵌入式电子血压计的设计基于单片机的氨分解率检测系统的研究与开发HYPERLINK"/detail.htm?3