The Genetic Algorithm Framework – Part 1

Introduction

Genetic Algorithms (GAs) are the nearest thing a software developer can get to magic. Watching a solution to a problem ‘evolve’, is awesome.

This article is a very simple description of the techniques used when implementing Genetic Algorithm and is intended as a very simple introduction for those not familiar with the science. In future articles, I will create GAs in C# using the Genetic Algorithm Framework for .NET (GAF). The GAF is a GA framework that makes it easy to create and modify GAs. It was written from first principles in 2013 in order to fully understand the workings of GA systems. The GAF was part of a project run in conjunction with the De Montfort University, Leicester, UK. The great thing is, as I have done all of the hard work, you don’t have to. The GAF brings all of that GA science and functionality to your project in an extremely easy to use form. However, I will leave details of the GAF for the next article. For now, we will look at a simple example, in order to understand some of the concepts.

An Example

If you find yourself saying, “I have no idea how to solve this, but I will recognise a good solution when I see one”, then a GA could be the answer. Being able to identify a good solution is paramount to making them work.

Let’s have a look at an example. GAs have been known to improve the design of aeroplane wings. Aeroplane wings have a lot of different parameters, Leading edge shape, width length and another thousand or so that make little sense to me. The great thing is, that with each design of Aeroplane wing we can, within a few milliseconds, model it in software and give it a score that represents how good it is. We can leave all the wind tunnel stuff until much later in the design process. The point here is that we, with the help of modelling software, will recognise a good aeroplane wing when we see one.

So, for our example, we can use a GA to create wings and software to measure how good they are.

How the GA Works

The genetic algorithm is an evolutionary approach to computing, inspired by Darwin’s theory of evolution and biological reproduction, that has the power to determine approximate solutions to optimisation problems. Evolutionary computation has its roots in the 1960s. However, the genetic algorithm that is used as the basis for research today stems from the work of John Holland in the 1980s.

Holland believed that if the features of natural evolution could be incorporated into a computer algorithm, a new way to solve difficult problems could be created. Holland’s work involved manipulating strings of ’1’s and ’0’s which he called Chromosomes.

The basic process adopted by GAs typically involves creating an initial set of random solutions (population) and evaluating them. Following a process of selection, the better solutions are identified (parents) and used to generate new solutions (children). These can be used to replace lesser members of the population. This new population (generation), is re-evaluated and the process continues, reproducing new generations until either a final solution is determined or some other criterion is reached.

GAs borrow their terms from the biological world. For example, GAs use a representation for potential solutions referred to as a chromosome and the operators that are used to create new child solutions such as crossover and mutation are derived from nature.

In their original and most basic form, GAs were used mainly for single objective search and optimisation algorithms. Common to most GAs is the use of a chromosome, genetic operators, a selection mechanism and an evaluation mechanism.

In our case as Aeroplane wing designers, all we have to do is determine the parameters we need in order to build a wing (for this, we ask an expert) and bundle them into a binary string, this will be the definition of our chromosome. Therefore, each chromosome will fully describe an aeroplane wing. The GA will do the rest.

Given that we have a definition of a chromosome, and that this describes an aeroplane wing, we can make aeroplane wings until the cows come home. We can, for example, create lots of random chromosomes in the hope that one of them make a useful wing. I know it sounds daft, the truth is this is kind of what we do.

A common approach when using GAs is to start by making a ‘population’ of random chromosomes (wings) perhaps a 100. You may remember earlier that we said we can test each one and score it, or to use the correct terminology, ‘evaluate its fitness’. Whilst it is very unlikely that any of our randomly created wings will actually be good enough to put on an aeroplane, some will be marginally better than others. Here is where the magic happens.

The Magic

Of our population of 100 chromosomes (aeroplane wings), we select some ‘parents’ and use them to make ‘children’. We then test these and add these to our population. Finally, we remove all the worst chromosomes leaving our population back at 100. To be honest, there are numerous ways to do what has just been described, but for now, we will keep it simple. The upshot is that our new ‘generation’ of aeroplane wings has become stronger. Do this a few hundred times and we end up with some pretty good aeroplane wings.

Making Children

There are many techniques for selecting parents and using them to make children. However, for the purposes of this description, we will assume we have a mechanism for selecting two suitable chromosomes as parents. We then use these parents to make two new chromosomes (children). Remember that each chromosome, in this example, defines an aeroplane wing. We are making child wings from parent wings.

As we have already stated, each wing is defined by a chromosome. A chromosome can take many forms, however, typically a binary string is used. Creating a binary string chromosome can be as simple as converting all of the aeroplane wing parameters into binary numbers and joining them all together. One simple way to create two children from two parents is to pick a random position within the binary string and ‘crossover’ the chromosomes. This gives two new chromosomes, see Fig. 1.

With a population of 100, we would do this 50 times and perhaps keep the best 100 chromosomes, the rest we delete or ‘kill’. We do not care if the chromosomes to be deleted are the new children, this is quite normal as many new children will be worse than their parents. We simply keep the best chromosomes, whoever they are. It can be a cruel GA world.

If the ability to create an aeroplane wing from simply carving up a few binary strings seems far fetched, then you are in for a treat. As I said before, GAs are the nearest thing to magic that a software developer can get.

Further Reading

If all of this is interesting, stay tuned. In the next article, I will start coding a simple GA in C# using the GAF. The GAF makes this a simple task. In addition, the structure of the GAF and the way in which it is used, helps in understanding the concepts further.

If you want to dive straight in, the GAF is available as a NuGet package.

PM> Install-Package GAF