Métodos híbridos de optimización multiobjetivo

Resumen

El presente trabajo de tesis doctoral aborda el problema de encontrar el frente óptimo de Pareto en problemas de optimización multiobjetivo. Para esto se propone un nuevo algoritmo de ramificación y poda paralelo. La principal contribución de este trabajo es la propuesta de dos nuevos algoritmos híbridos paralelos multiobjetivo de ramificación y poda para arquitecturas de memoria compartida (nombrado MBB) y memoria distribuida (nombrado DMBB). Los algoritmos propuestos presentan numerosas contribuciones que pueden ser adoptadas por otros algoritmos de este tipo. La primera contribución es un contenedor en forma de malla para almacenar el frente de Pareto, donde cada celda de la malla cubre una región de la aproximación al frente de Pareto. La segunda contribución es la integración de una cola de prioridad concurrente que permite ajustar dinámicamente la prioridad de las tareas pendientes por ejecutar permitiendo guiar la búsqueda eficientemente hacia las regiones más prometedoras. La tercera contribución es una extensión que generaliza la estructura integer-vector-matrix, llamada EIVM; esta nueva estructura permite almacenar representaciones basadas en permutaciones y la cual es apropiada para cualquier secuencia de números enteros. Los algoritmos propuestos son utilizados para encontrar las soluciones óptimas para diversas instancias de tres problemas de optimización que no han sido reportadas en la literatura. En específico para el problema de la optimización de la bisección de vértices se resolvieron 4 instancias, para el problema de rutas de vehículos se resolvieron un total de 5 instancias y para el problema de programación de tareas flexibles se resolvieron 12 instancias. Estas soluciones serán de gran utilidad para medir el desempeño de nuevos algoritmos.