According to its official documents, Jenetics is a library that is used for programming evolutionary algorithms written in Java. Jenetics is implemented using the Java Stream interface, so it works smoothly with the rest of the Java Stream API. Evolutionary algorithms have their roots in biology, as they use mechanisms inspired by biological evolution, such as reproduction, mutation, recombination, and selection. If you want to learn more about the theory behind evolutionary algorithms, I’d suggest reading Introduction to Evolutionary Algorithms first.
Disclaimer: This blog post is based on Introduction to Jenetics Library from Baeldung. But it is using the current library version (6.2.0) and a more complex example: The knapsack problem without using the libraries provided classes for the problem.
The knapsack problem
Wikipedia
Given a set of items, each with a weight and a value, determine the number of each item to include in a collection so that the total weight is less than or equal to a given limit and the total value is as large as possible. It derives its name from the problem faced by someone who is constrained by a fixed-size knapsack and must fill it with the most valuable items.
Defining the problem in code
In the following example, we have a class called “Knapsack” that represents our problem. The class defines items that consist of a size and a value (possibleKnapsackItems). These items are initialized with random values between 0 and 10 and put in a list to represent the items we can put into our knapsack. Furthermore, the class defines the maximum size the knapsack can hold. Attention: Don’t mix up the size of the knapsack (Knapsack.getKnapsackSize) with the number of items that we could put in the knapsack (Knapsack.getItemCount). The items that we actually put into the knapsack will be defined later in our evolutionary algorithm.
public final class Knapsack {
private final List<Item> possibleKnapsackItems; // items that *might* end up in the knapsack, depending on chromosome
private int knapsackSize;
public Knapsack(List<Item> possibleItems, int knapsackSize) {
this.possibleKnapsackItems = possibleItems;
this.knapsackSize = knapsackSize;
}
public static Knapsack initializeWithRandomItems(int size, int knapsackSize) {
Random random = new Random(123);
List<Item> items = Stream.generate(() ->
new Item((int) (random.nextDouble()*10),(int) (random.nextDouble()*10)))
.limit(size)
.collect(Collectors.toList());
return new Knapsack(items, knapsackSize);
}
public Item getItemByIndex(int index) { return this.possibleKnapsackItems.get(index); }
public int getItemCount() { return this.possibleKnapsackItems.size(); }
public int getKnapsackSize() { return this.knapsackSize; }
public static final class Item {
private final int size;
private final int value;
public Item(final int size, final int value) {
this.size = Requires.nonNegative(size);
this.value = Requires.nonNegative(value);
}
public int getSize() { return size; }
public int getValue() { return value; }
}
}Let’s get started with the Jenetics Library
In order to use Jenetics, we need to add the following dependency into our build.gradle:
implementation 'io.jenetics:jenetics:6.2.0'Next we create a runnable class App that will use the Jenetics library and our Knapsack class to run a genetic algorithm. First, let’s make use of our previously created class: We create a knapsack with a size of 100 and 80 items from which we can pick.
public class App {
private final static int ITEM_COUNT = 80;
private final static int KNAPSACK_SIZE = 100;
private final static int POPULATION_SIZE = 500;
private final Knapsack knapsack = Knapsack.initializeWithRandomItems(ITEM_COUNT, KNAPSACK_SIZE);
public static void main(String[] args) {
new App().run(POPULATION_SIZE);
}
public void run(int populationSize) {
// TODO Run the genetic algorithm
}
}Let’s work on the run() function. We need to convert the Knapsack problem into another representation that a genetic algorithm can work with, namely a chromosome. And indeed we can transform it into a so-called binary problem, where each one represents an item we put into the knapsack, each zero represents an item we don’t put in the knapsack.
Using the Jenetics library we can create a BitChromosome with a length of 80 which is equal to the number of items we can choose from (ITEM_COUNT) and a probability of having 1’s in the chromosome equal to 0.3. These BitChromosomes are accessible via a factory, meaning we can generate as many randomly initialized chromosomes as we want our population size to be.
final Factory<Genotype<BitGene>> gtf =
Genotype.of(BitChromosome.of(this.knapsack.getItemCount(), 0.3));Now, let’s create the execution environment:
final Engine<BitGene, Integer> engine = Engine
.builder(this::fitness, gtf)
.populationSize(populationSize)
.build();The Engine will run our genetic algorithm and needs a couple of information:
- The factory we just created, that produces our random chromosomes
- The number of random chromosomes we want to create and compare (called populationSize)
- Last but not least, a fitness function which we didn’t define, yet
The Fitness Function
The fitness function calculates the fitness of each chromosome. In the case of the knapsack problem, the fitness is equal to the sum of the values of the individual elements that we place in our knapsack (i.e. items with corresponding one in the chromosome). How to put that into code, is something you can think about now 😉
private Integer fitness(Genotype<BitGene> gt) {
BitChromosome chromosome = gt.chromosome().as(BitChromosome.class);
int fitness = 0;
// TODO: Calculate fitness
return fitness;
}A first run
In the final step, in our run function, we add some basic statistics, start the evolution and collect the results:
final EvolutionStatistics<Integer, ?> statistics = EvolutionStatistics.ofNumber();
final Phenotype<BitGene, Integer> best = engine.stream()
// Truncate the evolution stream after 7 "steady"
// generations.
.limit(bySteadyFitness(10))
// Update the evaluation statistics after
// each generation
.peek(statistics)
// Collect (reduce) the evolution stream to
// its best phenotype.
.collect(toBestPhenotype());
System.out.println(statistics);
System.out.println(best);If you put everything together and implemented the fitness function correctly, you should end up with a result looking like this:
+---------------------------------------------------------------------------+
| Time statistics |
+---------------------------------------------------------------------------+
| Selection: sum=0,029213700000 s; mean=0,000811491667 s |
| Altering: sum=0,120244900000 s; mean=0,003340136111 s |
| Fitness calculation: sum=0,054355500000 s; mean=0,001509875000 s |
| Overall execution: sum=0,199033900000 s; mean=0,005528719444 s |
+---------------------------------------------------------------------------+
| Evolution statistics |
+---------------------------------------------------------------------------+
| Generations: 36 |
| Altered: sum=133.010; mean=3694,722222222 |
| Killed: sum=0; mean=0,000000000 |
| Invalids: sum=0; mean=0,000000000 |
+---------------------------------------------------------------------------+
| Population statistics |
+---------------------------------------------------------------------------+
| Age: max=14; mean=2,183056; var=7,349621 |
| Fitness: |
| min = 0,000000000000 |
| max = 188,000000000000 |
| mean = 134,464166666667 |
| var = 4503,017550280571 |
| std = 67,104527047589 |
+---------------------------------------------------------------------------+
[11101010|00000100|11000101|10001000|10001111|10100000|01010010|10110000|11000101|10000101] -> 188If so, congratulations! You made it.
Further Optimiziation
So up until now, we told the engine to learn using 500 generations and let it decide on itself how to do mutation, recombination, and selection. Of course, if you want to improve the quality of your best phenotype you can configure these things yourself. An easy thing to do is to increase the number of generations to i.e. 5000 and your results will probably improve. But you can also tweak several things like mutation yourself:
final Engine<BitGene, Integer> engine = Engine
.builder(this::fitness, gtf)
.populationSize(populationSize)
.survivorsSelector(new TournamentSelector<>(5))
.offspringSelector(new RouletteWheelSelector<>())
.alterers(
new Mutator<>(0.115),
new SinglePointCrossover<>(0.16))
.build();But to gain some real improvements using your own configuration is something that is pretty time consuming and would need another blogpost, so I’ll leave that to you 😀
Greetings,
Domi