Pages

Resolvendo o problema do caixeiro viajante com Algoritmos Genéticos

Sunday, March 8, 2009

Olá Pessoal,

Como eu tinha citado no post anterior, sobre algoritmos genéticos, desenvolvi um pequeno simulador que soluciona o problema clássico NP-completo do caixeiro viajante (Traveling Salesman Problem - TSP) usando algoritmos genéticos (GA). Neste problema, o objetivo é encontrar a rota de menor distância entre N diferentes cidades. O caminho que o caixeiro faz é denominado de tour.


Se um caixeiro inicia do ponto A, e se as distâncias entre cada par de pontos é conhecida, qual é o menor caminho que visita todos os ponto e retorna ao ponto A ?


Para testar todas possibilidades de rotas para N cidades seria necessário calcular a permutação N!. Tudo bem, para um rota com 3 a 5 cidades, é fácil de calcular. Agora imagine um tour com 30 cidades! Seria necessário calcular a distância total de cada uma dessas 2.65 X 1032 diferentes rotas, assumindo um trilhão de cálculos por segundo, o que levaria aproximadamente 252,333,390,232,297 anos para achar a menor rota. Adicione mais uma cidade a esta rota e o tempo aumentaria em um fator exponencial elevado a 31. Fica claro, que é uma solução impossível calculando manualmente.

Algoritmos genéticos podem ser usados para solucionar este problema em menor tempo. Embora não haja garantias de encontrar a melhor solução, ela pode achar uma solução satisfatória bem próxima da ótima para um tour de 100 cidades em menos de 1 minuto. Há algums passos básicos para solucionar o problema do caixeiro viajante usando algoritmos genéticos, vejamos cada um deles a seguir:
  • Primeiro, um conjunto aleatório de rotas são criadas, inicializando assim a população. Este algoritmo cria uma população inicial 'gulosa', o qual dá preferência em montar conexões entre as cidades que estão mais próximas uma da outra.
  • Segundo, escolha as 2 melhores rotas (menores) da população para o cruzamento (crossover) e combine-os para gerar 2 novas rotas filhas. Grandes chances destas novas rotas filhas serem melhores que os seus pais.
  • Em raros casos, as rotas filhas sofrem o processo de mutação. Isto é feito para prevenir que todas as rotas da população sejam idênticas
  • As novas rotas filhas são inseridas na população substituindo no lugar de 2 rotas das maiores existentes. O tamanho da população se mantém constante.
  • As novas rotas filhas são repetidamente criadas até atingirem um critério de parada desejado (melhor rota).

Os dois maiores problemas encontrados usando Algoritmos Genéticos para solucionar o problema do caixeiro viajante são a codificação/representação da rota e o algoritmo de cruzamento (crossover) utilizado para combinar dois indíviduos (rotas) para gerar novos filhos.

No algoritmo genético padrão, cada cromossomo é codificado através de uma sequência de números ou bits e o cruzamento (crossover) é realizado, selecionando um ponto de corte aleatório da sequência de genes dos cromossomos-pai e após a troca de cada número na sequência a partir do ponto selecionado. Neste exemplo, o ponto de corte está entre o 3rde 4th item da lista. Para criar um filho, todos os items da sequência de genes a partir do ponto de corte são trocados entre os cromossomos pais.

Parent1F A B | E C G D
Parent2D E A | C G B F
Child1 F A B | C G B F
Child1 D E A | E C G D

A maior dificuldade do problema do caixeiro viajante é que toda cidade só pode ser usada apenas uma vez dentro de uma rota (tour). Se considerarmos que as letras apresentadas no exemplo acima representam cidades, então as rotas filhas criadas pela operação de crossover seriam consideradas inválidas. Já que Child1 vai para cidades F e B duas vezes, e nunca passa pela cidades D ou E.

A codificação das rotas não pode ser simplesmente a lista de cidades na ordem em que elas são percorridas. Outros métodos de codificação também foram criados para solucionar o problema do crossover. Embora estes métodos não criem rota inválidas, eles não levam em conta de que a rota "A B C D E F G" é a mesma rota "G F E D C B A". Para solucionar o problema do crossover, precisamos de um algoritmo mais sofisticado.

