CS492D Search Based Software Engineering (Autumn 2015)

Syllabus

This class covers metaheuristic optimisation algorithms and their application to software engineering problems. The goal of the class is twofold: the first objective is to understand major classes of metaheuristic algorithms, including local search algorithms and population based optimisation (such as genetic algorithm and particle swarm optimisation). The second objective is to study the application of these algorithms to software engineering problems. For this, the class will introduce the fundamental concepts in so called Search Based Software Engineering, and then study various application cases across the software development lifecycle (requirements, design, planning, testing, maintenance, etc). The desired learning outcome is to be able to use metaheuristic optimisation to automate, and/or gain insights into, software engineering tasks.

Evaluation

  • Coursework: 30%
  • Final Exam: 40%
  • Proposal Essay: 20%
  • Class Participation: 10%

Lectures

  1. Introduction to SBSE Part 1, Part 2
  2. Fitness Landscape
  3. Local Search Algorithms
  4. Evolutionary Computation, TSP Example
  5. Genetic Programming
  6. Bio-inspired Algorithms
  7. Multi-Objective Optimisation
  8. MOEA Evaluation Metrics
  9. Normalisation, Optimisation Cookbook
  10. Advanced Algorithms
  11. Overview of SBSE
  12. Elementary Landscape Analysis

Coursework

The coursework consists of solving two problems using stochastic approaches. The first is Travelling Salesman Problem, and the second is Sudoku. There is a class competition for each problem: we collectively execute the submissions against unknown problem instances, to determine which submission can compute the best solution in the shortest time. The winning entries received prizes and presented their solutions to the class. Slides from the winning entry presentation are attached below.

Proposal Essay

This assignment requires the participants to submit a proposal of an SBSE research project. The subject and the technique can be anything related to software engineering. Participants are strongly encouraged to produce empirical resutls as well, whenever possible. Detailed specification is here.