身心健康知识讲座

遗传算法理论与应用遗传算法(geneticalgorithms,GA)是人工智能的重要新分支，是基于达尔文进化论，在微型计算机上模拟生命进化机制而发展起来的一门新学科。它根据适者生存、优胜劣汰等自然进化规则来进行搜索计算和问题求解。遗传算法是模拟生物在自然环境中的遗传和进化过程而形成的一种自适应全局优化概率搜索算法。它最早由美国密执安大学的Holland教授提出，起源于60年代对自然和人工自适应系统的研究。遗传算法对许多用传统数学难以解决或明显失效的非常复杂问题，特别是最优化问题，GA提供了一个行之有效的新途径。一.遗传算法的发展遗传算法起源于对生物系统所进行的计算机模拟研究。早在20世纪40年代，就有学者开始如何利用计算机进行生物模拟的技术，他们从生物学的角度进行了生物的进化过程模拟、遗传过程模拟等研究工作。进入60年代后，美国密执安大学的Holland教授及其学生们受到这种生物模拟技术的启发，创造出了一种基于生物遗传和进化机制的适合于复杂系统优化计算的自适应概率优化技术——遗传算法。下面是在遗传算法的发展进程中一些关键人物所做出的一些主要贡献。1.J．H．Holland20世纪60年代，Holland认识到了生物的遗传和自然进化现象与人工自适应系统的相似关系，运用生物遗传和进化的思想来研究自然和人工自适应系统的生成以及它们与环境的关系，提出在研究和设计人工自适应系统时，可以借鉴生物遗传的机制，以群体的方法进行自适应搜索，并且充分认识到了交叉、变异等运算策略在自适应系统中的重要性。70年代，Holland教授提出了遗传算法的基本定理——模式定理(SchemaTheorem)，从而奠定了遗传算法的理论基础。模式定理揭示出了群体中的优良个体(较好的模式)的样本数将以指数级规律增长，因而从理论上保证了遗传算法是一个可以用来寻找最优可行解的优化过程。1975年，Holland出版了第一本系统论述遗传算法和人工自适应系统的专著《自然系统和人工系统的自适应性(AdaptationinNaturalandArtificialSystems)》。80年代，Holland教授实现了第一个基于遗传算法的机器学习系统——分类器系统(ClassifierSystems，简称CS)，开创了基于遗传算法的机器学习的新概念，为分类器系统构造出了一个完整的框架。2.J．D．Bagley1967年，Holland的学生Bagley在其博士论文中首次提出了“遗传算法”一词，并发表了遗传算法应用方面的第一篇论文。他发展了复制、交叉、变异、显性、倒位等遗传算子，在个体编码上使用了双倍体的编码方法。这些都与目前遗传算法中所使用的算子和方法相类似。他还敏锐地意识到了在遗传算法执行的不同阶段可以使用不同的选择率，这将有利于防止遗传算法的早熟现象，从而创立了自适应遗传算法的概念。3.K．A．DeJong1975年，DeJong在其博士论文中结合模式定理进行了大量的纯数值函数优化计算实验，树立了遗传算法的工作框架，得到了一些重要且具有指导意义的结论。例如，对于规模在50~100的群体，经过10~20代的进化，遗传算法都能以很高的概率找到最优或近似最优解。他推荐了在大多数优化问题中都较适用的遗传算法的参数，还建立了著名的DeJong五函数测试平台，定义了评价遗传算法性能的在线指标和离线指标。4.D．J．Goldberg1989年，Goldberg出版了专著《搜索、优化和机器学习中的遗传算法(GeneticAlgorithmsinSearch,OptimizationandMachineLearning)》。该书系统总结了遗传算法的主要研究成果，全面而完整地论述了遗传算法的基本原理及其应用。可以说这本书奠定了现代遗传算法的科学基础，为众多研究和发展遗传算法的学者所瞩目。5.L．Davis1991年，Davis编辑出版了《遗传算法手册(HandbookofGeneticAlgorithms)》一书，书中包括了遗传算法在科学计算、工程技术和社会经济中的大量应用实例。这本书为推广和普及遗传算法的应用起到了重要的指导作用。6.J．R．Koza1992年，Koza将遗传算法应用于计算机程序的优化设计及自动生成，提出了遗传编程(GeneticProgramming，简称GP)的概念。他将一段LISP语言程序作为个体的基因型，把问题的解编码为一棵树，基于遗传和进化的概念，对由数组成的群体进行遗传运算，最终自动生成性能较好的计算机程序。Koza成功地把他提出的遗传编码的方法应用于人工智能、机器学习、符号处理等方面。二．遗传算法的原理和特点遗传算法将生物进化原理引入待优化参数形成的编码串群体中，按着一定的适值函数及一系列遗传操作对各个个体进行筛选，从而使适值高的个体被保留下来，组成新的群体，新群体包含上一代的大量信息，并且引入了新的优于上一代的个体。这样周而复始，群体中各个体适值不断提高，直至满足一定的极限条件。此时，群体中适值最高的个体即为待优化参数的最优解。正是由于遗传算法独具特色的工作原理，使它能够在复杂空间进行全局优化搜索，并且具有较强的鲁棒性；另外，遗传算法对于搜索空间，基本上不需要什么限制性的假设（如连续、可微及单峰等）。同常规优化算法相比，遗传算法有如下特点：（1）遗传算法是对参数的编码进行操作，而非对参数本身。遗传算法首先基于一个有限的字母表，把最优化问题的自然参数集编码为有限长度的字符串。例如，一个最优化问题：在整数区间[0,31]上求函数2()fxx的最大值。若采用传统方法，需不断调节x参数的取值，直至得到最大的函数值为止。而采用遗传算法，优化过程的第一步是把参数x编码为有限长度的字符串，常用二进制字符串，设参数x的编码长度为5，“00000”代表0，“11111”代表31，区间[0,31]上的数与二进制编码之间采用线性映射方法；随机生成几个这样的字符串组成初始群体，对群体中的字符串进行遗传操作，直至满足一定的终止条件；求得最终群体中适值最大的字符串对应的十进制数，其相应的函数值则为所求解。可以看出，遗传算法是对一个参数编码群体进行操作，这样提供的参数信息量大，优化效果好。（2）遗传算法是从许多点开始并行操作，并非局限于一点，从而可有效防止搜索过程收敛于局部最优解。（3）遗传算法通过目标函数计算适值，并不需要其他推导和附加信息，因而对问题的依赖性较小。（4）遗传算法的寻优规则是由概率决定的，而非确定性的。（5）遗传算法在解空间进行高效启发式搜索，而非盲目地穷举或完全随机搜索。（6）遗传算法对所求解的优化问题没有太多的数学要求。由于它的进化特性，它在解的搜索中不需要了解问题的内在性质。遗传算法可以处理任意形式的目标函数和约束，无论是线性的还是非线性的，离散的还是连续的，甚至是混合的搜索空间。（7）遗传算法具有并行计算的特点，因而可通过大规模并行计算来提高计算速度。三．遗传算法的应用遗传算法提供了一种求解复杂杂系统优化问题的通用框架，它不依赖于问题的具体领域，对问题的种类有很强的鲁棒性，所以广泛应用于很多学科。下面是遗传算法的一些主要应用领域：（1）函数优化。函数优化是遗传算法的经典应用领域，也是对遗传算法进行性能评价的常用算例。很多人构造出了各种各样的复杂形式的测试函数，有连续函数也有离散函数，有凸函数也有凹函数，有低维函数也有高维函数，有确定函数也有随机函数，有单峰值函数也有多峰值函数等。用这些几何特性各具特色的函数来评价遗传算法的性能，更能反映算法的本质效果。而对于一些非线性、多模型、多目标的函数优化问题，用其他优化方法较难求解，而遗传算法却可以方便地得到较好的结果。（2）组合优化。随着问题规模的增大，组合优化问题的搜索空间也急剧扩大，有时在目前的计算机上用枚举法很难或甚至不可能求出其精确最优解。对这类复杂问题，人们已意识到应把主要精力放在寻求其满意解上，而遗传算法是寻求这种满意解的最佳工具之一。实践证明，遗传算法对于组合优化中的NP完全问题非常有效。例如，遗传算法已经在求解旅行商问题、背包问题、装箱问题、图形划分问题等方面得到成功的应用。（3）生产调度问题。生产调度问题在很多情况下所建立起来的数学模型难以精确求解，即使经过一些简化之后可以进行求解，也会因简化得太多而使得求解结果与实际相差甚远。而目前在现实生产中也主要是靠一些经验来进行调度。现在遗传算法已成为解决复杂调度问题的有效工具，在单件生产车间调度、流水线生产车间调度、生产规划、任务分配等方面遗传算法都得到了有效的应用。（4）自动控制。在自动控制领域中有很多与优化相关的问题需要求解，遗传算法已在其中得到了初步的应用，并显示出了良好的效果。例如用遗传算法进行航空控制系统的优化、使用遗传算法设计空间交会控制器、基于遗传算法的模糊控制器的优化设计、基于遗传算法的参数辨识、基于遗传算法的模糊控制规则的学习、利用遗传算法进行人工神经网络的结构优化设计和权值学习等，都显示出了遗传算法在这些领域中应用的可能性。（5）机器人学。机器人是一类复杂的难以精确建模的人工系统，而遗传算法的起源就来自于对人工自适应系统的研究，所以机器人学理所当然地成为遗传算法的一个重要应用领域。例如，遗传算法已经在移动机器人路径规划、关节机器人运动轨迹规划、机器人逆运动学求解、细胞机器人的结构优化和行为协调等方面得到研究和应用。（6）图像处理。图像处理是计算机视觉中的一个重要研究领域。在图像处理过程中，如扫描、特征提取、图像分割等不可避免地会存在一些误差，这些误差会影响图像处理的效果。如何使这些误差最小是使计算机视觉达到实用化的重要要求。遗传算法在这些图像处理中的优化计算方面找到了用武之地，目前已在模式识别、图像恢复、图像边缘特征提取等方面得到了应用。（7）人工生命。人工生命是用计算机、机械等人工媒体模拟或构造出的具有自然生物系统特有行为的人造系统。自组织能力和自学能力是人工生命的两大主要特征。人工生命与遗传算法有着密切的关系，基于遗传算法的进化模型是研究人工生命现象的重要基础理论。虽然人工生命的研究尚处于启蒙阶段，但遗传算法已在其进化模型、学习模型、行为模型、自组织模型等方面显示出了初步的应用能力，并且必将得到更为深入的应用和发展。人工生命与遗传算法相辅相成，遗传算法为人工生命的研究提供了一个有效的工具，人工生命的研究也必将促进遗传算法的进一步发展。（8）遗传编程。Koza发展了遗传编程的概念，他使用了以LISP语言所表示的编码方法，基于对一种树型结构所进行的遗传操作来自动生成计算机程序。虽然遗传编程的理论尚未成熟，应用也有一些限制，但它已成功地应用于人工智能、机器学习等领域。（9）机器学习。学习能力是高级自适应系统所应具备的能力之一。基于遗传算法的机器学习，特别是分类器系统，在很多领域中都得到了应用。例如，遗传算法被用于学习模糊控制规则，利用遗传算法来学习隶属度函数，从而更好地改进了模糊系统的性能；基于遗传算法的机器学习可用来调整人工神经网络的连接权，也可用于人工神经网络的网络结构优化设计；分类器系统也在学习式多机器人路径规划系统中得到了成功的应用。四．遗传算法的基本遗传学基础遗传算法是根据生物进化的模型提出的一种优化算法。自然选择学说是进化论的中心内容，根据进化论，生物的发展进化主要由三个原因，即遗传、变异和选择。遗传是指子代总是和亲代相似。遗传性是一切生物所共有的特性，它使得生物能够把它的特性、性状传给后代。遗传是生物进化的基础。变异是指子代和亲代有某些不相似的现象，即子代永远不会和亲代完全一样。它是一切生物所具有的共有特性，是生物个体之间相互区别的基础。引起变异的原因主要是生活环境的影响、器官使用的不同及杂交。生物的变异性为生物的进化和发展创造了条件。选择是指具有精选的能力，它决定生物进化的方向。在进化过程中，有的要保留，有的要被淘汰。自然选择是指生物在自然界的生存环境中适者生存，不适者被淘汰的过程。通过不断的自然选择，有利于生存的变异就会遗传下去，积累起来，使变异越来越大，逐步产生了新的物种。生物就是在遗传、变异和选择三种因素