Open access peer-reviewed chapter

Estimation of the Effort Component of the Software Projects Using Heuristic Algorithms

By Mitat Uysal

Published: January 1st 2010

DOI: 10.5772/7583

Downloaded: 2453

Abstract

In this study, a multivariate interpolation model was developed to estimate the effort component of the software projects. A COCOMO based equation was used to represent the effort function. The data set that was used consists of two independent variables, first is Lines of Code (LOC) and second is Methodology (ME) and one dependent variable Effort (CE). Data set is taken from NASA projects and the results that are obtained in this work are compared with the results of A.F.Sheta who is produced a similar model for estimating the effort component of software projects.

Keywords

  • Curve fitting
  • heuristic optimization
  • software cost estimation
  • software engineering

1. Introduction

The goal of an optimization method is to find the optimum solution of a given problem. If the goal function is a cost function, then optimum solution can be obtained by finding the minimum value of the function.

An optimization process proceeds with two important actions:

  1. a) Search

  2. b) Determining the improvement.

The goal function represents the objective in terms of the parameters and variables involved in the optimization problem.

Several search methods are used in the related optimization studies.

The purpose of this paper is to compare three of these search methods with respect to their applicability to the prediction of the effort component of the software projects.

There are three main classes of search techniques for problems of combinatorial optimization:

  1. 1. Enumerative techniques

  2. 2. Implicit enumerative techniques

  3. 3. Calculus-based techniques

Implicit enumerative techniques can be separated into two groups:

  1. 1. Guided search techniques

  2. 2. Neural networks

Guided search techniques consist of three algorithms:

  1. 1. Simulated annealing

  2. 2. Evolutionary algorithms (evolutionary strategies, genetic algorithms)

  3. 3. Tabu search (Affenzeller et al.)

Particle swarm optimization(PSO) is a new method in evolutionary computation that is similar to genetic algorithm in that the system is initialized with a population of random solutions.

In this study,simulated annealing algorithm is used as heuristic optimization algorithm.

The importance of software cost estimation is well documented. Good estimation techniques serve as a basis for communication between software personnel and non-software personnel such as managers sales people or even customers Knafe, 1995.

Resource models consist of one or more empirically derived equations that predict effort (in person-months), project duration (in chronological months) or the other pertinent project data.

Basili Basili 1980 described four classes of resources models:

  • Static single – variable models

  • Static multi – variable models

  • Dynamic multi – variable models

  • Theoretical models

The static single – variable model takes the form:

Resource = P1 * (Estimated Characteristics) P2

Where the resources could be effort, project duration, staff size or requisite lines of software documentation. The parameters P1 and P2 are derived from data collected from past projects. The basic version of the Constructive Cost Model or COCOMO is an example of a static single variable model.

Static multi – variable model has the following form :

Resources = P11 e1 + P21 e2 + ------ + Pn1 en

Where e i is the i’th software characteristics and P11, P21 are empirically derived optimal parameters for the i’th characteristics Pressmann, 1992.

A dynamic multi – variable model projects resource requirements as a function of time.

A theoretically approach to dynamic multi – variable modeling hypothesizes a continuous resource expenditure curve and from it, derives equations that model the behaviour of the resource. The Putnam estimation model is a theoretical dynamic multi – variable model.

Some new models are proposed for software cost estimation. One of them is Peters and Ramanna Model based on an application of the Choquet integral Peters and Rommano, 1996.

Fuzzy logic and neural networks are the other tools to develop software cost estimation models.

In the recent studies, evolutionary algorithms and genetic algorithms are widely used to estimate the optimal parameters of the software cost models. Typical examples are Sheta, 2006 and Huang and Chiu, 2006.

Dillibabu and Krish-naiah have developed an effort estimation model using COCOMO ΙΙ. 2000 reference.

Burgess and Lefley have concluded that Genetic Programming can offer significant improvements in accuracy of effort parameters but this depends on the measure and interpretation of accuracy used.

