Solving permutation problems with estimation of distribution algorithms and extensions thereof

Résumé

La tesis está dedicada al estudio y resolución de problemas de optimizacióncombinatoria basadas en permutaciones. Dichos problemas se caracterizan por el grannumero de posibles soluciones que pueden tomar: n!. Como consecuencia, la mayoríade los metodos de optimización exactos no son efectivos a la hora de resolverproblemas de este tipo. En este sentido, la comunidad científicia ha propuesto un grannúmero de métodos heurísticos y metaheurísticos para resolverlos.A lo largo del documento se desarrollan tres lineas de investigación diferenciadas quetienen como eje fundamental proponer avances en la resolución de los problemas depermutaciones. Una primera linea se encuadra en desarrollar algoritmos de estimaciónde distribuciones. La gran mayoría de este tipo de algoritmos no implementan modelosprobabilísticos eficaces para modelar permutaciones. En este sentido, se han estudiadolos modelos probabilísticos de Mallows, Generalized Mallows y Plackett-Luce, que, ala vista de los experimentos, suponen un paso adelante respecto a los algoritmosexistentes. La segunda linea de investigación, aborda los problemas de permutacionesdesde el ámbito de la búsqueda local y análisis de fitness landscapes. En particular, setoma el problema de ordenación lineal como caso de estudio, y extraemoscaracterísticas del problema, que permiten hacer una búsqueda más eficiente. Porúltimo, la tercera linea de investigación profundiza en la descomposición de la funciónasociada al problema en subfunciones elementales. Dicha descomposición permiteconocer mejor la estructura del problema, y en nuestro caso, multiobjectivizar elproblema reduciendo así su complejidad y facilitando su optimización.(No rebasar en extensión el presente recuadro)