Genetic Algorithms: Hypotheses and Genetic Operators
Genetic algorithm-Hypotheses
Hypotheses in the genetic algorithm are defined by bit strings whose interpretation depends on the application. To find the appropriate hypotheses, we need to begin with a population of the initial hypotheses. Operations such as random mutation and crossover help the current population to give rise to the next generation. The best hypotheses in the genetic algorithm are defined on the basis of fitness, it is the one that optimizes predefined numerical measures for the problem at hand. It is known as the hypotheses fitness.
What is the population?
Subsets in the solution of the current generation are known as population. Some things we should keep in mind while discussing population in the genetic algorithm are as follows:
- If the diversity of the population is not satisfied, it may lead to premature convergence.
- If the population size is too small, then a satisfactory mating pool might not be available, while a larger population can slow down the genetic algorithm. Therefore, the population size should be set in an optimal way to avoid these situations.
There are two methods of population initialization:
1. Random initialization
The initial population is populated with completely random solutions.
2. Heuristic initialization
A known heuristic is used to populate the initial population.
Representation of hypotheses
Hypotheses are represented using bit strings so that the manipulation by genetic operators is easier.
It is further explained through the following example:
Consider an outlook, that can have any of the following three values: sunny, overcast, or rain.
Then let the string 010 represents (Outlook = Overcast)
String 011 represents (Outlook = overcast or rain)
String 111 represents the general constraint.
Genetic operators
1. Crossover operator
The crossover operator copies selected bits from the parent to produce two new offspring from the two-parent string.
An additional string known as the crossover mask helps predict the choice of parent responsible for the bit position i, this bit position i is copied from one parent and used as the bit position for the offspring.
The main types of crossover operators are as follows:
1. Single point crossover
Single point crossover constructs the crossover mask in such a way that it starts with strings containing n contiguous 1s, which is followed by certain numbers of zeros to complete the string.
2. Two-point crossover
Two-point crossover creates offsprings by substituting intermediate segments of the parent into the middle of the second parent string, implying two offsprings are created by two parents by switching the roles.
3. Uniform crossover
It combines bit samples uniformly from the parent to create the offspring.
The crossover mask in the uniform crossover is generated as a random bit string that is independent of others.
2. Mutation
Mutation uses only one single parent to produce offspring.
The mutation operator chooses one single bit at a time to make small random changes to the bit string and is mostly performed after the crossover is already applied.
Reference