Evolution based memetic algorithm and its application in software cost estimation

Abstract

A new memetic algorithm named EAMDGA is designed by combining the characteristics of Environmental Adaption Method for Dynamic Environment (EAMD) and Genetic Algorithm (GA). This algorithm is highly efficient and robust in solving the unimodal and multimodal problems. It avoids the problems of getting trapped in local optima and premature convergence. Performance of this algorithm is checked over a group of 24 unimodal and multimodal benchmark functions provided by Black Box Optimization Benchmarking (BBOB-2013). It is found that EAMDGA is superior in performance in comparison to the other algorithms.

Keywords

Evolutionary algorithm adaptive learning optimization genetic algorithm EAMD phenotypic structure

1 Introduction

Optimization techniques are used to choose best solutions for different optimization problems. These problems may involve minimization or maximization of certain objective functions. Although a number of optimization algorithms are available to solve these problems, yet each algorithm has some predefined limitations which make it suitable only for a type of problem. For example some algorithm are very good for unimodal problems while others are good for multimodal problems, some of them perform well in exploring the whole search space while others in exploiting every region of the search space.

Hybridization of algorithms is one of the technique through which the aforementioned problems can be solved. In recent years, many hybrid algorithms have been proposed and they have proved their significance over individual algorithms to solve various optimization problems. Hybridization is a technique through which two or more algorithms are combined in such a way that they can remove the limitations of each other. In this paper Environmental Adaption Method for Dynamic Environment (EAMD) [1, 2] and Genetic Algorithm (GA) [5] are combined to establish an evolution-based nature inspired optimization algorithm.

Whatever is left of the paper is sorted out into twelve distinct sections. Section 2, is utilized for background details, which gives brief introduction of EAMD and GA. Related work is given in Section 3. Section 4 is used to explain the proposed work. Section 5 discusses experimental setup and simulation strategies. Result analysis and discussion are shown in Section 6. Application of the proposed algorithm in software cost/effort estimation is shown in Section 7. Finally the proposed work is concluded in Section 8.

2 Background details

EAMD [1, 2] is a population based randomized algorithm which is somehow inspired by the theory of adaptive learning [3] and it is a modified version of Environmental Adaptation Method (EAM) [4]. Adaptive learning theory says that individuals learn from the environment and improve their fitness according to the changes occurred in the environment. Thus, either they may adapt better or worst fitness values over time. If the individuals are able to adopt the environmental changes, they survive in the successive generations otherwise they do not sustain their life and as result eliminate from the environment. Environmental changes are steady and sometimes become more severe to survive. But environment guides individuals to improve their phenotypic as well as genotypic structure to survive against the environmental changes. EAMD has two operators to improve the fitness of the candidate solutions i.e. Adaption and Selection. Adaption is applied first on the individuals to improve their fitness, after that Selection operator is used to select the best individuals from the search space. This process is continued until the specified optimal value is obtained. EAMD is designed considering the natural adaptive technique of organisms against the unfamiliar environment with real valued parameters in the continuous changing environment (Dynamic Environment).

Genetic Algorithm (GA) [5] is a nature inspired algorithm that is based on the phenomena of survival of the fittest. This algorithm is basically based on three operators i.e. selection, crossover and mutation. These operators are applied on randomly generated solutions. Actually GA is an iterative process applied on the population and after each iteration it gives a modified population called generation. For each generation, fitness of each individual is evaluated on the objective function (fitness function). The more fit individuals have more chances to be selected for further operations (like recombination and mutation analogous to biological crossover and mutation) to form a new improved generation. Recombination (crossover) is a process through which more than one parent solutions meet with each other and produce a new child solution from them. Mutation is used to maintain diversity among the population from one generation to another generation. Mutation helps to avoid the search process to get stuck in local optima. This algorithm terminates after satisfying certain criteria i.e. maximum number of generations, or attainment of required fitness value.

3 Related work

Premalatha et al. [6] have proposed a hybrid algorithm to remove the shortcomings of Particle Swarm Optimization (PSO). Their algorithm is used to solve the problem of premature convergence and stagnation in the local optima of PSO through hybridization with Genetic Algorithm (GA). The crossover operator helps PSO to explore the new search area while mutation to PSO helps to increase the diversity in the solution space.

Kao et al. [7] have introduced a hybrid algorithm to optimize the multimodal function globally. Individuals are created in the new generation by the combination of GA operators and mechanism of PSO. In this algorithm, social interaction and private cognition of individuals are used to improve the individuals in new generation. The authors have combined the quality of both GA and PSO through a simple and efficient model to solve different types of continuous optimization problems.

HGAPSO is introduced by Kaveh et al. [8]. This paper has used the SAND formulation as a base to optimize different structures with the help of hybrid implementation of GA and PSO. They have used the maturing phenomena of nature for the evolution of individuals, which is modelled by GA and mimicked by PSO. PSO helps individuals to improve themselves using social interactions and information collected by them. HGAPSO is especially designed to work for larger problems.

