# Cooperative Coevolution with Two-Stage Decomposition for Large-Scale Global Optimization Problems

Authors: H. D. Yue; Y. Sun
Journal: Discrete Dynamics in Nature and Society
 (2021)

---

## Abstract

Cooperative coevolution (CC) is an effective framework for solving large-scale global optimization (LSGO) problems. However, CC with static decomposition method is ineffective for fully nonseparable problems, and CC with dynamic decomposition method to decompose problems is computationally costly. Therefore, a two-stage decomposition (TSD) method is proposed in this paper to decompose LSGO problems using as few computational resources as possible. In the first stage, to decompose problems using low computational resources, a hybrid-pool differential grouping (HPDG) method is proposed, which contains a hybrid-pool-based detection structure (HPDS) and a unit vector-based perturbation (UVP) strategy. In the second stage, to decompose the fully nonseparable problems, a known information-based dynamic decomposition (KIDD) method is proposed. Analytical methods are used to demonstrate that HPDG has lower decomposition complexity compared to state-of-the-art static decomposition methods. Experiments show that CC with TSD is a competitive algorithm for solving LSGO problems.


---

## Body

## 1. Introduction

Large-scale global optimization (LSGO) problems are widespread optimization problems in scientific research and engineering applications [1–6]. In this paper, continuous LSGO problems with 1000 or greater decision variables are studied and solved.There are two main challenges in solving LSGO problems: (1) dimensional catastrophe [7] and (2) traditional mathematical algorithms and evolutionary algorithms (EAs) with rapid performance degradation as the dimensionality grows [8–10]. There are two main approaches to solve difficulties. The first approach is to design or improve EAs with powerful exploration so that the EAs avoid getting trapped in local optima in large-scale solution space [11]. The second approach is the CC with problem decomposition, which adopts the idea of divide-and-conquer and is divided into two stages [12, 13], problem decomposition and problem optimization. Recently, CC has been used to solve a variety of problems [14–16]. The second approach is the one studied in this paper.Decomposition methods decompose LSGO problems into multiple subproblems. CC with dynamic decomposition method decomposes the problems dynamically during the optimization stage, although dynamic decomposition methods are costly to decompose problems, which decompose fully nonseparable problems into multiple subproblems according to certain criteria [17]. The most typical dynamic decomposition method is random grouping [18], but the random grouping method is unable to make near-optimal decomposition for many variables. Other dynamic decomposition methods such as delta grouping lose effectiveness for partially separable problems with more than one nonseparable subcomponent [19], and CCEA-AVP is computationally expensive and effective only when detecting linear variable correlations without nonlinear interdependency [20].CC with static decomposition method decomposes the problem in the problem decomposition stage, and advanced static decomposition method can accurately decompose problems [21–23]. The key for static decomposition method is to correctly identify the relationships between variables. The differential grouping (DG) method [24] is an effective decomposition method for identifying relationships between variables; however, DG has the drawbacks of being sensitive to threshold and not being able to identify overlapping problems. The variant DG2 of DG effectively alleviates the drawbacks of DG, but DG2 is costly to compute adaptive threshold [25]. Mei et al. proposed a global differential grouping (GDG) to alleviate the sensitivity of DG to threshold by setting a global threshold [26]. Sun et al. proposed a recursive differential grouping (RDG) [27] and RDG’s variants RDG2 [28] and RDG3 [29] to further improve the performance of the DG decomposition problems. The recursive interaction structure in RDG, which significantly improves the variable interaction efficiency and the complexity of the variable interaction structure, is Onlogn, where n denotes the problem dimension. Recently, Yang et al. proposed an efficient recursive differential grouping (ERDG) method to avoid repeated interactions during variable interactions [30]. However, the number of function evaluations (FEs) used to decompose problems increases quickly when the problem dimension rises; and the CC with MRF-based decomposition mechanism [31] proposed by Sun et al. and the three-level recursive differential grouping method [32] proposed by Bin et al. did not improve the ability of CC to solve nonseparable problems.However, the static decomposition method aims to group the decision variables correctly, so CC with static decomposition encounters a dilemma in solving the fully nonseparable problems. To further reduce the decomposition complexity and alleviate the dilemma, the main work of this paper is as follows:(1)
We propose a decomposition method TSD in this paper.(2)
An improved differential grouping method, HPDG, is proposed. HPDG is a static decomposition method with a very low complexity. A new decomposition framework, hybrid-pool-based detection structure (HPDS), is proposed in this paper. The complexity of HPDS isOnlogm, where n and m denote the problem dimension and the number of subproblems, respectively.(3)
A unit vector-based perturbation (UVP) strategy is proposed to improve the decomposition accuracy of HPDG.(4)
A known information-based dynamic decomposition (KIDD) method is proposed to decompose the fully nonseparable problems for alleviating the dilemma of CC with static decomposition in solving LSGO problems.In the remainder of this article, we first introduce the differential grouping, variable interaction structure, and CC framework in Section2. Then we present the CC with TSD in detail in Section 3. Numerical experiments are carried out and comparisons with the state-of-the-art algorithms are made in Section 4. Section 5 concludes the work of this paper and plans the next work.


## 2. Related Work

### 2.1. Cooperative Coevolution with Decomposition Method

Cooperative coevolution plays an important role in the development of populations, especially for large size populations. In evolutionary computation, the effectiveness of CC is very dependent on the efficient dividing of population, which in the LSGO problems is problem decomposition [24, 33–35].The steps for CC to solve LSGO problems are described in Algorithm1 [36]. subgroupj holds the indexes of the decision variables of the jth subgroup. In traditional CC framework, computational resources are equally distributed, and line 5 is not executed. First, the population is initialized and static decomposition method decomposes LSGO problems (lines 1-2). Then each subgroup is optimized separately and the population is updated. To improve the utilization of computational resources, contribution-based CC (CBCC) is proposed as described in line 5 [34, 37]. After optimizing each subgroup once separately, the subgroup with the largest contribution value is selected to optimize to the termination condition. To balance the exploitation and exploration, the subgroup with the largest contribution is selected by CBCC3 [38], which is evolved to the condition where the subgroup with the second largest contribution from the last optimization is larger than the subgroup with the largest current contribution.Algorithm 1: CC_with_decomposition (FuncID, D).
(1)
initialize (population);(2)
subgroups⟵group (FunID, D);(3)
forcycles≤Maximumdo(4)
Optimize each subgroup separately;(5)
Select a subgroup with heaviest contribution and optimize to termination;(6)
end for(7)
returnfitness;


### 2.2. Decomposition Method

#### 2.2.1. Problem Decomposition Framework

Problem decomposition framework is the logical structure of problem decomposition adopted by decomposition methods, and the logical structure determines the computational complexity of decomposition methods. Problem decomposition framework can be categorized into two types: double-pool decomposition framework and single-pool decomposition framework [39]. The double-pool decomposition framework includes a detection pool and an update pool, the identification between variables is performed in detection pool, and the identified variables are stored in the update pool, as shown in Figure 1(a). The variable interaction structure of the decomposition methods based on differential grouping belongs to the double-pool decomposition framework [24, 27–29]. In the single-pool decomposition framework, the two pools are integrated into a single one, as shown in Figure 1(b), and the interactions of decision variables can be identified one by one. Experiments [39] show that single-pool decomposition framework is more conducive to identification of the variables than double-pool decomposition framework. In this paper, we combine the advantages of these two decomposition frameworks and propose a hybrid-pool decomposition framework.Figure 1
Decomposition framework. (a) Double-pool procedure. (b) Single-pool procedure.
(a)(b)


#### 2.2.2. Differential Grouping and Its Improvement

For differential functions, there are three relationships between decision variables: no relationship, direct relationship, and indirect relationship [24]. Based on these three relationships, three types of LSGO problems are constituted: full separable problem, partially separable problem, and full nonseparable problem, and the overlapping problem is a special type of partially separable problem. The primary task of problem decomposition is to identify the relationships between decision variables. For LSGO problem fX, the decision vector X of fX is divided into m1≤m≤D mutually exclusive subsets, as shown in equation (1), with Xi∩​Xj=∅ for any Xi,Xj∈X.(1)X1=x1,x2,…,xp,X2=xp+1,xp+2,…,xq,…,Xm=xk,xk+1,…,xD.DG decomposes problems by identifying the relationships between each pair of variables. Let the two variables identified bexi and xj, if the partial derivative is(2)∂2fX∂xi∂xj=0or≤ε.In the above equation,ε is a very small positive real number parameter of DG used for determining whether two variables are related. Then xi is unrelated to xj; otherwise xi is related to xj. If the relationship between two variables is indirect, it is difficult for the DG to identify this relationship, as in the problem described by the following equation:(3)fX=x1+x2+x32+x2+x42,where x3 and x4 are related through x2 interacting with each other and DG cannot find the relationship between x3 and x4 because(4)∂2fX∂x3∂x4=0.Problem decomposition by identifying the relationship between each pair of variables is inefficient. RDG significantly reduces the FEs by using a recursive detection structure in unidentified variables to complete problem decomposition. The theory of the identification for two sets of variables proved by Sun et al. is as follows [27]:(5)fx∗+l1u1+l2u2−fx∗+l2u2≠fx∗+l1u1−fx∗.LetX1,X2 be subsets of the decision vector X of fX, let u1 and u2 be unit vectors of X1 and X2, respectively, and x∗ is a feasible solution, where X1≠∅,X2≠∅, X1∩​X2=∅, and l1,l2>0. If some variables of X1 and X2 are related, inequality (7) holds. Conversely, X1 and X2 are not related to each other [27].Based on RDG, ERDG uses interaction history information to complete problem decomposition and further reduces the FEs [27, 30]. However, RDG and ERDG apply perturbations to the variables by giving the same upper and lower bounds to the variables to be identified, so that the perturbation to identify all problems is fixed. The two changes of the fitness value are(6)Δ1=fX1,ub−fX1,lb,(7)Δ2=fX2u,mb−fX2l,mb,where X1,ub and X1,lb are candidate solutions that are given upper bounds and lower bounds, respectively, and mb denotes the mean of the upper bounds ub and lower bounds lb. The variables belonging to X2u,mb and X2l,mb are assigned the same upper bounds and lower bounds as X1, respectively, and the variables that do not belong to X1 are assigned mb.


## 2.1. Cooperative Coevolution with Decomposition Method

Cooperative coevolution plays an important role in the development of populations, especially for large size populations. In evolutionary computation, the effectiveness of CC is very dependent on the efficient dividing of population, which in the LSGO problems is problem decomposition [24, 33–35].The steps for CC to solve LSGO problems are described in Algorithm1 [36]. subgroupj holds the indexes of the decision variables of the jth subgroup. In traditional CC framework, computational resources are equally distributed, and line 5 is not executed. First, the population is initialized and static decomposition method decomposes LSGO problems (lines 1-2). Then each subgroup is optimized separately and the population is updated. To improve the utilization of computational resources, contribution-based CC (CBCC) is proposed as described in line 5 [34, 37]. After optimizing each subgroup once separately, the subgroup with the largest contribution value is selected to optimize to the termination condition. To balance the exploitation and exploration, the subgroup with the largest contribution is selected by CBCC3 [38], which is evolved to the condition where the subgroup with the second largest contribution from the last optimization is larger than the subgroup with the largest current contribution.Algorithm 1: CC_with_decomposition (FuncID, D).
(1)
initialize (population);(2)
subgroups⟵group (FunID, D);(3)
forcycles≤Maximumdo(4)
Optimize each subgroup separately;(5)
Select a subgroup with heaviest contribution and optimize to termination;(6)
end for(7)
returnfitness;


## 2.2. Decomposition Method

### 2.2.1. Problem Decomposition Framework

Problem decomposition framework is the logical structure of problem decomposition adopted by decomposition methods, and the logical structure determines the computational complexity of decomposition methods. Problem decomposition framework can be categorized into two types: double-pool decomposition framework and single-pool decomposition framework [39]. The double-pool decomposition framework includes a detection pool and an update pool, the identification between variables is performed in detection pool, and the identified variables are stored in the update pool, as shown in Figure 1(a). The variable interaction structure of the decomposition methods based on differential grouping belongs to the double-pool decomposition framework [24, 27–29]. In the single-pool decomposition framework, the two pools are integrated into a single one, as shown in Figure 1(b), and the interactions of decision variables can be identified one by one. Experiments [39] show that single-pool decomposition framework is more conducive to identification of the variables than double-pool decomposition framework. In this paper, we combine the advantages of these two decomposition frameworks and propose a hybrid-pool decomposition framework.Figure 1
Decomposition framework. (a) Double-pool procedure. (b) Single-pool procedure.
(a)(b)


### 2.2.2. Differential Grouping and Its Improvement

For differential functions, there are three relationships between decision variables: no relationship, direct relationship, and indirect relationship [24]. Based on these three relationships, three types of LSGO problems are constituted: full separable problem, partially separable problem, and full nonseparable problem, and the overlapping problem is a special type of partially separable problem. The primary task of problem decomposition is to identify the relationships between decision variables. For LSGO problem fX, the decision vector X of fX is divided into m1≤m≤D mutually exclusive subsets, as shown in equation (1), with Xi∩​Xj=∅ for any Xi,Xj∈X.(1)X1=x1,x2,…,xp,X2=xp+1,xp+2,…,xq,…,Xm=xk,xk+1,…,xD.DG decomposes problems by identifying the relationships between each pair of variables. Let the two variables identified bexi and xj, if the partial derivative is(2)∂2fX∂xi∂xj=0or≤ε.In the above equation,ε is a very small positive real number parameter of DG used for determining whether two variables are related. Then xi is unrelated to xj; otherwise xi is related to xj. If the relationship between two variables is indirect, it is difficult for the DG to identify this relationship, as in the problem described by the following equation:(3)fX=x1+x2+x32+x2+x42,where x3 and x4 are related through x2 interacting with each other and DG cannot find the relationship between x3 and x4 because(4)∂2fX∂x3∂x4=0.Problem decomposition by identifying the relationship between each pair of variables is inefficient. RDG significantly reduces the FEs by using a recursive detection structure in unidentified variables to complete problem decomposition. The theory of the identification for two sets of variables proved by Sun et al. is as follows [27]:(5)fx∗+l1u1+l2u2−fx∗+l2u2≠fx∗+l1u1−fx∗.LetX1,X2 be subsets of the decision vector X of fX, let u1 and u2 be unit vectors of X1 and X2, respectively, and x∗ is a feasible solution, where X1≠∅,X2≠∅, X1∩​X2=∅, and l1,l2>0. If some variables of X1 and X2 are related, inequality (7) holds. Conversely, X1 and X2 are not related to each other [27].Based on RDG, ERDG uses interaction history information to complete problem decomposition and further reduces the FEs [27, 30]. However, RDG and ERDG apply perturbations to the variables by giving the same upper and lower bounds to the variables to be identified, so that the perturbation to identify all problems is fixed. The two changes of the fitness value are(6)Δ1=fX1,ub−fX1,lb,(7)Δ2=fX2u,mb−fX2l,mb,where X1,ub and X1,lb are candidate solutions that are given upper bounds and lower bounds, respectively, and mb denotes the mean of the upper bounds ub and lower bounds lb. The variables belonging to X2u,mb and X2l,mb are assigned the same upper bounds and lower bounds as X1, respectively, and the variables that do not belong to X1 are assigned mb.


## 2.2.1. Problem Decomposition Framework

Problem decomposition framework is the logical structure of problem decomposition adopted by decomposition methods, and the logical structure determines the computational complexity of decomposition methods. Problem decomposition framework can be categorized into two types: double-pool decomposition framework and single-pool decomposition framework [39]. The double-pool decomposition framework includes a detection pool and an update pool, the identification between variables is performed in detection pool, and the identified variables are stored in the update pool, as shown in Figure 1(a). The variable interaction structure of the decomposition methods based on differential grouping belongs to the double-pool decomposition framework [24, 27–29]. In the single-pool decomposition framework, the two pools are integrated into a single one, as shown in Figure 1(b), and the interactions of decision variables can be identified one by one. Experiments [39] show that single-pool decomposition framework is more conducive to identification of the variables than double-pool decomposition framework. In this paper, we combine the advantages of these two decomposition frameworks and propose a hybrid-pool decomposition framework.Figure 1
Decomposition framework. (a) Double-pool procedure. (b) Single-pool procedure.
(a)(b)


## 2.2.2. Differential Grouping and Its Improvement

For differential functions, there are three relationships between decision variables: no relationship, direct relationship, and indirect relationship [24]. Based on these three relationships, three types of LSGO problems are constituted: full separable problem, partially separable problem, and full nonseparable problem, and the overlapping problem is a special type of partially separable problem. The primary task of problem decomposition is to identify the relationships between decision variables. For LSGO problem fX, the decision vector X of fX is divided into m1≤m≤D mutually exclusive subsets, as shown in equation (1), with Xi∩​Xj=∅ for any Xi,Xj∈X.(1)X1=x1,x2,…,xp,X2=xp+1,xp+2,…,xq,…,Xm=xk,xk+1,…,xD.DG decomposes problems by identifying the relationships between each pair of variables. Let the two variables identified bexi and xj, if the partial derivative is(2)∂2fX∂xi∂xj=0or≤ε.In the above equation,ε is a very small positive real number parameter of DG used for determining whether two variables are related. Then xi is unrelated to xj; otherwise xi is related to xj. If the relationship between two variables is indirect, it is difficult for the DG to identify this relationship, as in the problem described by the following equation:(3)fX=x1+x2+x32+x2+x42,where x3 and x4 are related through x2 interacting with each other and DG cannot find the relationship between x3 and x4 because(4)∂2fX∂x3∂x4=0.Problem decomposition by identifying the relationship between each pair of variables is inefficient. RDG significantly reduces the FEs by using a recursive detection structure in unidentified variables to complete problem decomposition. The theory of the identification for two sets of variables proved by Sun et al. is as follows [27]:(5)fx∗+l1u1+l2u2−fx∗+l2u2≠fx∗+l1u1−fx∗.LetX1,X2 be subsets of the decision vector X of fX, let u1 and u2 be unit vectors of X1 and X2, respectively, and x∗ is a feasible solution, where X1≠∅,X2≠∅, X1∩​X2=∅, and l1,l2>0. If some variables of X1 and X2 are related, inequality (7) holds. Conversely, X1 and X2 are not related to each other [27].Based on RDG, ERDG uses interaction history information to complete problem decomposition and further reduces the FEs [27, 30]. However, RDG and ERDG apply perturbations to the variables by giving the same upper and lower bounds to the variables to be identified, so that the perturbation to identify all problems is fixed. The two changes of the fitness value are(6)Δ1=fX1,ub−fX1,lb,(7)Δ2=fX2u,mb−fX2l,mb,where X1,ub and X1,lb are candidate solutions that are given upper bounds and lower bounds, respectively, and mb denotes the mean of the upper bounds ub and lower bounds lb. The variables belonging to X2u,mb and X2l,mb are assigned the same upper bounds and lower bounds as X1, respectively, and the variables that do not belong to X1 are assigned mb.


## 3. Proposed Method

### 3.1. Cooperative Coevolution with Two-Stage Decomposition

In this section, CC with TSD is proposed, which performs problem decomposition in the decomposition and optimization stages. In the decomposition stage, first the set of candidate solutions “population” is first initialized, and then HPDG groups the decision variables into different subgroups. In the optimization stage, KIDD dynamically decomposes the subgroups whose dimension is still high based on the decomposition information of HPDG, as described in Algorithm2. The CC proposed in this paper can decompose different types of problems before and during the optimization stage, whereas the traditional CC decomposes the problems only before or during the optimization.Algorithm 2: CC_with_TSD (FuncID, D).
(1)
Initialize population;(2)
subgroups⟵HPDG (FuncID, D);(3)
for FEs ≤ Maximum do(4)
subgroups⟵KIDD (subgroups);(5)
Traditional CC or contribution-based CC optimizes subgroups;(6)
end for(7)
return fitness;


### 3.2. Hybrid-Pool Differential Grouping

#### 3.2.1. Unit Vector-Based Perturbation

To determine whether two sets of variables are related, we apply perturbation to the sets. According to the IEEE 754 arithmetic [40], a large number of floating-point numbers affect the computational accuracy, and the HPD proposed in this paper uses the fixed-value perturbation described by equations (6) and (7) which affects the identification accuracy. We consider two types of problems divided in [41]:Type 1: The problems whose fitness value changes a lot even when very small upper bounds and very great lower bounds are set to those decision variables.Type 2: The problems whose fitness value changes slightly when very great upper bounds and very small lower bounds are set to those decision variables.The two types of changes in fitness values listed above are absolute changes, and relative change of fitness values is defined as follows.Definition 1.
Let the differences between the maximum and minimum values of problem 1 and problem 2 beθ1 and θ2, and the changes in fitness values are ϑ1 and θ2 for the same perturbation done for both problems, respectively. If ϑ1/θ1>ϑ2/θ2, then the change in fitness values of problem 1 is greater than that of problem 2.
Definition1 means that the magnitude of the change in fitness is compared relatively. The perturbation is applied to the set of variables according to the following equation. According to equation (5), the UVP strategy is described in equations (8) and (9), where l1 and l2 are real numbers greater than 0.(8)Δ1=fX|X1=X1+l1u1,X2−fX|X1,X2,(9)Δ2=fX|X1=X1+l1u1+l2u2,X2=X2+l2u2−fX|X1=X1+l2u2,X2=X2+l2u2.
SubsetsX1 and X2 of decision vector X are initialized. Then, the unit vectors u1 and u2 of X1 and X2 are calculated separately, and the variables in the decision vectors X1 and X2 that do not belong to X are assigned zero, and then the perturbations are applied to the currently identified subsets of variables, respectively.


#### 3.2.2. Hybrid-Pool Decomposition Framework

The hybrid-pool decomposition framework is shown in Figure2, where the detection pool and update pool are merged, all known groupings as detection pool and update pool and unidentified variables as another detection pool with one unidentified subgroup. The decomposition produce of HPDS is as follows. The current variable xi identifies relationships with other variables in detection pool and update pool, as shown in Figure 2. The identification between variables is divided into two parts: one is the identification of xi with the unidentified variables set V, and the other is the identification of xi with each identified subgroup through binary interaction, as shown in lines 5-6 of Algorithm 3; the interaction details are shown in Algorithm 4. Then the results of the interaction between two parts are combined as the steps in lines 7–17 of Algorithm 3. Zero means that no variable set is related to xi, and nonzero number means the index of the set related to xi.Figure 2
Hybrid-pool procedure.Algorithm 3: HPDG (FuncID, D).
(1)
V⟵x1,x2,…,xn;(2)
set seq and subgroups to∅;(3)
fori=1toD do(4)
left=1;right=sizesubgroups;(5)
r1=INTERACTIONxi,V,left,right;(6)
r2=INTERACTIONxi,subgroups,left,right;(7)
ifr1=0andr2=0then(8)
insertxi into seq;(9)
end if(10)
ifr1≠0andr2=0then(11)
create newsubgroupsright+1;(12)
insertxi into subgroupsright+1;(13)
end if(14)
ifr2≠0then(15)
insertxi into subgroupsr2;(16)
end if(17)
deletexi from V;(18)
end for(19)
return subgroups;Algorithm 4: Interaction (X1, X2, left, right).
(1)
ifleft≤rightthen(2)
middle=left+right/2;(3)
X1=X1+l1u1;(4)
delta1=y−computeFX1;(5)
X1=X1+l1u1+l2u2;X2=X2+l2u2;(6)
delta2=computeFX2−computeFX2;(7)
delta=fabsdelta1−delta2;(8)
ifdelta>ϵthen(9)
ifleft=rightthen(10)
return middle;(11)
else(12)
IDENTIFICATIONX1,X2,left,middle;(13)
end if(14)
else(15)
ifleft=rightthen(16)
return 0;(17)
else(18)
IDENTIFICATIONX1,X2,middle+1,right;(19)
end if(20)
end if(21)
end ifThe steps of binary detection for the identification of the current variablexi with other variables are described in Algorithm 3. First, xi interacts with all known subgroups at one time; if xi is not related to all subgroups, algorithm exits; otherwise, the known subgroups will be divided into two equal-sized parts, and xi interacts with one part of the known subgroups, and if they are related, the subgroups continue recursion; otherwise, xi interacts with the other known subgroups recursively. Continue the above operations until the subgroup related to xi is identified.


#### 3.2.3. Decomposition Complexity Analysis of HPDG

The detection complexity of the variablexi with known subgroups is shown in Figure 3. Let there be m subgroups after the problem is decomposed, and the detection depth of xi is p. The part in curly bracket indicates the set of subgroups interacting with xi. The number of subgroups m in the p th level can be expressed as m=2p−1, so the detection depth p=logm+1, and the decomposition complexity of HPDG of n-dimensional problem is Onlogm.Figure 3
HPD detection depth analysis.


### 3.3. Known Information-Based Dynamic Decomposition Method

In this section, we propose the KIDD method for the limitation that the static decomposition method cannot decompose fully nonseparable problems. KIDD and HPDG together constitute the TSD method to improve the performance of CC solving LSGO problems. KIDD is detailed in Algorithm5.Algorithm 5: KIDD (subgroups).
(1)
whilei=1tosizesubgroupsdo(2)
ifnumsubgroupi>subDthen(3)
random decompositionsubgroupi;(4)
update subgroups;(5)
end if(6)
end while(7)
return subgroups;KIDD checks all subgroups’ dimension decomposed by HPDG; if the subgroup’s dimension exceeds subD, the subgroup is decomposed by random grouping [18] and update subgroups set. subD denotes subgroup dimension, and the value of subD is set according to the performance of the optimizer used by CC.


## 3.1. Cooperative Coevolution with Two-Stage Decomposition

In this section, CC with TSD is proposed, which performs problem decomposition in the decomposition and optimization stages. In the decomposition stage, first the set of candidate solutions “population” is first initialized, and then HPDG groups the decision variables into different subgroups. In the optimization stage, KIDD dynamically decomposes the subgroups whose dimension is still high based on the decomposition information of HPDG, as described in Algorithm2. The CC proposed in this paper can decompose different types of problems before and during the optimization stage, whereas the traditional CC decomposes the problems only before or during the optimization.Algorithm 2: CC_with_TSD (FuncID, D).
(1)
Initialize population;(2)
subgroups⟵HPDG (FuncID, D);(3)
for FEs ≤ Maximum do(4)
subgroups⟵KIDD (subgroups);(5)
Traditional CC or contribution-based CC optimizes subgroups;(6)
end for(7)
return fitness;


## 3.2. Hybrid-Pool Differential Grouping

### 3.2.1. Unit Vector-Based Perturbation

To determine whether two sets of variables are related, we apply perturbation to the sets. According to the IEEE 754 arithmetic [40], a large number of floating-point numbers affect the computational accuracy, and the HPD proposed in this paper uses the fixed-value perturbation described by equations (6) and (7) which affects the identification accuracy. We consider two types of problems divided in [41]:Type 1: The problems whose fitness value changes a lot even when very small upper bounds and very great lower bounds are set to those decision variables.Type 2: The problems whose fitness value changes slightly when very great upper bounds and very small lower bounds are set to those decision variables.The two types of changes in fitness values listed above are absolute changes, and relative change of fitness values is defined as follows.Definition 1.
Let the differences between the maximum and minimum values of problem 1 and problem 2 beθ1 and θ2, and the changes in fitness values are ϑ1 and θ2 for the same perturbation done for both problems, respectively. If ϑ1/θ1>ϑ2/θ2, then the change in fitness values of problem 1 is greater than that of problem 2.
Definition1 means that the magnitude of the change in fitness is compared relatively. The perturbation is applied to the set of variables according to the following equation. According to equation (5), the UVP strategy is described in equations (8) and (9), where l1 and l2 are real numbers greater than 0.(8)Δ1=fX|X1=X1+l1u1,X2−fX|X1,X2,(9)Δ2=fX|X1=X1+l1u1+l2u2,X2=X2+l2u2−fX|X1=X1+l2u2,X2=X2+l2u2.
SubsetsX1 and X2 of decision vector X are initialized. Then, the unit vectors u1 and u2 of X1 and X2 are calculated separately, and the variables in the decision vectors X1 and X2 that do not belong to X are assigned zero, and then the perturbations are applied to the currently identified subsets of variables, respectively.


### 3.2.2. Hybrid-Pool Decomposition Framework

The hybrid-pool decomposition framework is shown in Figure2, where the detection pool and update pool are merged, all known groupings as detection pool and update pool and unidentified variables as another detection pool with one unidentified subgroup. The decomposition produce of HPDS is as follows. The current variable xi identifies relationships with other variables in detection pool and update pool, as shown in Figure 2. The identification between variables is divided into two parts: one is the identification of xi with the unidentified variables set V, and the other is the identification of xi with each identified subgroup through binary interaction, as shown in lines 5-6 of Algorithm 3; the interaction details are shown in Algorithm 4. Then the results of the interaction between two parts are combined as the steps in lines 7–17 of Algorithm 3. Zero means that no variable set is related to xi, and nonzero number means the index of the set related to xi.Figure 2
Hybrid-pool procedure.Algorithm 3: HPDG (FuncID, D).
(1)
V⟵x1,x2,…,xn;(2)
set seq and subgroups to∅;(3)
fori=1toD do(4)
left=1;right=sizesubgroups;(5)
r1=INTERACTIONxi,V,left,right;(6)
r2=INTERACTIONxi,subgroups,left,right;(7)
ifr1=0andr2=0then(8)
insertxi into seq;(9)
end if(10)
ifr1≠0andr2=0then(11)
create newsubgroupsright+1;(12)
insertxi into subgroupsright+1;(13)
end if(14)
ifr2≠0then(15)
insertxi into subgroupsr2;(16)
end if(17)
deletexi from V;(18)
end for(19)
return subgroups;Algorithm 4: Interaction (X1, X2, left, right).
(1)
ifleft≤rightthen(2)
middle=left+right/2;(3)
X1=X1+l1u1;(4)
delta1=y−computeFX1;(5)
X1=X1+l1u1+l2u2;X2=X2+l2u2;(6)
delta2=computeFX2−computeFX2;(7)
delta=fabsdelta1−delta2;(8)
ifdelta>ϵthen(9)
ifleft=rightthen(10)
return middle;(11)
else(12)
IDENTIFICATIONX1,X2,left,middle;(13)
end if(14)
else(15)
ifleft=rightthen(16)
return 0;(17)
else(18)
IDENTIFICATIONX1,X2,middle+1,right;(19)
end if(20)
end if(21)
end ifThe steps of binary detection for the identification of the current variablexi with other variables are described in Algorithm 3. First, xi interacts with all known subgroups at one time; if xi is not related to all subgroups, algorithm exits; otherwise, the known subgroups will be divided into two equal-sized parts, and xi interacts with one part of the known subgroups, and if they are related, the subgroups continue recursion; otherwise, xi interacts with the other known subgroups recursively. Continue the above operations until the subgroup related to xi is identified.


### 3.2.3. Decomposition Complexity Analysis of HPDG

The detection complexity of the variablexi with known subgroups is shown in Figure 3. Let there be m subgroups after the problem is decomposed, and the detection depth of xi is p. The part in curly bracket indicates the set of subgroups interacting with xi. The number of subgroups m in the p th level can be expressed as m=2p−1, so the detection depth p=logm+1, and the decomposition complexity of HPDG of n-dimensional problem is Onlogm.Figure 3
HPD detection depth analysis.


## 3.2.1. Unit Vector-Based Perturbation

To determine whether two sets of variables are related, we apply perturbation to the sets. According to the IEEE 754 arithmetic [40], a large number of floating-point numbers affect the computational accuracy, and the HPD proposed in this paper uses the fixed-value perturbation described by equations (6) and (7) which affects the identification accuracy. We consider two types of problems divided in [41]:Type 1: The problems whose fitness value changes a lot even when very small upper bounds and very great lower bounds are set to those decision variables.Type 2: The problems whose fitness value changes slightly when very great upper bounds and very small lower bounds are set to those decision variables.The two types of changes in fitness values listed above are absolute changes, and relative change of fitness values is defined as follows.Definition 1.
Let the differences between the maximum and minimum values of problem 1 and problem 2 beθ1 and θ2, and the changes in fitness values are ϑ1 and θ2 for the same perturbation done for both problems, respectively. If ϑ1/θ1>ϑ2/θ2, then the change in fitness values of problem 1 is greater than that of problem 2.
Definition1 means that the magnitude of the change in fitness is compared relatively. The perturbation is applied to the set of variables according to the following equation. According to equation (5), the UVP strategy is described in equations (8) and (9), where l1 and l2 are real numbers greater than 0.(8)Δ1=fX|X1=X1+l1u1,X2−fX|X1,X2,(9)Δ2=fX|X1=X1+l1u1+l2u2,X2=X2+l2u2−fX|X1=X1+l2u2,X2=X2+l2u2.
SubsetsX1 and X2 of decision vector X are initialized. Then, the unit vectors u1 and u2 of X1 and X2 are calculated separately, and the variables in the decision vectors X1 and X2 that do not belong to X are assigned zero, and then the perturbations are applied to the currently identified subsets of variables, respectively.


## 3.2.2. Hybrid-Pool Decomposition Framework

The hybrid-pool decomposition framework is shown in Figure2, where the detection pool and update pool are merged, all known groupings as detection pool and update pool and unidentified variables as another detection pool with one unidentified subgroup. The decomposition produce of HPDS is as follows. The current variable xi identifies relationships with other variables in detection pool and update pool, as shown in Figure 2. The identification between variables is divided into two parts: one is the identification of xi with the unidentified variables set V, and the other is the identification of xi with each identified subgroup through binary interaction, as shown in lines 5-6 of Algorithm 3; the interaction details are shown in Algorithm 4. Then the results of the interaction between two parts are combined as the steps in lines 7–17 of Algorithm 3. Zero means that no variable set is related to xi, and nonzero number means the index of the set related to xi.Figure 2
Hybrid-pool procedure.Algorithm 3: HPDG (FuncID, D).
(1)
V⟵x1,x2,…,xn;(2)
set seq and subgroups to∅;(3)
fori=1toD do(4)
left=1;right=sizesubgroups;(5)
r1=INTERACTIONxi,V,left,right;(6)
r2=INTERACTIONxi,subgroups,left,right;(7)
ifr1=0andr2=0then(8)
insertxi into seq;(9)
end if(10)
ifr1≠0andr2=0then(11)
create newsubgroupsright+1;(12)
insertxi into subgroupsright+1;(13)
end if(14)
ifr2≠0then(15)
insertxi into subgroupsr2;(16)
end if(17)
deletexi from V;(18)
end for(19)
return subgroups;Algorithm 4: Interaction (X1, X2, left, right).
(1)
ifleft≤rightthen(2)
middle=left+right/2;(3)
X1=X1+l1u1;(4)
delta1=y−computeFX1;(5)
X1=X1+l1u1+l2u2;X2=X2+l2u2;(6)
delta2=computeFX2−computeFX2;(7)
delta=fabsdelta1−delta2;(8)
ifdelta>ϵthen(9)
ifleft=rightthen(10)
return middle;(11)
else(12)
IDENTIFICATIONX1,X2,left,middle;(13)
end if(14)
else(15)
ifleft=rightthen(16)
return 0;(17)
else(18)
IDENTIFICATIONX1,X2,middle+1,right;(19)
end if(20)
end if(21)
end ifThe steps of binary detection for the identification of the current variablexi with other variables are described in Algorithm 3. First, xi interacts with all known subgroups at one time; if xi is not related to all subgroups, algorithm exits; otherwise, the known subgroups will be divided into two equal-sized parts, and xi interacts with one part of the known subgroups, and if they are related, the subgroups continue recursion; otherwise, xi interacts with the other known subgroups recursively. Continue the above operations until the subgroup related to xi is identified.


## 3.2.3. Decomposition Complexity Analysis of HPDG

The detection complexity of the variablexi with known subgroups is shown in Figure 3. Let there be m subgroups after the problem is decomposed, and the detection depth of xi is p. The part in curly bracket indicates the set of subgroups interacting with xi. The number of subgroups m in the p th level can be expressed as m=2p−1, so the detection depth p=logm+1, and the decomposition complexity of HPDG of n-dimensional problem is Onlogm.Figure 3
HPD detection depth analysis.


## 3.3. Known Information-Based Dynamic Decomposition Method

In this section, we propose the KIDD method for the limitation that the static decomposition method cannot decompose fully nonseparable problems. KIDD and HPDG together constitute the TSD method to improve the performance of CC solving LSGO problems. KIDD is detailed in Algorithm5.Algorithm 5: KIDD (subgroups).
(1)
whilei=1tosizesubgroupsdo(2)
ifnumsubgroupi>subDthen(3)
random decompositionsubgroupi;(4)
update subgroups;(5)
end if(6)
end while(7)
return subgroups;KIDD checks all subgroups’ dimension decomposed by HPDG; if the subgroup’s dimension exceeds subD, the subgroup is decomposed by random grouping [18] and update subgroups set. subD denotes subgroup dimension, and the value of subD is set according to the performance of the optimizer used by CC.


## 4. Experiment Results and Discussion

### 4.1. Experimental Methodology

The performances of the decomposition methods were compared on the IEEE CEC’2010 and CEC’2013 special sessions on large-scale global optimization [42, 43]. The experiments in this paper were divided into two parts. In the first part, HPDG was compared with DG [24], DG2 [25], RDG [27], RDG2 [28], and ERDG [30] on problem decomposition. HPDG set ε as RDG did, and the values of α used to calculate ε are shown in Tables 1 and 2.Table 1
The values ofα in CEC’2013 special sessions on large-scale global optimization.
Ff1f2f3f4-f5f6f7-f8f9f10f11f12–f15α1.00e−121.00e−101.00e−141.00e−121.00e−151.00e−121.00e−141.00e−151.00e−161.00e−12Table 2
The values ofα in CEC’2010 special sessions on large-scale global optimization.
Ff1-f2f3f4-f5f6f7–f20α1.00e−121.00e−031.00e−121.00e−101.00e−20Three evaluation metrics were selected to evaluate the performance of the decomposition methods:(1)
The decomposition accuracy is calculated as [30]; decision variables that are corelated to each other are grouped into the same subgroup and the variables that are not corelated to each other are grouped into different subgroups. In the experimental tables, “separable” and “non-sep” columns represent the decomposition accuracy of separable and nonseparable variables, respectively.(2)
The number of function evaluations (FEs) is used to decompose the problem [42, 43].(3)
In this paper, the growth rate of FEs is introduced to evaluate the performance of decomposition methods on high-dimensional problems, as in the following equation:(10)gr=hdFEs−ldFEsldFEs×100%,where gr denotes the growth rate of FEs, and hdFEs and ldFEs denote the FEs of two different dimensional problems, respectively.In the second part, TSD and other decomposition methods embedded in DECC were compared on problem optimization. Adaptive differential evolution with optional external archive (JADE) [44] was used to optimize the problem in optimization stage. FEs are set to 3e + 6 as the termination condition for each run of the experiment [43]. The parameters of the decomposition methods and JADE were set as in their publications.


### 4.2. Decomposition Comparison

#### 4.2.1. Comparison on Perturbation Strategy

In this section, we verify the effectiveness of UVP. As described in Table3, HPDS with UVP correctly decomposes the four test functions f3, f6, f7, and f10 and improves the decomposition accuracy on f8 and f11 compared with HPDS with fixed-value perturbation (FVP). That is because UVP applies perturbation of appropriate size when two sets of the variables interact, while the perturbation applied by FVP cannot satisfy the requirements of different problems.Table 3
Decomposition results of HPDG with UVP and FVP on 1000-dimensional CEC’2013 special sessions on large-scale global optimization. For each function, the best values of FEs and decomposition accuracy among different decomposition methods are shown in bold, respectively.
FHPDS with UVPHPDS with FVPFEsSeparableNon-sepFEsSeparableNon-sepf13008100.0%—3008100.0%—f23008100.0%—3008100.0%—f330080.0%—3008100.0%—f46704100.0%100.0%6704100.0%100.0%f58014100.0%0.0%8014100.0%0.0%f6108840.0%0.0%10884100.0%100.0%f766720.0%0.0%6672100.0%100.0%f88865—0.0%9506—20.0%f915367—100.0%13668—100.0%f1013988—0.0%14008—100.0%f1114298—0.0%14298—25.0%f125008—100.0%5008—100.0%f1313731—0.0%13804—0.0%f1413737—0.0%13388—0.0%f155008—100.0%5008—100.0%


#### 4.2.2. Decomposition Results of HPDG and Other Decomposition Methods

Table4 summarizes the decomposition results on CEC’2013 special sessions on large-scale global optimization. HPDG correctly decomposes all functions except f5, f8, f11, f13, and f15. HPDG suffers from a flaw when detecting the indirect relationship between variables; if the shared variables are not grouped firstly, the indirect related variables cannot be grouped into the same subgroup. Although the number of functions correctly decomposed by HPDG is similar compared to DG2, RDG, and RDG2, HPDG uses fewer Fes; as shown in the last row of Table 3, HPDG correctly decomposes 7 functions using fewer FEs than other methods. HPDG uses the fewest FEs on 9 out of 15 functions; this is because HPDG has lower decomposition complexity compared to other methods.Table 4
Decomposition results on 1000-dimensional CEC’2013 special sessions on large-scale global optimization. For each function, the best values of FEs and decomposition accuracy among different decomposition methods are shown in bold, respectively. Total number indicates the number of functions that are correctly decomposed by each method using fewer FEs than other methods.
HPDGNon-sep———100.0%0.0%100.0%100.0%20.0%100.0%100.0%25.0%100.0%0.0%0.0%100.0%7Separable100.0%100.0%100.0%100.0%100.0%100.0%100.0%————————FEs3.01e +033.01e +033.01e +036.70e +038.01e +031.09e +046.67e +039.51e +031.37e +041.40e +041.43e +045.01e +031.38e +041.34e +045.01e +03RDG2Non-sep———100.0%100.0%100.0%100.0%80.0%100.0%100.0%100.0%100.0%0.0%100.0%100.0%2Separable100.0%100.0%0.0%100.0%100.0%0.0%100.0%————————FEs3.00e +033.00e +036.01e +039.83e +039.90e +031.16e +049.81e +031.94e +041.91e +041.99e +041.94e +045.09e +041.52e +041.61e +045.99e +03RDGNon-sep———100.0%100.0%91.0%0.0%70.0%100.0%86.0%0.0%100.0%0.0%100.0%100.0%1Separable100.0%100.0%0.0%100.0%100.0%4.0%27.0%————————FEs3.01e +033.01e +036.00e +039.84e +031.11e +041.40e +041.19e +041.97e +041.97e +042.00e +041.13e +045.09e +048.60e +039.54e +036.15e +03DG2Non-sep———100.0%100.0%100.0%50.0%80.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%0Separable100.0%100.0%0.0%5.4%100.0%0.0%100.0%————————FEs5.01e +055.01e +055.01e +055.01e +055.01e +055.01e +055.01e +055.01e +055.01e +055.01e +055.01e +055.01e +054.10e +054.10e +055.01e +05DGNon-sep———49.0%66.0%50.0%0.0%65.0%100.0%65.0%0.0%0.0%0.0%0.0%100.0%1Separable100.0%100.0%100.0%5.0%100.0%100.0%9.0%————————FEs1.00e +061.00e +061.00e +061.60e +045.31e +055.81e +051.27e +042.27e +041.77e +044.80e +049.88e +031.51e +055.97e +031.40e +042.00e +03Ff1f2f3456789101112131415Total number


#### 4.2.3. Decomposition Results on High-Dimensional Functions

Since the structures of CEC’2013 special sessions on large-scale global optimization are fixed, the robustness of the decomposition methods is compared on extended high-dimensional CEC’2010 special sessions on large-scale global optimization. The extended high-dimensional CEC’2010 functions as the consistent set in the original CEC’2010 special sessions on large-scale global optimization [30].Tables5–9 summarize the decomposition results of the decomposition methods on 1000- to 5000-dimensional functions. Except for DG, each decomposition method has similar decomposition accuracy on the extended high-dimensional CEC’2010 functions, and all can decompose most of them correctly, but the FEs are significantly different. As the dimension grows, FEs used by DG and DG2 increase the most, RDG and RDG2 follow, and ERDG and HPDG are the best. That is because the complexity of DG and DG2 is On2 [24, 25], and the complexity of RDG and RDG2 is Onlogn [27, 28]. Table 10 summarizes the growth rates of FEs used by RDG, ERDG, and HPDG, which are calculated by equation (10). The least growth of FEs is used by ERDG and HPDG; this is because ERDG uses the historical information of variable interactions to avoid examining some interrelationship between variables [30], and the complexity of HPDG is Onlogm, which is the lowest. The FEs used by HPDG and ERDG are comparable. As described in Table 10, the growth rate of FEs used by HPDG is slightly better than that of ERDG.Table 5
Decomposition results on 1000-dimesnional CEC’2010 special sessions on large-scale global optimization. For each function, the best values of FEs and decomposition accuracy among different decomposition methods are shown in bold font, respectively.
HPDGNon-sep———100.0%100.0%100.0%100.0%0.0%100.0%100.0%100.0%100.0%0.0%100.0%100.0%100.0%100.0%0.0%100.0%100.0%Separable100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%0.0%100.0%100.0%———————FEs3.01e +033.01e +033.01e +035.01e +035.01e +035.01e +035.01e +035.26e +038.31e +038.31e +031.23e +048.31e +039.75e +031.36e +041.36e +041.36e +041.36e +041.59e +045.01e +035.01e +03RDG2Non-sep———100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%Separable100.0%100.0%0.0%100.0%100.0%0.0%100.0%100.0%100.0%100.0%0.0%100.0%100.0%———————FEs3.00e +033.00e +035.99e +034.29e +034.24e +038.56e +034.22e +035.60e +031.04e +041.40e +041.37e +041.43e +042.92e +042.06e +042.05e +042.09e +042.08e +044.99e +045.99e +035.09e +04RDGNon-sep———100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%Separable100.0%100.0%0.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%0.0%100.0%100.0%———————FEs3.01e +033.01e +036.00e +034.21e +034.15e +035.10e +044.23e +035.61e +031.43e +041.40e +041.37e +041.43e +042.92e +042.06e +042.05e +042.09e +042.08e +044.99e +046.00e +035.09e +04DG2Non-sep———100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%Separable100.0%100.0%0.0%100.0%100.0%8.6%100.0%100.0%100.0%100.0%8.6%100.0%100.0%———————FEs5.01e +055.01e +055.01e +055.01e +055.01e +055.01e +055.01e +055.01e +055.01e +055.01e +055.01e +055.01e +055.01e +055.01e +055.01e +055.01e +055.01e +055.01e +055.01e +055.01e +05DGNon-sep———100.0%100.0%100.0%0.0%0.0%100.0%100.0%90.0%100.0%0.0%100.0%100.0%80.0%100.0%0.0%100.0%0.0%Separable100.0%100.0%100.0%3.5%100.0%100.0%26.1%14.0%100.0%100.0%100.0%100.0%21.4%———————FEs1.00e +061.00e +061.00e +061.46e +049.06e +059.06e +056.77e +042.33e +042.71e +052.73e +052.71e +052.71e +055.03e +0420e +0442.10e +042.11e +042.10e +043.96e +042.00e +031.55e +05Ff1f2f3f4f5f6f7f8f9f10f11f12f13f14f15f16f17f18f19f20Table 6
Decomposition results on 2000-dimensiional CEC’2010 special sessions on large-scale global optimization. For each function, the best values of FEs and decomposition accuracy among different decomposition methods are shown in bold, respectively.
HPDGNon-sep———100.0%100.0%100.0%100.0%0.0%100.0%100.0%100.0%100.0%0.0%100.0%100.0%100.0%100.0%0.0%100.0%100.0%Separable100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%0.0%100.0%100.0%———————FEs6.01e +036.01e +036.01e +039.97e +039.97e +039.97e +039.97e +031.02e +041.86e +041.86e +042.88e +041.86e +042.07e +043.11e +043.11e +043.11e +043.11e +043.42e +041.00e +041.11e +04RDG2Non-sep———100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%Separable100.0%100.0%0.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%0.0%100.0%100.0%———————FEs6.00e +036.00e +031.20e +047.43e +037.58e +032.21e +067.45e +039.06e +033.36e +043.34e +043.08e +043.34e +046.44e +045.08e +045.21e +045.11e +035.18e +041.12e +051.20e +041.14e +05RDGNon-sep———100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%Separable100.0%100.0%0.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%0.0%100.0%100.0%———————FEs6.01e +036.01e +031.20e +047.44e +037.54e +035.32e +047.46e +039.07e +033.36e +043.34e +043.08e +043.34e +046.44e +045.08e +045.21e +045.11e +045.19e +041.12e +051.20e +041.14e +05DG2Non-sep———100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%Separable100.0%100.0%0.0%100.0%100.0%22.1%100.0%100.0%100.0%100.0%0.0%100.0%100.0%———————FEs2.00e +062.00e +062.00e +062.00e +062.00e +062.00e +062.00e +062.00e +062.00e +062.00e +062.00e +062.00e +062.00e +062.00e +062.00e +062.00e +062.00e +062.00e +062.00e +062.00e +06DGNon-sep———0.0100.0%100.0%100.0%0.0%100.0%100.0%85.0%100.0%0.0%100.0%100.0%87.5%100.0%0.0%100.0%0.0%Separable100.0%100.0%100.0%3.0%100.0%100.0%5.0%4.0%100.0%100.0%100.0%100.0%18.4%———————FEs4.00e +064.00e +064.00e +063.34e +043.81e +063.81e +063.20e +042.80e +041.10e +061.10e +061.10e +061.09e +061.38e +058.20e +048.20e +048.23e +048.20e +041.82e +054.00e +035.83e +05Ff1f2f3f4f5f6f7f8f9f10f11f12f13f14f15f16f17f18f19f20Table 7
Decomposition results on 3000-dimensional CEC'2010 special sessions on large-scale global optimization. For each function, the best values of FEs and decomposition accuracy among different decomposition methods are shown in bold, respectively.
HPDGNon-sep———100.0%100.0%100.0%100.0%0.0%100.0%100.0%100.0%100.0%0.0%100.0%100.0%100.0%100.0%0.0%100.0%100.0%Separable100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%0.0%100.0%100.0%———————FEs9.01e +039.01e +039.01e +031.47e +041.47e +041.47e +041.47e +041.50e +042.95e +042.95e +044.45e +042.95e +043.22e +044.98e +044.98e +044.98e +044.98e +045.34e +041.50e +041.50e +04RDG2Non-sep———100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%Separable100.0%100.0%0.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%0.0%100.0%100.0%———————FEs9.00e +039.00e +031.80e +041.06e +041.06e +041.84e +061.05e +041.20e +045.48e +045.51e +045.06e +045.52e +041.01e +058.62e +048.66e +048.59e +048.63e +041.77e +051.80e +041.82e +05RDGNon-sep———100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%Separable100.0%100.0%0.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%0.0%100.0%100.0%———————FEs9.01e +039.01e +031.80e +041.06e +041.06e +046.03e +041.05e +041.20e +045.49e +045.51e +045.09e +045.52e +041.01e +058.62e +048.66e +048.59e +048.63e +041.77e +051.80e +041.82e +05DG2Non-sep———100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%Separable100.0%100.0%0.0%100.0%100.0%8.3%100.0%100.0%100.0%100.0%0.0%100.0%100.0%———————FEs4.50e +064.50e +064.50e +064.50e +064.50e +064.50e +064.50e +064.50e +064.50e +064.50e +064.50e +064.50e +064.50e +064.50e +064.50e +064.50e +064.50e +064.50e +064.50e +064.50e +06DGNon-sep———0.0%100.0%100.0%0.0%0.0%100.0%100.0%70.0%100.0%0.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%Separable100.0%100.0%100.0%3.0%100.0%100.0%17.0%4.0%100.0%100.0%100.0%100.0%5.0%———————FEs9.00e +069.00e +069.00e +063.76e +048.71e +068.71e +062.74e +053.87e +042.45e +062.48e +062.53e +062.49e +069.50e +041.83e +051.83e +051.84e +051.83e +052.47e +056.00e +035.39e +05Ff1f2f3f4f5f6f7f8f9f10f11f12f13f14f15f16f17f18f19f20Table 8
Decomposition results on 4000-dimensional CEC'2010 special sessions on large-scale global optimization. For each function, the best values of FEs and decomposition accuracy among different decomposition methods are shown in bold, respectively.
HPDGNon-sep———100.0%100.0%100.0%100.0%0.0%100.0%100.0%100.0%100.0%0.0%100.0%100.0%100.0%100.0%0.0%100.0%100.0%Separable100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%0.0%100.0%100.0%———————FEs1.20e +041.20e +041.20e +042.00e +042.00e +042.00e +042.00e +042.02e +044.11e +044.11e +046.52e +044.11e +044.46e +047.00e +047.00e +047.00e +047.00e +047.45e +042.00e +042.00e +04RDG2Non-sep———100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%Separable100.0%100.0%0.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%0.0%100.0%100.0%———————FEs1.20e +041.20e +042.40e +041.38e +041.38e +041.55e +061.38e +041.54e +047.81e +047.79e +047.20e +047.80e +041.41e +051.24e +051.24e +051.23e +051.23e +052.44e +052.40e +042.51e +05RDGNon-sep———100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%Separable100.0%100.0%0.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%0.0%100.0%100.0%———————FEs1.20e +041.20e +042.40e +041.39e +041.38e +046.41e +041.38e +041.54e +057.81e +047.79e +047.29e +047.80e +041.41e +051.24e +051.24e +051.23e +051.23e +052.44e +052.40e +042.51e +05DG2Non-sep———100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%Separable100.0%100.0%0.0%100.0%100.0%15.7%100.0%100.0%100.0%99.8%0.0%100.0%100.0%———————FEs8.00e +068.00e +068.00e +068.00e +068.00e +068.00e +068.00e +068.00e +068.00e +068.00e +068.00e +068.00e +068.00e +068.00e +068.00e +068.00e +068.00e +068.00e +068.00e +068.00e +06DGNon-sep———0.0%100.0%100.0%100.0%0.0%100.0%100.0%85.0%100.0%0.0%100.0%100.0%86.5%100.0%0.0%100.0%0.0%Separable100.0%100.0%100.0%3.5%100.0%100.0%20.0%32.0%100.0%100.0%100.0%100.0%10.0%———————FEs1.60e +071.60e +071.60e +072.87e +041.56e +071.56e +075.54e +051.49e +064.36e +064.39e +064.39e +064.41e +063.29e +058.72e +043.24e +053.26e +053.24e +055.20e +058.00e +031.72e +06Ff1f2f3f4f5f6f7f8f9f10f11f12f13f14f15f16f17f18f19f20Table 9
Decomposition results on 5000-dimensional CEC'2010 special sessions on large-scale global optimization. For each function, the best values of FEs and decomposition accuracy among different decomposition methods are shown in bold, respectively.
HPDGNon-sep———100.0%100.0%100.0%100.0%0.0%100.0%100.0%100.0%100.0%0.0%100.0%100.0%100.0%100.0%0.0%100.0%100.0%Separable100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%0.0%100.0%100.0%———————FEs1.50e +041.50e +041.50e +042.50e +042.50e +042.50e +042.50e +042.52e +045.29e +045.29e +048.30e +045.29e +045.67e +049.07e +049.07e +049.07e +049.07e +049.47e +042.50e +042.50e +04RDG2Non-sep———100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%Separable100.0%100.0%0.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%0.0%100.0%100.0%———————FEs1.50e +041.50e +042.40e +041.68e +041.70e +041.44e +061.68e +041.83e +041.02e +051.02e +059.42e +041.02e +051.82e +051.63e +051.63e +051.64e +051.64e +053.18e +053.00e +043.26e +05RDGNon-sep———100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%Separable100.0%100.0%0.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%0.0%100.0%100.0%———————FEs1.50e +041.50e +043.01e +041.68e +041.70e +047.05e +041.68e +041.83e +041.02e +051.02e +059.42e +041.02e +051.82e +051.63e +051.63e +051.64e +051.64e +053.18e +053.00e +043.26e +05DG2Non-sep———100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%Separable100.0%100.0%0.0%100.0%100.0%8.3%100.0%100.0%100.0%100.0%0.0%100.0%100.0%———————FEs1.25e +071.25e +071.25e +071.25e +071.25e +071.25e +071.25e +071.25e +071.25e +071.25e +071.25e +071.25e +071.25e +071.25e +071.25e +071.25e +071.25e +071.25e +071.25e +071.25e +07DGNon-sep———0.0%100.0%100.0%0.0%0.0%100.0%100.0%74.0%100.0%0.0%100.0%100.0%80.0%100.0%0.0%100.0%0.0%Separable100.0%100.0%100.0%2.0%100.0%100.0%31.1%3.8%100.0%100.0%100.0%100.0%12.6%———————FEs2.48e +072.50e +072.50e +076.05e +042.45e +072.45e +072.44e +068.95e +046.97e +066.87e +066.95e +066.89e +065.95e +055.05e +055.05e +055.11e +055.05e +059.82e +051.00e +041.14e +06Ff1f2f3f4f5f6f7f8f9f10f11f12f13f14f15f16f17f18f19f20Table 10
The average growth rates of FEs off1, f2, f4, f5, f7, f10, f12, f13, f14, f15, f16, f17, f18, f19, and f20 on CEC’2010 special sessions on large-scale global optimization. The best growth rates of FEs are shown in bold font.
Decomposition methodRDG (%)ERDG (%)HPDG (%)D = 1000 to D = 2000124.1116.114.4D = 2000 to D = 300057.157.154.2D = 3000 to D = 400037.736.737.2D = 4000 to D = 500028.029.327.1


### 4.3. Optimization Results of CC with Decomposition Methods

Table11 summarizes the optimization results of the decomposition methods being embedded in DECC [24]. The DECC-TSD proposed in this paper achieves the best optimization results on six functions. Compared with the state-of-the-art DECC-ERDG, DECC-TSD is more advantageous on the fully nonseparable function f15. Therefore, DECC-TSD alleviates the dilemma of CC with static decomposition in solving the fully nonseparable problems.Table 11
The optimization results on CEC’2013 special sessions on large-scale global optimization,D = 1000. Average fitness values and deviations on CEC’2013 special sessions on large-scale global optimization over 25 independent results. The significantly best results are in bold (Wilcoxon test with home p value correction, α = 0.05).
FDECC-RDGDECC-RDG2DECC-ERDGDECC-HPDGDECC-TSDf1MeanStd3.66E +111.24E +103.66E +111.28E +103.41E +111.22E +103.68E +111.85E +103.69E +111.36E +10f2MeanStd1.34E +054.43E +031.36E +054.39E +031.44E +054.40E +031.20E +053.67E +031.21E +053.55E +03f3MeanStd3.42E +015.31E − 033.73E +01556E − 033.41E +015.41E − 032.17E +017.14E − 032.16E +016.84E − 03f4MeanStd4.53E +121.98E +114.33E +121.75E +114.13E +121.27E +111.89E +124.22E +113.33E +125.36E +11f5MeanStd5.21E +074.32E +065.28E +074.35E +061.21E +072.12E +062.83E +072.34E +063.24E +072.97E +06f6MeanStd1.10E +061.21E +021.13E +061.19E +029.98E +061.31E +021.07E +069.58E +021.07E +067.87E +02f7MeanStd6.12E +113.01E +116.31E +113.10E +111.12E +112.47E +112.82E +113.12E +111.25E +114.07E +10f8MeanStd5.11E +151.99E +155.32E +151.78E +155.11E +141.54E +147.78E +171.66E +178.14E +172.11E +17f9MeanStd4.91E +092.00E +084.93E +092.05E +083.91E +081.56E +071.70E +091.57E +081.46E +091.99E +08f10MeanStd9.97E +072.51E +069.88E +072.43E +067.39E +061.76E +059.58E +072.31E +059.58E +072.56E +05f11MeanStd4.99E +141.21E +144.97E +081.36E +086.29E +072.87E +071.09E +141.23E +142.28E +121.13E +12f12MeanStd7.78E +113.18E +107.86E +113.27E +106.47E +111.63E +108.70E +114.64E +101.66E +111.23E +10f13MeanStd3.45E +097.01E +083.58E +097.18E +081.53E +144.53E +081.87E +161.84E +161.41E +141.99E +14f14MeanStd2.53E +091.59E +092.43E +091.35E +091.78E +095.83E +081.25E +157.00E +146.99E +132.05E +13f15Mean9.09E +132.49E +139.09E +132.50E +137.08E +132.50E +138.61E +132.39E +132.91E +112.81E +11StdOn fully separable functionsf1 and f2, each decomposition method decomposes the problems using the same FEs, so they achieve the same results. Because HPDG uses the least FEs for decomposing f3 and f6, both HPDG and TSD achieve the best scores. On the partly separable function f13, RDG and RDG2 achieve the best scores, because HPDG and ERDG do not decompose it correctly. The optimization results of DECC-TSD with grey background in Table 11 indicate better optimization grades compared to DECC-HPDG. In the first stage of TSD, HPDG does not reduce the dimension of the fully nonseparable function f15, and, in the second stage of TSD, KIDD detects that the dimension of f15 is high, so KIDD dynamically decomposes f15, and thus the optimization result of DECC-TSD is better than that of DECC-HPDG on f15. Similarly, the optimization result of DECC-TSD on f11 is better than that of DECC-HPDG. Although HPDG does not decompose f12 and f13 correctly, KIDD performs an effective dimension reduction of the subgroups in the optimization stage, so DECC-TSD has better grades.


## 4.1. Experimental Methodology

The performances of the decomposition methods were compared on the IEEE CEC’2010 and CEC’2013 special sessions on large-scale global optimization [42, 43]. The experiments in this paper were divided into two parts. In the first part, HPDG was compared with DG [24], DG2 [25], RDG [27], RDG2 [28], and ERDG [30] on problem decomposition. HPDG set ε as RDG did, and the values of α used to calculate ε are shown in Tables 1 and 2.Table 1
The values ofα in CEC’2013 special sessions on large-scale global optimization.
Ff1f2f3f4-f5f6f7-f8f9f10f11f12–f15α1.00e−121.00e−101.00e−141.00e−121.00e−151.00e−121.00e−141.00e−151.00e−161.00e−12Table 2
The values ofα in CEC’2010 special sessions on large-scale global optimization.
Ff1-f2f3f4-f5f6f7–f20α1.00e−121.00e−031.00e−121.00e−101.00e−20Three evaluation metrics were selected to evaluate the performance of the decomposition methods:(1)
The decomposition accuracy is calculated as [30]; decision variables that are corelated to each other are grouped into the same subgroup and the variables that are not corelated to each other are grouped into different subgroups. In the experimental tables, “separable” and “non-sep” columns represent the decomposition accuracy of separable and nonseparable variables, respectively.(2)
The number of function evaluations (FEs) is used to decompose the problem [42, 43].(3)
In this paper, the growth rate of FEs is introduced to evaluate the performance of decomposition methods on high-dimensional problems, as in the following equation:(10)gr=hdFEs−ldFEsldFEs×100%,where gr denotes the growth rate of FEs, and hdFEs and ldFEs denote the FEs of two different dimensional problems, respectively.In the second part, TSD and other decomposition methods embedded in DECC were compared on problem optimization. Adaptive differential evolution with optional external archive (JADE) [44] was used to optimize the problem in optimization stage. FEs are set to 3e + 6 as the termination condition for each run of the experiment [43]. The parameters of the decomposition methods and JADE were set as in their publications.


## 4.2. Decomposition Comparison

### 4.2.1. Comparison on Perturbation Strategy

In this section, we verify the effectiveness of UVP. As described in Table3, HPDS with UVP correctly decomposes the four test functions f3, f6, f7, and f10 and improves the decomposition accuracy on f8 and f11 compared with HPDS with fixed-value perturbation (FVP). That is because UVP applies perturbation of appropriate size when two sets of the variables interact, while the perturbation applied by FVP cannot satisfy the requirements of different problems.Table 3
Decomposition results of HPDG with UVP and FVP on 1000-dimensional CEC’2013 special sessions on large-scale global optimization. For each function, the best values of FEs and decomposition accuracy among different decomposition methods are shown in bold, respectively.
FHPDS with UVPHPDS with FVPFEsSeparableNon-sepFEsSeparableNon-sepf13008100.0%—3008100.0%—f23008100.0%—3008100.0%—f330080.0%—3008100.0%—f46704100.0%100.0%6704100.0%100.0%f58014100.0%0.0%8014100.0%0.0%f6108840.0%0.0%10884100.0%100.0%f766720.0%0.0%6672100.0%100.0%f88865—0.0%9506—20.0%f915367—100.0%13668—100.0%f1013988—0.0%14008—100.0%f1114298—0.0%14298—25.0%f125008—100.0%5008—100.0%f1313731—0.0%13804—0.0%f1413737—0.0%13388—0.0%f155008—100.0%5008—100.0%


### 4.2.2. Decomposition Results of HPDG and Other Decomposition Methods

