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

PAGE9 本科毕业设计文献综述（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,Taej