Algoritmo genético para problema generalizado de atribuição
Data
2022-03-26
Autores
Montini, Beatriz de Barros
Título da Revista
ISSN da Revista
Título de Volume
Editor
Universidade Estadual Paulista (Unesp)
Resumo
Este trabalho aborda o Problema Generalizado de Atribuição. Visto que é um problema clássico de otimização, cujo objetivo é minimizar os custos de atribuir n tarefas a m agentes, a resolução do problema a ser estudada será pelo Algoritmo Genético. O desenvolvimento deste, consiste em construir soluções através do princípio da seleção natural e sobre os trabalhos de Mendel sobre a genética. A teoria da evolução natural consiste na ideia onde o mais apto sobreviva e este se reproduza, resultando na obtenção de uma nova geração. A resolução será testada nas instâncias de Yagiura (2021) e a implementação foi utilizando o software R, obtendo a melhor solução para as instâncias testadas.
This work addresses the Generalized Attribution Problem. Since it is a classical optimization problem, whose objective is to minimize the costs of assigning n tasks to m agents, the solution of the problem to be studied will be by the Genetic Algorithm. The development of this consists of building solutions through the principle of natural selection and on Mendel's work on genetics. The theory of natural evolution consists of the idea where the fittest survives and it reproduces, resulting in a new generation. The resolution will be tested in the instances of Yagiura (2021) and the implementation was using the R software, obtaining the best solution for the tested instances.
This work addresses the Generalized Attribution Problem. Since it is a classical optimization problem, whose objective is to minimize the costs of assigning n tasks to m agents, the solution of the problem to be studied will be by the Genetic Algorithm. The development of this consists of building solutions through the principle of natural selection and on Mendel's work on genetics. The theory of natural evolution consists of the idea where the fittest survives and it reproduces, resulting in a new generation. The resolution will be tested in the instances of Yagiura (2021) and the implementation was using the R software, obtaining the best solution for the tested instances.
Descrição
Palavras-chave
Problema generalizado de atribuição, Problema de otimização, Algoritmo genético, Generalized assignment problem, Optimization problem, Genetic algorithm