Shin and Goel described a detailed Radial Basis Function modeling study for software cost estimation using well-known NASA dataset.

Mantere and Alander have required the work applying computational evolutionary methods in software engineering.

Kaczmarek and Kucharski have presented a methodology for estimation of software size and effort at early stages of software development.

(Uysal, 2006) has developed a multivariate interpolation model to estimate the effort component using Lagrange interpolation model.

Advertisement

2. Effort Estimation Model That Is Used In This Study

Effort estimation can be used for several purposes. One of them is to use for project management purposes. Effort estimation methods can be classified in many groups.

The following software effort model is used in the present study:

E = f (LOC, ME)

Where E is effort, LOC is the number of lines of the developed Code and ME is methodology used in the software project.

f is a nonlinear function in terms of LOC and ME.

We present two different functions for f :

I.First function for f is expressed as below:

E=a.LOCb+c.MEd+eE1

The presented model contains five parameters a, b, c, d and e. This model is slightly different than the model that is proposed in Sheta, 2006.

II.Second function for f is expressed as below :

E=a.LOCb+c.MEd+e.ln(ME)+f.ln(LOC)+gE2

Above presented model is original and firstly proposed in this study.

Model contains 7 parameters; they are a, b, c, d, e, f and g.

3. Solution Method

In multidimensional global optimization,the main goal is to find a global optimum of an objective function defined in a given space. Deterministic and heuristic methods are used to solve multidimensional optimization problem.In some cases,hybrid techniques can be used to.

The following solution method is used to find optimal values of the model parameters:

Minimize     i=1n(Emeas-Ecomp)2E3

Where Emeas, is measured value of effort, Ecomp is computed value of effort according to the model used.

In order to minimize the total squared error given above, simulated annealing algorithm is used changing the parameter values of the model.

4. Evolutionary Computation and Simulated Annealing Algorithms

Evolutionary algorithms, simulated annealing and tabu search are widely used heuristic algorithms for combinatorial optimization.

The term evolutionary algorithm is used to refer to any probabilistic algorithm whose design is inspired by evolutionary mechanisms found in biological species Youssef et al., 2000.

One of the most widely known of heuristic algorithms is simulated annealing (SA) algorithm. SA exploits an analogy between the way in which a metal cools and freezes into a minimum energy crystalline structure (the annealing process) and the search for a minimum in a more general systemXianghua et al.,2007.

Simulated annealing is a generalization of a Monte Carlo method for examining the equations of state and frozen states of n-body systems that is found by Metropolis et al. in 1953.

In the optimization process, the solution randomly walks in its neighborhood with a probability determined by Metropolis principle while the system temperature decreases slowly; when the annealing temperature is closing zero, the solution stays at the global best solution in a high probability.Xianghua et al.,2007

An original MATLAB code is developed for simulated annealing algorithm in this work. This code is used to estimate the optimal values of the parameters of model 1 and model 2.

5. Results

Optimization algorithm have been applied on NASA software project data like Shin and Goel, 2000 and Sheta, 2006.

The data set consist of two independent variables, Lines Of Code (LOC) and the Methodology (ME) and one dependent variable, effort. LOC is described in Kilo Line of Code and effort is in man-months. Data set is given in Table 1.

Project NoKDLOCMEMeasured Effort
190.200030.0000115.8000
246.200020.000096.0000
346.500019.000079.0000
454.500020.000090.8000
531.100035.000039.6000
657.500029.000098.4000
712.800026.000018.9000
810.500034.000010.3000
921.500031.000028.5000
103.100026.00007.0000
114.200019.00009.0000
127.800031.00007.3000
132.100028.00005.0000
145.000029.00008.4000
1578.600035.000098.7000
169.700027.000015.6000
1712.500027.000023.9000
18100.800034.0000138.3000

Table 1.

NASA software project data Measured Effort.

