遗传算法的研究进展
在遗传算法被用作人工智能系统中的搜索方法之前,许多生物学家用计算机模拟自然遗传系统。特别是在弗雷泽的仿真研究中,他在1962中提出了与现在的遗传算法非常相似的概念和思想。然而,弗雷泽和其他学者并没有意识到自然遗传算法可以转化为人工遗传算法。霍兰德教授和他的学生很快意识到这种转变的重要性。霍兰德认为,发展一种能够模拟自然选择遗传机制的一般理论和方法,比找到一种或另一种解决问题的具体方法更有意义。在此期间,Holland不仅发现了基于适应度的人工遗传选择的基本功能,而且对种群操作进行了认真的研究。1965年,他首次提出了人工遗传操作的重要性,并将其应用于自然系统和人工系统。
1967年,Bagley在论文中首次提出了遗传算法这一术语,并讨论了遗传算法在自动博弈中的应用。他提出的操作,包括选择、交叉和变异,非常接近当前遗传算法中的相应操作。特别是他对选择运算做了非常有意义的研究。他意识到,选择概率应该在遗传进化的早期和晚期适当变化。为此,他引入了适应度缩放的概念,这是遗传算法中常用的技术。同时,他还首次提出了遗传算法自调整的概念,即将交叉和变异的概率融入到染色体本身的编码中,使算法能够进行自调整和优化。虽然巴格莱没有进行计算机模拟实验,但这些思想对后来遗传算法的发展起到了非常明显的作用。
在同一时期,罗森博格还研究了遗传算法,他的研究仍然是基于模拟生物进化,但他在遗传操作方面提出了许多独特的思想。Cavicchio在1970中应用遗传算法进行模式识别。事实上,他并没有直接参与模式识别,只是用遗传算法设计了一套用于识别的检测器。Cavicchio在遗传操作和遗传算法的自调整方面也做了很多有特色的研究。
温伯格在1971发表了题为《活细胞的计算机模拟》的论文。因为他像罗森博格一样关注生物遗传的模拟,所以他对遗传算法的贡献有时会被忽略。其实他的多层次或者说多层次遗传算法还是让人印象深刻的。
第一个用遗传算法进行函数优化的人是Hollstien。1971他在论文《计算机控制系统中的人工遗传自适应方法》中阐述了遗传算法在数字反馈控制中的应用方法。其实他主要讨论的是二元函数的优化。其中,对显性基因的控制、交叉和变异以及各种编码技术进行了深入研究。
1975是遗传算法研究史上非常重要的一年。这一年,霍兰德出版了他的著名专著《自然系统与人工系统之间的适应》。本书系统阐述了遗传算法的基本理论和方法,提出了对遗传算法的理论研究和发展极其重要的图式理论。这一理论首次证实了结构重组遗传操作对于获得隐含并行性的重要性。直到那时,我才知道基因操作在做什么,为什么做得这么好,这对以后陆续开发的基因操作有着不可估量的指导作用。
同年,德容完成了他的重要论文《遗传适应系统的行为分析》。他在这篇论文中的研究工作可以被视为遗传算法发展的里程碑,因为他将Holland的模式理论与他的计算实验相结合。德容虽然和霍尔斯廷一样,主要侧重于函数优化的应用研究,但他对选择、交叉和变异操作进行了进一步的改进和系统化,同时提出了代沟等新的遗传操作技术。可以认为,德容的研究工作为遗传算法及其应用奠定了坚实的基础,他的许多结论至今仍具有普遍的指导意义。
20世纪80年代,遗传算法迎来了一个繁荣发展的时期,无论是理论研究还是应用研究都成为一个非常热门的话题。特别是遗传算法的应用研究尤为活跃,不仅应用领域扩大,优化和学习规则的能力也显著提高,对工业应用的研究也在探索中。此外,一些新的理论和方法在应用研究中得到了迅速发展,这无疑为遗传算法增添了新的活力。
随着应用领域的扩大,遗传算法的研究出现了几个引人注目的新趋势。一个是基于遗传机器学习,这是一个新的研究课题,它将遗传算法从离散搜索空间中的优化搜索算法扩展到具有独特规则生成功能的全新机器学习算法。这种新的学习机制为解决人工智能中知识获取和知识优化提炼的瓶颈问题带来了希望。其次,遗传算法正日益与神经网络、模糊推理、混沌理论等其他智能计算方法进行渗透和结合,这将对21世纪开辟新的智能计算技术具有重要意义。第三,并行处理遗传算法的研究非常活跃。这一研究不仅对于遗传算法本身的发展,而且对于新一代智能计算机体系结构的研究都是非常重要的。第四,遗传算法和另一个被称为人工生命的全新研究领域正在不断渗透。所谓人工生命,就是用计算机模拟自然界中丰富多彩的生命现象,其中生物的自适应、进化和免疫是人工生命的重要研究对象,遗传算法将在这方面发挥一定的作用。第五,遗传算法越来越多地与进化规划、进化策略等进化计算理论相结合。EP和ES几乎与遗传算法同时独立发展。它们和遗传算法一样,也是模拟自然生物进化机制的智能计算方法。它们与遗传算法有相似之处和特点。
随着遗传算法研究和应用的不断深入和发展,一系列以遗传算法为主题的国际会议非常活跃。自1985以来,ICGA(国际遗传算法会议)每两年举行一次。在欧洲,自1990以来,类似的会议,即PPSN(来自自然的并行问题解决),每隔一年举行一次。除了遗传算法,大多数关于ES和EP的学术论文也出现在PPSN。另外,围绕遗传算法理论基础的学术会议是FOGA(遗传算法基础)。也是1990起隔年举办。这些国际学术会议的论文反映了近年来遗传算法的最新发展和趋势。