Page 53 - SMILESENG

Intl. Summer School on Search- and Machine Learning-based Software Engineering
Road to Human as the Fitness Function
Jaime Font∗, Lorena Arcega∗, Francisca Pe´rez∗ and Carlos Cetina∗ ∗SVIT Research Group
Universidad San Jorge, Zaragoza, Spain
Email: jfont@usj.es, larcega@usj.es, mfperez@usj.es and ccetina@usj.es
Abstract—In Search-Based Software Engineering, more than 100 works have involved the human in the search process to obtain better results. However, the case where the human completely replaces the fitness function remains neglected. There is a good reason for that; no matter how fast or efficient the human is, humans cannot assess millions of candidate solutions in a reasonable time. By contrast, computational intelligence techniques (such as evolutionary computation or machine learn- ing) are capable of dealing with large search spaces but are not as good as humans in understanding the context when making a decision. We propose to combine both, using the Human as the Fitness Function of an evolutionary approach designed to minimize the amount of work that the human has to perform.
We are using three ingredients to minimize the effort of the human. Firstly, we focus on Search-Based Model-Driven Engineering (SBMDE) because inspecting models should require less human effort than inspecting code thanks to the higher abstraction level of models compared to the code. Secondly, we apply intelligent operators that do not rely only on randomness to explore the search space but also embed relevant information for the search being performed. Thirdly, we apply techniques to handle unfeasible individuals (models that do not conform to their metamodel) and thus reducing the search space.
I. INTRODUCTION
Search-Based Software Engineering (SBSE) proposes to reformulate problems from the field of software engineering as search problems that can be addressed by existing meta- heuristic algorithms such as evolutionary algorithms. It has attracted many research efforts from different fields, as only three items are needed to apply SBSE: (1) an encoding to represent candidate solutions to the problem as individuals that can be manipulated; (2) a set of operators used to generate new individuals; (3) a fitness function that can assess how good is each candidate as a solution to the problem. Then, candidate solutions (which are encoded following the representation chosen) are evolved (by applying the operators) and are evaluated (by the fitness function) in an iterative process until optimal solutions to the problem are found.
SBSE has been applied to many different problems [1], and we have successfully applied it to maintenance tasks such as bug localization [2], traceability links recovery [3], or feature location [4]. Feature Location is defined as the task of identifying the set of software elements that realize a particular feature. This can be applied to different software artifacts (e.g.: source code or software models) and the elements identified can vary in granularity (a line of code, a method, or a whole class). In one of our previous works, we tackled the problem of feature location from the software of CAF, an industrial partner that has been producing railway solutions since 1917.
We estimated that the time needed by a single engineer to manually locate all the features present in their software products would be over 30 years [3].
Encodings and operators can be reused across domains or applications and adapted with minimum changes to be applied to different problems. The typical encoding used includes binary strings, value encoding, or tree encoding. Similarly, default operations for those encodings can be directly applied, either selection operators, crossover operators, or mutation operators. However, the fitness function is more bounded to the domain and not so easily translated from one domain to another, as it needs to take into account much information about the domain.
We propose to replace the fitness function with a human, taking advantage of the better understanding of the domain and the context of humans compared to computers. However, there is a good reason for not doing it, no matter how efficient the human is, humans cannot evaluate thousands of candidate solutions in reasonable time as they will suffer from fatigue. By contrast, computers are never tired and will surpass humans in tasks like the manipulation of individuals or the exploration of large search spaces. The following sections describe the steps that enabled us to use the Human as the Fitness Function (HaFF).
II. RELATED WORK
Traditionally, SBSE that has been applied to reformulate software engineering tasks into search problems relegated the human to the background and put most of the burden on the search strategy. Some works have attempted to address this by enabling the interaction of the human in the search process, mainly by providing scores to complement the fitness function. As part of our work, we have analyzed existing surveys about search-based software engineering applied to model-driven engineering [5] (covering works from 1998 to 2016) and about interactive search-based software engineering [6] (covering works from 1999 to 2017) and updated them (up to August 2020).
Most of the works (54.55%) involve humans in the selection of solutions. The next most common type of interaction is the modification of the obtained solution (31.82%). Our work is focused on the evaluation (fitness function), only 27.27% of the works involve humans in the evaluation. None of the works have been able to successfully replace the fitness function with a human in an industrial context as our work does.
41