The solution of constrained optimization problem is proposed by He et al. [9]. In this paper they have proposed hybrid PSO (HPSO) with a feasibility based rule. They have used Simulated Annealing (SA) to the best solution of the swarm to avoid the premature convergence. HPSO is very effective to solve the constrained optimization problems.

Sheikhalishahi et al. [10] have proposed a GA-PSO based hybrid algorithm to solve reliability redundancy allocation problem. This algorithm concurrently works on more than one things like on one side it increases the overall system reliability while on the other side it reduces the cost, system weight and volume.

In [11], Haung et al. have proposed a FPGA based hybrid GA-PSO algorithm for mobile robot to search an optimal path. This algorithm is specially designed to resolve the global path planning problem in a structure environment with obstacles. In experimental result, GA-PSO has shown the feasible paths in different environments and it gives better result than simple GAs.

To solve the well-known travelling salesman problem (TSP), a new Hybrid Genetic and Simulated Annealing Algorithm (HGSAA) is proposed by Elhaddad et al. [12]. This algorithm applies a new approach to solve the travelling salesman (TSP) problem. In HGSAA, simulated annealing helps genetic algorithm to avoid getting trapped in local minima. The proposed algorithm gives better results within the expected time for symmetric TSPs from TSPLIB.

Loukil et al. [13] have established a Genetic Algorithm (GA) and Simulated Annealing (SA) based hybrid algorithm for solving Quadratic 3-dimensional Assignment Problem (Q3AP). This problem is a kind of NP-hard problem. ParadisEO framework is used to implement the proposed algorithm and GRID5000 is used for checking the performance of the proposed algorithm.

A hybrid Algorithm to solve the Travelling Salesman Problem (TSP) is proposed by Nagpure et al. [14]. They have extended the operators of Artificial Bee Colony (ABC) i.e. Employed Bees, Onlooker Bees and Scout Bees with Genetic Algorithm to enhance the local search strategy. The experimental result shows that both precision and computational time of the hybrid algorithm is found superior than the conventional Genetic Algorithm.

Kumar et al. [15] have established a new hybrid algorithm including Artificial Bee Colony (ABC) and Genetic Algorithm (GA). The name of the proposed algorithm is crossover based ABC (CbABC). Crossover operator of GA is integrated with the ABC to strengthen the exploitation phase of ABC. Linear crossover operator is used with the ABC. The experimental result shows superiority of CbABC over normal ABC. The proposed CbABC can perform well for separable, multivariable, and multimodal function optimization.

A hybrid EDA-PSO algorithm is proposed by El-Abd et al. [16]. This algorithm makes sample of independent Gaussian distribution and this whole thing is based on the best half of the swarm. The choice of using the algorithm is decided by the probability P, used as a participation ratio, if P = 0, algorithm acts as a pure EDA and if P = 1, it acts as pure PSO algorithm. In hybrid approach, P lies between 0 and 1 (0 > P > 1), either PSO is applied on each particle or sampling of all individuals is done through EDA. Improvement in the fitness of particle updates the particle’s position.

Hybridization of PSO and DE is proposed by Nieto et al. [17]. The proposed algorithm DEPSO comprised the idea of DE into PSO. The performance of this algorithm is checked over Black-Box Optimization Benchmarking for noiseless functions (BBOB 2009) with dimensions 2, 3, 5, 10, 20 and 40. DEPSO has obtained accurate level of coverage rate, with simple model and uses relatively small number of function evaluations.

Liu et al. [18] have added an Adaptive Local Search Depth technique in Memetic Algorithm namely MA-ALSD. ALSD helps in arranging the computing resources dynamically for local search related to its performance. Performance of MA-ALSD is checked over Large Scale Continuous Global Optimization test-suite of CEC’2012. Best, worst, median, mean and standard derivation is computed for comparison with other algorithms. Result obtained this algorithm is superior to its competitive algorithms.

A global software optimization tool namely MEMPSODE with adaptive selection of local search namely Adapt-MEMPSODE is proposed by Voglis [19]. It is a variant of MEMPSODE which is static in nature and use only one local search at a time. Benchmark testing of this algorithm is conducted on BBOB 2013 test bed. Performance of this algorithm is found better than it previous version.

Nalepa [20] have proposed a memetic algorithm to solve vehicle routing problem with time windows (VRPTW) namely Adaptive Memetic Algorithm (AMA). During search, selection scheme and population size are automatic adjustable according to the nature of the problem. To maintain exploration and exploitation of the search space a new adaptive selection is used. Its convergence rate is very good as compared to Standard Memetic Algorithm.

4 Proposed work

In EAMD, individuals (each solution) improve their phenotypic structure by the guidelines received from the current environmental conditions. At the time of adaption, each uses adaption window for improving its fitness. Adaption operator of EAMD explores the whole search space to mark all possible good regions where the probability of getting good solutions is high. As the generations increases it automatically starts exploitation around good solutions to find optimal solution. Selection operator selects good solutions for the next generation from the solution space on the basis of their fitness value. The whole process continues until optimal solution isobtained.

