用基于共生遗传算法的学习框架求解柔性作业调度问题

摘要

车间作业调度问题(JSP)是许多实际问题的简化模型。寻找求解JSP问题的有效途径是调度和优化领域的重要课题。但是车间作业调度问题是NP难解问题，寻找具有多项式复杂度的算法几乎是不可能的。遗传算法是一种全局随机搜索算法，已经广泛的用于求解JSP问题。它把JSP问题的可行解通过编码从问题的解空间转化到遗传算法能够处理的搜索空间。GA的遗传算子操作能够通过交叉或变异父个体生成新个体的方式来从解空间中搜寻最优解。 GA通过交换父个体中的基因片段或改变某些基因来进化进而完成搜索。如果在进化过程中，我们能够尽可能的保留父个体中具有较高适应度的优秀基因片段，并将其遗传到下一代中，那么GA可以在最有希望的解空间中搜索，进而可以提高搜索效率。 本文中，我们通过用遗传算法对一个JSP实例多次求解，得到大量最优染色体编码串。经过认真分析，总结出代表问题特性的一些概念属性，并给出一个新的概念分级方法。基于这些属性及分类方法，应用数据挖掘算法从这些最优染色体编码串中学习知识，得到多组调度规则，仿真表明，这些调度规则可以有效的调度作业。调度规则也代表了这些最优染色体共有的特征。如果进化过程中在这些特征刚刚出现的时候，我们能够识别出来并将其遗传到后代个体中，显然可以改善后代种群的质量，进而可以提高搜索效率。 在最后部分，借鉴上述思想求解具有操作柔性的车间调度问题。根据问题的特点，我们使用共生机制改进了遗传算法并将其集成到一个学习框架中。提出了相应的编码解码方法和一组自适应概率函数并改进了学习框架，使其在进化过程中可以学习染色体的优秀特征。我们把调度问题分为两个子问题，分别生成两个不同类的种群，相互影响，共同进化，将两个种群中的最优染色体结合起来解码则可以得到最优调度。进化过程中，学习模块可以不断从当前种群的适应度最高的一些染色体中学习其优秀特征，并指导后代个体的进化。最后我们给出了仿真实验，结果表明这种方法在解的质量上有山东大学硕士学位论文一定程度的提高。

目录

文摘

英文文摘

原创性声明及关于学位论文使用授权的说明

第一章绪论

1.1作业调度问题简介

1.2作业调度问题的描述

1.3作业调度问题的分类

1.4作业调度问题的特点

1.5含柔性的作业调度问题

1.6作业调度问题的优化

1.6.1调度优化方法

1.6.2调度类型

1.7论文的组织和所做的工作

第二章遗传算法理论

2.1遗传算法的基本描述

2.2遗传算法的基本流程

2.2.1遗传算法的流程

2.2.2遗传算法的操作

2.3遗传算法的特点

2.4遗传算法的改进

2.5共生遗传算法

2.6自学习在解决车间调度中的重要性

第三章发掘job-shop调度中的排序规则

3.1遗传算法的设计

3.1.1遗传算法设计

3.1.2收集数据

3.2提取知识规则

3.2.1属性导向归纳法

3.2.2数据的准备

3.2.3抽象位置

3.2.4规则集的获取

3.3其他用例的测试

3.4本章小节

第四章使用一种学习框架求解柔性车间调度

4.1柔性车间调度问题定义

4.2学习框架

4.3演化算法模块

4.3.1染色体编码方式

4.3.2活动解码算法

4.3.3共生遗传算法

4.3.4选择操作

4.3.5交叉算子

4.3.6变异算子

4.4基于CDR的种群生成算法

4.4.1 CDR_PopGen算法

4.4.2集成CDR_PopGen，GA模块和SL模块

4.5 SL学习模块

4.5.1染色体空间

4.5.2操作空间

4.5.3操作空间对变异算子的影响

4.6实验仿真及分析

4.7本章小节

第五章总结

参考文献

致谢

攻读学位期间发表的学术论文和参加的工作