遗传算法与人工免疫算法对车间调度问题的求解

摘要

随着市场经济的发展，市场竞争日趋激烈，对于加工制造业，就要求能够合理安排工序，合理利用资源，减少工期，降低生产成本。因此，车间调度问题越来越受到人们的关注。车间调度问题属于Non-Polynomial-hard（NP.hard）问题，是典型优化问题中最难求解的问题。遗传算法（Genetic Algorithm，GA）以其通用性强，算法简单等特点，被广泛应用到车间调度问题的优化中。但是，正是由于其通用性强，而导致其灵活性差，尽管能够保证全局收敛性，但是它在实际应用中容易产生早熟收敛的问题，即在进化群体中少数个体的适应函数值远大于其他个体，这样经过少数几次迭代后，这些个体就占据了整个群体，进化过程就提前收敛了。人工免疫算法是自然免疫系统的机理应用于优化计算的成果之一，采用了基于浓度和适应度的一种适应式的选择机制，能够有效的促进优秀抗体的繁殖，抑制浓度过高的抗体，保证抗体多样性，提高个体的适应度和防止种群退化，避免了局部收敛，但频繁的提取育苗和注射育苗，增加了算法的时间复杂度。 介于以上两种算法优缺点分析，引入选择机制。本文所作的工作有： 首先，对遗传算法的研究，遗传算法中交叉算法具有举足轻重的作用，好的交叉算子能提高种群的进化速度，所以本文设计了新的三个体交叉算法。 其次，设计了人工免疫算法中疫苗的提取和接种方法，即基于加工机器的基因片断抽取疫苗方法和最后完工机器个体的接种方法。 再次，对种群提前收敛性能的研究，引入选择机制，当种群多样性高时用遗传算法高速进化，低时用人工免疫算法。 最后，通过对标准数据集的测试，从求得的最优值，时间效率和算法收敛程度三方面和以往的算法进行了对比分析。

目录

文摘

英文文摘

声明

第1章绪论

1.1课题研究背景

1.2本课题的意义

1.3生产调度

1.3.1生产调度的概念

1.3.2生产调度分类

1.4车间凋度问题研究

1.4.1车间作业调度问题的描述

1.4.2车间作业调度问题特点及分类

1.4.3车间作业调度模型描述

1.4.4作业调度的方法

1.5本文研究内容

第2章遗传算法

2.1遗传算法的基本理论

2.1.1遗传算法背景

2.1.2遗传算法的思想及特点

2.1.3遗传算法的操作流程

2.2求解Job-Shop调度问题的改进遗传算法设计

2.2.1编码方式

2.2.2基于工序的编码方式

2.2.3染色体的解码及适应度函数的求解

2.2.4选择算子

2.2.5交叉算子

2.2.6变异算子

2.2.7遗传算法参数设定

2.2.8收敛性分析

2.3本章小结

第3章人工免疫算法

3.1人工免疫算法的现状

3.2人工免疫算法的意义

3.3人工免疫算法的基本理论

3.3.1人工免疫算法的描述

3.3.2人工免疫算法特点分析

3.4基于信息熵的人工免疫算法

3.5基于改进的免疫育苗的免疫算法

3.5.1改进思想

3.5.2提取育苗

3.5.3接种育苗

3.5.4免疫选择

3.5.5算法流程

3.6本章小结

第4章对于求解车间调度问题的研究

4.1遗传算法与人工免疫算法的选择机制

4.1.1分析种群过早收敛程度的指标

4.1.2算法设计

4.2遗传算法和人工免疫算法对车间调度问题的求解

4.2.1问题描述

4.2.2抗原识别初始抗体建立

4.2.3人工免疫算法设计

4.2.4遗传算法设计

4.3算法收敛性

4.4本章小结

第5章实验仿真测试

5.1测试总体思想

5.2界面设计

5.3标准数据测试

5.4测试数据结果对比分析

5.5本章小结

结论

参考文献

攻读硕士学位期间发表的学术论文

致谢