Many-objective artificial bee colony algorithm for large-scale software module clustering problem

Abstract

The meta-heuristic search algorithms have been widely applied to solve the various science and engineering optimization problems. However, the performance of these algorithms is highly sensitive toward the number of objective functions and number of decision variables. Recently, it has been explored by the researchers that the performance of such algorithm degrades when the number of objective functions and decision variables increases by some limit. Hence, these algorithms can be hardly acceptable to the real-world optimization problems such as software module clustering problem (SMCP), which contains a large number of objective functions and decision variables. Previous researchers have proposed several approaches to address the many-objective optimization problems by revising existing meta-heuristic algorithms. Recently, an artificial bee colony algorithm (ABC), a meta-heuristic algorithm, effectively used to address the several multi-objective optimization problems. Even though in most of the cases ABC algorithm performs better compared to other meta-heuristic algorithms, it faces the same problems as other meta-heuristic algorithms for a large number of objective functions and decision variables. This paper proposes a many-objective artificial bee colony (MaABC) algorithm to solve many-objective SMCPs. In this contribution, we revised the original ABC by using, quality indicator, $L_{p}$-norm-based (p < 1) distances, and two external archives concepts. To validate the proposed approach, an extensive comparative study is performed with the existing many-objective optimization algorithms (i.e., Two-Arch2, NSGA-III, MOEA/D, and IBEA) over seven SMCPs. The statistical analysis of the results show that the proposed MaABC outperforms existing many-objective approaches in terms of modularization quality (MQ), cohesion, coupling, and inverted generational distance (IGD).

1 Introduction

The optimization problem containing more than three objective functions is usually regarded as many-objective optimization problem (MaOP) (Khare et al. 2003; Praditwong and Yao 2007). The MaOP is a special category of multi-objective optimization problem (MuOP). To solve the low-dimensional science and engineering MuOPs, various multi-objective evolutionary algorithms (MOEAs) (e.g., PESA-II (Corne et al. 2001), SPEA2 (Zitzler et al. 2002), and NSGA-II (Deb et al. 2002)) have been used successfully.

Traditional MOEAs based on the Pareto-dominance selection principles face great trouble when dealing with MuOPs with high-dimensional decision variables and many-objective functions (Wang et al. 2015). The empirical studies (Khare et al. 2003; Praditwong and Yao 2007) have also demonstrated that the effectiveness of MOEAs based on the Pareto-dominance selection principles degrades over large-scale optimization problems. The first reason of such performance degradation is that as the number of objective functions increases, the number of non-dominated solutions increases dramatically in the population that deteriorate the required selection pressure for the candidate solution to move in the next generation (Wang et al. 2015; Hughes 2008). The second reason is that the large number of objective functions felicitates the sparse distribution of candidate solution in the high-dimension objective space which hurdle diversity management.

To improve the performance of MOEAs in case of MaOPs, researchers have proposed several alternatives of traditional Pareto-dominance selection, such as L-optimality (Zou et al. 2008), $\upvarepsilon$-dominance (Laumanns et al. 2002; Hadka and Reed 2013), fuzzy dominance (Wang and Jiang 2007), $\uptheta$-dominance (Yuan et al. 2015), and preference order ranking (Pierro et al. 2007). We are not providing details about many other approaches regarding the many-objective optimization. The works (Bingdong et al. 2015) provided the detailed investigation about the various classes of many-objective optimization approaches that have been used to solve the many-objective optimization problems. In brief, the works (Bingdong et al. 2015) have categorized the many-objective optimization approaches in following major group: objective reduction (e.g., Cinneide et al. 2012), an indicator based (e.g., Zitzler and Künzli 2004), preference or reference set (e.g., Deb and Jain 2014), decompositions (e.g., Zhang and Li 2007). The main limitations of these are as follows: (1) The dimensionality reduction may fail in lessening the objective functions or yielding a solution set that does not contain the whole Pareto front (Bingdong et al. 2015), (2) in indicator-based approach, the hyper-volume calculation increases exponentially by the increase in the number of objectives (Cai et al. 2014), (3) in the preference-based approach, the overhead of decision making associated with the preference elicitation is one of the main drawbacks (Asafuddoula et al. 2015), (4) the main difficulty in the decomposition-based approach is to define proper weight vector (Cai et al. 2014).

In summary, there has been much advancement carried out to enhance the performance of MOEAs for MaOPs. However, these enhancements have not been widely explored to address the real-world, many-objective optimization problems (e.g., many-objective SMCPs (MaSMCPs)). The search-based software engineering (SBSE) exploited various meta-heuristic search algorithms to address the real-world software engineering problems (Harman and Jones 2001). Recently, the software module clustering problem (SMCP) has been regarded as an important search-based software engineering problem where meta-heuristic search algorithms were found more effective against deterministic approaches (Praditwong et al. 2011; Parashar and Chhabra 2016). The SMCP is natural many-objective optimization problem where many conflicting objective functions require to be optimized. Most of the previous work (Praditwong et al. 2011; Kumari et al. 2013; Kumari and Srinivas 2016) addresses the SMCP as multi-objective optimization problem using multi-objective optimization approaches (e.g., NSGA-II). The work (Mkaouer et al. 2015) first formulated the SMCP as many-objective software remodularization problems and solved using NSGA-III (Deb and Jain 2014) a genetic-based many-objective evolutionary algorithm. Even though NSGA-III has been used successfully to solve the MaSMCP, the applicability of other widely used meta-heuristic algorithms (e.g., artificial bee colony algorithm (Karaboga 2005)) has not been explored.

To solve the MaSMCP, we exploited various positive concepts, e.g., quality indicator (Zitzler and Künzli 2004), $L_{p}$-norm-based ($p < 1$) distances (Wang et al. 2015), and two external archives (Wang et al. 2015) from the existing meta-heuristic approaches and proposed a new approach, namely many-objective artificial bee colony (MaABC) algorithm. The researchers (Plevris and Papadrakakis 2011; Li and Yin 2012) have also reported that a good combination of two or more concepts into search algorithm may be advantageous, and they can perform considerably better than the single pure search algorithm in handling large-scale real-world optimization problems. The major contributions of the proposed work are as follows:

