El procedimiento de búsqueda adaptativa aleatoria voraz (también conocido como GRASP ) es un algoritmo metaheurístico que se aplica comúnmente a problemas de optimización combinatoria . GRASP consiste típicamente en iteraciones formadas por construcciones sucesivas de una solución aleatoria voraz y mejoras iterativas subsiguientes de la misma a través de una búsqueda local . [1] Las soluciones aleatorias voraces se generan añadiendo elementos al conjunto de soluciones del problema a partir de una lista de elementos clasificados por una función voraz según la calidad de la solución que obtendrán. Para obtener variabilidad en el conjunto de candidatos de soluciones voraces, los elementos candidatos bien clasificados se colocan a menudo en una lista de candidatos restringida (RCL) y se eligen al azar al construir la solución. Este tipo de método de construcción aleatoria voraz también se conoce como heurística semi-voraz , descrita por primera vez en Hart y Shogan (1987). [2]
GRASP fue introducido por primera vez por Feo y Resende (1989). [3] Los artículos de investigación sobre GRASP incluyen Feo y Resende (1995), [1] y Resende y Ribeiro (2003). [4]
Existen variantes del algoritmo clásico, como el Reactive GRASP. En esta variante, el parámetro básico que define la restrictividad del RCL durante la fase de construcción se autoajusta en función de la calidad de las soluciones encontradas previamente. [5] También existen técnicas para acelerar la búsqueda, como las perturbaciones de costes, las funciones de sesgo, la memorización y el aprendizaje, y la búsqueda local sobre soluciones parcialmente construidas. [4]