Understanding and Choosing Genotypes

Genetic Algorithms in Elixir — by Sean Moriarity (30 / 101)

👈 Using Behaviours to Model Problems | TOC | Solving One-Max for the Last Time 👉

One of the most important decisions you can make when using a genetic algorithm is the type of encoding you use to represent solutions. Encodings are simply representations of a single solution. A good encoding needs to contain only the information necessary to represent a complete solution to a problem. If a solution is a path through a grid, an encoding of a solution would only need to contain the coordinates of each gridpoint it passes through.

The type of encoding scheme you use is known as a genotype. The genotype of a chromosome tells you what the chromosome should look like. It defines your search space. For example, if you’re trying to create an optimal shipping route through fifteen cities, your genotype is a permutation of all fifteen cities.

While the genotype is the internal representation of solutions, the phenotype is the expressed representation of solutions. The following figure illustrates the relationship between genotype and phenotype:

You don’t need to understand the distinction between genotype and phenotype. It’s just some useful terminology.

Out of a number of different genotypes, this book will use three — binary, permutation, and real-value — because these are the most common and sufficient for fully understanding genetic algorithms. You’ll also meet a fourth — tree-based — because it’s relatively common, but you won’t use any in this book.

Binary Genotypes

Binary genotypes, or bitstrings, are genes consisting of only 1s and 0s. This is the genotype you used to represent solutions to the One-Max problem. The binary genotype is the most common genotype because you can apply it to such a wide variety of problems. One example of how you can use binary genotypes is in representing different characteristics. Each gene can represent the presence of a single characteristic — either with a 1 or a 0. You can even use binary genotypes to represent continuous values.

Binary Genotypes

INFORMATION

The binary genotype or bitstring was the original intended solution representation in the original genetic algorithm. For a long time, the use of a binary genotype is one thing that helped differentiate genetic algorithms from other evolutionary algorithms like evolution strategies. Some might argue that an algorithm can’t reasonably be considered a genetic algorithm if solutions aren’t encoded as bitstrings. Most of the time, however, this distinction doesn’t matter.

Permutation Genotypes

The second most common genotype is permutations. Permutations are especially effective for scheduling problems or finding paths in a finite set of points. The types of problems involving permutation genotypes are called combinatorial optimization. Combinatorial optimization problems look for ordered solutions. The traveling salesman problem is an example that you can implement using a permutation genotype. Each city is encoded as a number and the path is an order of cities. One limitation of permutations is the type of mutation and crossover that you can use. It’s especially difficult to create new chromosomes that maintain the integrity of the permutation.

Real-Value Genotypes

The last genotype you’ll see in this book is the real-value genotype. Real-value genotypes represent solutions using real values. This “real value” could be a string, a float, a character, and so forth. This is especially common for problems involving weights of some sort or where you need to generate a string. Real-value genotypes are less common, but they prove useful when you need to optimize parameters of some sort.

Why Real-Value Genotypes?

INFORMATION

As mentioned before, you can use binary genotypes to represent pretty much anything. So why is it necessary to have real-value genotypes? One reason is precision. When you manually encode and decode continuous values as binary genotypes, you lose access to the floating-point precision implemented natively on your machine. Additionally, the use of real-value genotypes can simplify your code, as you don’t have to worry about manually encoding and decoding solutions.

Tree/Graph Genotypes

One particularly interesting genotype that you’ll encounter is a tree-based or graph genotype. The most common application of tree genotypes is in genetic programming. Genetic programming is a branch of evolutionary computation in which one tries to evolve programs to achieve a desired result. The idea is that you can teach a computer to program itself. In these cases, solutions are typically represented as syntax trees representing valid programs. As interesting as they are, there’s little evidence that shows genetic programming is of any tangible use. It’s difficult to evolve solutions so that they remain valid, and other techniques out there perform better on programming tasks.

👈 Using Behaviours to Model Problems | TOC | Solving One-Max for the Last Time 👉

Genetic Algorithms in Elixir by Sean Moriarity can be purchased in other book formats directly from the Pragmatic Programmers. If you notice a code error or formatting mistake, please let us know here so that we can fix it.