Trabalho de Conclusão de Curso
Análise comparativa dos algoritmos genéticos many-objective em problemas de otimização discreta
Comparative analysis of many-objective genetic algorithms in discrete optimization problems
Registro en:
MARSON, Gabriel Augusto. Análise comparativa dos algoritmos genéticos many-objective em problemas de otimização discreta. 2017. 45 f. Trabalho de Conclusão de Curso (Graduação em Ciência da Computação) - Universidade Federal de Uberlândia, Uberlândia, 2017.
Autor
Marson, Gabriel Augusto
Institución
Resumen
This research aims to show the performance of some genetic multi-goals algorithms, especially those known as many-objective, applied on a discrete problem, the knapsack problem.
In addition, a study of the evolution of genetic algorithms, wich are a non-deterministic approach to solving problems, will be written. The study will go through multi-objectives algorithms, that solve 2 or 3 objective functions, and ending in the many-objectives, which are able to solve problems with various objective functions, ie starting on 4.
It is established a comparitive performance analysis of the NSGA-II algorithms (Nondominated
Sorting Genetic Algorithm II) and SPEA2 (Strength Pareto Evolutionary Algorithm 2), considered multi-objective, and the most recent ones, categorized as many-objectives like MOEA/D (Multi-objective Evolutionary Algorithm Based on Decomposition), AEMMT (Multiobjective Evolutionary Algorithm With Many Tables) and AEMMD (Multiobjective Evolutionary Algorithm with Multiple Dominances). The comparison will take, as criteria, the execution time and other
performance metrics applied to four or more objective functions.
This work, therefore, proves a greater effectiveness of the many-objective algorithms in
detriment of multi-goals when applied to a higher amount of objective functions. It also shows that, as the complexity of the problem increases, the many-objectives algorithms perform better than SPEA2 and NSGA-II. Trabalho de Conclusão de Curso (Graduação) Esta investigação tem como objetivo mostrar o desempenho de alguns algoritmos genéticos
multi-objetivos, em especial aqueles conhecidos como many-objective, em um problema
discreto da computação, o problema da mochila.
Além disso, será apresentado um estudo da evolução dos algoritmos genéticos que é uma
abordagem não determinística para resolver problemas, passando pelos multi-objetivos,
que resolvem problemas de 2 ou 3 funções objetivo, e finalizando nos many-objectives, que
são capazes de resolver problemas com várias funções objetivo, ou seja, a partir de 4. É
feita uma avaliação comparativa de desempenho dos algoritmos NSGA-II(Nondominated
Sorting Genetic Algorithm II ) e SPEA2(Strength Pareto Evolutionary Algorithm 2 ), considerados multi-objetivos e dos mais recentes que são considerados many-objectives como
o MOEA/D(Multi-objective Evolutionary Algorithm Based on Decomposition), AEMMT
(Multiobjective Evolutionary Algorithm With Many Tables) e AEMMD(Algoritmo Evolutivo Multiobjetivo com Múltiplas Dominâncias). De acordo o tempo de execução e outras
métricas de desempenho, será feita uma avaliação comparativa entre esses algoritmos para
lidar com quatro ou mais critérios de otimização.
Este trabalho, portanto comprova uma maior eficácia dos algoritmos many-objective em
detrimento dos multi-objetivos para uma quantidade de objetivos mais elevada. Ele também mostra que, a medida que a complexidade do problema aumenta, os many-objectives
apresentam um maior desempenho do que o SPEA2 e NSGA-II.
Ítems relacionados
Mostrando ítems relacionados por Título, autor o materia.
-
Hybridizing a multi-objective simulated annealing algorithm with a multi-objective evolutionary algorithm to solve a multi-objective project scheduling problem
Yannibelli, Virginia Daniela; Amandi, Analia Adriana (Elsevier, 2012-11)In this paper, a multi-objective project scheduling problem is addressed. This problem considers two conflicting, priority optimization objectives for project managers. One of these objectives is to minimize the project ... -
Docile Object and Proposing Object: : a study on the qualities of the object and its possibilities in the creative process in Performing Arts
Della Costa, Rossana; Rossini, Élcio