Metaheuristics for multi-objective optimization: design, analysis, and applications
Juan José Durillo · Dialnet (Universidad de la Rioja) · 2011
Esta tesis doctoral se centra en el diseno, analisis y evaluacion de tecnicas metaheuristicas para resolver problemas de optimizacion 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 apropiados para el diseno de este tipo de tecnicas, 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 optimizacion. Cada una de estas nuevas tecnicas ha sido evaluada y comparada con respecto a algoritmos de referencia del campo de optimizacion multi-objetivo, siguiendo un conjunto de pasos que son considerados como buenas practicas de investigacion con metaheuristicas (seleccion de un conjunto de problemas de prueba representativos, aplicacion de indicadores de calidad y validacion estadistica). Las tecnicas propuestas son: MOCell, un algoritmo genetico (genetic algorithm) celular (una subclase dentro de los geneticos); CellDE un celular hibridizado con evolucion diferencial (otro tipo de metaheuristica); SMPSO, un algoritmo basado en inteligencia colectiva (swarm intelligent); AbYSS, una tecnica basada en busqueda dispersa (scatter search); ssNSGA-ll, una version de estado estacionario (otra subclase dentro de los geneticos) del algoritmo mas conocido en optimizacion multi-objetivo, NSGA-II; pMOEA/D, una variante paralela de MOEA/D, una propuesta reciente que ha mostrado un rendimiento excelente en un gran numero de problemas; y finalmente, varias extensiones paralelas tambien para NSGA-II. Los ingredientes de mayor exito para el desarrollo de estas propuestas han sido fundamentalmente dos: por un lado, la inclusion de un archivo externo con las mejores soluciones encontradas ademas de un mecanismo para explotar la informacion del mismo (dependiente de cada tipo particular de tecnica), y por otro lado, la aplicacion de paralelismo. Dichas propuestas, ademas de varios algoritmos del estado del arte, se han evaluado teniendo en cuenta dos criterios: escalabilidad (comportamiento cuando el tamano del problema aumenta) y velocidad (esfuerzo requerido para obtener una solucion satisfactoria). En terminos de escalabilidad, MOCell y SMPSO han mostrado un rendimiento bastante competitivo, siendo las tecnicas que mejor escalan en un conjunto amplio de problemas de prueba. En terminos de velocidad, ademas de estos dos algoritmos, AbYSS ha mostrado ser una buena alternativa para afrontar un problema de optimizacion con garantias de encontrar una solucion satisfactoria de manera rapida en un gran numero 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 ingenieria del software y que se conoce como NRP. Este consiste en optimizar la planificacion de productos software. Los otros dos problemas pertenecen al campo de las telecomunicaciones: AFP, consistente en localizacion y configuracion de antenas de comunicacion, y, por otro lado, la optimizacion de un protocolo de difusion 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 metodo de referencia. Finalmente, en el caso del ultimo problema, SMPSO tambien ha mostrado un comportamiento sobresaliente en comparacion con otros algoritmos con los que se ha comparado.