Problema do caixeiro utilizando ag

Disponível somente no TrabalhosFeitos
  • Páginas : 6 (1467 palavras )
  • Download(s) : 0
  • Publicado : 25 de fevereiro de 2013
Ler documento completo
Amostra do texto
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 – Brazilallanpereira@hotmail.com.br,{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 ofartificial 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 seressã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[Goldberg 1989]. O problema do caixeiro viajante é um dos problemas mais estudados na área de otimização combinatória e consiste em achar um ciclo partindo de uma cidade (origem) percorrendo todas as outras cidades em uma única vez sem retornar a qualquer uma delas [Mestria 2011]. Quando o número de cidades é pequeno a quantidade de possíveis rotas é igualmente pequena, todavia quando o número decidades é grande o caixeiro fica impossibilitado de calcular o melhor caminho a ser tomado em um intervalo de tempo adequado. Encontrar a solução para o impasse enfrentado pelo caixeiro utilizando AG é viável porque, por ser um problema de otimização combinatória, existem diversas possibilidades de solução e o AG, quando bem elaborado, é capaz de encontrar soluções de alta qualidade. O AG não garanteencontrar a solução ótima, mas uma solução efetiva em um tempo de execução menor que o tempo que seria gasto por um ser

humano para encontrar uma solução [Brasil 2008]. Portanto, este artigo trata em codificar um programa utilizando os conceitos apropriados de AG, que tenha uso simples em que o usuário faça o papel do caixeiro e, também, tenha um tempo de execução eficaz ao problema. 2.Materiais e Método

Para desenvolver o AG foi preciso encontrar uma forma de calcular a quantidade de rotas a partir do número de cidades a se visitar. Esse cálculo foi feito transformando o problema, que é de otimização combinatória em um problema de enumeração, Silveira (2000). Foi necessário, então, verificar, através de comparações, qual a menor rota para encontrar a solução desejada. Oprograma foi codificado da seguinte maneira: O usuário (caixeiro viajante) informa o número de cidades que visitará. O cálculo da quantidade de distâncias a serem informadas é feito através fórmula: ( ) , em que “n” corresponde ao número de cidades informadas pelo usuário. A partir daí o usuário deverá informar a distância de cada cidade A à cidade B, considerando que todas as cidades a se visitar...
tracking img