Resumen de Metaheuristics for multi-objective optimization: design, analysis, and applications
Esta tesis doctoral se centra en el diseño, análisis y evaluación de técnicas metaheurísticas para resolver problemas de optimización con varios objetivos contrapuestos, a los que se conoce frecuentemente como problemas multi-objetivo. Se ha realizado un estudio de distintos mecanismos que pueden ser considerados como "ingredientes" apropiados para el diseño de este tipo de técnicas, y se han identificado aquellos con mayor importancia de acuerdo a su aplicabilidad y complejidad. Utilizando dichos ingredientes, esta tesis doctoral propone siete nuevos algoritmos de optimización. Cada una de estas nuevas técnicas ha sido evaluada y comparada con respecto a algoritmos de referencia del campo de optimización multi-objetivo, siguiendo un conjunto de pasos que son considerados como "buenas prácticas" de investigación con metaheurísticas (selección de un conjunto de problemas de prueba representativos, aplicación de indicadores de calidad y validación estadística).
Las técnicas propuestas son: MOCell, un algoritmo genético (genetic algorithm) celular (una subclase dentro de los genéticos); CellDE un celular híbridizado con evolución diferencial (otro tipo de metaheurística); SMPSO, un algoritmo basado en inteligencia colectiva (swarm intelligent); AbYSS, una técnica basada en búsqueda dispersa (scatter search); ssNSGA-ll, una versión de estado estacionario (otra subclase dentro de los genéticos) del algoritmo más conocido en optimización multi-objetivo, NSGA-II; pMOEA/D, una variante paralela de MOEA/D, una propuesta reciente que ha mostrado un rendimiento excelente en un gran número de problemas; y finalmente, varias extensiones paralelas también para NSGA-II. Los ingredientes de mayor éxito para el desarrollo de estas propuestas han sido fundamentalmente dos: por un lado, la inclusión de un archivo externo con las mejores soluciones encontradas además de un mecanismo para explotar la información del mismo (dependiente de cada tipo particular de técnica), y por otro lado, la aplicación de paralelismo.
Dichas propuestas, además de varios algoritmos del estado del arte, se han evaluado teniendo en cuenta dos criterios: escalabilidad (comportamiento cuando el tamaño del problema aumenta) y velocidad (esfuerzo requerido para obtener una solución satisfactoria). En términos de escalabilidad, MOCell y SMPSO han mostrado un rendimiento bastante competitivo, siendo las técnicas que mejor escalan en un conjunto amplio de problemas de prueba. En términos de velocidad, además de estos dos algoritmos, AbYSS ha mostrado ser una buena alternativa para afrontar un problema de optimización con garantías de encontrar una solución satisfactoria de manera rápida en un gran número de casos.
Finalmente, para el evaluar el comportamiento de nuestros algoritmos y validar las observaciones y conclusiones obtenidas sobre los problemas de prueba elegidos, se resuelven tres problemas reales. Un problema que pertenece al dominio de la ingeniería del software y que se conoce como NRP. Éste consiste en optimizar la planificación de productos software. Los otros dos problemas pertenecen al campo de las telecomunicaciones: AFP, consistente en localización y configuración de antenas de comunicación, y, por otro lado, la optimización de un protocolo de difusión en MANETs. En el primero de los problemas, MOCell ha obtenido soluciones de mejor calidad que varios de los algoritmos de referencia. En el caso de AFP, hemos evaluado AbYSS, que ha mostrado su efectividad frente a PAES, otro método de referencia. Finalmente, en el caso del último problema, SMPSO también ha mostrado un comportamiento sobresaliente en comparación con otros algoritmos con los que se ha comparado.
