Simulated Annealing

Traveling Salesman Problem

• Salesman has to visit 5 cities.

• Must return back the same city he started from.

• What is the efficient order of flights to minimize the overall distance flown.

• NP-Hard. Non Deterministic Polynomial.

• Uncross the paths where the paths crossed.

• Doing this iteratively.

Methods to help find the global maximum

4-Queens

5-Queens

n-Queens Heuristic Function

n-Queens local Minima

Local Maxima

Random Restarts

• Avoid the paths that we have already considered.

Hill-Climbing Quiz

Step Size Too Small

• With Small Steps you can get struck in the flat “Shoulder”.

Step Size Too Large

• Miss Sharp Hills Completely.

• Infinite Loop and never Terminate.

• Algorithm can oscillate and never terminate.

• Start with a large step-size and reduce the step-size with the smaller step-size.

Hill-Climbing Quiz 2

Annealing

• Wikipedia: https://en.wikipedia.org/wiki/Simulated_annealing

• Energy Minimization

• When the energy of the molecule reduces, the molecules arrange themselves in the lowest energy configuration and they form patterns like mud-cracks or honey combs.

• Honey-combs. Honeybees tries to optimize their storage space and minimize the structure they are building.

Simulated Annealing

• T is the simulated temperature at time t, which reduces from a high value at the beginning to near zero eventually.

• \(\delta E\) is the change in energy going from current to next.

• When T is small, it is normal hill-climbing.

• When \(\delta E\) is 0, we will get struck in a plateau. But eventually, we will random walk off the plateau.

Local Beam Search

• K-particles.

• Each time frame, we keep track of randomly generated neighbours of these particles and keep the k best ones for the next iteration.

Representing n-Queens

Genetic Algorithms

• The fitness function

\[28 - number_of_attacking_pairs\]

• Add the four scores and normalize them to a percentage.

• We roll a 100 sided die to select the first parent.

• 1-31 - First Board. 32 - to 60 second one, 61 to 90 - third one, 90 to 100 - fourth.

• After rolling die, we selected the parents in the second column here.

• Using Crossover.

• Take the first-part and tack them to the second part.

GA Crossover

GA Mutation

• What if there is a critical part of the solution that is in none of the parents.

• More randomness. Just like mutations in biology, we are going to use mutations in genetic algorithms.

• How many generations are needed to get a good answer.

GA Crossover Quiz

• Without mutation, we run the risk of never actually reaching the goal.