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 (firstname.lastname@example.org), Jinhan Kim (email@example.com)
- 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, Random and Local Search Algorithms
- 09/07: No lecture (FSE/SSBSE 2017)
- 09/12: No lecture (FSE/SSBSE 2017)
- 09/14: Evolutionary Computation 1/2, Coursework #1
- 09/19: Evolutionary Computation 2/2
- 09/21: Genetic Programming
- 09/26: Bio-inspired Algorithms
- 09/28: Multi-objective Optimisation
- 10/03: No lecture (Chuseok Holiday)
- 10/05: No lecture (Chuseok Holiday)
- 10/10: MOEA Evaluation Metrics, Normalisation, SBSE Overview
- 10/12: Theory - Elementary Landscape Analysis
- 10/17: No lecture (Midterm week)
- 10/19: No lecture (Midterm week)
- 10/24: Advanced Algorithms and Optimisation Tips
- 10/26: Project Pitch
- 10/31: Paper Reading. Presenter: Team 8, Dissenter: Team 6
- 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. https://dl.acm.org/citation.cfm?id=2754648
- 11/02: Paper Reading. Presenter: Team 6, Dissenter: Team 7
- G. Gay. Generating Effective Test Suites by Combining Coverage Criteria, pages 65–82. Springer Inter- national Publishing, Cham, 2017. https://link.springer.com/chapter/10.1007/978-3-319-66299-2_5
- 11/07: Paper Reading. Presenter: Team 7, Dissenter: Team 3
- 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. https://dl.acm.org/citation.cfm?id=1277179
- 11/09: Paper Reading. Presenter: Team 3, Dissenter: Team 4
- 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. https://dl.acm.org/citation.cfm?id=1555051
- 11/14: Paper Reading. Presenter: Team 4, Dissenter: Team 5
- 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. http://ieeexplore.ieee.org/document/5406532/
- 11/16: Paper Reading. Presenter: Team 5, Dissenter: Team 2
- G. Fraser and A. Arcuri. Whole test suite generation. Software Engineering, IEEE Transactions on, 39(2):276–291, Feb 2013. https://dl.acm.org/citation.cfm?id=2478706
- 11/21: Paper Reading. Presenter: Team 2, Dissenter: Team 1
- Sebastian Bauersfeld, Stefan Wappler, Joachim Wegener. A Metaheuristic Approach to Test Sequence Generation for Applications with a GUI. International Symposium on Search Based Software Engineering (SSBSE 2011), page 173-187 https://link.springer.com/chapter/10.1007%2F978-3-642-23716-4_17
- Sapienz is a search-based Android testing tool. It was developed as a research prototype (see the original ISSTA 2016 paper) and later bought by Facebook (see this ArsTechnica article).
- ExSyst is a system testing technique that exploits the UI in order to maximise structural coverage. It was developed at Saarland University, Germany.
- Sikuli is a scripting language that accepts graphical elements as function arguments: it was developed at MIT, USA.
- 11/23: Paper Reading. Presenter: Team 1, Dissenter: Team 9
- A. Arcuri and G. Fraser. Parameter tuning or default values? an empirical investigation in search-based software engineering. Empirical Software Engineering, 18(3):594–623, Jun 2013. https://link.springer.com/article/10.1007/s10664-013-9249-9
- Slides on No Free Lunch Theorem
- 11/28: Paper Reading. Presenter: Team 9, Dissenter: Team 8
- G. Xiao, F. Southey, R. C. Holte, and D. Wilkinson. Software testing by active learning for commercial games. In Proceedings of the 20th national conference on Artificial intelligence - Volume 2, AAAI’05, pages 898–903. AAAI Press, 2005. https://aaai.org/Library/AAAI/2005/aaai05-142.php
- 11/30: Project Presentation #1. Team 9, 1, 2, 5
- 12/05: Project Presentation #2. Team 4, 3, 7, 6, 8
- 12/07: 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: Learning to Rank for Automated Debugging
Your goal is to implement a learning-to-rank algorithm for automated debugging technique called fault localisation. Fault localisation aims to take various observations from test executions (including failing ones) and tell the developer where the responsible fault is within the code base. We will provide you with data from 156 faults in real world open source Java projects. Your task is to implement an algorithm such that it ranks all the faulty methods as high as possible based on the data we provide. Submit your algorithm as well as your best ranking model: we will evaluate your model using 54 unseen faults to see how generally applicable your model is. Detailed instruction can be seen in the coursework document and slides. This coursework is due on 8th December 2017: submission should be made on KLMS.
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 on 26th October 2017. Please see KLMS to read project topics from the last year.
Project Outcome Presentation: present the results you obtained within 15 minutes. We are going to use the 30th November and 5th Deembe slot.
Details about the deliverables are specified in the project documentation. Submission deadline is the end of 18th December 2017.
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.