XII. Problema do Caixeiro Viajante

Sobre o Problema

O problema do caixeiro viajante já foi mencionado em capítulos anteriores. Relembrando, são dadas cidades e as distâncias entre elas. O caixeiro viajante tem que visitar todas elas, mas não quer viajar demais. A tarefa consiste em encontrar a seqüência de cidades que faz com que a distância percorrida seja a menor possível. Em outras palavras, o problema é achar a rota mínima Hamiltoniana num gráfico de N nós.


Implementação

Foi usada uma população de 16 cromossomas. Para codificá-los foi utilizada Codificação por Permutação - você pode encontrar no capítulo sobre codificação, como codificar a permutação das cidades para o Problema do Caixeiro Viajante. O problema é selecionado completando o gráfico (isto é, cada nó é conectado ao outro) com distâncias euclidianas. Note que depois de adicionar ou excluir uma cidade é necessário criar novos cromossomas e reiniciar completamente o algoritmo.

Você pode escolher o tipo de cruzamento e de mutação. Veja a seguir uma descrição dos seus significados:

Cruzamento

  • Ponto único - parte do primeiro pai (isto é, parte da seqüencia das cidades) é copiada e o resto das cidades é copiada na mesma seqüência do segundo pai
  • Dois pontos - duas partes do primeiro pai são copiadas e o restante (que está entre essas duas partes) é colocada na mesma ordem que estão no segundo pai
  • Nenhum - sem cruzamento, a descendência é uma cópia exata dos pais

Mutação

  • Aleatória Normal (Normal Random Mutation) - umas poucas cidades são escolhidas e trocadas
  • Aleatória se Melhora (Random, only improving) - umas poucas cidades são escolhidas aleatoriamente somente se elas melhoram a solução (isto é, aumentam a adequação)
  • Sistemática se Melhora (Systematic, only improving) - cidades são escolhidas sistematicamente e trocadas somente se melhoram a solução (aumentam a adequação)
  • Aleatória Melhorada (Random improving) - o mesmo que "Aleatória se Melhora", porém antes que a mutação aleatória normal seja executada
  • Sistemática Melhorada (Systematic improving) - o mesmo que "Sistemática se Melhora", porém antes que a mutação aleatória normal seja executada
  • Nenhuma (None) - sem mutação


Exemplo

A demonstração seguinte mostra o AG otimizado para o problema do caixeiro viajante. O botão "Change View" muda a vista de toda a população para a melhor solução e vice versa. Você pode adicionar e retirar cidades clicando no gráfico. Depois de adicionar ou excluir uma cidade, uma rota aparecerá entre elas, assim como uma nova população de cromossomas aleatórios também é criada. Repare também que estamos resolvendo o problema em um gráfico completo.
Experimente executar o AG com diferentes tipos de cruzamento e mutação e repare como o desempenho (e a velocidade - adicione mais cidades para perceber) do AG muda.