An Overview of the Genetic Algorithm
Created | Updated Mar 10, 2015
The genetic algorithm is an evolutionary method of computation. It seeks to develop optimum solutions by breedingfit candidate solutions in a population. This probabilistic method has already proved to be useful in many practical fields, including drug and circuit design
The evolutionary nature of the GA makes it highly adaptive. This is a particularly useful facet of the process when the system is faced with a changing environment. Real time control systems may benefit from the adaptive nature of the GA.
GAs are capable of generating and evaluating vast numbers of potential solutions. This is ideal in highly complex systems where there may be no clear trajectory to the optimum solution or where the fitness landscape is multimodal. It also may be of use in chaotic systems, where effects become causes and combinatorial explosion makes the problem intractable to traditional problem solving methods.
They are adept at finding increasingly fit solutions by combining features of existing solutions and allowing the fittest to proliferate whilst pruning the least fit. Again, this makes the GA approach ideal for problems that are prone to combinatorial explosion, as there is no requirement for every point in the search space to be systematically evaluated. Instead the GA relies on probabilistic genetic drift to converge on the optimum solution.
Like evolution, there is no pre-set goal which must be given to the algorithm before setting it in motion. Instead it will develop the fittest solution it can, given the parameters set by the programmer. This is advantageous in that GAs do not require us to know the solution in advance. This allows the solution developed to be truly innovative, sometimes outperforming human experts in the fields of micro circuitry design (A Thompson 1998: Exploring beyond the scope of human design) and drug design (W.J. Feiereisen 2000: Putting Evolution to Work: A new 'genetic algorithm' designs drug molecules automatically)
GAs use knowledge about the field in question to assess the fitness of the solutions available to it, rather than using an external measure, such as differentiation (used by the Hill Climbing search method). Whilst this can be computationally demanding, it helps to ensure the solution developed is fit in terms which are relevant to the problem at hand.
The GA approach is massively parallel, working on many individuals in the population at one time. Whilst the population as a whole will tend to converge on one point over time, individuals in that population each occupy a point in search space as denoted by the values of their chromosomes. Individuals in the population occupying points closer to the optimum should have higher fitness values than those which do not. As a result, the fittest individuals will proliferate, and their offspring will come to dominate the population. It is probable that a proportion of those offspring will occupy points closer to the optimum, and so proliferate in turn, until the maximum is reached.
Finally the rules used by the GA are very simple, consisting only of selection, recombination and mutation. However from these three simple operators, varied and complex behaviours may emerge.
The evolutionary nature of the GA makes it highly adaptive. This is a particularly useful facet of the process when the system is faced with a changing environment. Real time control systems may benefit from the adaptive nature of the GA.
GAs are capable of generating and evaluating vast numbers of potential solutions. This is ideal in highly complex systems where there may be no clear trajectory to the optimum solution or where the fitness landscape is multimodal. It also may be of use in chaotic systems, where effects become causes and combinatorial explosion makes the problem intractable to traditional problem solving methods.
They are adept at finding increasingly fit solutions by combining features of existing solutions and allowing the fittest to proliferate whilst pruning the least fit. Again, this makes the GA approach ideal for problems that are prone to combinatorial explosion, as there is no requirement for every point in the search space to be systematically evaluated. Instead the GA relies on probabilistic genetic drift to converge on the optimum solution.
Like evolution, there is no pre-set goal which must be given to the algorithm before setting it in motion. Instead it will develop the fittest solution it can, given the parameters set by the programmer. This is advantageous in that GAs do not require us to know the solution in advance. This allows the solution developed to be truly innovative, sometimes outperforming human experts in the fields of micro circuitry design (A Thompson 1998: Exploring beyond the scope of human design) and drug design (W.J. Feiereisen 2000: Putting Evolution to Work: A new 'genetic algorithm' designs drug molecules automatically)
GAs use knowledge about the field in question to assess the fitness of the solutions available to it, rather than using an external measure, such as differentiation (used by the Hill Climbing search method). Whilst this can be computationally demanding, it helps to ensure the solution developed is fit in terms which are relevant to the problem at hand.
The GA approach is massively parallel, working on many individuals in the population at one time. Whilst the population as a whole will tend to converge on one point over time, individuals in that population each occupy a point in search space as denoted by the values of their chromosomes. Individuals in the population occupying points closer to the optimum should have higher fitness values than those which do not. As a result, the fittest individuals will proliferate, and their offspring will come to dominate the population. It is probable that a proportion of those offspring will occupy points closer to the optimum, and so proliferate in turn, until the maximum is reached.
Finally the rules used by the GA are very simple, consisting only of selection, recombination and mutation. However from these three simple operators, varied and complex behaviours may emerge.
