Subject description PIT9206

This course will cover the foundation of search and optimization algorithms. Traditional search algorithms will be introduced (e.g., Random Search and Hill Climbing), followed by Evolutionary Algorithms (EAs), such as Genetic Algorithms and (1+1) EA.

Students will learn the differences among the existing search algorithms, especially regarding their tradeoffs between the exploration and exploitation of the search landscape. Students will learn how to design custom fitness functions for different problem domains, and how to design new specialized search algorithms (e.g., specialized mutation operators). Students will then be introduced to the research field of Search-Based Software Engineering (SBSE), where search algorithms are used to solve Software Engineering (SE) problems. Concrete examples with open-source research tools (e.g., EvoMaster) will be given, e.g., on the SE problem of automated test case generation (e.g., how to design fitness functions based on source code analyses).

The aim of this course is to get participants up to date with the state of the art in terms of the application of search-based and evolution inspired algorithms to problems in software engineering.

The course will enable participants to understand how software engineering problems can be formulated as optimization problems, how state of the art algorithms can be applied to solving such problems, and how evolution inspired algorithm can be themselves customized to address specific problems. The course will focus on practical experience with the various algorithms, how they can be implemented and applied in practice, and how their results can be analyzed and interpreted with the appropriate statistical methods and visualization techniques.

On completion of the course, the student has achieved the following learning outcomes, defined in terms of knowledge, skills and general competence:

Knowledge The candidate...

• has an in-depth understanding of the main characteristics defining search and optimization problems, and how specific software engineering problems can be reformulated as optimization problems, for example how test case generation can be formulated as an optimization problem.

• has knowledge of the main characteristics of the most used state of the art search algorithms, their benefits and drawbacks, and their applicability to specific types of optimization problems. For example, understanding the critical difference between exploration and exploitation of the search landscape, and the impact of this difference on the solutions being generated for specific optimization problems.

• can critically assess and discuss the details of how evolution-inspired algorithms work, as well as their suitability for individual problems and applications.

• has an in-depth understanding of how search-based algorithms can be customized for individual problems and can critically discuss the suitability of particular operators on both familiar and newly defined optimization problems. For example, the impact that fitness functions and specialized search operators have on the search outcomes.

• has an in-depth understanding of how to analyze and compare the results of experiments with search algorithms.

Skills The candidate can...

• define problems they encounter as optimization problems, design relevant fitness functions and search operators that can exploit domain knowledge of those problems, and critically assess the benefits and drawbacks of those operators on the respective problems

• assess the suitability of existing evolutionary algorithms and, if needed, implement their own customized evolutionary algorithms to better exploit domain knowledge of optimization problems.

• individually use and extend existing open-source research tools used in the field of Search-Based Software Engineering, identifying and working to address particular gaps in the current body of knowledge.

• run experiments and prepare scripts to automatically analyze the results with statistical tests, automatically generating Latex tables and graphs to visualize the data results.

General competence The candidate can...

• discuss, propose, and critically evaluate search and optimization problem formulations, in both their work and other research.

• apply and assess evolutionary algorithms, their suitability to individual research problems, the quality of their implementation, and the implications of their results,

• can conduct relevant research within the field of Search-Based Software Engineering.

PhD in Applied Information Technology

Teaching dates: May 27 - 30, 2024

Lectures and student guidance: 24 hours

Self-study: 49 hours

Preparation for presentation/discussion in class: 20 hours

Assessment 40 hours

Total: 133 hours

No compulsory activity in this course.

Exam: Individual written home examination

Duration: Course duration

Grading scale: The Norwegian grading system uses the graded scale pass or fail

Weighting: Passing of the overall assessment

Support materials: All support materials are allowed

If graded fail the candidate can resubmit the written home exam within 2 weeks from the grade is announced. The number of attempts for the exam is stated in the regulations.

N/A