ISDA2006CCML2006TwoSpecialTalksHere第九章遗传算法9.1遗传算法的发展2．1975年是遗传算法研究历史上十分重要的一年。这一年Holland出版了他的著名专著《自然系统和人工系统的自适应》（AdaptationinNaturalandArtificialSystems），这是第一本系统论述遗传算法的专著，因此有人把1975年作为遗传算法的诞生年。Holland在该书中系统地阐述了遗传算法的基本理论和方法，并提出了对遗传算法的理论研究和发展极其重要的模式理论（schematheory）。该理论首次确认了结构重组遗传操作对于获得隐并行性的重要性。3．同年，K.A.DeJong完成了他的博士论文《一类遗传自适应系统的行为分析》（AnAnalysisoftheBehaviorofaClassofGeneticAdaptiveSystem）。该论文所做的研究工作，可看作是遗传算法发展进程中的一个里程碑，这是因为，他把Holland的模式理论与他的计算实验结合起来。尽管DeJong和Hollstien一样主要侧重于函数优化的应用研究，但他将选择、交叉和变异操作进一步完善和系统化，同时又提出了诸如代沟（generationgap）等新的遗传操作技术。可以认为，DeJong的研究工作为遗传算法及其应用打下了坚实的基础，他所得出的许多结论，迄今仍具有普遍的指导意义。4．进入八十年代，遗传算法迎来了兴盛发展时期，无论是理论研究还是应用研究都成了十分热门的课题。1985年，在美国召开了第一届遗传算法国际会议（InternationalConferenceonGeneticAlgorithms，ICGA），并且成立国际遗传算法学会（InternationalSocietyofGeneticAlgorithms，ISGA），以后每两年举行一次。5．1989年，Holland的学生D.E.Goldberg出版了专著《搜索、优化和机器学习中的遗传算法》（GeneticAlgorithmsinSearch,Optimization,andMachineLearning）。该书总结了遗传算法研究的主要成果，对遗传算法及其应用作了全面而系统的论述。6．在欧洲，从1990年开始每隔一年举办一次ParallelProblemSolvingfromNature学术会议，其中遗传算法是会议主要内容之一。此外，以遗传算法的理论基础为中心的学术会议还有FoundationsofGeneticAlgorithms，该会也是从1990年开始隔年召开一次。这些国际会议论文，集中反映了遗传算法近些年来的最新发展和动向。7．1991年，L.Davis编辑出版了《遗传算法手册》（HandbookofGeneticAlgorithms），其中包括了遗传算法在工程技术和社会生活中的大量应用实例。8．有关遗传算法的学术论文也不断在《ArtificialIntelligence》、《MachineLearning》、《Informationscience》、《ParallelComputing》、《GeneticProgrammingandEvoluableMachines》\《IEEETransactionsonNeuralNetworks》,《IEEETransactionsonSignalProcessing》等杂志上发表。1993年，MIT出版社创刊了新杂志《EvolutionaryComputation》。1997年，IEEE又创刊了《TransactionsonEvolutionaryComputation》。《AdvancedComputationalIntelligence》杂志即将发刊，由模糊集合创始人L.A.Zadeh教授为名誉主编。目前，关于遗传算法研究的热潮仍在持续，越来越多的从事不同领域的研究人员已经或正在置身于有关遗传算法的研究或应用之中。9.2传统遗传算法3．编码和解码前者是把搜索空间中的参数或解转换成遗传空间中的染色体或个体，此过程称为编码（coding）操作；后者是前者的逆操作，称为解码（decoding）操作。表9.1生物遗传学与遗传算法基础术语对照表二、传统遗传算法图9.1遗传算法的基本流程遗传算法三个主要操作算子是选择（selection）、交叉（crossover）和变异（mutation），它们构成了所谓遗传操作（geneticoperation），使遗传算法具备了其他传统方法所没有的特性。遗传算法中包含如下五个基本要素：(1)参数编码；(2)初始群体的设定；(3)适应度函数的设计；(4)遗传操作设计；(5)操作参数设定（主要指群体规模及执行遗传操作的概率等）。假定