In the beginning, size of the adaption window is taken very large that helps solutions to explore the whole search space and to adapt anywhere in the search space. Solutions improve their phenotypic structure individually without social interaction with other solutions. Environment helps solutions to improve their fitness value individually within the adaption window. However, as the solution progresses to capture optimal structure, it starts exploitation and as a result adaption window becomes shorter.

Since these solutions have already attained the best value in their local region, they will stick to the local optima. To recover from this problem they should interact with each other to identify new locations in the search space. Genetic Algorithm techniques are very helpful in improving the solutions by creating new structures through genetic operators (i.e. selection, crossover and mutation).

Technique of GA can help to improve the quality of solutions. When the stagnation problem occur population of EAMD is transferred to GA for the identification of new good regions in the search space. These new good regions are identified by the application of selection, crossover and mutation operators.

The process of GA is continued for fixed number of generations and the improved individuals are transferred to EAMD with new fitness. The individuals again start the process of EAMD (adaption and selection) and if they found stagnation point, the whole population is again transferred to GA. The whole process continues form EAMD to GA and vice-versa until the termination criteria is satisfied. Flowchart of the proposed work is shown in Fig. 1.

4.1 EAMDGA procedure

Step I: Initialization: Population of individuals denoted as POP and it is initialized randomly within the n-dimensional search space. Here f_best is assigned to infinite which denotes the best value of the fitness function. Counter (fail _ count) is used to count the fail attempt whenever f_best is ineffective to improve its value in the successive generations and initialize fail _ count with zero. Adaption Window is used and initialized with the whole search space to represent dynamic environment. A term Window _ Size decides how many generations are required for the “Adaption Window” to shrink. A specific number of generations are used to decide the value of Window _ Size which is calculated by the formula given below: $Window_Size = round (Dimension / 1.5) + 10$ (1)

Dimension denotes the number of variables which occupies the search space.

Step II: Calculation of Fitness Value: Fitness value of each individual is calculated on the 24 noise-less benchmark functions.

Step III: Breeding with improved Individuals in the Population: Adaption operator of EAMD improves the individuals of old population and injects individuals with new fitness value in the population while remaining the size of the population same.

