遗传算法研究历程回顾

遗传算法起源于对生物系统所进行的计算机模拟研究。

早在20世纪40年代，就有学者开始研究如何利用计算机进行生物模拟的技术。

20世纪60年代初，美国Michigan大学Holland教授最初尝试从生物进化机理中发展出适合于现实世界复杂优化问题的模拟进化算法，由于当时采用的主要遗传算子是变异算子而不是选择算子，所以效果并不好。加利福尼亚大学伯克利分校的Bremermann于1962年首次提出了杂交算子，即后代的特征取决于双亲有关基因的总和。Holland教授的学生Bagley于1967年在其博士论文中首次提出了“遗传算法”这一新名词，并发表了遗传算法应用方面的第一篇论文[104]，文献中采用了双倍体编码，发展了与目前类似的选择、杂交、变异、显性、倒位等基因操作算子，当时也觉察到遗传算法的早熟收敛问题，并发展了自组织遗传算法的概念。Cavicchio于1970年提出了整数编码，并以预选择策略来保证遗传算法进化迭代中的群体多样性。同年，Weinberg研究了运用多层遗传算法进行遗传算法的参数优化。

20世纪70年代初，Holland教授提出了模式定理（Schema theorem），遗传算法根据模式的适应度值、长度和阶次来为模式分配搜索次数，为那些适应度值较高、长度较短、阶次较低的模式分配的搜索次数将按指数率增长，而为那些适应度值较低、长度较长、阶次较高的模式分配的搜索次数按照指数率衰减，这从理论上保证了遗传算法是一个可以按照适应度值大小来搜索最优可行解的优化过程，因而模式定理也为遗传算法奠定了理论基础。Holland于1975年出版了第一本系统论述遗传算法和人工自适应系统的专著《自然系统和人工系统的自适应性》[17]。De Jong于1975年在其博士论文中结合模式定理进行了大量的纯数值函数优化计算实验，建立了遗传算法的工作框架，推荐了在大多数优化问题中都较适用的遗传算法的参数，还建立了著名的De Jong五函数测试平台，定义了评价遗传算法性能的在线指标和离线指标，得到了一些重要且具有指导意义的结论[104]。(www.xing528.com)

20世纪80年代，Holland教授实现了第一个基于遗传算法的机器学习系统—分类器系统，开创了基于遗传算法的机器学习的新概念，为分类器系统构造了一个完整的框架[24，105]。Goldberg于1989年出版了专著《搜索、优化和机器学习中的遗传算法》，该书系统总结了遗传算法的主要研究成果，全面而完整地论述了遗传算法的基本原理及其应用，奠定了现代遗传算法的科学基础[27]。

Davis于1991年出版的《遗传算法手册》包含了遗传算法在科学计算、工程技术和社会经济中的大量应用实例，为推广和普及遗传算法的应用起到了重要的指导作用[106]。Koza于1992年将遗传算法应用于计算机程序的优化设计及程序自动生成方面，提出了遗传编程（Genetic programming，简称GP）的概念[107]，并成功地把遗传编程的方法应用于机器学习、符号处理和人工智能等方面[5]。

进入21世纪，以不确定性、非线性、时间不可逆为内涵的复杂性科学已成为一个研究热点，由于遗传算法能有效地求解属于非线性类型的组合优化问题以及其他复杂非线性优化问题、多目标函数优化问题，从而得到了工程结构、计算数学、制造系统、航空航天、交通、计算机科学、通信、电子学、电力、材料科学等学科的广泛重视和研究。目前已在世界范围内掀起了关于遗传算法的研究与应用热潮，可以预测随着进化论、遗传学、分子生物学、计算机科学的不断发展，遗传算法也将在理论与应用中得到迅速发展和完善。