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

Résumé

Maximice o minimice una función objetivo definida sobre un espacio discreto. Dado que la mayoría dedichos problemas no pueden ser resueltos mediante una búsqueda exhaustiva, su resolución se aproximafrecuentemente mediante algoritmos heurísticos. Sin embargo, no existe ningún algoritmo que secomporte mejor que el resto de algoritmos para resolver todas las instancias de cualquier problema. Porello, el objetivo ideal es, dado una instancia de un problema, saber cuál es el algoritmo cuya resoluciónes más eficiente. Las dos líneas principales de investigación para lograr dicho objetivo son estudiar lasdefiniciones 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 Distribucionesdiseñados para resolver problemas basados en permutaciones. La principal motivación ha sido seguirprogresando en este campo para comprender mejor las relaciones entre los Problemas de OptimizaciónCombinatoria y los algoritmos de optimización.