遗传算法的由来及应用经验分享 2009-05-31 23:42 阅读157评论0字号：大中小遗传算法的研究前背景和发展历史1967年，Holland的学生J.D.Bagley在博士论文中首次提出“遗传算法(Genetic Algorithms)H一词 此后，Holland指导学生完成了多篇有关遗传算法研究的论文1971年，R.B.Hollstien在他的博士论文中 首次把遗传算法用于函数优化1975年是遗传算法研究历史上十分重要的一年这一年Holland出版了他 的著名专著《自然系统和人工系统的自适应》(Adaptation in Natural and Artificial Systems)，这是第一 本系统论述遗传算法的专著，因此有人把1975年作为遗传算法的诞生年Holland在该书中系统地阐述了 遗传算法的基本理论和方法，并提出了对遗传算法的理论研究和发展极其重要的模式理论(schema theor y)该理论首次确认了结构重组遗传操作对于获得隐并行性的重要性同年，K.A.De Jong完成了他的博 士论文《一类遗传自适应系统的行为分析》(An Analysis of the Behavior of a Class of Genetic Adaptive S ystem)。
该论文所做的研究工作，可看作是遗传算法发展进程中的一个里程碑，这是因为，他把Holland 的模式理论与他的计算实验结合起来尽管De Jong和Hollstien 一样主要侧重于函数优化的应用研究，但 他将选择、交叉和变异操作进一步完善和系统化，同时又提出了诸如代沟(generation gap)等新的遗传 操作技术可以认为，De Jong的研究工作为遗传算法及其应用打下了坚实的基础，他所得出的许多结论， 迄今仍具有普遍的指导意义进入八十年代，遗传算法迎来了兴盛发展时期，无论是理论研究还是应用研究都成了十分热门的课题1985 年，在美国召开了第一届遗传算法国际会议(International Conference on Genetic Algorithms，ICGA)，并且成立国际遗传算法学会(International Society of Genetic Algorithms，ISGA)，以后每两年举行一次1989年，Holland的学生D.E.Goldberg出版了专著《搜索、优化和机器学习中的遗传算法》(Genetic Al gorithms in Search , Optimization, and Machine Learning)。
该书总结了遗传算法研究的主要成果，对遗 传算法及其应用作了全面而系统的论述同年，美国斯坦福大学的Koza基于自然选择原则创造性地提出 了用层次化的计算机程序来表达问题的遗传程序设计(genetic programming, GP)方法，成功地解决了许多 问题在欧洲，从1990年开始每隔一年举办一次Parallel Problem Solving from Nature学术会议，其中遗 传算法是会议主要内容之一此外，以遗传算法的理论基础为中心的学术会议还有Foundations of Geneti c Algorithms，该会也是从1990年开始隔年召开一次这些国际会议论文，集中反映了遗传算法近些年来 的最新发展和动向1991年，L.Davis编辑出版了《遗传算法手册》(Handbook of Genetic Algorithms)，其中包括了 遗传算法在工程技术和社会生活中的大量应用实例1992年，Koza发表了他的专著《遗传程序设计:基于自然选择法则的计算机程序设计》”1994年， 他又出版了《遗传程序设计，第二册:可重用程序的自动发现》深化了遗传程序设计的研究，使程序设计自 动化展现了新局面。
有关遗传算法的学术论文也不断在《Artificial Intelligence》、《Machine Learning》、 《Information science》、《Parallel Computing》、《Genetic Programming and Evoluable Machines》' 《IEEE Transactions on Neural Networks》，《IEEE Transactions on Signal Processing》等杂志上发表 1993 年，MIT 出版社创刊了新杂志《Evolutionary Computation》1997 年，IEEE 又创刊了《Transacti ons on Evolutionary Computation》°《Advanced Computational Intelligenc e》杂志即将发刊，由模糊集 合创始人L.A.Zadeh教授为名誉主编目前，关于遗传算法研究的热潮仍在持续，越来越多的从事不同领 域的研究人员巳经或正在置身于有关遗传算法的研究或应用之中当前科学技术正进入多学科互相交叉、互相渗透、互相影响的时代，生命科学与工程科学的交叉、渗 透和相互促进是其中一个典型例子，也是近代科学技术发展的一个显著特点。
遗传算法的蓬勃发展正体现 了科学发展的这一特点和趋势制造机器智能一直是人类的梦想，人们为此付出了巨大的努力人工智能技术的出现，就是人们得到 的成果但是，近年来，随着人工智能应用领域的不断拓广，传统的基于符号处理机制的人工智能方法在 知识表示、处理模式信息及解决组合爆炸等方面所碰到的问题巳变得越来越突出，这些困难甚至使某些学 者对强人工智能提出了强烈批判，对人工智能的可能性提出了质疑众所周知，在人工智能领域中，有不少问题需要在复杂而庞大的搜索空间中寻找最优解或准优解像 货朗担问题和规划问题等组合优化问题就是典型的例子在求解此类问题时，若不能利用问题的固有知识 来缩小搜索空间则会产生搜索的组合爆炸因此，研究能在搜索过程中自动获得和积累有关搜索空间的知 识，并能自适应地控制搜索过程，从而得到最优解或准有解的通用搜索算法一直是令人瞩目的课题遗传 算法就是在这种背景下产生并经实践证明特别有效的算法遗传算法(Genetic Algorithm, GA)是近年来迅速发展起来的一种全新的随机搜索与优化算法,其基本 思想是基于Darw in的进化论和Mendel的遗传学说该算法由密执安大学教授Holland及其学生于1975 年创建。
此后，遗传算法的研究引起了国内外学者的关注自1985年以来.国际上巳召开了多次遗传算法 的学术会议和研讨会.国际遗传算法学会组织召开的ICGA( International Conference on Genetic Algorit hms)会议和FOGA( Workshop on Foundation of Genetic Algorithms)会议为研究和应用遗传算法提供了 国际交流的机会作为一种通用的问题求解方法，遗传算法采用简单的编码技术来表示各种复杂的结构并通过对一组编 码表示进行简单的遗传操作和优胜劣汰的自然选择来指导学习和确定搜索的方向近年来，遗传算法巳被成功地应用于下业、经济答理、交通运输、工业设计等不同领域.解决了许多 问题例如，可靠性优化、流水车间调度、作业车间调度、机器调度、设备布局设计、图像处理以及数据 挖掘等本文将从遗传算法的理论和技术两方而概述目前的研究现状描述遗传算法的主要特点、基木原 理以及各种改进算法，介绍遗传算法的程序设计遗传程序设计是借鉴生物界的自然选择和遗传机制，在遗传算法的基础上发展起来的搜索算法，它 己成为进化计算的一个新分支在标准的遗传算法中，由定长字符串(问题的可行解)组成的群体借助于复 制、交叉、变异等遗传操作不断进化找到问题的最优解或次优解。
遗传程序设计运用遗传算法的思想，常 采用树的结构来表示计算机程序，从而解决问题对于许多问题，包括人工智能和机器学习上的问题都可 看作是需要发现一个计算机程序，即对特定输入产生特定输出的程序，形式化为程序归纳，那么遗传程序 设计提供了实现程序归纳的方法把遗传算法和计算机程序结合起来的思想出现在遗传算法中，Holland把产生式语言和遗传算法结合 起来实现分类系统，还有一些遗传算法应用领域的研究者将类似于遗传算法的遗传操作施加于树结构的程 序上近年来，遗传程序设计运用遗传算法的思想自动生成计算机程序解决了许多问题，如预测、分类、符号回 归和图像处理等，作为一种新技术它己经与遗传算法并驾齐驱1996年，举行了第1次遗传程序设计国 际会议，该领域己引起越来越多的相关学者们的兴趣遗传算法简介遗传算法(Genetic Algorithm，简称GA)是一种基于进化论优胜劣汰、适者生存的物种遗传思想的搜索算法 本世纪50年代初，由于一些生物学家尝试用计算机模拟生物系统，从而产生了 GA的基本思想美国密执 根大学的霍勒德(J.H.Holland)于70年代初提出并创立了遗传算法遗传算法作为一种解决复杂问题的 崭新的有效优化方法，近年来得到了广泛的实际应用，同时也渗透到人工智能、机器学习、模式识别、图 像处理、软件技术等计算机学科领域。
GA在机器学习领域中的一个典型应用就是利用GA技术作为规则发 现方法应用于分类系统遗传算法将个体的集合——群体作为处理对象，利用遗传操作——交换和突变，使群体不断"进化"，直到 成为满足要求的最优解在霍勒德的GA算法中采用二进制串来表示个体考虑到物种的进化或淘汰取决于它们在自然界中的 适应程度，GA算法为每一个体计算一个适应值或评价值，以反映其好坏程度因而，个体的适应值越高， 就有更大的可能生存和再生，即它的表示特征有更大的可能出现在下一代中遗传操作"交换"旨在通过交 换两个个体的子串来实现进化；遗传操作"突变"则随偶地改变串中的某一（些）位的值，以期产生新的遗 传物质或再现巳在进化过程中失去的遗传物质霍勒德提出的遗传算法也称为简单遗传算法（simple genetic algorithm,SGA），是一种基本的遗传 算法SGA的处理过程如下：begin1. 选择适当表示，生成初始群体；2. 评估群体；3. While未达到要求的目标dobegin1. 选择作为下一代群体的各个体；2. 执行交换和突变操作；3. 评估群体；endend因此，对于一个SGA算法来说主要涉及以下内容：•编码和初始群体生成；•群体的评价；•个体的选择；■交换；•突变；1. 编码和初始群体的生成GA的工作基础是选择适当的方法表示个体和问题的解（作为进化的个体）°SGA要求个体均以0、1 组成的串来表示，且所有个体串都是等长的。
实际上，可以任意指定有限元素组成的串来表示个体，而不 影响GA的基本算法对于同一问题，可以有不同的编码表示方法由于遗传操作直接作用于所表示的串上，因而不同的表 示方法对SGA的效率和结果都会有影响从原理上讲，任何取值为整数（或其它有限可枚举的值）的变量， 均可用有限长度的0、1串来表示，而任何取值为连续实数的变量也均可用有限长度的0、1串来近似表示 因此，对任何一个变量，均可在一定程度上用0、1串来表示（编码），而当问题的解涉及多个变量时，则 可用各变量对应串的拼接（形成一个长串）来表示相应解SGA处理的起始点并非一个个体，而是由一组个体所组成的群体一般可用随机方法来产生初始群体， 当然最好能考虑各个体的代表性和分布概率2. 群体的评价对群体中各个体的适应性评价常需直接利用待优化问题的目标函数这一目标函数也可称为适应函数， 个体选择（或再生）过程正是基于这一函数来评价当前群体中各个体的再生概率3. 个体的选择选择操作是对自然界"适者生存"的模拟评价值（目标函数值）较大的个体有较高的概率。