Cooperative coevolutionary hybrid NSGA-II with Linkage Measurement Minimization for Large-scale Multi-objective optimization

Multi-objective evolutionary algorithms (MOEAs) have successfully solved various multi-objective problems[1]. However, the performance of the traditional MOEAs degrades dramatically as the dimension of the problem increases. When the scale of the problem reaches a certain dimension, this type of problem is called large-scale multi-objective optimization problems (LSMOPs). Solving LSMOPs is always tricky, and mainly due to the following aspects: (1). The complexity of optimization problems tends to increase with the increase of dimensions. (2). The search space of large-scale problems increases exponentially with the increase of the dimension, which is known as the curse of dimensionality[2]. Therefore, a number of generic MOEAs have also been developed for solving LSMOPs since 2013[3]. These methods are usually not aimed at a specific type of problem but want to develop a general framework to solve LSMOPs[4]. There are mainly three strategies currently. (1). Variable grouping method based on Cooperative Coevolution (CC)[3]. (2). Methods based on dimensionality reduction or problem transformation[5]. (3). Design new search strategies based on MOEAs[6]. These strategies succeed in solving many-objective optimization problems[7], constrained multi-objective optimization problems[8], and computationally expensive multi-objective optimization problems[9].

This paper mainly adopt CC framework to solve the LSMOPs. Inspired by divide and conquer, the CC framework decomposes the original problem into multiple non-separable sub-problems and applies evolutionary algorithms (EAs) to solve each sub-problem alternately[10]. This strategy has been a huge success in solving large-scale problems. However, several studies[11, 12] have shown that the CC framework is sensitive to problem decomposition strategies. In theory, a perfect variable grouping strategy can exponentially reduce the search space without losing optimization accuracy, while a poor grouping strategy will mislead the direction of optimization. Therefore, how to design the decomposition strategy has become a popular research topic.

In addition, unlike large-scale single-objective optimization problems (LSSOPs), in LSMOPs, the same variables in different objective functions may have different interactions. Currently, there are many variable grouping methods were extended from LSSMOPs to group the variables in LSMOPs, such as Fast interdependency identification (FII) for LSMOPs[13], Differential Grouping (DG) for LSMOPs[14], MOEA-DVA[15], and other methods. Although these methods show great performance in grouping accuracy, computational cost and local interaction identification make these algorithms limited. What is more, many studies[11, 12] in LSSOPs show that high-accuracy grouping is not equivalent to high-performance optimization, and ignoring some weak interactions can accelerate the optimization, especially under the fitness evaluation times (FEs) limitation.

Besides, In order to find the global optimum among the fitness landscape, the heuristic algorithm should be equipped with two major characteristics to ensure finding the global optimum. These two main characteristics are exploration and exploitation[16]. Exploration is the ability of an algorithm to search whole parts of a problem space whereas exploitation is the convergence ability to the best solution near a good solution. However, the No Free Lunch Theorems (NFLT)[17] has proved that there is no algorithm, which can perform general enough to solve all optimization problems, and a single optimizer cannot balance the exploitation and exploration well in optimization, thus, hybrid evolutionary algorithms and memetic algorithms have become a popular research topic.

In this paper, we propose a novel variable grouping method, named Linkage Measurement Minimization (LMM) and apply hybrid Nondominated Sorting Genetic Algorithm II (hNSGA-II) as the sub-problem optimizer (CC-hNSGA-LMM). In the grouping stage, our proposal allows an automatic decomposition that treats the variable grouping problem as a combinatorial optimization problem, and we design a linkage measure function to evaluate the variable grouping performance. In the sub-problem optimization stage, we introduce a Gaussian sampling operator based on a estimated convergence point combined with NSGA-II to balance the exploitation and exploration in optimization. Specifically, the main contributions of this paper are as follows.

(1) For variable grouping, we propose a novel automatic variable grouping strategy named LLM and explain the mathmatical mechanism of LLM in detial, which reveals the relationship between our proposal and LINC-R.

(2) For optimizer, we first hypothesize that the individuals around the PF have better fitness, and the participation of elite individuals in optimization can accelerate the convergence. Based on this hypothesis, we estimate a convergence point at every generation of optimization and apply the Gaussian sampling as a local search operator to exploit the potential individuals around the estimated convergence point.

(3) Theoretical analysis and numerical experiments show that our proposal has broad prospects in solving LSMOPs and can solve larger-scale and many-objective optimization problems through simple extension.

The rest of the paper is organized as follows, Section II covers preliminaries and a brief review of grouping methods. Section III introduces our proposal in detail. Section IV shows the experiments and analysis. Section V discusses about the direction of our research in the future, Section VI concludes the paper and shows future directions.

