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.
The first half of the course will be a series of lectures on metaheuristic algoithms. The second half will be a series of case studies based on paper presentations, given by students, about important and/or recent papers in the field of Search Based Software Engineering.
Note: due to the larger-than-usual attendance number, it has not been decided yet how to run the project part of the course. Consequently, the below lecture schedule is only tentative.
- Coursework: 30%
- Project: 30%
- Final Exam: 30%
- Class Participation: 10%
- Seongmin Lee (email@example.com), Jinhan Kim (firstname.lastname@example.org)
- T/A Office Hour: 14:30-17:30, Wednesdays, N1 Room 402
- 08/29: Introduction 1/2
- 08/31: Introduction 2/2
- 09/05: Fitness Landscape
- 09/07: No lecture (FSE/SSBSE 2017)
- 09/12: No lecture (FSE/SSBSE 2017)
- 09/14: Random and Local Search Algorithms
- 09/19: Evolutionary Computation 1/2, Coursework #1
- 09/21: Evolutionary Computation 2/2
- 09/26: Multi-objective Optimisation
- 09/28: Genetic Programming
- 10/03: No lecture (Chuseok Holiday)
- 10/05: No lecture (Chuseok Holiday)
- 10/10: Bio-inspired Algorithms
- 10/13: Normalisation, SBSE Overview
- 10/17: No lecture (Midterm week)
- 10/19: No lecture (Midterm week)
- 10/24: Theory - Elementary Landscape Analysis
- 10/27: Advanced Algorithms
- 11/30: No lecture (Undergraduate Admission Interview Day)
- 12/12: Final Term Exam
Courseworks consist of solving large scale problems using stochastic approaches. There will be a class leaderboard, so that participants can submit their solutions to see how well they are doing. The winning entries will receive prizes and present their solutions to the class. In addition to submission of solutions to the leaderboard, participants should submit their implementation and report online.
- Coursework #1: Travelling Salesman Problem
Your goal is to implement a solver for the Travelling Salesman Problem. This is a well known NP-complete problem with lots of practical applications. Please refer to the coursework document for more details. This coursework is due on 28 September 2017: submission should be made on KLMS.
- Corusework #2: To be announced.
The course project will be about actual application of metaheuristic problem solving to software engineering. Please see the document. Groups should prepare two talks:
Project Idea Pitch: introduce what your group plans to do within 5 minutes. 1st November 2016. Here are some example project ideas.
Project Outcome Presentation: present the results you obtained within 15 minutes. We are going to use the 13th December slot, but it may have to be moved so that all groups can fit.
Details about the deliverables are specified in the project documentation. Submission deadline is to be announced.
Here are some papers on various SBSE topics to pick from in order to prepare for the first paper presentation of your group. You can also consult the SBSE Repository.
A. Bagnall, V. Rayward-Smith, and I. Whittley. The next release problem. Information and Software Technology, 43(14):883–890, Dec. 2001.
Y. Zhang, M. Harman, and S. A. Mansouri. The Multi-Objective Next Release Problem. In GECCO ’07: Proceedings of the 2007 Genetic and Evolutionary Computation Conference, pages 1129–1136. ACM Press, 2007.
G. Antoniol, M. D. Penta, and M. Harman. Search-based Techniques Applied to Optimization of Project Planning for a Massive Maintenance Project. In Proceedings of the 21st IEEE International Conference on Software Maintenance (ICSM ’05), pages 240–249, Los Alamitos, California, USA, 25-30 September 2005. IEEE Computer Society.
F. Ferrucci, M. Harman, J. Ren, and F. Sarro. Not going to take this anymore: Multi-objective overtime planning for software engineering projects. In Proceedings of the 2013 International Conference on Software Engineering, ICSE ’13, pages 462–471, Piscataway, NJ, USA, 2013. IEEE Press.
B. S. Mitchell and S. Mancoridis. On the automatic modularization of software systems using the bunch tool. IEEE Transactions on Software Engineering, 32(3):193–208, 2006.
K. Praditwong, M. Harman, and X. Yao. Software module clustering as a multi-objective search problem. IEEE Transactions on Software Engineering, 37(2):264–282, March-April 2010.
Test Data Generation
C. Michael, G. McGraw, and M. Schatz. Generating software test data by evolution. IEEE Transactions on Software Engineering, 27(12):1085–1110, December 2001.
G. Fraser and A. Arcuri. Whole test suite generation. Software Engineering, IEEE Transactions on, 39(2):276–291, Feb 2013.
M. Harman, L. Hu, R. Hierons, J. Wegener, H. Sthamer, A. Baresel, and M. Roper. Testability transformation. IEEE Transactions on Software Engineering, 30(1):3–16, Jan. 2004.
W. Weimer, T. Nguyen, C. L. Goues, and S. Forrest. Automatically finding patches using genetic programming. In Proceedings of the 31st IEEE International Conference on Software Engineering (ICSE ’09), pages 364–374, Vancouver, Canada, 16-24 May 2009. IEEE.
Z. P. Fry, B. Landau, and W. Weimer. A human study of patch maintainability. In Proceedings of the 2012 International Symposium on Software Testing and Analysis, ISSTA 2012, pages 177–187, New York, NY, USA, 2012. ACM.
S. Yoo and M. Harman. Pareto efficient multi-objective test case selection. In Proceedings of International Symposium on Software Testing and Analysis, pages 140–150. ACM Press, July 2007.
M. G. Epitropakis, S. Yoo, M. Harman, and E. K. Burke. Empirical evaluation of pareto efficient multi- objective regression test case prioritisation. In Proceedings of the 2015 International Symposium on Software Testing and Analysis, ISSTA 2015, pages 234–245, New York, NY, USA, 2015. ACM.
- M. O’Cinnéide, L. Tratt, M. Harman, S. Counsell, and I. Hemati Moghadam. Experimental assessment of software metrics using automated refactoring. In Proceedings of the ACM-IEEE international symposium on Empirical software engineering and measurement, ESEM ’12, pages 49–58, New York, NY, USA, 2012. ACM.
D. White, A. Arcuri, and J. Clark. Evolutionary improvement of programs. IEEE Transactions on Evolutionary Computation, 15(4):515 –538, August 2011.
W. Langdon and M. Harman. Optimizing existing software with genetic programming. Transactions on Evolutionary Computation, 19(1):118–135, 2015.
B. R. Bruce. Energy optimisation via genetic improvement: A sbse technique for a new era in software development. In Proceedings of the Companion Publication of the 2015 Annual Conference on Genetic and Evolutionary Computation, GECCO Companion ’15, pages 819–820, New York, NY, USA, 2015. ACM.
Deep Parameter Optimisation
- F. Wu, W. Weimer, M. Harman, Y. Jia, and J. Krinke. Deep parameter optimisation. In Proceedings of the 2015 Annual Conference on Genetic and Evolutionary Computation, GECCO 2015, pages 1375–1382, 2015.
- S. Yoo. Evolving human competitive spectra-based fault localisation techniques. In G. Fraser and J. Teixeira de Souza, editors, Search Based Software Engineering, volume 7515 of Lecture Notes in Computer Science, pages 244–258. Springer Berlin Heidelberg, 2012.