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).

	import java.util.concurrent.atomic.AtomicInteger;
	import org.jenetics.Genotype;
	import org.jenetics.LongChromosome;
	import org.jenetics.LongGene;
	import org.jenetics.engine.Engine;
	import org.jenetics.engine.EvolutionResult;
	import org.jenetics.util.Factory;
	/**
	*
	* Select the genotype with greatest algorithms sum
	*
	* @author wsiqueir
	*
	*/
	public class LargestDigitSum {
	private static Integer fitness(Genotype<LongGene> lt) {
	LongChromosome lc = lt.getChromosome().as(LongChromosome.class);
	AtomicInteger sum = new AtomicInteger(0);
	lc.stream().forEach(l -> {
	String str = String.valueOf(l.longValue());
	for (char ch : str.toCharArray()) {
	sum.addAndGet(Integer.parseInt(String.valueOf(ch)));
	}
	});
	System.out.println(lt + ", sum " + sum.get());
	return sum.get();
	}
	public static void main(String[] args) {
	Factory<Genotype<LongGene>> gtf = Genotype.of(LongChromosome.of(1, 100, 3));
	Engine<LongGene, Integer> engine = Engine.builder(LargestDigitSum::fitness, gtf).build();
	Genotype<LongGene> result = engine.stream().limit(10).collect(EvolutionResult.toBestGenotype());
	System.out.println("Selected: " + result + ". Sum: " + fitness(result));
	}
	}

view raw LargestDigitSum.java hosted with ❤ by GitHub

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:

	import java.util.Random;
	import org.jenetics.AnyChromosome;
	import org.jenetics.AnyGene;
	import org.jenetics.Genotype;
	import org.jenetics.RouletteWheelSelector;
	import org.jenetics.engine.Engine;
	import org.jenetics.engine.EvolutionResult;
	import org.jenetics.util.Factory;
	/**
	*
	* Will learn how to write the sentence you chose
	*
	* @author wsiqueir
	*
	*/
	public class SentenceWriter {
	final static String SENTENCE = "Be or not to be?";
	private static String POSSIBLE_CHARS;
	static Random r = new Random();
	public static Character generateRandomString() {
	POSSIBLE_CHARS = " abcdefghijklmnopqrstuvxzwyABCDEFGHIJKLMNOPQRSTUVXZWY!?.,'";
	int i = r.nextInt(POSSIBLE_CHARS.length());
	return POSSIBLE_CHARS.charAt(i);
	}
	private static Integer fitness(Genotype<AnyGene<Character>> ch) {
	int sum = 0;
	for (int i = 0; i < SENTENCE.length(); i++) {
	char target = SENTENCE.charAt(i);
	char allele = ch.getChromosome().getGene(i).getAllele();
	if (allele == target) {
	sum += 100;
	}
	sum += POSSIBLE_CHARS.length() - Math.abs(target - allele);
	}
	return sum;
	}
	public static void main(String[] args) {
	Factory<Genotype<AnyGene<Character>>> gtf = Genotype
	.of(AnyChromosome.of(SentenceWriter::generateRandomString, SENTENCE.length()));
	final Engine<AnyGene<Character>, Integer> engine = Engine.builder(SentenceWriter::fitness, gtf)
	.offspringSelector(new RouletteWheelSelector<>()).build();
	Genotype<AnyGene<Character>> result = engine.stream().limit(50000).collect(EvolutionResult.toBestGenotype());
	System.out.println("Selected: " + result);
	}
	}

view raw SentenceWriter.java hosted with ❤ by GitHub

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: