Um algoritmo genético para otimização do processo de perfuração de placas de circuito impresso

Página do item simplificado
dc.contributor.advisorAmorim, Cláudio Alves de
dc.contributor.authorMachado, Bartira de Oliveira Sena
dc.contributor.refereeSantos, Tricia Souto
dc.contributor.refereeCeledon, Julian Hermogenes Quezada
dc.date.accessioned2024-09-17T12:35:26Z
dc.date.available2024-09-17T12:35:26Z
dc.date.issued2011-09-30
dc.description.abstractEste trabalho tem por fim apresentar uma solução aproximada do problema do caixeiro viajante com o intuito de otimizar o processo de perfuração de placas de circuito impresso pela redução do comprimento da rota a ser percorrida pela broca. Para tal, foi elaborado um algoritmo genético híbrido combinando heurísticas de construção (Heurística de Savings) e otimização de rotas (RemoveSharp e LocalOpt) a uma variação do operador de crossover Edge Recombination e um operador de mutação (Shuffling). Este trabalho inclui, ainda, as análises da importância da variabilidade genética na população de um algoritmo genético e dos efeitos da preservação das “subrotas comuns” a dois cromossomos no operador Edge Recombination. Para efeito de teste e validação do algoritmo elaborado, foram utilizadas as instâncias d198, a228 e pcb442 da TSPLIB que representam modelos de placas de circuito impresso. Os resultados obtidos foram comparados com outros algoritmos presentes na literatura comprovando a eficiência do algoritmo implementado, com uma variação de até 3,4% da solução ótima para cada uma das instâncias.
dc.description.abstract2The aim of this work is to present an approximate solution to the traveling salesman problem in order to optimize the process of drilling printed circuit boards by reducing the length of the route to be covered by the drill. To this end, a hybrid genetic algorithm was developed combining construction heuristics (Savings Heuristic) and route optimization (RemoveSharp and LocalOpt) with a variation of the Edge Recombination crossover operator and a mutation operator (Shuffling). This work also includes analysis of the importance of genetic variability in the population of a genetic algorithm and the effects of preserving the “common subroutes” of two chromosomes in the Edge Recombination operator. In order to test and validate the algorithm, TSPLIB instances d198, a228 and pcb442, which represent printed circuit board models, were used. The results obtained were compared with other algorithms in the literature, proving the efficiency of the implemented algorithm, with a variation of up to 3.4% of the optimal solution for each of the instances.
dc.format.mimetypeapplication/pdf
dc.identifier.citationMACHADO, Bartira de Oliveira Sena. Um algoritmo genético para otimização do processo de perfuração de placas de circuito impresso. Orientador: Claudio Alves de Amorim. 2011. 70 f. Trabalho de conclusão de curso - (Bacharelado em Sistemas de Informação), Deprtamento de Ciências Exatas e da Terra, Campus I, Universidade do Estado da Bahia, Salvador, 2011.
dc.identifier.urihttps://saberaberto.uneb.br/handle/20.500.11896/6225
dc.language.isopor
dc.publisherUniversidade do Estado da Bahia
dc.publisher.programGraduação
dc.rightsinfo:eu-repo/semantics/openAccess
dc.rights.urihttp://creativecommons.org/licenses/by/3.0/br/
dc.rights2Attribution 3.0 Brazilen
dc.subject.keywordsPlacas de circuito impresso
dc.subject.keywordsProblema do caixeiro viajante
dc.subject.keywordsAlgoritmos genéticos
dc.titleUm algoritmo genético para otimização do processo de perfuração de placas de circuito impresso
dc.title.alternativeA genetic algorithm for optimizing the printed circuit board drilling process
dc.typeinfo:eu-repo/semantics/bachelorThesis
Arquivos
Pacote Original
Agora exibindo 1 - 1 de 1
Imagem de Miniatura
Nome:
Um algoritmo genético para otimização_Bartira Machado.pdf
Tamanho:
1.02 MB
Formato:
Adobe Portable Document Format
Descrição:
Baixar
Licença do Pacote
Agora exibindo 1 - 1 de 1
Imagem de Miniatura
Nome:
license.txt
Tamanho:
462 B
Formato:
Item-specific license agreed upon to submission
Descrição:
Baixar
Coleções
Bacharelado em Sistemas de Informação - DCET1