| 题名 | 引力搜索算法及其在车间调度问题中的应用研究 |
| 作者 | 薛飞龙 |
| 答辩日期 | 2019 |
| 导师 | 赵付青 |
| 关键词 | 引力搜索算法 阻塞流水车间调度问题 自适应机制 变邻域操作 |
| 学位名称 | 硕士 |
| 英文摘要 | 车间调度问题广泛存在于现代制造业系统中,是提高企业生产效率的关键支撑技术。阻塞流水车间调度问题(Blocking Flow Shop Problem,BFSP)在制造业系统中是一类非常重要的模型,也是一种典型的NP-Hard问题。随着问题规模的扩大,BFSP的求解难度呈现指数式增长并且传统的数学方法已经不能有效地求解该问题,甚至无法求出最优解。因此,无论是在生产系统的应用方面,还是在调度问题的理论研究方面,如何设计有效的调度策略仍然是本领域的研究热点和难点。引力搜索算法(Gravitational Search Algorithm,GSA)是一种受牛顿万有引力定律启发而发展出的新型智能优化算法。引力搜索算法具有易实现、原理简单等优点,已广泛应用于现实生产中的多个领域。本文在深入研究了GSA的运行机制,分析了算法存在的优缺点之后,对算法的框架和特有的更新机制进行了改进,提高了算法的搜索性能,并将其应用于解决单目标实值优化问题中。然后在深入研究了阻塞流水车间调度问题的基础上,结合GSA的特性,将算法进行改进,并成功应用到调度问题中去。本文的主要研究内容和成果如下:(1)通过对GSA算法分析之后发现,它存在着对参数敏感性高、进化后期易停滞等缺点。针对上述问题,本文提出了一种与差分进化算法结合的混合GSA算法(A Hybrid Algorithm Based on Self-Adaptive Gravitational Search Algorithm and Differential Evolution,SGSADE)用以解决单目标实值优化问题。在SGSADE中,为了克服算法对参数敏感性高的缺点,使用了一种参数自适应的机制用以调整关键参数和。通过这种机制能有效地提升算法的收敛速度并且在平衡局部搜索能力和全局搜索能力方面表现出良好的性能。在算法的位置更新操作中,使用了基于差分进化算法(Differential Evolution,DE)的交叉和变异机制。新更新方式的引入使得算法在进化后期能够保持一定的种群多样性。为了进一步增强算法局部搜索能力,使用了一种基于莱维飞行的扰动操作。在标准测试集上的仿真结果和两个严格的假设检验结果表明SGSADE优于其对比算法。(2)针对阻塞流水车间调度问题,本文提出了一种离散的的GSA优化算法(A Discrete Gravitational Search Algorithm for the blocking flow shop problem with total flow time mini mization,DGSA)用来最小化总流经时间。在DGSA中,为了得到优良的初始化种群,使用了一种新的启发式方法,即VPF(Variable Profile Fitting)与NEH结合的方法VPF_NEH(n)。此方法能够有效地平衡初始化种群的质量和多样性。在种群粒子的加速度、速度以及位置的更新阶段,原始的连续更新方式不再适用于调度问题。在此阶段,使用了三个关键操作算子:变邻域操作(Variable Neighborhood Operators,VNO)、路径重连以及应用在位置更新阶段的加法操作。新加入的算子能够防止种群过早收敛并且在算法进化过程中能够有效的平衡局部搜索能力与全局搜索能力。基于标准测试集的仿真结果表明了DGSA在求解BFSP时的有效性和优越性。(3)针对GSA算法的理论分析匮乏的问题,本文对SGSADE的收敛性和DGSA的时间复杂度进行了分析。对于SGSADE,使用了有限齐次马尔科夫链模型,证明了算法能够以概率1收敛到全局最优。对于DGSA,使用了Method of Fitness-Based Partitions理论,并且给出了算法的运行时间期望的上界。 |
| 语种 | 中文 |
| 页码 | 84 |
| URL标识 | 查看原文 |
| 内容类型 | 学位论文 |
| 源URL | [http://ir.lut.edu.cn/handle/2XXMBERH/95505]  |
| 专题 | 兰州理工大学 |
| 作者单位 | 兰州理工大学 |
| 推荐引用方式 GB/T 7714 | 薛飞龙. 引力搜索算法及其在车间调度问题中的应用研究[D]. 2019. |
| 个性服务 |
| 查看访问统计 |
| 相关权益政策 |
| 暂无数据 |
| 收藏/分享 |
除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。
修改评论