Heuristics & Approximation Algorithms, University of Nottingham, 9th - 13th April 2018
Heuristics and Approximation Algorithms are Operational Research tools that provide solutions to real-world problems across a wide range of application areas despite their inherent complexity and uncertainty. Heuristics are ‘rules of thumb’ and other clever algorithms that despite being relatively simple to implement can provide good (though not necessarily optimal) and fast solutions to otherwise intractable problems. This course features the main techniques and also practical sessions, so that participants leave with the capabilities to start implementing their own heuristics.
On completion of the block, the student should have a working knowledge of the theory, applications and implementation issues of the main heuristic approaches to combinatorial optimization and their practical application.
Knowledge and Understanding
On completion of the block, the student will be expected to
- understand the basic theory underlying the main heuristic approaches to optimization, such as local search, genetic algorithms and their variants;
- be aware of the strengths and limitations of each approach.
On completion of the block, the student is expected to give evidence of the following intellectual skills
- be able to critically evaluate the quality of different heuristic optimization approaches;
- be capable of applying their knowledge and understanding to develop an appropriate heuristic for a new problem.
On completion of the block, the student is expected to have developed the following subject-specific practical skills
- be familiar with at least one software tool in the area;
- be able to apply an appropriate range of optimization heuristics to a given problem.
What are heuristics? Classification of heuristic search, When to use heuristic search? Local search, Design of local search algorithms (representation of solutions, neighbourhood, search process, escaping from local optima, Multistart Local Search, GRASP, Variable Neighbourhood Search), Constraint handling, Parameter tuning, Analysis of heuristic search performance, Complexity theory
2. Simulated Annealing - Basic concepts, Algorithm, Practical considerations (initial temperature, equilibrium state, cooling schedule, stopping condition), Simulated Annealing inspired algorithms (Threshold Accepting, Great Deluge Algorithm)
3. Tabu Search - Basic concepts, Algorithm, Memories (short-memory, intermediate memory, long term memory), Diversification techniques, Practical considerations
4. Evolutionary Computation - Basic concepts, Components of Evolutionary Computation, Classification of Evolutionary Computation algorithms, Genetic Algorithm, Practical considerations
5. Approximation Algorithms
6. Multiobjective Evolutionary Algorithms - Basic concepts, Multiobjective applications, Classification, Evolutionary Multiobjective Optimisation (fitness assignment, diversity preserving, elitism), Weighted Sum Approach, VEGA, Procedure for finding the approximation of Pareto set, NSGA-II, Performance evaluation
7. Real-world problems solved by heuristics/meta-heuristics
8. Lab session (4 hours)
- Start Date: 04/09/2018
- End Date: 13/04/2018
- Location: University of Nottingham