Improvement heuristics II - Simulated Annealing
14 important questions on Improvement heuristics II - Simulated Annealing
What is the idea behind SA?
- Generate a neighbour B from solution A;
- When the change is positive, accept B;
- If else, accept B with a certain probability;
How do you calculate the probability of accepting a neighbor in SA?
Consider the Boltzmann distribution
- What does delta stand for?
- What does T stand for?
- Consider delta when is the probability of acceptance higher?
- Delta is the difference between the neigbor solution and the current solution;
- T is the temperature, cooling parameter;
- The smaller the delta the higher the probability of accepting;
- Higher grades + faster learning
- Never study anything twice
- 100% sure, 100% understanding
How is the temperature updated?
Explain what the markov chain length does in SA
What is a static vs a dynamic Markov chain?
Fixed M (Markov Chain Length)
Dynamic
Increase M after each chain because the probability of transition decreases
SA makes use of a stopping criteria. What are [3] possible termination criteria?
- Reaching maximum number of iterations;
- Solution at the end of the Markov Chain did not change for x chains;
- Temperature reaches a preset minimum value;
What do finite time implements of SA lead to?
Implementation of SA requires [3] things in practice, what are these [3] things?
- Well-chosen problem representation;
- Transition mechanism;
- Cooling Schedule;
In SA what is meant with the transition mechanism, and what are [2] requirements in picking one?
- Every solution must be reachable;
- Must be possible in as few transitions as possible;
Give [4] transition mechanism examples;
- K-opt;
- Or-opt;
- Swap;
- Move;
How can the SA algorithm be sped up?
What is the acceptance ratio used for?
In choosing the parameters for the cooling scheme how do you determine Markov Chain Length M and decrease factor alpha and in what order?
- Length Markov Chain is the number of neighbor solutions;
- Decrease factor alpha follows from the Markov Chain Length;
The question on the page originate from the summary of the following study material:
- A unique study and practice tool
- Never study anything twice again
- Get the grades you hope for
- 100% sure, 100% understanding
![Trustpilot Logo](/images/design_2020/lp/clp-trustpilot-en.png)