• The Process
• The Reality

Genetic Algorithms: The Process

Initialisation

The initial population M(0) is a randomly generated combination of 1's and 0's encapsulating the 'search space' or the set of possible solution. If more is known about the population a domain can be specified.

Selection

Only the fittest may survive to replicate. Hence a Fitness Function is devised to ascertain which member pairs are allowed to have their solution passed onto the next generation, M(i+1).

Fitness Function:

A Fitness Function determines which pairs are to be chosen for an intermediate population IP that will mate to form the next generation. A root Evaluation function is able to provide a computable evaluation of the suitability of an individuals being a possible solution. As the function is quite essential to the entire process of GA, it must be able to evaluate members with a high degree of accuracy. Consequently poor/loose Evaluation Functions are one of the main limitations of GA.

Evaluation Function: Fitness Function:


Example:

Assume that the average g, over a population is 17
And for individual, c.0, it is: g(c.0) = 25
Then: Fitness f(c.0) = 25/17 = 1.47
Hence: 1 copy will go to the IP and there is a 0.47 another copy will go to the IP

Thus holding the analogy of evolution that only thriving individuals will be chosen to reproduce and from this set, not everyone will reproduce.

Selection Methadologies:

Roulette Wheel and Tournament Selection are among common methods of selecting an individual from the current set that will be passed onto the IP. They are used to create constraints, on an otherwise, 'open' selection process.

• Roulette Wheel:
  The fitness of the individuals is normalised so that, each individuals fitness score is: sum of populations fitness/individuals fitness.
  Hence, the fitness score has been compared to the population and those individuals with highe scores are more likely to be passed to the IP.
  
  
• Tournament Selection:
  Select 2 candidates randomly and compare their fitness score. The one with the greatest score will go to IP. A fixed population GA of size N will require 2N tournaments.
  
  
• Stochastic Tournament Selection:
  Combine the above 2 selection methods, where the individual selected from the Roulette Wheel is passed onto the Tournament

Mating

Member pairs are now ready to share their solutions. The Selected Set, or the Intermediate Population IP, now has a set of potential parents randomly chosen. These individuals are to create, via Reproduction, the next generation M (i+1). Similarly to real life, the proposed individuals success for mating will be determined by a probability function p(C ), such that: not everyone can find a partner. From the Selected set, individuals are randomly chosen to mate with a probability of successful mating of P. Note: The same individual maybe chosen more than once and others not at all. This process will involve recombination of the bit string .

However the mating protocol differs where:

• There is no notion and distinction of sexes.
• The a member of the IP maybe chosen to mate with themselves – possible analogous asexual reproduction

Recombination

The grinding blocks of evolution now takes place, as the individuals which have produced the most promising solution will have sections of their strings combined to form the offspring of the second generation. From the set of Proposed Parents, the selected individuals can recombine their bit strings in 3 possible methods, all of which produce offspring that are the same length due to the, fixed , bit string representation of GA population. Again drawing parallels biological process of reproduction and inheritance, the recombination procedure splices sections of both parents together.

1: One Point Crossover

• Select a random point form first individual and the same point in the second
• The individuals now have a right and left hand side
• LHS of the first is shunted to the RHS of the second
• LHS of the second is shunted to the RHS of the first

2: Two Point Crossover

• Two random points are selected in the first individual splitting it into 3 sections
• Identical points chosen in the second individual
• The middle sections are swapped between the 2 individuals and spliced with the their respective remaining encoding

3: Inversion

• Paralleling asexual biological reproduction
• The selected parent is split into segments
• One of the segments has their encoding reversed

Mutation

The point selection may seem arbitrary, however, recombinations keep large sections of the bit string in tact, meaning, regions that have a high evaluation score are likely to be passed on, especially if this region is quite small.
Even though this process produces a large range of solutions, it may lead the evaluation function towards a local maxima. Hence it is essential for moving out of a local maxima, where analogous to biological evolution, evolution and adaptation has plateaud.
The mutation process occurs at random intervals of the GA. Each bit will be inverted ( 1 -> 0, or, 0 -> 1 ) with a relatively small probability of 0.01, for example.

Termination Check

Continuous iterations of this process will make successive generations inherit the characteristics of the individual that were closest matches to possible solutions in the previous generation ( strongest traits ), thus giving rise to, after many generations, an individual which is an optimal solution - the criterion for the Termination Check. However, if the Check fails to extract an individual that is optimal it will terminate under the default case of time.

About | Home