Many grouping methods have been proposed based on CC for LSSOPs in recent years[11, 12], and meanwhile, some works have been expanded to LSMOPs[13, 4]. In this section, we firstly introduce some preliminaries including the concept of multi-objective problems, separability of functions, estimation of a convergence point, and NSGA-II. Then, we will provide a brief review of grouping methods both in LSSOPs and LSMOPs.

In this section, we will introduce the details of our proposal and the techniques. The flowchart of our proposal is shown in Figure 2.

Our proposal includes the decomposition stage and the optimization stage. Next, we will introduce the flow of our proposal in detail.

In decomposition stage, our previous research[37] regards the decomposition problem as an optimization problem and designed the linkage measurement function based on LINC-R. Next, we will give a simple mathematical explanation of our proposal.

In LINC-R, we can rewrite Eq (6) to Eq (8)

And we notice that LINC-R can be understood as the additive form of vector. Eq (8) can also be written to Eq (9)

Figure 3 shows how original LINC-R and variant LINC-R work on separable variables.

Next, we derive the variant LINC-R to $3$-D or higher dimensions. In $3$-D space, the schematic diagram is shown in Figure 4.

Similarly, we define the fitness difference in $3$-D space in Eq (10)

And Eq (11) defines the variant LINC-R in $3$-D space

Therefore, we can reasonably infer the variant LINC-R in $n$-D space on Eq (12).

Notice that we only detect the interactions based on the finite individuals, which means when $|{\Delta }_{1,2,...,n}-({\Delta }_1+{\Delta }_2+...+{\Delta }_n)|>ϵ$ is not satisfied at least once in all individuals, then we consider this function is a fully separable function by default. Although this strategy is limited especially for trap functions, it is impossible to check the interactions on the whole fitness landscape, and in LSSOPs, perturbation-based methods often identify the interactions based on 1 sample such as DG, DG2, etc. due to the FEs. Thus, Eq (13) is approximately correct in LSSOPs.

However, when Eq (13) is not satisfied, we only know that interactions exist in some variable pairs, but we cannot know the interactions exist in which pairs, so we can actively to detect the interactions between variables. Taking the $3$-D space as an example,

Therefore, Our target is to apply the heuristic algorithm to find the interactions between all variables as much as possible. According to the above explanation, in the $n$-D problem, the linkage measurement function in our proposal is designed as Eq (15)

$m$ is the number of sub-problems. Eq (15) is the original linkage measurement function of our proposal[37]. Meanwhile, our further research notice that this linkage measurement function often contains multiple optima especially in separable functions and partially separable function. Therefore, we can attach a reasonable penalty to lead the direction of optimization. Eq (16) defines a linkage measurement function with a penalty term.

Then, we extend Eq (16) to LSMOPs with multiple samples. Eq (17) is our linkage measurement function in this paper.

$w_j$ is the weight of the $j^{th}$ objective function, and $M$ is the number of objective functions in LSMOPs. We apply averaging weight in Eq (17).

To optimize this linkage measurement function, we also apply Elitist Genetic Algorithm (EGA)[38]. The pseudocode of decomposition stage is shown in Algorithm 2

The elitist reservation strategy directly replicates the best individual without crossover, mutation, and selection to the next generation. This strategy can prevent the optimal individual from destroying the superior gene and chromosome structure during crossover mutation.

In optimization stage, first we hypothesize that there is much possible for better individuals around the PF individuals. This hypothesis is extended from single objective optimization problems[20]. Based on this hypothesis, we find the PF in every generation of optimization by quick search. The pseudocode of quick search is shown in Algorithm 3.

And the function Dominate is realized in Algorithm 4.

The target of our quick search is only to find the whole PF in the current population, thus the fast non-dominated sorting in this situation is wasteful and unnecessary. From Algorithm 3, the worst and best time complexity of quick search is $O\left(M{N}^2\right)$ and $O\left(MN\right)$ respectively. $M$ is the number of objective functions, and $N$ is the population size. After the PF is found, we estimate the convergence point with averaging strategy and apply the Gaussian sampling with the mean of the estimated convergence point. Figure 5 and Algorithm 5 shows how our proposal works.

Finally, the whole process of our proposal in optimization stage is described on Algorithm 6

In this Section, we ran many experiments to evaluate our proposal, CC-hNSGA-LMM. In Section IV-A, we introduce the experiment settings, including benchmark functions, comparing methods, parameters of algorithms, and the performance indicators. In Section IV-B, we provide the experiment results. Finally, we analyze our proposal both in decomposition stage and optimization stage in Section IV-C.