Improvement heuristics I - Local Search, steepest descent
17 important questions on Improvement heuristics I - Local Search, steepest descent
What is the definition of a local search alogrithm?
- Start with feasible solution;
- Repeatedly search neighborhood for improvements;
Give [4] steps of a local search algorithm;
- Start with given initial solution;
- Search neighborhood for a better solution using some operation;
- Accept or reject the solution and start again;
- Stop if local optimum or stopping criteria is reached;
Give the definition of local search, steepest descent
The method stops when a local optimum is reached.
- Higher grades + faster learning
- Never study anything twice
- 100% sure, 100% understanding
Explain the neighborhood operator k-OPT
When is a tour k-optimal?
What is the idea of OR-opt?
Steepest descent
- [1] advantage
- [2] disadvantages
- Quickly generates a solution
Disadvantage
- Converges fast
- Get stuck easily in a local optimum
How can local optimality be overcome? Also, give the name of these.
Metaheuristics
How does GRASP apply the concept of intensification and diversification?
What is a method to overcome cycling?
What are possible attributes for a recently visited solution that is stored in the tabu-list?
- Entire solution;
- Moves - operators;
- Changed items;
What is meant with aspiration level in tabu search?
Why is an aspiration level sometimes necessary?
- Global best | Best overall solution is found;
- Region best | Best solution with a certain property is found;
- Recent best | Best recently visited solution;
Give the [5] tabu search implementation decisions
- Initial solution;
- Neighbourhood operator;
- Tabu list length;
- Tabu list attributes;
- Stopping criteria;
What is meant with connectivity, Why is it needed?
Needed to reach global optimum.
What influence has the tabu list length on a solution? How can static and dynamic tabu lists be of use?
Give [2] stopping criteria considering the tabu list
- If improvements are not realized after a predetermined number of exchanges;
- If all the direct neighbours are in the tabu list;
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)