Algoritmo Genético e um exemplo com JavaFX

Saindo do labirinto usando algoritmo genético

Esse post é uma união de pois posts no meu blog em inglês

Um dos tópicos mais fascinantes no mundo da ciência da computação é Inteligência Artificial (IA). Uma sub-divisão no mundo da inteligência artificial são aqueles algoritmos que são baseados na natureza e nesse grupo temos os Algoritmos Genéticos.

Algoritmos Genéticos

Eu não irei me aprofundar nesse tópico, mas há ótimos materiais na internet.  A ideia geral é um algoritmo que leve em conta, dado um indíviduo, ele:

• Tenha variação genética em diversos indivíduos (organismos também se aplica aqui);
• Possa se reprodução e levar o código genético para suas gerações;
• A cada reprodução haja ligeiras variações genéticas;
• Uma "nota" para saber quão aquele indíviduo está adaptado ao ambiente atual.

Isso tudo é parte da teoria mais que comprovada de Darwin. O nome "teoria" confunde algumas pessoas e isso é incrível, acham que por ser uma teoria, é algo não confiável, mas interessantemente todas as evidências validam essa teoria desde que ela foi publicada! Sobre IA e Evolução, Pirulla fala um pouco disso no vídeo abaixo.



Para saber mais sugiro a página da Wikipédia sobre o assunto e o vídeo de uma aula do MIT e, de novo, um vídeo do Shiffman.

Algoritmos genéticos usando Java

Para colocar isso em prática usando em Java você pode desenvolver o seu próprio mini framework com DNA, Genes, cromossomos, algoritmos de mutação ou cruzamento e algoritmos de seleção natural, mas pra que reinventar a roda? No mundo Java temos algumas bibliotecas já conhecidas nesse meio, destaco a JGAP, um pouco antiga, e a moderna Jenetics, que usa Java 8 e os novos conceitos como Lambda, Method Reference, Stream, etc. O guia do usuário da API Jenetics é muito bom, cobre quase todas as classes que são usadas durante a programação. Mas ainda senti falta de exemplos mais claros, por isso, antes de tentar algo visual com JavaFX, eu criei 3 pequenas aplicações.


Seleciona o conjunto de double que tem a maior soma de algarismos; Esse é um exemplo besta, mas que mostra algumas classes importantes da API. A ideia é: dado um conjunto de double, qual tem a maior soma dos algarismos? Veja o código.
CODE

A saída é algo assim:

[[[85],[23],[62]]], sum 26
[[[42],[5],[53]]], sum 19
[[[4],[82],[14]]], sum 19
[[[17],[99],[41]]], sum 31
[[[32],[16],[23]]], sum 17
[[[15],[85],[38]]], sum 30
[[[54],[30],[51]]], sum 18
[[[31],[20],[76]]], sum 19
[[[88],[63],[69]]], sum 40
[[[52],[11],[6]]], sum 15
 (Um monte de passo intermediário)
[[[88],[97],[97]]], sum 48
[[[88],[97],[97]]], sum 48
[[[88],[29],[25]]], sum 34
[[[88],[97],[95]]], sum 46
[[[88],[97],[97]]], sum 48
Selected: [[[88],[97],[97]]]. Sum: 48

Veja que podemos resolver ele ser usar algoritmo genético, mas no código acima você pode começar a entender a pegada da API: Cromossomos tem um conjunto de genes, os genes são os objetos reais da sua aplicação (um número, uma String, um objeto do tipo pessoa...), genotype é o conjunto de cromossomos e criamos dois métodos importantes: um gera valores para serem trabalhados pela API (no exemplo acima usamos um cromossomo da própria API e ele tem o método pra gerar: Genotype.of(LongChromosome.of(1, 100, 3));) e o método que recebe o Genotype para que você possa trabalhar nele e retornar um ranking ou um número que indica quanto aquele genotype está adaptado ao ambiente (ver o método fitness).


Escrevendo uma frase: Se você conseguir 1 milhão de macacos e falar pra eles darem tapas no teclado de 1 milhão de computadores, qual seria a chance desse texto sair uma música da banda Queen? Raras, muito raras. Um programa com algoritmo genético pode chegar a esse resultado muito mais rápido e é claro que esse é somente outro exemplo. Veja abaixo um programa com Jenetics que consegue escrever uma frase que você escrever usando evolução:




Escape do Labirinto: Esse é um exemplo um pouco mais elaborado. Nele temos um pequeno labirinto gerado e a função do algoritmo genético é evoluir o conjunto inicial de direções do labirinto para encontrar uma saída. Bem, esse código é um pouco extenso, assim peço para vocês verem no meu github. A ideia é ter genes que são customizados, do tipo Direction  e esses genes são uma possível saída para o labirinto, representado pela classe Maze. Incrivelmente, com algoritmo genético, as direções iniciais são mutadas de forma que conseguem encontrar uma saída do labirinto! Vejam uma tela:

Como esse é um blog sobre JavaFX, foi criada uma aplicação que desenha o labirinto e permite que você teste parâmetros para rodar o algoritmo! O código dele também é extenso e ninguém vai ler um blog com dezenas de linhas de código! Então, caso queiram estudar mais, aqui vão os passos para executar a aplicação (precisa de Maven e Java 8):

• Primeiro instalem o DrawingFX que já falei sobre ele aqui: http://aprendendo-javafx.blogspot.com.br/2017/01/desenvolvimento-rapido-de-aplicacoes-de.html
• Clone o repositorio  https://github.com/jesuino/drawing-fx (ou baixe o código), entre no diretório criado com o código e rode: mvn clean install
• Agora clone o repositório onde está todo o código do labirinto: https://github.com/jesuino/genetics-algorithm-tests
• Por fim, entre no diretório com o código e rode:

$ mvn clean package exec:java -Dexec.mainClass=org.fxapps.genetics.mazefx.MazeFXApp

O resultado pode ser visto no vídeo abaixo: