Definición de pesos en MOEA/D usando arreglos de cubrimiento para resolver problemas de optimización de muchos objetivos

Abstract

Los problemas de optimización de muchos objetivos son cada día más comunes. Entre los algoritmos evolutivos utilizados para su solución, destaca el enfoque basado en descomposición con el algoritmo MOEA/D y sus variaciones. Las variaciones de MOEA/D buscan mejorar la definición de vectores de peso, la adaptación de estos en el proceso de búsqueda y la búsqueda en sí misma, modificando los operadores de selección, cruce, mutación y reemplazo, entre otros. Aunque el éxito del algoritmo depende en gran medida de qué tan bien se definan los vectores de peso al descomponer el problema, la investigación sobre el tema es escasa. Para definir los vectores de peso, en esta tesis se propone el uso de arreglos de cobertura aumentada (ACA), unos objetos matemáticos que permiten un mejor muestreo de las interacciones de los M objetivos, utilizando el menor número de vectores de peso, en función de un nivel de interacción o fuerza previamente definido por el usuario. Al comparar el método propuesto en problemas de las familias DTLZ y WFG versus la definición de vectores de peso en MOEA/D-DE (una variante de MOEA/D que usa los operadores de evolución diferencial) y los resultados obtenidos contra NSGA-III, se observó que en poblaciones pequeñas a medianas (hasta 850 soluciones) con 40 a 100 objetivos, se mejoran los resultados de los algoritmos medidos en distancia generacional invertida, lo cual se respalda con los resultados de las prueba estadística no paramétrica de Friedman y el post hoc de Holm, con reducciones significativas en el tiempo de ejecución. El uso de ACAs permite la definición de vectores de peso en tiempo no lineal (logarítmico) a medida que crece el número de objetivos. Con lo anterior, se espera que las variaciones de MOEA/D y de otros los algoritmos basados en descomposición incluyan el enfoque propuesto y, por lo tanto, mejoren los resultados reportados a la fecha en la literatura.

Many-objective optimization problems are today ever more common. Among the evolutionary algorithms used in their solution, the decomposition-based approach stands out, with MOEA/D and its variations playing major roles. MOEA/D variations seek to improve the definition of weight vectors and evolution operators - selection, crossover, mutation, and replacement. Although the success of the algorithm depends heavily on how well the weight vectors are defined in decomposing the problem, research on the topic is scarce. To better define weight vectors, this paper proposes the use of augmented covering arrays (ACAs), mathematical objects that enable a better sampling of interactions of M objectives using the least number of weight vectors, based on an interaction level, or strength, previously defined by the user. Comparing the proposed method in DTLZ and WFG problems versus traditional weight vectors definition in MOEA/D-DE and results obtained against NSGA-III, it was seen that in small to medium populations (up to 850 solutions) with 40 to 100 objectives, better results are obtained in Inverted Generational Distance supported by Friedman nonparametric and Holm post-hoc tests, with significant reductions in execution time. The use of ACAs enables weight vectors definition in nonlinear (logarithmic) time as the number of objectives grows. MOEA/D variations and decomposition-based algorithms may thus be expected to include the proposed approach and thereby improve on results in the literature.