Operations Research 2025
Abstract Submission

109. Intelligent Optimization: explorations in using Reinforcement Learning for the Online Tuning of Optimization Heuristics

Invited abstract in session WE-12: AI in Optimization Heuristics, stream Artificial Intelligence, Machine Learning and Optimization.

Wednesday, 16:30-18:00
Room: H10

Authors (first author is the speaker)

1. Roberto Battiti
DISI, University of Trento
2. Mauro Brunato
DISI, University of Trento

Abstract

Reactive Search Optimization (RSO) [1] advocates the integration of sub-symbolic machine learning techniques into search heuristics. The word reactive hints at a ready response to events during the search through an internal online feedback loop for the self-tuning of critical parameters. In this manner the knowledge about the specific task and the local properties of the fitness surface surrounding the current tentative solution can influence the future search steps to render them more effective. Reinforcement Learning (RL) arises in a different context of machine learning, in which feedback signals from the environment are used by the learner to modify future actions.

This paper is about Reinforcement Learning (RL) applied to online parameter tuning in Stochastic Local Search (SLS) methods for Combinatorial Optimization.

Our initial investigation about using RL for Optimization [2] considered RL for the Reactive Tabu Search (RTS) method, where the appropriate amount of diversification in prohibition-based (Tabu) local search is adapted in a fast online manner to the characteristics of a task and of the local configuration.

The topic of (deep) Reinforcement Learning for Optimization is witnessing an intense research effort in recent years. In this work we compare the novel and old approaches on significant Combinatorial Optimization tasks to assess their strengths and weaknesses.

[1] The Reactive Tabu Search
Roberto Battiti, Giampietro Tecchiolli
ORSA Journal on Computing 1994/5
Volume 6 (2)
Pages 126-140

[2] Learning while Optimizing an Unknown Fitness Surface.
Roberto Battiti, Mauro Brunato, Paolo Campigotto.
Proc. 2nd Learning and Intelligent Optimization Workshop (LION2007 II, Trento, Italy, 2008

Keywords

Status: accepted

Back to the list of papers