GRASP: Procedimiento de Búsqueda Adaptativa Codiciosa Aleatorizada

GRASP, o Procedimiento de Búsqueda Adaptativa Codiciosa Aleatorizada, es una metaheurística multi-arranque diseñada para resolver problemas de optimización combinatoria. Combina la construcción codiciosa de soluciones con aleatorización y búsqueda local, ofreciendo un equilibrio entre exploración y explotación del espacio de búsqueda.

Visión General

Cada iteración de GRASP consiste de dos fases principales:

1. Fase de Construcción: Una solución factible se construye codiciosamente usando decisiones aleatorizadas.
2. Fase de Búsqueda Local: La solución construida se mejora a través de un procedimiento de búsqueda local.

La mejor solución encontrada en todas las iteraciones se mantiene como resultado final.

1. Fase de Construcción

En la fase de construcción, la solución se construye un elemento a la vez. En lugar de siempre elegir el mejor elemento posible (como en algoritmos puramente codiciosos), GRASP usa una Lista de Candidatos Restringida (LCR) que incluye buenos candidatos basados en una función codiciosa. Un candidato de esta lista se selecciona al azar para ser agregado a la solución parcial.

Esto introduce diversificación en el proceso de búsqueda, permitiendo al algoritmo explorar múltiples regiones del espacio de solución.

Ejemplo de Pseudocódigo:

Inicializar solución vacía S
mientras S está incompleta:
    Evaluar todos los elementos candidatos usando una función codiciosa
    Construir LCR con los mejores candidatos (basado en umbral de calidad α)
    Seleccionar aleatoriamente un candidato de LCR
    Agregar candidato seleccionado a S

El parámetro α (alfa) controla el equilibrio entre avaricia vs. aleatoriedad:

• α = 0 → puramente codicioso
• α = 1 → puramente aleatorio

2. Fase de Búsqueda Local

Una vez que se construye una solución completa, se aplica una búsqueda local para tratar de mejorarla explorando su vecindario.

La búsqueda local continúa hasta que no se pueda encontrar una mejor solución dentro del vecindario de la solución actual (es decir, alcanza un óptimo local).

Ejemplo de Pseudocódigo:

función BúsquedaLocal(S):
    repetir:
        Encontrar el mejor vecino S' de S
        si S' es mejor que S:
            S ← S'
        sino:
            retornar S

3. Algoritmo GRASP

Marco Completo de GRASP:

función GRASP(max_iteraciones):
    mejor_solución ← ∅
    para i desde 1 hasta max_iteraciones:
        S ← ConstrucciónCodiciosAleatorizada()
        S ← BúsquedaLocal(S)
        si S es mejor que mejor_solución:
            mejor_solución ← S
    retornar mejor_solución

¿Por Qué Usar GRASP?

• Simplicidad: GRASP es relativamente fácil de implementar.
• Efectividad: Funciona bien en una amplia gama de problemas.
• Personalizable: Las estrategias de construcción y búsqueda local pueden adaptarse a problemas específicos.
• Paralelizable: Las iteraciones independientes lo hacen adecuado para computación paralela.

Aplicaciones

GRASP ha sido aplicado exitosamente a muchos problemas combinatorios, incluyendo:

• Problema del Viajante de Comercio (TSP)
• Coloreo de Grafos
• Programación de Talleres
• Cobertura de Conjuntos
• Enrutamiento de Vehículos

Ejemplo: GRASP para el Problema de Cobertura de Conjuntos

Definición del Problema

Dado un universo de elementos y una colección de subconjuntos, el objetivo es encontrar el menor número de subconjuntos cuya unión cubra todo el universo.

Estrategia de Construcción

• En cada paso, elegir un subconjunto que cubra el mayor número de elementos no cubiertos.
• Usar LCR para aleatorizar la elección.

Estrategia de Búsqueda Local

• Tratar de remover o reemplazar subconjuntos para reducir el número total de subconjuntos manteniendo la cobertura.

Referencias

• Feo, T. A., & Resende, M. G. C. (1995). Greedy randomized adaptive search procedures. Journal of Global Optimization.
• Resende, M. G. C., & Ribeiro, C. C. (2016). Optimization by GRASP. Springer.

Conclusión

GRASP es una metaheurística poderosa y adaptable que efectivamente equilibra la construcción codiciosa y búsqueda aleatorizada con mejora local. Su diseño modular la hace ideal para abordar varios problemas de optimización NP-difíciles de manera robusta y eficiente.

Si está buscando un método heurístico rápido, flexible y efectivo, GRASP es un gran punto de partida.