GRASP
GRASP
GRASP
GRASP
[Greedy Randomized Adaptive Search Procedure]
El término GRASP fue introducido por Feo y Resende en 1995 como una nueva técnica
metaheurística de propósito general. 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 su esfuerzo a construir soluciones de alta calidad que son posteriormente procesadas
para obtener otras aún mejores.
Las técnicas metaheurísticas son nuevas herramientas que han sido desarrolladas en los últimos
años para la resolución de diferentes tipos de problemas que antes no habían podido ser
abordados debido a su complejidad.
Son varias las situaciones en las que resulta muy recomendable la utilización de este tipo de
algoritmo:
- Cuando no se necesita una solución óptima, sino una solución satisfactoria que oriente
sobre el comportamiento del problema.
- Suelen ser más fáciles de entender por parte de gente no experta, el entendimiento de
las heurísticas que los complejos métodos que utilizan la mayoría de las técnicas exactas.
No obstante, estas técnicas también presentan inconvenientes. Uno de los más destacados es que,
en la mayoría de los casos en los que estos algoritmos son utilizados, no se conoce el valor del
óptimo, y dado que son procedimientos en los que no se asegura la optimalidad, no se puede
tener una idea clara del nivel de calidad de la solución obtenida.
Son muchas las metaheurísticas creadas hasta el día de hoy. Unas, tienen su uso limitado a
problemas particulares, mientras que otras pueden ser aplicadas a problemas más diversos. Entre
estas últimas podríamos destacar las siguientes como las más importantes:
- Recocido simulado.
- Algoritmos genéticos.
- GRASP.
- Búsqueda Tabú
La palabra GRASP proviene de las siglas de “Greedy Randomized Adaptative Search Procedure”,
que en castellano sería algo así como: Procedimientos de Búsqueda basados en funciones
“Greedy” Aleatorizadas Adaptativas. Se trata de una metaheurística basada en un procedimiento
de búsqueda avaricioso, aleatorio y adaptativo el cual, aplicado a una amplia gama de problemas
de optimización, garantiza una buena solución, aunque no necesariamente la óptima.
GRASP es un procedimiento iterativo donde cada paso consiste en una fase de construcción y una
de mejora.
Se dice además que el procedimiento es adaptativo porque en cada iteración se actualizan los
beneficios obtenidos de añadir el elemento seleccionado a la solución parcial. Es decir, la
evaluación que se tenga de añadir un determinado elemento a la solución en la iteración j no
coincidirá necesariamente con la que se tenga en la iteración j+1.
Por otro lado, el heurístico es aleatorio porque no selecciona el mejor candidato según la función
greedy adaptada sino que, con el objeto de diversificar y no repetir soluciones en dos
construcciones diferentes, se construye una lista con los mejores candidatos de entre los que se
selecciona uno al azar.
Dado que la fase inicial no garantiza la optimalidad local respecto a la estructura de entorno en la
que se esté trabajando (notar que hay selecciones aleatorias), se aplica un procedimiento de
búsqueda local como posprocedimiento para mejorar la solución obtenida.
Al realizar el GRASP muchas iteraciones, nos está ofreciendo un muestreo del espacio de
soluciones existente.
1. Fase Constructiva:
2. Fase de Mejora:
3. Actualización:
Un procedimiento de búsqueda local parte de una solución inicial, calcula su entorno o vecindad y
escoge una nueva solución perteneciente a dicho entorno. Dicho de otro modo, realiza un
movimiento que, aplicado sobre la solución de partida, da como resultado una nueva solución que
pertenece a la vecindad de la de partida. En el GRASP, este proceso es utilizado reiteradamente:
En cada iteración el algoritmo hace un movimiento, “visitando” una nueva solución del entorno de
la solución de partida.
Los algoritmos GRASP son algoritmos de tipo iterativo en los que cada iteración incluye una fase
de construcción de una solución y otra de postprocesamiento en la cual se optimiza la solución
generada en la primera fase.
Se puede establecer una analogía con el problema de la Programació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 generada inicialmente.
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 la distancia a un conjunto de centroides el mínimo de las distancias a cada centroide).
Obviamente, el primer centroide ha de escogerse de forma aleatoria.
Un posible algoritmo greedy aleatorio consiste en utilizar como RCL la lista de los patrones más
alejados a los centroides ya escogidos. El tamaño de esta lista puede ser, por ejemplo, igual al 5%
de las muestras disponibles.
El algoritmo greedy aleatorio es análogo al algoritmo greedy clásico, teniendo en cuenta que, en
cada momento, se escoge aleatoriamente uno de los patrones más alejados al conjunto de centroides
ya establecido.
Como técnica de búsqueda local se puede emplear, por ejemplo, el conocido algoritmo de las K
medias, cuya convergencia depende de la configuración inicial de los clusters.
Una solución se representa por un vector en el cual la componente i-ésima indica el agrupamiento al
que pertenece el patrón i-ésimo. Para mutar una solución se altera cada componente del vector
solución con una probabilidad P. Como es lógico, las componentes del vector se mantendrán con
una probabilidad 1-P. Como valor de P escogeremos 0.3 para aplicar una mutación fuerte que
permita una buena exploración del espacio de búsqueda.
BIBLIOGRAFIA:
http://elvex.ugr.es/software/nc/help/spanish/nc/clustering/GRASP.html
http://www.scielo.org.co/scielo.php?script=sci_arttext&pid=S0123-21262010000200004
https://sci2s.ugr.es/sites/default/files/files/Teaching/GraduatesCourses/Algoritmica/Tema05-
Multiarranque_I-MetodosBasicos_y_G-12-13.pdf