Title:  Metaheuristic Optimisation 
Long Title:  Metaheuristic Optimisation 
Field of Study: 
Computer Science

Valid From: 
Semester 1  2018/19 ( September 2018 ) 
Module Coordinator: 
TIM HORGAN 
Module Author: 
Alejandro Arbelaez 
Module Description: 
This module explores techniques for the analysis and design of efficient techniques to solve reallife problems. In this module the learner will be introduced to the complexity of solving hard combinatorial problems, i.e., recognise and prove NPhard problems. Additionally, the module covers effective and efficient metaheuristic techniques to tackle complex decision problems, especially combinatorial optimisation problems. 
Learning Outcomes 
On successful completion of this module the learner will be able to: 
LO1 
Categorise a reallife problem with respect to its computational complexity. 
LO2 
Assess the benefits and limitations of metaheuristics to solve NPhard problems. 
LO3 
Solve an NPhard problem with metaheuristics to find a satisfactory lowerbound solution. 
LO4 
Analyse the average performance of a randomised algorithm to solve an NPhard problem 
LO5 
Apply natureinspired and local search metaheuristics to solve reallife problems. 
Prerequisite learning 
Module Recommendations
This is prior learning (or a practical skill) that is strongly recommended before enrolment in this module. You may enrol in this module if you have not acquired the recommended learning but you will have considerable difficulty in passing (i.e. achieving the learning outcomes of) the module. While the prior learning is expressed as named CIT module(s) it also allows for learning (in another module or modules) which is equivalent to the learning specified in the named module(s). 
No recommendations listed 
Incompatible Modules
These are modules which have learning outcomes that are too similar to the learning outcomes of this module. You may not earn additional credit for the same learning and therefore you may not enrol in this module if you have successfully completed any modules in the incompatible list. 
No incompatible modules listed 
Corequisite Modules

No Corequisite modules listed 
Requirements
This is prior learning (or a practical skill) that is mandatory before enrolment in this module is allowed. You may not enrol on this module if you have not acquired the learning specified in this section.

No requirements listed 
Corequisites

No Co Requisites listed 
Module Content & Assessment
Indicative Content 
Computational Complexity Theory
Complexity classes (P, NP, NPcomplete, and NPhard); P vs. NP; polynomialtime reductions to prove NPcompleteness; tractability and intractability; the no free lunch theorem.

Populationbased metaheuristics
Mainstream populationbased metaalgorithms such as: evolutionary and genetic algorithms, estimation of distribution algorithms (EDAs); antcolony optimization, particle swarm optimization, and artificial bee colony algorithm

Single solutionbased metaheuristics
Application of standard local search techniques such as: neighborhood search, variable neighborhood search, hill climbing, simulated annealing, and Tabu search; global Vs. local optimum solutions

Randomised Algorithms
Las Vegas and Monte Carlo algorithms; kopt and LinKernighan algorithms; random walk; randomised search trees; randomised sorting.

Performance of randomised algorithms
Random variables and their properties; average caseruntime of Las Vegas algorithms; runtime distributions of las Vegas algorithm; evaluate and compare randomised algorithms.

Applications
Applying populationbased and single solutionbased metaheuristics to solve realworld problems , e.g., assignment problem, Boolean satisfiability problem, traveling salesman problem, and knapsack problem

Assessment Breakdown  % 
Course Work  100.00% 
Course Work 
Assessment Type 
Assessment Description 
Outcome addressed 
% of total 
Assessment Date 
Project 
In this project the students will be given a problem and they will have to show that the problem is NPcomplete and implement a populationbased metaheuristic, to solve the problem and critically evaluate the performance the solution. 
1,2,3 
50.0 
Week 6 
Project 
In this project the students will be given a reallife problem and the students will have to implement a single solutionbased metaheuristic to solve the problem and critically evaluate the performance of the solution 
3,4,5 
50.0 
Sem End 
No End of Module Formal Examination 
Reassessment Requirement 
Coursework Only
This module is reassessed solely on the basis of resubmitted coursework. There is no repeat written examination.

The institute reserves the right to alter the nature and timings of assessment
Module Workload
Workload: Full Time 
Workload Type 
Workload Description 
Hours 
Frequency 
Average Weekly Learner Workload 
Lecture 
Presentation of theory. 
2.0 
Every Week 
2.00 
Lab 
Lab supporting lectures. 
2.0 
Every Week 
2.00 
Independent & Directed Learning (Noncontact) 
Student undertakes independent study. The student reads recommended papers and practices implementation. 
3.0 
Every Week 
3.00 
Total Hours 
7.00 
Total Weekly Learner Workload 
7.00 
Total Weekly Contact Hours 
4.00 
Workload: Part Time 
Workload Type 
Workload Description 
Hours 
Frequency 
Average Weekly Learner Workload 
Lecture 
Presentation of theory. 
2.0 
Every Week 
2.00 
Lab 
Lab supporting lectures. 
2.0 
Every Week 
2.00 
Independent & Directed Learning (Noncontact) 
Student undertakes independent study. The student reads recommended papers and practices implementation. 
3.0 
Every Week 
3.00 
Total Hours 
7.00 
Total Weekly Learner Workload 
7.00 
Total Weekly Contact Hours 
4.00 
Module Resources
Recommended Book Resources 

 Stuart Russell and Peter Norvig 2016, Artificial Intelligence: A Modern Approach, Pearson Education Limited [ISBN: 9781292153964]
 ElGhazali Talbi 2009, Metaheuristics: From Design to Implementation, John Wiley & Sons [ISBN: 9780470278]
 XinShe Yang 2010, NatureInspired Metaheuristic Algorithms, 2 Ed., Luniver Press [ISBN: 9781905986286]
 Supplementary Book Resources 

 Steve S. Skiena 2009, The Algorithm Design Manual, 2nd Edition Ed., Springer [ISBN: 9781848000698]
 Holger H. Hoos and Thomas Stützle 2004, Stochastic Local Search: Foundations & Applications, Morgan Kaufmann [ISBN: 978149330373]
 Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein, 2009 2009, Introduction to Algorithms, 3rd Edition Ed., MIT Press [ISBN: 9780262033848]
 Supplementary Article/Paper Resources 

 Holger H. Hoos and Thomas Stutzle 1998, Evaluating Las Vegas Algorithms: Pitfalls and Remedies, Proceedings of the Fourteenth Conference on Uncertainty in Artificial Intelligence
 Stephen A. Cook 1971, The Complexity of TheoremProving Procedures, Proceedings of the Third Annual ACM Symposium on Theory of Computing
 Keld Helsgaun 2009, General kopt submoves for the LinKernighan TSP heuristic, Math. Program. Comput, 1
 Charlotte Truchet, Alejandro Arbelaez, Florian Richoux, Philippe Codognet 2016, Estimating parallel runtimes for randomized algorithms in constraint solving, Journal Of Heuristics, 22
 Other Resources 

 Website: Design and Analysis of Algorithms
 Website: Professor Michael MitzenmacherData Structures and Algorithms
 Website: David EppsteinDesign and Analysis of Algorithms

Module Delivered in
