InTech uses cookies to offer you the best online experience. By continuing to use our site, you agree to our Privacy Policy.

Technology » "New Trends in Technologies", book edited by Blandna Ramov, ISBN 978-953-7619-62-6, Published: January 1, 2010 under CC BY-NC-SA 3.0 license. © The Author(s).

Chapter 9

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

By Mitat Uysal
DOI: 10.5772/7583

Article top

Overview

NASA Software Projects Data in 3D.
Figure 1. NASA Software Projects Data in 3D.
Measured Data and Predicted Values according to the first model.
Figure 2. Measured Data and Predicted Values according to the first model.
Surface of Effort E=f(LOC,ME).
Figure 3. Surface of Effort E=f(LOC,ME).
Measured Data and Predicted values according to the second model.
Figure 4. Measured Data and Predicted values according to the second model.

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

Mitat Uysal1

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.

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+e
(1)

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)+g
(2)

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)2
(3)

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
10 3.100026.00007.0000
11 4.200019.00009.0000
12 7.800031.00007.3000
13 2.100028.00005.0000
14 5.000029.00008.4000
1578.600035.000098.7000
16 9.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.

media/image4.png

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.

media/image5.png

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.

media/image6.png

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.

media/image7.png

Figure 4.

Measured Data and Predicted values according to the second model.

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.

References

1 - V. Basili, 1980 “Models and Metrics for Software Management and Engineering”, IEEE Computer Society Press,
2 - C. J. Burgess, M. Lefley, 2001 Can“.GeneticProgramming.ImproveSoftware.EffortEestimation?. A.ComperativeEvaluation”. InformationSoftwareTechnology. 43 863 873
3 - M. C. Cunha, ., L Ribeiro, .,” 2004 Tabu search algorithms for water network optimization.”,Europ.J. Operational Res. 157 746 758
4 - R. Dillibabu, K. Krashnaiah, , 2000 “Cost Estimation of a Software Product Using COCOMO Model- a case study”, Int. Journal of Project Management 23, 297-307, 2005
5 - C. Houch, J. Joines, M. G. Kay, 1996 Genetic“. A.Algorithmfor.FunctionOptimization. A.MatlabImplementation”. A. C. M.Trans On Math. Software,
6 - S. J. Huang, N. H. Chiu, 2006 Optimization“.ofAnalogy.Weightsby.GeneticAlgorithm.forSoftware.EffortEstimation..InformationSoftwareTech. 48, 1034 1045 ,
7 - J., Kaczmarek, M. Kucarski, . 2004,“Size and Effort Estimation for Applications Written in Java. Information and Software Tech. 46, 589 601
8 - G. J. Knafl, J. A. Morgan, R. L. Follenweider, R. M. Korcich, “Software.failuredata.analysisusing.theleast.squaresapproach.thetime.perfailure.concept”Int. J., Morgan, J.A., Follenweider, R.L., Korcich, R.M., “Software failure data analysis using the least squares approach and the time per failure concept”, Int. J. Reliability, Quality, Safety Eng., 2 161 175
9 - T. Mantere, J. T. Alender, . Evolutionary“.SoftwareEngineering. A.review”Appl.SoftComputing. 315 331 2005
10 - J. F. Peters, S. Ramanna, 1996 Application“.ofthe.ChoquetIntegral.inSoftware.CostEstimation”. IEEE .862 866
11 - R. S. Pressman, 1992SoftwareEngineering. A.Practitioner’sApproach.The McGraw. Hill,
12 - A. F. Sheta, 2006 Estimation“.ofthe. COCOMO. ModelParameters.UsingGenetic.Algorithmsfor. NASA. SoftwareProject”. Journalof.ComputerScience. 2(2), 118-123,
13 - M. Shin, A. L. Goel, 2000Empirical“.DataModeling.inSoftware.EngineeringUsing.RadialBasis.Functions”I. E. E. E. and Software Eng. 26 6 June
14 - M. Uysal, “2006 Multivariate Interpolation Model to Estimate the Effect Component of Software Project ”, Inf. Tech. Journal 5 (6), 1143-1145,
15 - X. Xianghua, .,L., Xingang, R. Jianxun, ,” 2007 Optimization of heat conduction using combinatorial optimization algorithms,Int.J. of Heat and Mass Transfer,50 1675 1682
16 - H. Youssef, S. M. Sait, H. Adiche, 2001 Evolutionary“.AlgorithmsSimulated.AnnealingTabuSearch. A.ComparativeStudy”. Eng Appl. of Artificial Int. 14, 167 181