Algoritmo de GRASP

ALGORITMO DE GRASP
GRASP es una técnica de los años 80 que tiene como objetivo resolver problemas difíciles en el campo de la optimización combinatoria. Esta técnica dirige la mayor parte de suesfuerzo a construir soluciones de alta calidad que son posteriormente procesadas para obtener otras aún mejores.
Los algoritmos GRASP son algoritmos de tipo iterativo en los que cada iteración incluyeuna fase de construcción de una solución y otra de pos procesamiento en la cual se optimiza la solución generada en la primera fase.
Se puede establecer una analogía con el problema de laProgramación Lineal, donde primero se construye una solución factible y después se aplica el algoritmo Simplex. Sin embargo, en GRASP se le da bastante importancia a la calidad de la solución generadainicialmente.
La estructura básica de un algoritmo GRASP es la siguiente:
Mientras no se satisfaga el criterio de parada
1. Construir una solución greedy aleatoria
2. Aplicar una técnica de búsqueda local ala solución greedy aleatoria obtenida en el paso anterior (para mejorarla)
3. Actualizar la mejor solución encontrada
Se puede extender este algoritmo si se le añade un operador de mutación(mecanismo de generación de vecinos) al procedimiento GRASP básico:
Mientras no se satisfaga el criterio de parada
Solución = Solución greedy aleatoria
Repetir L veces
Solución = Búsqueda local(Solución)
Actualizar la mejor solución (si corresponde)
Solución = Mutación(Solución)
Algoritmo greedy
Como algoritmo greedy se puede utilizar una versión simplificada del algoritmo de Batchelor y Wilkins.Como centros de los agrupamientos se escogerán patrones del conjunto de entrenamiento de forma que el patrón escogido en cada momento sea el más alejado a los centroides ya fijados (siendo ladistancia a un conjunto de centroides el mínimo de las distancias a cada centroide). Obviamente, el primer centroide ha de escogerse de forma aleatoria.

Mecanismo de generación de soluciones greedy...