Numerical Cruncher



Clustering


GRASP
[Greedy Randomized Adaptive Search Procedure]



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.

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.

La estructura básica de un algoritmo GRASP es la siguiente:

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:

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.

Mecanismo de generación de soluciones greedy aleatorias

En la construcción de soluciones greedy aleatorias se utiliza una lista de candidatos [RCL: Restricted Candidate List] en la que se incluyen los mejores aspirantes a formar parte de la solución. De esa lista se escoge un candidato aleatoriamente.

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.

Técnica de búsqueda local

La estrategia de búsqueda local se utiliza para mejorar la solución obtenida mediante en el mecanismo de generación de soluciones greedy aleatorias. Mientras la solución no sea un óptimo local, se encuentra una solución mejor entre los vecinos de la solución actual.

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.

Operador de mutación (algoritmo GRASP extendido)

En el algoritmo GRASP extendido es necesario considerar un operador de mutación que se aplicará sobre la solución actual cada vez que finalice la ejecución del algoritmo de búsqueda local.

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.