Ensemble machine learning-based stopping rule for greedy randomized adaptive search procedure
Open Access
- 27 March 2026
- journal article
- research article
- Published by EDP Sciences in RAIRO - Operations Research
- Vol. 60 (2) , 643-684
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.Keywords
Funding Information
- Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (001)
This publication has 57 references indexed in Scilit:
- Bézier-based biased random-key genetic algorithm to address printability constraints in the topology optimization of concrete structuresStructural and Multidisciplinary Optimization, 2022
- A GRASP for the Minimum Cost SAT Problem2017
- Learning a Stopping Criterion for Local Search2016
- Optimization by GRASP2016
- Brief History and Overview of Intelligent Optimization Algorithms2014
- Parallel Genetic Algorithms2011
- GRASP with Path-Relinking: Recent Advances and Applications2005
- GRASP with Path-Relinking for the Quadratic Assignment ProblemLecture Notes in Computer Science, 2004
- Greedy Randomized Adaptive Search ProceduresJournal of Global Optimization, 1995
- Bayesian stopping rules for multistart global optimization methodsMathematical Programming, 1987