SUJETAR

Procedimiento de búsqueda adaptativa aleatoria codiciosa (GRASP)

El algoritmo Greedy Randomized Adaptive Search Procedure (GRASP) es un metaheurística introducido por Feo y Resende en 1989.

Su funcionamiento se basa en la repetición de dos fases: una construcción glotona seguida de una busqueda local.

La característica del método GRASP es su fase de construcción de una solución. Para ello, el algoritmo mantiene una lista actualizada de fragmentos de posibles soluciones (RCL, lista de candidatos restringidos). La solución se construye paso a paso yendo a elegir elementos (en nuestro caso, son las ganancias de combinar mallas en zonas) en la lista RCL. Esta lista está ordenada, es la parte codiciosa del algoritmo.

Un elemento se extrae aleatoriamente de las mejores posibilidades de la lista RCL, es la parte aleatoria del algoritmo. Gracias a la parte aleatoria, la fase de construcción permite por tanto variar la forma de las soluciones generadas, pero estas son de buena calidad ya que la elección aleatoria se realiza entre un conjunto de buenos candidatos. La investigación local se aplica a la solución factible resultante de la fase de construcción para ver si aún es posible mejorar esta solución.

Cabe señalar dos puntos:
  • el RCL se actualiza con elementos seleccionados según una heurística específica adaptada al problema considerado.
  • la elección de un elemento en el RCL para construir la solución es aleatoria.
Procedimiento de búsqueda adaptativa aleatoria codiciosa GRASP