Contributions on theoretical aspects of estimation of distributions algorithms
Cristina González · Dialnet (Universidad de la Rioja) · 2006
La presente tesis se centra en el estudio teorico de los algoritmos EDAs (Estimation of Distribution Algorithms), Los EDAs son algoritmos de optimizacion validos tanto en espacios continuos como en discretos que pueden enmarcarse dentro de la Computacion Evolutiva. Son heuristicos estocasticos basados en poblaciones de individuos, en los que cada individuo de la poblacion codifica una posible solucion del problema de optimizacion. Hasta el momento se ha trabajado mucho tanto en la creacion de nuevos EDAs como en la aplicacion de los mismos, pero este esfuerzo no ha venido acompanado de un analisis teorico de los mismos. La presente tesis quiere ser una contribucion en el analisis teorico de los EDAs, aportando informacion sombre el modelado matematico y el comportamiento de los mismos. Este trabajo aborda los importantes cuestiones que miden el rendimiento de cualquier algoritmo de optimizacion: convergencia y complejidad temporal. Por un lado es importante conocer bajo que condiciones se puede garantizar que el algoritmo alcanza una solucion optima (convergencia). Por otro lado, el numero de esperado de pasos necesarios para alcanzar una solucion optima (conocido como tiempo de computo) es una importante medida de la eficiencia de un algoritmo. Relacionado con ello, en esta tesis se estudia la relacion entre el tiempo de computo y el tamano del problema (complejidad temporal). Las dos herramientas matematicas utilizadas a lo largo de esta tesis para analizar y modelar los EDAs han sido las cadenas de Markov y los sistemas dinamicos discretos. Las principales aportaciones de esta tesis han sido: * Construccion de un marco analitico basado en cadenas de Markov para el estudio de la convergencia de una EDA generico. Utilizando la condicion anterior se han analizado los EDAs discretos mas comunes. Para que no se pueda asegurar convergencia a traves de la condicion se han impuesto condiciones en la