Figure 1 shows same data in 3D space.

Figure 1.

NASA Software Projects Data in 3D.

The optimal values of parameters in the first function (1) were estimated using Simulated Annealing algorithm as below:

a=3.3275 b=0.8202 c= - 0.0874 d= 1.6840 e=18.0550

So, function can be written as follows :

E=3.3275.LOC0.8202 - 0.0874.ME1.6840 + 18.0550

The required iteration number is 1200.

Figure 2 shows the measured data (NASA projects data) and the predicted values obtained according to the function given above.

Figure 2.

Measured Data and Predicted Values according to the first model.

Applying the two variables (LOC and ME) mentioned above, the effort model surface as a function of LOC and ME was obtained as shown in Figure 3.

Figure 3.

Surface of Effort E=f(LOC,ME).

The optimal values of parameters in the second function (2) were estimated using Simulated Annealing Algorithm as below:

a=3.8930 b=0.7923 c= - 0.2984 d= 1.3863 e=2.8935

f= -1.2346 g=15.5338

Second function can be written using these optimal values as follows:

E=3.8930.LOC0.7923 - 0.2984.ME1.3863 + 2.8935.ln(ME) -1.2346.ln(LOC) + 15.5338

The required iteration number for the second model is 1910.

For the optimal solutions, the total squared error in the second function is less than the total squared error in the first function.

Figure 4 shows the measured data and the predicted values obtained according to function given above.

Figure 4.

Measured Data and Predicted values according to the second model.

Advertisement

6. Conclusion and Future Work

In this paper, it has been shown that Simulated Annealing algorithm can be used to estimate the optimal parameters of the effort components of software projects. The upper and lower bounds of the search space should be considerately given by designer or be cited from other reference papers, if possible. Generally speaking, if a larger search space is built, it would be more time of computations and convergence of search may become very slow. Conversely, if the search space is set too small, the optimal parameters probably could not been found.

A new model has been proposed (model 2) to estimate the software effort.

It can be seen that this new model provides better results than the previous studies.

The effectiveness of SA’s tend to depend on implementation details, how the problem is encoded etc. Mantere et.al, 2005.

All three heuristic search algorithms(GeneticAlgorithms,TabuSearch,SimulatedAnnealing) work well and produce an acceptable sub-optimal solution within a reasonable amount of time.

The SA algorithm outperforms the TS and GA algorithms in all the simulation runs.

In the future work, a GUI will be developed for the two variables estimation model.

© 2010 The Author(s). Licensee IntechOpen. This chapter is distributed under the terms of the Creative Commons Attribution-NonCommercial-ShareAlike-3.0 License, which permits use, distribution and reproduction for non-commercial purposes, provided the original is properly cited and derivative works building on this content are distributed under the same license.

How to cite and reference

Link to this chapter Copy to clipboard

Cite this chapter Copy to clipboard

Mitat Uysal (January 1st 2010). Estimation of the Effort Component of the Software Projects Using Heuristic Algorithms, New Trends in Technologies, Blandna Ramov, IntechOpen, DOI: 10.5772/7583. Available from:

chapter statistics

2453total chapter downloads

1Crossref citations

More statistics for editors and authors

Login to your personal dashboard for more detailed statistics on your publications.

Access personal reporting

Related Content

This Book

Next chapter

Design of Neural Network Mobile Robot Motion Controller

By Jasmin Velagic, Nedim Osmic and Bakir Lacevic

Related Book

First chapter

Diversifying Electricity Customer Choice: REVing Up the New York Energy Vision for Polycentric Innovation

By Joseph Nyangon and John Byrne

We are IntechOpen, the world's leading publisher of Open Access books. Built by scientists, for scientists. Our readership spans scientists, professors, researchers, librarians, and students, as well as business professionals. We share our knowledge and peer-reveiwed research papers with libraries, scientific and engineering societies, and also work with corporate R&D departments and government entities.

More About Us