Week 5: Stochastic Local Search - Simulated Annealing, Genetic Algorithms

Question 1

Simulated Annealing

Answer 1

This algorithm mimicks the mechanics of how molecules of heated metal form into shape as the metal cools down.

For phase k, iteration length k times.

Within the loop, use a neighbourhood generator function to make a new configuration. If the new configuration is better than the current best configuration, accept the configuration. Otherwise, accept it if a random number ranging from 0 to 1 is less than exp((c(config) - c(new config)/T_k). Note that T_k decreases with each subsequent phase.

Question 2

Genetic Algorithms

Answer 2

Parameters:
Prob(h) = selection function for individual h
k = population size in each generation
r = fraction of the population generated by crossover
q = mutation rate
P = the initial population of size k, generated randomly
Select (1-r) x k probabilities with respect to Prob(h) to pass on to the next iteration.
r x k pairs are selected to generate offspring using crossover.
q x k individuals are generated using mutation.

Keep repeating until the termination condition is reached.

Question 3

Crossover

Answer 3

This is a method of generating offspring for genetic algorithms. For an n-point crossover operation, pick n random points to make n+1 intervals. The new offspring will contain the odd-numbered intervals from the first parent and the even-numbered intervals from the second parent.

Question 4

Roulette Selection Strategy

Answer 4

The chances that an individual is picked is directly proportional to the individual’s fitness value.

Question 5

Rank Selection Strategy

Answer 5

If there are k individuals, the individual with the highest fitness value gets a value of k. The values then keep decreasing, until the individual with the lowest fitness value gets a value of 1. The chance the individual is selected is now directly proportional to the assigned value.

Question 6

Tournament Selection

Answer 6

The method of choosing the individual is by selecting q individuals, and picking the one with the highest fitness level. Thus, the chance that someone is picked is directly proportional to (fitness-based rank - 1) Choose (q-1)