论文部分内容阅读
在工程管理中,调度问题是至关重要的研究课题之一。作为一种新型的元启发式优化算法,蝙蝠算法(Bat Algorithm,BA)以模拟回声定位系统的形式得到了国内外学者的广泛关注和重点研究,其特点是参数少,具有较强的鲁棒性,应用于求解连续型优化问题和优化管理问题,具有广阔的应用前景。然而,该算法本身也存在一些不可避免的缺陷,如容易陷入局部最优、后期优化准确性低等问题,影响了蝙蝠算法的搜索能力,制约了算法解决应用问题的能力和范围。针对蝙蝠算法理论基础较为薄弱,局部搜索与全局搜索的失衡会致使算法的收敛速度慢等问题,本文以蝙蝠算法为主线,通过改进蝙蝠种群的多样性、提高算法的局部搜索能力以及全局搜索能力,提出了一种混合的蝙蝠算法。该算法设计了一种调度规则用来初始化栖息地,利用种群分组、基于均方误差的反向传播算法和共轭梯度法改进和优化了混合算法的搜索方向、步长、响度和脉冲发射率,并提出基于多邻域搜索的局部搜索策略和基于莱维飞行的全局搜索策略。针对以上三种改进策略,分别与原蝙蝠算法相结合,提出三种不同类型的蝙蝠算法,并应用于调度问题以验证这三种算法的可行性和有效性。主要研究工作如下:(1)为了提高初始蝙蝠种群的多样性,提出了一种基于k-means聚类因子和邻域结构的离散蝙蝠算法(DBA)。该算法从调度模型中生成初始种群,重新划分蝙蝠的捕食范围,提出一种新的基于邻域结构的动态捕食机制和迁移策略,并改进Kmeans相似性算子,根据最高相似性对蝙蝠进行种群分组;引入精英学习策略,提高离散蝙蝠算法的局部搜索能力,防止过早收敛。求解三阶段装配流水线问题的仿真结果表明,在测试产品数量、机器数量和组这三个不同维度问题上,DBA的性能更优于禁忌搜索、变邻域搜索以及两个启发式算法;下限和调度模型的引入可以提高其整体性能;种群分组、动态控制参数、精英策略等这些特征的改进能够有效地提高DBA的局部搜索能力。(2)为了提高蝙蝠算法的局部搜索能力,提出了一种基于变邻域搜索和两种学习策略的改进型蝙蝠优化算法(IMBA)。该算法设计了一种基于均方误差MSE的反向传播算法的搜索型蝙蝠种群和一种基于共轭梯度的捕获型蝙蝠种群,这两种不同搜索能力的种群旨在求解调度优化问题时,蝙蝠算法的收敛性和多样性难以兼顾的问题;同时,充分挖掘种群信息,设计一种新的选择机制用来更新蝙蝠算法的速度和位置,有效地解决了在求解最优问题中,如何在搜索和探索两个方面进行权衡的问题;利用高斯和精英学习的方法,帮助蝙蝠种群跳出局部最优;根据INSERT算子的三个邻域结构,提出具有可变邻域搜索的局部搜索方法VND3BA和VND2BA,使IMBA在搜索过程中避免过早收敛。同时,引入分布式计算与三阶段装配流水线调度问题相结合,求解三阶段的分布式装配置换流水车间调度优化问题,仿真结果表明了IMBA可以最大限度地减少该问题的完工时间。该算法不仅可以得到最低的相对百分比偏差值,也得到了最小的平均RPD值,充分证明了IMBA是一种具有良好性能、更加稳定以及鲁棒性更强的算法。(3)为了提高算法的全局搜索能力,提出了一种基于莱维飞行的混合多目标蝙蝠算法(MOBA)。在蝙蝠种群分类的基础上,更新算法的搜索方向和步长,调整网络的权重和偏差,该方法扩展了搜索范围,并增强了求解可行解的能力;其次,利用基于均方误差的反向传播和共轭梯度方法,对蝙蝠算法的响度和脉冲发射率进行了改进和优化,能有效地解决局部最优、早熟收敛等问题,并能有效地提高算法的收敛精度和收敛速度;最后,引入莱维飞行使之与蝙蝠算法相结合,长短交替的特征可以有效地寻找全局最优解。同时求解云计算的资源调度问题,以最小完工时间、吞吐量、成本和最稳定的不平衡度为目标函数,仿真实验证明了与其他多目标算法相比,MOBA可以更有效地实现对更好的目标区域的搜索,减少云计算中的任务云的完成时间;在保证网络节点负载均衡的前提下,显著的降低了云计算系统的成本和能源消耗,从而实现了资源的均衡合理的使用,从而实现了快速且良好的可持续发展。由此说明了MOBA能很好地平衡算法的局部搜索和全局搜索,可作为全局优化的一种有效算法。(4)融合了前三种改进策略,最终提出了一种混合蝙蝠算法(IHBA)。为了验证混合蝙蝠算法的性能,并将应用于更复杂的具有序列相关设置时间的三阶段分布式混合流水车间调度问题和函数优化问题,其中,三阶段分布式混合流水车间调度问题包括将工作分配给工厂、确定每个工厂的工作顺序和在每个阶段为每个工序选择机器等三个子问题,使第一阶段设置SDST与工序相关,即目标函数为最小化平均流动时间和最大延迟时间。通过比较蝙蝠的种群规模、问题的维度、不同的惯性权重和迭代阈值,选择适合于求解该问题的参数值,采用LOV规则将IHBA中的个体由实数向量转化为工件排序。仿真实验证明了在函数优化问题中,三种改进策略融合的算法IHBA具有比DBA、IMBA和MOBA更好的求解性能、更优的收敛速度和精度。同时,在求解具有SDST的三阶段分布式混合流水车间调度问题中,考虑应付日期的相对范围和延迟因素方面,IHBA比IMBA的表现更好且波动幅度更小,说明了应付日期的范围可以影响算法的性能,且随着其范围的增大,性能会变得相对较差;延迟因素的变化则会改变应付日期的时间间隔;在工序和第一阶段不同数量的并行机器方面,IHBA的平均误差百分比的结果比IMBA小,且工序波动和工作数量的表现比IMBA好。由此可见,本文提出的IHBA算法是可以解决复杂的混合流水车间调度问题的一种全局优化算法。