Table4 summarizes the decomposition results on CEC’2013 special sessions on large-scale global optimization. HPDG correctly decomposes all functions except f5, f8, f11, f13, and f15. HPDG suffers from a flaw when detecting the indirect relationship between variables; if the shared variables are not grouped firstly, the indirect related variables cannot be grouped into the same subgroup. Although the number of functions correctly decomposed by HPDG is similar compared to DG2, RDG, and RDG2, HPDG uses fewer Fes; as shown in the last row of Table 3, HPDG correctly decomposes 7 functions using fewer FEs than other methods. HPDG uses the fewest FEs on 9 out of 15 functions; this is because HPDG has lower decomposition complexity compared to other methods.Table 4
Decomposition results on 1000-dimensional CEC’2013 special sessions on large-scale global optimization. For each function, the best values of FEs and decomposition accuracy among different decomposition methods are shown in bold, respectively. Total number indicates the number of functions that are correctly decomposed by each method using fewer FEs than other methods.
HPDGNon-sep———100.0%0.0%100.0%100.0%20.0%100.0%100.0%25.0%100.0%0.0%0.0%100.0%7Separable100.0%100.0%100.0%100.0%100.0%100.0%100.0%————————FEs3.01e +033.01e +033.01e +036.70e +038.01e +031.09e +046.67e +039.51e +031.37e +041.40e +041.43e +045.01e +031.38e +041.34e +045.01e +03RDG2Non-sep———100.0%100.0%100.0%100.0%80.0%100.0%100.0%100.0%100.0%0.0%100.0%100.0%2Separable100.0%100.0%0.0%100.0%100.0%0.0%100.0%————————FEs3.00e +033.00e +036.01e +039.83e +039.90e +031.16e +049.81e +031.94e +041.91e +041.99e +041.94e +045.09e +041.52e +041.61e +045.99e +03RDGNon-sep———100.0%100.0%91.0%0.0%70.0%100.0%86.0%0.0%100.0%0.0%100.0%100.0%1Separable100.0%100.0%0.0%100.0%100.0%4.0%27.0%————————FEs3.01e +033.01e +036.00e +039.84e +031.11e +041.40e +041.19e +041.97e +041.97e +042.00e +041.13e +045.09e +048.60e +039.54e +036.15e +03DG2Non-sep———100.0%100.0%100.0%50.0%80.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%0Separable100.0%100.0%0.0%5.4%100.0%0.0%100.0%————————FEs5.01e +055.01e +055.01e +055.01e +055.01e +055.01e +055.01e +055.01e +055.01e +055.01e +055.01e +055.01e +054.10e +054.10e +055.01e +05DGNon-sep———49.0%66.0%50.0%0.0%65.0%100.0%65.0%0.0%0.0%0.0%0.0%100.0%1Separable100.0%100.0%100.0%5.0%100.0%100.0%9.0%————————FEs1.00e +061.00e +061.00e +061.60e +045.31e +055.81e +051.27e +042.27e +041.77e +044.80e +049.88e +031.51e +055.97e +031.40e +042.00e +03Ff1f2f3456789101112131415Total number


### 4.2.3. Decomposition Results on High-Dimensional Functions

Since the structures of CEC’2013 special sessions on large-scale global optimization are fixed, the robustness of the decomposition methods is compared on extended high-dimensional CEC’2010 special sessions on large-scale global optimization. The extended high-dimensional CEC’2010 functions as the consistent set in the original CEC’2010 special sessions on large-scale global optimization [30].Tables5–9 summarize the decomposition results of the decomposition methods on 1000- to 5000-dimensional functions. Except for DG, each decomposition method has similar decomposition accuracy on the extended high-dimensional CEC’2010 functions, and all can decompose most of them correctly, but the FEs are significantly different. As the dimension grows, FEs used by DG and DG2 increase the most, RDG and RDG2 follow, and ERDG and HPDG are the best. That is because the complexity of DG and DG2 is On2 [24, 25], and the complexity of RDG and RDG2 is Onlogn [27, 28]. Table 10 summarizes the growth rates of FEs used by RDG, ERDG, and HPDG, which are calculated by equation (10). The least growth of FEs is used by ERDG and HPDG; this is because ERDG uses the historical information of variable interactions to avoid examining some interrelationship between variables [30], and the complexity of HPDG is Onlogm, which is the lowest. The FEs used by HPDG and ERDG are comparable. As described in Table 10, the growth rate of FEs used by HPDG is slightly better than that of ERDG.Table 5
Decomposition results on 1000-dimesnional CEC’2010 special sessions on large-scale global optimization. For each function, the best values of FEs and decomposition accuracy among different decomposition methods are shown in bold font, respectively.
HPDGNon-sep———100.0%100.0%100.0%100.0%0.0%100.0%100.0%100.0%100.0%0.0%100.0%100.0%100.0%100.0%0.0%100.0%100.0%Separable100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%0.0%100.0%100.0%———————FEs3.01e +033.01e +033.01e +035.01e +035.01e +035.01e +035.01e +035.26e +038.31e +038.31e +031.23e +048.31e +039.75e +031.36e +041.36e +041.36e +041.36e +041.59e +045.01e +035.01e +03RDG2Non-sep———100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%Separable100.0%100.0%0.0%100.0%100.0%0.0%100.0%100.0%100.0%100.0%0.0%100.0%100.0%———————FEs3.00e +033.00e +035.99e +034.29e +034.24e +038.56e +034.22e +035.60e +031.04e +041.40e +041.37e +041.43e +042.92e +042.06e +042.05e +042.09e +042.08e +044.99e +045.99e +035.09e +04RDGNon-sep———100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%Separable100.0%100.0%0.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%0.0%100.0%100.0%———————FEs3.01e +033.01e +036.00e +034.21e +034.15e +035.10e +044.23e +035.61e +031.43e +041.40e +041.37e +041.43e +042.92e +042.06e +042.05e +042.09e +042.08e +044.99e +046.00e +035.09e +04DG2Non-sep———100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%Separable100.0%100.0%0.0%100.0%100.0%8.6%100.0%100.0%100.0%100.0%8.6%100.0%100.0%———————FEs5.01e +055.01e +055.01e +055.01e +055.01e +055.01e +055.01e +055.01e +055.01e +055.01e +055.01e +055.01e +055.01e +055.01e +055.01e +055.01e +055.01e +055.01e +055.01e +055.01e +05DGNon-sep———100.0%100.0%100.0%0.0%0.0%100.0%100.0%90.0%100.0%0.0%100.0%100.0%80.0%100.0%0.0%100.0%0.0%Separable100.0%100.0%100.0%3.5%100.0%100.0%26.1%14.0%100.0%100.0%100.0%100.0%21.4%———————FEs1.00e +061.00e +061.00e +061.46e +049.06e +059.06e +056.77e +042.33e +042.71e +052.73e +052.71e +052.71e +055.03e +0420e +0442.10e +042.11e +042.10e +043.96e +042.00e +031.55e +05Ff1f2f3f4f5f6f7f8f9f10f11f12f13f14f15f16f17f18f19f20Table 6
Decomposition results on 2000-dimensiional CEC’2010 special sessions on large-scale global optimization. For each function, the best values of FEs and decomposition accuracy among different decomposition methods are shown in bold, respectively.
HPDGNon-sep———100.0%100.0%100.0%100.0%0.0%100.0%100.0%100.0%100.0%0.0%100.0%100.0%100.0%100.0%0.0%100.0%100.0%Separable100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%0.0%100.0%100.0%———————FEs6.01e +036.01e +036.01e +039.97e +039.97e +039.97e +039.97e +031.02e +041.86e +041.86e +042.88e +041.86e +042.07e +043.11e +043.11e +043.11e +043.11e +043.42e +041.00e +041.11e +04RDG2Non-sep———100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%Separable100.0%100.0%0.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%0.0%100.0%100.0%———————FEs6.00e +036.00e +031.20e +047.43e +037.58e +032.21e +067.45e +039.06e +033.36e +043.34e +043.08e +043.34e +046.44e +045.08e +045.21e +045.11e +035.18e +041.12e +051.20e +041.14e +05RDGNon-sep———100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%Separable100.0%100.0%0.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%0.0%100.0%100.0%———————FEs6.01e +036.01e +031.20e +047.44e +037.54e +035.32e +047.46e +039.07e +033.36e +043.34e +043.08e +043.34e +046.44e +045.08e +045.21e +045.11e +045.19e +041.12e +051.20e +041.14e +05DG2Non-sep———100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%Separable100.0%100.0%0.0%100.0%100.0%22.1%100.0%100.0%100.0%100.0%0.0%100.0%100.0%———————FEs2.00e +062.00e +062.00e +062.00e +062.00e +062.00e +062.00e +062.00e +062.00e +062.00e +062.00e +062.00e +062.00e +062.00e +062.00e +062.00e +062.00e +062.00e +062.00e +062.00e +06DGNon-sep———0.0100.0%100.0%100.0%0.0%100.0%100.0%85.0%100.0%0.0%100.0%100.0%87.5%100.0%0.0%100.0%0.0%Separable100.0%100.0%100.0%3.0%100.0%100.0%5.0%4.0%100.0%100.0%100.0%100.0%18.4%———————FEs4.00e +064.00e +064.00e +063.34e +043.81e +063.81e +063.20e +042.80e +041.10e +061.10e +061.10e +061.09e +061.38e +058.20e +048.20e +048.23e +048.20e +041.82e +054.00e +035.83e +05Ff1f2f3f4f5f6f7f8f9f10f11f12f13f14f15f16f17f18f19f20Table 7
Decomposition results on 3000-dimensional CEC'2010 special sessions on large-scale global optimization. For each function, the best values of FEs and decomposition accuracy among different decomposition methods are shown in bold, respectively.
HPDGNon-sep———100.0%100.0%100.0%100.0%0.0%100.0%100.0%100.0%100.0%0.0%100.0%100.0%100.0%100.0%0.0%100.0%100.0%Separable100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%0.0%100.0%100.0%———————FEs9.01e +039.01e +039.01e +031.47e +041.47e +041.47e +041.47e +041.50e +042.95e +042.95e +044.45e +042.95e +043.22e +044.98e +044.98e +044.98e +044.98e +045.34e +041.50e +041.50e +04RDG2Non-sep———100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%Separable100.0%100.0%0.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%0.0%100.0%100.0%———————FEs9.00e +039.00e +031.80e +041.06e +041.06e +041.84e +061.05e +041.20e +045.48e +045.51e +045.06e +045.52e +041.01e +058.62e +048.66e +048.59e +048.63e +041.77e +051.80e +041.82e +05RDGNon-sep———100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%Separable100.0%100.0%0.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%0.0%100.0%100.0%———————FEs9.01e +039.01e +031.80e +041.06e +041.06e +046.03e +041.05e +041.20e +045.49e +045.51e +045.09e +045.52e +041.01e +058.62e +048.66e +048.59e +048.63e +041.77e +051.80e +041.82e +05DG2Non-sep———100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%Separable100.0%100.0%0.0%100.0%100.0%8.3%100.0%100.0%100.0%100.0%0.0%100.0%100.0%———————FEs4.50e +064.50e +064.50e +064.50e +064.50e +064.50e +064.50e +064.50e +064.50e +064.50e +064.50e +064.50e +064.50e +064.50e +064.50e +064.50e +064.50e +064.50e +064.50e +064.50e +06DGNon-sep———0.0%100.0%100.0%0.0%0.0%100.0%100.0%70.0%100.0%0.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%Separable100.0%100.0%100.0%3.0%100.0%100.0%17.0%4.0%100.0%100.0%100.0%100.0%5.0%———————FEs9.00e +069.00e +069.00e +063.76e +048.71e +068.71e +062.74e +053.87e +042.45e +062.48e +062.53e +062.49e +069.50e +041.83e +051.83e +051.84e +051.83e +052.47e +056.00e +035.39e +05Ff1f2f3f4f5f6f7f8f9f10f11f12f13f14f15f16f17f18f19f20Table 8
Decomposition results on 4000-dimensional CEC'2010 special sessions on large-scale global optimization. For each function, the best values of FEs and decomposition accuracy among different decomposition methods are shown in bold, respectively.
HPDGNon-sep———100.0%100.0%100.0%100.0%0.0%100.0%100.0%100.0%100.0%0.0%100.0%100.0%100.0%100.0%0.0%100.0%100.0%Separable100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%0.0%100.0%100.0%———————FEs1.20e +041.20e +041.20e +042.00e +042.00e +042.00e +042.00e +042.02e +044.11e +044.11e +046.52e +044.11e +044.46e +047.00e +047.00e +047.00e +047.00e +047.45e +042.00e +042.00e +04RDG2Non-sep———100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%Separable100.0%100.0%0.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%0.0%100.0%100.0%———————FEs1.20e +041.20e +042.40e +041.38e +041.38e +041.55e +061.38e +041.54e +047.81e +047.79e +047.20e +047.80e +041.41e +051.24e +051.24e +051.23e +051.23e +052.44e +052.40e +042.51e +05RDGNon-sep———100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%Separable100.0%100.0%0.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%0.0%100.0%100.0%———————FEs1.20e +041.20e +042.40e +041.39e +041.38e +046.41e +041.38e +041.54e +057.81e +047.79e +047.29e +047.80e +041.41e +051.24e +051.24e +051.23e +051.23e +052.44e +052.40e +042.51e +05DG2Non-sep———100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%Separable100.0%100.0%0.0%100.0%100.0%15.7%100.0%100.0%100.0%99.8%0.0%100.0%100.0%———————FEs8.00e +068.00e +068.00e +068.00e +068.00e +068.00e +068.00e +068.00e +068.00e +068.00e +068.00e +068.00e +068.00e +068.00e +068.00e +068.00e +068.00e +068.00e +068.00e +068.00e +06DGNon-sep———0.0%100.0%100.0%100.0%0.0%100.0%100.0%85.0%100.0%0.0%100.0%100.0%86.5%100.0%0.0%100.0%0.0%Separable100.0%100.0%100.0%3.5%100.0%100.0%20.0%32.0%100.0%100.0%100.0%100.0%10.0%———————FEs1.60e +071.60e +071.60e +072.87e +041.56e +071.56e +075.54e +051.49e +064.36e +064.39e +064.39e +064.41e +063.29e +058.72e +043.24e +053.26e +053.24e +055.20e +058.00e +031.72e +06Ff1f2f3f4f5f6f7f8f9f10f11f12f13f14f15f16f17f18f19f20Table 9
Decomposition results on 5000-dimensional CEC'2010 special sessions on large-scale global optimization. For each function, the best values of FEs and decomposition accuracy among different decomposition methods are shown in bold, respectively.
HPDGNon-sep———100.0%100.0%100.0%100.0%0.0%100.0%100.0%100.0%100.0%0.0%100.0%100.0%100.0%100.0%0.0%100.0%100.0%Separable100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%0.0%100.0%100.0%———————FEs1.50e +041.50e +041.50e +042.50e +042.50e +042.50e +042.50e +042.52e +045.29e +045.29e +048.30e +045.29e +045.67e +049.07e +049.07e +049.07e +049.07e +049.47e +042.50e +042.50e +04RDG2Non-sep———100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%Separable100.0%100.0%0.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%0.0%100.0%100.0%———————FEs1.50e +041.50e +042.40e +041.68e +041.70e +041.44e +061.68e +041.83e +041.02e +051.02e +059.42e +041.02e +051.82e +051.63e +051.63e +051.64e +051.64e +053.18e +053.00e +043.26e +05RDGNon-sep———100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%Separable100.0%100.0%0.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%0.0%100.0%100.0%———————FEs1.50e +041.50e +043.01e +041.68e +041.70e +047.05e +041.68e +041.83e +041.02e +051.02e +059.42e +041.02e +051.82e +051.63e +051.63e +051.64e +051.64e +053.18e +053.00e +043.26e +05DG2Non-sep———100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%Separable100.0%100.0%0.0%100.0%100.0%8.3%100.0%100.0%100.0%100.0%0.0%100.0%100.0%———————FEs1.25e +071.25e +071.25e +071.25e +071.25e +071.25e +071.25e +071.25e +071.25e +071.25e +071.25e +071.25e +071.25e +071.25e +071.25e +071.25e +071.25e +071.25e +071.25e +071.25e +07DGNon-sep———0.0%100.0%100.0%0.0%0.0%100.0%100.0%74.0%100.0%0.0%100.0%100.0%80.0%100.0%0.0%100.0%0.0%Separable100.0%100.0%100.0%2.0%100.0%100.0%31.1%3.8%100.0%100.0%100.0%100.0%12.6%———————FEs2.48e +072.50e +072.50e +076.05e +042.45e +072.45e +072.44e +068.95e +046.97e +066.87e +066.95e +066.89e +065.95e +055.05e +055.05e +055.11e +055.05e +059.82e +051.00e +041.14e +06Ff1f2f3f4f5f6f7f8f9f10f11f12f13f14f15f16f17f18f19f20Table 10
The average growth rates of FEs off1, f2, f4, f5, f7, f10, f12, f13, f14, f15, f16, f17, f18, f19, and f20 on CEC’2010 special sessions on large-scale global optimization. The best growth rates of FEs are shown in bold font.
Decomposition methodRDG (%)ERDG (%)HPDG (%)D = 1000 to D = 2000124.1116.114.4D = 2000 to D = 300057.157.154.2D = 3000 to D = 400037.736.737.2D = 4000 to D = 500028.029.327.1


