Jenetics — Java Genetic Algorithm

Examples

Ones Counting

Ones counting is one of the simplest model-problem and consists of a binary chromosome. The fitness of a Genotype is proportional to the number of ones. The FitnessFunction looks like this:

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(Genotype<BitGene> genotype) {
		int count = 0;
		for (BitGene gene : genotype.getChromosome()) {
			if (gene.getBit()) {
				++count;
			}
		}
		return count;
	}
}

public class OnesCounting {
	public static void main(String[] args) {
		Factory<Genotype<BitGene>> gtf = Genotype.valueOf(
			new BitChromosome(20, 0.15)
		);
		Function<Genotype<BitGene>, Integer> ff = new OneCounter();
		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.

  +---------------------------------------------------------+
  |  Population Statistics                                  |
  +---------------------------------------------------------+
  |                     Age mean: 1.36000000000             |
  |                 Age variance: 3.74530612245             |
  |                      Samples: 50                        |
  |                 Best fitness: 18                        |
  |                Worst fitness: 5                         |
  +---------------------------------------------------------+
  +---------------------------------------------------------+
  |  Fitness Statistics                                     |
  +---------------------------------------------------------+
  |                 Fitness mean: 12.30000000000            |
  |             Fitness variance: 8.25510204082             |
  |        Fitness error of mean: 1.73948268172             |
  +---------------------------------------------------------+

The given example will print the overall timing statistics onto the console.

0/1 Knapsack Problem

In the knapsack problem a set of items, together with their size and value, is given. The task is to select a disjoint subset so that the total size does not exeed the knapsacks size. (Wikipedia: Knapsack problem) For the 0/1 knapsack problem we define a BitChromosome, one bit for each item. If the ith BitGene is set to one the ith item is selected.

import org.jscience.mathematics.number.Float64;

import org.jenetics.BitChromosome;
import org.jenetics.BitGene;
import org.jenetics.Chromosome;
import org.jenetics.GeneticAlgorithm;
import org.jenetics.Genotype;
import org.jenetics.Mutator;
import org.jenetics.NumberStatistics;
import org.jenetics.RouletteWheelSelector;
import org.jenetics.SinglePointCrossover;
import org.jenetics.util.Factory;
import org.jenetics.util.Function;

final class Item {
	public double size;
	public double value;
}

final class KnappsackFunction
	implements Function<Genotype<BitGene>, Float64>
{
	private final Item[] _items;
	private final double _size;

	public KnappsackFunction(final Item[] items, double size) {
		_items = items;
		_size = size;
	}

	public Item[] getItems() {
		return _items;
	}

	@Override
	public Float64 apply(final Genotype<BitGene> genotype) {
		final Chromosome<BitGene> ch = genotype.getChromosome();

		double size = 0;
		double value = 0;
		for (int i = 0, n = ch.length(); i < n; ++i) {
			if (ch.getGene(i).getBit()) {
				size += _items[i].size;
				value += _items[i].value;
			}
		}

		if (size > _size) {
			return Float64.ZERO;
		} else {
			return Float64.valueOf(value);
		}
	}
}

public class Knapsack {

	private static KnappsackFunction FF(int n, double size) {
		Item[] items = new Item[n];
		for (int i = 0; i < items.length; ++i) {
			items[i] = new Item();
			items[i].size = (Math.random() + 1)*10;
			items[i].value = (Math.random() + 1)*15;
		}

		return new KnappsackFunction(items, size);
	}

	public static void main(String[] argv) throws Exception {
		KnappsackFunction ff = FF(15, 100);
		Factory<Genotype<BitGene>> genotype = Genotype.valueOf(
			new BitChromosome(15, 0.5)
		);

		GeneticAlgorithm<BitGene, Float64> ga = 
			new GeneticAlgorithm<>(genotype, ff);
		
		ga.setMaximalPhenotypeAge(30);
		ga.setPopulationSize(100);
		ga.setStatisticsCalculator(
			new NumberStatistics.Calculator<BitGene, Float64>()
		);
		ga.setSelectors(
			new RouletteWheelSelector<BitGene, Float64>()
		);
		ga.setAlterers(
			 new Mutator<BitGene>(0.115),
			 new SinglePointCrossover<BitGene>(0.16)
		);

		ga.setup();
		ga.evolve(100);
		System.out.println(ga.getBestStatistics());
	}
}

The console out put for the Knapsack GA will look like the listing beneath.

  +---------------------------------------------------------+
  |  Population Statistics                                  |
  +---------------------------------------------------------+
  |                     Age mean: 1.55000000000             |
  |                 Age variance: 2.69444444444             |
  |                      Samples: 100                       |
  |                 Best fitness: 188.57227213871303        |
  |                Worst fitness: 0.0                       |
  +---------------------------------------------------------+
  +---------------------------------------------------------+
  |  Fitness Statistics                                     |
  +---------------------------------------------------------+
  |                 Fitness mean: 157.60654768894           |
  |             Fitness variance: 1486.23455609328          |
  |        Fitness error of mean: 15.76065476889            |
  +---------------------------------------------------------+

Traveling Salesman Problem (TSP)

The Traveling Salesman problem is a very good example which shows you how to solve combinatorial problems with an GA. Jenetics contains several classes which will work very well with this kind of problems. Wrapping the base type into an EnumGene is the first thing to do. In our example, every city has an unique number, that means we are wrapping an Integer into an EnumGene. Creating a genotype for integer values is very easy with the factory method of the PermutationChromosome. For other data types you have to use one of the constructors of the permutation chromosome. As alterers, we are using a swap-mutator and a partially-matched crossover. These alterers guarantees that no invalid solutions are created—every city exists exactly once in the altered chromosomes.

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>>, Float64>
{
	private final double[][] _adjacence;
	public FF(final double[][] adjacence) {
		_adjacence = adjacence;
	}
	@Override
	public Float64 apply(Genotype<EnumGene<Integer>> genotype) {
		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 Float64.valueOf(length);
	}
}

public class TravelingSalesman {

	public static void main(String[] args) {
		final int stops = 20;

		Function<Genotype<EnumGene<Integer>>, Float64> ff = 
			new FF(adjacencyMatrix(stops));
		Factory<Genotype<EnumGene<Integer>>> gt = Genotype.valueOf(
			PermutationChromosome.ofInteger(stops)
		);
		final GeneticAlgorithm<EnumGene<Integer>, Float64>
			ga = new GeneticAlgorithm<>(gt, ff, Optimize.MINIMUM);
		ga.setStatisticsCalculator(
			new Calculator<EnumGene<Integer>, Float64>()
		);
		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;
}

The listing above shows the output generated by our example. The last line represents the phenotype of the best solution found by the GA, which represents the traveling path. As you can see, the GA has found the shortest path, in reverse order.

  +---------------------------------------------------------+
  |  Population Statistics                                  |
  +---------------------------------------------------------+
  |                     Age mean: 1.48333333333             |
  |                 Age variance: 3.72212931996             |
  |                      Samples: 300                       |
  |                 Best fitness: 62.573786016092335        |
  |                Worst fitness: 315.49784819824816        |
  +---------------------------------------------------------+
  +---------------------------------------------------------+
  |  Fitness Statistics                                     |
  +---------------------------------------------------------+
  |                 Fitness mean: 118.87334461782           |
  |             Fitness variance: 6464.82405084876          |
  |        Fitness error of mean: 6.86315575146             |
  +---------------------------------------------------------+
  [19|18|17|16|15|14|13|12|11|10|9|8|7|6|5|4|3|2|1|0] --> 62.573786016092335
© Copyright Franz Wilhelmstötter