Dynamic operator management in meta-heuristics using reinforcement learning: an application to permutation flowshop scheduling problems

📄 arXiv: 2408.14864v1 📥 PDF

作者: Maryam Karimi Mamaghan, Mehrdad Mohammadi, Wout Dullaert, Daniele Vigo, Amir Pirayesh

分类: cs.LG

发布日期: 2024-08-27

💡 一句话要点

提出基于强化学习的动态算子管理框架，用于置换流水车间调度问题。

🎯 匹配领域: 支柱二：RL算法与架构 (RL & Architecture)

关键词: 强化学习 元启发式算法 动态算子管理 置换流水车间调度 Q学习 组合优化 自适应算法

📋 核心要点

  1. 现有元启发式算法在算子选择上依赖专家知识，且算子组合固定，难以适应复杂问题。
  2. 提出基于强化学习的动态算子管理框架，自动调整算子组合，并自适应选择最优算子。
  3. 在置换流水车间调度问题上的实验表明，该框架在最优性差距和收敛速度上优于现有算法。

📝 摘要（中文）

本研究提出了一种基于强化学习的框架，用于在元启发式算法中动态管理大量的搜索算子组合。该框架借鉴禁忌搜索的思想，通过临时排除效率较低的算子并在搜索过程中更新算子组合来实现持续自适应。采用基于Q学习的自适应算子选择机制，在每个阶段从动态更新的算子组合中选择最合适的算子。与传统方法不同，所提出的框架不需要专家提供关于搜索算子的输入，从而允许领域内的非专家有效地使用该框架。通过应用于置换流水车间调度问题来分析所提出框架的性能。结果表明，在最优性差距和收敛速度方面，所提出的框架优于最先进的算法。

🔬 方法详解

问题定义：论文旨在解决置换流水车间调度问题（Permutation Flowshop Scheduling Problem, PFSP）。现有元启发式算法在解决PFSP时，通常依赖于固定的算子组合和专家经验来选择算子，这限制了算法的自适应性和通用性。对于非专家用户，难以有效利用这些算法。

核心思路：论文的核心思路是利用强化学习（Reinforcement Learning, RL）来动态管理和选择元启发式算法中的搜索算子。通过RL，算法可以自动学习不同算子在不同搜索阶段的效率，并动态调整算子组合，从而提高算法的自适应性和性能。

技术框架：该框架主要包含以下几个模块：1) 算子组合动态更新：借鉴禁忌搜索的思想，根据算子的历史表现，动态地将表现不佳的算子暂时排除在算子组合之外。2) 基于Q学习的自适应算子选择：使用Q学习算法，将搜索状态作为状态空间，将算子选择作为动作空间，通过奖励函数来评估每个算子的表现，从而学习最优的算子选择策略。3) 奖励函数设计：奖励函数用于评估每个算子的表现，并指导Q学习算法的学习方向。奖励函数的设计需要考虑问题的具体特点，例如，可以根据解的改进程度来设计奖励函数。

关键创新：该论文的关键创新在于：1) 提出了一种基于强化学习的动态算子管理框架，可以自动调整算子组合和选择算子，无需专家干预。2) 将禁忌搜索的思想融入到算子组合的动态更新中，提高了算法的搜索效率。3) 将Q学习应用于自适应算子选择，使得算法可以根据搜索状态选择最优的算子。

关键设计：1) 状态空间：搜索状态的表示方式，例如，可以使用当前解的目标函数值、迭代次数等作为状态特征。2) 动作空间：可供选择的算子集合。3) 奖励函数：根据解的改进程度来设计奖励函数，例如，可以使用目标函数值的变化量作为奖励。4) Q学习参数：学习率、折扣因子等参数需要根据具体问题进行调整。

🖼️ 关键图片

fig_0
fig_1
fig_2

📊 实验亮点

实验结果表明，所提出的基于强化学习的动态算子管理框架在置换流水车间调度问题上优于现有算法。具体而言，该框架在最优性差距和收敛速度方面均取得了显著提升。与现有算法相比，该框架能够更快地找到更优的解，并且具有更好的鲁棒性。

🎯 应用场景

该研究成果可应用于各种组合优化问题，尤其是在调度、路径规划、资源分配等领域。通过自动学习和调整搜索策略，该框架可以帮助非专家用户更有效地解决复杂的优化问题，提高生产效率和资源利用率。未来，该框架可以扩展到其他元启发式算法和更广泛的应用领域。

📄 摘要（原文）

This study develops a framework based on reinforcement learning to dynamically manage a large portfolio of search operators within meta-heuristics. Using the idea of tabu search, the framework allows for continuous adaptation by temporarily excluding less efficient operators and updating the portfolio composition during the search. A Q-learning-based adaptive operator selection mechanism is used to select the most suitable operator from the dynamically updated portfolio at each stage. Unlike traditional approaches, the proposed framework requires no input from the experts regarding the search operators, allowing domain-specific non-experts to effectively use the framework. The performance of the proposed framework is analyzed through an application to the permutation flowshop scheduling problem. The results demonstrate the superior performance of the proposed framework against state-of-the-art algorithms in terms of optimality gap and convergence speed.