Criar algoritmo genético em Java para Iniciantes – Parte 2

Criar algoritmo genético em Java para IniciantesEsta é a segunda parte da série de tutoriais “Criar algoritmo genético em Java para Iniciantes”. Nesta segunda parte iremos começar a programar a nossa versão de algoritmo genético aplicado ao problema do caixeiro-viajante e para isso iremos utilizar a linguagem Java.

Parte 2 – Criação do algoritmo genético

No contexto do problema do caixeiro-viajante as localizações por onde o mercador passa são chamadas de cidades (City) e os percursos que o mercador pode percorrer de rotas (Tour). No código Java iremos adoptar estas convenções, City para cidade e Tour para passeios/rotas. O código Java que apresento já a seguir encontra-se altamente comentado para que possa perceber todos os detalhes do algoritmo. Recomendo que leia todos os comentários com atenção.

Para começar criamos uma classe City.java que descreve uma cidade.

City.java

 

Agora devemos criar uma classe que irá descrever uma tour (rota).

Tour.java

Agora vamos criar uma classe que guarda todos os destinos que uma tour (rota) deve ter.

TourManager.java

 Precisamos também de uma classe para gerir um conjunto de rotas, ou seja, uma população.

Population.java

Agora o mais importante, uma classe que irá tratar de aplicar o algoritmo genético às populações de rotas. Esta classe irá evoluir uma população para a geração seguinte.

GA.java

E por fim iremos criar a class App que irá conter o método main. Nesse método iremos criar as nossas cidades que irão pertencer a cada rota, e iremos criar a população mais primitiva que será depois evoluída utilizando a classe GA juntamente com um loop.

App.java

Resultado da execução:

O mapa que mostrei na primeira parte desta série de tutoriais, ligado de acordo com a solução acima é o seguinte:

Algoritmo Genético - Resultado Final

Como resultado, encontramos uma solução bastante boa que se não for a solução optima estará concertara muito perto da solução óptima. Quanto maior for o comprimento das nossas populações e quanto maior o número de gerações, mais perto ficará o resultado final da solução óptima, contudo mais tempo de computação será utilizado.

Este post faz parte de uma série de três tutoriais, não perca as outras partes:

Gostou deste artigo? Caso tenha dúvidas deixe um comentário abaixo.

Deixar uma resposta