Genetic Algorithms

As we’ve said, genetic algorithms mimic evolution. These algorithms almost literally emulate the biological process.

DNA molecules are the building blocks of life. They’re formed by four different types of components that we’ll call A, C, T, and G. We can think of DNA as a sequence of these four letters. A little change in this sequence (changing one of the letters for others) is called a mutation, and can have an enormous impact on the individual.

For example, cancer is provoked by mutations. But mutations are also responsible for the lifeforms we can see today, including ourselves. Mutations are responsible for evolution.

A new individual (plant, cell, human, etc.) has one part of the DNA of each of its progenitors. In this new individual, both progenitors’ DNA segments coexist and are combined to create a unique new chain and, therefore, a unique new life.

In genetic algorithms, we’re going to incorporate these two operations: the mutation in one solution and the crossover of two solutions to create a new one.

Evolution defends the theory that those individuals that had advantageous mutations, prevailed (survived until our days). In the same way, in genetic algorithms, the best solutions are preserved for the next iterations. To assess the quality of a solution, we use a score or fitness function. This strategy of preserving the best solutions (the solutions with higher values in the score function) for the next generations is called elitism.

Let’s explore the details of genetic algorithms.

Definition of generic algorithm

We can define mutations and crossover operations between solutions to any problem. For example, anything in a computer can be represented using zeros and ones. A mutation in a genetic algorithm can be swapping a zero for a one, or vice versa. For example:

• Given a solution $s_0 = 110100$.
• A possible mutation is $s_1 = 100100$.

Note how the second one became a zero.

A mutation is any operation that modifies the solution in some way. We can add one to the solution, alter the sign, or multiply by some value. Any way of changing a solution can be considered a mutation; but most of the time, we assume that a mutation doesn’t drastically change a solution. We assume that big changes are the result of the application of many mutations during the execution of the algorithm.

Crossover operations transform two solutions into one. We can sum up both solutions, mix their components when the solutions are vectors, mix the bits of the solutions, and/or make any other operation with the parent solutions. This is the equivalent of reproduction in the real world, where two individuals combine their genetic material to create a new unique individual. Any function that takes two solutions and returns a new solution can be considered a crossover. As it happens in the real world, most of the time we define crossover operations in a way that the new solution shows some of the properties of its progenitors.

Besides the mutation and crossover operations that are responsible for producing new generations of solutions, we also need a way to compare two solutions under some quality criterion. Given a set of solutions, how do we know which is the best solution between them (i.e., the solution that’s nearer the optimum)? We usually use a score or fitness function. This is normally defined as a positive function so that the bigger the score, the better the solution. This way, we have a measure of how good a solution is and we can keep the best solutions for the next generations. This strategy is called elitism, where only the best solutions are considered for crossover and for further iterations.

In genetic algorithms, we have a target function $f$ we want to optimize, a score function $g$ ...