Resolvendo o problema do caixeiro viajante com Algoritmos Genéticos

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 10³² 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 3^rde 4^th 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.

Parent1	F A B | E C G D
Parent2	D 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:

City	First Connection	Second Connection
A	F	B
B	A	E
C	E	G
D	G	F
E	B	C
F	D	A
G	C	D

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