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 Comment

  1. 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. 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. Só pra constar.. Esté é um problema NP-Árduo e não NP-Completo

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

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

  6. 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. Valeu d+ muito boa sua analise de algoritmo.
    continue assim garoto!

  8. Bacana Túlio,

    seu blog é interessante e muito útil!

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

  10. Rubens trigueiro de carvalho says:

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

Deixe uma resposta