Contributions on theoretical aspects of estimation of distributions algorithms

Résumé

La presente tesis se centra en el estudio teórico de los algoritmos EDAs (Estimation of Distribution Algorithms), Los EDAs son algoritmos de optimización válidos tanto en espacios continuos como en discretos que pueden enmarcarse dentro de la Computación Evolutiva. Son heurísticos estocásticos basados en poblaciones de individuos, en los que cada individuo de la población codifica una posible solución del problema de optimización. Hasta el momento se ha trabajado mucho tanto en la creación de nuevos EDAs como en la aplicación de los mismos, pero este esfuerzo no ha venido acompañado de un análisis teórico de los mismos. La presente tesis quiere ser una contribución en el análisis teórico de los EDAs, aportando información sombre el modelado matemático y el comportamiento de los mismos. Este trabajo aborda los importantes cuestiones que miden el rendimiento de cualquier algoritmo de optimización: convergencia y complejidad temporal. Por un lado es importante conocer bajo qué condiciones se puede garantizar que el algoritmo alcanza una solución óptima (convergencia). Por otro lado, el número de esperado de pasos necesarios para alcanzar una solución óptima (conocido como tiempo de computo) es una importante medida de la eficiencia de un algoritmo. Relacionado con ello, en ésta tesis se estudia la relación entre el tiempo de cómputo y el tamaño del problema (complejidad temporal). Las dos herramientas matemáticas utilizadas a lo largo de ésta tesis para analizar y modelar los EDAs han sido las cadenas de Markov y los sistemas dinámicos discretos. Las principales aportaciones de ésta tesis han sido: * Construcción de un marco analítico basado en cadenas de Markov para el estudio de la convergencia de una EDA genérico. Utilizando la condición anterior se han analizado los EDAs discretos más comunes. Para que no se pueda asegurar convergencia a través de la condición se han impuesto condiciones en la