Package org.jenetics

Introduction

See: Description

Package org.jenetics Description

Introduction

The Jenetics project provides a Genetic Algorithm (GA) implementation. The project has very few dependencies to other libraries. At runtime it only depends on the Jenetics library.

The order of the single execution steps of genetic algorithms may slightly differ from implementation to implementation. The following pseudo-code shows the Jenetics genetic algorithm steps. Genetic algorithm

Line (1) creates the initial population and the line (2) calculates the fitness value of the individuals. (This is done by the GeneticAlgorithm.setup() method.) Line (4) increases the generation number and line (5) and (6) selects the survivor and the offspring population. The offspring/survivor fraction is determined by the offspringFraction property of the GA. The selected offspring are altered in line (7). The next line combines the survivor population and the altered offspring population-- after removing the died individuals--to the new population. The steps from line (4) to (9) are repeated until a given termination criterion is fulfilled.

Data structures

Structure Diagram

The diagram above shows the main data structures of the GA implementation. The Gene is the base of the building block. Genes are aggregated in Chromosomes. One to n Chromosomes are aggregated in Genotypes. A Genotype and a fitness Function form the Phenotype. Phenotypes are collected into a Population.

Getting started

The minimum GA setup needs a genotype factory, Factory<Genotype<?>>, and a fitness Function. The Genotype implements the Factory interface and can therefore be used as prototype for creating the initial Population and for creating new random Genotypes.
public static void main(final String[] args) { final Factory〈Genotype〈BitGene〉〉 gtf = Genotype.of( BitChromosome.of(10, 0.5) ); final Function〈Genotype〈BitGene〉 Double〉 ff = ... final GeneticAlgorithm〈BitGene, Double〉 ga = new GeneticAlgorithm〈〉(gtf, ff, Optimize.MAXIMUM) ga.setup(); ga.evolve(100); System.out.println(ga.getBestPhenotype()); }

The genotype factory, gtf, in the example above will create genotypes which consists of one BitChromosome with length 10. The one to zero probability of the newly created genotypes is set to 0.5. The fitness function is parameterized with a BitGene and a Double. That means that the fitness function is calculating the fitness value as Double. The return type of the fitness function must be at least a Comparable. The GeneticAlgorithm object is then created with the genotype factory and the fitness function. In this example the GA tries to maximize the fitness function. If you want to find the minimal value you have to change the optimize parameter from Optimize.MAXIMUM to Optimize.MINIMUM. The ga.setup() call creates the initial population and calculates its fitness value. Then the GA evolves 100 generations (ga.evolve(100)) an prints the best phenotype found so far onto the console.

In a more advanced setup you may want to change the default mutation and/or selection strategies.
public static void main(final String[] args) { ... ga.setSelectors(new RouletteWheelSelector〈BitGene〉()); ga.setAlterers( new SinglePointCrossover〈BitGene〉(0.1), new Mutator〈BitGene〉(0.01) ); ga.setup(); ga.evolve(100); System.out.println(ga.getBestPhenotype()); }

The selection strategy for offspring and survivors are set to the roulette-wheel selector. It is also possible to set the selector for offspring and survivors independently with the setOffspringSelector and setSurvivorSelector methods. The alterers are concatenated, at first the crossover (with probability 0.1) is performed and then the chromosomes are mutated (with probability 0.01).

Serialization

With the serialization mechanism you can write a population to disk and load it into an GA at a later time. It can also be used to transfer populations to GAs, running on different hosts, over a network link. The IO class, located in the org.jenetics.util package, supports native Java serialization and XML serialization. For XML marshaling Jenetics internally uses the XML support from the Javolution project.
// Writing the population to disk. final File file = new File("population.xml"); IO.jaxb.write(ga.getPopulation(), file); // Reading the population from disk. final Population〈DoubleGene,Double〉 population = (Population〈DoubleGene, Double〉)IO.jaxb.read(file); ga.setPopulation(population);

Examples

Ones Counting

