Contributions to the mathematical modeling of estimation of distribution algorithms and pseudo-boolean functions

Abstract

Maximice o minimice una función objetivo definida sobre un espacio discreto. Dado que la mayoría de dichos problemas no pueden ser resueltos mediante una búsqueda exhaustiva, su resolución se aproxima frecuentemente mediante algoritmos heurísticos. Sin embargo, no existe ningún algoritmo que se comporte mejor que el resto de algoritmos para resolver todas las instancias de cualquier problema. Por ello, el objetivo ideal es, dado una instancia de un problema, saber cuál es el algoritmo cuya resoluciones más eficiente. Las dos líneas principales de investigación para lograr dicho objetivo son estudiar las definiciones de los problemas y las posibles instancias que cada problema puede generar y el estudio delos diseños y características de los algoritmos. En esta tesis, se han tratado ambas lineas. Por un lado,hemos estudiado las funciones pseudo-Booleanas y varios problemas binarios específicos. Por otro lado,se ha presentado un modelado matemático para estudiar Algoritmos de Estimación de Distribuciones diseñados para resolver problemas basados en permutaciones. La principal motivación ha sido seguir progresando en este campo para comprender mejor las relaciones entre los Problemas de Optimización Combinatoria y los algoritmos de optimización.