Please use this identifier to cite or link to this item: https://ri.ufs.br/jspui/handle/riufs/14134
Document Type: Dissertação
Title: Um estudo de transformações matemáticas em pontos de referência em algoritmos de otimização com muitos objetivos
Authors: Oliveira, Matheus Carvalho de
Issue Date: 7-Dec-2020
Advisor: Carvalho, André Britto de
Co-advisor: Delgado, Myriam Regattieri De Biase da Silva
Resumo : Problemas de Otimização de Muitos Objetivos (MaOPs, do inglês Many Objective Optimization Problems) são problemas que possuem mais de três funções objetivo a serem otimizadas. A maioria dos Algoritmos Evolutivos Multiobjetivo possui baixa escalabilidade quando o número de funções objetivo aumenta. Para enfrentar essa limitação, novas estratégias têm sido propostas. Uma delas é o uso de pontos de referência para aprimorar a capacidade de busca dos algoritmos. O NSGA-III é um algoritmo baseado em pontos de referência e vem sendo aplicado com sucesso para resolver os MaOPs. Ele usa um conjunto de pontos de referência localizados em um hiperplano normalizado o qual é igualmente inclinado a todos os eixos dos objetivos e intercepta cada eixo de forma equidistante no nível 1, 0. Apesar dos bons resultados do NSGA-III, a forma da hiper-superfície que serve de referência não é explorada de forma extensiva na literatura. Este trabalho procura propor um algoritmo capaz de explorar a relação entre os pontos de referência e a melhoria da busca em um contexto de otimização de muitos objetivos. Num primeiro momento são propostas três transformações do conjunto de pontos de referência utilizados pelo NSGA-III. Além disso, o procedimento de Adaptação Guiada por Vetor (RVEA) também é aplicado para modificar periodicamente o conjunto de pontos de referência do NSGA-III original. Num segundo momento do desenvolvimento da proposta, um novo algoritmo (K-Greedy) é apresentado, tendo como principal característica realizar as transformações nos pontos de referência de maneira autônoma, a partir de um conjunto de transformações disponíveis. Nos experimentos, avalia-se o desempenho das transformação propostas tanto de forma isolada (na primeira etapa) quanto integradas no conjunto de transformações possíveis realizadas pelo algoritmo K-Greedy (na segunda etapa do desenvolvimento). Nestes experimentos, as versões original e adaptadas do NSGA-III são confrontadas considerando-se vários problemas de benchmarking, observando a convergência e a diversidade através da análise de testes estatísticos. Os resultados mostram que as transformações, em especial aquelas realizadas de forma alternada pelo K-Greedy, são capazes de prover melhorias no NSGA-III sem deteriorar o desempenho à medida que se incrementa o número de objetivos.
Abstract: Many-Objective Optimization Problems (MaOPs) are problems that have more than three objective functions to be optimized. Most Multi-Objective Evolutionary Algorithms scale poorly when the number of objective functions increases. To face this limitation, new strategies have been proposed. One of them is the use of reference points to enhance the search of the algorithms. NSGA-III is a reference point based algorithm that has been successfully applied to solve MaOPs. It uses a set of reference points placed on a normalized hyper-plane which is equally inclined to all objective axes and intercepts at 1.0 each axis. Despite the good results of NSGA-III, the shape of the hyper-surface that supports the search is not deeply explored in the literature. This work seeks to propose an algorithm capable of exploring the relation between reference points and the improvement of the search in the optimization of many objective problems. At first, we propose three different mechanisms to transform the set of reference points used by NSGA-III. In addition, the Vector Guided Adaptation (RVEA) procedure is applied to modify periodically the original NSGA-III set of reference points. In a second stage of the development, a new algorithm (K-Greedy) is presented, whose main characteristic is to perform the transformations of the reference points autonomously from a set of available transformations. In the experiments, the performance of the proposed transformations is evaluated both, in separated way (in the first stage) and also when integrated in a pool of the K-Greedy algorithm (in the second stage). In these experiments, the original and adapted versions of the NSGA-III are confronted considering several problems of benchmarking, observing the convergence and diversity through the analysis of statistical tests. The results show that the transformations, especially those alternately carried out by K-Greedy, are able to provide improvements in the NSGA-III without deteriorating the performance when the number of objectives increases.
Keywords: Computação
Otimização matemática
Algorítmos
Many-objective optimization
Reference points
Greedy algorithm
NSGA-III
Subject CNPQ: CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO
Sponsorship: Fundação de Apoio a Pesquisa e à Inovação Tecnológica do Estado de Sergipe - FAPITEC/SE
Language: por
Institution: Universidade Federal de Sergipe
Program Affiliation: Pós-Graduação em Ciência da Computação
Citation: OLIVEIRA, Matheus Carvalho de. Um estudo de transformações matemáticas em pontos de referência em algoritmos de otimização com muitos objetivos. 2020. 71f. Dissertação (Mestrado em Ciência da Computação) - Universidade Federal de Sergipe, São Cristóvão, Sergipe, 2020.
License: Autorização para publicação no Repositório da Universidade Federal de Sergipe (RI-UFS), concedida pelo autor.
URI: https://ri.ufs.br/jspui/handle/riufs/14134
Appears in Collections:Mestrado em Ciência da Computação

Files in This Item:
File Description SizeFormat 
MATHEUS_CARVALHO_OLIVEIRA.pdf5,1 MBAdobe PDFThumbnail
View/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.