遗传算法简介.docVIP

第1章绪论

生物在自然界中的生存繁衍，显示出了其对自然环境的优异自适应能力。受其启发，人们致力于对生物各种生存特性的机理研究和行为模拟，为人工自适应系统的设计和开发提供了广阔的前景。遗传算法〔GeneticAlgorithms，简称GA〕就是这种生物行为的计算机模拟中令人瞩目的重要成果。基于对生物遗传和进化过程的计算机的模拟，遗传算法使得各种人工系统具有优良的自适应能力和优化能力。本章主要介绍遗传算法的起源、开展、特点及应用等问题。

问题的概述

遗传算法的生物学根底

生物在其延续生存的过程中，逐渐适应于其生存环境，使得其品质不断得到改进，这种生命现象称为进化〔Evolution〕生物进化是以集团形式进行的，这样的一个团体称为群体〔Population〕，组成群体的单个生物称为个体〔Individual〕，每个个体对其生存环境都有不同的适应能力，这种适应能力称为个体适应度〔Fitness〕。达尔文〔Darwin〕把在生存斗争适者生存，不适者淘汰的过程叫做自然选择〔NaturalSelection〕[1]。达尔文的自然选择学说说明，遗传和变异是决定生物进化的内在因素，生物开展进化主要有三个原因：遗传、变异和选择。遗传是指父代与子代之间，在性状上存在的相似现象。变异是指父代与子代之间，以及子代的个体之间，在性状上或多或少地存在的差异现象。选择是指具有精选的能力，它决定生物进化的方向。

世间的生物从其亲代继承特性或性状，这种生命现象就称为遗传〔Heredity〕，研究这种生命现象的科学叫做遗传学〔Genetics〕[2]。由于遗传的作用，使得人们可以种瓜得瓜、种豆得豆，也使得鸟仍然是在天空中飞翔，鱼仍然是在水中遨游。遗传算法正是吸取了自然生物系统“适者生存，优胜劣汰”的进化原理，从而使它能够提供一个在复杂空间中进行鲁棒有哪些信誉好的足球投注网站的方法，为解决许多传统的优化方法难以解决的优化问题提供了新的途径。

同传统的优化算法相比，遗传算法具有自己的特点。遗传算法是对参数的编码进行操作，而非对参数本身。遗传算法是从许多点开始并行操作，而非局限于一点，因而可以有效地防止有哪些信誉好的足球投注网站过程收敛于局部最优解。遗传算法通过目标函数来计算适值，而不需要其他推导和附加信息，从而对问题的依赖性较小。遗传算法的寻优规那么是由概率决定的，而非确定性的。当染色体结合时，双亲的遗传基因的结合使得子女保持父母的特征；当染色体结合后，随机的变异会造成子代同父代的不同。

另外，遗传算法对所解的优化问题没有太多的数学要求，在求解很多组合优化问题时，不需要有很强的技巧和对问题有非常深入的了解，因而应用范围广。遗传算法具有并行计算的特点，因而可通过大规模并行计算来提高计算速度。遗传算法更适合大规模复杂NP－hard优化问题的求解。遗传算法同求解问题的其他启发式算法有较好的兼容性，对于各种特殊问题可以提供极大的灵活性来混合构造领域独立的启发式，从而保证算法的有效性。当然，最重要的特点还是遗传算法计算简单，功能强。

遗传算法起源于对生物系统所进行的计算机模拟研究。早在本世纪40年代，就有学者开始研究如何利用计算机进行生物模拟的技术。进入60年代后，美国Michigan大学的Holland教授受到这种生物模拟技术的启发，创造出了一种基于生物遗传和进化机制的适合于复杂系统优化计算的自适应概率优化技术——遗传算法。70年代初，Holland提出了遗传算法的根本定理——模式定理〔SchemaTheorem〕，从而奠定了遗传算法的理论根底。1975年，Holland出版了其开创性的著作《自然和人工系统中的自适应性〔AdaptationinNaturalandArtificialSystems〕》[3]。

同年，DeJong基于遗传算法的思想在计算机上进行了大量的纯数值函数优化计算实验，他推荐了在大多数优化问题中都较适用的遗传算法的参数，还定义了评价遗传算法性能的在线指标和离线指标。在一系列研究工作的根底上，80年代由Goldberg进行归纳总结，出版了专著《有哪些信誉好的足球投注网站、优化和机器学习中的遗传算法〔GeneticAlgorithmsinSearch,OptimizationandMachineLearning〕》[4],从而形成了遗传算法的根本框架。

1991年，Davis编辑出版了《遗传算法手册〔HandbookofGeneticAlgorithms〕》[1]一书，此书为推广和普及遗传算法的应用起到了重要的指导作用。1992年，Koza将遗传算法应用于计算机程序的优化设及自动生成，提出了遗传编程〔GeneticProgramming，简称GP〕的概念。

正是由于80年代中期，遗传算法研究的蓬勃开展，吸引了大批的科学研究者和工程技术人员从事该领域的研究和开发应用工作。

尽管遗传算法