The basic algorithm for a GA

Image of: Fig 1. The basic Genetic Algorithm

Fig 1. The basic Genetic Algorithm

The algorithm

The basic algorithm by which GAs operate is reasonably well established. The above figure shows the generic one used by most, although some variations may occur depending on the application. In general the particular methods employed in each of the above stages do not matter. What is important is that the general algorithm is followed and the evolutionary techniques that underlie it are understood. The following sections discuss the need for each of these steps in terms of their relevance to evolutionary processes.

Population

A population is initiated of legal solutions, selected by choosing random input values. There are no fixed rules for how large the population should be. The answer is dependent upon the type of problem. For a simple problem with a regular search space a small population of 40 to 100 will probably be sufficient. For larger more complex problems and especially those with an irregular search space larger populations of 400 or more are recommended. The clue is diversity a diverse population, i.e. a large one will tend to search out niches in engineering terms that means finding elusive, difficult to find solutions to problems.

Fitness

The fitness of individual chromosomes is a relative matter. For example when maximising a function; if one individual has a higher value, once processed by the function, than another then that individual is considered fitter. Things get a little more involved with multi-criteria problems. In these cases comparisons can be carried out to see if an individual dominates other members of a population by taking all criteria into consideration. If they do they are considered fitter. The most dominant, i.e. those who dominate all others, are referred to as Pareto solutions. These are considered as candidate solutions to whatever problem you are trying to solve.

Selection of the Fittest

Roulette Wheel selection process

GAs operate over a number of generations. Following the evolutionary theme of this method, this means fitter solutions will tend to survive to the next generation. The selection method employed by many approaches is the roulette wheel selection process. In nature all individuals have a chance of surviving from one generation to the next fitter solutions (i.e. those most dominant) have a better chance. Weaker more dominated individuals have a smaller chance (still an opportunity) of surviving.

more on the Roulette Wheel section process

Crossover

Crossover operator

Nature generates the next generation using a mating process. As a result two parents create offspring, who consist of the genetic material of both parents. These offspring can be weaker or fitter than their parents (or similar). If they are weaker they will tend to die out if they are stronger their chances of survival are better. GAs try to replicate this using a crossover operator. This emulates the mating process by exchanging chromosome patterns between individuals to create offspring for the next generation.

more on the Crossover operator

Mutation

Mutation operator

Mutation exists in nature and causes an unanticipated change in a chromosome pattern. This can result in a much weakened individual and occasionally a much stronger one. Either way the principle behind mutation from an evolutionary point of view is that it occurs rarely, spontaneously and without reference to any other individual in the population. If the change is beneficial to the general population then that individual will tend to survive and will pass this trait on in future replication processes. Because of the way that GAs represent individuals this process is a very simple one and a typical mutation operator is relatively easy to implement. It is important to remember that these processes occur very infrequently otherwise they would have a disruptive effect on the overall population.

more on the Mutation operator

There are no definitive methods of establishing how many generations a GA should run for. Simple problems may converge on good solutions after only 20 or 30 generations. More complex problems may need more. It is not unusual to run a GA for 400 generations for more complex problems such as jobshops. The above figure suggests 100 generations. The most reliable method of deciding on this is trial and error, although a number of authors have suggested methods for determining how long a solution should live.

Contact the EDC

For further details of the EDC's activities please get in touch with us through our contact page.

Commercial Research at Newcastle University

A full list of commercially available research facilities for Newcastle University can be found on the Services for Business web pages.