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

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

基于改进遗传算法的混合下问生产调度问题研究

Ｂａｇｌｅｙ发明“遗传算法＂一词并发表了第一篇有关遗传算法应用的论文，在他开创性的博士论文中采用双倍体编码，发展了与目前类似的复制、交叉、变异、显性、倒位等基因操作，他还敏锐地察觉到防止早熟收敛的机理，并发展了自组织遗传算法的概念。与此同时，Ｒｏｓｅｎｂｅｒｇ在他的博士论文中进行了单细胞生物群体的计算机仿真研究，对以后函数优化的研究颇有启发，并发展了自适应交换策略。

七十年代，Ｈｏｌｌａｎｄ提出了重要的模式理论，建议采用二进制编码，与前面几位博士不同，Ｈｏｌｌａｎｄ首次采用二进制编码来研究函数优化问题，并指出了运用Ｇｒａｙ码的一些优点，他研究了从生物系统引申出的各种不同的选择和配对策略。Ｃａｖｉｃｃｈｉｏ在１９７０年研究了基于遗传算法的子程序选择和模式识别问题，在模式识别问题上，采用整数编码，检索空向很大，他提出了以预选择策略保证群体多样性，对遗传算法参数进行中心控制的方法。同年，Ｗｅｉｎｂｅｒｇ研究了生物体的计算机仿真，他的贡献在于提出运用多层遗传算法来进行遗传算法的参数自优化。１９７２年，Ｆｒａｎｔｚ的博士论文中研究了许多新的问题，如基因非线性（异位显性）现象，基因迁移操作及多点交叉操作等。由于没有设计出诸如

ＧＡ．ｄｅｃｅｐｔｉｏｎ之类合适的非线性优化问题，实验结果并不具备说服力。这一年，Ｈｏｌｌａｎｄ的模式理论也日渐成熟，但在编码策略上出现了至今仍执争论的两派，一派根据模式定理建议尽量少的符号编码，一派以数值优化计算的方便和精度为准采用一个基因一个参数的方法，并把相应的基因操作改造成适合实数操作的形式Ｂｏｓｗｏｒｔｈ．Ｚｏｏ和Ｚｅｉｇｌｅｒ是后者的开创者，１９７５年建立了遗传算法的发展历史上的两块里程碑，一是Ｈｏｌｌａｎｄ出版了经典著作《ＡｄａｐｔａｔｉｏｎｉｎＮａｔｕｒｅａｎｄＡｒｔｍｃｉａｌＳｙｓｔｅｍ》，该书是作者十几年间许多思想及其实现的结晶，详细阐述了遗传算法的理论，并为其奠定了数学基础，发展了一整套模拟生物自适应系统的理论：二是ＤｅＪｏｎｇ完成了具有指导意义的博士论文《Ａｎ

ＢｅｈａｖｉｏｒｏｆａＣｌａｓｓｏｆＧｅｎｅｔｉｃＡｄａｐｔｉｏｎＡｎａｌｙｓｉｓｏｆｔｈｅＳｙｓｔｅｍ》，他深入领会了模式定理并做了大量严格的计算实验，给出了明确的结论，对遗传算法的六种方案的性能及机理进行了详细实验和分析，他的工作成为后继者的范例并为以后的广泛应用奠定了坚实的基础。为克服ＤｅＪｏｎｇ的轮盘赌选择操作中的随机误差，Ｂｒｉｎｄｌｅ于１９８１年在她的博士论文中研究了六种复制策略。

进入八十年代，随着以符号系统模仿人类智能的传统人工智能暂时陷入困境，神经网络、机器学习和遗传算法等从生物系统底层模拟智能的研究重新复活并获得繁荣。Ｇｏｌｄｂｅｒｇ在遗传算法研究中起着继往开来的作用，他在博士论文中第一次把遗传算法用于实际的工程系统一煤气管道的优化。从此遗传算法的理论研究更为深入和丰富，应用研究更加广泛和完善。自１９８５年起，遗传算法及其应用国际会议每两年召开一次，有关人工智能的会议和刊物上大多有遗传算法的专题。Ｇｏｌｄｂｅｒｇ的理论以及其他学者专著的出版有力地推动了遗传算法的传播。

九十年代开始，以不确定性，非线性，时间不可逆为内涵，以复杂问题为