FXApps: Genetic algorithms with Java
source link: http://fxapps.blogspot.com/2017/01/genetic-algorithms-with-java.html
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
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.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)); } }
It will produce an output like the following:
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:[[[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
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); } }
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.
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):
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK