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

• URL: http://arxiv.org/abs/2408.14864v1
• Date: Tue, 27 Aug 2024 08:38:17 GMT
• Title: Dynamic operator management in meta-heuristics using reinforcement learning: an application to permutation flowshop scheduling problems
• Authors: Maryam Karimi Mamaghan, Mehrdad Mohammadi, Wout Dullaert, Daniele Vigo, Amir Pirayesh,
• Abstract summary: This study develops a framework based on reinforcement learning to dynamically manage a large portfolio of search operators within meta-heuristics. A Q-learning-based adaptive operator selection mechanism is used to select the most suitable operator from the dynamically updated portfolio. The performance of the proposed framework is analyzed through an application to the permutation flowshop scheduling problem.
• Score: 0.3495246564946556
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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.

Related papers

• Hierarchical Reinforcement Learning for Temporal Abstraction of Listwise Recommendation [51.06031200728449]
  We propose a novel framework called mccHRL to provide different levels of temporal abstraction on listwise recommendation. Within the hierarchical framework, the high-level agent studies the evolution of user perception, while the low-level agent produces the item selection policy. Results observe significant performance improvement by our method, compared with several well-known baselines.
  arXiv  Detail & Related papers  (2024-09-11T17:01:06Z)
• Constrained Multi-objective Optimization with Deep Reinforcement Learning Assisted Operator Selection [28.088046969822543]
  This work proposes an online operator selection framework assisted by Deep Reinforcement Learning. The proposed approach can adaptively select an operator that maximizes the improvement of the population according to the current state. The framework is embedded into four popular CMOEAs and assessed on 42 benchmark problems.
  arXiv  Detail & Related papers  (2024-01-15T09:51:19Z)
• Graph Reinforcement Learning for Operator Selection in the ALNS Metaheuristic [0.0]
  We formulate the choice of operators as a Markov Decision Process. We propose a practical approach based on Deep Reinforcement Learning and Graph Neural Networks.
  arXiv  Detail & Related papers  (2023-02-28T15:39:42Z)
• Backpropagation of Unrolled Solvers with Folded Optimization [55.04219793298687]
  The integration of constrained optimization models as components in deep networks has led to promising advances on many specialized learning tasks. One typical strategy is algorithm unrolling, which relies on automatic differentiation through the operations of an iterative solver. This paper provides theoretical insights into the backward pass of unrolled optimization, leading to a system for generating efficiently solvable analytical models of backpropagation.
  arXiv  Detail & Related papers  (2023-01-28T01:50:42Z)
• Socio-cognitive Optimization of Time-delay Control Problems using Evolutionary Metaheuristics [89.24951036534168]
  Metaheuristics are universal optimization algorithms which should be used for solving difficult problems, unsolvable by classic approaches. In this paper we aim at constructing novel socio-cognitive metaheuristic based on castes, and apply several versions of this algorithm to optimization of time-delay system model.
  arXiv  Detail & Related papers  (2022-10-23T22:21:10Z)
• Option-Aware Adversarial Inverse Reinforcement Learning for Robotic Control [44.77500987121531]
  Hierarchical Imitation Learning (HIL) has been proposed to recover highly-complex behaviors in long-horizon tasks from expert demonstrations. We develop a novel HIL algorithm based on Adversarial Inverse Reinforcement Learning. We also propose a Variational Autoencoder framework for learning with our objectives in an end-to-end fashion.
  arXiv  Detail & Related papers  (2022-10-05T00:28:26Z)
• Improved Algorithms for Neural Active Learning [74.89097665112621]
  We improve the theoretical and empirical performance of neural-network(NN)-based active learning algorithms for the non-parametric streaming setting. We introduce two regret metrics by minimizing the population loss that are more suitable in active learning than the one used in state-of-the-art (SOTA) related work.
  arXiv  Detail & Related papers  (2022-10-02T05:03:38Z)
• Neural Combinatorial Optimization: a New Player in the Field [69.23334811890919]
  This paper presents a critical analysis on the incorporation of algorithms based on neural networks into the classical optimization framework. A comprehensive study is carried out to analyse the fundamental aspects of such algorithms, including performance, transferability, computational cost and to larger-sized instances.
  arXiv  Detail & Related papers  (2022-05-03T07:54:56Z)
• Portfolio Search and Optimization for General Strategy Game-Playing [58.896302717975445]
  We propose a new algorithm for optimization and action-selection based on the Rolling Horizon Evolutionary Algorithm. For the optimization of the agents' parameters and portfolio sets we study the use of the N-tuple Bandit Evolutionary Algorithm. An analysis of the agents' performance shows that the proposed algorithm generalizes well to all game-modes and is able to outperform other portfolio methods.
  arXiv  Detail & Related papers  (2021-04-21T09:28:28Z)
• NOVAS: Non-convex Optimization via Adaptive Stochastic Search for End-to-End Learning and Control [22.120942106939122]
  We propose the use of adaptive search as a building block for general, non- neural optimization operations. We benchmark it against two existing alternatives on a synthetic energy-based structured task, and showcase its use in optimal control applications.
  arXiv  Detail & Related papers  (2020-06-22T03:40:36Z)
• Learning Heuristic Selection with Dynamic Algorithm Configuration [44.91083687014879]
  We show that dynamic algorithm configuration can be used for dynamic selection dynamics of a planning system. We show that this approach generalizes over existing approaches and that it can exponentially improve performance of the domain search.
  arXiv  Detail & Related papers  (2020-06-15T09:35:07Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.