A machine learning framework for neighbor generation in metaheuristic search

• URL: http://arxiv.org/abs/2212.11451v1
• Date: Thu, 22 Dec 2022 01:58:04 GMT
• Title: A machine learning framework for neighbor generation in metaheuristic search
• Authors: Defeng Liu, Vincent Perreault, Alain Hertz, Andrea Lodi
• Abstract summary: We propose a general machine learning framework for neighbor generation in metaheuristic search. We validate our methodology on two metaheuristic applications.
• Score: 4.521119623956821
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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.

Related papers

• Exploratory Landscape Analysis for Mixed-Variable Problems [0.7252027234425334]
  We provide the means to compute exploratory landscape features for mixed-variable problems where the decision space is a mixture of continuous, binary, integer, and categorical variables. To further highlight their merit for practical applications, we design and conduct an automated algorithm selection study. Our trained algorithm selector is able to close the gap between the single best and the virtual best solver by 57.5% over all benchmark problems.
  arXiv  Detail & Related papers  (2024-02-26T10:19:23Z)
• Optimizing Solution-Samplers for Combinatorial Problems: The Landscape of Policy-Gradient Methods [52.0617030129699]
  We introduce a novel theoretical framework for analyzing the effectiveness of DeepMatching Networks and Reinforcement Learning methods. Our main contribution holds for a broad class of problems including Max-and Min-Cut, Max-$k$-Bipartite-Bi, Maximum-Weight-Bipartite-Bi, and Traveling Salesman Problem. As a byproduct of our analysis we introduce a novel regularization process over vanilla descent and provide theoretical and experimental evidence that it helps address vanishing-gradient issues and escape bad stationary points.
  arXiv  Detail & Related papers  (2023-10-08T23:39:38Z)
• A Block-Coordinate Approach of Multi-level Optimization with an Application to Physics-Informed Neural Networks [0.0]
  We propose a multi-level algorithm for the solution of nonlinear optimization problems and analyze its evaluation complexity. We apply it to the solution of partial differential equations using physics-informed neural networks (PINNs) and show on a few test problems that the approach results in better solutions and significant computational savings.
  arXiv  Detail & Related papers  (2023-05-23T19:12:02Z)
• Learning Proximal Operators to Discover Multiple Optima [66.98045013486794]
  We present an end-to-end method to learn the proximal operator across non-family problems. We show that for weakly-ized objectives and under mild conditions, the method converges globally.
  arXiv  Detail & Related papers  (2022-01-28T05:53:28Z)
• Algorithm Selection on a Meta Level [58.720142291102135]
  We introduce the problem of meta algorithm selection, which essentially asks for the best way to combine a given set of algorithm selectors. We present a general methodological framework for meta algorithm selection as well as several concrete learning methods as instantiations of this framework.
  arXiv  Detail & Related papers  (2021-07-20T11:23:21Z)
• Learning Primal Heuristics for Mixed Integer Programs [5.766851255770718]
  We investigate whether effective primals can be automatically learned via machine learning. We propose a new method to represent an optimization problem as a graph, and train a Graph Conal Network on solved problem instances with known optimal solutions. The prediction of variable solutions is then leveraged by a novel configuration of the B&B method, Probabilistic Branching with guided Depth-first Search.
  arXiv  Detail & Related papers  (2021-07-02T06:46:23Z)
• Diversity in Kemeny Rank Aggregation: A Parameterized Approach [3.6603644500568806]
  A recent trend in artificial intelligence, called solution diversity, has focused on the development of notions of optimality. In this work, we investigate the impact of this combination in the field of Kemeny Rank Aggregation. Our main results work both when considering the traditional setting of aggregation over linearly ordered votes, and in the more general setting where votes are partially ordered.
  arXiv  Detail & Related papers  (2021-05-19T21:50:03Z)
• End-to-End Constrained Optimization Learning: A Survey [69.22203885491534]
  It focuses on surveying the work on integrating solvers and optimization methods with machine learning architectures. These approaches hold the promise to develop new hybrid machine learning and optimization methods to predict fast, approximate, structural, solutions to problems and to enable logical inference.
  arXiv  Detail & Related papers  (2021-03-30T14:19:30Z)
• PAMELI: A Meta-Algorithm for Computationally Expensive Multi-Objective Optimization Problems [0.0]
  The proposed algorithm is based on solving a set of surrogate problems defined by models of the real one. Our algorithm also performs a meta-search for optimal surrogate models and navigation strategies for the optimization landscape.
  arXiv  Detail & Related papers  (2021-03-19T11:18:03Z)
• A Two-stage Framework and Reinforcement Learning-based Optimization Algorithms for Complex Scheduling Problems [54.61091936472494]
  We develop a two-stage framework, in which reinforcement learning (RL) and traditional operations research (OR) algorithms are combined together. The scheduling problem is solved in two stages, including a finite Markov decision process (MDP) and a mixed-integer programming process, respectively. Results show that the proposed algorithms could stably and efficiently obtain satisfactory scheduling schemes for agile Earth observation satellite scheduling problems.
  arXiv  Detail & Related papers  (2021-03-10T03:16:12Z)
• Optimizing Wireless Systems Using Unsupervised and Reinforced-Unsupervised Deep Learning [96.01176486957226]
  Resource allocation and transceivers in wireless networks are usually designed by solving optimization problems. In this article, we introduce unsupervised and reinforced-unsupervised learning frameworks for solving both variable and functional optimization problems.
  arXiv  Detail & Related papers  (2020-01-03T11:01:52Z)

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.