STOCHASTIC SEARCH ALGORTITHMS-I & II

Question 1

What is combinatorial explosion

Answer 1

combinatorial explosion refers to the rapid increase in the number of possibilities or potential solutions.

Question 2

Write formula for Maximising and Minimising

Answer 2

Max –> 1 / (1 + exp( ΔE / T ) )

Min –> 1 / (1 + exp( -ΔE / T ) )

Question 3

Explain Selection, Crossover and Mutation

Answer 3

Selection –> Parent selection is a crucial process of selecting parents which mate and recombine to create off springs for the next generation. Parent selection is very crucial to the convergence rate of a GA.

Crossover –> 2 or more parents are selected and one or more off springs are produced. This is Exploration.

Mutation –> This is a small random change in the chromosome, to get a new solution. This is exploitation.

Question 4

Discuss the types of Crossovers

Answer 4

One Point Crossover –> A random point is selected and the tail of the two parents is swapped.

Multi Point Crossover –> 2 or more points are selected, and the selected segments are then swapped.

Uniform Crossover –> we flip a coin for each chromosome to decide whether or not it’ll be included in the off-spring.

Question 5

Explain the Fitness Proportionate Selection

Answer 5

Every individual can become a parent based on how fit they are. This is of two types-
i) Roulette Wheel Selection
ii) Stochastic Universal Sampling

Question 6

Explain Roulette Wheel Selection

Answer 6

Each individual is given a fitness value and a circular wheel is created n pies, the size of these pies is proportionate
to the fitness value of each individual.

Then the wheel is rotated, the selected individual is the parent. This is repeated until the desired number of parents are selected.

Question 7

Explain Stochastic Universal Sampling

Answer 7

This is similar to roulette wheel selection, but here multiple parents are selected in just one spin.

Question 8

Explain Tournament Selection