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

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.