This paper is concerned with the bi-objective problem in searchbased software engineering for high-level decision-making. The paper presents bi-objective models for next release problem and modularization quality problem that characterized by the presence of two conflicting demands, for which the decision maker must find a suitable balance. The complex nature of such kind of problem has motivated the application of heuristic optimization techniques to obtain Pareto-optimal solutions. In this case, limitation on the size of the problem is reasonable.
Search-Based Software Engineering (SBSE) has become a subfield of software
engineering characterized by growing of activity and research interest. SBSE seeks to
reformulate Software Engineering problems as ‘search problems’ [
It has been argued that the virtual nature of software makes it well suited for
Search-Based Optimization (SBO) [
Traditionally SBSE has based on finding the optimal or near-optimal solution to the problem with respect to a single objective. However, single-objective approach often is incorrect because of existing of many incomparable objectives in the framework of one problem. Incomparability of objectives makes inapplicable waiting of the different objectives in order to combine them into a single weighted sum objective.
This reason has caused applying of multi-objective approaches in SBSE and using
SBSE as a tool for decision support. To underpin the focus on decision support, SBO
problem should be formulated as multi-objective problems, to which a Pareto optimal
approach can be applied [
In this paper, we explore existing bi-objective approaches for high-level decision support in software development process. The rest of the paper is organized as follows. Section 2 briefly describes using of bi-objective models for Next Release and Modularization Problems. Section 3 presents SBO on decision-making perspective. Finally, section 4 draws the main conclusions.
Software engineers have been exploiting many different software development
methodologies that recommend different framework of stages. In this paper, we base
on the fact that high-level decision most often need support on requirement
specification and design stages, which present, more or less, in every methodology.
To explore bi-objective models at these stages, we use papers gathered in repository
of publications on SBSE [
One of the core problems of requirement specification stage in incremental
methodologies is Next Release Problem (NRP). Decision maker determines which
features should be included in the next release of the product in order to satisfy the
highest possible number of customers and entail the minimum cost for the company
[
In NRP a set of customers, C = {c1, ..., cm}, each customer has a degree of importance for the company that can be reflected by a weight factor, Weight = {w1, ..., wm}, where w0,1 and j1wj 1 .
m
It is assumed that there is the set of independent requirements, R = {r1, ..., rn}, that are targeted for the next release of an existing software system. Satisfying each requirement entails spending a certain amount of resources, which can be translated into cost terms, Cost = {cost1, ..., costn}.
Satisfaction of requirements provides value for the company. The level of satisfaction for a given customer depends on the subset of requirements that are satisfied in the next release of the software product. The requirements are not equally important for a given customer. Each customer cj (1<j<m) assigns a value to requirement ri (1<i<n) denoted by value(ri, cj) where value(ri, cj)>0 if customer j has the requirement i and 0 otherwise.
In the formulation of the bi-objective NRP, two objectives are taken into consideration in order to maximize customer satisfaction (or the total value for the company) and minimize required cost. Let the decision vector x x1,...,xn0,1 determines the requirements that are to be satisfied in the next release. In this vector, xi is 1 if the requirement i is selected and 0 otherwise.
The first objective function is considered for maximizing total value:
n m Maximize xi wj valueri , c j .
i1 j1
The problem is to select a subset of the customers’ requirements, which results in the maximum value for the company.
The second objective function is considered for minimizing total cost required for the satisfaction of customer requirements: n Minimizecosti xi .
i1
In order to convert the second objective to a maximization problem, the total cost is multiplied by -1. Therefore, the bi-objective model can be represented as follows: n m Maximize f1x xi wj valueri , c j
i1 j1 n Maximize f2 x costi xi i1
Software design usually includes low-level component and algorithm design and high-level, architecture design. A high-level software engineering problem that is most related to software architectures is Modularization Problem (MP). Decision Maker finds the best grouping of components to subsystems. For that, structure of software system is transformed into a directed graph G, the main question to be answered is what constitutes a good partition of the software structure graph. The goodness of a partition is usually measured with a combination of cohesion and coupling.
Cohesion is a measure of the degree to which the components of a single subsystem belong together. A high cohesion indicates a good modularization arrangement because the components grouped within the same subsystem are highly dependent on each other. A low cohesion, on the other hand, generally indicates a poor modularization arrangement because the components grouped within a subsystem are not strongly related.
The cohesion Ai of subsystem i with Ni components is defined as:
Ai Ni2 i , where µi is the number of intra-edge dependencies (relationships to and from components within the same subsystem), Ni2 is the maximum number of possible dependencies between the components of subsystem i.
Coupling is a measure of the connectivity between distinct subsystems. A high degree of coupling is undesirable because it indicates that subsystems are highly dependent on each other. Conversely, a low degree of coupling is desirable because it indicates that individual subsystems are largely independent of each other.
The coupling Eij between subsystems i and j, each consisting of Ni and Nj components respectively, is defined as: 0 Eij
ij 2Ni N j if i j if i j , where ij is the number of inter-edge dependencies (relationships to and from components of subsystems i and j).
In the formulation of the bi-objective MP, two objectives expresses the tradeoff between cohesion and coupling are taken into consideration in order to create highly cohesive subsystems and penalize the creation of too many dependencies between subsystems.
Given software structure graph G partitioned into k clusters, modeled partition of software system into subsystems, we define MP as:
Maximize f1x
Maximize f2 x 1 k
Ai k i1 kk 1 n k
Eij 2 i1 j1 .
(2)
SBO can be applied to situations in which the human will decide on the solution to be adopted, but the search process can provide insight to help guide the decision maker. This insight agenda, in which SBO is used to gain insights and to provide decision support to the software engineering decision maker, has found natural resonance and applicability when used at the early stages of the software engineering lifecycle, where the high-level decisions made can have far-reaching implications.
Many of the values used to define a problem for optimization, particularly at the early stages of the software development process, come from estimates. In these situations, it is not optimal solutions that the decision maker requires, as much as guidance on which of the estimates are most likely to affect the solutions. Therefore, SBO is not merely a research program in which one seeks to ‘solve’ software engineering problems; it is a rich source of insight and decision support.
Bi-objective problems stated above are NP-hard, and, therefore, cannot be solved using exact optimization techniques for large-scale problem instances. That is why metaheuristic search techniques are usually applied to find approximations of Pareto optimal set (or front) for the bi-objective problem. Decision maker selects the solution from the found set according to his (her) preferences.
Restriction on SBO approach connected with the point at which the problem becomes too small. For NRP, limitation is a function of the number of requirements, which should exceed about 20 requirements. By contrast, there is no number of customers that is too small for the problem to be worthwhile. For MP, limitation is a function of the number of components, which should exceed about 20 components.
Vital errors in software engineering such as too many requirements being realized in release and poor quality of software architecture are caused by false intuition of the decision maker. SBO can address this problem, it automatically scour the search space for the solutions that best fit the human assumptions in the objective functions. However, it has been widely observed that search techniques are good at producing unexpected answers. Automated search techniques effectively work in tandem with the human encapsulating human assumptions and intuition.
Future work will consider modification of SBO for including dependency relationship between requirements in NRP, between components in MP, and exploring the integrated model for both problems. 5. Doval, D., Mancoridis, S., Mitchell, B.S.: Automatic Clustering of Software Systems using a Genetic Algorithm. In: Proceedings of Software Technology and Engineering Practice, pp. 73--91 (1998)