Genetic algorithms (GA) can be seen as an unusual kind of search strategy. In GA, there is a set of candidate solutions to a problem; typically this set is initially filled with random possible solutions, not necessarily all distinct. Each candidate is typically an ordered fixed-length array of values (called alleles) for attributes (genes). Each gene is regarded as atom in what follows; the set of alleles for that gene is the set of values that the gene can possibly take. Thus, in building GA for a specific problem the first task is to decide how to represent possible solutions.
Suppose we have thus decided on such a representation, GA usually proceeds in the following way:
1. Initialization: A set of candidate solutions is randomly generated. For example, if the problem is to maximize a function of x, y and z, the initial step may be to generate a collection of random triples if that is the chosen representation.
2. Iteration: through the following steps, until some termination criterion is met (such as no improvement in the best solution so far after some specified time, or until a solution has been found the fitness of which is better than a given adequate value).
The process alters the set repeatedly; each set is commonly called a generation.
1. Evaluation.
Using some predefined problem-specific measure of fitness, we evaluate every member of the current set to determine good a solution of problem can be. The measure is called the candidate’s fitness, and the idea is that fitter candidates are, in some way, closer to be one of the solutions we are seeking. However, GA do not require that fitness is a perfect measure of quality; they can, to some modest extent, tolerate a fitness measure in which the fitter of some pairs of candidates is also the poorer as a solution.
2. Selection.
Select pairs of candidates solutions forms the current generation to be used for breeding. This may be done entirely randomly, or stochastically based on fitness.
3. Breeding.
Produce new individuals by using genetic operators on the individuals chosen in the selection step. There are two main kinds of operators:
a. Crossover: A new individual is produced by recombining features of a pair of parents solutions.
b. Mutation: A new individual is produced by slightly altering an existing one.
4. Population update.
The set is altered, typically by choosing to remove some or all of the individuals in the existing generation (usually beginning with the least fit) and replacing these with individuals produced in the breeding step. The new population thus produced becomes the current generation.
Figure: A basic genetic algorithm
GA are a class of stochastic search algorithms based on biological evolution. A basic GA can be represented as in Figure. GA applies the following major steps by Mitchell (1996) and Negnevitsky (2005):
Step 1: Represent the problem variable domain as a chromosome of a fixed length; choose the size of a chromosome population, the probability of crossover rate and the probability of mutation rate.
Step 2: Define a fitness function to measure the performance, or fitness, of an individual chromosome in the problem domain. The fitness function establishes the basis for selecting chromosomes that will be mated during reproduction.
Step 3: Randomly generate an initial population of chromosomes of population.
Step 4: Calculate the fitness of each individual chromosome.
Step 5: Select a pair of chromosomes for mating from the current population. Parents chromosomes are selected with a probability related to their fitness. Highly fit chromosomes have a higher probability of being selected for mating than less fit chromosomes.
Step 6: Create a pair of offspring chromosomes by applying the genetic operators - crossover and mutation.
Step 7: Place the created offspring chromosomes in the new population.
Step 8: Repeat Step 5 until the size of the new chromosomes population becomes equal to the size of the initial population.
Step 9: Replace the initial (parents) chromosomes population with the new (offspring) population.
Step 10: Go to Step 4, and repeat the process until the termination criterion is satisfied.
Reference
.
Step 1: Represent the problem variable domain as a chromosome of a fixed length; choose the size of a chromosome population, the probability of crossover rate and the probability of mutation rate.
Step 2: Define a fitness function to measure the performance, or fitness, of an individual chromosome in the problem domain. The fitness function establishes the basis for selecting chromosomes that will be mated during reproduction.
Step 3: Randomly generate an initial population of chromosomes of population.
Step 4: Calculate the fitness of each individual chromosome.
Step 5: Select a pair of chromosomes for mating from the current population. Parents chromosomes are selected with a probability related to their fitness. Highly fit chromosomes have a higher probability of being selected for mating than less fit chromosomes.
Step 6: Create a pair of offspring chromosomes by applying the genetic operators - crossover and mutation.
Step 7: Place the created offspring chromosomes in the new population.
Step 8: Repeat Step 5 until the size of the new chromosomes population becomes equal to the size of the initial population.
Step 9: Replace the initial (parents) chromosomes population with the new (offspring) population.
Step 10: Go to Step 4, and repeat the process until the termination criterion is satisfied.
Reference
.
