Uso de análise de superfície de aptidão, seleção adaptativa de operadores e aprendizado de máquina na solução de problemas multi e com muitos objetivos

Abstract

Resumo: Muitos problemas do mundo real podem ser representados como um problema de otimização multiobjetivo ou com muitos objetivos. Tais problemas não possuem uma única solução, mas um conjunto de soluções ótimas. Essa característica faz com que o uso de Algoritmos Evolutivos Multiobjetivo (AEMOs) seja interessante para resolver esses tipos de problemas, visto que eles são capazes de aproximar o conjunto de soluções em uma execução. Os AEMOs podem ser divididos em três categorias principais: baseados em Pareto, em indicadores de qualidade ou em decomposição. Neste trabalho explorou-se o uso de algoritmo baseado em decomposição. A medida que o número de objetivos de um problema aumenta, a capacidade de busca de muitos AEMOs é deteriorada. Uma das tendências para melhorar o desempenho de AEMOs é o uso de seleção adaptativa de operadores, a qual visa escolher o melhor operador a ser utilizado em cada momento do processo de otimização. As principais técnicas de seleção adaptativa encontradas na literatura, e utilizadas nessa tese, são Probability Matching, Adaptive Pursuit e Multi-Armed Bandit. Vários fatores influenciam o desempenho da seleção adaptativa de operadores e, dentre eles, o foco dessa tese foi na recompensa atribuída a cada operador. Na literatura existem diversas formas de calcular a recompensa associada a cada operador, mas a maioria delas limita-se a utilizar apenas informações sobre o desempenho, geralmente medido pela convergência das soluções modificadas pelo operador. Nesta tese foram utilizadas métricas de análise de superfície para aprimorar a recompensa. Além disso, foram utilizadas métricas de análise de superfície de aptidão na extração de informações dos problemas. As características extraídas foram utilizadas por algoritmos de aprendizado de máquina para identificar a melhor combinação de método de seleção adaptativa de operadores e métrica de análise de superfície de aptidão para recompensa em cada instância de um problema. Diferentes tipos de problemas foram utilizados, de benchmarks bem conhecidos na literatura até problemas do mundo real. Os resultados foram encorajadores e indicam que o uso de métricas e técnicas de análise de superfície de aptidão para solucionar problemas multiobjetivo e com muitos objetivos pode ser eficiente.

Abstract: Many real-world problems can be represented as a multi or many objective problem. Such problems do not have a single solution, but a set of optimal solutions. This feature makes the use of Multi-Objective Evolutionary Algorithms (AEMOs) interesting to solve these type of problems, as they are able to approximate the set of solutions in one run. AEMOs can be divided into three main categories: Pareto-based, quality indicator or decomposition. In this work, the use of an algorithm based on decomposition was explored. As the number of objectives for a problem increases, the search ability of many AEMOs is deteriorated. One modern trends to improve the performance of AEMOs is the use of adaptive operator selection, which aims to choose the best operator to be used at each stage of the optimization process. The main selection techniques found in the literature, and used in this thesis, are Probability Matching, Adaptive Pursuit and Multi-Armed Bandit. Several factors influence the performance of adaptive operator selection and, among them, the focus of this thesis was on the reward attributed to each operator. In the literature there are several ways to calculate the reward associated with each operator, but most of them are limited to using only information about performance, usually measured by the convergence of operator-modified solutions. In this thesis, fitness landscape analysis metrics were used to improve the reward. In addition, metrics from fitness landscape analysis for feature extraction from problems were used. The extracted features were used by machine learning algorithms to identify the best combination of adaptive operator selection method and fitness landscape analysis metric as reward for each instance of a problem. Different types of problems were used, from well-known benchmarks in the literature to real-world problems. The results obtained were encouraging and indicate that the inclusion of metrics and techniques from fitness landscape analysis for solving multi and many-objective problems can be efficient.