## 4.2.1. Comparison on Perturbation Strategy

In this section, we verify the effectiveness of UVP. As described in Table3, HPDS with UVP correctly decomposes the four test functions f3, f6, f7, and f10 and improves the decomposition accuracy on f8 and f11 compared with HPDS with fixed-value perturbation (FVP). That is because UVP applies perturbation of appropriate size when two sets of the variables interact, while the perturbation applied by FVP cannot satisfy the requirements of different problems.Table 3
Decomposition results of HPDG with UVP and FVP on 1000-dimensional CEC’2013 special sessions on large-scale global optimization. For each function, the best values of FEs and decomposition accuracy among different decomposition methods are shown in bold, respectively.
FHPDS with UVPHPDS with FVPFEsSeparableNon-sepFEsSeparableNon-sepf13008100.0%—3008100.0%—f23008100.0%—3008100.0%—f330080.0%—3008100.0%—f46704100.0%100.0%6704100.0%100.0%f58014100.0%0.0%8014100.0%0.0%f6108840.0%0.0%10884100.0%100.0%f766720.0%0.0%6672100.0%100.0%f88865—0.0%9506—20.0%f915367—100.0%13668—100.0%f1013988—0.0%14008—100.0%f1114298—0.0%14298—25.0%f125008—100.0%5008—100.0%f1313731—0.0%13804—0.0%f1413737—0.0%13388—0.0%f155008—100.0%5008—100.0%


## 4.2.2. Decomposition Results of HPDG and Other Decomposition Methods

Table4 summarizes the decomposition results on CEC’2013 special sessions on large-scale global optimization. HPDG correctly decomposes all functions except f5, f8, f11, f13, and f15. HPDG suffers from a flaw when detecting the indirect relationship between variables; if the shared variables are not grouped firstly, the indirect related variables cannot be grouped into the same subgroup. Although the number of functions correctly decomposed by HPDG is similar compared to DG2, RDG, and RDG2, HPDG uses fewer Fes; as shown in the last row of Table 3, HPDG correctly decomposes 7 functions using fewer FEs than other methods. HPDG uses the fewest FEs on 9 out of 15 functions; this is because HPDG has lower decomposition complexity compared to other methods.Table 4
Decomposition results on 1000-dimensional CEC’2013 special sessions on large-scale global optimization. For each function, the best values of FEs and decomposition accuracy among different decomposition methods are shown in bold, respectively. Total number indicates the number of functions that are correctly decomposed by each method using fewer FEs than other methods.
HPDGNon-sep———100.0%0.0%100.0%100.0%20.0%100.0%100.0%25.0%100.0%0.0%0.0%100.0%7Separable100.0%100.0%100.0%100.0%100.0%100.0%100.0%————————FEs3.01e +033.01e +033.01e +036.70e +038.01e +031.09e +046.67e +039.51e +031.37e +041.40e +041.43e +045.01e +031.38e +041.34e +045.01e +03RDG2Non-sep———100.0%100.0%100.0%100.0%80.0%100.0%100.0%100.0%100.0%0.0%100.0%100.0%2Separable100.0%100.0%0.0%100.0%100.0%0.0%100.0%————————FEs3.00e +033.00e +036.01e +039.83e +039.90e +031.16e +049.81e +031.94e +041.91e +041.99e +041.94e +045.09e +041.52e +041.61e +045.99e +03RDGNon-sep———100.0%100.0%91.0%0.0%70.0%100.0%86.0%0.0%100.0%0.0%100.0%100.0%1Separable100.0%100.0%0.0%100.0%100.0%4.0%27.0%————————FEs3.01e +033.01e +036.00e +039.84e +031.11e +041.40e +041.19e +041.97e +041.97e +042.00e +041.13e +045.09e +048.60e +039.54e +036.15e +03DG2Non-sep———100.0%100.0%100.0%50.0%80.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%0Separable100.0%100.0%0.0%5.4%100.0%0.0%100.0%————————FEs5.01e +055.01e +055.01e +055.01e +055.01e +055.01e +055.01e +055.01e +055.01e +055.01e +055.01e +055.01e +054.10e +054.10e +055.01e +05DGNon-sep———49.0%66.0%50.0%0.0%65.0%100.0%65.0%0.0%0.0%0.0%0.0%100.0%1Separable100.0%100.0%100.0%5.0%100.0%100.0%9.0%————————FEs1.00e +061.00e +061.00e +061.60e +045.31e +055.81e +051.27e +042.27e +041.77e +044.80e +049.88e +031.51e +055.97e +031.40e +042.00e +03Ff1f2f3456789101112131415Total number


## 4.2.3. Decomposition Results on High-Dimensional Functions

