No2Art05

114

I+D Computación, Vol. 1, No. 2, Noviembre 2002

Predicción del Desempeño de Algoritmos Exactos y Heurísticos:
un Enfoque Estadístico*
Joaquín Pérez O.1, Rodolfo A. Pazos R.1, Juan Frausto S.2, David Romero3 y Laura Cruz R.4
1
Centro Nacional de Investigación y Desarrollo Tecnológico
2
ITESM, Campus Morelos
3
Instituto de Matemáticas UNAM
4
Instituto Tecnológico de Cd. Madero
{jperez,pazos}@sd-cenidet.com.mx, jfrausto@campus.mor.itesm.mx,
david@matcuer.unam.mx, lcruz@avantel.net

Abstract.– Traditionally algorithms are compared through the theoretical analysis of their
performance, from which it is concluded that one outperforms the other. In contrast, the method
presented in this paper statistically evaluates and characterizes the algorithms using functions that
relate performancewith problem size, in order to define dominance regions. This method generates
first a representative sample of the algorithms performance, then using a simplified regression analysis
determines performance functions, which are finally incorporated into an algorithm selection
mechanism. For testing purposes, a set of randomly generated instances of the database distribution
problem was solved usingan exact algorithm (Branch & Bound) and a heuristic algorithm (Simulated
Annealing). Experimental results show that problem size affects differently both algorithms, in such a
way that there exist regions where one algorithm is more efficient than the other, and therefore it is
possible to determine analytically the most adequate algorithm to solve a problem instance depending
on its size.
Keywords: heuristic optimization, statistical tests, algorithm selection.

1. INTRODUCCIÓN
ste trabajo suma esfuerzos dirigidos hacia la automatización del diseño de la distribución de bases
de datos mediante la utilización del modelo matemático de distribución descrito en la sección 2.1.
Aunque se sabe que el diseño de la distribución afecta directamente el desempeño global de los
sistemasdistribuidos, la complejidad de este problema ha frenado el desarrollo de metodologías y
herramientas de apoyo al diseño.

E

En la solución del problema de la distribución de datos y de otros problemas difíciles de
optimización combinatoria, se han utilizado algoritmos exactos y heurísticos. Los primeros han sido
ampliamente estudiados y se consideran prácticos para ejemplares pequeños [14], mientras quelos
segundos son considerados prometedores para ejemplares de grandes magnitudes [6, 19, 21, 22]. Para
obtener lo mejor de ambos, se requiere conocer analíticamente para qué tamaño de problema conviene
utilizar un algoritmo exacto y para cuál, un heurístico. Sin embargo, la falta de metodologías
matemáticas para predecir el desempeño de estos algoritmos dificulta la evaluación de los mismos y laselección del algoritmo más adecuado para un ejemplar dado [15].
*

Proyecto apoyado parcialmente por COSNET, clave 643.01-P.
Artículo recibido el 24 de noviembre de 2001.
ISSN 1665-238X

Pérez et al.: Predicción del Desempeño de Algoritmos Exactos y Heurísticos: un Enfoque Estadístico

115

El estudio teórico del desempeño de los algoritmos heurísticos basado en el análisis de los casos
medio ypeor, 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 [11]. 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 analizados con rigurosos métodos estadísticos [7].
En particular, estudios experimentales que comparen algoritmos exactos y heurísticos son
escasos y de utilidad práctica limitada. El trabajo más completo y actualizado es el presentado por
Hoos y Stutzle en [8], el cual se enfoca al análisis de algunos de los...