Search Based Requirements Optimisation: Existing Work & Challenges

Search Based Requirements Optimisation:

Existing Work & Challenges

Yuanyuan Zhang y, Anthony Finkelstein z, and Mark Harman y

y King's College London zUniversity College London

Strand, London Malet Place, London

WC2R 2LS, UK WC1E 6BT, UK

Abstract. In this position paper, we argue that search based software

engineering techniques can be applied to the optimisation problem dur-

ing the requirements analysis phase. Search based techniques o®er sig-

ni¯cant advantages; they can be used to seek robust, scalable solutions,

to perform sensitivity analysis, to yield insight and provide feedback ex-

plaining choices to the decision maker. This position paper overviews

existing achievements and sets out future challenges.

1 Introduction

Once an initial set of requirements has been gathered by requirements elicitation,

there is a business-level analysis problem: choices have to be made to identify

optimal choices and trade{o®s for decision makers. For example, one important

goal is to select near optimal subsets from all possible requirements to satisfy

the demands of customers, while at the same time making sure that there are

su±cient resources to undertake the selected tasks.

To illustrate, Figure 1 demonstrates a possible spread of equally optimal

requirements optimisation results. Two competing objectives are considered: cost

to the provider and estimated satisfaction rating achieved by a solution. Each

circle on the represents an equally optimal solution. That is, each circle denotes a

solution for which no better solution (subset of requirements) can be found that

o®ers better customer satisfaction without increasing cost. The set of possible

solutions form what is known as a Pareto front. Pareto fronts show a solution

space of candidate solutions, from which the decision maker can select. As will

be seen later, Pareto fronts also yield insights into the structure of the problem.

This requirement selection problem is one example of the way in which re-

quirements decisions can be formulated as optimisation problems. Other exam-

ples include ordering requirements to achieve earliest satisfaction, balancing each

customer's needs against the others and balancing tensions between system and

user requirements.

Such problems are inherently complex optimisation problems that seek to

balance many competing and conoicting concerns, so it would be natural to

seek algorithms for decision support. Sadly is often infeasible to apply precise

analytic algorithms, because the problems are typically NP hard. To overcome

this di±cultly, Search Based Software Engineering (SBSE) uses metaheuristic

optimisation algorithms that explore and solve complex, multi-objective, highly

constrained problems in Software Engineering [5]. This paper argues that Re-

quirements Optimisation can be viewed as an application area for SBSE.

0 2000 4000 6000 8000 10000 12000 14000

−140

−120

−100

−80

−60

−40

−20

0

Customers' Satisfaction Rating

−1*Cost

Fig. 1. Fictitious Data: 15 customers; 40 requirements. Adapted from Zhang et al. [13].

Each circle represents an equally optimal candidate solution that balances the objective

of minimising supplier cost against the objective of maximising customer satisfaction.

See Figure 2 for a comparison to real world requirements data from Motorola.

2 Background: Requirements Optimisation

Previous work on Requirements Optimisation has shown that metaheuristic op-

timisation techniques can be used to search for a balance between costs and

bene¯ts associated with sets of requirements. This has come to be known as the

Next Release Problem (NRP) [2]. In the NRP, as formulated by Bagnall et al.,

the goal is to ¯nd the ideal set of requirements that balance customer requests

within resource constraints.

In this formulation the problem is a constrained single objective optimisation

problem. Bagnall et al. applied a variety of techniques to a set of synthetic data

to demonstrate the feasibility of SBSE for this problem. Greer and Ruhe also

studied the NRP [4], proposing an iterative Genetic Algorithm and presenting

results for real world requirements problems. Their approach balances the re-

sources required for all releases; assessing and optimizing the extent to which

the ordering conoicts with stakeholder priorities.

More recently, there has been work on multi-objective formulations of the

NRP