METODOLOGÍA PROCEDIMIENTO DE BÚSQUEDA BASADOS EN FUNCIONES “GREEDY” ALEATORIZADAS ADAPTATIVAS. “GRASP”
La metodología GRASP fue desarrollada al final de la década de los 80 con el objetivo inicial de resolver problemas de cubrimientos de conjuntos (Feo & Resende, A probabilistic heuristic for a computationally difficult set covering problem., 1989) esta metodología ha sido uno de los métodos meta-heurísticos más exitosos de los últimos años. El término GRASP fue introducido por Feo y Resende en 1995 (Feo & Resende, Greedy randomized adaptive search procedures, 1995) como una nueva técnica meta-heurística de propósito general. GRASP es el acrónimo de Greedy Randomized Adaptive Search Procedure que significa Procedimiento de Búsqueda Basados en Funciones “Greedy” Aleatorizadas Adaptativas.
Al definir la metodología GRASP es conveniente que podamos relacionarlo a otros métodos, dentro del conjunto de las meta-heurísticas para entender su procedimiento, lo más similar a este método sea referirse al método Multi-start el cual consiste en generar múltiples soluciones iníciales aleatorias de tal forma que a cada una de ellas se le pueda aplicar una búsqueda local. Pues bien, GRASP es similar salvo que las soluciones sobre las que se aplica la búsqueda local no son completamente aleatorias, tienen un componente de aleatoriedad el cual está controlado y enmarcado dentro de un proceso constructivo. Así pues, GRASP consiste en repetir múltiples veces un esquema de dos fases: construir una solución y aplicarle búsqueda local. La segunda fase (búsqueda local) se puede aplicar una búsqueda local convencional (o incluso una Búsqueda en Vecindad Variables, VNS, si se desea).
Entonces GRASP consiste de dos fases: la constructiva donde se produce una solución factible, aunque no necesariamente es óptima y la segunda fase es una búsqueda local, en la cual se examinan vecindades de la solución de la fase anterior, esta fase usa la solución inicial como punto de partida de la fase de búsqueda local.
