Diseño de una nueva función de escalarización usando programación genética

Diseño de una nueva función de escalarización usando programación genética

Amín Vanya Bernabé Rodríguez
 

Texto completo de la Tesis     

 


Resumen

Una gran variedad de problemas del mundo real pueden ser modelados como problemas en los que es necesario optimizar de forma simultánea dos o más funciones objetivo, las cuales se encuentran normalmente en conflicto entre sí. Éstos se conocen como Problemas de Optimización Multiobjetivo (POMs) y se han desarrollado distintas técnicas para su solución. En particular, los Algoritmos Evolutivos Multi-objetivo (AEMOs) han sido ampliamente utilizados para este fin. Se han propuesto diferentes tipos de AEMOs para la solución de POMs. Uno de los más utilizados es el basado en optimalidad de Pareto, el cual clasifica las soluciones con base en el número de individuos que la dominan. Sin embargo, existe evidencia experimental que indica que los algoritmos basados en este criterio deterioran su desempeño conforme se aumenta el número de objetivos. Esto ha motivado el desarrollo de otros enfoques, tales como los algoritmos basados en indicadores y los basados en descomposición. Los métodos de descomposición y algunos de los basados en indicadores utilizan funciones de escalarización. Una función de escalarización es un tipo de función matemática que permite transformar un POM en varios problemas mono-objetivo, adoptando pesos para definir diferentes direcciones de búsqueda. Dos de las principales ventajas de estas funciones son su facilidad de implementación y la posibilidad de incorporar información sobre las preferencias del usuario en el proceso de solución. Si bien existen en la literatura diversas funciones de escalarización, todas ellas han sido propuestas por humanos.

En esta tesis, proponemos el uso de programación genética para generar nuevas funciones de escalarización de forma automática. Existen estudios que muestran que el desempeño de los AEMOs basados en funciones de escalarización depende directamente de la función utilizada, por lo que consideramos relevante el proponer nuevas funciones de escalarización. Mediante la implementación propuesta en esta tesis pudimos producir nuevas funciones de escalarización, de las cuales elegimos dos (F4A y F4B) para realizar una validación experimental. Para fines de dicho estudio, utilizamos la heurística MOMBI-II como nuestro AEMO base, adoptando un conjunto de problemas de prueba estándar y comparando resultados mediante el uso de tres indicadores de desempeño: el hipervolumen, la energía-s y la cobertura de conjuntos. Los resultados obtenidos indican que la función F4A logra un desempeño similar al de la función ASF, que es la utilizada por defecto en MOMBIII. Por otro lado, la función F4B logra un mejor desempeño en la mayoría de los problemas de prueba en comparación con ASF. De esta forma, consideramos que la implementación propuesta es una forma válida de generar nuevas funciones de escalarización que sean competitivas con respecto a funciones utilizadas en el área.

 

Abstract

A great variety of real-world problems can be modelled as problems in which it is necessary to simultaneously optimize two or more objective functions, which are normally in conflict with each other. These are known as Multi-objective Optimization Problems (MOPs) and different techniques have been developed to solve them. Particularly, Multi-objective Evolutionary Algorithms (MOEAs) have been widely used for this sake. Different types of MOEAs have been proposed to solve MOPs. One of the most commonly used is the one based on Pareto optimality, which classifies solutions based on the number of individuals that dominate it. However, there is experimental evidence indicating that algorithms based on this criterion deteriorate their performance as the number of objectives increases. This has motivated the development of other approaches, such as algorithms based on performance indicators and on decomposition. Algorithms based on decomposition, as well as some indicator-based approaches rely on the use of scalarizing functions. A scalarizing function is a mathematical function that allows to transform a MOP into several single-objective problems, using weights to define different search directions. Two of the main advantages of scalarizing functions are their ease of implementation and their possibility to incorporate information about the user’s preferences during the search process. Although a variety of scalarizing functions are available in the literature, all of them have been proposed by humans.

In this thesis, genetic programming is proposed to automatically generate new scalarizing functions. There are studies indicating that the performance of MOEAs based on scalarizing functions directly depends on the adopted function. Thus, it is relevant to propose new scalarizing functions. Through the implementation proposed in this thesis, we were able to produce new scalarizing functions, from which two were selected (F4A and F4B) to perform an experimental validation. For the purposes of this study, we used MOMBI-II as our baseline MOEA, and we adopted a set of standard test problems, comparing results through the use of three performance indicators: hypervolume, s-energy and coverage of two sets. The obtained results indicate that F4A has a similar performance to that of the scalarizing function ASF, which is the one adopted by default in MOMBI-II. On the other hand, the function F4B has a better performance in most of the test problems as compared to ASF. This way, we consider that the proposed implementation is a valid way of generating new scalarizing functions that are competitive with respect to other functions adopted in the area.