| 【中文题名】 | 用基于共生遗传算法的学习框架求解柔性作业调度问题 |
| 【英文题名】 | Using a Learning Architecture Based on Symbiotic Genetic Algorithm to Solving Flexible Job-Shop Scheduling Problems |
| 【学科专业】 | 计算机软件与理论 |
| 【论文级别】 | 硕士论文 |
| 【投稿时间】 | 2007-7-19 |
| 【中关键词】 | 作业调度,遗传算法,共生机制,柔性,学习, |
| 【英关键词】 | job-shop scheduling problem,genetic algorithms,symbiotic mechanism,flexibility,learning, |
| 【分类导航】 | 工业技术>自动化技术、计算机技术>自动化基础理论>人工智能理论>> |
| 【论文摘要】 |
车间作业调度问题(JSP)是许多实际问题的简化模型。寻找求解JSP问题的有效途径是调度和优化领域的重要课题。但是车间作业调度问题是NP难解问题，寻找具有多项式复杂度的算法几乎是不可能的。遗传算法是一种全局随机搜索算法，已经广泛的用于求解JSP问题。它把JSP问题的可行解通过编码从问题的解空间转化到遗传算法能够处理的搜索空间。GA的遗传算子操作能够通过交叉或变异父个体生成新个体的方式来从解空间中搜寻最优解。
GA通过交换父个体中的基因片段或改变某些基因来进化进而完成搜索。如果在进化过程中，我们能够尽可能的保留父个体中具有较高适应度的优秀基因片段，并将其遗传到下一代中，那么GA可以在最有希望的解空间中搜索，进而可以提高搜索效率。
本文中，我们通过用遗传算法对一个JSP实例多次求解，得到大量最优染色体编码串。经过认真分析，总结出代表问题特性的一些概念属性，并给出一个新的概念分级方法。基于这些属性及分类方法，应用数据挖掘算法从这些最优染色体编码串中学习知识，得到多组调度规则，仿真表明，这些调度规则可以有效的调度作业。调度规则也代表了这些最优染色体共有的特征。如果进化过程中在这些特征刚刚出现的... |
| 【论文题纲】 |
|
摘要 |
8-10 |
|
ABSTRACT |
10-12 |
|
第一章 绪论 |
12-18 |
|
1.1 作业调度问题简介 |
12 |
|
1.2 作业调度问题的描述 |
12-13 |
|
1.3 作业调度问题的分类 |
13-14 |
|
1.4 作业调度问题的特点 |
14-15 |
|
1.5 含柔性的作业调度问题 |
15 |
|
1.6 作业调度问题的优化 |
15-17 |
|
1.6.1 调度优化方法 |
15-16 |
|
1.6.2 调度类型 |
16-17 |
|
1.7 论文的组织和所做的工作 |
17-18 |
|
第二章 遗传算法理论 |
18-24 |
|
2.1 遗传算法的基本描述 |
18 |
|
2.2 遗传算法的基本流程 |
18-21 |
|
2.2.1 遗传算法的流程 |
18-19 |
|
2.2.2 遗传算法的操作 |
19-21 |
|
2.3 遗传算法的特点 |
21 |
|
2.4 遗传算法的改进 |
21-22 |
|
2.5 共生遗传算法 |
22-23 |
|
2.6 自学习在解决车间调度中的重要性 |
23-24 |
|
第三章 发掘job-shop调度中的排序规则 |
24-34 |
|
3.1 遗传算法的设计 |
24-26 |
|
3.1.1 遗传算法设计 |
24-26 |
|
3.1.2 收集数据 |
26 |
|
3.2 提取知识规则 |
26-32 |
|
3.2.1 属性导向归纳法 |
26-27 |
|
3.2.2 数据的准备 |
27-28 |
|
3.2.3 抽象位置 |
28-30 |
|
3.2.4 规则集的获取 |
30-32 |
|
3.3 其他用例的测试 |
32-33 |
|
3.4 本章小节 |
33-34 |
|
第四章 使用一种学习框架求解柔性车间调度 |
34-56 |
|
4.1 柔性车间调度问题定义 |
34-35 |
|
4.2 学习框架 |
35-36 |
|
4.3 演化算法模块 |
36-45 |
|
4.3.1 染色体编码方式 |
37-39 |
|
4.3.2 活动解码算法 |
39-40 |
|
4.3.3 共生遗传算法 |
40-42 |
|
4.3.4 选择操作 |
42-43 |
|
4.3.5 交叉算子 |
43-44 |
|
4.3.6 变异算子 |
44-45 |
|
4.4 基于CDR的种群生成算法 |
45-47 |
|
4.4.1 CDR_PopGen算法 |
45-47 |
|
4.4.2 集成CDR_PopGen,GA模块和SL模块 |
47 |
|
4.5 SL学习模块 |
47-51 |
|
4.5.1 染色体空间 |
48-49 |
|
4.5.2 操作空间 |
49-50 |
|
4.5.3 操作空间对变异算子的影响 |
50-51 |
|
4.6 实验仿真及分析 |
51-55 |
|
4.7 本章小节 |
55-56 |
|
第五章 总结 |
56-57 |
|
参考文献 |
57-61 |
|
致谢 |
61-62 |
|
攻读学位期间发表的学术论文和参加的工作 |
62-63 |
|
| 【DOI】 | LunWen.ID:2.2008.388656 |
