Ensemble machine learning-based stopping rule for greedy randomized adaptive search procedure

¹ PESC/COPPE, Federal University of Rio de Janeiro, Rio de Janeiro, RJ, Brazil
² Institute of Science and Technology, São Paulo State University, Sorocaba, SP, Brazil
³ Recod.ai Lab, Institute of Computing, State University of Campinas, Campinas, SP, Brazil
⁴ Tercio Pacitti Institute (NCE), Federal University of Rio de Janeiro, Rio de Janeiro, RJ, Brazil

^* Corresponding author: This email address is being protected from spambots. You need JavaScript enabled to view it.

Received: 21 June 2025
Accepted: 14 January 2026

Abstract

As with many metaheuristics, the Greedy Randomized Adaptive Search Procedure (GRASP) lacks an effective stopping rule in its standard form and relies on ineffective criteria. This often leads to a waste of computational resources. To address this limitation, rules based on Bayesian statistics, cumulative distribution function, extreme value theory, and machine learning algorithms have been proposed in the literature. However, these methods also present shortcomings, as they may fail on certain instance types or be computationally expensive. In response, this work seeks to better understand these shortcomings and overcome some of them through an ensemble-based machine learning approach. To demonstrate its capabilities, the new rule was evaluated on a custom dataset composed of execution data from three optimization problems and compared to a group of alternatives. The evaluation used cross-validation and an additional test designed to assess generalization across problems, in which the model was trained on two optimization problems and tested on a third. Two custom metrics focused on evaluating how well the rules stop the metaheuristic at predetermined points in the search are also introduced. The results indicate that the proposed stopping rule is competitive on harder instances.