Genetic Algorithms

Some problems for which we want to find an optimum solution for are simply too complex and time consuming to solve using conventional techniques. Genetic algorithms are a mathematical tool often used to solve such problems. Rather than trying to understand why certain complex behaviour is observed as it is and then calculating a formula to calculate the optimal solution, we simply use a mathematical process, which works like genetics in the real world.

Evolution occurs in our world because nature is made up of many types of interacting agents (which could be people, plants, cities, etc.) each seeking to increase their level of fitness within the environment in which they live. Agents which do not have enough fitness will diminish, fail to reproduce to the next generation, or even die out altogether. Agents that are fit, tend to grow and prosper and reproduce more into the following generation. This way the whole population tends to become increasingly fit for the environment in which it exists.  That is, it seeks out the optimal strategies to cope with the problems that confront them. Just as nature does not need to know the rules of nature to evolve an efficient genetic solution, we do not need to fully understand the problems we are seeking to solve using genetic algorithms.

A genetic algorithm mimics the ways a population uses evolution to find optimal solutions using mathematical means rather than genetics.

Sometimes we will seek an optimal maximum solution, such as a company wishing to maximise its profit in a competitive business environment. At other times we want to find a minimum solution such as a country wishing to formulate a policy to reduce pollution.

We therefore create a virtual population of agents who will live in a virtual world, which includes the problem to which we seek a solution. Let us take a simple example. If you remember back to your school day mathematics, you may remember making graphs of mathematical equations. Below is the graph of the function y= x²+3. In this simple example, we can easily see that the optimum minimum solution is the point (0,3) because it is the lowest point on the graph where the condition y=x²+3 is met.

The optimal solution is rarely this simple, so using a genetic algorithm, we send out lots of agents to various points on the graph which are chosen at random to see how fit they are in terms of the solution we seek. Any points which are not on the line y=x.2+3 are immediately discarded as not fit. Of those that are fit, we check to see how low the value of x is. We know for this system, the nearer it is to zero, the more fit the agent. We can then use various techniques to further refine our search, such as hill climbing. Once we have found one good point, perhaps at (2,7), we try a point either side of it to test whether it returns an even better value. If we take a lower value of y, say 1 and find the x value is 4, which is better because it is less than 7.  We would then take an even lower point, say 0.5 and would find it even more fit at with the x value of 3.25. We might then overshoot and guess -1, which would give us an x value of 4. Because we have a lower value that 4 we check values of x between –1 and 1 We would then take a value in between, say 0.25, which we would find to be better. We can continue many times (i.e. over many generations) to evolve the best solution. While we might not get the exact maximum solution, but this method can find very close solutions to the optimum in surprisingly short times.

We have used a very simple example, which very seldom matches problems we find in the real world. It would be easy to get trapped into thinking we had found the best maximum, the global maximum, when in fact we had only found a local maximum. So when we have found a good maximum, it is often worthwhile to keep looking because an even more efficient solution may well be found. It can therefore be useful to continue to add some more random guesses as we go in case we have missed the optimal point entirely in our first random assigning of agents. In many real world problems there can be millions, billions, or even trillions of possible solutions, so that even a random sample of agents struggles to get a good coverage of the problem space.

We can also imagine the same situation depicted as a fitness landscape with hills and valleys. We wish to find the optimal place on the landscape. It is similarly easy to get stuck at a local maximum point so that much energy would need to be exerted to go from one position, which is already quite optimal to find a place that might be even more optimal. Again the system is not foolproof and can miss the global maximum or even the best local optimum, but it is often a more efficient and speedy means of generating a fit solution to the problem at hand without necessarily knowing anything about the system we are trying to maximise.