Step IV: { Update Population using the Selection Operator: Old and new population are merged and sorted on the basis of their fitness value to select top n number of individuals form the population. Here n is same to the population size taken earlier. This process of updating the population with new individuals continues until the desired solution is obtained.∥Step V: Measurement of the Improvement in f_best: In this step fitness of the best individual of the updated population is compared with the f_best value of the previous generation. If the fitness value of the best individual of the updated population is better than the previous one then update f_best and reset fail _ count to 0 otherwise increases the fail _ count by 1.∥Step VI: Use Genetic Algorithm (GA) to Update the Population: Application of the GA is based on fail_count. If fail _ count reaches to predefined threshold value, then individual from the old population are updated using GA to produce new individuals in the population and send it back to EAMD. How much iterations are required for GA to improve the old population depends on the number of generations that the individuals have elapsed in EAMD. Finally the population is updated using step IV and reset the fail _ count to 0.∥Step VII: Shrinking of the Adaption Window: The term step _ count decides the shrink time and AW _ shrink gives the estimated value through which the “Adaption Window” will shrink. It represents that how the resultant environment becomes worst to survive.∥Step VIII: Check Stopping Criteria: The stopping condition is decided by the number of function evaluation. If it is greater than the maximum number of function evaluation then the algorithm terminates automatically. Otherwise step III starts for next generation.

5 Experimental setup and simulation strategies for benchmark testing

To check the performance of the proposed algorithm over 24 benchmark functions [22], Black-Box Optimization Benchmarking (BBOB) noiseless test-bed from Comparing Continuous Optimisers (COCO) platform [21] has been used. Different dimensions like 2D, 3D, 5D, 10D, 20D and 40D have been used without any restart mechanism. To compare the proposed hybrid algorithm with other state-of-the-art algorithms, [–5, 5]^D is used as a search domain. In this experiment, –5 is the lower bound and +5 is the upper bound and random solutions are generated within this range. In the initial stage of this experiment, the size of the Adaption Window is same as the search domain but after some generations it is reduced up to the specified limit. This limit is decided by the Window_size and is calculated by the equation number (1). The size of the population is 25 * Dimension i.e. dimension dependent and it is different for different dimensions and the maximum function evaluation is calculated by the equation number (2). The total function evaluation for each dimension is calculated by the equation number (3). $\begin{matrix} Maximum function evaluation \\ = (200 + Dimension) + 1000 \end{matrix}$ (2) $\begin{matrix} Total function evaluation \\ = Maximum function \\ evaluation * Function evaluation \\ in single iteration \end{matrix}$ (3)

The experiment is conducted on Intel Core i7 3.4 GHz with 64 bit machine under Windows 7 operating system using MATLAB 2013a.

5.1 Benchmark functions and used terminology

The performance of the proposed algorithm is checked over 24 noise free single objective real-parameter benchmark functions [22 –25]. The performance is checked on the basis of getting the optimal solution as per stopping criteria and the valid convergence rate for the optimal solution. The benchmark functions are scalable with dimension and at a time fifteen instances are calculated for each benchmark function. The search region of all functions is defined over the entire places in R^D.

The search domain for global optimum is [–5, 5]^D. Global optimum of most of the functions are also found in [–4, 4]^D which can be a fair setting for initial solutions. Benchmark functions used for the experimental work are shown in Table 1.

Δf precision is required to reach the optimal function value. The term fopt is used for the optimal function value applied to each benchmark function individually. The ftarget is the target function value to reach the optimal value. The smallest specified final target value is ftarget = fopt + 10^-8, but also larger values of ftarget are evaluated. N trials are used in this paper for each function and dimensionality individually for each single setup. D indicates the search space dimensionality used for all functions. D = 2, 3, 5, 10, 20 and 40, where dimensionality 40 is the optional.

5.2 Expected running time

It is the most important performance measure and it is defined as the expected number of function evaluations to reach a target function value for the first time. ERT is computed for a non-zero success rate p_s as follows: $\begin{matrix} ERT (f_{target}) & = & {RT}_{S} + \frac{1 - p_{s}}{p_{s}} {RT}_{US} \\ = & \frac{p_{s} {RT}_{S} + (1 - p_{s}) {RT}_{US}}{p_{s}} \\ = & \frac{# {FE}_{S} (f_{best} \geq f_{target})}{# succ} \end{matrix}$

Where, RT_S denotes the running times and RT_US denote the average number of function evaluations for successful and unsuccessful trials. Zero for none respective trial and ps denotes the fraction of successful trials. Success of trial depends on reaching the f_target. Evaluations that reach after f_target are neglected. The #FEs denotes the number of function evaluations executed in all trials, while the best function value is not smaller than sum of all trials. The #succ denotes the number of successful trials. ERT estimates the expected running time to reach f_target, as a function of f_target. RT_S and ps depend on the f_target value in a particular situation. Sometimes if all trials are not successful, ERT also considers the termination criteria of the algorithm.

6 Result analysis and discussion

Simulation is conducted according to [22] on the noise free benchmark functions [23 –25]. Expected Running Time (ERT) is given in Fig. 2, dependent on the given target function value f_t, where f_t = f_opt + Δf and Δf = 10^-8. The ERT value is calculated over all trails that relevant to each other as the number of function evaluations executed during each trial. The notation #succ is used in tables to represent the number of trails needed to reach the final value of the target f_t.

The rank-sum test is used in the experiment to test the statistical significance of the given target Δf_t. This rank-sum test is applied on each trail for getting the best value of Δf. It is measured only up to the smallest number of overall function evaluations for any unsuccessful trial under consideration if applicable. The line of best 2009 in Fig. 3 is related to the best ERT discovered during BBOB 2009 for every single target. The CPU time calculated as per function evaluation is 1.0, 1.0, 1.1, 1.2, 1.5, 1.7 times 10^–5 seconds for dimensions 2, 3, 5, 10, 20 and 40 respectively. Figure 3 depicts the graphical representation of the overall performance of EAMDGA with other algorithms for all 1–24 benchmark functions and for all dimensions ata glance.

The performance of EAMDGA is compared with eleven state of the art algorithms like HCMA, HPSO, EAMD, GA, HGAPSO, EDA-PSO, CauchyEDA, HGSAA, DE-PSO, CbABC and best 2009 of BBOB. Table 2 shows the dimension wise result of the proposed algorithm on different benchmark functions. It shows the performance of EAMDGA for different group of functions separately i.e. for “separable functions (f1-f4)”, from 2D to 40D the position obtained by EAMDGA are varying. Up to 10D and for 40D the overall performance is satisfactory and in 3D, EAMDGA secures the 2nd position as compared to other algorithms. But, in 20D, it obtains 9th position. In “low or moderate conditioning functions (f5-f9)”, in higher dimensions i.e. 10D-40D the position obtained by EAMDGA is very promising as compared to lower dimensions. For “Unimodal with high conditioning functions (f10-f14)”, it gives satisfactory result in all dimensions and in 40D, it acquires 2nd position. Function range f15-f19 is named as “Multi-modal with adequate global structure” in which the proposed algorithm gives better result in all dimensions and in higher dimension (40D) it again secures the 2nd position. “Multi-modal with weak global structure (f20-f24)”, EAMDGA gives outstanding result against the other algorithms up to 5D. It has obtained 1st position in 5D and it also shows its superiority over best algorithms proposedby BBOB.

Till now all algorithms are compared separately by group of functions and these groups are framed on the basis of their attributes, complexity and unimodal/multimodal nature. When all algorithms are compared together on 24 benchmark functions, it is found that EAMDGA acquires better position in all dimensions. In 5D, it again secures 1st position and defeats other algorithms. It is observed that the proposed algorithm performs well in lower and higher dimensions. It also shows its strength and capability to solve unimodal and multimodal problems.

7 Application of EAMDGA in software cost estimation

During the software development, the objective of any software cost estimation technique is to accurately estimate the cost, time, effort and expertise of working staff needed for the project in early stage of the software development life cycle. Due to the growing challenges, different cost estimation models are proposed over the last several years for accurate estimation of the cost of software development. In this paper, Sheta [26] model has been taken which is a modified version of the very popular Boehm’s COCOMO model [27 –29] for parameter tuning. The parameters of Sheta model has been tuned enough by EAMDGA, to estimate the consequences of different factors that affect the overall software development cost. Simulation is conducted in MATLAB environment and the measurement of the results is tested on the basis of Magnitude of Relative Error (MRE), Prediction (PRED), Value Accounted For (VAF) and Mean Magnitude of Relative Error (MMRE). The dataset presented by Bailey et al. [30] is taken as an input to check the estimation accuracy of the proposed algorithm.

Software cost estimation is the technique of foreseeing the most reasonable and substantial measure of effort essential for the development of any software. The cost prediction of any software is an extremely troublesome assignment because of the association of numerous factors that influence the estimation process. Amid the estimation of software numerous parameters are required to be fine-tuned on the grounds that these are directly responsible for the validity of the cost estimation. Underestimating the software cost might ruin the required estimation. It might influence different things and may bring about lacking of required quality, undeveloped functions and delay in deployment of software. While on account of overestimation, it might reason for the misuse of available funds and may prompt miss the chances to use the accessible funds in making other software. So the exactness regarding inside of time and spending plan is critical in anticipating the software cost to keep up the decency of the software quality.

A few cost estimation strategies are proposed and the prerequisites of software varies that makes the estimation more challenging for the software development team. So the need of exact, substantial and reliable cost estimation is a major challenge in software development. It is highly expected to get the precise estimate of the cost, but there is as no such technique that can accurately predict the software development cost because of uncertainties, and imprecision associated with the software development process. This is a kind of optimization problem and due to this most of the researchers have explored the domain of natural phenomena based optimization techniques such as evolutionary computation, swarm intelligence, differential evolution etc. to form better estimation model. These techniques have tremendous exploration capabilities and power to handle impression which motivated us to improve the performance of existing model. EAMDGA is also a nature based optimization techniques that randomly generatessolutions with higher level of performance accuracy.

In the proposed work EAMDGA is applied to optimize the parameters of the models proposed by Sheta [26] to obtain the accurate estimation of the effort for all types of projects. The experiments are conducted on the data set of 18 software projects, presented by Bailey et al. [30]. In the dataset three things such as Kilo Developed Line of code (KDLOC), Methodology (M) and the Measured Effort are considered for the experiment. Magnitude of Relative Error (MRE) and Mean Magnitude of Relative Error (MMRE) are considered as the fitness function to evaluate the performance of the cost estimation models. EAMDGA is used to obtain the optimal (minimum) value of the parameters a, b, c and d of the models proposed by Sheta for which MRE and MMRE is minimized as compared to existing models. We have also measured, value accounted for (VAF) and prediction at level L (PRED (L)) to check the accuracy of the proposed technique.

7.1 Details of the evaluation techniques

In the proposed work, VAF, MRE, MMRE and PRED (L) [26 , 31–33] are used as measurement techniques for cost estimation models. But MRE and MMRE are considered as the fitness function. Overview of these techniques is as follows:

Value Accounted For (VAF)

It is an evaluation technique used to verify the authenticity of the model. It uses measured and estimated value for checking the performance of the model. The VAF is calculated as follows:

$\begin{matrix} VAF & = & [1 - var (measured effort \\ - estimated effort) / var \\ (measured effort) \times 100] \end{matrix}$ (4)

Variance (var) in Equation 4 is calculated as: $var = \frac{1}{n} \sum_{i - 1}^{n} (x_{i})^{2} - {(\frac{1}{n} \sum_{i - 1}^{n} x_{i})}^{2}$ (5)

In Equation (5), x is a variable and n denotes the total number of values of x.

Relative Error (RE):

Relative error is one of the ratio measurement techniques that give an error rate by measuring the average of prediction errors in every unit of effort. The measurement techniques like MRE, MMRE and PRED is based on the relative error (RE) [33].

$\begin{matrix} RE & = & (measured effort - estimated effort) / \\ measured effort \end{matrix}$ (6)

Magnitude of Relative Error (MRE)

It is calculated by taking the absolute value of the relative error i.e.

$\begin{matrix} {MRE}_{i} & = & abs ((measured {effort}_{i} - estimated \\ {effort}_{i}) / measured {effort}_{i}) \end{matrix}$ (7)

Mean magnitude of relative error (MMRE)

It is the average of MRE over n number of observations. $MMRE = \frac{1}{n} \sum_{i = 1}^{n} {MRE}_{i}$ (8)

Prediction at Some Level (PRED)

It is another measurement technique of ratio measure that evaluates the performance of estimation technique. PRED with the prediction at level L is given below: $PRED (L) = k / n$ (9)

Here, L is the limit for k and k is the value that gives the total number of observations less than or equal to L and n is the total number of observations that has been considered. We can take any value of L but generally 0.25 is considered for the measurement. The quality of the estimation method depends on the minimum value of MMRE and maximum value of PRED.

7.2 Software cost estimation models

Boehm proposed Constructive Cost Model (COCOMO) which is classified based on the type of projects to be handled. They include three types of project classification including organic, semidetached and embedded and every project classification have fixed parameter value [34, 35]. Sheta have used Genetic Algorithm to propose a new estimate of the parameters of the COCOMO model to generalize the computation of the effort required for all projects. He has proposed three software effort estimation models based on Boehm model mentioned below. These models have different set of parameters which is used to determine the usefulness of the results. He has added the effect of methodology in the basic model as given in Equation (10) to improve the prediction capability of the basic COCOMO model as shown in Equation (11). He has further added a bias term in the basic model with methodology as depicted in Equation (12) and realized that it stabilizes the model which helps in reducing the effect of noise in accurate measurement. Proposed Sheta models are given below:

Model 1: This model has two parameters a and b with Developed line of code (DLOC). $EE = a (DLOC) b$ (10)

Model 2: This model takes DLOC, Methodology (M) and three parameters a, b and c. $EE = a (DLOC) b + c (M)$ (11)

Model 3: This model takes one additional parameter d. $EE = a (DLOC) b + c (M) + d$ (12)

Here EE stands for estimated effort. The objective of the proposed work is to find the generalized optimal value of all parameters using EAMDGA and to provide most accuracy in estimation of the effort required for all type of software projects. The experiment has been conducted on the dataset shown in Table 3. This table shows the measured effort and the corresponding line of code and methodology used in 18 software projects. Table 4 mention the terms used in cost estimation as used in [26].

7.3 Software cost estimation by EAMDGA

The working of cost/effort estimation by EAMDGA is divided in three steps which are mentioned below and related proposed working model is shown in Fig. 4:

Step 1: All individuals of population having four parameters (a, b, c and d) are initialized randomly within the specified search limit, shown in Table 10. A population will be created randomly of size (PS * D), where D (dimension) which actually shows the number of parameters. PS stands for population size.

Step 2: In the initial generation, parametric values of the first row vector are applied on all 18 software projects. Then EE and MRE are calculated for 1 to 18 software projects respectively with same parametric values. After that MMRE is calculated on all 18 MREs i.e. from MRE1 to MRE18. Store MMRE and the corresponding value of a, b, c and d in temporary memory. This process will be continued rest of the row vectors in the given matrix and the corresponding MMRE and related four parametric values will be calculated and compared with the previous stored values. Finally the optimal value (minimum value) will be stored in the temporary memory.

Step 3: Apply EAMDGA algorithm to optimize the value of four parameters i.e. a, b, c, and d for each row vector. Then apply step 2 to find the optimum value of MMRE and the corresponding value of four parameters. Compare it with the stored values. After comparison, update the value of MMRE and four parameters. This process continues up to the specified number of generations. Finally the optimum value of MMRE and the corresponding four parameters value will be obtained.

The goal of proposed algorithm is to generate the global optimal value of a, b, c and d which minimize the difference between actual software effort (measured effort) and estimated software effort. The procedure used for software cost estimation is as follows.

1: Create initial random population N of the parameters a, b, c and d within the specified search space limit [0 10], [0.3 2], [–0.5 0.5], and [0 20] respectively. Here population is a matrix of size PS * D, where D denotes the number of dimension which is equal to the number of parameters.

2: While (number of generations < MaxGen) do // Repeat the following steps 3 to 10 until the specified number of generations (MaxGen) has reached.

3: For each row vector of parameter values in the matrix do

For i = 1, 2 ... ... ... . PS

// Do the following operations

Calculate EEi // using Equation 7 to

9 according to the project type

Calculate MREi // using Equation 4

end for

4: Calculate MMREi // using Equation 5.

5: Store and replace minimum MMRE and corresponding four values of parameters.

6: Apply adaption operator of EAMDGA algorithm to optimize the value of a, b, c and d.

7: Merge initial population with optimized value of a, b, c and d and sort this population according to their minimum value.

8: Apply selection operator to select N best solution and generate new population.

9: Number of generations ← number of generations + 1.

10: End while

11: Select minimum MMRE and also select the corresponding value of four parameters where the optimum MMRE has obtained.

12: Print the final value of a, b, c, d and MMRE according to step 11.

In the proposed algorithm, estimated efforts are calculated along with measured (actual) efforts for different projects and they are used to calculate the magnitude of relative error (MRE). In every generation, value of four parameters is optimized to minimize the MMRE. Initially population of four parameters is generated and as per model type, each row vector of parameters is applied to calculate the MRE of all 18 projects. Correspondingly the MMRE is calculated and the minimum value of MMRE is stored along with their parameters. In successive generation each row vector is optimized by EAMDGA and the whole process is repeated. After the completion of each generation the current MMRE is compared with the previous generation and it is updated with minimum MMRE along with parameters. This is continued until the last generation is reached. Finally the reduced MMRE and related optimized parameters are stored as a finalresult.

7.4 Result analysis

In the proposed work initial population of four parameters is randomly generated and EAMDGA is applied on these parameters to improve the accuracy of the estimation process. The estimated effort and MRE obtained by the proposed algorithm gives better results than the existing techniques for all three models proposed by Sheta. Estimated effort is very close to the measured effort and MRE is very less as compared to other method for all models. Results received by the proposed work are superior to the other methods. For every model distinct optimal value is obtained for the related parameters. Separate graph is used to show the significance of the proposed work for all project types. When we compare model 2 to model 1, a better estimation has achieved. The same thing is happened in the comparison of model 2 to model 3. The parameters have been tuned enough to provide better estimation than other estimation techniques. All models proposed by Sheta are optimized by the proposed method and the parameters are tuned enough using EAMDGA is as follows:

Model 1: EE = 1.5889 (DLOC) ^0.9889

Model 2: EE = 0.59378 (DLOC) ^1.1911 + 0.11902 (M)

Model 3: EE = 0.4872 (DLOC) ^1.2312 + 0.09885 (M)+ 1.2247

Here EE is the estimated effort, DLOC stands for developed line of code and M is the methodology added in the basic COCOMO model to improve the prediction quality of the model.

The optimized value of parameters by EAMDGA for three models is given in Tables 5–7 respectively. These values are used in calculating the estimated effort.

MMRE and PRED results of three methods are presented in Table 8. The value found by the proposed method is better than other two methods. It also gives the better value of VAF than others which is shown in Table 9.

In Table 10, MMRE and PRED results obtained by the EAMDGA is superior to the Sheta and Sharma et al. techniques. The VAF value estimated by the proposed technique is better to as compared to other methods presented in Table 11.

New measurement of MMRE, PRED and VAF proposed by Sharma et al. [36] is included for model 3. Table 12 present MMRE and PRED which is obtained by all methods during the experimental work and results show the superiority of the proposed method. In all kind of measurements, proposed method gives better results. The value of VAF shown in Table 13 of proposed method shows better result than the other algorithms.

8 Conclusion

In this paper, a novel nature inspired population based hybrid optimization algorithm EAMDGA is proposed that solves unimodal and multimodal problems effectively. The proposed algorithm proves its robustness by avoiding the problem of getting trapped in local optima and premature convergence. The result of this experiment shows that EAMDGA has proved its strength with balanced convergence rate, less number of function evaluations, diversity in solutions and many more. It has dominated the best 2009 in 5D of COCO platform that expresses the significance and superiority of the proposed algorithm. It also shows the better results in other dimensions.

EAMDGA is used to estimate the software cost with an intent to minimize the difference between the estimated (predicted) and measured (actual) effort of different project. For this, parameters a, b, c and d of Alaa F. Sheta software cost estimation models is tuned with EAMDGA to obtain the optimal value of software cost.

To check the closeness between predicted result and actual result, MRE and MMRE are taken as fitness function. From the results it is clear that the value obtained by proposed algorithm is more accurate as compared to other estimated value like Sheta, Sharma et al. and Brajesh et al. The minimum value of MMRE obtained by the proposed method (EAMDGA) is 19.63% which is very less as compared to other proposed techniques. Percentage of prediction (PRED (L)) at L = 25% is 72.78 which is better than the other techniques.

Footnotes

Acknowledgments

The authors of this paper would like to give special gratitude to the developer of COCO platform for providing such a tremendous benchmark setup, different datasets (noise-less and noise-free) of different well established algorithms, outstanding high-quality post processing utilities and automatic text documentation of every work.

References

Tripathi

, et al., Environmental adaption method for dynamic environment, Systems, Man and Cybernetics (SMC), 2014 IEEE International Conference on, IEEE, 2014.

An environmental adaption method with real parameter encoding for dynamic environment,(in press), Journal of Intelligent and Fuzzy Systems (2015) (in press).

Wund

M.A.

, Assessing the impacts of phenotypic plasticity on evolution, Integrative and Comparative Biology 52(1) (2012), 5–15.

Mishra

K.K.

, Tiwari

and Misra

A.K.

, A bio inspired algorithm for solving optimization problems. In Computer and Communication Technology (ICCCT), 2011 2nd International Conference on, IEEE, 2011, pp. 653–659.

Davis

, ed., Handbook of genetic algorithms. Vol. 115. New York: Van Nostrand Reinhold, 1991.

Premalatha

and Natarajan

A.M.

, Hybrid PSO and GA for global maximization, Int J Open Problems Compt Math 2(4) (2009), 597–608.

Kao

Y.-T.

and Zahara

, A hybrid genetic algorithm and particle swarm optimization for multimodal functions, Applied Soft Computing 8(2) (2008), 849–857.

Kaveh

and Malakouti

, Rad, Hybrid genetic algorithm and particle swarm optimization for the force method-based simultaneous analysis and design, Iranian Journal of Science and Technology, Transaction B: Engineering 34(B1) (2010), 15–34.

and Wang

, A hybrid particle swarm optimization with a feasibility-based rule for constrained optimization, Applied Mathematics and Computation 186(2) (2007), 1407–1422.

10.

Sheikhalishahi

, Ebrahimipour

, Shiri

, Zaman

and Jeihoonian

, A hybrid GA–PSO approach for reliability optimization in redundancy allocation problem, The International Journal of Advanced Manufacturing Technology 68(1-4) (2013), 317–338.

11.

Huang

H-.C.

, FPGA-based hybrid GA-PSO algorithm and its application to global path planning for mobile robots, Przeglad Elektrotechniczny 88(7B) (2012), 281–284.

12.

Elhaddad

and Omar

, A new hybrid genetic and simulated annealing algorithm to solve the traveling salesman problem, In Proceedings of the World Congress on Engineering, vol. 1, 2010, pp. 2078–0958.

13.

Loukil

, Mehdi

, Melab

, Talbi

and Bouvry

, A parallel hybrid genetic algorithm-simulated annealing for solving Q3AP on computational grid. In Parallel & Distributed Processing, 2009 IPDPS 2009 IEEE International Symposium on, IEEE, 2009, pp. 1–8.

14.

Nagpure

and Raja

, RBGCA-Bee Genetic Colony Algorithm for Travelling Salesman Problem.

15.

Kumar

, Sharma

V.K.

and Kumari

, A novel hybrid crossover based artificial bee colony algorithm for optimization problem, International Journal of Computer Applications 82(8) (2013), 18–25.

16.

El-Abd

and Kamel

M.S.

, Black-box optimization benchmarking for noiseless function testbed using an EDA and PSO hybrid. Proceedings of the 11th Annual Conference Companion on Genetic and Evolutionary Computation Conference: Late Breaking Papers ACM, 2009.

17.

García-Nieto

, Alba

and Apolloni

, Noiseless functions black-box optimization: Evaluation of a hybrid particle swarm with differential operators. Proceedings of the 11th Annual Conference Companion on Genetic and Evolutionary Computation Conference: Late Breaking Papers ACM, 2009.

18.

Liu

and Bin

, Memetic algorithm with adaptive local search depth for large scale global optimization. 2014 IEEE Congress on Evolutionary Computation (CEC) IEEE, 2014.

19.

Voglis

, Adapt-MEMPSODE: A memetic algorithm with adaptive selection of local searches. Proceedings of the 15th annual Conference Companion on Genetic and Evolutionary computation ACM, 2013.

20.

Nalepa

, Adaptive memetic algorithm for the vehicle routing problem with time windows. Proceedings of the Companion Publication of the 2014 Annual Conference on Genetic and Evolutionary Computation ACM, 2014.

21.

http://coco.gforge.inria.fr/

22.

Hansen

, Auger

, Finck

and Ros

, Real-parameter black-box optimization benchmarking 2012: Experimental setup. Technical report, INRIA, 2012.

23.

Hansen

, et al. Real-parameter black-box optimization benchmarking 2009: Noiseless functions definitions. Technical Report RR-INRIA, 2009. Updated February, 2010.

24.

Finck

, Hansen

, Ros

and Auger

, Real-parameter black-box optimization benchmarking: Presentation of the noiseless functions. Technical Report 2009/20, Research Center PPE, 2009. Updated February.

25.

Finck

, Hansen

, Ros

and Auger

, Real-parameter black-box optimization benchmarking 2010: Presentation of the noisy functions. Technical Report 2009/21, Research Center PPE 2010.

26.

Sheta

A.F.

, Estimation of the COCOMO model parameters using genetic algorithms for NASA software projects, Journal of Computer Science 2(2) (2006), 118.

27.

Tadayon

, Neural network approach for software cost estimation. Information Technology: Coding and Computing, 2005 ITCC 2005 International Conference on, Vol. 2. IEEE, 2005.

28.

Kumar

, Ananda Krishna

and Satsangi

P.S.

, Fuzzy systems and neural networks in software engineering project management, Applied Intelligence 4(1) (1994), 31–52.

29.

Alaa

F.S.

and Al-Afeef

, A GP effort estimation model utilizing line of code and methodology for NASA software projects, Intelligent Systems Design and Applications (ISDA), 2010 10th International Conference on IEEE, 2010.

30.

Bailey

J.W.

and Basili

V.R.

, A meta-model for software development resource expenditures, Proceedings of the 5th International Conference on Software Engineering IEEE Press, 1981.

31.

Y.-F.

, Xie

and Goh

T.N.

, A study of project selection and feature weighting for analogy based software cost estimation, Journal of Systems and Software 82(2) (2009), 241–252.

32.

Foss

, et al., A simulation study of the model evaluation criterion MMRE, Software Engineering, IEEE Transactions on 29(11) (2003), 985–995.

33.

Singh

B.K.

, et al., Effect of Variations in Measurement Process for Software Development Efforts. Multimedia, Computer Graphics and Broadcasting (MulGraB), 2014 6th International Conference on, IEEE, 2014.

34.

, http://en.wikipedia.org/wiki/COCOMO

35.

Kemerer

C.F.

, An empirical validation of software cost estimation models, Communications of the ACM 30(5) (1987), 416–429.

36.

Sharma

, Sinhal

and Verma

, Software assessment parameter optimization using genetic algorithm, International Journal of Computer Applications 72(7) (2013), 8–13.