LEMABE: a novel framework to improve analogy-based software cost estimation using learnable evolution model

Analogy-based estimation method

The analogy-based estimation is a very simple, efficient, and practical method in its nature. In this method, no particular formula is used, and in order to estimate a new project, it has to be compared with similar projects which have completed in the past, known as historical datasets or repositories. Analogy-based estimation consists of four parts, including the historical dataset, similarity function, K-nearest neighbors, and solution function. Moreover, its process consists of the following steps:

1. Creating the historical dataset accessible through real or artificial datasets;

2. Obtaining features associated with a new project in a way that they are in line with historical datasets;

3. Using a predefined similarity function such as the Euclidean or Manhattan distance functions so that can be retrieved the projects similar to the new project;

4. The new project’s cost is estimated using the solution function.

In the following, each component of the analogy-based estimation system has been separately described briefly.

Similarity function

The similarity function is the core of the analogy-based estimation method, in which the degree of similarity between two different projects is calculated. The general form of the similarity function is as follows:

(1) $sim\left(p.p^{\mathrm{\prime }}\right)=f\left(Lsim\left(f_1.f_1^{\mathrm{\prime }}\right).Lsim\left(f_2.f_2^{\mathrm{\prime }}\right).\dots Lsim\left(f_n.f_n^{\mathrm{\prime }}\right)\right)$where p and p′ are indicative of the new and old projects in the repository, $f_i$ and $f_i^{{}^{\prime }}$ indicate the value of the i^th feature in the mentioned projects, n is the total number of features in each project, and $Lsim(.)$ function calculates the degree of similarity between two corresponding features of the projects. $Lsim(.)$ and $f(.)$ functions show the general structure of the similarity function. Among the various types of similarity functions, Euclidean distance similarity function (ES) and the Manhattan distance similarity function (MS) are the most useful ones in the software development cost estimation domain. In mathematics, the Euclidean distance is the ordinary distance between two points used in comparing the distances by optimization problems (Shepperd & Schofield, 1997). The similarity between the two projects is obtained using the Euclidean Similarity distance through Eq. (2) (Hong & Kim, 2000).

(2) $sim\left(p.p^{\mathrm{\prime }}\right)={\displaystyle \frac{1}{\left[\sqrt{\sum _{i=1}^n{w}_{i}Dis\left(f_i.f_i^{\mathrm{\prime }}\right)+\delta }\right]}\delta =0.0001}$

$$\{\begin{array}{c}{\left(f_i-f_i^{{}^{\prime }}\right)}^{2}iffeaturesarenumeric\\ 1iffeaturesarenumericand{f}_i=f_i^{{}^{\prime }}\\ 0iffeaturesarenumericand{f}_i\ne f_i^{{}^{\prime }}\end{array}$$where $w_i$ is the i^th feature’s weight, and its value is between 0 and 1. Also, $\delta =0.0001$ is a small fixed number that is placed in the equation to prevent division by zero.

The Manhattan Similarity distance (MS), also known as the city block distance-based similarity, is a type of Euclidean distance in which the distance between two points is the sum of the absolute differences of their coordinates. It is shown in Eq. (3) (Gardner, 1997).

(3) $sim\left(p.p^{\mathrm{\prime }}\right)={\displaystyle \frac{1}{\left[\sum _{i=1}^n{w}_{i}Dis\left(f_i.f_i^{\mathrm{\prime }}\right)+\delta \right]}\delta =0.0001}$

$$\{\begin{array}{c}\left|f_i-f_i^{{}^{\prime }}\right|iffeaturesarenumeric\\ 1iffeaturesarenumericand{f}_i=f_i^{{}^{\prime }}\\ 0iffeaturesarenumericand{f}_i\ne f_i^{{}^{\prime }}\end{array}$$

Since the dataset is developed base on trial and error, there is no obligation in choosing the Euclidean function or Manhattan function. The nature of the projects and the level of their normality in the data set can have a significant impact on the performance of similarity functions. In some previous works, several other similarity functions have been used, including rank mean similarity (Walkerden & Jeffery, 1997), maximum distance similarity, Minkowski similarity (Angelis & Stamelos, 2000), but there is no specific method to show the best similarity function (Li & Ruhe, 2008; Li, Xie & Goh, 2008). In a systematic literature review, Wen et al. (2012) identified 8 machine learning models for software effort estimation. Most of these studies have been done on the Euclidean, Manhattan, and Minkowski distance, and a limited number of them have determined the similarity degree between two projects using Grey distance (Azzeh, Neagu & Cowling, 2010).

K-Nearest Neighbor

The KNN algorithm is an example of instance-based learning, in which the training datasets are stored, and then, classification for a record that has not been classified yet is done simply by comparing it with the most similar records in the training dataset (Larose & Larose, 2014). The number of KNN is known as a vital parameter very effective on accuracy. Regarding the selection of k value, if k is very small, the effect outliers or unusual observations (noise) increases, and if k value is very large, the local behavior is ignored. Some of the papers have suggestions for how to keep k value fixed (Chiu & Huang, 2007), but k value is dynamic in most papers.

Solution function

In this section, it will be clarified how we can use similar projects and combine them in order to estimate costs for the new project. The following evaluation methods have been used as a basis for the solution function in this research:

• Closest analogy (Walkerden & Jeffery, 1999);

• Unweighted mean;

• Median;

• Inverse distance weighted mean.

Mean is known as a classic criterion, which has a central tendency. In addition, the average software cost (k values) can be calculated when k > 1. Median is another classic criterion with central tendency. In this criterion, software costs (k values) can be calculated when k > 2. In comparison with mean, the median is a stronger statistical criterion because it is more sensitive to outliers. At the same time, number of outliers will growth by increasing the number of projects. Inverse distance weighted mean shows that similar projects are more important than less similar ones. Equation (4) shows the formula of inverse distance weighted mean (Kadoda et al., 2000).

(4) $\widehat{C_p}=\sum _{k=1}^n{\displaystyle \frac{Sim\left(P.P_k\right)}{\sum _{i=1}^{n}Sim\left(P.P_k\right)}{C}_{pk}}$where P shows the project whose cost has to be estimated. P_k is the k^th similar project. $Sim\left(P.P_k\right)$ is indicative of the similarity between projects P and P_k, and C_pk is the cost of the most similar project to P_k.

Because the solution function is one of the most influential components in estimating accuracy, several studies have attempted to improve its performance. Some studies have used only one solution function (Li & Ruhe, 2008), while other studies have considered several types of solution functions (Li, Xie & Goh, 2009).

Learnable evolution model

All common methods of evolutionary computations have been inspired by Darwin’s theory’s principles: “…one general law, leading to the advancement of all organic beings, namely, multiply, vary, let the strongest life and the weakest die” (Darwin, 1987). Darwin’s evolutionary computations are semi-blind, in which operators such as mutation (an unusual reproduction with variety), crossover (sexual reconstruction or recombination), and selection (survival of the fittest) were used to produce new population. In this type of evolution, individuals of the new population are not guided by the trained individuals of the previous population, but there is a trial and error process that is done in a parallel way. The main idea of LEM comes from a combination of evolutionary search and machine learning methods introduced in 2000 (Michalski, 2000). This strategy runs a machine learning model so that it can identify those individuals performing better in doing tasks. These reasons are expressed as inductive hypotheses and then used to produce the new population of these individuals. In fact, the new population is produced using hypotheses related to individuals with high fitness in the previous population.

LEM may switch between the machine learning mode and Darwinian Evolution mode or rely completely on machine learning. If LEM only runs the machine learning mode, it is so repeatedly applied that machine learning reaches evolution for the new population. While working with both modes, LEM switches from one mode to another when it can meet the termination condition. The evolutionary process proceeds until the solution for LEM is satisfactory, or the allocated sources become exhausted (Wojtusiak & Michalski, 2006).

The evolution process in LEM begins with a number of individuals of one initial population. In evolutionary processing of individuals may demonstrate solutions to issue or instructions for generating Solutions. An overview of the LEM process is given below:

1. Creating population: the initial population is created randomly or based on a particular method

2. Running the machine learning mode

   1. Extracting the extrema: two groups are selected from the present population members; one group with high performance, known as H-group in short, and one group with low performance, known as L-group in short. The value of these groups is obtained using the fitness function’s value.

   2. Making hypotheses: one machine learning method for describing the H-group and L-group is applied so that it can distinguish the two groups. While describing H-group or L-group, the evolution history, i.e., the previous population or description of previous populations, has to be taken into account.

   3. Creating a new population: to do so, the samples learned in the H-group have to be combined with the new population. Describing samples is done either randomly or in the form of rules from the described samples.

   4. Proceeding to step (2-a) and repeating the machine learning mode until it reaches the termination condition. Once the termination condition is met in the machine learning mode, one of the following actions can be taken:

      • 1) Ending the evolution process

      • 2) Repeating the process from stage 1; this operation is called start-over.

      • 3) Proceeding to stage 3

