Departamento de Computación

La mayoría de los problemas del mundo real involucran la optimizacion simultánea de varios objetivos (generalmente en conflicto entre sí y expresados en distintas unidades de medida). Estos problemas son llamados multiobjetivo o multicriterio (POMs). La investigacion de operaciones ha desarrollado un numero considerable de técnicas para resolver estos problemas. Sin embargo, dada la complejidad de la mayoría de los problemas de optimización multiobjetivo del mundo real (p. ej., alta dimensionalidad, discontinuidad, multimodalidad), estas técnicas presentan varias limitantes o no resultan prácticos para resolverlos. Uno de los enfoques alternativos más exitosos para resolver eficazmente estos problemas es el uso de los algoritmos evolutivos multiobjetivo (AEMO). No obstante, uno de los puntos débiles de estos algoritmos es su alto consumo de recursos computacionales, lo cual motiva, de manera natural, el uso del paralelismo. La paralelización de los AEMOs es un campo relativamente nuevo, y como consecuencia, existen pocas publicaciones al respecto. En la mayoría de estas publicaciones no se discuten detalladamente los aspectos relacionados con el desarrollo y la implementación de los AEMOs paralelos (pAEMOs). Asimismo, no se ha considerado una selección justificada de los problemas de prueba y de las métricas para evaluar tanto la eficacia como la eficiencia de los pAEMOs. En esta tesis se presenta un nuevo AEMO paralelo competitivo con respecto a los AEMOs representativos del estado del arte desde el punto de vista de la efectividad y la eficiencia. El algoritmo propuesto, denominado algoritmo genético multiobjetivo con multiples resoluciones (MRMOGA, ’Multiple Resolution Multi-Objective Genetic Algorithm’), esta basado en el modelo de islas con nodos heterogéneos y se construyó sobre un cúmulo de computadoras. El algoritmo se caracteriza por codificar las soluciones con una resolución distinta en cada isla. De esta manera se consigue dividir el espacio de búsqueda en regiones disjuntas del espacio de las variables de decisión. Para evaluar la efectividad del algoritmo propuesto se utilizaron métricas conocidas para evaluar AEMOs secuenciales, a saber: el conteo de aciertos, la distancia generacional invertida, el espaciamiento y la cobertura de conjuntos. Para evaluar la eficiencia se utilizaron las siguientes métricas conocidas en la computación paralela: aceleración, eficiencia y fracción serial. Los resultados del algoritmo propuesto se compararon con los obtenidos por una versión paralela del NSGA-II.
Con base en los resultados obtenidos podemos afirmar que el esquema de MRMOGA para dividir el espacio de búsqueda mediante distintas resoluciones mejora considerablemente la eficácia y la eficiencia de un pAEMO. Además, el algoritmo propuesto tiene una gran capacidad exploratoria ya que, con respecto al algoritmo de referencia, en todas las funciones de prueba encontró soluciones que se extienden mejor a lo largo del frente de Pareto real. Asimismo, MRMOGA demostró una capacidad inusualmente buena para resolver POMs con restricciones, incluso para aquellos problemas reconocidos por su dificultad.