A machine learning framework for neighbor generation in metaheuristic search
This work addresses the challenge of enhancing metaheuristic efficiency for combinatorial optimization problems, though it appears incremental as it builds on existing methods with a learning-based twist.
The paper tackles the problem of improving metaheuristic search for combinatorial optimization by proposing a machine learning framework for neighbor generation, achieving a satisfactory trade-off between exploration and exploitation in applications like Wireless Network Optimization and Mixed-Integer Programs.
This paper presents a methodology for integrating machine learning techniques into metaheuristics for solving combinatorial optimization problems. Namely, we propose a general machine learning framework for neighbor generation in metaheuristic search. We first define an efficient neighborhood structure constructed by applying a transformation to a selected subset of variables from the current solution. Then, the key of the proposed methodology is to generate promising neighbors by selecting a proper subset of variables that contains a descent of the objective in the solution space. To learn a good variable selection strategy, we formulate the problem as a classification task that exploits structural information from the characteristics of the problem and from high-quality solutions. We validate our methodology on two metaheuristic applications: a Tabu Search scheme for solving a Wireless Network Optimization problem and a Large Neighborhood Search heuristic for solving Mixed-Integer Programs. The experimental results show that our approach is able to achieve a satisfactory trade-off between the exploration of a larger solution space and the exploitation of high-quality solution regions on both applications.