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.