Please use this identifier to cite or link to this item:
https://repositorio.ufu.br/handle/123456789/36044
ORCID: | http://orcid.org/0000-0002-5874-5676 |
Document type: | Tese |
Access type: | Acesso Aberto |
Title: | Indicadores de convergência e diversidade em algoritmos evolutivos para otimização multiobjetivo |
Alternate title (s): | Convergence and diversity indicators of evolutionary algorithms for multiobjective optimization |
Author: | Carvalho, Luiz Carlos Felix |
First Advisor: | Fernandes, Márcia Aparecida |
First member of the Committee: | Gabriel, Paulo Henrique Ribeiro |
Second member of the Committee: | Martins, Luiz Gustavo Almeida |
Third member of the Committee: | Soares, Anderson da Silva |
Fourth member of the Committee: | Sanches, Danilo Sipoli |
Summary: | A convergência de Algoritmos Evolutivos Multiobjetivo (AEMO's) é um tema que não tem na literatura o devido retorno se comparado à importância que possui, porém é possível que esse fato esteja mudando. A relevância é destacada pois a convergência está diretamente ligada à capacidade de um AEMO obter a solução de um problema. Os estudos atuais utilizam indicadores para observar características no conjunto de soluções não dominadas do algoritmo, de modo a analisar determinado aspecto, auxiliando no estudo da convergência. Este trabalho propõe dois indicadores, Taxa de Concentração (Concentration Rate, CR) e Taxa de Diversidade (Diversity Rate, DR), para analisar características comportamentais e determinar um ponto de parada para AEMO's, além de um indicador que pode ser utilizado para determinar o ponto de convergência de um AEMO, Indicador de Estabilidade no Espaço de Soluções (Stability in Solution Space, S3). Para realizar os experimentos, dois AEMO's foram propostos, Algoritmo de Estimativa de Distribuição Simples (Simple Estimation of Distribution Algorithm, SEDA) e Algoritmo de Estimativa de Distribuição Simples com Inteligência de Enxame (Simple Estimation of Distribution Algorithm with Swarm Intelligence, SEDASI), para tratar o problema Job Shop Flexível. Os experimentos realizados, que contemplaram os AEMO's e indicadores propostos e da literatura, foram realizados com o problema Job Shop Flexível e com o benchmark ZDT. Os resultados mostraram a efetividade dos indicadores em apresentar as características a que se propõe e em auxiliar um processo para determinar o ponto de parada e de convergência de AEMO's, com resultados competitivos com os de métodos conhecidos da literatura. |
Abstract: | The convergence of Multiobjective Evolutionary Algorithms (MOEA’s) is an important area in the study of this type algorithm, all the same, it is a topic that is currently not adequately represented in the literature, but this fact seems to be a changing one. This relevant importance is highlighted, as convergence is directly linked to the ability of an MOEA to obtain a solution to a problem. Current studies use indicators to observe characteristics in the set of non-dominated solutions of the algorithm, in order to analyze a certain aspect, which aids in the study of convergence. This work proposes two indicators, Concentration Rate (CR) and Diversity Rate (DR), to analyze behavioral characteristics and determine a stopping criteria for MOEA's, in addition to an indicator that can be used to determine the convergence point of a MOEA - Indicator of Stability in Solution Space (S3). To perform the necessary experiments, two MOEA's were proposed, the Simple Estimation of Distribution Algorithm (SEDA) and the Simple Estimation of Distribution Algorithm with Swarm Intelligence (SEDASI), to deal with the Flexible Job Shop Problem. The experiments, which included the MOEA's along with the proposed indicators, as well as those of the literature, were performed with the Flexible Job Shop Problem and the benchmark ZDT. The results showed the effectiveness of the indicators in presenting the proposed characteristics, while assisting in a process that determines the stopping and convergence point of MOEA's, with results that are competitive with those of methods already established in the literature. |
Keywords: | Convergência Convergence Diversidade Diversity Otimização multiobjetivo Multiobjective optimization Algoritmos evolutivos multiobjetivo Multiobjective evolutionary algorithms Ponto de parada Stopping criteria Detecção de convergência Convergence detection Otimização por Enxame de Partículas Particle Swarm Optimization Otimização por Enxame de Partículas com Diversidade Particle Swarm Optimization with Diversity Algoritmos de Estimativa de Distribuição Estimation of Distribution Algorithms Indicadores Indicators Hipervolume Hypervolume Problema Job Shop Flexível Flexible Job Shop Problem Computação Computation |
Area (s) of CNPq: | CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO::METODOLOGIA E TECNICAS DA COMPUTACAO |
Subject: | Ciência da Computação Inteligência artificial Algorítmos computacionais |
Language: | por |
Country: | Brasil |
Publisher: | Universidade Federal de Uberlândia |
Program: | Programa de Pós-graduação em Ciência da Computação |
Quote: | CARVALHO, Luiz Carlos Felix. Indicadores de convergência e diversidade em algoritmos evolutivos para otimização multiobjetivo. 2021. 134 f. Tese (Doutorado em Ciência da Computação) - Universidade Federal de Uberlândia, Uberlândia, 2022. DOI http://doi.org/10.14393/ufu.te.2021.511. |
Document identifier: | http://doi.org/10.14393/ufu.te.2021.511 |
URI: | https://repositorio.ufu.br/handle/123456789/36044 |
Date of defense: | 2-Sep-2021 |
Appears in Collections: | TESE - Ciência da Computação |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
IndicadoresConvergenciaDiversidade.pdf | 2.9 MB | Adobe PDF | View/Open |
This item is licensed under a Creative Commons License