• The SMCP is transformed as search-based many-objective optimization problem, namely many-objective SMCP (MaSMCP). Two MaSMCP formulations, extended maximizing cluster approach (E-MCA) and extended equal-size cluster approach (E-ECA) based on multi-objective software module clustering formulations (Praditwong et al. 2011), have been designed.

• To address the MaSMCP, a new many-objective meta-heuristic algorithm, namely many-objective artificial bee colony (MaABC) algorithm, has been proposed. The MaABC is designed by incorporating the various positive concepts (e.g., quality indicator, $L_{p}$-norm-based (p < 1) distances, and two external archives from the existing meta-heuristic approaches into the original ABC algorithm).

• To confirm the supremacy of the proposed MaABC approach, an extensive comparative study has been conducted and the obtained results are compared with the relevant existing many-objective optimization algorithms (i.e., Two-Arch2 (Wang et al. 2015), NSGA-III (Deb and Jain 2014), MOEA/D (Zhang and Li 2007), and IBEA (Zitzler and Künzli 2004) over seven practical software module clustering problems. The statistical analysis of the results indicate that the proposed approach outperforms existing approaches in terms of modularization quality (MQ), cohesion, coupling and IGD.

The rest part of this article is arranged as follows: Section 2 briefly provides some basic concepts and background. Section 3 discusses related work relevant to the proposed approach. Section 4 presents description of proposed MaABC for object-oriented software (OOS) systems. Section 5 gives the experimental setup. Section 6 presents the results and compares with the best performing many-objective algorithms from the existing literature to show the supremacy of the MaABC algorithm. Section 7 discusses the threats to validity. Finally, Sect. 8 gives the concluding remarks and future research directions.

2 Software module clustering

This section provides the basic background and many-objective formulation related to search-based software module clustering problem.

2.1 Software module clustering problem

To ensure the program design quality such as comprehensibility, maintainability, and extendibility, the software developer organizes the highly cohesive source code elements (i.e., modules) into the same group (i.e., cluster) and non-cohesive elements into different groups. The task of organizing software modules into clusters based on some criteria is generally referred as software module clustering problem (SMCP). Formally, the SMCP can be defined as follows: Given a set ${N}={1, 2, . . .,n}$ of software modules which are connected with each other with connection weights w(i, j) where i, j ${\epsilon } N$, the SMCP consists of generating a partition $\hbox {P}=\{\hbox {C} _{1}, \hbox {C} _{2}, . . ., \hbox {C}_{{m}}\}$ of ${n}^{{*}}{m}$ clusters, such that $1 \le {m} \le n$ with $\hbox {C} _{{i}} \ne \Phi , \hbox {C} _{{i}} \cap \hbox {C} _{{j}}=\Phi , {i} \ne {j}$, and $\cup _{i=1}^{m} C_{i} =N$ so as to optimize some design criteria. In SMCP, the choice of what constitutes a software elements and a cluster depends on the software abstraction level where clustering is performed. This paper considers object-oriented classes of the source code as modules and packages (used as group of classes) as clusters.

2.2 Software module clustering as an optimization problem

The main goal of the SMCP is to find one or more feasible partitions which correspond to extreme values of certain quality properties. Based on the number of quality criteria, SMCPs can be addressed by formulating as mono-objective, multi-objective, and many-objective optimization problem. The brief descriptions of these formulations are given below.

• Mono-objective optimization The formulation of SMCP as a mono-objective optimization problem (MoSMCP) deals with the task of determining a clustering solution that optimizes a single quality criterion as fitness function. From a given cluster design vector c, an optimal clustering solution c$^*$ can be determined as follows:

  $$\begin{aligned} { f (\text{ c }^*) = \min /\max f(\text{ c }) {\vert } \text{ c } \in \quad \varPsi } \end{aligned}$$

  (1)

  The symbol $\varPsi$ denotes the set of all feasible clustering solution. The function f can be a minimization or maximization function.

• Multi-objective Optimization: The formulation of SMCP as a multi-objective optimization problem (MuSMCP) deals with the task of determining a set of trade-off clustering solutions that optimizes more than one and less than or equal to three design criteria as objective functions simultaneously. From a given cluster design vector c, a set of trade-off clustering solutions c$^*$ can be determined as follows:

  

  (2)

  The symbols M and $\hbox {f}_{{i}}$ represent the number of design criteria (i.e., objective functions) and the ${i}{\mathrm{th}}$ design criterion, respectively. The P, Q, $\hbox {c}_i^L$, and $\hbox {c}_i^U$ denote the number of inequality design constraints, number of equality design constraints, lower bound of the decision variable $x_i$, and upper bound of the decision variable $x_i$, respectively.

2.3 Software module clustering as a many-objective optimization problem

The formulation of SMCP as a many-objective optimization problem (MaSMCP) deals with the task of determining a set of trade-off clustering solutions that optimizes more than three design criteria as objective functions simultaneously. From a given cluster design vector c, a set of trade-off clustering solutions c$^*$ can be determined as follows:

$$\begin{aligned} f(c^{*})=\left\{ {{\begin{array}{lll} {\hbox {min} \hbox {f}_{1} \hbox {(c), f}_{2} \hbox {(c), . . . , f}_\mathrm{M}} \hbox {(c)}^{T} &{}\quad {M>3} \\ {\hbox {g}_{{j}} (\hbox {c})\ge 0} &{}\quad {j=1, \ldots , P} \\ {\hbox {h}_{\mathrm{k}} (\hbox {c})=0} &{}\quad {k=1, \ldots , Q} \\ {\hbox {c}_i^L \le c_i \le \hbox {c}_i^U} &{}\quad {i=1, \ldots , n} \\ \end{array} }} \right. \end{aligned}$$

(3)

The symbols M and $\hbox {f}_{{i}}$ represent the number of design criteria (i.e., objective functions) and the ${i}{\mathrm{th}}$ design criterion, respectively. The P, Q, $\hbox {c}_i^L$, and $\hbox {c}_i^U$ denote the number of inequality design constraints, number of equality design constraints, lower bound of the decision variable $x_i$, and upper bound of the decision variable $x_i$, respectively. In the following, we present the two many-objective formulations, namely extended maximizing cluster approach (E-MCA) and extended equal-size cluster approach (E-ECA) for software module clustering problem. These formulations are, respectively, the extended versions of maximizing cluster approach (MCA) and equal-size cluster approach (ECA) proposed in the works (Praditwong et al. 2011).

Extended maximizing cluster approach (E-MCA) The main aim of E-MCA many-objective software module clustering formulation is to achieve good clustering having low coupling and high cohesion, while minimizing the number of isolated clusters, maximizing the number of clusters, minimizing the cluster cyclic dependencies, minimizing average shortest path length between a source and all other reachable clusters. The objective functions defined under the E-MCA approach are:

• Maximizing the sum of intracluster dependencies.

• Minimizing the sum of intercluster dependencies.

• Maximizing the number of clusters.

• Maximizing the modularization quality (MQ).

• Minimizing the number of isolated clusters.

• Minimizing cluster cyclic dependencies.

• Minimizing average shortest path length between a source and all other reachable clusters.

Extended equal-size cluster approach (E-ECA) The main goal of the E-ECA approach is to encourage the generation of clusters of nearly equal size. The objective functions defined in this formulation are:

• Maximizing the sum of intracluster dependencies.

• Minimizing the sum of intercluster dependencies.

• Maximizing the number of clusters.

• Maximizing the modularization quality (MQ).

• Minimizing the difference between maximum and minimum number of modules in a cluster.

• Minimizing cluster cyclic dependencies.

• Minimizing average shortest path length between a source and all other reachable clusters.

Modularization quality (MQ) was first introduced by the works (Mancoridis et al. 1999), later the works (Praditwong et al. 2011) redefined it. In this paper, we use the MQ definition the same as defined in the works (Praditwong et al. 2011).

3 Basic concepts

3.1 Original ABC algorithm

The artificial bee colony (ABC) is a meta-heuristic search technique inspired by the intelligent foraging behavior of honey bees. It was originally designed by Karaboga (Karaboga 2005). Recently ABC gained wide attention and found to be effective and well situated for solving the various types of optimization problems in science and engineering fields (Dahiya et al. 2010; Jadhav and Bamane 2016; Xianneng and Guangfei 2016; Hashim et al. 2016; Amarjeet and Chhabra 2017a). The working procedure of ABC algorithm is mainly divided into three essential parts: food source positions, nectar amount, and different types of honey bees. Each food source position corresponds to the feasible candidate solution of the problem, and the nectar amount corresponds to the food source quality (i.e., fitness of the candidate solution). The honey bees are classified into three categories: employed bees, onlooker bees, and scout bees. Each type of honey bees performs particular operation to generate new candidate solutions (food source positions). The brief description of the original ABC algorithm is as follows:

• Population initialization phase The population of ABC algorithm contains a certain number of food sources (i.e., Np), and initially these food sources are produced randomly according to the problem’s search space. For a continuous optimization problem following equation is used to initialize the food source.

  $$\begin{aligned} v_{id} =v_{id}^{\min } +r\times (v_{id}^{\max } -v_{id}^{\min } ) \end{aligned}$$

  (4)

  where i represents food source number in the population with the range of $i=1, 2, \ldots Np$, d represents the dimension (i.e., decision variable) of each food source having range of $d=1, 2, \ldots D$, r represents a uniform random number distributed over the interval [0, 1], and $v_{id}^{\max }$ and $v_{id}^{\min }$ represent the upper and lower bounds for the decision variable d, respectively. After the population initialization, each food source is associated a “limit” variable with 0 value. If a food source in the population could not be improved after a certain number of trials (i.e., limit) then that food source is abandoned.

• Employed bee phase In the employed bee phase, the ${i}{\mathrm{th}}$ food source $v_{i }$ of the population is assigned to the ${i}{\mathrm{th}}$ employed bee, which perform search operation randomly around the neighbor of current food source, and determines a new food source as follows.

  $$\begin{aligned} v_{\hbox {new},d} =v_{id} +r\times (v_{id} -v_{kd} ) \end{aligned}$$

  (5)

  where $i\in \{1, . . . ,Np\},$ and selection strategy of index k is random with the condition $k\in \{1, . . . ,Np\} \wedge k\ne i$. The $v_{\text {new} }$ represents a new food source which is randomly chosen from the neighbor. After generating new solution $v_{\text {new}}$ its fitness is calculated and compared to the original food source $v_i$; thereafter, the solution with the highest fitness value is selected.

• Onlooker bee phase The onlooker bees make a decision on food sources whether to select or not of the food source selected by the employed bees. To perform this, the onlooker bees use the probability values, calculated using Eq. (6), to select the food source for determining promising regions in the search space.

  $$\begin{aligned} p_i =\frac{fit_i }{\sum _{i=n}^{SN} {fit_i } } \end{aligned}$$

  (6)

  where $fit_i$ is the fitness value of the ${i}{\mathrm{th}}$ food source.

• Scout bee phase If a food source in employed and onlooker bee phase cannot be further improved through a fixed iteration, then that food source is supposed to be discarded. The scout bee performs a random search operation over the whole feasible search space and generates a new food source, and the abandoned food source is replaced with it.

3.2 Indicator-based ranking

The Pareto-dominance-based MOEAs face challenges in converging toward the true Pareto front in many-objective optimization problems. In order to solve this problem, the ranking strategy of MOEAs was redefined in different ways (e.g., $\uptheta$ dominance (Yuan et al. 2015), grid dominance (Yang et al. 2013), preference order ranking (Pierro et al. 2007)). These improved approaches have successfully used to optimize large-scale many-objective optimization problems. Min–max strategy (Coello 1996; Coello and Christiansen 1998) is also an alternate which can be used for the ranking of non-dominated solutions. In this paper, to rank the non-dominated solution we use the concept of quality indicator $I_{\varepsilon +}$ given in IBEA (Zitzler and Künzli 2004). The $I_{\varepsilon + }$ is used to calculate the minimum distance that one solution requires, in order to dominate another solution in the objective space. The value of I $_{\varepsilon + }$ between two solutions c$_{1}$ and c$_{2}$ can be computed as follows:

$$\begin{aligned}&f(c_i )=\sum _{c_j \in P\backslash \{c_i \}} {-e^{-I_{\varepsilon +} (c_j , c_i )/0.05}} \end{aligned}$$

(7)

$$\begin{aligned}&I_{\varepsilon +} (c_1 ,c_2 )=\min _\varepsilon (f_i (c_1 )-\varepsilon \le f_i (c_2 )) 1\le i\le m \end{aligned}$$

(8)

where $f(c_{\mathrm{i}})$ is the fitness of a candidate solution c$_{{i }}$ of population P, and m is the number of objective functions. This method of fitness assignment improves the efficiency and effectiveness of the candidate solution selection process from the current population for the next generation.

Fig. 1

Framework of proposed MaABC algorithm

3.3 L$_{p}$-norm-based ($p < 1$) distance

The choice of distance metric in high-dimensional applications is not clear; the notion for the similarity calculation is very heuristic (Aggarwal and Hinneburg 2001). Many applications with high-dimensional algorithms and indexing structures use the Euclidean distance metric. The study (Aggarwal and Hinneburg 2001) demonstrated that the efficiency and effectiveness of Euclidean distance ($L_{2}$-norm) degrades as the number of dimensions increases. However, the fractional distances ($L_{\mathrm{k}}$-norm, $k < 1$) and Manhattan distance ($L_{1}$-norm) perform better in a high-dimensional space. The concluding remark of the study (Aggarwal and Hinneburg 2001) also showed that the fractional distances ($L_{k}$-norm, $k~<~1$) are more effective compared to Manhattan distance ($L_{1}$-norm) in a high-dimensional space. The $L_{\mathrm{k}}$-norm is defined as follows:

$$\begin{aligned} L_k (x,y)=\sum _{i=1}^d {(||x^{i}-y^{i}||^{k})} ^{1/k}| x,y\in R^{d}, k\in Z \end{aligned}$$

(9)

For MaSMCPs with many numbers of objective functions, an Lk-norm-based ($k < 1$) distance measure with a constant k may not suit all the cases. Hence, the value of k in this paper is set as k = 1 / m(m is the number of objectives) similar to the work (Wang et al. 2015).

4 Many-objective artificial bee colony (MaABC)

ABC algorithm has demonstrated several advantages: very few control parameters, relatively easy implementation, and good exploration and exploitation capability. Previous works (Karaboga and Basturk 2007, 2008; Karaboga and Akay 2009; Akay and Karaboga 2012) demonstrated that ABC has better performance than that of an ant colony algorithm (ACO), particle swarm optimization (PSO), differential evolutionary (DE), and genetic algorithm (GA) in solving large and complex optimization problems. The applicability and usefulness of the ABC algorithm has not been studied by any researcher till date to solve the software multi-objective SMCPs (more specifically many-objective SMCPs (MaSMCPs)).

Based on the optimization concept of ABC and full consideration software module clustering feature, this paper proposes a many-objective artificial bee colony (MaABC) algorithm to solve the MaSMCP. Unlike Pareto-dominance-based multi-objective ABC, the proposed MaABC approach is designed by evaluating the solution on the basis of quality indicator (Zitzler and Künzli 2004) and Lp-norm (p<1) distances (Wang et al. 2015). Additionally, the approach used two external archives, namely convergence archive (CA) and divergence archive (DA). The overall process of MaABC is presented in Fig. 1. Similar to the other meta-heuristic search optimization algorithms our proposed MaABC is an iterative process. It begins with an initial population of randomly generated food source position (i.e., module clustering solutions), and then the following steps are repeated until a stopping criterion is satisfied: (1) update the external archives CA and DA, (2) send the employed bees to search the new food source around the neighbor of food source which is already present in her memory, (3) send onlooker bees on food sources based on food source nectar amounts (i.e., fitness values) advertised by employed bees, (4) place scout bees randomly in the search area for finding the new food sources, and (5) store the best food sources found so far into the external two archives, (6) repeat the step 2 to 5 until the termination criterion is satisfied.

Fig. 2

Representation of a software module clustering solution

Table 1 Basic symbols and their meaning corresponding to ABC algorithm

4.1 Problem representation

To solve any optimization problems using a search-based meta-heuristic algorithm, the problem must be defined and encoded corresponding to the different operators of the algorithms so that problem can be tackled easily and effectively. The MaSMCP is a discrete many-objective combinatorial optimization problem. The original ABC algorithm was designed to address the continuous optimization problem. To increase its applicability to the discrete combinatorial optimization problems, researchers always converted the continuous domain into the discrete domain. And this overhead causes difficulties to the ABC algorithm.

In this paper, the particular solution of MaSMCP problem is encoded as a vector of n decision variables where the index of the vector and value at that index correspond to the modules and clusters, respectively. Let us consider a particular module clustering solution c$_{i}$ which is denoted with a vector $\hbox {c}_{{i}}$ and decision variables d: $\mathop {C_i }\limits ^\rightarrow =(c_i^1 ,c_i^2 , . . . , c_i^{|D|} )$. In this solution representation, each element $c_i^d$ of vector $\hbox {c}_{{i}}$ refers to a particular dimension of decision variable of the considered problem. To demonstrate it, let us consider a hypothetical software system depicted in Fig. 2.

In Fig 2, the module clustering solution for a hypothetical SMCP contains eight modules distributed in three clusters C$_{1}$, C$_{2}$ and C$_{3}$. Hence, according to our encoding method, it is represented as a vector c $=$ [1, 1, 2, 2, 2, 3, 3, 3], where vector index from 1 to 8 represents the modules and values 1 to 3 correspond to the clusters in which that modules exist. For example modules 1 and 2 are grouped in the same cluster C$_{1}$; hence the value of the vector indexed with 1 and 2 is 1. Similarly, modules 3, 4, and 5 are in cluster C$_{2 }$ and modules 6, 7, and 8 are in cluster C$_{3}$. The basic symbols and their meaning corresponding to ABC algorithm and MaSMCP are given in Table 1.

4.2 Population initialization

In MaABC each population member (i.e., food source/candidate solution) is initialized randomly using the formula $c_i^d =\text {RandInt}(UB_{^{i}}^d -LB_i^d )$. The notations $UB_{^{i}}^d$ and $LB_i^d$ correspond to the upper and lower bound on the d th decision variable for the i th member of the population; RandInt () denotes a random function that selects a random integer value between $LB_i^d$ and $UB_{^{i}}^d$. The main steps of the population initialization are given in Algorithm 1.

4.3 Send employed bees

In this phase, each employed bees fly toward the current module clustering solution (food source) that she has in her memory and exploit a new food source around the vicinity of the current solution. To force the employed bees toward a better neighboring solution the employee bees are guided by current population and two archives (CA and DA). To this contribution, the value of each decision variables for a new solution is determined as follows:

$$\begin{aligned} v_i^d =\left\{ {{\begin{array}{ll} {\text {RandInt}(c_1^d ,c_2^d ,\ldots ,c_{|N_p |}^d )} &{}\quad {if r\ge 0.5} \\ {\text {RandInt}(c_1^d ,c_2^d , \ldots ,c_{|CA+DA|}^d )} &{}\quad {if r<0.5} \\ \end{array} }} \right. \end{aligned}$$

(10)

The RandInt function generates a value by the randomly selected dimension from the population and archives (CA + DA) with 0.5 probabilities each. The step-by-step process of the employed bees is given in Algorithm 2.

4.4 Send onlooker bees

In this step of the algorithm, each onlooker bees make the selection decision for module clustering solution advertized by the employed bees on the basis of fitness value (nectar amount). The onlooker bee selects a solution based on the probability which is calculated as follows:

$$\begin{aligned} p_i =\frac{fit (c_i )}{\sum _{m=1}^{\text {Food}\,{\text {Number}}} {fit (c_m )} } \end{aligned}$$

(11)

where ${p}_{{i}}$ is the selection probability of the module clustering solution $\hbox {c}_{{i}}$. The $fit(c_{i})$ is the fitness of the module clustering solution $\hbox {c}_{{i}}$ advertized by the each employed bee i. The detailed steps are given in Algorithm 3.

4.5 Send scout bees

In this phase, if the food source corresponding to the module clustering solution does not improve in certain iteration, then it is abandoned from the population. The employed bees related to the abandoned food source turn into a scout bee, and the corresponding food source is changed with a module clustering solution that is generated in the same manner as that in the population initialization phase. The detailed steps are given in Algorithm 4.

4.6 Update CA and DA archives

To guide the employed and onlooker bees in a good direction, the MaABC algorithm uses the two external archives concepts inspired by the work presented in Wang et al. (2015). The two archives are used to store best module clustering solutions found in each generation. These archives are named as CA (convergence archive) and DA (diversity archive) with equal fixed size. Both CA and DA archives are updated according to Algorithm 5.

4.7 Selection in overflowed CA and DA

If the number of solutions in the CA and DA increases in the size of CA and DA, then the algorithm activates the selection method to remove the module clustering solution corresponding to the food sources from both CA and DA archives. To select the module clustering solution from the CA archive, we use the concept of quality indicator $I_{\varepsilon +}$ given in IBEA (Zitzler and Künzli 2004) discussed in Sect. 3.2 The food source with low rank is selected from the CA and then removed. This selection strategy specially is used to ensure the diversity in the CA archive. Finally, an updated CA with a fixed number of module clustering solutions can be obtained. On the other hand, in case of DA overflow, we select and delete the module clustering solution of DA that has a minimum Lp-norm (p < 1) (i.e., discussed in Sect. 3.3) distance from the module clustering solutions of the CA archives.

4.8 Termination

The steps send employed bee, send onlooker bee, send scout bee, and update archive iterate cycle by cycle until the termination condition is met.

By the termination of the MaABC algorithm, the external archive CA and DA are returned as the output. In our implementation, the MaABC terminates after a predefined number of fitness evaluations.

5 Experimental setup

This section provides detailed description about the experimental setup to assess the proposed MaABC algorithm.

5.1 Software systems

In order to evaluate the performance of our proposed MaABC algorithm, we have tested it on seven open-source software systems (i.e., JFreeChart, JHotDraw, JavaCC, JUnit, Java Servlet API, XML API DOM, and DOM 4 J) with different characteristics. These software systems have also been used to evaluate the similar clustering techniques by the previous researchers (Amarjeet and Chhabra 2014; Mkaouer et al. 2015; Amarjeet and Chhabra 2015, 2017b). Table 2 provides a brief summary of the software systems.

Table 2 Characteristics of selected software projects

5.2 Research questions

To evaluate the effectiveness of MaABC, we answer the following research questions.

RQ1. :

Does proposed approach produce clustering solution having a better MQ compared to existing approaches?

RQ2. :

Does proposed approach produce clustering solution having a better coupling compared to existing approaches?

RQ3. :

Does proposed approach produce clustering solution having a better cohesion compared to existing approaches?

RQ4. :

Does proposed approach produce clustering solution having a better IGD compared to existing approaches?

To answer these research questions, we cluster the seven software systems using the proposed MaABC and existing many-objective meta-heuristic search algorithms.

Table 3 Algorithms and their parameter values

5.3 Existing algorithms and parameter settings

In order to verify the performance of the proposed many-objective algorithm, the four state-of-the-art many-objective meta-heuristic search algorithms (i.e., Two-Arch2 (Wang et al. 2015), NSGA-III (Deb and Jain 2014), MOEA/D (Zhang and Li 2007), and IBEA (Zitzler and Künzli 2004)) are considered. These algorithms are implemented in jMetal, a multi-objective meta-heuristic framework, on a 16-core 2.60 GHz Intel Xeon CPU with 8 GB RAM. The parameter settings of each algorithm (i.e., proposed and state-of-the-art algorithms) are given in Table 3. To have a fair comparison of considered algorithms, each of the algorithms is given equal number of number of fitness evaluations ($N_{\hbox {FE}})$ (Črepinšek et al. 2014).

5.4 Collecting results and statistical tests

The many-objective meta-heuristic search algorithms are stochastic optimizer, i.e., they can generate different results on each run over the same problem. In this experiment, the results are collected from the experiment by executing each of the meta-heuristics on each problem instance by 31 independent simulation runs.

6 Results and analysis

In order to evaluate the behavior of our proposed algorithm, we compare MaABC with Two_Arch2, NSGA-III, MOEA/D, and IBEA on 7 many-objective software module clustering problems with 7 numbers of objective functions. The compared meta-heuristic algorithms are all representatives of multi-objective evolutionary algorithms for many-objective optimization problems. The results of MaABC, Two_Arch2, NSGA-III, MOEA/D, and IBEA on the each problem are shown in Tables 4, 5, 6, 7, 8, 9, 10, 11, where the algorithms are statistically analyzed by using Wilcoxon’s rank sum test with 95% confidence level ($\alpha$ = 0.05) (Arcuri and Fraser 2013). Sections 6.1, 6.2, 6.3, and  6.4 present comparison among MaABC, Two_Arch2, NSGA-III, MOEA/D, and IBEA algorithms regarding MQ, coupling, cohesion, and IGD, respectively.

Table 4 Median MQ values obtained from algorithms with E-MCA formulation

Table 5 Median MQ values obtained from algorithms with E-ECA formulation

Table 6 Median coupling values obtained from algorithms with E-MCA formulation

Table 7 Median coupling values obtained from algorithms with E-ECA formulation

Table 8 Cohesion values obtained from algorithms with E-MCA formulation

Table 9 Cohesion values obtained from algorithms with E-ECA formulation

Table 10 IGD values obtained from algorithms with E-MCA formulation

Table 11 IGD values obtained from algorithms with E-ECA formulation

6.1 The MQ value as assessment criterion

In this section, the proposed software module clustering approach, MaABC, was compared with Two_Arch2, NSGA-III, MOEA/D, and IBEA in terms of MQ values. Table 4 presents metric MQ in terms of median and standard deviation obtained from different meta-heuristic algorithms with E-MCA formulation on the seven problem suite. Similarly, Table  5 presents metric MQ in terms of median and standard deviation obtained from different meta-heuristic algorithms with E-ECA formulation on the seven problem suite.

If we see the results presented in Table 4, it clearly indicates that the MQ values achieved by the MaABC approach are significantly better over the most of the problem instances. Most specifically, if we compare the MQ values of MaABC with MQ values of each individual algorithm, we observed that (1) the comparative results between MaABC and Two_Arch2 algorithms show that the MaABC is able to achieve better Two_Arch2 in six problems out of seven, in which five cases are significantly better. (2) The comparison results between MaABC and NSGA-III show that the MaABC approach performs better in six problems out of seven problems, in which 4 cases are significantly better. (3) The comparative results between MaABC and other two algorithms (i.e., MOEA/D and IBEA) show that the MaABC approach outperforms MOEA/D and IBEA in most of the cases.

The MQ values achieved by each of the algorithm with E-ECA formulation presented in Table 5 show that the proposed MaABC approach outperforms in most of the cases. The MaABC performs better than Two_Arch2 in all cases, in which three cases are significantly better. The MaABC also performs better than NSGA-III in all cases, in which five cases are significantly better. The MOEA/D and IBEA perform significantly worst MaABC in all problem instances. The results also show that the MQ values achieved by MaABC with E-ECA formulation are more effective compared to E-MCA formulation.

Figure 3 presents the results of MQ achieved by each of the considered algorithms with E-MCA and E-ECA formulation over all seven problem instances. From Fig. 3, it is clear that the proposed MaABC is able to generate clustering solution having better MQ values compared to Two_Arch2, NSGA-III, MOEA/D, and IBEA.

Fig. 3

Comparison of MQ values obtained from algorithms with E-EMA and E-ECA

Fig. 4

Comparison of coupling values obtained from algorithms with E-EMA and E-ECA

6.2 Coupling as an assessment criterion

To answer the research question RQ2, the software module clustering generated by proposed approach and rival algorithms has been evaluated in terms of coupling as an assessment criterion. The values of coupling obtained by MaABC and existing many-objective optimization algorithms with E-MCA many-objective software clustering formulation over all seven problems are shown in Table 6. The values of coupling obtained by MaABC and existing many-objective optimization algorithms with E-ECA many-objective software clustering formulation are shown in Table 7. To make the distinction among each algorithm, the coupling results are also demonstrated using bar charts which are demonstrated in Fig. 4.

In cases of E-MCA formulation, the coupling results reported in Table 6 show that the MaABC performs better than Two_Arch2, NSGA-III, MOEA/D, and IBEA approaches in all seven software module clustering problems, in which most of the cases are significantly better in favor of MaABC. Similarly, in case of E-ECA formulation the coupling results demonstrated in Table 7 show that the MaABC also performs better Two_Arch2, NSGA-III, MOEA/D, and IBEA approaches in all seven problem instances in which most of the cases are significantly better in favor of MaABC.

Now if we compare the coupling results between E-MCA and E-ECA formulation, the coupling results demonstrated in Tables 6 and 7 also show that the module clustering solution obtained by MaABC with E-ECA is more effective compared to E-MCA formulation.

Fig. 5

Comparison of cohesion values obtained from algorithms with E-EMA and E-ECA

The achieved coupling results of MaABC, Two_Arch2, NSGA-III, MOEA/D, and IBEA are also demonstrated in Fig. 4. It is clearly observed that the coupling values of MaABC presented in Fig. 4 are better in most of the cases compared to Two_Arch2, NSGA-III, MOEA/D, and IBEA with both E-MCA and E-ECA formulations.

6.3 Cohesion as an assessment criterion

To answer the research question RQ2, this section compares the cohesion of module clustering solutions produced by the proposed MaABC approach and existing many-objective meta-heuristic algorithms (i.e., Two_Arch2, NSGA-III, MOEA/D, and IBEA). To validate the answer of approach, each algorithm was analyzed with two software module clustering many-objective formulations (i.e., E-MCA and E-ECA) over all seven module clustering problems.

Table 8 compares the median and standard deviation results in terms of cohesion between MaABC and each of the existing rival many-objective meta-heuristic algorithms (i.e., Two_Arch2, NSGA-III, MOEA/D, and IBEA) with E-MCA formulation over seven SMCPs. Similarly, Table 9 compares the median and standard deviation results in terms of cohesion between MaABC and each of the existing rival many-objective meta-heuristic algorithms with E-MCA formulation over seven SMCPs.

For all the problem instances, the cohesion values presented in Table 8 clearly indicate that the proposed MaABC is able to achieve better cohesion when compared with each algorithm, in which most of the cases are statistically significant in favor of MaABC. Similarly, the cohesion results of the E-ECA formulation presented in Table 9 also indicate that the MaABC is able to achieve better cohesion values compared to existing algorithms in all cases in which most of the cases are significantly better.

Now if we compare the cohesion results between E-MCA formulation (for all problem instances and for all algorithms) and E-ECA formulation (for all problem instances and for all algorithms), it can be easily observed that the each algorithm on each problem instance the E-ECA formulation is able to generate better cohesion results compared to E-MCA formulation.

Figure 5 presents the results of cohesion achieved by each of the considered algorithms with E-MCA and E-ECA formulation over all seven problem instances. From Fig. 5, it is clear that the proposed MaABC is able to generate clustering solution having better cohesion values compared to Two_Arch2, NSGA-III, MOEA/D, and IBEA.

6.4 IGD as assessment criterion

In the previous sections, we compared MaABC with existing many-objective algorithms (i.e., Two_Arch2, NSGA-III, MOEA/D, and IBEA) in terms of structural quality metrics (i.e., MQ, coupling, and cohesion). In this section, we compare the MaABC with existing algorithms in terms of IGD values for both E-MCA and E-ECA formulations. Tables 10 and 11 show the median IGD values for MaABC and all rival algorithms under comparison. For the E-MCA formulation, Table 10 shows that MaABC outperforms other algorithms, except in the JavaCC problem instance where MaABC performs significantly worse NSGA-III. In existing algorithms, Two_Arch2 performs better than NSGA-II, MOEA/D, and IBEA in most of the cases. Additionally, NSGA-III seems to be better MOEA/D and IBEA. For E-ECA formulation, the IGD values presented in Table 11 indicate that the MaABC performs significantly better existing approaches in most of the cases.

6.5 Results summary

This section discusses the contributions and implications of our proposed MaABC approach in solving the MaSMCPs using proposed MaABC. The main contribution of the MaABC with respect to existing MOEAs is that the MaABC integrates the external archive and indicator-based concepts into the ABC algorithm to achieve a good balance between exploration and exploitation in case of MaSMCPs. The results presented in Sects. 3.1 to 3.4 showed that the MaABC performed better compared to the existing many-objective optimization approaches (i.e., Two_Arch2, NSGA-II, MOEA/D, and IBEA) in terms of MQ, coupling, cohesion, and IGD in most of the cases. Hence, it can be concluded that the proposed approach can be a good alternate for solving the software clustering problems containing many-objective functions compared to other existing approaches.

7 Threats to validity

To clarify the limitations and strengths of our proposed multi-objective software module clustering approach, we explore the factors that could influence the validity of the achieved results. There are two major categories of threats (i.e., external validity and internal validity) that could affect the results of proposed approach.

External validity (or selection validity) corresponds to the degree to which obtained results (samples) of the approach can be generalized to the broad perspective of problems. In search-based software engineering, this is a very important threat to validity of results because of the large number of diverse software projects available to any study of software module clustering. In our experimentation, this threat to validity has been mitigated by the fact that the proposed approach is concerned with module dependency graph (MDG), an abstract representation of software systems. Since there is a many to one relation between the software systems and MDG (i.e., many individual software systems can map into a single MDG), the findings for a set of MDGs of a particular size are relevant to wider MDGs. In order to mitigate the possible external threats to validity, the experimentation uses various size of MDGs, both un-weighted and weighted.

Internal validity corresponds to the degree to which conclusions can be drawn about the causal effect of independent variables on the dependent variables. In this empirical study, possible internal threats come from violations of statistical assumptions or inappropriate statistical tests, inaccurate underlying analysis, and the extent to which the variables used in the experiment precisely measure the concepts they claim to measure. In this empirical study, we use Wilcoxon’s rank sum test. Wilcoxon’s rank sum test is more appropriate when the type of distribution of data is unknown.

8 Related works

To address the SMCPs, large numbers of analytical and search-based approaches have been proposed. The formulation of SMCPs as search-based optimization problem and solving it using search-based meta-heuristic algorithms gained wide attention. Based on the problem formulation, the search-based software module clustering approaches can be categorized into single-objective, multi-objective, and many-objective software module clustering. The subsequent subsections discuss literature background of these approaches.

Table 12 Summary of relevant single- and multi-objective optimization approaches

8.1 Single-objective optimization approaches

In the works by Mancoridis et al. (1998), the authors proposed a single-objective search technique to cluster the software systems. In this contribution, they adapted the genetic algorithm (GA) as search algorithm and designed a modularization quality (MQ) metric to guide the search process. In order to improve the MQ’s effectiveness, the metric was redefined over the years (Mitchell and Mancoridis 2002; Praditwong et al. 2011). Later the authors (Mancoridis et al. 1999) proposed a single-objective optimization tool named as Bunch for software module clustering. The effectiveness of the Bunch was evaluated over medium- and large-size software systems.

Doval et al. (1999) proposed a single-objective optimization technique for finding the good partition of the module dependency graph (MDG). The MDG is a graphical representation of software systems, where nodes represent the software elements and edges represent the dependency between elements. They used GA as search technique and MQ as fitness function. The work (Mitchell and Mancoridis 2002) adapted genetic algorithm, simulated annealing, and hill-climbing algorithms to cluster the software systems.

Harman et al. (2002) introduced an encoding scheme for representation of the software clustering solution which reduces the size of the search space and proposed new crossover method to support the retention and formation of building blocks. They claimed that the new designed crossover method is more effective for genetic algorithms compared to the standard crossover method. Mahdavi et al. (2003) presented a multiple hill-climbing algorithm to cluster the software systems. They evaluated the proposed approach over 19 software projects and found that presented approach has generated good results. The works (Mitchell et al. 2004) illustrated that designing the search landscape for search-based meta-heuristic optimization is a good approach for gaining insight into the search algorithms.

Harman et al. (2005) performed an empirical study for evaluation of robustness of two fitness function (i.e., MQ and EVM). The robustness results of MQ and EVM were compared. The comparison results showed that the both fitness function degrades slowly as the percentage of mutation is applied, but the EVM fitness function emerges to be more robust compared to MQ fitness function. Praditwong (2011) proposed a new grouping genetic algorithm (GGA) to address the single-objective software module clustering problems.

The works (Jinhuang and Jing 2016) introduced a new quality metric, namely modularization similarity (MS), for software clustering problem. The MS is based on the structural similarity and experience and knowledge of software design. The main goal of the MS is to guide the module clustering process toward good-quality clustering solutions. They also compared the clustering results obtained through MS with the results of MQ. The comparison results demonstrated that the MS outperforms the basic MQ. Table 12 provides a brief description of about the single-objective software module clustering approaches.

8.2 Multi-objective optimization approaches

Praditwong et al. (2011) presented two multi-objective formulations, namely equal-size cluster approach (ECA) and maximizing cluster approach (MCA), for software module clustering problems. Each of the MCA and ECA multi-objective formulations consists of five different partial conflicting objective functions. To optimize each MCA and ECA formulation, they used a Two-Archive-based GA (Praditwong and Yao 2006). They evaluated the effectiveness of MCA and ECA formulations over the real-world module clustering problems. Their experimental results claimed that the proposed MCA and ECA-based multi-objective approaches are able to generate significantly better clustering results than the existing single-objective clustering approaches.

Barros (2012) conducted an empirical study to assess the effectiveness and efficiency of two multi-objective formulations while searching clustering solution with multi-objective meta-heuristic algorithms. The works (Kumari et al. 2013) were claimed to be the first for applying the hyper-heuristics multi-objective approach to address the software module clustering problems. They evaluated the supremacy of the proposed work on six software systems with multiple conflicting objective functions. They reported that the hyper-heuristics-based multi-objective approach requires less computational cost in generating better-quality clustering solutions compared to existing approaches.

The works (Amarjeet and Chhabra 2014) presented a multi-objective software module clustering approach aiming to preserve the core components of the existing software modularization while clustering process of software systems. The approach was evaluated on seven software clustering problems with MCA and ECA multi-objective module clustering formulations. Their empirical results claimed that the approach was able to preserve the core components and at the same time it also achieved the desired clustering quality. Amarjeet and Chhabra (2017c) formulated the software module clustering problem as a problem of improving the package structure within the existing clustering. To this contribution, they proposed different objective functions that help in improving the existing package structure of the software systems.

The works (Kumari and Srinivas 2016) presented the hyper-heuristic approach named as multi-objective hyper-heuristic evolutionary algorithm (MHypEA) to solve the multi-objective software module clustering problems. They evaluated the hyper-heuristic approach using MCA and ECA multi-objective formulation given by Praditwong et al. (2011). The clustering results obtained through MHypEA compared with clustering achieved through NSGA-II and Two-Archive algorithm (Praditwong and Yao 2006). The comparison results showed that the MHypEA performs better than the NSGA-II and Two-Archive algorithms. The works (Amarjeet and Chhabra 2017c) presented a multi-objective approach to address the software module clustering problem. They proposed a new objective functions based on the lexical and structural information. The results demonstrated that the combined use of lexical and structural information is able to generate better clustering solution compared to individual structural or lexical information.

Table 13 Summary of relevant many-objective approaches applied in SBSE

8.3 Many-objective optimization approaches

The study (Praditwong et al. 2011) reported that the multi-objective formulation of the software module clustering problem and solving it using multi-objective evolutionary algorithms has been found more effective compared to the single-objective formulation of software module clustering problem. This is mainly due to the balanced exploration and exploitation ability of multi-objective evolutionary algorithms. Despite the success of multi-objective evolutionary algorithms, it does not perform well in problems that belong to the many-objective optimization field (Mkaouer et al. 2015).

In the literature of multi-objective software module clustering, many studies use the multi-objective evolutionary algorithms to solve the software clustering problems (e.g., Praditwong et al. 2011; Barros 2012; Kumari et al. 2013). The main reasons of performance degradation of multi-objective evolutionary algorithms with many-objective optimization are as follows: (1) As the number of objective functions in optimization problem increases by more than three, it faces difficulties in differentiating the solutions of population, (2) the execution time taken by non-dominated sorting process of multi-objective evolutionary algorithms increases, resulting in increase in overall time complexity of algorithm (Hughes 2008).

To address the challenges of the multi-objective evolutionary algorithms, many approaches have been proposed in the literature of multi-objective evolutionary algorithms. Interested researchers/academicians can find more details in the literature survey presented by works (Wang et al. 2015). They classified the many-objective optimization approaches into the following groups: (1) objective reduction approaches (e.g., Cinneide et al. 2012; Gong et al. 2013), (2) preference-based approaches (e.g., Said and Bechikh 2013) , (3) reference set-based approaches (e.g., Deb and Jain 2014), (4) indicator-based approaches (e.g., Zitzler and Künzli 2004; Bader 2011), (5) aggregation-based approaches (e.g., Garza-Fabre et al. 2009), (6) relaxed dominance-based approaches (e.g., GarzaspsFabre et al. 2010), (7) decomposition-based approaches (e.g., Zhang and Li 2007), and (8) external archive-based approaches (e.g., Praditwong and Yao 2006; Wang et al. 2015). Table 13 provides the summary of the many-objective methodologies of the software engineering field.

9 Conclusions and future works

This work investigated the incorporation of indicator-based ranking and two external archive techniques into artificial bee colony algorithm in order to solve the software module clustering problems with many objectives (i.e., more than three objective functions). The proposed ABC-based module clustering approach is named as many-objective artificial bee colony algorithm (MaABC). Two versions of many-objective software module clustering formulations (i.e., extended equal-size cluster approach (E-ECA) and extended maximizing cluster approach (E-MCA)) have been introduced. To verify the performance of proposed MaABC, it has been evaluated on seven software clustering problems obtained from different module dependency graphs (MDGs) of object-oriented software systems. The clustering results obtained from MaABC have also been compared with existing approaches (i.e., Two_Arch2, NSGA-II, MOEA/D, and IBEA) in terms of MQ, coupling, cohesion, and IGD. The achieved clustering results demonstrated that MaABC is able to generate better clustering compared to existing approaches. Future works include a detailed empirical study on different ranking strategies (e.g., $\uptheta$-dominance, grid dominance, preference order ranking) for non-dominated solutions including min–max method to solve the many-objective software remodularization problem.