Design a Genetic Algorithm in Java

1. Introduction

The aim of this series is to explain the idea of genetic algorithms.

Genetic algorithms are designed to solve problems by using the same processes as in nature — they use a combination of selection, recombination, and mutation to evolve a solution to a problem.

Let’s start by explaining the concept of those algorithms using the simplest binary genetic algorithm example.

2. How Genetic Algorithms Work

Genetic algorithms are a part of evolutionary computing, which is a rapidly growing area of artificial intelligence.

An algorithm starts with a set of solutions (represented by individuals) called population. Solutions from one population are taken and used to form a new population, as there is a chance that the new population will be better than the old one.

Individuals that are chosen to form new solutions (offspring) are selected according to their fitness — the more suitable they are, the more chances they have to reproduce.

3. Binary Genetic Algorithm

Let’s take a look at the basic process for a simple genetic algorithm.

3.1. Initialization

In the initialization step, we generate a random Population that serves as a first solution. First, we need to decide how big the Population will be and what is the final solution that we expect:

SimpleGeneticAlgorithm.runAlgorithm(50,
  "1011000100000100010000100000100111001000000100000100000000001111");

In the above example, the Population size is 50, and the correct solution is represented by the binary bit string that we may change at any time.

In the next step we are going to save our desired solution and create a random Population:

setSolution(solution);
Population myPop = new Population(populationSize, true);

Now we are ready to run the main loop of the program.

3.2. Fitness Check

In the main loop of the program, we are going to evaluate each Individual by the fitness function (in simple words, the better the Individual is, the higher value of fitness function it gets):

while (myPop.getFittest().getFitness() < getMaxFitness()) {
    System.out.println(
      "Generation: " + generationCount
      + " Correct genes found: " + myPop.getFittest().getFitness());
    
    myPop = evolvePopulation(myPop);
    generationCount++;
}

Let’s start with explaining how we get the fittest Individual:

public int getFitness(Individual individual) {
    int fitness = 0;
    for (int i = 0; i < individual.getDefaultGeneLength()
      && i < solution.length; i++) {
        if (individual.getSingleGene(i) == solution[i]) {
            fitness++;
        }
    }
    return fitness;
}

As we can observe, we compare two Individual objects bit by bit. If we cannot find a perfect solution, we need to proceed to the next step, which is an evolution of the Population.

3.3. Offspring

In this step, we need to create a new Population. First, we need to Select two parent Individual objects from a Population, according to their fitness. Please note that it is beneficial to allow the best Individual from the current generation to carry over to the next, unaltered. This strategy is called an Elitism:

if (elitism) {
    newPopulation.getIndividuals().add(0, pop.getFittest());
    elitismOffset = 1;
} else {
    elitismOffset = 0;
}

In order to select two best Individual objects, we are going to apply tournament selection strategy:

private Individual tournamentSelection(Population pop) {
    Population tournament = new Population(tournamentSize, false);
    for (int i = 0; i < tournamentSize; i++) {
        int randomId = (int) (Math.random() * pop.getIndividuals().size());
        tournament.getIndividuals().add(i, pop.getIndividual(randomId));
    }
    Individual fittest = tournament.getFittest();
    return fittest;
}

The winner of each tournament (the one with the best fitness) is selected for the next stage, which is Crossover:

private Individual crossover(Individual indiv1, Individual indiv2) {
    Individual newSol = new Individual();
    for (int i = 0; i < newSol.getDefaultGeneLength(); i++) {
        if (Math.random() <= uniformRate) {
            newSol.setSingleGene(i, indiv1.getSingleGene(i));
        } else {
            newSol.setSingleGene(i, indiv2.getSingleGene(i));
        }
    }
    return newSol;
}

In the crossover, we swap bits from each chosen Individual at a randomly chosen spot. The whole process runs inside the following loop:

for (int i = elitismOffset; i < pop.getIndividuals().size(); i++) {
    Individual indiv1 = tournamentSelection(pop);
    Individual indiv2 = tournamentSelection(pop);
    Individual newIndiv = crossover(indiv1, indiv2);
    newPopulation.getIndividuals().add(i, newIndiv);
}

As we can see, after the crossover, we place new offspring in a new Population. This step is called the Acceptance.

Finally, we can perform a Mutation. Mutation is used to maintain genetic diversity from one generation of a Population to the next. We used the bit inversion type of mutation, where random bits are simply inverted:

private void mutate(Individual indiv) {
    for (int i = 0; i < indiv.getDefaultGeneLength(); i++) {
        if (Math.random() <= mutationRate) {
            byte gene = (byte) Math.round(Math.random());
            indiv.setSingleGene(i, gene);
        }
    }
}

All types of the Mutation and the Crossover are nicely described in this tutorial.

We then repeat steps from subsections 3.2 and 3.3, until we reach a termination condition, for example, the best solution.

4. Tips and Tricks

In order to implement an efficient genetic algorithm, we need to tune a set of parameters. This section should give you some basic recommendations how to start with the most importing parameters:

• Crossover rate – it should be high, about 80%-95%
• Mutation rate – it should be very low, around 0.5%-1%.
• Population size – good population size is about 20-30, however, for some problems sizes 50-100 are better
• Selection – basic roulette wheel selection can be used with the concept of elitism
• Crossover and mutation type – it depends on encoding and the problem

Please note that recommendations for tuning are often results of empiric studies on genetic algorithms, and they may vary, based on the proposed problems.

5. Conclusion

This tutorial introduces fundamentals of genetic algorithms. You can learn about genetic algorithms without any previous knowledge of this area, having only basic computer programming skills.

Please also note that we use Lombok to generate getters and setters. You can check how to configure it correctly in your IDE in this article.

For further examples of genetic algorithms, check out all the articles of our series:

• How to Design a Genetic Algorithm? (this one)
• The Traveling Salesman Problem in Java