3. Running the Darwinian evolution mode: in this section, one of the methods of Darwinian evolution is run, i.e., one mutation, crossover, and selection is applied for producing the new population. This operation is ongoing until the Darwinian evolution mode reached the termination condition.

4. Alternating the modes: in this mode, we proceed to stage two and then keep switching between stages 2 and 3 until the LEM termination condition is met. The best-obtained individual is the evolution result.

The termination condition in the machine learning mode is fulfilled in a day if a particular level of performance is reached. In this stage, if the termination condition of LEM is not met yet, the start-over operation is run, or it proceeds to the termination condition of the Darwinian evolution mode. If LEM always selects the start-over operation, the evolution process will only be based on a repetitive program of the machine learning mode. This version of LEM operation is called uniLEM because it does not include the Darwinian evolution mode. If LEM uses both modes, it is called duoLEM. The flowchart of LEM algorithms has been illustrated in Fig. 1.

When LEM selects the start-over operation, it has to proceed to stage 1. One simple solution for running stage 1 is to describe a new population like in other evolutionary algorithms randomly. In LEM, however, this usually happens for the first time while running stage 1, and there are other methods such as select-elite, avoid-past-features, using suggestions, and creating another variant for running the start-over operation.

Evaluation criteria

Since different researches use different functions for testing their methods, selecting suitable evaluation criteria for comparison with other methods is a difficult task because the evaluation criteria employed in different papers are different, and in most cases, the program’s source code is not available. For this reason, in this research, we have tried to use the most common evaluation criteria that have been used in the majority of papers.

The magnitude of Relative Error (MRE) is the most common performance indicator used for measuring the efficiency of software prediction models. MRE calculates the percentage of absolute error against the real effort, as shown in Eq. (5). The mean of MREs, called MMRE, shown in Eq. (6). Also, the median of MREs is called MdMRE.

(5) $MR{E}_i={\displaystyle \frac{\left|Estimatedvalue-actualvalue\right|}{actualvalue}}$

(6) $$MMRE={\displaystyle \frac{\sum _{i=1}^{N}MR{E}_i}{N}}$$

PRED(X) is another performance indicator that shows the percentage of predictions correctly predicting x value, as defined in Eq. (7).

(7) $PRED\left(x\right)=\sum _{i=1}^N{D}_i\ast {\displaystyle \frac{100}{N}}$

