A Meta-learning Approach to Recommend the Meta-heuristic Algorithm Based on Instance Features

Jianshuang Cui, Fan YangAtlantis 2023 · DOI · OpenAlex

Abstract

This paper studies a framework for implementing meta-heuristic algorithm selection based on a meta-learning approach, which is used to recommend the most suitable meta-heuristic algorithm for different problem instances instantly. A small sample of instances for the capacitated vehicle routing problem (CVRP) is selected as an experimental data set, with artificial bee colony, particle swarm optimization, ant colony, artificial fish colony, and genetic algorithms selected as the recommended algorithms. This study establishes the classification labels corresponding to the problem and the algorithm by running the optimization algorithms. The meta-knowledge base corresponding to the features and labels is generated by extracting a set of instance features. When a new instance is given, its features only need to be extracted to recommend an algorithm. In the process, three meta-learning algorithms—random forest (RF), BP neural network, and K-nearest neighbor (KNN)—are used to train the meta-model, and comparative analysis is applied. The experimental results show that the average recommendation accuracy is about 80%.

Introduction

In the field of optimization, the "No Free Lunch" theorem posits that no single algorithm is universally superior across all possible problems. For the Capacitated Vehicle Routing Problem (CVRP)—a classic NP-hard challenge involving the delivery of goods to customers with limited vehicle capacity—researchers have developed numerous meta-heuristics, such as Genetic Algorithms (GA) and Ant Colony Optimization (ACS).

However, an algorithm that excels on one delivery route might perform poorly on another. Currently, practitioners often select an algorithm based on intuition or exhaustive trial-and-error testing. This research aims to bridge this gap by creating an automated recommendation system that analyzes the "fingerprint" (features) of a specific CVRP instance to instantly suggest the most efficient solver.

Methodology

The proposed framework consists of four primary modules designed to automate the selection process:

  1. Problem Module: 19 static features are extracted from CVRP instances, including the number of vehicles, total demand, and various distance metrics (minimum, average, and standard deviation of distances).
  2. Algorithm Module: Five popular swarm intelligence algorithms—Artificial Bee Colony (ABC), Particle Swarm Optimization (PSO), Ant Colony System (ACS), Artificial Fish Swarms (AFSA), and Genetic Algorithm (GA)—are executed on a set of instances to establish ground truth labels for performance.
  3. Meta-learning Module: Three machine learning models—Random Forest (RF), Backpropagation (BP) Neural Networks, and K-Nearest Neighbor (KNN)—are trained to map instance features to the best-performing algorithm.
  4. Prediction Module: For any new instance, features are extracted and fed into the trained meta-recommendation model to output the most suitable algorithm.
The proposed meta-learning framework for algorithm recommendation.

A key technical contribution is the MSE-based feature screening method. By iteratively adding features and retaining only those that decreased the Mean Squared Error (MSE), the researchers effectively pruned the feature set, simplifying the computation without sacrificing accuracy.

Datasets and Experimental Setup

The study utilized 102 instances from the CVRPLIB, a standard library for vehicle routing problems. These instances varied in complexity, with customer nodes ranging from 19 to 101. For final validation, a separate set of 20 "unseen" instances was used to test the model's real-world predictive power.

Key Results and Insights

The experimental results demonstrate that the meta-learning approach significantly outperforms random selection. While a random choice has only a 20% probability of picking the best algorithm among five, the meta-learning approach achieves approximately 80% accuracy.

Performance comparison of meta-learning algorithms showing BP neural network as the top performer.
  • Top Performer: The BP Neural Network consistently outperformed other models, achieving a recommendation accuracy ($Hr$) of 80.00% and the lowest MSE (0.080). This suggests that the relationship between CVRP geometry (like demand distribution and node density) and algorithm efficiency is highly non-linear and complex.
  • Comparative Accuracy: Random Forest followed with a 70.00% accuracy rate, while KNN trailed at 65.00%.
  • Generalization: When tested on the 20 unseen instances, the BP model maintained its 80% accuracy, proving its robustness and ability to generalize beyond the training data.

Conclusion

The algorithm recommendation framework based on instance features provides a viable path toward automated optimization. By treating a problem's features as its "contour," the meta-learner identifies which meta-heuristics are best equipped for specific problem shapes. Future work may involve expanding the dataset, incorporating dynamic "probing" features, and extending the framework to other combinatorial problems like scheduling.

Summary updated

Abstract

This paper studies a framework for implementing meta-heuristic algorithm selection based on meta-learning approach, which is used to recommend the most suitable meta-heuristic algorithm for different problem instances instantly.Therefore, a small sample of instances for capacitated vehicle routing problem (CVRP) is selected as an experimental data set, artificial bee colony, particle swarm optimization, ant colony, artificial fish colony and genetic algorithm which are selected as the recommended algorithms.This study establishes the classification label corresponding to the problem and the algorithm by running the optimization algorithms.The meta-knowledge base corresponding to the feature and the label is generated by extracting a set of instance features.When a new instance is given, its features only need to be extracted to recommend an algorithm.In the process, three meta-learning algorithms of random forest, BP neural network and K-nearest neighbor are used to train meta-model, and comparative analysis is applied.The experimental results show that the average recommendation accuracy is about 80%.The algorithm recommendation framework based on instance features can be extended to similar applications.
BibTeX
@inproceedings{cui2023meta,
  author = {Jianshuang Cui and Fan Yang},
  title = {{A Meta-learning Approach to Recommend the Meta-heuristic Algorithm Based on Instance Features}},
  booktitle = {Atlantis},
  year = {2023},
  doi = {10.2991/978-94-6463-056-5\_23},
}
Figure