#REQUEST.pageInfo.pagedescription#

Site Navigation

COMP9058 - Metaheuristic Optimisation

banner1
Title:Metaheuristic Optimisation
Long Title:Metaheuristic Optimisation
Module Code:COMP9058
 
Credits: 5
NFQ Level:Expert
Field of Study: Computer Science
Valid From: Semester 1 - 2018/19 ( September 2018 )
Module Delivered in 2 programme(s)
Module Coordinator: TIM HORGAN
Module Author: Alejandro Arbelaez
Module Description: This module explores techniques for the analysis and design of efficient techniques to solve real-life problems. In this module the learner will be introduced to the complexity of solving hard combinatorial problems, i.e., recognise and prove NP-hard problems. Additionally, the module covers effective and efficient meta-heuristic 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 real-life problem with respect to its computational complexity.
LO2 Assess the benefits and limitations of meta-heuristics to solve NP-hard problems.
LO3 Solve an NP-hard problem with meta-heuristics to find a satisfactory lower-bound solution.
LO4 Analyse the average performance of a randomised algorithm to solve an NP-hard problem
LO5 Apply nature-inspired and local search meta-heuristics to solve real-life problems.
Pre-requisite 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
Co-requisite Modules
No Co-requisite 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
Co-requisites
No Co Requisites listed
 

Module Content & Assessment

Indicative Content
Computational Complexity Theory
Complexity classes (P, NP, NP-complete, and NP-hard); P vs. NP; polynomial-time reductions to prove NP-completeness; tractability and intractability; the no free lunch theorem.
Population-based meta-heuristics
Mainstream population-based meta-algorithms such as: evolutionary and genetic algorithms, estimation of distribution algorithms (EDAs); ant-colony optimization, particle swarm optimization, and artificial bee colony algorithm
Single solution-based meta-heuristics
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; k-opt and Lin-Kernighan algorithms; random walk; randomised search trees; randomised sorting.
Performance of randomised algorithms
Random variables and their properties; average case-runtime of Las Vegas algorithms; runtime distributions of las Vegas algorithm; evaluate and compare randomised algorithms.
Applications
Applying population-based and single solution-based meta-heuristics to solve real-world problems , e.g., assignment problem, Boolean satisfiability problem, traveling salesman problem, and knapsack problem
Assessment Breakdown%
Course Work100.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 NP-complete and implement a population-based meta-heuristic, 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 real-life problem and the students will have to implement a single solution-based 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 re-submitted 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 (Non-contact) 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 (Non-contact) 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]
  • El-Ghazali Talbi 2009, Metaheuristics: From Design to Implementation, John Wiley & Sons [ISBN: 978-0-470-278]
  • Xin-She Yang 2010, Nature-Inspired 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: 978-149330373]
  • 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 Theorem-Proving Procedures, Proceedings of the Third Annual ACM Symposium on Theory of Computing
  • Keld Helsgaun 2009, General k-opt submoves for the Lin-Kernighan 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
 

Module Delivered in

Programme Code Programme Semester Delivery
CR_KARIN_9 Master of Science in Artificial Intelligence 1 Mandatory
CR_KSADE_9 Master of Science in Software Architecture & Design 2 Mandatory

Cork Institute of Technology
Rossa Avenue, Bishopstown, Cork

Tel: 021-4326100     Fax: 021-4545343
Email: help@cit.edu.ie