Atenção: Todas as denúncias são sigilosas e sua identidade será preservada.
Os campos nome e e-mail são de preenchimento opcional
Metadados | Descrição | Idioma |
---|---|---|
Autor(es): dc.contributor | Barros, André Macário | - |
Autor(es): dc.contributor | Barros, André Macário | - |
Autor(es): dc.contributor | Casanova, Dalcimar | - |
Autor(es): dc.contributor | Barbosa, Marco Antonio de Castro | - |
Autor(es): dc.creator | Guerra, André Luiz Lemos | - |
Data de aceite: dc.date.accessioned | 2022-08-04T20:16:25Z | - |
Data de disponibilização: dc.date.available | 2022-08-04T20:16:25Z | - |
Data de envio: dc.date.issued | 2022-03-07 | - |
Data de envio: dc.date.issued | 2022-03-07 | - |
Data de envio: dc.date.issued | 2021-05-18 | - |
Fonte completa do material: dc.identifier | http://repositorio.utfpr.edu.br/jspui/handle/1/27552 | - |
Fonte: dc.identifier.uri | http://educapes.capes.gov.br/handle/capes/705855 | - |
Descrição: dc.description | 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. | - |
Descrição: dc.description | 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. | - |
Formato: dc.format | application/pdf | - |
Idioma: dc.language | pt_BR | - |
Publicador: dc.publisher | Universidade Tecnológica Federal do Paraná | - |
Publicador: dc.publisher | Pato Branco | - |
Publicador: dc.publisher | Brasil | - |
Publicador: dc.publisher | Departamento Acadêmico de Informática | - |
Publicador: dc.publisher | Engenharia de Computação | - |
Publicador: dc.publisher | UTFPR | - |
Direitos: dc.rights | openAccess | - |
Palavras-chave: dc.subject | Algorítmos genéticos | - |
Palavras-chave: dc.subject | Caixeiros-viajantes | - |
Palavras-chave: dc.subject | Otimização combinatória | - |
Palavras-chave: dc.subject | Arranjos de lógica programável em campo | - |
Palavras-chave: dc.subject | Genetic algorithms | - |
Palavras-chave: dc.subject | Traveling sales personnel | - |
Palavras-chave: dc.subject | Combinatorial optimization | - |
Palavras-chave: dc.subject | Field programmable gate arrays | - |
Palavras-chave: dc.subject | CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO | - |
Título: dc.title | Implementando em FPGA um algoritmo genético para a busca de soluções para o problema do caixeiro viajante | - |
Título: dc.title | Implementing in FPGA a genetic algorithm to search for solutions to the traveling salesman problem | - |
Tipo de arquivo: dc.type | livro digital | - |
Aparece nas coleções: | Repositorio Institucional da UTFPR - RIUT |
O Portal eduCAPES é oferecido ao usuário, condicionado à aceitação dos termos, condições e avisos contidos aqui e sem modificações. A CAPES poderá modificar o conteúdo ou formato deste site ou acabar com a sua operação ou suas ferramentas a seu critério único e sem aviso prévio. Ao acessar este portal, você, usuário pessoa física ou jurídica, se declara compreender e aceitar as condições aqui estabelecidas, da seguinte forma: