Sr Sr Aja

Predicción del Desempeño de Algoritmos Exactos y Heurísticos: un Enfoque
Estadístico
Joaquín Pérez O.1,2, Rodolfo A. Pazos R.1, David Romero3, Laura Cruz R.4
1

Centro Nacional de Investigación y Desarrollo Tecnológico
2
Instituto de Investigaciones Eléctricas
3
Instituto de Matemáticas, UNAM
4
Instituto Tecnológico de Cd. Madero
E-mail: jperez@iie.org.mx, pazos@sd-cenidet.com.mx,david@matcuer.unam.mx,
lcruzr@avantel.net

Resumen
El método clásico para comparar algoritmos heurísticos, utiliza pruebas estadísticas muy
conocidas para relacionar significativamente el desempeño empírico de los algoritmos y concluye
en que uno de ellos es el mejor. Sin embargo no es posible saber sistemáticamente cómo se
comportan los algoritmos para diferentes tamaños del problema. Encontraste, el método
presentado en este artículo, evalúa y caracteriza estadísticamente los algoritmos mediante
funciones que relacionan el desempeño con el tamaño del problema. Este método primero genera
una muestra representativa del comportamiento de los algoritmos, posteriormente mediante
análisis de regresión, determina las funciones de desempeño, las que incorpora finalmente a un
mecanismode selección de algoritmos. Para realizar las pruebas se resolvió un conjunto aleatorio
de ejemplares del problema del diseño de la distribución de bases de datos con un algoritmo
exacto (Ramificación y Acotamiento) y un algoritmo heurístico (Recocido Simulado). Los
resultados de la experimentación muestran que el tamaño del problema afecta de manera diferente
a ambos algoritmos formandoregiones donde cada uno es más eficiente que el otro y que es
factible determinar analíticamente el algoritmo más adecuado para resolver un ejemplar del
problema en función de su tamaño.
1. Introducción
Este trabajo suma esfuerzos dirigidos hacia la automatización del diseño de la distribución
de una base de datos mediante la utilización del modelo FURD, el cual optimiza el diseño de lafragmentación vertical, ubicación y migración dinámica de datos. Aunque se sabe que el diseño
de la distribución afecta directamente el desempeño global de los sistemas distribuidos, la
complejidad de este problema ha frenado el desarrollo de metodologías y herramientas de apoyo
al diseño.
En la solución del problema de la distribución de datos y de otros problemas difíciles de
optimizacióncombinatoria, se han utilizado algoritmos exactos y heurísticos. Los primeros han
sido ampliamente estudiados y se consideran prácticos para ejemplares pequeños [1], mientras
que los segundos son considerados prometedores para ejemplares de grandes magnitudes [2, 3, 4,
5, 6]. Para obtener lo mejor de ambos, se requiere conocer analíticamente para qué tamaño de

problema conviene utilizar un algoritmoexacto y para cuál, un heurístico. Sin embargo, la falta
de metodologías matemáticas para predecir el desempeño de estos algoritmos, particularmente de
los heurísticos, dificulta la evaluación de los mismos y la selección del algoritmo más adecuado
para un ejemplar dado [7, 8, 9].
El estudio teórico del desempeño de los algoritmos heurísticos, basado en el análisis de
los casos medio y peor,con frecuencia es difícil de realizar. Además, debido a que describe el
comportamiento de los algoritmos en el límite, no ayuda a decidir qué tan bien se comportan los
algoritmos con ejemplares específicos [8]. Por otro lado, el análisis experimental sí es adecuado
para ejemplares específicos y es ampliamente reportado en publicaciones científicas. Sin
embargo, se utiliza muy informalmente, noreúne estándares mínimos de reproducción y sólo
ocasionalmente se reportan resultados obtenidos con rigurosos métodos estadísticos [10, 11, 12].
En [8, 9] se discuten los métodos estadísticos más aceptados para evaluar empíricamente a
las heurísticas: la prueba de signo, la prueba de Wilcoxon, la prueba de Friedman, la distribución
de Weibull y la función de utilidad. El proceso general...