基于聚类和熵引导的无监督学习方法在多目标进化优化中的应用——以再入式混合流水线调度问题为例

《Swarm and Evolutionary Computation》：Clustering and entropy-guided unsupervised learning for multi-objective evolutionary optimization of reentrant hybrid flow shop scheduling

　　李车祥|韩玉燕|王玉婷|陈庆达|高方正
中国聊城市聊城大学计算机科学学院，252059

**摘要**
具有总能耗约束的重入混合流水线调度问题（RHFSP）对可持续制造提出了重大挑战。为了解决这个问题，本研究提出了一种结合聚类和熵引导的无监督学习（CEUL-MOEA）的多目标进化算法。在CEUL-MOEA中，采用了一种探索-利用协同进化种群框架来平衡全局搜索和局部优化。然后，引入了四个轻量级的内部评估指标来评估收敛性、边界覆盖率和分布均匀性，进一步支持了六种自适应指标驱动的局部搜索策略的设计。此外，还设计了一种基于聚类和熵引导的邻域搜索方法，该方法利用基于密度的聚类和基于熵的加权来动态分配搜索资源。另外，提出了两个关于能量驱动的向后调整（ED-BA）策略的定理及其正式证明。基于这些定理，设计了单循环和多循环ED-BA策略以减少空闲能耗。在275个RHFSP实例上的广泛实验表明，所提出的算法在收敛性、多样性和能源优化方面优于现有方法，平均减少了90%的AGD，84%的AIGD，以及55%的AHV。

**引言**
实现碳峰值和碳中和已成为促进绿色和低碳发展的关键策略。这些举措不仅推动了高质量的经济增长，也为长期可持续性奠定了重要基础[1,2]。在此背景下，生产调度在决定资源利用效率和碳排放方面起着至关重要的作用[3]。调度优化的程度直接影响制造业绿色转型的深度和效果。
在各种调度问题中，重入混合流水线调度问题（RHFSP）已成为一个具有代表性的但极具挑战性的优化问题[4]。RHFSP的特点是多阶段处理、重入作业流和并行资源，广泛应用于钢铁生产[5]、半导体制造[6]和航空航天[7]等高科技制造领域。图1直观地展示了半导体晶圆制造过程。在这个过程中，作业通常会经历多个重入处理周期，经过氧化扩散、薄膜沉积、光刻、蚀刻、离子注入和封装测试等阶段[8]。每个阶段都由并行机器支持。这种固有的复杂性不仅显著增加了优化难度，还进一步突显了RHFSP在实现低碳和高效率生产中的战略重要性。
近年来，机器学习（ML）在模拟包括经济学[9]、金融[10]、商业[11]、管理[12]和医学[13]在内的多个领域的复杂非线性模式方面表现出色，为复杂问题的智能优化提供了新的范式。与依赖大量标记数据的监督学习相比，无监督学习更适合于标记样本不可用且解决方案空间结构未知的调度优化场景。与基于代理的方法（如神经网络或高斯过程）不同，后者需要大规模训练数据并主要关注预测准确性，本工作中的无监督学习强调在搜索空间中发现解决方案结构的任务。因此，将无监督学习整合到复杂的离散调度优化中提供了一种有效的方法，以利用高维解决方案空间中的潜在结构信息。
同时，已有大量研究致力于使用智能优化算法解决多目标RHFSP问题，并取得了显著进展。然而，大多数现有研究仍然主要关注传统的基于时间的目标，如完工时间和总延迟（TT）[14]，而对总能耗（TEC）这一关键维度关注较少。目前缺乏系统化的框架来建模和优化能耗与生产效率之间的内在权衡。为了填补这一空白，本研究探讨了一个旨在同时最小化完工时间和TEC的多目标RHFSP模型。然而，解决这类复杂的多目标问题引入了几项挑战：（1）传统的进化算法往往难以平衡收敛性和多样性，容易陷入局部最优解[15]；（2）常见的性能指标（如代际距离（GD）和逆代际距离（IGD）依赖于知道真实的帕累托前沿，而随着目标和种群规模的增加，超体积（HV）面临指数级的计算负担[16]；（3）传统的邻域搜索策略通常缺乏问题特定的知识，导致搜索效率低下且缺乏指导；（4）随意使用向后调整策略可能会无意中增加能耗，而不是实现预期的节能效果。
受这些观察的启发，本研究将基于聚类和熵的无监督学习纳入多目标优化过程，以揭示解决方案空间中的潜在结构模式，并实现自适应的数据驱动搜索控制。因此，提出了一种结合聚类和熵引导的无监督学习（CEUL-MOEA）的多目标进化算法。通过嵌入探索-利用种群协同进化机制以及多种协调的优化策略，所提出的算法有效提高了收敛性能、解决方案多样性和整体鲁棒性。本研究的主要贡献如下：
（1）为了解决第一个挑战，本研究构建了一个基于探索和利用种群的协同进化多目标优化框架。在该框架中，利用种群通过内部评估指标驱动的局部搜索机制进行精细搜索，而探索种群通过性能驱动的合作交叉机制增强全局搜索能力。
（2）为了解决第二个挑战，引入了四个轻量级的内部评估指标来评估收敛性、边界覆盖率和分布均匀性。这些指标提供了对外部指标的可扩展和实用的替代方案，并进一步支持了六种指标驱动的局部搜索策略的设计，这些策略动态指导利用种群。
（3）为了解决第三个挑战，开发了一种基于聚类和熵引导的邻域搜索方法。首先使用基于密度的聚类方法识别目标空间中的分布模式，区分密集区域和稀疏区域。随后，基于熵的加权机制量化每个簇内的解决方案密度，以动态分配搜索资源。
（4）为了解决第四个挑战，提出了两个关于能量驱动的向后调整（ED-BA）策略的定理及其正式证明。基于这些定理，设计了单循环和多循环ED-BA策略。该方法通过为目标操作的开始时间引入有针对性的延迟来减少非生产性空闲时间，而不违反可行性或延长整体完工时间，从而实现更节能的调度结果。

