Metaheurística - Algorítmo Genético na resolução do problema do caixeiro viajante

07/06/2008

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 »

  1. 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!

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

  3. Gustavo said,

    Outubro 9, 2008 @ 14:44

    Só pra constar.. Esté é um problema NP-Árduo e não NP-Completo

  4. Bia said,

    Março 18, 2009 @ 11:21

    Então é pra isso que você pediu o código que eu criei????!!!
    Sem comentários!!!!!

  5. Tulio Faria said,

    Março 18, 2009 @ 11:30

    Kkkk… Essa Bia… (a Bia é uma amiga meio “lesada”)…

  6. 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,

  7. Douglas Guerra said,

    Junho 25, 2009 @ 10:42

    Valeu d+ muito boa sua analise de algoritmo.
    continue assim garoto!

  8. Marco Antônio said,

    Abril 11, 2010 @ 17:01

    Bacana Túlio,

    seu blog é interessante e muito útil!

  9. Welington said,

    Abril 20, 2010 @ 00:25

    Tulio, vc tem essa ou uma implementacao parecida com essa no MATLAB?

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

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

RSS feed for comments on this post · URI do TrackBack

Deixe seu comentário