Metaheurística - Algorítmo Genético na resolução do problema do caixeiro viajante
Olá pessoal,
essa semana apresentei na faculdade mais um trabalho interessante. Era sobre chegar a uma solução razoável para o problema do caixeiro viajante.
O problema do caixeiro viajante é um dos problemas chamados de NP-Completo, cujo a complexidade é dada como grande.
O problema consiste em um caixeiro viajante que tem N cidades a visitar, todas as cidades possuem ligação entre si e quer-se descobrir a melhor ordem de visita das cidades voltando ao ponto inicial, com a menor distância e sem passar mais de uma vez por cidade.
Achar a solução para esse problema com poucas cidades não é tão dificil, por exemplo, com 4 cidades, há a possibilidade de 4! soluções, ou seja, 24 soluções. A medida que aumentamos o número de cidades inviabilizamos o uso de força bruta (testar todas as possibilidades) pelo o fato do número de soluções aumentar.
O algoritmo genético se espelha na natureza para resolver um determinado problema. Assim sendo, no problema do caixeiro viajante, temos uma população composta por soluções aleatórias para o problema. Desta soluções, pegamos uma porcentagem das melhores e as usamos para gerar as demais. E podemos também fazer algumas mutações para evitar da população ser formada somente por clones
.
Na solução do problema feita em Java por mim, eu tenho uma população de 10 soluções geradas aleatoriamente. A cada evolução eu ordeno essas soluções deixando os melhores primeiro. Eu determinei uma taxa de mortalidade de 50%, ou seja, vou pegar os 5 piores e substituir pelo cruzamento dos 5 melhores. Esse cruzamento também é aleatório, sendo que escolho duas soluções pai de forma aleatória, tento copiar seus “genes”, e ao final completo o que não foi possível ser copiado com “genes” aleatórios (mutação). Na implementação, as distâncias entre cidades é dada por uma matriz de adjacência de 8×8 (8 cidades).
O código completo do Algorítmo Genético implementado em Java.
A implementação não garante uma solução ótima, mas tende a ser uma solução razoável na maioria das vezes.
Bom é isso, até a próxima pessoal!
11 Comentários »
RSS feed for comments on this post · URI do TrackBack
Este site é escrito por Tulio Faria, analista de sistemas, apaixonado por web, jogos e por qualquer cacareco tecnológico.
taiar said,
Junho 7, 2008 @ 17:55
em aeds3, na ufmg, quase todos os problemas caem em NP-completos…
eh legal estudar a força bruta com processos paralelos mas, realmente, heurísticas deixam alguns problemas quase 40 vezes mais rápidos!
Iradilson said,
Agosto 19, 2008 @ 20:49
Estou cursando a disciplina de AG aqui na UFRN na pós de eng elétrica. a utilização de heurísticas em algumas aplicações de antenas inteligentes resolve muitos problemas (que em sua grande maioria são NP-completos)
muito bom o código em java
vlw
Gustavo said,
Outubro 9, 2008 @ 14:44
Só pra constar.. Esté é um problema NP-Árduo e não NP-Completo
Bia said,
Março 18, 2009 @ 11:21
Então é pra isso que você pediu o código que eu criei????!!!
Sem comentários!!!!!
Tulio Faria said,
Março 18, 2009 @ 11:30
Kkkk… Essa Bia… (a Bia é uma amiga meio “lesada”)…
Bruno Novais said,
Junho 12, 2009 @ 16:08
Tulio, você tem alguma implementação para o problema do caixeiro
viajante, usando a força bruta?? Estou querendo, pesquisei, e falaram q há uma forma de resolver pela busca em profundidade, mas estou meio perdido..
Att,
Douglas Guerra said,
Junho 25, 2009 @ 10:42
Valeu d+ muito boa sua analise de algoritmo.
continue assim garoto!
Marco Antônio said,
Abril 11, 2010 @ 17:01
Bacana Túlio,
seu blog é interessante e muito útil!
Welington said,
Abril 20, 2010 @ 00:25
Tulio, vc tem essa ou uma implementacao parecida com essa no MATLAB?
Rubens trigueiro de carvalho said,
Maio 6, 2010 @ 12:21
tulio, qual tipo de seleção voce usou do
algortimo genetico, existe varios tipos
seleção por roleta, seleção por classificação etc.
Emerson Ribeiro said,
Setembro 12, 2011 @ 20:11
Boa noite …
Se eu quisesse fixar a primeira cidade, fazendo com que a mutação só acontecesse a partir da segunda cidade, qual parte do código eu iria ter que alterar …
Muito obrigado