$$D_i=\{\begin{array}{c}1ifMMRE<{\displaystyle \frac{x}{100}}\\ 0otherwise\end{array}$$

$$whenx=25thePREDmetricisdefindasPRED\left(0.25\right)$$

Since most of the papers have used these three criteria for evaluating their proposed methods, we used the same criteria in the current research too. The goal is to minimize MMRE as the final error value and maximize PRED (0.25).

Training phase

In this phase, a set of training data is given to the model, and the analogy-based cost estimation system is adjusted by features weight, and the LEM algorithm investigates the weight vector in training samples to minimize errors. Except for EFFORT, the rest of the features are considered independent features. Initially, the weight of all features is randomly selected in the range of 0 to 1. Of course, the weights can be equalized, in which case all weights are selected 0 or 1. In this phase, a project is selected in each iteration from the training data, and it is estimated using the proposed equations, i.e., the similarity function, k, the nearest neighbor, as well as the solution function. The important point in this process is that we will use it to find the optimal weights. Indeed, the weights are suggested by the LEM algorithm and injected into the model. The amount is then estimated as the proposed cost for that project. The proposed cost is compared to the real cost of the project, and its MRE metric is calculated. This process is repeated until all training projects are estimated. In the next step, MMRE and PRED (0.25) are calculated using the MRE values obtained for training data, and these values are passed (sent) to the LEM algorithm. The weights are changed (modified) by the LEM by evaluating the evaluation criteria until the termination criteria (number of repetitions (iterations) or error rate) are met (satisfied) and the weights are recorded as optimized weights. Architecture of this phase has been illustrated in Fig. 2.

Testing phase

The main purpose of the testing phase is to assess the accuracy of the estimation model made using the testing data. In this phase, the optimized weights obtained from the training phase are applied to the similarity function. Similar to what was done in the training phase, a project is entered into the model and then using the similarity function, K nearest neighbors and solution function, the cost is predicted, and MRE will be counted. This process is repeated for all testing data. Finally, the MMRE and PRED (0.25) evaluation criteria are calculated. The architecture of this phase has been illustrated in Fig. 3.

Experiment design

In the present research, three popular datasets, i.e. Desharnais, Maxwell and ISBSG, were used to evaluate the proposed method. If the accuracy of the cost estimation model is calculated using the projects used to make the model, performance appraisal may be very optimistic, and Estimation error, in this case, maybe significantly lower and may not work well in real-world environments (Hayes, Ryan & Zseller, 1994). In the meantime, the cross-validation approach provides a more realistic, more accurate assessment, in which the data set is divided into several sets of training and testing data. In this paper, 10-fold cross-validation validations are used. In order to design the experiment and to evaluate the proposed method using different experiments, the preprocessing operation has to be run on the data at first. Data preprocessing is one of the most important parts of estimation problems, and its goal is for all features to have the same effect on the target feature. To do so, the data will become normal within the interval [0, 1] using the min-max equation. The normalization operation is done to remove different effects of features (Dejaeger et al., 2011). Then, to train the proposed model, the training datasets have to be divided into training datasets and testing datasets. This was done through the 10-fold cross-validation method in this research. In this division, the datasets are randomly divided into 10 almost-equal sets, among which one set is considered the testing dataset and nine other sets are considered the training datasets.

As mentioned earlier, the analogy-based estimation method has three control parameters, including similarity function, K-nearest neighbor, and solution function. In designing the present experiment, Euclidean and Manhattan distances employed for similarity function and the most common solution functions, i.e., median and mean, used to obtain the proposed estimation value. Moreover, the number of closest projects with each other was assumed as variables within the interval of 1 to 5. After specifying the values of parameters, we first defined the effect of different combinations of these parameters in the search space of each parameter and finally selected the most appropriate produced model to be tested with other methods.

Experimenting with the proposed method

To experiment the proposed model, the possibility of obtaining the most desirable configuration of the analogy-based estimation method was investigated. To do so, we used three evaluation criteria, i.e., MMRE, PRED (0.25), and MdMRE on Desharnais, Maxwell and ISBSG datasets.

Tables 2–4 show the results of applying the proposed model on the Desharnais and Maxwell datasets, respectively, in which different combinations of the main ABE parameters, which include KNN, similarity function, and solution function, are presented.

According to the proposed framework, evaluating the best option in different criteria was different, but the most suitable and responsive model for all datasets belongs to the Euclidean distance and k-nearest neighbor as well as the median solution function. In addition, the lowest value of MMRE and MdMRE belongs to the Euclidean distance with five nearest neighbors as well as the median solution function, but their PRED value does not contain the highest value among models, although it has relatively suitable values. Based on the obtained results, the highest value of PRED belongs to the Manhattan distance and three nearest neighbors, as well as the median solution function. The summarization from the Best Results of the Model’s Evaluation based on Three Datasets shown in Table 5.

Comparing the efficiency of LEMABE with other methods

One point to consider while comparing some methods is that the criteria of evaluation functions’ quality and the selected intervals of datasets must be the same so that comparison is made properly. The performance of the proposed framework was validated and compared with the most efficient and commonly used variants of other popular models, namely PSO-based, GA-based feature weight optimization in ABE (GA-ABE), Differential evolution in ABE (DABE), ANN with backpropagation learning-based (de Barcelos Tronto, da Silva & Sant’Anna, 2008; Park & Baek, 2008; López-Martín, 2015), Radial basis function (RBF)-based SDEE (Shin & Goel, 2000). Also, one of the regression-based estimation methods which is multiple regression (MLR) (Mittas & Angelis, 2010), was involved in the comparison process. All of the estimation frameworks using historical data sets and the algorithm parameters were adjusted automatically. The results of such comparisons were applied to different datasets, as shown in Tables 6–8.

Table 6 shows the results of using the selected estimation methods on the Deshernais dataset based on MMRE, MdMRE and PRED (0.25) criteria. The results show that the proposed model produces more accurate estimates in the testing phase than other methods [MMRE = 0.21, PRED (0.25) = 0.60, MdMRE = 0.15] and subsequently (DABE with values [ MMRE = 0.24, PRED (0.25) = 0.52, MdMRE = 0.23] and the worst estimate was for MLR [MMRE = 0.82, PRED (0.25) = 0.22, MdMRE = 0.76].

The results of applying different estimation models on the Maxwell data set are shown in Table 7. As can be seen in the table, the proposed model has achieved the best performance criteria among other models, the values of which are [MMRE = 0.11, PRED (0.25) = 0.61, MdMRE = 0.16]. GA-ABE was followed by [MMRE = 0.23, PRED (0.25) = 0.53, MdMRE = 0.26]. In addition, MLR produced the worst estimates [MMRE = 0.84, PRED (0.25) = 0.29, MdMRE = 0.83].

Table 8 shows the estimate valuesobtained using the proposed model in the ISBSG dataset. As seen in the table, the performance range of metrics for ISBSG dataset is quite different from the others. The best performance is obtained with [MMRE = 0.61, PRED (0.25) = 0.59, MdMRE = 0.69]. DABE [MMRE = 0.69, PRED (0.25) = 0.58, MdMRE = 0.69] is the closest method to the proposed model and MLR provides the worst estimates for this dataset [MMRE = 0.98, PRED (0.25) = 0.20, MdMRE = 0.99].

As can be seen in the above tables, the value of MMRE and MdMRE criteria is lower than similar values in comparison with other models. Since improving the proposed model and providing comprehensive and clear results is the main goal of this article, to achieve this goal, the percentage improvement of ABE, PSO-based, GA-ABE, DABE models compared to the proposed model are shown in Figs. 4–6. Due to the lack of proper results in ANN, RBF and MLR models, they have been discontinued.

Figure 4 shows the progress made using the proposed model in the Deshernais dataset. According to Fig. 4, the most advanced is the ABE model, in which the evaluation criteria of MMRE, MdMRE, and PRED (0.25) have values of 50%, 57%, and 20%, respectively. The improvement rates of MMRE and MdMRE are almost the same in both PSO-based and GA-ABE models, while in these models, the PRED (0.25) improvement rate is less than 10%. This suggests that the scope of improvement is limited to a few projects. Meanwhile, the percentage of improvement of DABE model has been lower than other models. In general, it can be concluded that in this data set, the progress of MMRE and MdMRE in all estimation models has been higher than PRED (0.25), and LEM can significantly improve the ABE performance in Deshernais data set.

The improvement percentage of the proposed model is shown in Maxwell’s dataset in Fig. 5. It is observed that the proposed model has improved the accuracy of the ABE model in all three criteria of MMRE, MdMRE, and PRED (0.25) by 86%, 79%, and 64%, respectively, which does not indicate the wide range of test projects. A high percentage of accuracy increases that the use of LEM can significantly increase ABE performance in the Maxwell data set. It is also observed that the MMRE and MdMRE criteria for other types of estimation models have also increased significantly. The highest PRED (0.25) progress in this data set occurred with 64%. However, in GA, this value has been minimized, which could be due to the similarity of the internal structure of GA and LEM.

Figure 6 illustrates the percentage of improvement obtained using the proposed model in the ISBSG dataset. It has been observed that the PRED value (0.25) for all types of ABE has increased significantly. Due to the number of outliers and nonnormal projects in ISBSG data set, there has been less improvement in the MMRE and MdMRE criteria.