40.325 Heuristic Methods for Optimisation
This course introduces metaheuristic and surrogate optimisation algorithms, which are artificial intelligence search methods used to find approximate solutions to complex, high dimensional optimisation problems, potentially under incomplete information and limited computational resources.
The course covers both foundational and advanced metaheuristic methods, including simulated annealing, tabu search, genetic algorithms, particle swarm optimisation, ant colony optimisation, differential evolution, and multiobjective methods. Students will learn to implement these algorithms in Python, analyse their performance, and apply them to real world engineering optimisation problems drawn from ESD domains such as logistics, supply chain, scheduling, and resource allocation. The course also introduces surrogate optimisation methods, including radial basis function approximation, Latin hypercube sampling, stochastic RBF algorithms, and parallel surrogate optimisation, which build computationally efficient approximations of expensive objective functions to reduce evaluation costs. Students will develop the ability to compare algorithms empirically and to creatively modify existing algorithms for problem specific improvements.
Learning objectives
On successful completion of this course, students should be able to
- Learn the basic principles and theoretical foundations of metaheuristic optimisation, including the distinction between local and global optimisation, and the concept of multimodal objective functions.
- Understand how decision making problems in engineering and systems design can be modelled and solved using metaheuristic and surrogate optimisation methods.
- Understand, implement, and evaluate classical metaheuristic algorithms (simulated annealing, tabu search, genetic algorithms) for both discrete and continuous optimisation problems.
- Understand and implement advanced metaheuristic methods, including particle swarm optimisation, ant colony optimisation, and differential evolution, to address large scale, high dimensional optimisation problems.
- Apply multiobjective optimisation methods (e.g. NSGA-II) to problems with competing objectives, and interpret Pareto optimal solutions.
- Learn the principles of surrogate optimisation (response surface methods), including radial basis function approximations, experimental design via Latin hypercube sampling, and the surrogate optimisation algorithm workflow.
- Design and execute a surrogate optimisation workflow using the stochastic RBF (SRBF) algorithm, and compare surrogate methods against heuristics on benchmark and real world problems.
- Empirically compare the performance of different algorithms on benchmark and real world problems using appropriate statistical methods.
Measurable outcomes
On successful completion of this course, students will be adept in the following.
- Be able to explain and differentiate the principles of various metaheuristic algorithms, including simulated annealing, tabu search, genetic algorithms, particle swarm optimisation, ant colony optimisation, differential evolution, and multiobjective methods.
- Write and execute Python implementations of these metaheuristic algorithms and apply them to solve real world optimisation problems.
- Compare the performance of different algorithms and assess their advantages and limitations by evaluating convergence rates, solution quality, and computational efficiency over multiple trials.
- Implement a surrogate optimisation workflow using radial basis function approximations, Latin hypercube sampling, and stochastic RBF algorithms to efficiently optimise computationally expensive objective functions.
- Apply multiobjective optimisation methods and interpret Pareto fronts to reason about trade offs in engineering design problems.
- Design and analyse modifications to existing metaheuristic algorithms to improve their performance on specific problem classes, and justify the design choices made.
- Use statistical methods to evaluate the relative performance of alternative heuristic algorithms across multiple stochastic trials.
Prerequisites
Course instructor
Number of credits: 12