**论文结构**
第2节回顾了有关重入混合流水线调度问题的相关工作和研究动机。第3节介绍了问题描述和数学模型。第4节详细介绍了结合聚类和熵引导的无监督学习的多目标进化算法的设计和实现。第5节描述了实验设计和结果分析。最后，第6节总结了研究并概述了未来研究的潜在方向。

**相关工作**
近年来，由于RHFSP在复杂制造系统中的实际相关性，它受到了广泛关注。研究人员提出了各种启发式、元启发式和基于ML的方法来解决RHFSP的单目标和多目标形式。在单目标优化领域，大多数研究集中在最小化完工时间上。Hekmatfar等人[17]开发了一种混合遗传算法（HGA），其性能优于其他方法。

**问题描述和数学模型**
RHFSP可以分解为两个基本子问题：作业排序和机器分配。问题考虑了n个作业，每个作业必须通过L个重入周期的生产阶段。每个周期包含S个顺序处理阶段，其中阶段s(s=1,…,S)配备了ms(ms≥1)个相同的并行机器。至少有一个阶段满足ms≥2，从而引入了并行处理能力。所有作业必须按顺序在各个阶段进行处理，这意味着一个作业可以...

**多目标进化算法结合聚类和熵引导的无监督学习**
为了有效解决RHFSP，本研究提出了一种CEUL-MOEA，如算法1和图4所示。所提出的算法结合了探索-利用种群协同进化框架，显著增强了复杂调度场景中的全局探索和局部利用能力。图4的顶部（第3-5行）对应于初始化阶段，采用了不同的策略来确保种群具有足够的多样性和高质量。

**实验配置**
实验在配备Intel Core i7–13790F处理器（3.60 GHz）和32 GB RAM的Windows 10 64位平台上进行。所有算法均用Python实现，并在PyCharm 2021 IDE中执行。为了确保实验公平性，每个算法每个实例独立执行五次，终止标准定义为TimeLimit=50×L×n×S毫秒，其中L、n和S分别代表周期数、作业数和阶段数。

**结论和未来工作**
本文重点关注RHFSP，因为它在复杂制造系统中的实际重要性。首先开发了一个具有TEC约束的数学模型。然后，提出了一种结合聚类和熵引导的无监督学习（CEUL-MOEA）的多目标进化算法。该方法采用探索-利用协同进化框架来平衡全局和局部搜索，并引入了一种轻量级的基于内部评估的局部搜索策略。

**局限性**
尽管所提出的CEUL-MOEA取得了良好的性能，但仍存在一些局限性。从建模角度来看，它目前仅限于具有TEC目标的RHFSP，尚未扩展到多工厂或多站点调度等更复杂的场景。此外，尚未考虑碳排放和环境影响等关键可持续性指标。从算法角度来看，尽管无监督学习组件避免了显式训练，但...

**未来工作**
未来的研究将把CEUL-MOEA扩展到多工厂和多站点调度问题，以更好地反映现实世界的制造环境。将纳入与可持续性相关的目标，特别是碳排放，以构建更全面的多目标优化框架。将探索自适应参数控制策略以提高鲁棒性和降低敏感性。此外，还将探索更先进的学习范式，如基于图的表示方法...

**作者贡献声明**
李车祥：撰写——原始草稿、验证、软件、方法论、调查、概念化。
韩玉燕：撰写——审阅与编辑、监督、方法论、调查、资金获取。
王玉婷：撰写——审阅与编辑、监督、方法论、调查、数据整理。
陈庆达：监督。
高方正：监督。