Ones counting is one of the simplest model-problem. It uses a binary chromosome and forms a classic genetic algorithm. In the classic genetic algorithm the problem is a maximization problem and the fitness function is positive. The domain of the fitness function is a bit-chromosome. The fitness of a Genotype is proportional to the number of ones.
import org.jenetics.BitChromosome; import org.jenetics.BitGene; import org.jenetics.GeneticAlgorithm; import org.jenetics.Genotype; import org.jenetics.Mutator; import org.jenetics.NumberStatistics; import org.jenetics.Optimize; import org.jenetics.RouletteWheelSelector; import org.jenetics.SinglePointCrossover; import org.jenetics.util.Factory; import org.jenetics.util.Function; final class OneCounter implements Function〈Genotype〈BitGene〉, Integer〉 { @Override public Integer apply(final Genotype〈BitGene〉 genotype) { return ((BitChromosome)genotype.getChromosome()).bitCount(); } } public class OnesCounting { public static void main(String[] args) { final Factory〈Genotype〈BitGene〉〉 gtf = Genotype.of( BitChromosome.of(20, 0.15) ); final Function〈Genotype〈BitGene〉, Integer〉 ff = new OneCounter(); final GeneticAlgorithm〈BitGene, Integer〉 ga = new GeneticAlgorithm〈〉(gtf, ff, Optimize.MAXIMUM); ga.setStatisticsCalculator( new NumberStatistics.Calculator〈BitGene, Integer〉() ); ga.setPopulationSize(50); ga.setSelectors( new RouletteWheelSelector〈BitGene, Integer〉() ); ga.setAlterers( new Mutator〈BitGene〉(0.55), new SinglePointCrossover〈BitGene〉(0.06) ); ga.setup(); ga.evolve(100); System.out.println(ga.getBestStatistics()); } }
The genotype in this example consists of one BitChromosome with a ones probability of 0.15. The altering of the offspring population is performed by mutation, with mutation probability of 0.55, and then by a single-point crossover, with crossover probability of 0.06. After creating the initial population, with the ga.setup() call, 100 generations are evolved. The tournament selector is used for both, the offspring- and the survivor selection---this is the default selector.

Traveling Salesman

The Traveling Salesman problem is one of the classical problems in computational mathematics and it is the most notorious NP-complete problem. The goal is to find the shortest distance, or the path, with the least costs, between N different cities. Testing all possible path for N cities would lead to N! checks to find the shortest one. The following example uses a path where the cities are lying on a circle. That means, the optimal path will be a polygon. This makes it easier to check the quality of the found solution.
import static java.lang.Math.PI; import static java.lang.Math.abs; import static java.lang.Math.sin; import org.jenetics.Chromosome; import org.jenetics.EnumGene; import org.jenetics.GeneticAlgorithm; import org.jenetics.Genotype; import org.jenetics.NumberStatistics.Calculator; import org.jenetics.Optimize; import org.jenetics.PartiallyMatchedCrossover; import org.jenetics.PermutationChromosome; import org.jenetics.SwapMutator; import org.jenetics.util.Factory; import org.jenetics.util.Function; class FF implements Function〈Genotype〈EnumGene<Integer〉〉, Double〉 { private final double[][] _adjacence; public FF(final double[][] adjacence) { _adjacence = adjacence; } @Override public Double apply(final Genotype〈EnumGene〈Integer〉〉 genotype) { final Chromosome〈EnumGene〈Integer〉〉 path = genotype.getChromosome(); double length = 0.0; for (int i = 0, n = path.length(); i 〈 n; ++i) { final int from = path.getGene(i).getAllele(); final int to = path.getGene((i + 1)%n).getAllele(); length += _adjacence[from][to]; } return length; } } public class TravelingSalesman { public static void main(String[] args) { final int stops = 20; final Function〈Genotype〈EnumGene〈Integer〉〉, Double〉 ff = new FF(adjacencyMatrix(stops)); final Factory〈Genotype〈EnumGene〈Integer〉〉〉 gt = Genotype.of( PermutationChromosome.ofInteger(stops) ); final GeneticAlgorithm〈EnumGene〈Integer〉, Double〉 ga = new GeneticAlgorithm〈〉(gt, ff, Optimize.MINIMUM); ga.setStatisticsCalculator( new Calculator〈EnumGene〈Integer〉, Double〉() ); ga.setPopulationSize(300); ga.setAlterers( new SwapMutator〈EnumGene〈Integer〉〉(0.2), new PartiallyMatchedCrossover〈Integer〉(0.3) ); ga.setup(); ga.evolve(700); System.out.println(ga.getBestStatistics()); System.out.println(ga.getBestPhenotype()); } private static double[][] adjacencyMatrix(int stops) { double[][] matrix = new double[stops][stops]; for (int i = 0; i 〈 stops; ++i) { for (int j = 0; j 〈 stops; ++j) { matrix[i][j] = chord(stops, abs(i - j), RADIUS); } } return matrix; } private static double chord(int stops, int i, double r) { return 2.0*r*abs(sin((PI*i)/stops)); } private static double RADIUS = 10.0; }
Since:
1.0
Version:
1.6 — $Date: 2014-03-05 $
Author:
Franz Wilhelmstötter

© 2007-2014 Franz Wilhelmstötter  (2014-03-07 19:35)