智能优化方法的改进王颖

河南财经政法大学成功学院本科生毕业论文(设计)智能优化方法的改进院系名称信息工程系姓名王颖学号2010341108专业计算机科学与技术指导教师李喜艳讲师2014年4月20I摘要遗传算法GAs(GeneticAlgorithms)是一种模拟自然界生物进化的智能优化算法,产生于一些生物学家用计算机模拟生物进化过程的仿真实验。1960年，美国的J．H．Holland把它创造性地应用于人工系统，并成功地利用它解决了一些实际问题，例如“旅行商问题，加上该算法简单易行、鲁棒性强，特别是他不需要专门的领域知识而仅用适应度函数作评价来指导搜索过程。从此，它的实用价值逐渐被人们所认识。特别是近十年，由于计算机性能的提高，以及并行分布式计算的推广，GAs由于自身独特的优势而越来越受到人们的重视[1,2]。遗传算法目前已经在优化控制、机器学习、模式识别、神经网络和并行处理等领域得到了越来越广泛的应用[3-6]。遗传算法是一种新兴的技术,正处于发展期。虽然在应用领域获得了丰收，但其理论基础还比较薄弱，有许多地方需要研究和发展充实。例如简单遗传算法SGAs(SimpleGeneticAlgorithms)由于自身固有的缺陷，通常优化过程的收敛速度较慢，而且算法稳定性较差。论文的主要工作是遗传算法的基本概念、构成要素、基本流程、收敛性、特点并举例验证了两种简单遗传算法。并针对遗传算法的一些问题做了一些简单的验证，通过对两种简单遗传代码的分析，举例说明，实践结果验证等，更加深入地研究和讨论遗传算法。并对这两种结果进行比较，得出两种算法的优劣，比以后的研究做准备。关键词：遗传算法；收敛性[7]；简单遗传算法；错误!未找到引用源。错误!未找到引用源。IIAbstractGeneticalgorithm(ga)GAsakindofintelligentoptimizationalgorithmofmimicnaturalbiologicalevolution,producedinsomebiologicalhomecomputeranalogsimulationexperimentofbiologicalevolution.In1960,theUnitedStatesJ.H.Hollandmakeitcreativelyappliedtotheartificialsystems,anduseitsuccessfullysolvessomeactualproblems,suchasthetravelingsalesmanproblem,andthisalgorithmissimple,strongrobustness,especiallyhedoesn'tneedspecialdomainknowledgeandinevaluationoffitnessfunctiontoguidethesearchprocess.Sincethen,itspracticalvalueisgraduallyknownbypeople.Especiallythepast10years,duetotheimprovementoftheperformanceofthecomputer,andtheexpansionofparallelanddistributedcomputation,GAsduetoitsuniqueadvantagesandmoreandmoreimportancebypeople.Geneticalgorithm(ga)isnowintheoptimizationcontrol,machinelearning,patternrecognition,neuralnetworksandparallelprocessing,andotherfieldshasbeenmoreandmorewidelyused.Geneticalgorithm(ga)isanemergingtechnologyandindevelopment.Althoughhadagoodharvestinthefieldofapplication,butitstheoreticalbasisisrelativelyweak,therearesomanyplacesneedtoenrichtheresearchanddevelopment.suchastheSimpleGeneticalgorithm(SimplebasedAlgorithms)duetoitsinherentdefect,usuallyslowerconvergencespeedofoptimizationprocess,andpoorstabilityofthealgorithm.Paper'smainworkisthebasicconceptofgeneticalgorithm,theconstituentelements,thebasicprocess,convergence,characteristicsandexamplesverifythetwokindsofsimplegeneticalgorithm.Andaimsatsomeproblemsofgeneticalgorithmtodosomesimpleauthentication,basedontheanalysisofthetwokindsofsimplegeneticcode,forexample,practicalresultsandsoon,morein-depthresearchanddiscussthegeneticalgorithm.Andcomparisonofthetwokindsofresults,itisconcludedthatthemeritsofthetwoalgorithms,thantoprepareforthelaterresearch.KeyWords:Geneticalgorithm;Convergence;Simplegeneticalgorithm;III目录1引言...................................................................41.1选题依据..............................................................41.2遗传算法的研究现状...................................................41.3本文的主要工作及章节安排.............................................42遗传算法简介..............................................................62.1遗传算法的基本概念....................................................62.2遗传算法的构成要素和流程图............................................62.2.1遗传编码.........................................................62.2.2适应度函数和尺度变换..............................................82.2.3算法参数..........................................................92.2.4遗传算法的基本流程..............................................102.3遗传算法的收敛性和特点...............................................112.3.1标准遗传算法的收敛性.............................................112.3.2遗传算法的特点...................................................112.4本章小结.............................................................123简单遗传算法步骤及两个实例分析说明......................................133.1简单遗传算法.........................................................133.2两种简单的算法流程分析...............................................133.3两种简单遗传算法的比较..............................................193.4本章小结............................................................214展望与总结...............................................................22参考文献..................................................................23致谢....................................................................2441引言1.1选题依据生物在自然界中的生存繁衍，显示了其对自然环境的优异的自适应能力。遗传算法所借鉴的生物学基础就是生物的进化和遗传。遗传算法是由美国J.Holland教授于20世纪60年代末到70年代初提出的。遗传算法的主要特点是采用群体搜索的方法和在种群中个体之间进行信息交换,利用简单的编码技术和遗传算子和选择策略来模拟自然界中的复杂现象,不受搜索空间范围大小的限制性假设的约束,不要求诸如导数是否存在和单峰、连续性等问题的假设。由J.Grefenstette和D.Goldberg等对先前的遗传算法进行了大量的改进，这就使得遗传算法可以应用到更宽广的领域。遗传算法目前在工业工程、人工智能、自动控制、模式识别、生物工程和并行处理等领域的成功应用，使得该算法得到了广泛的关注。在人工智能领域中,有不少问题需要在庞大而复杂的空间中寻找最优解或次优解。在求解典型的NP完全问题这类问题时,为了避免产生搜索的组合爆炸,必须利用问题的本身固有知识来缩小搜索空间的范围。因此能够在搜索过程中自动获得和积累有关搜索空间的知识并自适应地完成整个搜索过程,从而得到次优解或最优解[8-12]的通用的搜索算法一直是一个热门的话题。其中遗传算法就是能自适应地完成整个搜索过程的通用的特别有效的算法。遗传算法的主要特点是通用、简单并且他不依赖于问题的具体领域，对问题的种类有很强的鲁棒性[13]，应用范围广并适应于并行分布处理。虽然遗传算法本身在应用方法和理论上仍有待进一步的探索,但它在适应控制、适应控制、和人工生命组合优化问题求解等领域的应用中己展现出了其显著的特点(对全局信息的有效利用能力)。1.2遗传算法的研究现状近年来，遗传算法的研究领域出现了一些新的动向：一是基于遗传算法的机器学习，这一新的研究课题把遗传算法从历来离散的搜索空间的优化搜索算法扩展到具有独特的规则生成功能的机器学习算法。这一新的学习机制对于解决人工智能中知识获取和知识优化难题带来了希望。二是遗传算法和神经网络、模糊推理以及混沌理论等其它智能计算方法相互渗透和结合。三是并行处理的遗传算法的研究十分活跃，这一研究不仅对遗传算法本身的发展，而且还对于新一代智能计算机体系结构的研究都是十分重要的。四是遗传算法和人工生命的研究领域正在不断渗透。人工生