Búsqueda Tabú Introducción Es una metaheur´istica presentada por Fred Glover. Utiliza memoria adaptativa y exploración inteligente. Hereda de Búsqueda Local. Implementa mecanismos de diversi?cación.
Búsqueda Tabú Memoria Adaptativa y exploración inteligente Búsqueda Tabú para los problemas de Agrupamiento y de Zonificación Arnaldo P´rez Casta˜o Memoria Adaptativa Representa su capacidad para recordar la evolución de la Búsqueda. Se logra a trav´s del uso de estructuras de datos como la lista Tabú y la Memoria de Frecuencia. Exploración inteligente Se basa en la información recogida durante la Búsqueda. Se utiliza esta información para tomar decisiones.
Búsqueda Tabú Codificación y Vecindad Solución codificada como par (elementos,centros). Vecindad obtenida intercambiando cada elemento con cada centro. Teniendo la solución s = ((e1 , …, en-k ), (c1 , …, ck )) implica ((c1 , …, en-k ), (e1 , …, ck )) ? N(s)
Búsqueda Tabú Programación objetivo Punto de referencia z * = min fk (s ), ?k ? {1, …r }, s ? S
Búsqueda Tabú PSET (Pareto Set) Componente encargado de actualizar el Frente Pareto obtenido por el algoritmo. Chequea que nuevas soluciones sean no dominadas.
Problema de Agrupamiento Definición Un Agrupamiento es una partición de n objetos en k grupos de manera que objetos en un mismo grupo tengan la mayor similitud posible y objetos en grupos distintos posean la mayor disimilitud. Para encontrar soluciones suelen optimizarse una combinación de las siguientes funciones: Diametro Inter-clase Prom. Intra-clase Intra-clase
Problema de Zonificación Aparece en el siglo XIX para separar las ´reas industriales de las residenciales. Pertenece al campo de estudios urbanos. Encuentra aplicaciones en diferentes esferas como el arte, el dise˜o de interiores, la arquitectura, la plani?cación territorial.
Es un caso especial de agrupamiento en el que su evaluación se realiza teniendo en cuenta un criterio de homogeneidad en los grupos. Un objeto para este problema es un AGB. Definición Un Area Geoestatica Basica (AGB) es un par (posición,variables), donde posición es representada por un par (x, y ) indicando la posición espacial del area y variables es una lista de valores para alguna de las variables demograficas consideradas en el problema que involucra esta AGB.
Se toman en cuenta varias funciones objetivo: Función Intra-Clase que se describe como: min k i=1 d(ci , e) ?e ? e(ci ) Función de Homogeneidad que se describe como: min k i=1 |V (ci ) – k * V * (ci )|
Problema de Zonificación Estrategia Se calcula la distancia inter-clase. Se calcula la homogeneidad. Se gestionan las nuevas soluciones utilizando PSET.
Medidas de evaluación Medidas externas que se basan en la partición optima que es conocida a priori. RandIndex: indica el porciento de decisiones correctas que se tomaron. Jaccard: indica el grado de solapamiento entre dos conjuntos.
Resultados Agrupamiento clasico 236.46 230.33 201.71 192.15 191.73 89.84 134.94 309.40 309.47 310.70 0.83 0.84 0.70 0.70 0.70 0.83 0.84 0.65 0.65 0.65 Tabla: Resultados obtenidos para el conjunto de datos Corazon en 15 iteraciones y 3 clases.
Resultados Agrupamiento clasico
Resultados Agrupamiento clasico Diametro 840.10 835.11 835.04 1269.13 Prom.Intra-clase 424.09 424.80 425.19 345.52 Rand 0.72 0.72 0.72 0.34 Jaccard 0.45 0.45 0.45 0.33 Tabla: Resultados obtenidos para el conjunto de datos Vinos en 15 iteraciones y 3 clases.
Resultados Zonificación Hom 11847.379 11004.949 10636.740 10466.369 10451.237 10388.293 10435.767 10429.598 10386.362 10427.542 10403.743 10384.556 11870.684 Comp 36.382 46.265 46.267 46.488 47.993 49.566 49.384 49.389 49.657 49.433 49.451 50.391 32.710 Tabla: Resultados para la Zonificación en 15 iteraciones y k = 5.
Resultados Zonificación
Comparaciones Comparación entre VNS y BT Búsqueda Tabú para los problemas de Agrupamiento y VNS BT de Zonificación Hom 55262 37111 73647 94983 Comp 3256.4 4419.6 2162.4 1217.2 Hom 11847.379 11004.949 10636.740 10466.369 Comp 36.382 46.265 46.267 46.488 10451.237 10388.293 10435.767 10429.598 10386.362 10427.542 10403.743 10384.556 11870.684 47.993 49.566 49.384 49.389 49.657 49.433 49.451 50.391 32.710
Comparaciones Comparación entre BTII y BT para el conjunto Corazon. BTII BT Media Desv. Sol. Media Desv. Sol. Di´metro Prom. Intra-clase 217.51 157.09 157.09 32.27 3 210.47 230.87 19.14 97.78 5
Conclusiones La efectividad de cada uno de los algoritmos propuestos fue comprobada mediante un proceso de experimentación con datos de la vida real obteniendo resultados satisfactorios Las comparaciones realizadas para el problema de Zonificación arrojaron resultados superiores para la Búsqueda Tabú. Los resultados alcanzados son exitosos y pueden servir como base para futuras investigaciones y proyectos en el campo de la optimización.
1. El criterio de aspiración en la Búsqueda tabu tiene el rol de desactivar la prohibición tabu, ¿qué papel juega este criterio en el algoritmo propuesto? R/ El criterio de aspiración en el enfoque tiene el rol de presionar la Búsqueda hacia la frontera Pareto, creando un conjunto de posibles soluciones no dominadas, y no permitir que soluciones que han sido visitadas sean nuevamente visitadas.
¿Qué mecanismo emplea el enfoque para mantener una buena diversidad de la frontera Pareto? R/ La función de agregación de los objetivos con coeficientes de pesos variables propuesta, conjuntamente con los mecanismos de memoria a corto y largo plazo implementados en el espacio de las variables de decisión permiten diversificar la Búsqueda adecuadamente.
3. ¿Qué importancia tiene agrupar tomando en consideración diferentes matrices de disimilaridad? R/ En ocasiones podemos tener datos demograficos como, sexo, edad, educación, etc, y otros datos como en el caso de Zonificación que son datos espaciales y deseamos agrupaciones homogeneas con respectos a dichos datos. En estos casos es mas conveniente tener los datos por separados para un mejor estudio de los mismos porque los que analizan el problema pueden estar interesado en agrupaciones homogeneas con respecto a las variables espaciales mientras desea conocer las variaciones con respecto a una o mas variables demograficas.