Genetic Algorithms

If you find the post useful,kindly acknowledge the above source and not this blog. This post has been reproduced here as a study material for my students. No commercial activity is involved.

Genetic Algorithms(GA) were developed in the early 1970's by John Holland and are search and optimization algorithms which mimic some of the processes of natural selection and evolution as propounded by Charles Darwin.

Charles Darwin (1809-1882)

Different search methodologies used at present are given in the Chart below

(click on the fig. to enlarge it)


GA perform directed random search through a given set of alternatives/solutions with the aim of finding the best solution according to given criteria. These criteria or constraints are defined in terms of an objective function and usually the problem takes the form of maximizing or minimizing this function. The objective function is referred to in GA terminology as the fitness function. The main feature of GA is that the set of alternatives/ solutions must be coded in some particular format as a string (of bits,alphanumeric combinations etc.) through a process called encoding .

Eg. let one of the solutions to the problem be a value '7' then by using a binary encoding technique we can represent this as a 4 bit value '0111' (I will explain the encoding process in detail in future sections).

These encoded strings are then called chromosomes and the individual elements that make up the chromosome are referred to as genes. In the example stated above: 0111 is the chromosome and each individual bit is the gene.
Now each chromosome represents an alternative/solution and GA then takes a set(referred to as population) of chromosomes and applies genetic inheritance operators to that set of chromosomes to generate offsprings that compete with other strings in the given set for survival to the next generation of population.

The basic working of a GA is illustrated through the flowchart given below:


(click on the fig. to enlarge it)


If you cannot understand still, look at the figure below:

(click on the fig. to enlarge it)

In general, GA go through 4 steps:

1. Encoding
2. Reproduction/Selection
3. Crossover
4. Mutation

1. Encoding:

2. Reproduction/Selection:

2.1 Roulette Wheel Selection

Roulette wheel: the size of each slice corresponds to the fitness of the appropriate individual.

(click on the fig. to enlarge it)

Steps for the roulette wheel

1. Sum the fitnesses of all the population members, TF
2. Generate a random number m, between 0 and TF
3. Return the first population member whose fitness added to the preceding population members is greater than or equal to m




(click on the fig. to enlarge it)


2.2 Tournament selection1. Randomly choose a group of T individuals from the population.
2. Select the best one.

How to guarantee that the best member of a population will survive?

2.3 Elitist model of selectionThe best member of the current population is set to be a member of the next.
3. Crossover

1. Combine two individuals to create new individuals for possible inclusion in next generation.

2. Main operator for local search (looking close to existing solutions)

3. Perform each crossover with probability Pc {0.5,…,0.8}

4. Crossover points selected at random.

5. Individuals not crossed carried over in population.

Crossover Techniques

1. Single-Point (1-Point) Crossover

• Choose a random point on the two parents

• Split parents at this crossover point

• Create children by exchanging tails

• Pc typically in range (0.6, 0.9)

l

Performance with 1 Point Crossover depends on the order that variables occur in the representation

– More likely to keep together genes that are near each other

- Can never keep together genes from opposite ends of strings

- This is known as Positional Bias

- Can be exploited if we know about the structure of our problem, but this is not usually the case

2. 2-Point Crossover

3. n-Point Crossover

• Choose n random crossover points
• Split along those points
• Glue parts, alternating between parents
• Generalisation of 1 point (still some positional bias)

3.1 Even point Crossover

3.2 Odd point Crossover

4. Uniform Crossover

• Assign 'heads' to one parent, 'tails' to the other
• Flip a coin for each gene of the first child
• Make an inverse copy of the gene for the second child
• Inheritance is independent of position