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 escolhida e trocadas
Aleatória se Melhora (Random, only improving) - umas poucas cidades são escolhidas aleatóriamente 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 amutação aleatória normal seja executada
Nenhuma (None) - sem mutação

Exemplo

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

Defeito conhecido: Se você está usando versões antigas do Java no Netscape, por favor aperte o botão "Change View" antes de fazer qualquer coisa pois em caso contrário alguns gráficos não responderão.

Isto é um applet, porém seu navegador não suporta Java. Se você quer ver os applets, por favor verifique os requisitos do navegador.

(c) Marek Obitko, 1998