一种改进遗传算法及其在车间作业调度中的应用

摘要

遗传算法（Genetic Algorithm，GA）不依赖于求解问题的具体领域，有较强的适用性和鲁棒性，同时还是一种开放式算法，很容易与其他算法结合，通过彼此取长补短，构造更好性能的算法。因此，遗传算法被广泛应用于诸如车间作业调度这样的NP-hard难题求解。
　　作者在研究遗传算法求解车间作业调度问题中，遇到了种群容易陷入早熟、收敛速度很慢等困难。经过深入分析和反复试验，发现主要是局部迂回搜索和算法对参数初值的敏感性所造成。本文通过同时采用禁忌搜索和自适应动态调整策略，得出了一种改进遗传算法。禁忌搜索通过最大限度地禁止迂回搜索，提高算法的局部搜索能力和爬山能力，避免算法陷入局部最优，在一定程度上直接加快了算法的整体收敛速度；算法参数的自适应动态调整策略，是根据种群个体的进化情况来动态调整算法的交叉概率和变异概率，降低计算结果精度对参数初值的过强依赖，从而解决了算法对参数初值的敏感性问题。通过数值试验，验证了这种改进的遗传算法具有更高的可靠性和更优的性能。
　　作者把这种改进的遗传算法反过来应用到车间作业调度中，给出了该改进遗传算法求解车间作业调度问题的各个环节和整个流程的详细描述。在此基础上，设计并实现了基于该算法的一个车间作业调度软件系统原型，并通过在该原型上所做的试验，进一步验证了本文改进算法的明显效果。

目录

封面

中文摘要

英文摘要

目录

1 绪 论

1.1 课题背景及意义

1.2 国内外研究现状与发展趋势

1.3 论文主要内容及结构

2 遗传算法概要

2.1 遗传算法的基本思想

2.2 遗传算法的基本流程

2.3 遗传算法的应用

2.4 小结

3 一种改进遗传算法（AGATS）

3.1 禁忌搜索的引入

3.2 参数的自适应动态调整

3.3 改进遗传算法AGATS及数值试验

3.4 小结

4 AGATS在车间作业调度中的应用

4.1 车间作业调度（JSS）概要

4.2 应用AGATS求解JSS问题的细节描述

4.3 一个基于AGATS的JSS系统原型

4.4 小结

5 总结与展望

5.1 论文工作总结

5.2 未来研究展望

致谢

参考文献