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

Carregando...
Imagem de Miniatura
Data
2011-09-30
Título da Revista
ISSN da Revista
Título de Volume
Editor
Universidade do Estado da Bahia
Resumo

Este 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.


Descrição
Palavras-chave
Citação
MACHADO, 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.
Palavras-chave