生物地理学优化算法及其在动态车间调度中的应用研究

摘要

作为当代制造业生产系统中的核心内容和关键技术，车间调度对制造系统性能有着极其重要的作用。合理且高效的调度策略能够极大的提高制造企业的生产效率，进而增强制造企业的市场竞争力。多数的生产调度问题较为复杂，是典型的NP-hard问题。而随着问题规模的不断增大，传统的方法已经无法满足实际生产中的需求。因此，对于车间调度问题理论的研究以及对有效的调度方案的设计仍然是本领域的研究热点。 生物地理学优化算法（Biogeography-based Optimization,BBO）是一种受生物地理学理论启发而得的新型群体智能优化算法。BBO算法因其独特的运行机制、相对较少的参数以及较强的局部搜索能力等优点受到了广泛的关注。本文针对BBO算法进行了深入的研究，并通过理论和实验分析了BBO算法的优缺点，针对不同的车间调度问题对BBO算法进行改进，平衡了算法的全局搜索能力和局部搜索能力。本文的主要研究内容如下： （1）针对标准BBO算法在函数优化问题中探索能力较弱且过度依赖坐标系的问题，本文提出了一种基于两阶段迁移模型的差分生物地理学优化算法（Two-stage Differential Biogeography-based Optimization,TDBBO）。在TDBBO算法中，首先通过两阶段迁移模型维持进化早期的种群多样性并在进化后期加快种群收敛速度。其次，针对算法过度依赖坐标系的问题，设计了改进的迁移算子并将其用于增强算法的旋转不变性。并引入了高斯变异算子使得种群能有效地跳出局部最优解。最后通过引入贪婪选择策略加速收敛。此外，本文还应用Markov模型对TDBBO算法的全局收敛性进行了分析。在CEC2017标准测试函数上的实验结果表明，相比于一些先进的BBO算法的变体，TDBBO算法具有更快的收敛速度以及更高的精度。 （2）针对零等待流水车间调度问题（No-wait Flow Shop Problem,NWFSP）,设计了一种混合生物地理学优化算法（Hybrid Biogeography-based Optimization with Variable Neighborhood Search Mechanism，HBV）进行求解。在HBV算法中，首先使用MNEH和NN机制产生较优的初始种群。其次，将路径重定向技术和基于块的自我提升策略嵌入到迁移算子来加快HBV算法的收敛速度。并且设计了基于迭代贪心算法（IG）的变异算子探索潜在的搜索区域，最后应用基于块邻域结构和插入邻域结构的变邻域搜索策略对每一代最佳的候选解进行局部搜索。此外，运用Markov模型对HBV算法的全局收敛性能进行分析。仿真结果和统计分析表明HBV算法在求解NWFSP问题是具有较高的效率和较好的精度。 （3）针对经典的作业车间调度问题（Job Shop Scheduling Problem,JSSP）设计了基于反向学习和模拟退火的生物地理学优化算法（Oppositional Metroplis Biogeography-based Optimization，OMBBO）。首先使用最小值编码规则（Smallest Position Value，SPV）将JSSP问题域转换为连续问题域，并运用活动调度解码规则计算makespan以缩减搜索空间。其次，使用混沌理论和反向学习策略初始化种群。并引入了改进的迁移算子和高斯变异算子增强标准BBO算法的全局搜索能力。此外，设计了基于模拟退火的接收准则控制种群的多样性。最后使用基于关键路径的变邻域搜索在全局最优解的附近进行搜索。仿真结果表明OMBBO算法显著优于经典的JSSP算法。

目录

声明

插图索引

附表索引

算法索引

符号注释表

缩略词注释表

第1章 绪 论

1.1引言

1.2车间调度问题概述

1.2.1车间调度问题的简要描述

1.2.2车间调度问题的分类

1.2.3车间调度问题的求解方法

1.3进化算法概述

1.4本文的研究内容和章节安排

第2章 生物地理学优化算法

2.1引言

2.2生物地理学

2.3生物地理学优化算法概述

2.4迁移算子

2.5变异算子

2.6生物地理学优化算法的研究现状

2.7本章小结

第3章 基于两阶段模型的差分生物地理学优化算法

3.1引言

3.2 TDBBO算法

3.2.1改进的迁移算子

3.2.2两阶段迁移模型

3.2.3 Gaussian变异算子

3.2.4 TDBBO算法流程

3.2.5 TDBBO算法收敛性分析

3.3数值实验及结果分析

3.3.1参数设置

3.3.2实验结果与分析

3.4本章小结

第4章 基于混合生物地理学优化算法的零等待流水车间调度

4.1引言

4.2零等待流水车间调度问题

4.2.1问题描述

4.2.2数学描述

4.2.3 NWFSP研究现状

4.3基于HBV的NWFSP调度算法

4.3.1种群初始化方法

4.3.2迁移算子

4.3.3变异算子

4.3.4变邻域搜索

4.3.5精英保留策略

4.3.6 HBV算法框架

4.3.7 HBV算法收敛性分析

4.4仿真实验及结果分析

4.4.1参数分析

4.4.2算法不同部分的性能测试

4.4.3在Taillard测试集上的仿真实验结果与比较

4.4.4在VRF测试集上的仿真实验结果与比较

4.4.5实验分析与讨论

4.5本章小结

第5章 基于改进生物地理学优化算法的作业车间调度

5.1引言

5.2作业车间调度问题

5.2.1问题描述

5.2.2数学描述

5.2.3 JSSP研究现状

5.3基于OMBBO的JSSP调度算法

5.3.1编解码规则

5.3.2种群初始化方法

5.3.3迁移算子

5.3.4变异算子

5.3.5模拟退火接收准则

5.3.6变邻域搜索

5.3.7 OMBBO算法框架

5.4仿真实验及结果分析

5.5本章小结

总结与展望

参 考 文 献

致谢

附录A 攻读学位期间的研究成果及发表的学术论文

附录B 攻读学位期间参与的科研项目