Publicação: Algoritmo genético: um estudo comparativo dos métodos de seleção aplicado a um problema de otimização de carregamento em caminhão
Carregando...
Tipo do documento
Data
Direito de acesso
Coleções
Programa
Área do conhecimento
CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO::TEORIA DA COMPUTACAO::ANALISE DE ALGORITMOS E COMPLEXIDADE DE COMPUTACAO
Título da Revista
ISSN da Revista
Título de Volume
Autores
Orientador
Coorientador
Resumo
Os algoritmos genéticos simulam a seleção natural proposta por Darwin, sendo utilizados
em várias áreas de conhecimento. Eles têm notoriedade em resolver problemas
combinatórios, tais como o cacheiro viajante e o problema da mochila. Neste trabalho
uma variante do problema da mochila é tratada com algoritmo genético, em que se busca
a melhor maneira de transportar uma combinação de produtos que não exceda o limite de
um caminhão e maximize o valor da venda (a soma do valor de todos os produtos neste
carregamento) sem que seja repetido nenhum item. Além de encontrar a melhor solução
para o problema proposto, também tem-se como objetivo secundário discutir a diferença
no desempenho do algoritmo ao se utilizar o método da seleção da roleta e o método da
seleção por torneio. O algoritmo foi codificado em Python, pois além de ser uma
linguagem amplamente utilizada também por sua eficiência de trabalhar com listas. Ao
final deste estudo, foi concluído que o algoritmo codificado com o método de seleção por
torneio é mais eficiente que o método da roleta, ratificando a literatura desta área de
pesquisa.
Abstract
Genetic algorithms simulate the natural selection proposed by Darwin, being used in
several areas of knowledge. They are famous for solving combinatorial problems, such
as the traveling salesman problem and the knapsack problem. In this work, a variant of
the knapsack problem is treated with a genetic algorithm, which seeks the best way to
transport a combination of products that does not exceed the limit of a truck and
maximizes the sales value (the sum of the price of all products in this load) without any
item being repeated. In addition to finding the best solution to the proposed problem, the
secondary objective is also to discuss the difference in the performance of the algorithm
when using the roulette wheel selection method and the tournament selection method.
The algorithm was coded in Python, as in addition to being a widely used language, it is
also highly capable of working with lists. At the end of this study, it was concluded that
the algorithm coded with the tournament selection method is more efficient than the
roulette wheel method, confirming the literature in this area of research.
Palavras-chave
algoritmo genético, genetic algorithm, Problema da mochila, Knapsack problem, Métodos de seleção, Selection methods
Citação
FACINA, Abner Silveira. Algoritmo genético: um estudo comparativo dos métodos de seleção aplicado a um problema de otimização de carregamento em caminhão. 2023. 47 f. Trabalho de Conclusão de Curso ( Graduação em Gestão da Informação) - Universidade Federal de Uberlândia, Uberlândia, 2023.