基于改进遗传算法的混合车间调度问题研究1(18)

基于改进遗传算法的混合车间调度问题研究

硕Ｉ：学位论文

第２章遗传算法技术研究

２．１引言

当前科学技术正进入多学科互相交叉、互相渗透、互相影响的时代，生命科学与工程科学的交叉、渗透和相互促进是其中一个典型例子，也是近代科学技术发展的一个显著特点。遗传算法的蓬勃发展正体现了科学发展的这一特点和趋势。

制造智能化机器一直是人类的梦想，人们为此付出了巨大的努力。人工智能技术的出现，就是人们得到的成果。但是，近年来，随着人工智能应用领域的不断拓广，传统的基于符号处理机制的人工智能方法在知识表示、处理模式及解决组合爆炸等方面所碰到的问题已变得越来越突出，这些困难甚至使某些学者对人工智能提出了强烈批判，对人工智能的可能性提出了质疑。

众所周知，在人工智能领域中，有不少问题需要在复杂而庞大的搜索空间中寻找最优解或准优解。像货朗担问题和规划问题等组合优化问题就是典型的例子。在求解此类问题时，若不能利用问题的固有知识来缩小搜索空间，则会产生搜索的组合爆炸。因此，研究能在搜索过程中自动获取和积累有关搜索空间的知识，并能自适应地控制搜索过程，从而得到最优解或准优解的通用搜索算法一直是科学研究的热点。遗传算法就是在这种背景下产生并且经实践证明它是一种特别有效的算法。

２．２遗传算法的历史回顾

遗传算法（ＧｅｎｅｔｉｃＡ１９０ｉｒｔｈｍ）是一类借鉴生物界自然选择和自然遗传机制的随机搜索算法，１９７５年，它由美国Ｈｏｌａｎｄ教授首先在《自然结合人工智能系统的适应性》一书中提出阳引，其主要特点是群体搜索策略和种群中个体之间的信息交换，搜索不依赖于梯度信息。它尤其适应于处理传统搜索方法难以解决的复杂和非线性问题。由于它具有这些特点，自２０世纪８０年代以来关于它的理论和应用研究都成了十分热门的课题，尤其是应用研究格外活跃，应用遗传算法解决车间调度问题是重要研究领域之一。

从上世纪六十年代开始，密切根大学教授Ｈｏｌｌａｎｄ开始研究自然和人工系统的自适应行为。在这些研究中，他试图发展一种用于创造通用程序和机器的理论，通用程序和机器具有适应任意环境的能力。在六十年代中期至七十年代末期，基于语言智能和逻辑一数学智能的传统人工智能十分盛行，而基于自然进化的思想则遭到怀疑和反对，Ｈｏｌｌａｎｄ及数位博士生任坚持了这一方面的研究。