Introduction

The term Genetic Algorithm (or GA) describes a set of methods, which can be used to optimise complex problems. As the name suggests, the processes employed by GAs are inspired by natural selection and genetic variation. To achieve this a GA uses a population of possible solutions to a problem and applies a series of processes to them.

These processes mimic those in nature in such a way that subsequent populations are fitter and more adapted to their environment. As time and generations progress, they become better suited to their environment and given sufficient time provide better more optimal solutions.

Robustness of GAs

... many complex engineering problems ... cannot be optimised analytically

Many problems in engineering are complex ones. This generally means they cannot be optimised analytically. Even when they can be resolved this way, the computational effort is often impracticable due to their complexity.

Alternatively, there are many types of search methods employing a numerical approach. Unfortunately these can lack robustness when confronted with highly complex or unorthodox problems. Attempts made to optimise complex systems using these traditional methods (such as hill climbing) can often fail. Where traditional methods transit carefully from one solution to the next making it very easy for the solution to become trapped in a localised maxima, GAs command a population of solutions, which climb many peaks simultaneously.

The impetus of a GA population to improve is not influenced by local gradients, but by their individual fitness and aptness to their environment. Where the environment is a mathematical landscape of the problem being optimised. This robustness thus gives GAs the ability to outperform more conventional search techniques due to their implementation of adaptive evolutionary approaches.

GA representation of problems

In keeping with the evolutionary theme each individual in a GA population is represented by a chromosome. As in nature this chromosome contains genetic information relating to each individuals characteristics.

For simple genetic algorithms the chromosome is often represented as a binary string, i.e. 101010001112. GAs can make use of this to represent numerical information forming an input value into a system or problem.

For example if an input range was determined to be between 50 and 60, and we decided to use a chromosome length of 10 bits. All the initial population would have binary representations of values distributed between 00000000002 and 11111111112. In base 10 this is every value between 0 and 1023. Mapping these to our input values, a 10 bit chromosome therefore represents all potential input values between 50 and 60 with an accuracy of approximately 0.01.

The algorithm

The basic steps for almost all GAs involves the following:

1 Initialise:

Create a starting population, which represents legal solutions to a problem.

2 Fitness:

Measure the aptness (or fitness) of each individual in the population.

3 Selection:

Using biased randomness select the fittest individuals to survive to the next generation. Note a biased random procedure will tend to select the fittest but will sometimes select weak individuals (see roulette wheel below).

4 Crossover:

Replicate the mating process by crossing over randomly selected individuals. This means exchanging chromosome information.

5 Mutation:

Replicate mutation in the population by selecting an individual (randomly and infrequently) and subtly altering its chromosome pattern.

6 Repeat:

Return to measuring the population fitness (step two above). This constitutes one generation.

Repeating the above algorithm (highlighted in Figure 1) has the effect of improving the overall fitness of the population. Repeated often enough, over say 100 generations or more, will produce fitter, more optimal solutions.

Fitness

We need to ascertain some form of fitness that can be associated with a particular individual. With simple GAs this can just be the value output from a function or a computer model of the system we are trying to optimise.

For more complex problems involving multi-criteria, a fitness measure associated with solution dominance can be used.

Reproduction by selection

To selectively reproduce the population to determine the next generation we use a biased random selection procedure based on fitness. This is implemented using a roulette wheel method.

An imaginary roulette wheel is constructed with a segment for each individual in the population. Figure 2 shows that the size of the segment is based on the aptness of the particular individual. A fit individual will occupy a larger slice of the roulette wheel than a weaker one.

Selection is made by rotating the wheel a number of times equal to the population size. When the wheel stops the individual it points to is selected. This means that fitter individuals will tend to be selected more frequently than weaker ones.

Crossover

Just relying on selection, a population would eventually consist only of the fittest individuals from the initial random population.

To better explore potential solutions GAs employ a crossover operator, which mimics the reproduction process. Two individuals are mated by an exchange of these characteristics, and two child chromosomes are created.

In the simplest form two individuals are selected for mating using a probability factor P_x (0.7 say). A randomly selected set of patterns from the parents are then exchanged to form two child chromosomes. A typical method is shown in Figure 3.

Mutation

A further enhancement to allow chromosomes to explore all aspects of a search space is mutation. The previous operations help to reproduce and improve the level of fitness of a population, however the general form of the characteristics will remain unchanged.

The concept of mutation also mimics nature in that very occasionally (with P_m=0.001 say) a wild-card is played, which causes an upset to the schematic order. Stochastically, this helps to ensure that all possible solutions are potentially investigated.

Typically mutation will involve swapping two randomly selected bits in a chromosome, i.e. 11101000002 will become 11001001002 if the 3rd and 8th bits are selected (see Figure 4).

Application of GAs

Since their development in the late 1980’s GAs have been used to find solutions to many types of problems. Typical early academic problems such as the TSP and the 8 Queens problem soon evolved into more serious engineering applications.

A unique characteristic of GAs is that the fundamental algorithm is unaware of the problem it is optimising. All that is required is that the input parameters into a model or system can be efficiently transformed to and from a suitable GA chromosome format. This means that GA optimisation can be applied to many types of complex problem.

In recent years the scope has increased substantially so that GAs can be used to optimise complex scheduling problems, spatial layout and many other types of complex engineering systems that are otherwise impossible to efficiently maximise.

Author: John Dalton

Contact: john.dalton@ncl.ac.uk