Boosting Ant Colony Optimization via Solution Prediction and Machine Learning

• URL: http://arxiv.org/abs/2008.04213v2
• Date: Sun, 7 Nov 2021 05:54:16 GMT
• Title: Boosting Ant Colony Optimization via Solution Prediction and Machine Learning
• Authors: Yuan Sun, Sheng Wang, Yunzhuang Shen, Xiaodong Li, Andreas T. Ernst, and Michael Kirley
• Abstract summary: This paper introduces an enhanced meta-heuristic (ML-ACO) that combines machine learning (ML) and ant colony optimization (ACO) to solve optimization problems.
• Score: 10.687150889251031
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: This paper introduces an enhanced meta-heuristic (ML-ACO) that combines machine learning (ML) and ant colony optimization (ACO) to solve combinatorial optimization problems. To illustrate the underlying mechanism of our ML-ACO algorithm, we start by describing a test problem, the orienteering problem. In this problem, the objective is to find a route that visits a subset of vertices in a graph within a time budget to maximize the collected score. In the first phase of our ML-ACO algorithm, an ML model is trained using a set of small problem instances where the optimal solution is known. Specifically, classification models are used to classify an edge as being part of the optimal route, or not, using problem-specific features and statistical measures. The trained model is then used to predict the probability that an edge in the graph of a test problem instance belongs to the corresponding optimal route. In the second phase, we incorporate the predicted probabilities into the ACO component of our algorithm, i.e., using the probability values as heuristic weights or to warm start the pheromone matrix. Here, the probability values bias sampling towards favoring those predicted high-quality edges when constructing feasible routes. We have tested multiple classification models including graph neural networks, logistic regression and support vector machines, and the experimental results show that our solution prediction approach consistently boosts the performance of ACO. Further, we empirically show that our ML model trained on small synthetic instances generalizes well to large synthetic and real-world instances. Our approach integrating ML with a meta-heuristic is generic and can be applied to a wide range of optimization problems.

Related papers

• Sample-Efficient Multi-Agent RL: An Optimization Perspective [103.35353196535544]
  We study multi-agent reinforcement learning (MARL) for the general-sum Markov Games (MGs) under the general function approximation. We introduce a novel complexity measure called the Multi-Agent Decoupling Coefficient (MADC) for general-sum MGs. We show that our algorithm provides comparable sublinear regret to the existing works.
  arXiv  Detail & Related papers  (2023-10-10T01:39:04Z)
• DynamoRep: Trajectory-Based Population Dynamics for Classification of Black-box Optimization Problems [0.755972004983746]
  We propose a feature extraction method that describes the trajectories of optimization algorithms using simple statistics. We demonstrate that the proposed DynamoRep features capture enough information to identify the problem class on which the optimization algorithm is running.
  arXiv  Detail & Related papers  (2023-06-08T06:57:07Z)
• Probabilistic Unrolling: Scalable, Inverse-Free Maximum Likelihood Estimation for Latent Gaussian Models [69.22568644711113]
  We introduce probabilistic unrolling, a method that combines Monte Carlo sampling with iterative linear solvers to circumvent matrix inversions. Our theoretical analyses reveal that unrolling and backpropagation through the iterations of the solver can accelerate gradient estimation for maximum likelihood estimation. In experiments on simulated and real data, we demonstrate that probabilistic unrolling learns latent Gaussian models up to an order of magnitude faster than gradient EM, with minimal losses in model performance.
  arXiv  Detail & Related papers  (2023-06-05T21:08:34Z)
• Representation Learning with Multi-Step Inverse Kinematics: An Efficient and Optimal Approach to Rich-Observation RL [106.82295532402335]
  Existing reinforcement learning algorithms suffer from computational intractability, strong statistical assumptions, and suboptimal sample complexity. We provide the first computationally efficient algorithm that attains rate-optimal sample complexity with respect to the desired accuracy level. Our algorithm, MusIK, combines systematic exploration with representation learning based on multi-step inverse kinematics.
  arXiv  Detail & Related papers  (2023-04-12T14:51:47Z)
• Pretrained Cost Model for Distributed Constraint Optimization Problems [37.79733538931925]
  Distributed Constraint Optimization Problems (DCOPs) are an important subclass of optimization problems. We propose a novel directed acyclic graph schema representation for DCOPs and leverage the Graph Attention Networks (GATs) to embed graph representations. Our model, GAT-PCM, is then pretrained with optimally labelled data in an offline manner, so as to boost a broad range of DCOP algorithms.
  arXiv  Detail & Related papers  (2021-12-08T09:24:10Z)
• COCO Denoiser: Using Co-Coercivity for Variance Reduction in Stochastic Convex Optimization [4.970364068620608]
  We exploit convexity and L-smoothness to improve the noisy estimates outputted by the gradient oracle. We show that increasing the number and proximity of the queried points leads to better gradient estimates. We also apply COCO in vanilla settings by plugging it in existing algorithms, such as SGD, Adam or STRSAGA.
  arXiv  Detail & Related papers  (2021-09-07T17:21:09Z)
• A Bi-Level Framework for Learning to Solve Combinatorial Optimization on Graphs [91.07247251502564]
  We propose a hybrid approach to combine the best of the two worlds, in which a bi-level framework is developed with an upper-level learning method to optimize the graph. Such a bi-level approach simplifies the learning on the original hard CO and can effectively mitigate the demand for model capacity.
  arXiv  Detail & Related papers  (2021-06-09T09:18:18Z)
• Quantum-Assisted Feature Selection for Vehicle Price Prediction Modeling [0.0]
  We study metrics for encoding the search as a binary model, such as Generalized Mean Information Coefficient and Pearson Correlation Coefficient. We achieve accuracy scores of 0.9 for finding optimal subsets on synthetic data using a new metric that we define. Our findings show that by leveraging quantum-assisted routines we find solutions that increase the quality of predictive model output.
  arXiv  Detail & Related papers  (2021-04-08T20:48:44Z)
• Offline Model-Based Optimization via Normalized Maximum Likelihood Estimation [101.22379613810881]
  We consider data-driven optimization problems where one must maximize a function given only queries at a fixed set of points. This problem setting emerges in many domains where function evaluation is a complex and expensive process. We propose a tractable approximation that allows us to scale our method to high-capacity neural network models.
  arXiv  Detail & Related papers  (2021-02-16T06:04:27Z)
• Cauchy-Schwarz Regularized Autoencoder [68.80569889599434]
  Variational autoencoders (VAE) are a powerful and widely-used class of generative models. We introduce a new constrained objective based on the Cauchy-Schwarz divergence, which can be computed analytically for GMMs. Our objective improves upon variational auto-encoding models in density estimation, unsupervised clustering, semi-supervised learning, and face analysis.
  arXiv  Detail & Related papers  (2021-01-06T17:36:26Z)
• Discrete-Valued Latent Preference Matrix Estimation with Graph Side Information [12.836994708337144]
  We develop an algorithm that matches the optimal sample complexity. Our algorithm is robust to model errors and outperforms the existing algorithms in terms of prediction performance.
  arXiv  Detail & Related papers  (2020-03-16T06:29:24Z)

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.