融合粗糙数据推理的离散麻雀搜索算法求解HFSP问题  

Discrete sparrow search algorithm incorporating rough data-deduction for solving hybrid flow-shop scheduling problems

作　　者：周宁 张嵩霖 张晨 ZHOU Ning;ZHANG Songlin;ZHANG Chen(School of Electronic and Information Engineering,Lanzhou Jiaotong University,Lanzhou 730070,China)

机构地区：[1]兰州交通大学电子与信息工程学院,兰州730070

出　　处：《北京航空航天大学学报》2024年第2期398-408,共11页Journal of Beijing University of Aeronautics and Astronautics

基　　金：国家自然科学基金(61650207,61963023);兰州交通大学天佑创新团队(TY202003)。

摘　　要：针对麻雀搜索算法(SSA)易陷入局部最优、无法求解离散优化问题等不足,提出了一种改进离散麻雀搜索算法(IDSSA)。抽象原始麻雀搜索算法的位置更新公式,针对个体的不同身份设计新的离散化启发式位置更新策略,并针对混合流水车间调度问题(HFSP)设计了编码与解码方式;引入粗糙数据推理理论,通过数学证明解释了引入理论的可行性与合理性,为算法提供理论支撑,提高可解释性;利用上近似的性质扩大搜索空间,提高种群多样性,避免算法早熟,结合划分及粗糙数据推理提出3种策略,促进种群间信息共享,调节种群的开发能力与探索能力,降低算法陷入局部最优的概率;使用改进离散麻雀搜索算法求解混合流水车间调度问题,对3个小规模实例与10个Liao经典测试集进行仿真实验,验证了改进离散麻雀搜索算法求解混合流水车间调度问题的可行性,通过与遗传算法、差分进化算法等经典算法的对比实验,证明了所提算法的优越性与改进策略的有效性。To address the shortcomings of the sparrow search algorithm(SSA),such as easy fall into local optimum and inability to solve discrete optimization problems,an improved discrete sparrow search algorithm(IDSSA)is proposed.Firstly,the position update formula of the original sparrow search algorithm is abstracted,with a new discrete heuristic position update strategy designed according to the different identities of individuals,and with the encoding and decoding methods designed for the hybrid flow-shop scheduling problem(HFSP).Secondly,the rough data-deduction theory is introduced,and the feasibility and rationality of the above theory are explained by mathematical proofs,providing theoretical support for the algorithm and improving the interpretability.Then,the nature of upper approximation is adopted to expand the search space,improve the population diversity,and avoid prematurity of the algorithm.Division and rough data-deduction are combined to propose three strategies to promote information sharing among populations,regulate the exploitation ability and exploration ability of populations,and reduce the probability of the algorithm falling into local optimum.Finally,the improved discrete sparrow search algorithm is used to solve the hybrid flow shop scheduling problem.Simulation experiments are carried out on three small-scale practical examples and ten Liao’s classic test sets to verify the feasibility of the improved algorithm.Results show the superiority of the proposed algorithm and the effectiveness of the improved strategy through comparison with classical algorithms such as genetic algorithm and differential evolutionary algorithm.

关 键 词：麻雀搜索算法 离散化算法 粗糙集理论 全局优化 近似算法 数据关联 混合流水车间调度 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构] TB181[自动化与计算机技术—计算机科学与技术]