- 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.
- Avoid the paths that we have already considered.
- With Small Steps you can get struck in the flat "Shoulder".
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- Without mutation, we run the risk of never actually reaching the goal.