第九章遗传算法.ppt

第九章 遗传算法 ——第三篇 进化计算 ISDA2006 Whole name: International Conference on Intelligent System Design and Applications There are many famous experts: James Kennedy (An additional lecture on Friday) Edward Tseng Xinhe Xu Khalid Saeed Fuchun Sun et al. Gary G Yen: (A Special talk on EA on Monday) CCML2006 China Conference on Machine Learning: Hainan Experts: Shoujue Wang Libo Wang Shifu Chen Zhihua Zhou Jiali Feng Songchan Chen Et al Two Special Talks Here James Kennedy: Swarm Intelligence Gary G Yen: Evolutionary Multiobjective Optimization All in English Notes: Learn live English, not just for a certificate Learn how to solve problems, not just knowledge of techniques in exercises 第九章 遗传算法 遗传算法（Genetic Algorithm，GA）是一类以Darwin自然进化论和Mendel 遗传变异理论为基础的求解复杂全局优化问题的仿生型算法，它是由美国J.H.Holland教授首次提出的。 9.1 生物进化与遗传算法的发展 9.2 传统遗传算法 9.3 遗传算法的特点与研究课题 9.1 遗传算法的发展 1．遗传算法是在本世纪六七十年代由美国Michigan大学的J.H.Holland 教授及其学生和同事发展起来的。1967年，他的学生J.D.Bagley在博士论文中首次提出“遗传算法（Genetic Algorithms）”一词。此后，Holland指导学生完成了多篇有关遗传算法研究的论文。1971年，R.B.Hollstien在他的博士论文中首次把遗传算法用于函数优化。 2．1975年是遗传算法研究历史上十分重要的一年。这一年Holland出版了他的著名专著《自然系统和人工系统的自适应》（Adaptation in Natural and Artificial Systems），这是第一本系统论述遗传算法的专著，因此有人把1975年作为遗传算法的诞生年。Holland在该书中系统地阐述了遗传算法的基本理论和方法，并提出了对遗传算法的理论研究和发展极其重要的模式理论（schema theory）。该理论首次确认了结构重组遗传操作对于获得隐并行性的重要性。 3．同年，K.A.De Jong完成了他的博士论文《一类遗传自适应系统的行为分析》（An Analysis of the Behavior of a Class of Genetic Adaptive System）。该论文所做的研究工作，可看作是遗传算法发展进程中的一个里程碑，这是因为，他把Holland的模式理论与他的计算实验结合起来。尽管De Jong和Hollstien 一样主要侧重于函数优化的应用研究，但他将选择、交叉和变异操作进一步完善和系统化，同时又提出了诸如代沟（generation gap）等新的遗传操作技术。可以认为，De Jong的研究工作为遗传算法及其应用打下了坚实的基础，他所得出的许多结论，迄今仍具有普遍的指导意义。 4．进入八十年代，遗传算法迎来了兴盛发展时期，无论是理论研究还是应用研究都成了十分热门的课题。1985年，在美国召开了第一届遗传算法国际会议（International Conference on Genetic Algorithms ，ICGA），并且成立国际遗传算法学会（International Society of Genetic Algorithms ，ISGA），以后每两年举行一次。 5．1989年，Holland的学生D.E.Goldberg出版了专著《有哪些信誉好的足球投注网站、优化和机器学习中的遗传算法》（Genetic Algorithms in Search , Optimization, and Machine Learning）。该书总结了