Genetic algorithms with Java

One of the most fascinating topics in computer science world is Artificial Intelligence. A subset of Artificial intelligence are the algorithms that were created inspired in the nature. In this group, we have Genetic Algorithms (GA).

Genetic Algorithms 

To find out more about this topic I recommend the following MIT lecture and the Nature of Code book and videos created by Daniel Shiffman.

Genetic Algorithms using Java

After I remembered the basics about it, I wanted to practice, so I tried my own implementation, but I would have to write a lot of code to do what certainly others already did. So I started looking for Genetic Algorithm libraries and found Jenetics, which is a modern library that uses Java 8 concepts and APIs, and there's also JGAP. I decided to use Jenetics because the User Guide was so clear and it has no other dependency, but Java 8.
The only thing I missed for Jenetics are more small examples like the ones I will show in this post. They have examples, one very basic that you can find in user guide and a complex one.

Simple Genetic Algorithms examples using Jenetics

I have to say that this all happened last 2 days! Therefore, I am not a genetic algorithm specialist, but a hobbyist. I even had to ask Jenetics twitter if I was doing it right.

@William_Antonio Your example looks good. But you are using the 'POPULATION' constant for limiting the EvolutionStream generations.

— Jenetics GA (@jeneticsga) January 9, 2017

And at that point I was calling what can be interpreted as the number of generations as the population. I still have a lot to learn and improve how I use the library and the fitness methods I created, but here are some examples:

Select double numbers with the largest digits sum: That's not the most suitable use for genetic algorithms, but it is a way to get familiar with the API and its concepts. The idea was to keep the population that has the largest sum of all numbers digits. I used only a few lines of code to create this small example, but the reason is that Jenetics has a few built in chromosomes, including a LongChromosome:

	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

It will produce an output like the following:

[[[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
 (... lot of intermediate steps..)
[[[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

Teach it how to write a sentence: When talking about GA, Daniel Shiffman usually mentions the idea of probability of millions of monkeys randomly typing on a keyboard trying  to write a Shakespeare book - that's almost impossible to get the book done if using only random process - GA would solve it much faster. One example to show how GA works is make it write a sentence - many will say that it is an useless use for the library, but I  say it is good to learn. See the code:

	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

The output will usually be the sentence formed or something close to the sentence. I have to say that at my first implementation I used the entire ascii table to it would guess any text - but that was a bad idea :).


Escape the maze: Ok, so far I have created small examples using mostly Jenetics classes, so I tried something a little more complex - but not that hard (let's not destroy the fun): escape the maze. In the code I have a model Maze, the model and utility methods for a given maze and the MazeSolver, the class that makes use of Jenetics to solve a given maze.

My fitness function is far away from being perfect, but it works! I didn't find no maze that couldn't be solved so far. One thing to improve is how to use less steps because I spent a few hours trying to find a balance between reach the target and use less steps: to give a high score to solutions that used less steps was usually leading to solutions that are not reaching the target!

The full code is on my github - I won't paste the full maze code here - the few readers I have are complaining about large code in a post! (they are right, I hate it too)

And for next post I will talk about the JavaFX view for the maze (I still need to make a few improvements):