Search Based Requirements Optimisation: Existing Work & Challenges
Essay by Maxi • June 28, 2011 • Research Paper • 2,299 Words (10 Pages) • 1,956 Views
Essay Preview: 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
...
...