4.5 Greedy Randomized Adaptive Search (GRASP)

GRASP es un método de multi-inicio (multi-start) o iterativo en donde cada iteración tiene dos fases: (i) construcción y (ii) búsqueda local (ver tabla 4.8).

**Tabla 4.8:** Algoritmo de Búsqueda GRASP.
$\begin{table} \begin{tabbing} 123\=123\=123\= \kill \textbf{procedimiento} GRASP... ... Soluci\a'{o}n) \\ \textbf{return} Mejor Soluci\a'{o}n \end{tabbing}\end{table}$

En la fase de construcción se encuentra una solución factible cuya vecindad es investigada hasta llegar a un mínimo local.

**Tabla 4.9:** Algoritmo de Greedy Randomized Construction
$\begin{table} \begin{tabbing} 123\=123\=123\= \kill \textbf{procedimiento} Greed... ...entales $c(e) \forall e \in C$ \\ \textbf{return} $s$ \end{tabbing}\end{table}$

Sea el conjunto candidato (

), todos los elementos que se pueden incorporar a la solución parcial que se está construyendo sin que se pierda la factibilidad.

La selección del elemento a incorporar se determina mediante una evaluación greedy de todos los elementos candidatos (e.g., incremento en la función de costo al aumentar algún elemento).

Esta evaluación crea una lista de candidados restringida (RCL) formada por los mejores elementos (i.e., los que incrementen menos la función de costo).

Esta lista puede estar restringida en cuanto a la cantidad de elementos (cardinalidad) o en cuanto a la calidad de los elementos.

La calidad se puede restringir de acuerdo la siguiente cota: $c(e) \in \{c^{min},c^{min} + \alpha(c^{max} - c^{min})\}$

Con $\alpha=0$ se vuelve un algoritmo completamente greedy, mientras que con $\alpha=1$ se vuelve una estrategia aleatoria.

$\alpha$ sirve para establecer un balance entre costo computacional y calidad de las soluciones.

El elemento que se incorpora en la construcción de la solución, se selecciona aleatoriamente dentro de RCL.

Una vez incorporado se actualiza la lista de candidados y se re-evaluan los costos incrementales.

El algoritmo de búsqueda local puede ser con el mejor candidato (best-improvement) o el primer candidato (first-improvement) que mejore la solución actual.

Algunas extensiones se ocupan principalmente por como controlar los posibles valores de $\alpha$ .

También se han hecho extensiones para no seleccionar el elemento de RCL aleatoriamente, sino siguiendo ciertas preferencias de acuerdo al lugar que ocupan.

Por otro lado se han hecho combinaciones o mejoras usando path relinking, pero esto lo veremos más adelante.