Use este identificador para citar ou linkar para este item:
http://repositorio.utfpr.edu.br/jspui/handle/1/27552
Título: | Implementando em FPGA um algoritmo genético para a busca de soluções para o problema do caixeiro viajante |
Título(s) alternativo(s): | Implementing in FPGA a genetic algorithm to search for solutions to the traveling salesman problem |
Autor(es): | Guerra, André Luiz Lemos |
Orientador(es): | Barros, André Macário |
Palavras-chave: | Algorítmos genéticos Caixeiros-viajantes Otimização combinatória Arranjos de lógica programável em campo Genetic algorithms Traveling sales personnel Combinatorial optimization Field programmable gate arrays |
Data do documento: | 18-Mai-2021 |
Editor: | Universidade Tecnológica Federal do Paraná |
Câmpus: | Pato Branco |
Citação: | GUERRA, André Luiz Lemos. Implementando em FPGA um algoritmo genético para a busca de soluções para o problema do caixeiro viajante. 2021. Trabalho de Conclusão de Curso (Engenharia de Computação) - Universidade Tecnológica Federal do Paraná (UTFPR), Pato Branco, 2021. |
Resumo: | O Problema do Caixeiro Viajante que busca encontrar a rota de menor custo entre diversas cidades de um conjunto, passando por cada uma delas apenas uma vez e retornando à cidade inicial. Existem diversas aplicações para este problema tais como planejamento de processos, manufatura celular, gerenciamento de rotas, estrutura de matrizes e até mesmo montagem de placas de circuito impresso. Encontrar uma solução exata é custoso em tempo e processamento, para isso existem métodos aproximativos. Contudo algumas aplicações do PCV tem uma necessidade de respostas em questão de microssegundos. Nessas situações o paralelismo é uma forte opção para aceleração. Dentro dos métodos aproximativos a meta-heurística Algoritmo Genético se destaca, por sua capacidade de paralelização. Neste trabalho foi implementada uma arquitetura configurável em FPGA, que representa a meta-heurística algoritmo genético, capaz de buscar soluções para o problema do caixeiro viajante. A implementação ocorreu em um microcontrolador combinado a blocos lógicos reconfiguráveis e foi realizada em um kit FPGA Spartan 3E. Por fim, foram realizados experimentos que comprovaram um crescimento linear do tempo de execução conforme se aumentou o número de cidades do problema. |
Abstract: | The Traveling Salesman Problem that seeks to find the lowest cost route between several cities in a set, going through each one only once and returning to the starting city. There are several applications for this problem such as process planning, cell manufacturing, route management, matrix structure and even the assembly of printed circuit boards. Finding an exact solution is costly in time and processing, for which there are approximate methods. However, some PCV applications have a microsecond response requirement. In these cases, parallelism is a strong option for acceleration. Within the approximate methods, the metaheuristic Genetic Algorithm stands out for its parallelization capacity. In this work, a reconfigurable architecture in FPGA was implemented, which represents the meta-heuristic genetic algorithm, capable of seeking solutions to the traveling salesman problem. The implementation took place in a microcontroller combined with reconfigurable logic blocks and was carried out in a kit FPGA Spartan 3E. Finally, experiments were conducted which proved a linear increase runtime as the number of cities in the problem increased. |
URI: | http://repositorio.utfpr.edu.br/jspui/handle/1/27552 |
Aparece nas coleções: | PB - Engenharia de Computação |
Arquivos associados a este item:
Arquivo | Descrição | Tamanho | Formato | |
---|---|---|---|---|
implementandofpgaalgoritmogenetico.pdf | 957,15 kB | Adobe PDF | Visualizar/Abrir |
Os itens no repositório estão protegidos por copyright, com todos os direitos reservados, salvo quando é indicado o contrário.