Minha solução consiste de criar links em ambas direções para cada rota. No nosso exemplo anterior, Parent1 poderia ser armazenado como:

CityFirst Connection Second Connection
AFB
BAE
CEG
DGF
EBC
FDA
GCD


A operação de crossover é mais complicada do que apenas simplesmente combinar 2 sequências. O cruzamento deve considerar todos os links existentes nas rotas pais e colocá-los nas rotas filhas. Logo, para o Child 1, são utilizados os links existentes no Parent 2 e depois no Parent 1. Para o Child 2, alterna-se entre Parent 2 e Parent 1 selecionando um diferente conjunto de links. Para ambos os filhos, há uma chane de o link criado torne a rota inválida, onde em vez de ter uma rota completa para todas as cidades, há vários trechos desconectados. Neste caso, tais links devem ser rejeitados. Para completar os links faltantes, cidades são selecionadas aleatoriamente.

Eventualmente, o algoritmo genético poderá criar soluções idênticas, o que não é o ideal. Todos indivíduos semelhantes em uma população acarreta na não convergência do algoritmo até achar a solução ótima. Para solucionar isso, usamos o processo de mutação, onde algumas rotas filhas são aleatoriamente modificadas a fim de produzir uma nova rota distinta.

Este algoritmo genético usa uma população inicial gulosa. Isto significa que o algoritmo genético não cria uma população individuos totalmente aleatória. Ele preferirá criar rotas com links entre cidades que sejam bem próximas uma das outras. Isto não é feito 100% do tempo, porque, claro, poderia acarretar na criação de uma população de rotas bastante similares.

Há 6 parâmetros para controlar a execução do Algoritmo Genético:

  • Tamanho da população- O tamanho da população é o número de quantas rotas devem ser criadas aleatoriamente quando o algoritmo é iniciado. Uma imensa população faz com que o algoritmo demore mais para encontrar a solução. Em contrapartida, uma pequena população aumenta as chances de que todas as rotas criadas sejam eventualmente bem semelhantes. Consequentemente, isto aumenta as chances de que a melhor solução não seja encontrada.
  • Seleção - A cada geração, um número N de rotas são selecionadas da população. As 2 melhores rotas são utilizadas para o cruzamento (crossover). As 2 piores rotas são substituídas pelos 2 novos filhos gerados. Um valor alto para N aumenta as chances de que rotas com alto valor de aptidão sejam escolhidas, porém pode provocar a redução de chances de outras rotas não tão boas serem escolhidas.
  • Mutação% - A taxa de mutação informa as chances de cada filho após o crossover sofram o processo de mutação. Quando uma rota é modificada, uma das cidades é aleatoriamente movida de um ponto para outro ponto dentro da rota.
  • Número máximo de gerações - Quantas gerações devem ser criadas até que a execução do algoritmo finalize. Utilizada como críterio de parada para este problema.
  • Lista de cidades - Neste programa temos a opção de importar nomes de cidades já previamente construídas ou gerá-las em tempo de execução. Em futuras versões, poderemos fazer com que sejam importadas as cidades e suas localizações a partir de um arquivo XML.
Os parâmetros iniciais do algoritmo são:

Parâmetro Valor inicial
Tam. Pop. 10,000
Seleção N 5
Mutação 3 %



Para execução, é necessário ter instalado o ambiente de execução Python (> 2.5) e o pluggin para construção de interfaces gráficas PyFltk (versão de acordo com o Python instalado na sua máquina).


Clique aqui para fazer o download do TSP GA Simulator.


Para executar, após extrair todo o conteúdo em uma pasta, basta abrir o arquivo Tsp.py pelo IDLE (ambiente de edição de arquivos) do Python e clicar em Run -> RunModule.

Vale salientar que esse simulador não é a versão final e nem tão sofisticada. Quaisquer sugestões ou melhorias são válidas para tornar este simulador mais interessante. Algumas melhorias devem ser realizadas no processo de crossover. Mandem comentários!

Referências:

