Neural Networks for Local Search and Crossover in Vehicle Routing: A Possible Overkill?

• URL: http://arxiv.org/abs/2210.12075v1
• Date: Fri, 9 Sep 2022 22:08:17 GMT
• Title: Neural Networks for Local Search and Crossover in Vehicle Routing: A Possible Overkill?
• Authors: \'Italo Santana, Andrea Lodi and Thibaut Vidal
• Abstract summary: We investigate the use of predictions from graph neural networks (GNNs) in the form of heatmaps to improve the Hybrid Genetic Search (HGS) We show that exploiting more sophisticated strategies using measures of node relatedness can significantly enhance performance. However, contrary to initial expectations, we also observed that heatmaps did not present significant advantages over simpler distance measures.
• Score: 10.882329986831087
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Extensive research has been conducted, over recent years, on various ways of enhancing heuristic search for combinatorial optimization problems with machine learning algorithms. In this study, we investigate the use of predictions from graph neural networks (GNNs) in the form of heatmaps to improve the Hybrid Genetic Search (HGS), a state-of-the-art algorithm for the Capacitated Vehicle Routing Problem (CVRP). The crossover and local-search components of HGS are instrumental in finding improved solutions, yet these components essentially rely on simple greedy or random choices. It seems intuitive to attempt to incorporate additional knowledge at these levels. Throughout a vast experimental campaign on more than 10,000 problem instances, we show that exploiting more sophisticated strategies using measures of node relatedness (heatmaps, or simply distance) within these algorithmic components can significantly enhance performance. However, contrary to initial expectations, we also observed that heatmaps did not present significant advantages over simpler distance measures for these purposes. Therefore, we faced a common -- though rarely documented -- situation of overkill: GNNs can indeed improve performance on an important optimization task, but an ablation analysis demonstrated that simpler alternatives perform equally well.

Related papers

• Ant Colony Sampling with GFlowNets for Combinatorial Optimization [68.84985459701007]
  This paper introduces the Generative Flow Ant Colony Sampler (GFACS), a neural-guided probabilistic search algorithm for solving optimization (CO) GFACS integrates generative flow networks (GFlowNets), an emerging amortized inference method, with ant colony optimization (ACO), a promising probabilistic search algorithm.
  arXiv  Detail & Related papers  (2024-03-11T16:26:06Z)
• Genetically Modified Wolf Optimization with Stochastic Gradient Descent for Optimising Deep Neural Networks [0.0]
  This research aims to analyze an alternative approach to optimizing neural network (NN) weights, with the use of population-based metaheuristic algorithms. A hybrid between Grey Wolf (GWO) and Genetic Modified Algorithms (GA) is explored, in conjunction with Gradient Descent (SGD) This algorithm allows for a combination between exploitation and exploration, whilst also tackling the issue of high-dimensionality.
  arXiv  Detail & Related papers  (2023-01-21T13:22:09Z)
• A Metaheuristic Algorithm for Large Maximum Weight Independent Set Problems [58.348679046591265]
  Given a node-weighted graph, find a set of independent (mutually nonadjacent) nodes whose node-weight sum is maximum. Some of the graphs airsing in this application are large, having hundreds of thousands of nodes and hundreds of millions of edges. We develop a new local search algorithm, which is a metaheuristic in the greedy randomized adaptive search framework.
  arXiv  Detail & Related papers  (2022-03-28T21:34:16Z)
• Flipping the switch on local exploration: Genetic Algorithms with Reversals [0.0]
  Authors show that gradient-free search techniques are suitable for providing an optimal solution in the discrete domain. They also show that the use of multiple local searches can improve performance on local searches. It is observed that the proposed GA variants have the least average cost across all benchmarks including the problem proposed and IC performs better than its constituents.
  arXiv  Detail & Related papers  (2022-02-02T08:27:11Z)
• Boosting Graph Search with Attention Network for Solving the General Orienteering Problem [7.0786689796236155]
  We propose a novel combination of a beam search and a learned algorithm for solving the orienteering problem. We acquire the algorithm with an attention network that takes the distances among nodes as input, and learn it via a reinforcement learning framework. Our method can surpass a wide range of baselines and achieve results close to the optimal or highly specialized approach.
  arXiv  Detail & Related papers  (2021-09-10T08:23:19Z)
• Practical Schemes for Finding Near-Stationary Points of Convex Finite-Sums [45.91933657088324]
  We conduct a systematic study of the algorithmic techniques in finding near-stationary points of convex finite-sums. Our main contributions are several algorithmic discoveries. We put an emphasis on the simplicity and practicality of the new schemes, which could facilitate future developments.
  arXiv  Detail & Related papers  (2021-05-25T16:46:35Z)
• Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
  This paper investigates the classical integer least-squares problem which estimates signals integer from linear models. The problem is NP-hard and often arises in diverse applications such as signal processing, bioinformatics, communications and machine learning. We propose a general hyper-accelerated tree search (HATS) algorithm by employing a deep neural network to estimate the optimal estimation for the underlying simplified memory-bounded A* algorithm.
  arXiv  Detail & Related papers  (2021-01-07T08:00:02Z)
• Hybrid Genetic Search for the CVRP: Open-Source Implementation and SWAP* Neighborhood [6.85316573653194]
  We introduce a simple -- open-source -- implementation of the hybrid genetic search (HGS) specialized to the capacitated vehicle routing problem (CVRP) This state-of-the-art algorithm uses the same general methodology as Vidal et al. (2012) but also includes additional methodological improvements and lessons learned over the past decade of research.
  arXiv  Detail & Related papers  (2020-11-23T21:37:49Z)
• Investigating the Scalability and Biological Plausibility of the Activation Relaxation Algorithm [62.997667081978825]
  Activation Relaxation (AR) algorithm provides a simple and robust approach for approximating the backpropagation of error algorithm. We show that the algorithm can be further simplified and made more biologically plausible by introducing a learnable set of backwards weights. We also investigate whether another biologically implausible assumption of the original AR algorithm -- the frozen feedforward pass -- can be relaxed without damaging performance.
  arXiv  Detail & Related papers  (2020-10-13T08:02:38Z)
• Second-Order Guarantees in Centralized, Federated and Decentralized Nonconvex Optimization [64.26238893241322]
  Simple algorithms have been shown to lead to good empirical results in many contexts. Several works have pursued rigorous analytical justification for studying non optimization problems. A key insight in these analyses is that perturbations play a critical role in allowing local descent algorithms.
  arXiv  Detail & Related papers  (2020-03-31T16:54:22Z)
• AutoML-Zero: Evolving Machine Learning Algorithms From Scratch [76.83052807776276]
  We show that it is possible to automatically discover complete machine learning algorithms just using basic mathematical operations as building blocks. We demonstrate this by introducing a novel framework that significantly reduces human bias through a generic search space. We believe these preliminary successes in discovering machine learning algorithms from scratch indicate a promising new direction in the field.
  arXiv  Detail & Related papers  (2020-03-06T19:00:04Z)

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.