Algoritmo genético: um estudo comparativo dos métodos de seleção aplicado a um problema de otimização de carregamento em caminhão

Facina, Abner Silveira

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

Show full item record