Los indicadores de calidad (ICs) son funciones que le asignan un valor real a un conjunto que representa una aproximación a un frente de Pareto generado por un optimizador multi-objetivo, dependiendo de propiedades de calidad específicas. En la comunidad de optimización evolutiva multi-objetivo, los ICs han sido principalmente empleados en dos maneras: (1) para la evaluación de algoritmos evolutivos multi-objetivo (AEMOs), y (2) para guiar el proceso evolutivo de AEMOs, siendo el componente principal de sus mecanismos de selección. Con respecto al primer caso, una de las líneas de investigación más importantes ha sido la búsqueda de nuevos ICs unarios que midan la convergencia hacia el frente de Pareto y que tengan la propiedad de Pareto-compatibilidad, es decir, que sus preferencias sean compatibles con la relación de dominancia de Pareto que es el criterio típicamente empleado al resolver problemas de optimización multi-objetivo (POMs). Actualmente, el indicador de hipervolumen y sus variantes son los únicos ICs unarios Pareto-compatibles. Por otra parte, los ICs han promovido el diseño de nuevos esquemas de selección que permitan a los AEMOs incrementar su presión de selección para resolver POMs que tengan más de tres funciones objetivo (los denominados problemas de optimización con muchos objetivos) y para generar aproximaciones a los frentes de Pareto con diversas distribuciones de soluciones debido a las preferencias específicas de los ICs. Recientemente, se ha enfatizado que el desempeño de algunos AEMOs del estado del arte depende de la forma del frente de Pareto del POM a resolverse. Desafortunadamente, los mecanismos de búsqueda de estos AEMOs están sobre-especializados para resolver problemas de prueba cuyos frentes de Pareto están altamente correlacionados con la forma de un simplex. En consecuencia, es necesario diseñar AEMOs cuyo desempeño sea invariante a la forma del frente de Pareto.
Esta tesis está enfocada en tratar el problema de dependencia de los AEMOs a las geometrías de los frentes de Pareto y el diseño de nuevos ICs Pareto-compatibles. Con respecto a la dependencia a la forma de los frentes, se propone el uso de múltiples mecanismos de selección basados en indicadores bajo dos esquemas principales: competición y cooperación. La idea subyacente de ambos esquemas es superar las debilidades de un mechanismo de selección basado en un indicador con las fortalezas de otros. Al combinar múltiples mecanismos de selección basados en indicadores se mostró a través de diversas propuestas que es posible generar aproximaciones a los frentes de Pareto con buenas propiedades de convergencia y diversidad, independientemente de la forma geométrica del frente, usando los esquemas competitivo y cooperativo. Por otra parte, se propuso la combinación matemática de uno o más ICs debilmente Pareto-compatibles con al menos uno que sea Pareto-compatible, dando como resultado un nuevo indicador Pareto-compatible. Esta propuesta permite incrementar el número de ICs Pareto-compatibles disponibles para ser usados tanto en la evaluación de AEMOs como en sus mecanismos de selección.
Abstract
Quality indicators (QIs) are set functions that assign a real value to a set that represents the Pareto front approximation generated by a multi-objective optimizer, depending on specific quality properties. In the evolutionary multi-objective optimization community, QIs have been mainly employed in two ways: (1) for the assessment of multi-objective evolutionary algorithms (MOEAs), and (2) to guide the evolutionary process of MOEAs, being the backbone of selection mechanisms. Concerning the former case, one of the most important research paths has been the finding of new unary QIs that measure convergence towards the Pareto front, having the Pareto-compliance property, i.e., their preferences should be compliant with the Pareto dominance relation which has been the typical optimality criterion when solving multi-objective optimization problems (MOPs). Currently, the hypervolume indicator and its variants are the only known unary QIs Pareto-compliant. On the other hand, QIs have promoted the design of new selection mechanisms that allow MOEAs to increase their selection pressure to solve MOPs having more than three objective functions (the so-called many-objective optimization problems) and to generate Pareto front approximations with different distribution properties due to the inner preferenes of QIs. Some studies have stressed out that the performance of some state-of-the-art MOEAs depends on the Pareto front shape of the MOPs being tackled. Unfortunately, the search mechanisms of these MOEAs are overspecialized to solve benchmark problems with Pareto front shapes highly correlated with the shape of a simplex. In consequence, it is necessary to design MOEAs whose performance is invariant to the Pareto front shape.
In this thesis, we focus on tackling the Pareto front shape dependence of MOEAs and the design of new Pareto-compliant QIs. Regarding the shape dependence, we propose to use multiple indicator-based selection mechanisms under competitive and cooperative schemes. The underlying idea of both schemes is to overcome the weaknesses of an indicator-based selection mechanism with the strengths of the others. When combining multiple indicator-based selection mechanisms, we showed through different proposals that it is possible to generate Pareto front approximations having good convergence and diversity, regardless of the geometrical shape, using both the competitive and the cooperative approaches. On the other hand, we proposed the mathematical combination of one or more weakly Pareto-compliant QIs with at least one Pareto-compliant indicator to produce new Pareto-compliant QIs. This approach allows to increase the number of Pareto-compliant indicators to be used for the assessment of MOEAs or in their selection mechanisms.