Since the structures of CEC’2013 special sessions on large-scale global optimization are fixed, the robustness of the decomposition methods is compared on extended high-dimensional CEC’2010 special sessions on large-scale global optimization. The extended high-dimensional CEC’2010 functions as the consistent set in the original CEC’2010 special sessions on large-scale global optimization [30].Tables5–9 summarize the decomposition results of the decomposition methods on 1000- to 5000-dimensional functions. Except for DG, each decomposition method has similar decomposition accuracy on the extended high-dimensional CEC’2010 functions, and all can decompose most of them correctly, but the FEs are significantly different. As the dimension grows, FEs used by DG and DG2 increase the most, RDG and RDG2 follow, and ERDG and HPDG are the best. That is because the complexity of DG and DG2 is On2 [24, 25], and the complexity of RDG and RDG2 is Onlogn [27, 28]. Table 10 summarizes the growth rates of FEs used by RDG, ERDG, and HPDG, which are calculated by equation (10). The least growth of FEs is used by ERDG and HPDG; this is because ERDG uses the historical information of variable interactions to avoid examining some interrelationship between variables [30], and the complexity of HPDG is Onlogm, which is the lowest. The FEs used by HPDG and ERDG are comparable. As described in Table 10, the growth rate of FEs used by HPDG is slightly better than that of ERDG.Table 5
Decomposition results on 1000-dimesnional CEC’2010 special sessions on large-scale global optimization. For each function, the best values of FEs and decomposition accuracy among different decomposition methods are shown in bold font, respectively.
HPDGNon-sep———100.0%100.0%100.0%100.0%0.0%100.0%100.0%100.0%100.0%0.0%100.0%100.0%100.0%100.0%0.0%100.0%100.0%Separable100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%0.0%100.0%100.0%———————FEs3.01e +033.01e +033.01e +035.01e +035.01e +035.01e +035.01e +035.26e +038.31e +038.31e +031.23e +048.31e +039.75e +031.36e +041.36e +041.36e +041.36e +041.59e +045.01e +035.01e +03RDG2Non-sep———100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%Separable100.0%100.0%0.0%100.0%100.0%0.0%100.0%100.0%100.0%100.0%0.0%100.0%100.0%———————FEs3.00e +033.00e +035.99e +034.29e +034.24e +038.56e +034.22e +035.60e +031.04e +041.40e +041.37e +041.43e +042.92e +042.06e +042.05e +042.09e +042.08e +044.99e +045.99e +035.09e +04RDGNon-sep———100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%Separable100.0%100.0%0.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%0.0%100.0%100.0%———————FEs3.01e +033.01e +036.00e +034.21e +034.15e +035.10e +044.23e +035.61e +031.43e +041.40e +041.37e +041.43e +042.92e +042.06e +042.05e +042.09e +042.08e +044.99e +046.00e +035.09e +04DG2Non-sep———100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%Separable100.0%100.0%0.0%100.0%100.0%8.6%100.0%100.0%100.0%100.0%8.6%100.0%100.0%———————FEs5.01e +055.01e +055.01e +055.01e +055.01e +055.01e +055.01e +055.01e +055.01e +055.01e +055.01e +055.01e +055.01e +055.01e +055.01e +055.01e +055.01e +055.01e +055.01e +055.01e +05DGNon-sep———100.0%100.0%100.0%0.0%0.0%100.0%100.0%90.0%100.0%0.0%100.0%100.0%80.0%100.0%0.0%100.0%0.0%Separable100.0%100.0%100.0%3.5%100.0%100.0%26.1%14.0%100.0%100.0%100.0%100.0%21.4%———————FEs1.00e +061.00e +061.00e +061.46e +049.06e +059.06e +056.77e +042.33e +042.71e +052.73e +052.71e +052.71e +055.03e +0420e +0442.10e +042.11e +042.10e +043.96e +042.00e +031.55e +05Ff1f2f3f4f5f6f7f8f9f10f11f12f13f14f15f16f17f18f19f20Table 6
Decomposition results on 2000-dimensiional CEC’2010 special sessions on large-scale global optimization. For each function, the best values of FEs and decomposition accuracy among different decomposition methods are shown in bold, respectively.
HPDGNon-sep———100.0%100.0%100.0%100.0%0.0%100.0%100.0%100.0%100.0%0.0%100.0%100.0%100.0%100.0%0.0%100.0%100.0%Separable100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%0.0%100.0%100.0%———————FEs6.01e +036.01e +036.01e +039.97e +039.97e +039.97e +039.97e +031.02e +041.86e +041.86e +042.88e +041.86e +042.07e +043.11e +043.11e +043.11e +043.11e +043.42e +041.00e +041.11e +04RDG2Non-sep———100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%Separable100.0%100.0%0.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%0.0%100.0%100.0%———————FEs6.00e +036.00e +031.20e +047.43e +037.58e +032.21e +067.45e +039.06e +033.36e +043.34e +043.08e +043.34e +046.44e +045.08e +045.21e +045.11e +035.18e +041.12e +051.20e +041.14e +05RDGNon-sep———100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%Separable100.0%100.0%0.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%0.0%100.0%100.0%———————FEs6.01e +036.01e +031.20e +047.44e +037.54e +035.32e +047.46e +039.07e +033.36e +043.34e +043.08e +043.34e +046.44e +045.08e +045.21e +045.11e +045.19e +041.12e +051.20e +041.14e +05DG2Non-sep———100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%Separable100.0%100.0%0.0%100.0%100.0%22.1%100.0%100.0%100.0%100.0%0.0%100.0%100.0%———————FEs2.00e +062.00e +062.00e +062.00e +062.00e +062.00e +062.00e +062.00e +062.00e +062.00e +062.00e +062.00e +062.00e +062.00e +062.00e +062.00e +062.00e +062.00e +062.00e +062.00e +06DGNon-sep———0.0100.0%100.0%100.0%0.0%100.0%100.0%85.0%100.0%0.0%100.0%100.0%87.5%100.0%0.0%100.0%0.0%Separable100.0%100.0%100.0%3.0%100.0%100.0%5.0%4.0%100.0%100.0%100.0%100.0%18.4%———————FEs4.00e +064.00e +064.00e +063.34e +043.81e +063.81e +063.20e +042.80e +041.10e +061.10e +061.10e +061.09e +061.38e +058.20e +048.20e +048.23e +048.20e +041.82e +054.00e +035.83e +05Ff1f2f3f4f5f6f7f8f9f10f11f12f13f14f15f16f17f18f19f20Table 7
Decomposition results on 3000-dimensional CEC'2010 special sessions on large-scale global optimization. For each function, the best values of FEs and decomposition accuracy among different decomposition methods are shown in bold, respectively.
HPDGNon-sep———100.0%100.0%100.0%100.0%0.0%100.0%100.0%100.0%100.0%0.0%100.0%100.0%100.0%100.0%0.0%100.0%100.0%Separable100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%0.0%100.0%100.0%———————FEs9.01e +039.01e +039.01e +031.47e +041.47e +041.47e +041.47e +041.50e +042.95e +042.95e +044.45e +042.95e +043.22e +044.98e +044.98e +044.98e +044.98e +045.34e +041.50e +041.50e +04RDG2Non-sep———100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%Separable100.0%100.0%0.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%0.0%100.0%100.0%———————FEs9.00e +039.00e +031.80e +041.06e +041.06e +041.84e +061.05e +041.20e +045.48e +045.51e +045.06e +045.52e +041.01e +058.62e +048.66e +048.59e +048.63e +041.77e +051.80e +041.82e +05RDGNon-sep———100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%Separable100.0%100.0%0.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%0.0%100.0%100.0%———————FEs9.01e +039.01e +031.80e +041.06e +041.06e +046.03e +041.05e +041.20e +045.49e +045.51e +045.09e +045.52e +041.01e +058.62e +048.66e +048.59e +048.63e +041.77e +051.80e +041.82e +05DG2Non-sep———100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%Separable100.0%100.0%0.0%100.0%100.0%8.3%100.0%100.0%100.0%100.0%0.0%100.0%100.0%———————FEs4.50e +064.50e +064.50e +064.50e +064.50e +064.50e +064.50e +064.50e +064.50e +064.50e +064.50e +064.50e +064.50e +064.50e +064.50e +064.50e +064.50e +064.50e +064.50e +064.50e +06DGNon-sep———0.0%100.0%100.0%0.0%0.0%100.0%100.0%70.0%100.0%0.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%Separable100.0%100.0%100.0%3.0%100.0%100.0%17.0%4.0%100.0%100.0%100.0%100.0%5.0%———————FEs9.00e +069.00e +069.00e +063.76e +048.71e +068.71e +062.74e +053.87e +042.45e +062.48e +062.53e +062.49e +069.50e +041.83e +051.83e +051.84e +051.83e +052.47e +056.00e +035.39e +05Ff1f2f3f4f5f6f7f8f9f10f11f12f13f14f15f16f17f18f19f20Table 8
Decomposition results on 4000-dimensional CEC'2010 special sessions on large-scale global optimization. For each function, the best values of FEs and decomposition accuracy among different decomposition methods are shown in bold, respectively.
HPDGNon-sep———100.0%100.0%100.0%100.0%0.0%100.0%100.0%100.0%100.0%0.0%100.0%100.0%100.0%100.0%0.0%100.0%100.0%Separable100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%0.0%100.0%100.0%———————FEs1.20e +041.20e +041.20e +042.00e +042.00e +042.00e +042.00e +042.02e +044.11e +044.11e +046.52e +044.11e +044.46e +047.00e +047.00e +047.00e +047.00e +047.45e +042.00e +042.00e +04RDG2Non-sep———100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%Separable100.0%100.0%0.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%0.0%100.0%100.0%———————FEs1.20e +041.20e +042.40e +041.38e +041.38e +041.55e +061.38e +041.54e +047.81e +047.79e +047.20e +047.80e +041.41e +051.24e +051.24e +051.23e +051.23e +052.44e +052.40e +042.51e +05RDGNon-sep———100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%Separable100.0%100.0%0.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%0.0%100.0%100.0%———————FEs1.20e +041.20e +042.40e +041.39e +041.38e +046.41e +041.38e +041.54e +057.81e +047.79e +047.29e +047.80e +041.41e +051.24e +051.24e +051.23e +051.23e +052.44e +052.40e +042.51e +05DG2Non-sep———100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%Separable100.0%100.0%0.0%100.0%100.0%15.7%100.0%100.0%100.0%99.8%0.0%100.0%100.0%———————FEs8.00e +068.00e +068.00e +068.00e +068.00e +068.00e +068.00e +068.00e +068.00e +068.00e +068.00e +068.00e +068.00e +068.00e +068.00e +068.00e +068.00e +068.00e +068.00e +068.00e +06DGNon-sep———0.0%100.0%100.0%100.0%0.0%100.0%100.0%85.0%100.0%0.0%100.0%100.0%86.5%100.0%0.0%100.0%0.0%Separable100.0%100.0%100.0%3.5%100.0%100.0%20.0%32.0%100.0%100.0%100.0%100.0%10.0%———————FEs1.60e +071.60e +071.60e +072.87e +041.56e +071.56e +075.54e +051.49e +064.36e +064.39e +064.39e +064.41e +063.29e +058.72e +043.24e +053.26e +053.24e +055.20e +058.00e +031.72e +06Ff1f2f3f4f5f6f7f8f9f10f11f12f13f14f15f16f17f18f19f20Table 9
Decomposition results on 5000-dimensional CEC'2010 special sessions on large-scale global optimization. For each function, the best values of FEs and decomposition accuracy among different decomposition methods are shown in bold, respectively.
HPDGNon-sep———100.0%100.0%100.0%100.0%0.0%100.0%100.0%100.0%100.0%0.0%100.0%100.0%100.0%100.0%0.0%100.0%100.0%Separable100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%0.0%100.0%100.0%———————FEs1.50e +041.50e +041.50e +042.50e +042.50e +042.50e +042.50e +042.52e +045.29e +045.29e +048.30e +045.29e +045.67e +049.07e +049.07e +049.07e +049.07e +049.47e +042.50e +042.50e +04RDG2Non-sep———100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%Separable100.0%100.0%0.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%0.0%100.0%100.0%———————FEs1.50e +041.50e +042.40e +041.68e +041.70e +041.44e +061.68e +041.83e +041.02e +051.02e +059.42e +041.02e +051.82e +051.63e +051.63e +051.64e +051.64e +053.18e +053.00e +043.26e +05RDGNon-sep———100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%Separable100.0%100.0%0.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%0.0%100.0%100.0%———————FEs1.50e +041.50e +043.01e +041.68e +041.70e +047.05e +041.68e +041.83e +041.02e +051.02e +059.42e +041.02e +051.82e +051.63e +051.63e +051.64e +051.64e +053.18e +053.00e +043.26e +05DG2Non-sep———100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%100.0%Separable100.0%100.0%0.0%100.0%100.0%8.3%100.0%100.0%100.0%100.0%0.0%100.0%100.0%———————FEs1.25e +071.25e +071.25e +071.25e +071.25e +071.25e +071.25e +071.25e +071.25e +071.25e +071.25e +071.25e +071.25e +071.25e +071.25e +071.25e +071.25e +071.25e +071.25e +071.25e +07DGNon-sep———0.0%100.0%100.0%0.0%0.0%100.0%100.0%74.0%100.0%0.0%100.0%100.0%80.0%100.0%0.0%100.0%0.0%Separable100.0%100.0%100.0%2.0%100.0%100.0%31.1%3.8%100.0%100.0%100.0%100.0%12.6%———————FEs2.48e +072.50e +072.50e +076.05e +042.45e +072.45e +072.44e +068.95e +046.97e +066.87e +066.95e +066.89e +065.95e +055.05e +055.05e +055.11e +055.05e +059.82e +051.00e +041.14e +06Ff1f2f3f4f5f6f7f8f9f10f11f12f13f14f15f16f17f18f19f20Table 10
The average growth rates of FEs off1, f2, f4, f5, f7, f10, f12, f13, f14, f15, f16, f17, f18, f19, and f20 on CEC’2010 special sessions on large-scale global optimization. The best growth rates of FEs are shown in bold font.
Decomposition methodRDG (%)ERDG (%)HPDG (%)D = 1000 to D = 2000124.1116.114.4D = 2000 to D = 300057.157.154.2D = 3000 to D = 400037.736.737.2D = 4000 to D = 500028.029.327.1


## 4.3. Optimization Results of CC with Decomposition Methods

Table11 summarizes the optimization results of the decomposition methods being embedded in DECC [24]. The DECC-TSD proposed in this paper achieves the best optimization results on six functions. Compared with the state-of-the-art DECC-ERDG, DECC-TSD is more advantageous on the fully nonseparable function f15. Therefore, DECC-TSD alleviates the dilemma of CC with static decomposition in solving the fully nonseparable problems.Table 11
The optimization results on CEC’2013 special sessions on large-scale global optimization,D = 1000. Average fitness values and deviations on CEC’2013 special sessions on large-scale global optimization over 25 independent results. The significantly best results are in bold (Wilcoxon test with home p value correction, α = 0.05).
FDECC-RDGDECC-RDG2DECC-ERDGDECC-HPDGDECC-TSDf1MeanStd3.66E +111.24E +103.66E +111.28E +103.41E +111.22E +103.68E +111.85E +103.69E +111.36E +10f2MeanStd1.34E +054.43E +031.36E +054.39E +031.44E +054.40E +031.20E +053.67E +031.21E +053.55E +03f3MeanStd3.42E +015.31E − 033.73E +01556E − 033.41E +015.41E − 032.17E +017.14E − 032.16E +016.84E − 03f4MeanStd4.53E +121.98E +114.33E +121.75E +114.13E +121.27E +111.89E +124.22E +113.33E +125.36E +11f5MeanStd5.21E +074.32E +065.28E +074.35E +061.21E +072.12E +062.83E +072.34E +063.24E +072.97E +06f6MeanStd1.10E +061.21E +021.13E +061.19E +029.98E +061.31E +021.07E +069.58E +021.07E +067.87E +02f7MeanStd6.12E +113.01E +116.31E +113.10E +111.12E +112.47E +112.82E +113.12E +111.25E +114.07E +10f8MeanStd5.11E +151.99E +155.32E +151.78E +155.11E +141.54E +147.78E +171.66E +178.14E +172.11E +17f9MeanStd4.91E +092.00E +084.93E +092.05E +083.91E +081.56E +071.70E +091.57E +081.46E +091.99E +08f10MeanStd9.97E +072.51E +069.88E +072.43E +067.39E +061.76E +059.58E +072.31E +059.58E +072.56E +05f11MeanStd4.99E +141.21E +144.97E +081.36E +086.29E +072.87E +071.09E +141.23E +142.28E +121.13E +12f12MeanStd7.78E +113.18E +107.86E +113.27E +106.47E +111.63E +108.70E +114.64E +101.66E +111.23E +10f13MeanStd3.45E +097.01E +083.58E +097.18E +081.53E +144.53E +081.87E +161.84E +161.41E +141.99E +14f14MeanStd2.53E +091.59E +092.43E +091.35E +091.78E +095.83E +081.25E +157.00E +146.99E +132.05E +13f15Mean9.09E +132.49E +139.09E +132.50E +137.08E +132.50E +138.61E +132.39E +132.91E +112.81E +11StdOn fully separable functionsf1 and f2, each decomposition method decomposes the problems using the same FEs, so they achieve the same results. Because HPDG uses the least FEs for decomposing f3 and f6, both HPDG and TSD achieve the best scores. On the partly separable function f13, RDG and RDG2 achieve the best scores, because HPDG and ERDG do not decompose it correctly. The optimization results of DECC-TSD with grey background in Table 11 indicate better optimization grades compared to DECC-HPDG. In the first stage of TSD, HPDG does not reduce the dimension of the fully nonseparable function f15, and, in the second stage of TSD, KIDD detects that the dimension of f15 is high, so KIDD dynamically decomposes f15, and thus the optimization result of DECC-TSD is better than that of DECC-HPDG on f15. Similarly, the optimization result of DECC-TSD on f11 is better than that of DECC-HPDG. Although HPDG does not decompose f12 and f13 correctly, KIDD performs an effective dimension reduction of the subgroups in the optimization stage, so DECC-TSD has better grades.


## 5. Conclusions

In this paper, we propose a TSD to improve the performance of CC in solving LSGO problems. In the first stage of TSD, HPDG is proposed, which provides a variable detection structure HPDS with very low complexity to decompose problems, and the UVP is proposed for HPDS to improve the decomposition accuracy. HPDG further reduces the FEs used to decompose the LSGO problems. In the second stage of TSD, KIDD decomposes the subgroups with high dimension based on the decomposition information of HPDG. TSD alleviates the dilemma of CC with static decomposition in solving fully nonseparable problems and reducing the computational cost of decomposition methods.In future work, we plan to further improve the decomposition accuracy of HPDG and research new algorithms to solve fully nonseparable LSGO problems.



---

*Source: 2653807-2021-10-29.xml*