Problema do caixeiro utilizando ag

Problema do Caixeiro Viajante utilizando Algoritmo Genético
Allan Pereira Silva¹, Gustavo Rodrigues Coelho¹, Ludimila da Bela Cruz¹, Lourdes Mattos Brasil¹
1

Laboratório de Informática em Saúde (LIS), Laboratórios de Engenharia e Inovação (LEI) da Faculdade Gama (FGA) – Universidade de Brasília (UnB) Área Especial 2 Lote 14 Setor Central, Gama – 72.405-610 – Brasília – DF – Brazil [e-mail],{gust.rod.coelho, lbelacruz, lmbrasil}@gmail.com

Abstract.This paper proposes a solution based on the use of Genetic Algorithm – GA - to traveling salesman problem. The traveling salesman problem is a combinatorial optimization problem, where the salesman must visit “n” cities every trip and find the shortest route that passes through all cities. AG is a technique of artificial intelligence based on Charles Darwin’s theory of evolution of species and is used, for example, in problems with a large set of possible solutions. Resumo.Neste artigo, propõe-se uma solução a partir da utilização de Algoritmo Genético – AG - para o problema do caixeiro viajante. A problemática do caixeiro viajante trata-se de uma otimização combinatória, em que o caixeiro precisa visitar “n” cidades percorrendo a menor rota que passe por todas as cidades. AG é uma técnica da inteligência artificial baseada na teoria de Charles Darwin de evolução das espécies e é utilizada, por exemplo, em problemas com um grande conjunto de possíveis soluções. 1. Introdução Algoritmos Genéticos – AG’s - são baseados na teoria da evolução das espécies de Charles Darwin (1859), que afirma que os seres são capazes de se adaptar, evoluir e se reproduzir no meio em que vivem. São utilizados em diversas áreas como engenharia, saúde e ciência da computação para resolver desde problemas com um grande conjunto de soluções, que exigem uma busca inteligente, até problemas em que um desfecho específico é necessário. De maneira simplificada algoritmo genético é um método interativo de busca e otimização