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

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.



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



prev             next


(c) Marek Obitko, 1998
Versão em Português do Brasil (c) Hermelindo Pinheiro Manoel
- Terms of use