Understanding Genetic Algorithms
DATA STRUCTURES AND ALGORITHMS

Understanding Genetic Algorithms

Solving a Battleship board game as an optimization problem

Battleship: The board game. Photo: Amazon¹

A genetic algorithm is a prime example of technology imitating nature to solve complex problems, in this case, by adopting the concept of natural selection in an evolutionary algorithm. Genetic algorithms, introduced in 1960 by John Holland,² extend Alan Turing’s concept of a “learning machine”³ and are best-suited for solving optimization problems such as the traveling salesman.⁴

To intuitively understand the practical implementation and fundamental requirements for employing genetic algorithms, we can set up a toy problem and solve the board of the classic guessing game, Battleship, first released by Milton Bradley in 1967. But rather than calling a sequence of individual shots, let’s ask our genetic algorithm to make a series of guesses of the entire board.

Setting Up the Board

Genetic algorithms can be applied to problems whose solutions can be expressed as genetic representations, which are simply arrays of ones and zeros. Each binary element is called a gene, while an array of multiple genes is referred to as a chromosome. The optimal solution of a given problem is the chromosome that results in the best fitness score of a performance metric.

A Battleship board is composed of a 10 x 10 grid, upon which we can randomly place five ships of varying length. Our fleet includes a carrier (5), a battleship (4), a cruiser (3), a submarine (3) and a destroyer (2). We can express the board as a binary representation simply by denoting the squares occupied by our ships as ones and the unoccupied squares as zeros.

We can randomly position each of our ships by following a few simple steps:

Position the head of the ship with a random two-dimensional tuple. Orient the heading of the ship with a random cardinal direction. Locate the tail of the ship based on its head position, direction and length. Check that the tail of the ship remains within the boundaries of the board. Check that the ship does not overlap with any previously positioned ships. Repeat the process if the ship fails either of the two assertion tests.

Python functions to generate a random Battleship board and evaluate candidate fitness. Source: Author⁵

This results in a two-dimensional binary matrix, which must be transformed into a one-dimensional array that conforms to the genetic form. We can reshape the board by stacking the rows to create a chromosome of 100 genes. Since each gene in the board solution can either be a one or a zero, our toy problem could have been arranged in 2¹⁰⁰ or 1.27e+30 possible ways!

Board Solution in Genetic Form

00001110000000000000000001111000000000000000010000…

00010100000001010000000101000010000100001000000000

Binary representation of Battleship board with 5 ships occupying 17 squares (red 1). Image: Author

Guessing the Entire Board

We can randomly guess the entire board by generating a chromosome with any combination of 100 genes. By guessing that each gene has an equal probability of being occupied (red) or unoccupied (blue), a random sample should be expected to contain 50 occupied squares. By overlaying the guess and the solution (ones & zeros), we can visualize how well they match.

Random chromosome with 51 occupied squares (red) and 49 unoccupied squares (blue). Image: Author

The fitness of a chromosome can most simply be assessed by counting how many genes correctly match those in the genetic solution (green) and then dividing by the total number of genes (green & red). This accuracy rate of our random chromosome is already 52%! Even though there are only 17 occupied squares, any binomial distribution will approach a median accuracy of 50%.

The genetic algorithm can now learn from this fitness metric to suggest an even higher performing chromosome. Fitness functions can be as sophisticated as desired to provide more informative feedback. For instance, we could calculate a confusion matrix,⁶ commonly used in classification problems to account for false positives and false negatives, to return precision and recall.

Accuracy rate of random chromosome with 52 matches (green) and 48 mismatches (red). Image: Author

Now that we know how to create a random chromosome and assess its fitness, let’s create a generation or gene pool of 10 random guesses and observe how well they do. We can sort the chromosomes by level of fitness and label the top performers, which are 57% accurate, as elite. Even though we have only a small sample, the median fitness of the sample distribution is still 52.5%.

Fitness of 10 random chromosomes in generation 1. Image: Author

Creating Descendent Generations

Now that we have established our gene pool, we can use the natural selection concept of survival of the fittest to create a new generation from an old one. The first step is to select the elite chromosomes from the old generation to be parents of the new generation. These parent chromosomes can then create children via two popular genetic operators, known as crossover and mutation.

Elitism

The fittest chromosomes from the former generation that are selected to be parents of all of the chromosomes in a new generation.

Crossover

Two chromosomes can be spliced at a random crossover gene and recombined to create two children, sharing gene chains from both parents.

Mutation

Random genes of one chromosome can be inverted with bit flips to create a single child that exhibits a small genetic variation from its parent.

Let’s create a second generation of 10 chromosomes with a 20% elite rate (two parents), a 20% crossover rate (one pair of spliced children) and a 60% mutation rate (six mutant children). Our bit flip rate is 1%, such that mutants vary from their parents by one gene on average. We can once again sort our generation by fitness and find that our two elites are now 58% and 60% fit!

Fitness of 2 elitism, 2 splice pair and 6 mutation chromosomes in generation 2. Image: Author

What happens if we iteratively repeat this process to create new generations? With each successive generation, we only retain the highest performers and discard non-optimal solutions. By carrying over elites, we guarantee that generational peak performance can potentially increase and never decrease. After 155 generations, a chromosome reaches the solution with 100% fitness!

Fitness of 2 elitism, 2 splice pair and 6 mutation chromosomes in generation 155. Image: Author

Converging to the Genetic Solution

We have fixed the size of each generation to be 10 chromosomes, but the genetic algorithm incorporates randomness in many areas, from our random chromosomes to the crossover genes to the bit flip rate. Statistics of the first 10 generations show how natural selection gradually improves the population fitness, while dispersion is highest in the first random generation.

Fitness distribution statistics for generations 1 to 10. Image: Author

Statistics of the last 10 generations show that each population is extremely fit with the least fit chromosome scoring 95%. As a high fitness chromosome approaches the genetic solution, it becomes more likely that its fitness can only improve by mutating a single gene. Thus, high mutation rates and low bit flip rates give fit generations the best chance of achieving the target solution.

Fitness distribution statistics for generations 146 to 155. Image: Author

We can visualize the performance of the genetic algorithm by plotting fitness statistics across generations. Any random binomial distribution will empower the first generation with 50% fitness. Elitism guarantees that generational peak performance will be monotonically increasing, while crossover promotes substantial initial improvements and mutation pushes them to the top.

Convergence of the gene pool towards the optimal solution over 155 generations. Image: Author

Tuning the Model Parameters

The randomness of the genetic algorithm means that its performance and efficiency will vary over a series of repeated trials. By solving 1,000 games and plotting the distribution of total chromosomes created over all generations, we see that our genetic algorithm will typically find the optimal solution after creating only about 1,700 chromosomes out of 1.27e+30 possibilities!

This performance distribution is specific to the hyper-parameters of our model, which are 10 chromosomes per generation, a 20% elite rate, a 20% crossover rate, a 60% mutation rate and a 1% bit flip rate. In the future, we could optimize the efficiency of our genetic algorithm for this problem by minimizing the convergence rate with respect to these feature parameters.

Performance metric of a genetic algorithm with fixed model parameters over 1,000 samples. Image: Author

The source code written for this analysis is available on GitHub,⁷ which includes a random generator of a Battleship board, implementation of a genetic algorithm and the examples presented in this article. While there are many more details in mastering genetic algorithms, we should feel confident that we understand the fundamentals of this optimization algorithm.

References
['Adam C Dick']
['Technology', 'Artificial Intelligence', 'Machine Learning', 'Data Science', 'Programming']