# Boosting Ant Colony Optimization via Solution Prediction and Machine Learning

arXiv: https://arxiv.org/abs/2008.04213 · HTML: https://mlsanity.com/paper/2008.04213/

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 29 Jul 2020.

## Built on by (most cited first, 7 of 7)

- [DeepACO: Neural-enhanced Ant Systems for Combinatorial Optimization](https://mlsanity.com/paper/2309.14032/) (2023)
- [Algorithm Evolution Using Large Language Model](https://mlsanity.com/paper/2311.15249/) (2023)
- [Metaheuristics and Large Language Models Join Forces: Toward an Integrated Optimization Approach](https://mlsanity.com/paper/2405.18272/) (2024)
- [Adaptive Stabilization Based on Machine Learning for Column Generation](https://mlsanity.com/paper/2405.11198/) (2024)
- [Enhancing Constraint Programming via Supervised Learning for Job Shop Scheduling](https://mlsanity.com/paper/2211.14492/) (2022)
- [A learning-based solution approach to the application placement problem in mobile edge computing under uncertainty](https://mlsanity.com/paper/2403.11259/) (2024)
- [Machine Learning-Enhanced Ant Colony Optimization for Column Generation](https://mlsanity.com/paper/2407.01546/) (2024)

## Abstract (arXiv)

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.