Esquemas de Selección Alternativos para Algoritmos Evolutivos Multi-Objetivo
Adriana Menchaca Méndez
|
Texto completo de la Tesis 
Video del evento 
Resumen
Muchas de las aplicaciones existentes en la ingeniería, la ciencia ó la industria requieren de la resolución de problemas de optimización que involucran varias funciones objetivo (normalmente en conflicto entre sí), las cuales deben ser optimizadas de manera simultánea (v.g., una función objetivo no puede ser mejorada sin deteriorar otra). Estos son los llamados problemas de optimización multi-objetivo (MOPs por sus siglas en inglés). Por lo anterior, cuando resolvemos MOPs no aspiramos a obtener una única solución óptima sino mas bien un conjunto de soluciones óptimas. Este conjunto es conocido como “conjunto de óptimos de Pareto” y a su imagen se le conoce como “frente de Pareto óptimo”. Aunque existen diversas técnicas de programación matemática que nos permiten resolver MOPs, éstas adolecen de varias desventajas, p.ej., la mayor parte de ellas generan una única solución en cada ejecución, tienen dificultades para lidiar con MOPs que cuentan con frentes de Pareto desconectados o que tienen varios falsos frentes de Pareto y requieren que las funciones objetivo y las restricciones se proporcionen en forma algebraica. Estas limitantes han motivado el uso de algoritmos evolutivos para resolver MOPs, dando pie a los denominados algoritmos evolutivos multi-objetivo (MOEAs por sus siglas en inglés). A pesar de las ventajas que presenta el uso de MOEAs con respecto a las técnicas de programación matemática, este tipo de algoritmos también tienen dificultades en cierto tipo de problemas. De entre dichas limitantes, quizás la más relevante es el hecho de que los MOEAs basados en jerarquización de Pareto (la técnica de selección más utilizada en los MOEAs que se han propuesto en los últimos 25 años) tienen dificultades para lidiar con MOPs que tienen muchas funciones objetivo (4 o más). Esto se debe a que el número de soluciones no dominadas crece muy rápidamente conforme aumentamos el número de funciones objetivo, lo que, en consecuencia, produce que la presión de selección se diluya a la misma velocidad. Esta limitante ha motivado un número importante de estudios, dando pie a un área que hoy se conoce como “optimización con muchas funciones objetivo”, cuyo objetivo fundamental es el diseño de mecanismos de selección que escalen adecuadamente en la presencia de 4 o más funciones objetivo. En esta tesis estudiamos diferentes mecanismos de selección que no están basados en la relación de dominancia Pareto con el objetivo de identificar sus principales desventajas y limitantes. Como resultado de este estudio, proponemos varios mecanismos de selección enfocados a la resolución de problemas de optimización con muchas funciones objetivos. Dichos mecanismos pueden ser clasificados en tres tipos: (i) los basados en el indicador de “hipervolumen”, (ii) los basados en una función de aptitud llamada “maximin” y (ii) los basados tanto en el indicador de “hipervolumen” como en la función de aptitud “maximin”. Los diferentes mecanismos de selección propuestos se incorporan a un MOEA, surgiendo así, seis nuevos algoritmos, los cuales son comparados con respecto a MOEAs representativos del estado del arte (SMS-EMOA y MOEA/D) usando problemas de prueba y medidas de desempeño estándar de la literatura especializada. Con base en los experimentos y en el análisis estadístico realizado podemos decir que todos los MOEAs propuestos son competitivos con respecto a SMS-EMOA, si consideramos solamente la calidad de las soluciones encontradas, y todos ellos son superiores a él, si consideramos el tiempo de ejecución requerido para generar dichas soluciones. Con respecto a MOEA/D, los algoritmos aquí propuestos son superiores si consideramos únicamente la calidad de las soluciones generadas, aunque resultan inferiores si consideramos el tiempo de ejecución requerido. Es importante mencionar que aunque el tiempo de ejecución de los algoritmos propuestos es mayor al requerido por el MOEA/D, éste sigue siendo aceptable para problemas con muchas funciones objetivo. Finalmente, cabe destacar que los MOEAs propuestos en esta tesis no requieren de información adicional a diferencia, por ejemplo, de MOEA/D o de los MOEAs basados en el indicador R2, que requieren de un conjunto de pesos convexos bien distribuidos, o de los MOEAs basados en el indicador Δp que requieren de un conjunto de referencia el cual idealmente debiera ser el “frente de Pareto óptimo”
Abstract
Many of the existing applications in engineering, science or industry, require of the solution of problems involving several (normally conflicting) objective functions, which must be simultaneously optimized (i.e., an objective function cannot be improved without worsening another one). These are the so-called multi-objective optimization problems (MOPs). Thus, when solving MOPs, we don’t aim to obtain a single optimum solution, but a set of them. Such set is known as the “Pareto optimal set” and its image is known as “Pareto optimal front.” Although a variety of mathematical programming techniques are available for solving MOPs, they have several disadvantages, e.g., most of them generate a single solution per run, have difficulties to deal with MOPs having disconnected Pareto fronts or with multi-frontal MOPs, and they require that both the objective functions and the constraints are provided in algebraic form. These limitations have motivated the use of evolutionary algorithms for solving MOPs, giving rise to the so-called multi-objective evolutionary algorithms (MOEAs). In spite of the advantages that MOEAs have with respect to mathematical programming techniques, they also present difficulties in certain types of problems. From such limitations, perhaps the most relevant is the fact that MOEAs based on Pareto ranking (the most common selection technique adopted by the MOEAs that have been proposed in the last 25 years) have difficulties to deal with MOPs having many objective functions (4 or more). This problem arises because the number of nondominated solutions grows very quickly as we increase the number of objective functions which, in consequence, dilutes the selection pressure at the same rate. This limitation has motivated an important number of studies, giving rise to an area called “many-objective optimization”, whose main goal is to design selection mechanisms that can properly scale in the presence of 4 or more objective functions. In this thesis, we study different selection mechanisms that are not based on the Pareto dominance relation, with the aim of identifying their main disadvantages and limitations. As a result of this study, we propose several selection mechanisms focused on the solution of many-objective optimization problems. Such mechanisms can be classified in three types: (i) those based on the “hypervolume” indicator, (ii) those based on a fitness function called “maximin” and (iii) those based both on the “hypervolume” indicator and the “maximin” fitness function. The proposed selection mechanisms are incorporated into a MOEA, giving rise to six new algorithms, which are compared with respect to MOEAs that are representative of the state-of-the-art (SMS-EMOA and MOEA/D) using standard test problems and performance measures taken from the specialized literature. Based on our experiments and on our statistical analysis of results, we conclude that all the proposed MOEAs are competitive with respect to SMS-EMOA, if we only consider the quality of the solutions found, and all of them are superior to SMS-EMOA if we consider the execution time required to generate such solutions. With respect to MOEA/D, all the algorithms proposed here are superior if we only consider the quality of the solutions obtained, although they are all inferior to MOEA/D if we consider the required execution time. It is worth noticing, however, that, although the execution time required by the algorithms proposed here is higher than the time required by MOEA/D, such an execution time remains affordable for solving many-objective optimization problems. Finally, it is worth indicating that the MOEAs proposed in this thesis do not require any additional information, unlike, for example, MOEA/D or MOEAs based on the R2 indicator, which require a set of well-distributed convex weights, or MOEAs based on the Δp indicator, which require of a reference set which, ideally, should be the “Pareto optimal front.”
