Mike Holman

Introduction
This article is intended to be a simple introduction to search and optimisation using genetic algorithms. Hopefully someone will find it useful. This is part one in a series of posts.

Genetic algorithms are algorithms which mimic concepts from evolutionary biology in order to perform some search or optimisation function. First of all, let’s look at what is meant by search and optimisation by way of an example.

Imagine that you are the pilot of an airliner. The efficiency of your aircraft is related to the altitude at which you cruise. If you fly too low, the air is dense and the resulting increase in drag will cause you to use more fuel to maintain your crusing speed. Conversely if you fly too high where the air is much thinner, the engines will not have enough air to operate effectively and you will also use more fuel than is necessary to get to your destination. Somewhere between these two extremes lies an optimal altitude at which flying any higher or lower would result in more fuel being used.

Knowing this altitude is advantageous as it gives the airline an economic advantage compared to less well informed competitors. If it is using less fuel, its operating costs are lower making the business more competitive. In fact many airlines monitor the flight paths of all their airliners, and will reprimand pilots who deviate from a fuel efficient route without good reason.

Now we know why we are trying to find this altitude, we need a method to go about it. If you were to draw this relationship between efficiency (on the vertical axis) and cruising altitude (on the horizontal axis) you would end up with a graph that resembled the following:

Looking at the graph above, we can immediately see that it is shaped like a hill. By tracing a horizontal line from the top of the hill to the vertical axis, we can determine the maximum efficiency that our aircraft can obtain. If instead, we dropped a vertical line from the top of the hill to the horizontal axis, we can see at what altitude this maximum efficiency occurs – the optimum cruising altitude. The graph is described by the following function (which in this example may be provided by the engine’s manufacturers):

This equation serves as a model for our system. As we have the mathematical function which describes the altitude-efficiency relationship, elementary calculus provides us with the tool to find the optimum altitude analytically. If we differentiate the original function, we are left with a new function which describes the slope of the tangent to the original function for any given point on the horizontal axis. In plain English, this means we can find the rate at which the efficiency is changing at any point on the graph.

Plotting this equation on our existing graph gives the following:

Clearly, the line created by the new equation crosses the horizontal axis directly underneath the optimal efficiency (the “hill top”) indicated by the original function. The point where this line crosses the horizontal axis tells us the optimal cruising altitude for our aeroplane. To find this point, we solve the equation for dy/dx = 0 (or in plain English, find the altitude at which the rate of change of the efficiency is zero, where it has stopped increasing but has not yet started to decrease):

Therefore the optimum altitude for efficient flying is 36 (thousand feet). Putting this value back into our original model tells us that the efficiency at the optimum altitude is also 36 (miles per gallon). Adding the above line to our graph helps to make the relationship clear:

In this example we were searching for the optimum altitude for efficient flight. Because we had a known function relating altitude and efficiency, with a single optimal value, which was also easy to differentiate, we were able to find the optimum value using analytical methods.

In the next post we will look at some more complicated examples which are not so simple to solve!