Please use this identifier to cite or link to this item:
https://repositorio.ufu.br/handle/123456789/39783
Document type: | Trabalho de Conclusão de Curso |
Access type: | Acesso Aberto |
Title: | Algoritmo genético: um estudo comparativo dos métodos de seleção aplicado a um problema de otimização de carregamento em caminhão |
Alternate title (s): | Genetic algorithm: a comparative study of selection methods applied to a truck loading optimization problem |
Author: | Facina, Abner Silveira |
First Advisor: | Brasil, Christiane Regina Soares |
First member of the Committee: | Paula, Verônica Angélica Freitas de |
Second member of the Committee: | Soares, Alexsandro Santos |
Summary: | 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. |
Keywords: | algoritmo genético genetic algorithm Problema da mochila Knapsack problem Métodos de seleção Selection methods |
Area (s) of CNPq: | CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO::TEORIA DA COMPUTACAO::ANALISE DE ALGORITMOS E COMPLEXIDADE DE COMPUTACAO |
Language: | por |
Country: | Brasil |
Publisher: | Universidade Federal de Uberlândia |
Quote: | 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. |
URI: | https://repositorio.ufu.br/handle/123456789/39783 |
Date of defense: | 30-Nov-2023 |
Appears in Collections: | TCC - Gestão da Informação |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
AlgoritmoGenéticoUm.pdf | TCC | 1.08 MB | Adobe PDF | ![]() View/Open |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.