sábado, 4 de abril de 2015

Problema do Caixeiro Viajante com Algoritmos Genéticos

Olá pessoal, recentemente fiz uma implementação simples de algoritmos genéticos para resolver o problema do caixeiro viajante.

O problema do caixeiro viajante (tavelling salesman problem) consiste em iniciar um percurso em uma determinada cidade, passar por todas as outras cidades uma única vez e terminar na cidade onde começou. O custo do percurso tem que ser mínimo.

É bem intuitivo transformar para grafos onde as cidades seriam os vértices e as arestas seriam as ligações entre as cidades com um determinado custo.

Veja o grafo a seguir:


Um dos menores custos para o grafo anterior é 9 com o percurso:

0 -> 3 -> 4 -> 2 -> 1 -> 0.

Apesar de ser fácil de entender, esse problema é da classe NP-difícil. Não se sabe um algoritmo que resolva ele em tempo polinomial, por isso são utilizadas heurísticas para tentar resolvê-lo como é o caso dos algoritmos genéticos.

Algoritmos genéticos é uma técnica de busca para achar soluções aproximadas em problemas de otimização e busca. Os algoritmos genéticos não garantem uma solução ótima, mas geralmente garantem boas soluções.

Um cromossomo nada mais é que um indíviduo, uma string enfim. No problema em questão o cromossomo é um percurso, por exemplo:

1 2 3 4 5

O cromossomo (indivíduo) acima indica que o percurso começou na cidade 1, depois foi para a cidade 2, 3, 4 e 5. Lembrando que para que o percurso seja válido é preciso verificar também se há conexão (aresta) saindo da última cidade (nesse caso é a cidade 5) e chegando na cidade de onde começou o percurso (nesse caso é a cidade 1).

A população inicial é gerada aleatoriamente através de permutações randômicas onde é garantido que cada indivíduo não terá cidades repetidas, pois esta é uma restrição do problema do caixeiro viajante.

Uma população é um conjunto de indivíduos, lembrando que no nosso caso um indivíduo é um percurso válido, consequentemente só existem percursos válidos em nossa população.

Lembrando que existem muitas variações de implementação de algoritmos genéticos, estou descrevendo como eu implementei para resolver o problema do caixeiro viajante, fique à vontade para modificar, melhorar enfim.

A população é ordenada crescentemente pelo custo de cada percurso, ou seja, do percurso de menor custo para o percurso de maior custo.

Para evitar que fosse ordenado o vetor de população a cada inserção de um novo indivíduo, foi implementada uma função para inserir o indivíduo na posição correta através de uma busca binária.

Após gerar a população inicial, são selecionados randomicamente os pais que irão participar do processo reprodutório.

Após selecionados os pais, são feitos cruzamentos entre os indivíduos para que possam ser gerados novos indivíduos, esse é o processo reprodutório onde indíviduos trocam genes para gerar outros indivíduos. Um gene no nosso caso nada mais é que uma cidade. Um conjunto de genes forma um indivíduo (cromossomo).

O crossover faz a troca de genes. No crossover implementado, são selecionados dois pontos aleatórios, esses pontos geram subvetores (ou substrings) que são partes de um indivíduo. Essas partes são invertidas e trocadas pelos pais.

Pai 1:  1 2 3 4
Pai 2:  1 4 2 3

são selecionados dois pontos aleatórios...

parte do pai 1:  2 3
parte do pai 2:  4 2

parte invertida do pai 1:  3 2
parte invertida do pai 2:  2 4

Filho 1:  1 2 4 4
Filho 2:  1 3 2 3

Opa! Geramos filhos inválidos, pois em ambos os filhos temos cidades repetidas, portanto, são indivíduos inválidos. Para resolver isso foi usado um mapa de genes para cada pai indicando se o gene já está sendo usado ou não. Inicialmente todos os genes não estão usados, vai marcando cada gene à medida que vai sendo selecionado. Caso tente inserir um gene que já está sendo usado, então é escolhido algum gene do mapa de genes que ainda não foi usado.

A taxa de mutação contribui para uma diversidade. É gerado um número aleatório de 1 a 100, se a taxa de mutação for 5% e o número gerado for menor ou igual a 5, então é feita a mutação que consiste na troca de dois genes.

Foi implementado também um gerador de grafos aleatórios onde são gerados grafos com uma grande quantidade de arestas para testar a implementação com exemplos maiores. Os grafos gerados têm pelo menos um percurso que atende ao problema do caixeiro viajante. Quanto maior o número de vértices, mais arestas o grafo terá porque a adição de arestas ao grafo aleatório leva em conta o número de vértices, ou seja, a quantidade de percursos cresce absurdamente ao aumentar o número de vértices.

A implementação foi feita em C++, segue o link do repositório:



Nenhum comentário: