In this chapter we will begin to explore the techniques used to implement a basic genetic algorithm. The program we develop here will be modified adding features in the succeeding chapters in this book. We will also explore how the performance of a genetic algorithm can vary depending on its parameters and configuration.

To follow along with the code in this section you’ll need to first have the Java JDK installed on your computer. You can download and install the Java JDK for free from the Oracle’s website:

oracle.com/technetwork/java/javase/downloads/index.html

Although not necessary, in addition to installing the Java JDK, for convenience you may also choose to install a Java compatible IDE such as Eclipse or NetBeans.

Pre-Implementation

Before implementing a genetic algorithm it’s a good idea to first consider if a genetic algorithm is the right approach for the task at hand. Often there will be better techniques to solve specific optimization problems, usually by taking advantage of some domain dependent heuristics. Genetic algorithms are domain independent, or “weak methods”, which can be applied to problems without requiring any specific prior knowledge to assist with its search process. For this reason, if there isn’t any known domain specific knowledge available to help guide the search process, a genetic algorithm can still be applied to discover potential solutions.

When it has been determined that a weak search method is appropriate, the type of weak method used should also be considered. This could simply be because an alternative method provides better results on average, but it could also be because an alternative method is easier to implement, requires less computational resources, or can find a good enough result in a shorter time period.

Pseudo Code for a Basic Genetic Algorithm

The pseudo code for a basic genetic algorithm is as follows:

1: generation = 0;
2: population[generation] = initializePopulation(populationSize);
3: evaluatePopulation(population[generation]);
3: While isTerminationConditionMet() == false do
4:     parents = selectParents(population[generation]);
5:    population[generation+1] = crossover(parents);
6:   population[generation+1] = mutate(population[generation+1]);
7:    evaluatePopulation(population[generation]);
8:     generation++;
9: End loop;

The pseudo code begins with creating the genetic algorithm’s initial population. This population is then evaluated to find the fitness values of its individuals. Next, a check is run to decide if the genetic algorithm’s termination condition has been met. If it hasn’t, the genetic algorithm begins looping and the population goes through its first round of crossover and mutation before finally being reevaluated. From here, crossover and mutation are continuously applied until the termination condition is met, and the genetic algorithm terminates.

This pseudo code demonstrates the basic process of a genetic algorithm; however it is necessary that we look at each step in more detail to fully understand how to create a satisfactory genetic algorithm.

About the Code Examples in this Book

Each chapter in this book is represented as a package in the accompanying Eclipse project. Each package will have, at minimum, four classes:

• A GeneticAlgorithm class, which abstracts the genetic algorithm itself and provides problem-specific implementations of interface methods, such as crossover, mutation, fitness evaluation, and termination condition checking.
• An Individual class, which represents a single candidate solution and its chromosome.
• A Population class, which represents a population or a generation of Individuals, and applies group-level operations to them.
• A class that contains the “main” method, some bootstrap code, the concrete version of the pseudocode above, and any supporting work that a specific problem may need. These classes will be named according to the problem it solves, e.g. “AllOnesGA”, “RobotController”, etc.

The GeneticAlgorithm, Population, and Individual classes that you initially write in this chapter will need to be modified for each of the following chapters in this book.

You could imagine that these classes are actually concrete implementations of interfaces such as a GeneticAlgorithmInterface, PopulationInterface, and IndividualInterface–however, we’ve kept the layout of the Eclipse project simple and avoided using interfaces.

The GeneticAlgorithm classes you’ll find throughout this book will always implement a number of important methods such as ‘calcFitness’, ‘evalPopulation’, ‘isTerminationConditionMet’, ‘crossoverPopulation’, and ‘mutatePopulation’. However, the contents of these methods will be slightly different in each chapter, based on the requirements of the problem at hand.

While following the examples in this book we recommend copying the GeneticAlgorithm, Population, and Individual classes over to each new problem, as some methods’ implementations will remain the same from chapter to chapter, but others will differ.

Also, be sure to read the comments in the source code in the attached Eclipse project! To save space in the book we’ve left long comments and docblocks out, but have taken great care to annotate the source code thoroughly in the Eclipse file available for download. It’s like having a second book to read!

In many cases, the chapters in this book will ask you to add or modify a single method in a class. Generally, it doesn’t matter where in a file you add a new method, so in these cases we’ll either omit the rest of the class from the example, or we’ll show function signatures only to help keep you on track.

Basic Implementation

To remove any unnecessary details and keep the initial implementation easy to follow, the first genetic algorithm we will cover in this book will be a simple binary genetic algorithm.

Binary genetic algorithms are relatively easy to implement and can be incredibly effective tools for solving a wide spectrum of optimization problems. As you may remember from Chapter 1, binary genetic algorithms were the original category of genetic algorithm proposed by Holland (1975).

The Problem

First, let’s review the “all ones” problem, a very basic problem that can be solved using a binary genetic algorithm.

The problem isn’t very interesting, but it serves its role as being a simple problem which helps emphasize the fundamental techniques involved. As the name suggests, the problem is simply finding a string which is comprised entirely of ones. So for a string with a length of 5 the best solution would be, “11111”.

Parameters

Now we have a problem to solve, let’s move on to the implementation. The first thing we’re going to do is set up the genetic algorithm parameters. As covered previously, the three primary parameters are population size, mutation rate and crossover rate. We also introduce a concept called “elitism” in this chapter, and will include that as one of the parameters of the genetic algorithm.

To begin, create a class called GeneticAlgorithm. If you’re using Eclipse, you can do this by selecting File New Class. We have chosen to name packages corresponding to the chapter number in this book, therefore we’ll work in the package “Chapter2”.

This GeneticAlgorithm class will contain the methods and variables needed for operations of the genetic algorithm itself. For example, this class includes the logic to handle crossover, mutation, fitness evaluation, and termination condition checking. After the class has been created, add a constructor which accepts the four parameters: population size, mutation rate, crossover rate, and number of elite members.

package chapter2;
/**
 * Lots of comments in the source that are omitted here!
 */
public class GeneticAlgorithm {
      private int populationSize;
      private double mutationRate;
      private double crossoverRate;
      private int elitismCount;

public GeneticAlgorithm(int populationSize, double mutationRate, double crossoverRate, int elitismCount) {
            this.populationSize = populationSize;
            this.mutationRate = mutationRate;
            this.crossoverRate = crossoverRate;
            this.elitismCount = elitismCount;
      }

      /**
       * Many more methods implemented later...
       */
}

When passed the required parameters, this constructor will create a new instance of the GeneticAlgorithm class with the required configuration.

Now we should create our bootstrap class – recall that each chapter will require a bootstrap class to initialize the genetic algorithm and provide a starting point for the application. Name this class “AllOnesGA” and define a “main” method:

package chapter2;
public class AllOnesGA {
      public static void main(String[] args) {
            // Create GA object
            GeneticAlgorithm ga = new GeneticAlgorithm(100, 0.01, 0.95, 0);
            // We’ll add a lot more here...
      }
}

For the time being, we’ll just use some typical values for the parameters, population size = 100; mutation rate = 0.01; crossover rate = 0.95, and an elitism count of 0 (effectively disabling it – for now). After you have completed your implementation at the end of the chapter, you can experiment with how changing these parameters affect the performance of the algorithm.

Initialization

Our next step is to initialize a population of potential solutions. This is usually done randomly, but occasionally it might be preferable to initialize the population more systematically, possibly to make use of known information about the search space. In this example, each individual in the population will be initialized randomly. We can do this by selecting a value of 1 or 0 for each gene in a chromosome at random.

Before initializing the population we need to create two classes, one to manage and create the population and the other to manage and create the population’s individuals. It will be these classes that contain the methods to fetch an individual’s fitness, or get the fittest individual in the population, for example.

First let’s start by creating the Individual class. Note that we’ve omitted all the comments and method docblocks below to save paper! You can find a thoroughly annotated version of this class in the accompanying Eclipse project.

package chapter2;

public class Individual {
      private int[] chromosome;
      private double fitness = -1;

      public Individual(int[] chromosome) {
            // Create individual chromosome
            this.chromosome = chromosome;
      }

      public Individual(int chromosomeLength) {
            this.chromosome = new int[chromosomeLength];
            for (int gene = 0; gene < chromosomeLength; gene++) {
                  if (0.5 < Math.random()) {
                        this.setGene(gene, 1);
                  } else {
                        this.setGene(gene, 0);
                  }
            }

      }

      public int[] getChromosome() {
            return this.chromosome;
      }

      public int getChromosomeLength() {
            return this.chromosome.length;
      }

      public void setGene(int offset, int gene) {
            this.chromosome[offset] = gene;
      }

      public int getGene(int offset) {
            return this.chromosome[offset];
      }

      public void setFitness(double fitness) {
            this.fitness = fitness;
      }

      public double getFitness() {
            return this.fitness;
      }

      public String toString() {
            String output = "";
            for (int gene = 0; gene < this.chromosome.length; gene++) {
                  output += this.chromosome[gene];
            }
            return output;
      }
}

The Individual class represents a single candidate solution and is primarily responsible for storing and manipulating a chromosome. Note that the Individual class also has two constructors. One constructor accepts an integer (representing the length of the chromosome) and will create a random chromosome when initializing the object. The other constructor accepts an integer array and uses that as the chromosome.

Aside from managing the Individual’s chromosome it also keeps track of the individual’s fitness value, and also knows how to print itself as a string.

The next step is to create the Population class which provides the functionality needed to manage a group of individuals in a population.

As usual, comments and docblocks have been omitted from this chapter; be sure to look at the Eclipse project for more context!

package chapter2;

import java.util.Arrays;
import java.util.Comparator;

public class Population {
      private Individual population[];
      private double populationFitness = -1;

      public Population(int populationSize) {
            this.population = new Individual[populationSize];
      }

      public Population(int populationSize, int chromosomeLength) {
            this.population = new Individual[populationSize];

            for (int individualCount = 0; individualCount < populationSize; individualCount++) {
                  Individual individual = new Individual(chromosomeLength);
                  this.population[individualCount] = individual;
            }
      }

      public Individual[] getIndividuals() {
            return this.population;
      }

      public Individual getFittest(int offset) {
            Arrays.sort(this.population, new Comparator<Individual>() {
                  @Override
                  public int compare(Individual o1, Individual o2) {
                        if (o1.getFitness() > o2.getFitness()) {
                              return -1;
                        } else if (o1.getFitness() < o2.getFitness()) {
                              return 1;
                        }
                        return 0;
                  }
            });

            return this.population[offset];
      }

      public void setPopulationFitness(double fitness) {
            this.populationFitness = fitness;
      }

      public double getPopulationFitness() {
            return this.populationFitness;
      }

      public int size() {
            return this.population.length;
      }

      public Individual setIndividual(int offset, Individual individual) {
            return population[offset] = individual;
      }

            public Individual getIndividual(int offset) {
            return population[offset];
      }

      public void shuffle() {
            Random rnd = new Random();
            for (int i = population.length - 1; i > 0; i--) {
                       int index = rnd.nextInt(i + 1);
                       Individual a = population[index];
                       population[index] = population[i];
                       population[i] = a;
            }
      }
}

The population class is quite simple; its main function is to hold an array of individuals which can be accessed as needed in a convenient way by the class methods. Methods such as the getFittest( ) and setIndividual( ) are examples of methods which can access and update the individuals in the population. In addition to holding the individuals it also stores the population’s total fitness which will become important later on when implementing the selection method.

Now that we have our population and individual classes, we can implement them in the GeneticAlgorithm class. To do so, simply create a method named ‘initPopulatio’ anywhere in the GeneticAlgorithm class.

public class GeneticAlgorithm {
      /**
       * The constructor we created earlier is up here...
       */

      public Population initPopulation(int chromosomeLength) {
            Population population = new Population(this.populationSize, chromosomeLength);
            return population;
      }

      /**
       * We still have lots of methods to implement down here...
       */
}

Now that we have a Population and an Individual class, we can return to our ‘AllOnesGA’ class and start working with the ‘initPopulation’ method. Recall that the ‘AllOnesGA’ class only has a ‘main’ method, and that it represents the pseudocode presented earlier in the chapter.

When initializing the population in the main method, we also need to specify the length of individuals’ chromosomes – here we are going to use a length of 50:

 public class AllOnesGA {
    public static void main(String[] args){
        // Create GA object
        GeneticAlgorithm ga = new GeneticAlgorithm(100, 0.01, 0.95, 0);

        // Initialize population
        Population population = ga.initPopulation(50);
    }
}

Evaluation

In the evaluation stage, each individual in the population has their fitness value calculated and stored for future use. To calculate the fitness of an individual we use a function known as the “fitness function”.

Genetic algorithms operate by using selection to guide the evolutionary process towards better individuals. Because it’s the fitness function that makes this selection possible, it’s important that the fitness function is designed well and provides an accurate value for the individual’s fitness. If the fitness function isn’t well-designed it can take longer to find a solution which satisfies the minimum criteria, or possibly, fail to find an acceptable solution at all.

Fitness functions will often be the most computationally demanding components of a genetic algorithm. Because of this, it’s important that the fitness function is also well optimized helping to prevent bottlenecks and allowing the algorithm to run efficiently.

Each specific optimization problem requires a uniquely developed fitness function. In our example of the all-ones problem, the fitness function is rather straightforward, simply counting the number of ones found within an individual’s chromosome.

Now add a calcFitness method to the GeneticAlgorithm class. This method should count the number of ones in the chromosome, and then normalize the output to be between zero and one by dividing by the chromosome length. You may add this method anywhere in the GeneticAlgorithm class, so we’ve omitted the surrounding code below:

public double calcFitness(Individual individual) {

      // Track number of correct genes
      int correctGenes = 0;

      // Loop over individual’s genes
      for (int geneIndex = 0; geneIndex < individual.getChromosomeLength(); geneIndex++) {
            // Add one fitness point for each "1" found
            if (individual.getGene(geneIndex) == 1) {
                  correctGenes += 1;
            }
      }

      // Calculate fitness
      double fitness = (double) correctGenes / individual.getChromosomeLength();

      // Store fitness
      individual.setFitness(fitness);

      return fitness;
}

We also need a simple helper method to loop over every individual in the population and evaluate them (i.e., call calcFitness on each individual). Let’s call this method evalPopulation and add it to the GeneticAlgorithm class as well. It should look like the following, and again you may add it anywhere:

public void evalPopulation(Population population) {
      double populationFitness = 0;

      for (Individual individual : population.getIndividuals()) {
            populationFitness += calcFitness(individual);
      }

      population.setPopulationFitness(populationFitness);
}

At this point, the GeneticAlgorithm class should have the following methods in it. For brevity’s sake, we’ve omitted the body of the functions and are just showing a collapsed view of the class:

package chapter2;

public class GeneticAlgorithm {
      private int populationSize;
      private double mutationRate;
      private double crossoverRate;
      private int elitismCount;

      public GeneticAlgorithm(int populationSize, double mutationRate, double crossoverRate, int elitismCount) { }
      public Population initPopulation(int chromosomeLength) { }
      public double calcFitness(Individual individual) { }
      public void evalPopulation(Population population) { }
}

If you’re missing any of these properties or methods, please go back and implement them now. We have four more methods to implement in the GeneticAlgorithm class: isTerminationConditionMet, selectParent, crossoverPopulation, and mutatePopulation.

Termination Check

The next thing needed is to check if our termination condition has been met. There are many different types of termination conditions. Sometimes, it’s possible to know what the optimal solution is (rather, it’s possible to know the fitness value of the optimal solution), in which case we can check directly for the correct solution. However, it’s not always possible to know what the fitness of the best solution is, so we can terminate when the solution has become “good enough”; that is, whenever the solution exceeds some fitness threshold. We could also terminate when the algorithm has run for too long (too many generations), or we can combine a number of factors when deciding to terminate the algorithm.

Due to the simplicity of the all-ones problem, and the fact that we know the correct fitness should be 1, it’s reasonable in this case to terminate when the correct solution has been found. This won’t always be the case! In fact, it will only rarely be the case – but we’re lucky this is an easy problem.

To begin, we must first construct a function which can check if our termination condition has occurred. We can do this by adding the following code to the GeneticAlgorithm class. Add this anywhere, and as usual we’ve omitted the surrounding class for brevity’s sake.

public boolean isTerminationConditionMet(Population population) {
      for (Individual individual : population.getIndividuals()) {
            if (individual.getFitness() == 1) {
                  return true;
            }
      }

      return false;
}

The above method checks each individual in the population and will return true – indicating that we’ve found a termination condition and can stop – if the fitness of any individual in the population is 1.

Now that the termination condition has been built, a loop can be added to the main bootstrap method in the AllOnesGA class using the newly added termination check as its loop conditional. When the termination check returns true, the genetic algorithm will stop looping and return its results.

To create the evolution loop, modify the main method of our executive AllOnesGA class to represent the following. The first two lines of the snippet below are already in the main method. By adding this code we’re continuing to implement the pseudocode presented at the beginning of the chapter – recall that the “main” method is a concrete representation of the genetic algorithm pseudocode. Here’s what the main method should look like now:

public static void main(String[] args) {
      // These two lines were already here:
      GeneticAlgorithm ga = new GeneticAlgorithm(100, 0.001, 0.95, 0);
      Population population = ga.initPopulation(50);

      // The following is the new code you should be adding:
      ga.evalPopulation(population);
      int generation = 1;

      while (ga.isTerminationConditionMet(population) == false) {
            // Print fittest individual from population
            System.out.println("Best solution: " + population.getFittest(0).toString());

            // Apply crossover
            // TODO!

            // Apply mutation
            // TODO!

            // Evaluate population
            ga.evalPopulation(population);

            // Increment the current generation
            generation++;
      }

      System.out.println("Found solution in " + generation + " generations");
      System.out.println("Best solution: " + population.getFittest(0).toString());
}

We’ve added an evolution loop that checks the output of isTerminationConditionMet. Also new to the main method are the addition of evalPopulation calls both before and during the loop, the generation variable that keeps track of the generation number, and the debug message that helpfully lets you know what the best solution in each generation looks like.

We’ve also added an end-game: when we exit the loop, we’ll print some information about the final solution.

However, at this point our genetic algorithm will run, but it won’t ever evolve! We’ll be stuck in an infinite loop unless we’re lucky enough that one of our randomly generated individuals happens to be all ones. You can see this behavior directly by clicking the “Run” button in Eclipse; the same solution will be presented over and over and the loop will never end. You’ll have to force the program to stop running by clicking the “Terminate” button above Eclipse’s console.

To continue building our genetic algorithm we need to implement two additional concepts: crossover and mutation. These concepts actually drive the evolution of a population forward through random mutation and survival of the fittest.

Crossover

At this point, it’s time to start evolving the population by applying mutation and crossover. The crossover operator is the process in which individuals from the population trade genetic information, hopefully to create a new individual which contains the best parts from its parents’ genomes.

During crossover each individual in the population is considered for crossover; this is where the crossover rate parameter is used. By comparing the crossover rate to a random number, we can decide whether the individual should have crossover applied to it, or whether it should be added straight into the next population unaffected by crossover. If an individual is selected for crossover then a second parent needs be found. To find the second parent, we need to pick one of many possible selection methods.

Roulette Wheel Selection

Roulette wheel selection - also known as fitness proportionate selection - is a selection method which uses the analogy of a roulette wheel to select individuals from a population. The idea is that individuals from the population are placed on a metaphoric roulette wheel depending on their fitness value. The higher the fitness of the individual, the more space it’s allocated on the roulette wheel. The image below demonstrates how individuals are typically positioned in this process.

Each number on the wheel above represents an individual from the population. The higher the fitness of the individual, the larger their portion of the roulette wheel. If you now imagine spinning this wheel, it’s much more likely that the fitter individuals will be picked because they fill more space on the wheel. This is why this selection method is often referred to as fitness proportionate selection; because solutions are selected based on their fitness in proportion to the fitness of the rest of the population.

There are many other selection methods that we could use such as: tournament selection (Chapter 3) and stochastic universal sampling (an advanced form of fitness proportional selection). However, in this chapter we will be implementing one of the most common selection methods: roulette wheel selection. In later chapters we will be looking at other selection methods and how they differ.

Crossover Methods

In addition to the various selection methods that can be used during crossover, there are also different methods to exchange the genetic information between two individuals. Different problems have slightly different properties and work better with specific crossover methods. For example, the all-ones problem simply requires a string that consists entirely of 1s. A string of “00111” has the same fitness value as a string of “10101” – they both contain three 1s. With genetic algorithms of this type, this isn’t always the case. Imagine we are trying to create a string which lists, in order, the numbers one to five. In this case the string “12345” has a very different fitness value from “52431”. This is because we’re not just looking for the correct numbers, but also the correct order. For problems such as this, a crossover method that respects the order of the genes is preferable.

The crossover method we will be implementing here is uniform crossover. In this method each gene of the offspring has a 50% change of coming from either its first parent or its second parent.

Crossover Pseudo Code

Now that we have a selection and a crossover method, let’s look at some pseudo code which outlines the crossover process to be implemented.

1: For each individual in population:
2:      newPopulation = new array;
2:       If crossoverRate > random():
3:             secondParent = selectParent();
4:            offspring = crossover(individual, secondParent);
5:            newPopulation.push(offspring);
6:      Else:
7:            newPopulation.push(individual);
8:      End if
9: End loop;

Crossover Implementation

To implement roulette wheel selection, add a selectParent( ) method anywhere in the GeneticAlgorithm class.

public Individual selectParent(Population population) {
      // Get individuals
      Individual individuals[] = population.getIndividuals();

      // Spin roulette wheel
      double populationFitness = population.getPopulationFitness();
      double rouletteWheelPosition = Math.random() * populationFitness;

      // Find parent
      double spinWheel = 0;
      for (Individual individual : individuals) {
            spinWheel += individual.getFitness();
            if (spinWheel >= rouletteWheelPosition) {
                  return individual;
            }
      }
      return individuals[population.size() - 1];
}

The selectParent( ) method essentially runs a roulette wheel in reverse; at a casino, the wheel already has markings on it, and then you spin the wheel and wait for the ball to drop into position. Here, however, we select a random position first and then work backward to figure out which individual lies in that position. Algorithmically, it’s easier this way. Choose a random number between 0 and the total population fitness, then loop through each individual, summing their fitnesses as you go, until you reach the random position you chose at the outset.

Now that the selection method has been added, the next step is to create the crossover method using this selectParent( ) method to select the crossover mates. To begin, add the following crossover method to the GeneticAlgorithm class.

public Population crossoverPopulation(Population population) {
      // Create new population
      Population newPopulation = new Population(population.size());

      // Loop over current population by fitness
      for (int populationIndex = 0; populationIndex < population.size(); populationIndex++) {
            Individual parent1 = population.getFittest(populationIndex);

            // Apply crossover to this individual?
            if (this.crossoverRate > Math.random() && populationIndex > this.elitismCount) {
                  // Initialize offspring
                  Individual offspring = new Individual(parent1.getChromosomeLength());

                  // Find second parent
                  Individual parent2 = selectParent(population);

                  // Loop over genome
                  for (int geneIndex = 0; geneIndex < parent1.getChromosomeLength(); geneIndex++) {
                        // Use half of parent1's genes and half of parent2's genes
                        if (0.5 > Math.random()) {
                              offspring.setGene(geneIndex, parent1.getGene(geneIndex));
                        } else {
                              offspring.setGene(geneIndex, parent2.getGene(geneIndex));
                        }
                  }

                  // Add offspring to new population
                  newPopulation.setIndividual(populationIndex, offspring);
            } else {
                  // Add individual to new population without applying crossover
                  newPopulation.setIndividual(populationIndex, parent1);
            }
      }

      return newPopulation;
}

In the first line of the crossoverPopulation( ) method, a new empty population is created for the next generation. Next, the population is looped over and the crossover rate is used to consider each individual for crossover. (There’s also a mysterious “elitism” term here, which we’ll discuss in the next section.) If the individual doesn’t go through crossover, its added straight to the next population, otherwise a new individual is created. The offspring’s chromosome is filled by looping over the parent chromosomes and randomly adding genes from each parent to the offspring’s chromosome. When this crossover process has finished for each individual of the population, the crossover method returns the next generation’s population.

From here we can implement the crossover function into our main method in the AllOnesGA class. The entire AllOnesGA class and main method is printed below; however the only change from before is the addition of the line that calls crossoverPopulation( ) below the “Apply crossover” comment.

package chapter2;
public class AllOnesGA {
      public static void main(String[] args) {
            // Create GA object
            GeneticAlgorithm ga = new GeneticAlgorithm(100, 0.001, 0.95, 0);

            // Initialize population
            Population population = ga.initPopulation(50);

            // Evaluate population
            ga.evalPopulation(population);

            // Keep track of current generation
            int generation = 1;

            while (ga.isTerminationConditionMet(population) == false) {
                  // Print fittest individual from population
                  System.out.println("Best solution: " + population.getFittest(0).toString());

                  // Apply crossover
                  population = ga.crossoverPopulation(population);

                  // Apply mutation
                  // TODO

                  // Evaluate population
                  ga.evalPopulation(population);

                  // Increment the current generation
                  generation++;
            }

            System.out.println("Found solution in " + generation + " generations");
            System.out.println("Best solution: " + population.getFittest(0).toString());
      }
}

At this point, running the program should work and return a valid solution! Try it for yourself by clicking the Run button in Eclipse and observing the console that appears.

As you can see, crossover alone is sufficient to evolve a population. However, genetic algorithms without mutation are prone to getting stuck in local optima without ever finding the global optimum. We won’t see this demonstrated in such a simple problem, but in more complex problem domains we need some mechanism to nudge a population away from local optimums to try and see if there’s a better solution elsewhere. This is where the randomness of mutation comes into play: if a solution is stagnating near a local optimum, a random event may kick it in the right direction and send it toward a better solution.

Elitism

Before discussing mutation, let’s take a look at the “elitismCount” parameter we introduced in the crossover method.

A basic genetic algorithm will often lose the best individuals in a population between generations due to the effects of the crossover and mutation operators. However, we need these operators to find better solutions. To see this problem in action, simply edit your genetic algorithm’s code to print the fitness of the fittest individual over each generation. You’ll notice that although it will typically go up, there are occasions when the fittest solution is lost and replaced with a less optimal one during crossover and mutation.

One simple optimization technique used to tackle this problem is to always allow the fittest individual, or individuals, to be added unaltered to the next generation’s population. This way the best individuals are no longer lost from generation to generation. Although these individuals don’t have crossover applied to them, they can still be selected as a parent for another individual allowing their genetic information to still be shared with others in the population. This process of retaining the best for the next generation is called elitism.

Typically, the optimal number of ‘elite’ individuals in a population will be a very small proportion of the total population size. This is because if the value is too high, it will slow down the genetic algorithm’s search process due to a lack of genetic diversity caused by preserving too many individuals. Similarly to the other parameters discussed previously, it’s important to find a balance for optimal performance.

Implementing elitism is simple in both crossover and mutation contexts. Let’s revisit the conditional in crossoverPopulation( ) that checks to see if crossover should be applied:

// Apply crossover to this individual?
if (this.crossoverRate > Math.random() && populationIndex >= this.elitismCount) {
      // ...
}

Crossover is only applied if both the crossover conditional is met and the individual is not considered elite.

What makes an individual elite? At this point, the individuals in the population have already been sorted by their fitness, so the strongest individuals have the lowest indices. Therefore, if we want three elite individuals, we should skip indices 0-2 from consideration. This will preserve the strongest individuals and let them pass through to the next generation unmodified. We’ll use the same exact conditional in the mutation code to follow.

Mutation

The last thing we need to add to complete the evolution process is mutation. Like crossover, there are many different mutation methods to choose from. When using binary strings one of the more common methods is called bit flip mutation. As you may have guessed, bit flip mutation involves flipping the value of the bit from 1 to 0, or from 0 to 1, depending on its initial value. When the chromosome is encoded using some other representation, a different mutation method would usually be implemented to make better use of the encoding.

One of the most important factors in selecting mutation and crossover methods is to make sure that the method you’ve selected still yields a valid solution. We’ll see this concept in action in later chapters, but for this problem we simply need to make sure that 0 and 1 are the only possible values a gene can mutate to. A gene mutating to, say, 7 would give us an invalid solution.

This advice seems moot and over-obvious in this chapter, but consider a different simple problem where you need to order the numbers one through six without repeating (i.e., end up with “123456”). A mutation algorithm that simply chose a random number between one and six could yield “126456”, using “6” twice, which would be an invalid solution because each number can only be used once. As you can see, even simple problems sometimes require sophisticated techniques.

Similarly to crossover, mutation is applied to the individual based on the mutation rate. If the mutation rate is set to 0.1 then each gene has a 10% chance of being mutated during the mutation stage.

Let’s go ahead and add the mutation function to our GeneticAlgorithm class. We can add this anywhere:

public Population mutatePopulation(Population population) {
      // Initialize new population
      Population newPopulation = new Population(this.populationSize);

      // Loop over current population by fitness
      for (int populationIndex = 0; populationIndex < population.size(); populationIndex++) {
            Individual individual = population.getFittest(populationIndex);

            // Loop over individual’s genes
            for (int geneIndex = 0; geneIndex < individual.getChromosomeLength(); geneIndex++) {
                  // Skip mutation if this is an elite individual
                  if (populationIndex >= this.elitismCount) {
                        // Does this gene need mutation?
                        if (this.mutationRate > Math.random()) {
                              // Get new gene
                              int newGene = 1;
                              if (individual.getGene(geneIndex) == 1) {
                                    newGene = 0;
                              }
                              // Mutate gene
                              individual.setGene(geneIndex, newGene);
                        }
                  }
            }

            // Add individual to population
            newPopulation.setIndividual(populationIndex, individual);
      }

      // Return mutated population
      return newPopulation;
}

The mutatePopulation( ) method starts by creating a new empty population for the mutated individuals and then begins to loop over the current population. Each individual’s chromosome is then looped over and each gene is considered for bit flip mutation using the mutation rate. When the entire chromosome of an individual has been looped over, the individual is then added to the new mutation population. When all individuals have gone through the mutation process the mutated population is returned.

Now we can complete the final step of the evolution loop by adding the mutate function to the main method. The finished main method is as follows. There are only two differences from the last time: first, we’ve added the call to mutatePopulation( ) below the “Apply mutation” comment. Also, we’ve changed the “elitismCount” parameter in the “new GeneticAlgorithm” constructor from 0 to 2, now that we understand how elitism works.

package chapter2;
public class AllOnesGA {

      public static void main(String[] args) {
            // Create GA object
            GeneticAlgorithm ga = new GeneticAlgorithm(100, 0.001, 0.95, 2);

            // Initialize population
            Population population = ga.initPopulation(50);

            // Evaluate population
            ga.evalPopulation(population);

            // Keep track of current generation
            int generation = 1;

            while (ga.isTerminationConditionMet(population) == false) {
                  // Print fittest individual from population
                  System.out.println("Best solution: " + population.getFittest(0).toString());

                  // Apply crossover
                  population = ga.crossoverPopulation(population);

                  // Apply mutation
                  population = ga.mutatePopulation(population);

                  // Evaluate population
                  ga.evalPopulation(population);

                  // Increment the current generation
                  generation++;
            }

            System.out.println("Found solution in " + generation + " generations");
            System.out.println("Best solution: " + population.getFittest(0).toString());
      }
}

Execution

You’ve now completed your first genetic algorithm. The Individual and Population classes are printed in their entirety earlier in the chapter, and your version of those classes should look exactly like the above. The final AllOnesGA executive class–the class that bootstraps and runs the algorithm–is provided directly above.

The GeneticAlgorithm class is quite long, and you built it piece by piece, so at this point please check that you’ve implemented the following properties and methods. To save space I’ve omitted all comments and method bodies here—I’m just showing a collapsed view of the class–but make sure your version of the class has each one of these methods implemented as described above.

package chapter2;

public class GeneticAlgorithm {
    private int populationSize;
    private double mutationRate;
    private double crossoverRate;
    private int elitismCount;

    public GeneticAlgorithm(int populationSize, double mutationRate, double crossoverRate, int elitismCount) { }
    public Population initPopulation(int chromosomeLength) { }
    public double calcFitness(Individual individual) { }
    public void evalPopulation(Population population) { }
    public boolean isTerminationConditionMet(Population population) { }
    public Individual selectParent(Population population) { }
    public Population crossoverPopulation(Population population) { }
    public Population mutatePopulation(Population population) { }
}

If you’re using the Eclipse IDE, you can now run the algorithm by opening up the AllOnesGA file and clicking the “Run” button, found typically in the top menu of the IDE.

While running, the algorithm will print information to the console, which should automatically appear in Eclipse when clicking Run. Because of the randomness of every genetic algorithm, each run will look a little bit different, but here’s an example of what your output may look like:

Best solution: 11001110100110111111010111001001100111110011111111
Best solution: 11001110100110111111010111001001100111110011111111
Best solution: 11001110100110111111010111001001100111110011111111
[ ... Lots of lines omitted here ... ]
Best solution: 11111111111111111111111111111011111111111111111111
Best solution: 11111111111111111111111111111011111111111111111111
Found solution in 113 generations
Best solution: 11111111111111111111111111111111111111111111111111

At this point, you should play with the various parameters you’ve given to the GeneticAlgorithm constructor: populationSize, mutationRate, crossoverRate, and elitismCount. Don’t forget that statistics rule the performance of genetic algorithms, so you can’t evaluate the performance of an algorithm or a setting with only one run – you’ll want to run at least 10 trials of each different setting before judging its performance.

Summary

In this chapter, you’ve learned the basics of implementing a genetic algorithm. The pseudocode at the beginning of the chapter provides a generic conceptual model for all genetic algorithms you’ll implement throughout the rest of the book: each genetic algorithm will initialize and evaluate a population, and then enter a loop that performs crossover, mutation, and re-evaluation. The loop only exits if a termination condition is met.

Throughout this chapter you built the supporting components of a genetic algorithm, particularly the Individual and Population classes, which you’ll largely reuse in the following chapters. You then purpose-built a GeneticAlgorithm class to solve the “all ones” problem specifically, and ran it successfully.

You’ve also learned the following: while each genetic algorithm is similar conceptually and structurally, different problem domains will require different implementations of evaluation techniques (i.e., fitness scoring, crossover techniques, and mutation techniques).

The rest of this book will explore those different techniques through example problems. In the following chapters you’ll reuse the Population and Individual classes with only slight modifications. However, each following chapter will require heavy modifications to the GeneticAlgorithm class, as that class is where crossover, mutation, termination conditions, and fitness evaluation occurs.