Problema do caixeiro viajante - Wikipedia
Algoritmos Genéticos - UFRJ


Até a próxima!

Marcel Pinheiro Caraciolo

14 comments:

  1. Olá Marcel.
    Estou implementando o TSP em Java em uma disciplina. Estava utilizando a codificação clássica do cromossomo e achei muito interessante essa idéia de "link". No meu caso eu estava utilizando um cruzamento (clássico) de 3 pontos (pois com somente 1 ponto estava convergindo muito rápido), mas acho que com a idéia de link o algoritmo pode encontrar uma solução melhor, devido ao problema que ABCD = DABC.
    Gostaria de parabenizá-lo pelo artigo que está muito bem escrito. Confesso que fiquei um pouco em dúvida na parte dos cruzamentos dos links. Agora estou meio ocupado, então mais tarde irei ler com mais atenção e baixar o código para tentar entender e qualquer dúvida me comunico com você através deste post.
    Valeu.

    ReplyDelete
  2. Seria interessante colocar isso no gps!

    ReplyDelete
  3. Marcel teria como consertar o link do simulador?
    Estou estudando mais a fundo o caixeiro viajante e iria me ajudar um exemplo implementado.
    Obrigado pela atenção

    ReplyDelete
  4. boa noite, este artigo é muito interessante e é o que estou á procura, mas será que podia disponibilizar o programa? só para ver como funciona? é que o link já não está a funcionar.
    Cumprimentos
    Joaquim Santos

    ReplyDelete
  5. Pessoal o codigo foi atualizado :) podem baixar agora!

    ReplyDelete
    Replies
    1. Marcel Caraciolo, estou precisando do código do Problema do Caixeiro Viajante. Gostaria de entrar em contato com você por email. Meu email delminhaerks@hotmail.com , se você puder entrar em contato comigo ficarei muito grata.

      Delete
  6. " Minha solução consiste de criar links em ambas direções para cada rota."
    Tem certeza que a solução é sua?
    http://www.lalena.com/AI/Tsp/

    ReplyDelete
    Replies
    1. Se a solução for desse cara, então ele esta milionário.

      Delete
  7. Tua explicação pra esse exemplo de uso dos algoritmos genéticos tá muito boa!
    Tava com umas dúvidas e o texto ajudou muito a saná-las, obrigada!

    ReplyDelete
  8. Ola, pessoal não sei se estou utilizando o canal certo de pesquisa, mas gostaria de conhecer ou criar um algorítimo para criação de rota de troca.
    O caso seria o seguinte, 5 pessoas, cada uma com um item para troca, com a disposição para receber em troca até 5 itens diferentes. O objetivo será criar uma rota de trocas o mais curta possível. Se alguém ja viu o pensou nisto gostaria de trocar informações.

    ReplyDelete
  9. WIZTECH Automation, Anna Nagar, Chennai, has earned reputation offering the best automation training in Chennai in the field of industrial automation. Flexible timings, hands-on-experience, 100% practical. The candidates are given enhanced job oriented practical training in all major brands of PLCs (AB, Keyence, ABB, GE-FANUC, OMRON, DELTA, SIEMENS, MITSUBISHI, SCHNEIDER, and MESSUNG)

    PLC training in chennai
    Automation training in chennai
    Best plc training in chennai
    PLC SCADA training in chennai
    Process automation training in chennai
    Final year eee projects in chennai
    VLSI training in chennai

    ReplyDelete
  10. Embedded system training: Wiztech Automation Provides Excellent training in embedded system training in Chennai - IEEE Projects - Mechanical projects in Chennai Wiztech provide 100% practical training, Individual focus, Free Accommodation, Placement for top companies. The study also includes standard microcontrollers such as Intel 8051, PIC, AVR, ARM, ARMCotex, Arduino etc.

    Embedded system training in chennai
    Embedded Course training in chennai
    Matlab training in chennai
    Android training in chennai
    LabVIEW training in chennai
    Arduino training in chennai
    Robotics training in chennai
    Oracle training in chennai
    Final year projects in chennai
    Mechanical projects in chennai
    ece projects in chennai

    ReplyDelete