# Using Objective Clustering for Solving Many-Objective Optimization Problems

Authors: Xiaofang Guo; Yuping Wang; Xiaoli Wang
Journal: Mathematical Problems in Engineering
 (2013)

---

## Abstract

Many-objective optimization problems involving a large number (more than four) of objectives have attracted considerable attention from the evolutionary multiobjective optimization field recently. With the increasing number of objectives, many-objective optimization problems may lead to stagnation in search process, high computational cost, increased dimensionality of Pareto-optimal front, and difficult visualization of the objective space. In this paper, a special kind of many-objective problems which has redundant objectives and which can be degenerated to a lower dimensional Pareto-optimal front has been investigated. Different from the works in the previous literatures, a novel metric, interdependence coefficient, which represents the nonlinear relationship between pairs of objectives, is introduced in this paper. In order to remove redundant objectives, PAM clustering algorithm is employed to identify redundant objectives by merging the less conflict objectives into the same cluster, and one of the least conflict objectives is removed. Furthermore, the potential of the proposed algorithm is demonstrated by a set of benchmark test problems scaled up to 20 objectives and a practical engineering design problem.


---

## Body

## 1. Introduction

Real-world engineering application problems often need to simultaneously optimize more than four objectives, called many-objective optimization problems [1]. Existing multiobjective evolutionary algorithms (MOEAs) have been successfully applied to solve problems with only two or three objectives, but they are not appropriate for problems with even more objectives. Since conventional multiobjective evolutionary algorithms rely primarily on Pareto ranking to guide the search, this enforces only little selection pressure in a many-objective setting. The more the objectives are, the larger is the proportion of nondominated solutions in a population, which results in the loss of selection pressure to drive the population toward the Pareto front [2]. Furthermore, the number of points required to approximate the Pareto front increases exponentially with the number of objectives, which makes it more difficult to capture the whole Pareto front for many-objective optimization. In addition, it is not possible to visualize the Pareto front with more than three objectives in a figure.The classical MOEAs such as NSGA-II and SPEA2 do not perform well in many-objective optimization cases. Over the last few years, a large proportion of hot issues in MOEAs have been related to many-objective optimization problems, and efforts have been made to deal with the aforementioned difficulties. The approaches for solving many-objective problems can be classified as follows. (1) The approaches based on the modifications of Pareto-dominance relations over the nondominated solutions (e.g., average and maximum ranking [3], favor preference relation [4], preference order ranking [5], and L-optimality [6]) and assigning different ranks to nondominated solutions: if the objectives are many, all the individuals in population are often Pareto-optimal solutions. There will be no difference of the selection pressure for the individuals in these algorithms. Thus, these algorithms cannot make a diverse search in the full Pareto front and can usually obtain a part of the Pareto front. (2) The approaches using some techniques to improve the scalability of MOEAs, for example, methods like MSOPS [7] and MSOPSII [8] use an aggregation method and perform many parallel searches using multiple conventional target vectors in different directions. Recently, surface evolutionary algorithm (SEA) [9] and a hybrid NSGA-II [10] were proposed, and they seem to be more efficient than the existing algorithms of this kind for many objectives. (3) The approaches based on finding the redundant objectives and reducing the number of objectives via removing some redundant objectives [11], in fact, there exists a kind of many-objective optimization problems with M objectives, where a subset of the original objectives can represent the optimization problem adequately, and the Pareto-optimal front is less than M-dimensions [12]. The objectives included in this subset are referred to as the essential objectives or nonredundant objectives, while the rest of the original objectives, which are unnecessary for the Pareto-optimal front and can be removed from the original set of objectives, are named redundant objectives. The process of removing the redundant objectives from the original objective set is called objective reduction or dimensionality reduction [13]. A lot of research works are carried out around the objective reduction. Brockhoff and Zitzler [14, 15] explored an objective reduction method for many-objective optimization problems. In their study, the effects on problems’ characteristics by adding or omitting objectives are investigated and a general definition of conflicts between objectives is proposed as a theoretical foundation for objective reduction. Moreover, two greedy algorithms are proposed to reduce the number of objectives, one of which finds a minimum number of objectives and the other finds a k-sized objective subset with the minimum possible error. Another method for objective reduction is based on the information of the correlation between pairs of objectives. Deb and Saxena [16, 17] proposed a technique for reducing redundant objectives based on principal component analysis (PCA), which takes the correlation between objectives as an indicator of the conflict. A large set of nondominated solutions are generated by NSGA-II, and the correlation matrix is computed for analyzing the relation of the objectives. Meanwhile, the conflict between a pair of objectives is judged by the correlation coefficient calculated by the set of nondominated solutions in this pair of objectives. If two objectives are negatively correlated, they are in conflict with each other. This method aims at computing a set of most important conflicting objectives, which can be obtained by an analysis of the eigenvectors and eigenvalues of the correlation matrix. Furthermore, Saxena and Deb [18] developed two new nonlinear dimensionality reduction algorithms employing the correntropy and maximum variance unfolding, namely, C-PCA-NSGA-II and MVU-PCA-NSGA-II, respectively. They are suitable for the data points that live on a nonlinear manifold or the data structure that is non-Gaussian. At the same time, Jaimes et al. [13] developed another dimensionality reduction scheme based on an unsupervised feature selection technique. In their scheme, the original objective set is divided into homogeneous neighborhoods based on a correlation matrix generated from a set of nondominated solutions. The conflict degree between redundant objectives is proportional to their distance, that is, the more conflict between two objectives, the farther the distance between them in the objective space. Therefore, the most compact neighborhood is chosen as the most relevant objective set, and all the objectives in it except the center one are removed as redundant objectives.The motivation of this paper is as follows. First, note that there are some limitations to use correlation coefficient to represent the relation between objectives [12, 13, 15, 16]. As well known, correlation coefficient can indicate the linear correlation between random variables. Similarly, it can make an analogy to the relationship between objectives. Thus, many scholars use correlation coefficient to represent the relation between objectives. However, nonlinear relation between objectives cannot be expressed by correlation coefficient. In order to overcome this shortcoming, by using the union of mutual information and correlation coefficient, a new metric called interdependence coefficient is proposed in this paper. Secondly, clustering algorithm is adopted to divide the original objective set into a few subsets with an aim at taking less conflict objectives into one cluster and assigning more conflict objectives into different clusters. Afterwards, the cluster which has the least conflict is chosen, and some of the objectives in it are removed based on some rules for the purpose of objective reduction. Here, partitioning around Medoid (PAM) clustering algorithm is borrowed to accomplish clustering. In this way, the procedure of objective reduction can be integrated with an MOEA to find a high quality Pareto-optimal front.This paper is organized as follows. The theoretical foundations are introduced in Section2. Section 3 describes proposed objective reduction algorithm using objective clustering (OC-ORA). The simulation results are given and discussed in Section 4. Finally, conclusions are made in Section 5.


## 2. Related Works

### 2.1. Many-Objective Problem and the Concept of Objective Reduction

Definition 1 (many-objective problem).
Without loss of generality, the multiobjective optimization problems are mathematically defined as follows:(1)minx∈Sf(x)={f1(x),f2(x),…,fm(x)},
where x=(x1,…,xn) is a solution vector of decision variables in the solution space S  and fi(x) is the ith objective function in the objective space. If the number of objectives is more than four, the problem is named many-objective optimization problem.Definition 2 (Pareto domination).
A vectorx is said to dominate another vector y if and only if
(2)(∀i)(fi(x)≤fi(y))∧(∃j)(fj(x)<fj(y)).Definition 3 (Pareto-optimal solution).
A solutionx∈S is said to be Pareto optimal with respect to solution space S if and only if there is no y∈S for which y dominates x.Definition 4 (Pareto-optimal set).
Pareto-optimal set is the set that consists of all Pareto-optimal solutions in solution spaceS, and the image of Pareto-optimal set in objective space is Pareto front.Definition 5 (conflicting objectives).
LetSχ be a subset of decision space S, given any x1,x2∈Sχ, if fi(x1)≤fi(x2) implies fj(x1)≥fj(x2), then one calls objective fi is in conflict with objective fj on Sχ. If fi(x1)≤fi(x2) implies fj(x1)≤fj(x2), then one calls objective fi is in nonconflict with objective fj on Sχ.Definition 6 (an essential objective set).
Given a many-objective optimization problem withM objectives, the original objective set is F0={f1,f2,…,fM}. The essential objective set is the smallest set of conflicting objectives which are sufficient to generate the Pareto front of the many-objective optimization problem, denoted by Fτ (|Fτ|=m<M).Definition 7 (a redundant objective set).
A redundant objective set refers to the objectives, which are not necessary to obtain the Pareto front, given byFredu=Fo∖Fτ. Notably, an objective could be redundant if it is nonconflicting or correlated with some other objectives.Accordingly, the analyst solving this type of problem has to decide whether all objectives are essential or not and employ an objective reduction algorithm to obtain an essential objective setFτ.


### 2.2. The Traditional Representation of the Correlation between a Pair of Objectives

The correlation coefficient matrix is used to measure the conflict between each pair of objectives [12, 13]. This matrix is computed by using an approximation set of the Pareto-optimal solutions generated by MOEA, for example, NSGA-II. A negative correlation between a pair of objectives means that when one objective increases, the other will decrease, while a positive correlation represents the opposite. Thus, the more positive the correlation between two objectives is, the less conflict between them will exist, and one of the objectives can be regarded as the redundant one, which can be eliminated from the original objective set.However, correlation coefficient can only indicate linear correlation between objectives, while the nonlinear relation cannot be expressed. In order to overcome this limitation, a new metric is proposed by using the union of mutual information and correlation coefficient in this paper to measure the correlation between objectives. The introduction of mutual information [19, 20] is described as follows.


### 2.3. Mutual Information

Definition 8 (self-information of random event).
Supposex is a discrete random event and X is a discrete random variable, then the self-information of the random event x is defined by
(3)I(x)=-log2P{X=x}.
The functionI(x) can be interpreted as the amount of information provided by the event {X=x} or our uncertainty about the event {X=x} [19]. According to this interpretation, the less probable an event is, the more information we receive when it occurs. A certain event (one that occurs with probability 1) provides no information, whereas an unlikely event provides a very large amount of information.Definition 9 (self-information or entropy of random variable).
Suppose thatX is a discrete random variable; that is, its range R={x1,x2,…} is finite or countable. Let pi=P{X=xi}. The self-information or entropy of random variable X is defined by
(4)H(X)=E(I(xi))=∑ipilog21pi.It turns out thatH(X) is the expectation of I(xi) over all possible events, and it can be thought of as a measure of the amount of information provided by an observation of X or our uncertainty about X.Definition 10 (conditional entropy).
For a pair of random variablesX and Y, a quantity H(X∣Y) is called the conditional entropy of X with a given Y. More precisely, if H(X∣Y=y) is the entropy of the variable X on condition of the variable Y taking a certain value, then H(X∣Y) is the result of averaging H(X∣Y=y) over all possible values that may take as follows:
(5)H(X∣Y)=∑jp(yj)H(X∣yj)=∑jp(yj)∑ip(xi∣yj)log21p(xi∣yj)=-∑i∑jp(xi,xj)log2p(xi∣yj).
Given the value of the other random variableY, the conditional entropy quantifies the remaining amount of information needed to describe the outcome of a random variable X. Here, H(X∣Y)=0 if and only if the value of Y is completely determined by the value of X. Conversely, H(X∣Y)=H(X) if and only if Y and X are independent random variables.Definition 11 (mutual information [19]).
Consider two random variablesX and Y with a joint probability mass function p(x,y) and marginal probability mass functions p(x) and p(y). The mutual information I(X;Y) is the relative entropy between the joint distribution and the product distribution p(x)p(y), which can be defined by (6). Thus, the mutual information I(X;Y) is the reduction in the uncertainty of X due to the knowledge of Y:
(6)I(X;Y)=∑x,yp(x,y)logp(x,y)p(x)p(y)=∑x,yp(x,y)logp(x∣y)p(x)=-∑x,yp(x,y)logp(x)+∑x,yp(x,y)logp(x∣y)=H(X)-H(X∣Y)=H(Y)-H(Y∣X)=H(X)+H(Y)-H(XY).
One can see from the above expression that the mutual information is symmetric inX and Y. This symmetry means that this notion of uncertainty has the property that the information we gain about X when knowing Y is the same as the information we gain about Y when knowing X.


### 2.4. PAM Clustering Algorithm

Kaufman and Rousseeuw [21, 22] proposed a clustering algorithm partitioning around medoids (PAM), which partitions a set of objects into k clusters, where the objects in one cluster show a high degree of similarity, while objects belonging to different clusters are as dissimilar as possible. PAM clustering algorithm only needs a distance matrix between objects and does not need the location of the objects or other information. Motivated by the idea of PAM, we use this clustering algorithm to divide the set of many objectives into different clusters.In PAM,k partitions for n objects are formed. Initially, k medoids (central points) are selected from the set of objects randomly. A medoid representing a cluster is located in the center of the cluster, and each remaining object is assigned to a cluster whose medoid is the nearest to this object. Then one of the medoids is replaced by a nonmedoid such that the quality of resulting cluster can be improved. The quality is estimated by a cost function that measures the average dissimilarity between every object in this cluster and its corresponding medoid. We replace the distance or similarity measure in PAM by a new metric named interdependence coefficient to measure the degree of correlation between pairs of objectives.


## 2.1. Many-Objective Problem and the Concept of Objective Reduction

Definition 1 (many-objective problem).
Without loss of generality, the multiobjective optimization problems are mathematically defined as follows:(1)minx∈Sf(x)={f1(x),f2(x),…,fm(x)},
where x=(x1,…,xn) is a solution vector of decision variables in the solution space S  and fi(x) is the ith objective function in the objective space. If the number of objectives is more than four, the problem is named many-objective optimization problem.Definition 2 (Pareto domination).
A vectorx is said to dominate another vector y if and only if
(2)(∀i)(fi(x)≤fi(y))∧(∃j)(fj(x)<fj(y)).Definition 3 (Pareto-optimal solution).
A solutionx∈S is said to be Pareto optimal with respect to solution space S if and only if there is no y∈S for which y dominates x.Definition 4 (Pareto-optimal set).
Pareto-optimal set is the set that consists of all Pareto-optimal solutions in solution spaceS, and the image of Pareto-optimal set in objective space is Pareto front.Definition 5 (conflicting objectives).
LetSχ be a subset of decision space S, given any x1,x2∈Sχ, if fi(x1)≤fi(x2) implies fj(x1)≥fj(x2), then one calls objective fi is in conflict with objective fj on Sχ. If fi(x1)≤fi(x2) implies fj(x1)≤fj(x2), then one calls objective fi is in nonconflict with objective fj on Sχ.Definition 6 (an essential objective set).
Given a many-objective optimization problem withM objectives, the original objective set is F0={f1,f2,…,fM}. The essential objective set is the smallest set of conflicting objectives which are sufficient to generate the Pareto front of the many-objective optimization problem, denoted by Fτ (|Fτ|=m<M).Definition 7 (a redundant objective set).
A redundant objective set refers to the objectives, which are not necessary to obtain the Pareto front, given byFredu=Fo∖Fτ. Notably, an objective could be redundant if it is nonconflicting or correlated with some other objectives.Accordingly, the analyst solving this type of problem has to decide whether all objectives are essential or not and employ an objective reduction algorithm to obtain an essential objective setFτ.


## 2.2. The Traditional Representation of the Correlation between a Pair of Objectives

The correlation coefficient matrix is used to measure the conflict between each pair of objectives [12, 13]. This matrix is computed by using an approximation set of the Pareto-optimal solutions generated by MOEA, for example, NSGA-II. A negative correlation between a pair of objectives means that when one objective increases, the other will decrease, while a positive correlation represents the opposite. Thus, the more positive the correlation between two objectives is, the less conflict between them will exist, and one of the objectives can be regarded as the redundant one, which can be eliminated from the original objective set.However, correlation coefficient can only indicate linear correlation between objectives, while the nonlinear relation cannot be expressed. In order to overcome this limitation, a new metric is proposed by using the union of mutual information and correlation coefficient in this paper to measure the correlation between objectives. The introduction of mutual information [19, 20] is described as follows.


## 2.3. Mutual Information

Definition 8 (self-information of random event).
Supposex is a discrete random event and X is a discrete random variable, then the self-information of the random event x is defined by
(3)I(x)=-log2P{X=x}.
The functionI(x) can be interpreted as the amount of information provided by the event {X=x} or our uncertainty about the event {X=x} [19]. According to this interpretation, the less probable an event is, the more information we receive when it occurs. A certain event (one that occurs with probability 1) provides no information, whereas an unlikely event provides a very large amount of information.Definition 9 (self-information or entropy of random variable).
Suppose thatX is a discrete random variable; that is, its range R={x1,x2,…} is finite or countable. Let pi=P{X=xi}. The self-information or entropy of random variable X is defined by
(4)H(X)=E(I(xi))=∑ipilog21pi.It turns out thatH(X) is the expectation of I(xi) over all possible events, and it can be thought of as a measure of the amount of information provided by an observation of X or our uncertainty about X.Definition 10 (conditional entropy).
For a pair of random variablesX and Y, a quantity H(X∣Y) is called the conditional entropy of X with a given Y. More precisely, if H(X∣Y=y) is the entropy of the variable X on condition of the variable Y taking a certain value, then H(X∣Y) is the result of averaging H(X∣Y=y) over all possible values that may take as follows:
(5)H(X∣Y)=∑jp(yj)H(X∣yj)=∑jp(yj)∑ip(xi∣yj)log21p(xi∣yj)=-∑i∑jp(xi,xj)log2p(xi∣yj).
Given the value of the other random variableY, the conditional entropy quantifies the remaining amount of information needed to describe the outcome of a random variable X. Here, H(X∣Y)=0 if and only if the value of Y is completely determined by the value of X. Conversely, H(X∣Y)=H(X) if and only if Y and X are independent random variables.Definition 11 (mutual information [19]).
Consider two random variablesX and Y with a joint probability mass function p(x,y) and marginal probability mass functions p(x) and p(y). The mutual information I(X;Y) is the relative entropy between the joint distribution and the product distribution p(x)p(y), which can be defined by (6). Thus, the mutual information I(X;Y) is the reduction in the uncertainty of X due to the knowledge of Y:
(6)I(X;Y)=∑x,yp(x,y)logp(x,y)p(x)p(y)=∑x,yp(x,y)logp(x∣y)p(x)=-∑x,yp(x,y)logp(x)+∑x,yp(x,y)logp(x∣y)=H(X)-H(X∣Y)=H(Y)-H(Y∣X)=H(X)+H(Y)-H(XY).
One can see from the above expression that the mutual information is symmetric inX and Y. This symmetry means that this notion of uncertainty has the property that the information we gain about X when knowing Y is the same as the information we gain about Y when knowing X.


## 2.4. PAM Clustering Algorithm

Kaufman and Rousseeuw [21, 22] proposed a clustering algorithm partitioning around medoids (PAM), which partitions a set of objects into k clusters, where the objects in one cluster show a high degree of similarity, while objects belonging to different clusters are as dissimilar as possible. PAM clustering algorithm only needs a distance matrix between objects and does not need the location of the objects or other information. Motivated by the idea of PAM, we use this clustering algorithm to divide the set of many objectives into different clusters.In PAM,k partitions for n objects are formed. Initially, k medoids (central points) are selected from the set of objects randomly. A medoid representing a cluster is located in the center of the cluster, and each remaining object is assigned to a cluster whose medoid is the nearest to this object. Then one of the medoids is replaced by a nonmedoid such that the quality of resulting cluster can be improved. The quality is estimated by a cost function that measures the average dissimilarity between every object in this cluster and its corresponding medoid. We replace the distance or similarity measure in PAM by a new metric named interdependence coefficient to measure the degree of correlation between pairs of objectives.


## 3. Objective Clustering-Based Objective Reduction Algorithm (OC-ORA) for Many-Objective Optimization Problems

An objective clustering-based objective reduction algorithm is proposed in this section. It is a progressive procedure for objective reduction and can calculate an interdependence coefficient matrix (a measure of the degree of correlation) between each pair of objectives. It is used to combine with MOEA to obtain the nondominated solution set. Given anM-objectives optimization problem, if the number of essential objective set is less than M, the objectives with nonconflict may be the redundant ones. In OC-ORA, PAM is adopted to divide the current objective set into a number of clusters according to the correlation with objectives. Subsequently, we identify the most correlated pair of objectives in the most correlated cluster in order to remove the redundant objective for many-objective problems. In the proposed algorithm, the MOEA and the objective reduction are executed alternately; this process will end when no further objective reduction can be achieved. Figure 1 shows the procedure in the proposed OC-ORA.Figure 1
Flow chart of the proposed OC-ORA.


### 3.1. Interdependence Coefficient between Pairs of Objectives

Note that correlation coefficients can only reflect the linear relations between objectives [13], but they cannot represent nonlinear relations. In order to overcome this limitation, a new metric using the mutual information and correlation coefficient, named interdependence coefficient, is developed to describe the correlation between objectives. This new measure between pairs of objectives is also calculated based on a set of nondominated solutions generated by multiobjective evolutionary procedure via NSGA-II.


#### 3.1.1. The Definition of Interdependence Coefficient

For a pair of objectivesfi and fj, its mutual information is defined as I(fi;fj) by Definition 11. Note that mutual information is nonnegative, and thus it cannot distinguish the negative correlation. To overcome the shortcoming, the union of mutual information and correlation coefficient is used to measure the correlation relation between objectives. The new measure named interdependence coefficient, denoted by dfi,fj, is defined as follows:
(7)dfi,fj=1-sign(ρfi,fj)·I(fi;fj)H(fi)·H(fj),
where ρfi,fj and I(fi;fj) represent the correlation coefficient and mutual information between a pair of objectives fi and fj, respectively. sign(ρfi,fj) is a symbolic function used to distinguish the positive and negative correlations between a pair of objectives. In addition, the mutual information is normalized in (7), and its value is limited in the range of [0,1]. Thus, interdependence coefficient dfi,fj∈[0,2] is used to measure the degree of correlation. In this way, we could guarantee that the greater the value of the interdependence coefficient between two objectives is, the more conflict or the less interdependent between them will exist, and vice versa. Value 2 indicates that objectives fi and fj are completely negatively correlated or totally conflict with each other, and Value 0 indicates that the objectives are completely positively correlated or without any conflict with each other:
(8)sign(ρfi,fj)={1ρfi,fj≥0-1ρfi,fj<0.


#### 3.1.2. The Approximate Calculation of Entropy and Mutual Information between Two Objectives

In order to facilitate understanding, we will analyze the process of calculating the mutual information between any pair of objectivesfi and fj. A set of nondominated solutions generated by multiobjective evolutionary procedure NSGA-II are taken as original data for calculating the entropy. In (6), the entropy of fi,fj, and fifj, that is, H(fi), H(fj), and H(fifj), must be known before calculating the mutual information I(fi;fj). In (4), for a given objective fi, we take fi as a random variable, denoted by X and the values of fi on the nondominated solutions as the values of random variable X. Meanwhile, we use the maximum and minimum values of fi on these nondominated solutions to construct an interval [minimum, maximum] which can be seen as the region of random variable X and then divide it into many smaller subintervals. Here, we assume that all values of X corresponding to all nondominated solutions fall on arbitrary position of the interval with the same possibility. Then, we count the number of nondominated solutions in each subinterval and calculate the probability of the random variable X falling into each subinterval. This probability can be calculated by P(X∈subintervalk)=Nk/N, where Nk denotes the number of nondominated solutions in the kth subinterval (k=1,2,…) and N denotes the number of nondominated solutions. In order to simplify the problem and calculate the entropy of objectives fi in (4), we assume that if the number of subintervals is sufficiently large, each subinterval can be approximately seen as a point and the variable X can be seen as a discrete random variable. Thus, the probability of the random variable X falling into a subinterval can be approximately regarded as the probability of X taking the middle point xk of this subinterval, where xk=(upperboundk-lowerboundk)/2. In this way, the entropy H(fi) can be calculated based on (4).Similar to the calculation of the entropy of one objective, we need to divide the region in which the nondominated solutions locate into many smaller subregions in two-dimensional space and count the number of nondominated solutions in each subregion and calculate the probability of the two-dimensional random variable falling into each subregion in order to calculateH(fifj).


### 3.2. The Process of Objective Clustering and Objective Reduction

#### 3.2.1. The Procedure of Objective Clustering

After calculating the interdependence coefficient between every pair of objectives, we get an interdependence coefficient matrix with orderM, named D=(dij)M×M, in which each element dij represents the interdependence coefficient between the ith and the jth objectives. This matrix is used to measure the degree of correlation between each pair of objectives.Then, we use PAM clustering algorithm to group all objectives into some small clusters. The reason of using PAM clustering algorithm is that it only needs a distance matrix between objects as the input, and it does not need the location of the objects or other information. Here, the interdependence coefficient matrix is taken as the distance matrix. The larger the interdependence coefficient is, the farther (less similar) the corresponding pair of objectives will be.According to the procedure of PAM,k objectives are chosen arbitrarily from the original objective set as the initial centers of k clusters, and each of the other (M-k) objectives is classified into a cluster whose center is nearest to this objective. Next, a central objective is replaced by a noncentral objective repeatedly until the quality of the resulting cluster cannot be improved. In this way, the objectives in one cluster show a high degree of correlation, while objectives belonging to different clusters reflect more conflict.


#### 3.2.2. The Process of Objective Reduction

In the process of objective reduction, we calculate the interdependence coefficients matrix in each cluster and take the cluster containing the minimum interdependence coefficient as the most highly correlated cluster, and the pair of objectives with the minimum interdependence coefficient can be regarded as the most relevant objectives in the current objective set. Note that the more the minimum interdependence coefficient in the most highly correlated cluster close to zero, the less is the conflict of the corresponding pair of objectives. Here, we use a redundant thresholdθ to remove the redundant objective. If the minimum interdependence coefficient in the most highly correlated cluster is less than a predetermined threshold θ, one of the objectives in this pair will be removed from the current objective set; otherwise, all the objectives will be retained. In the proposed algorithm, the multiobjective evolutionary algorithm and the strategy of objective reduction are executed alternately where at most, one objective is removed in an iteration.The process of objective reduction consists of two steps. Figure2 shows the main skeleton. (1)
Recalculate the interdependence coefficient matrix in each cluster obtained by objective clustering process. Take thetth cluster containing the minimum interdependence coefficient, that is, the cluster with dpqt=minl∈{1,2,⋯k}mini,j∈Cl(dijl), as the most highly correlated cluster, where fp and fq are the objectives with the minimum interdependence coefficient dpqt and are the candidates of redundant objective. Figure 2(a) shows two clusters determined by PAM with total six objectives marked from number 1 to 6, where red triangle represents the central point of the cluster and green circle represents noncentral point. As it can be seen from the figure, d13 is the minimum interdependence coefficient in the left cluster and d45 in the right cluster. Because of d13<d45, the cluster on the left is the most highly correlated cluster, and f1 or f3 is the candidate redundant objective.(2)
Remove one of the candidate redundant objectives. Firstly, identify the value of the minimum interdependence coefficientdpqt. If dpqt>θ, the correlation between fp and fq is weak and all of objectives should be retained; else, check either fp or fq is the central objective in its cluster, if either of the two is central point, the other one can be removed as the redundant objective. If neither of them is the central objective, we could calculate the sum of interdependence coefficients between each of fp and fq and the other objectives in the current objectives set and take the one fp or fq with the smaller sum as the redundant objective, denoted by fredn=argmin{∑fi≠fkdfi,fk∣fk=fp,fq}. As can be seen in Figure 2(b), objective 1 and 3 are the most highly correlated objectives in the cluster, since the 3th objective is the center in the left cluster, it will be retained and the objective 1 is regarded as the redundant objective to be removed.The strategy of the objective reduction method employed.
(a)
(b)Algorithm 12 (OC-ORA).
22222
Step  1  (Initialization). Set an iteration counter t=0; original objective set is Ft={f1,f2,…,fM}, and the number of predefined clusters is k.
Step  2. Initialize a random population Pt, run NSGA-II corresponding to Ft for Ng generations, and obtain a nondominated set At.
Step  3. Calculate the interdependence coefficient matrix based on the nondominated set At, and use the PAM clustering algorithm to divide the objective set Ft into k clusters.
Step  4. According to the clusters of objective set Ft obtained in Step  3, remove one of the redundant or the most interdependent objective from Ft according to the above objective reduction rules, and the remaining objective set is denoted as Ft+1.
Step  5. If Ft=Ft+1, stop; else t:=t+1,Ft:=Ft+1; return to Step  2.


## 3.1. Interdependence Coefficient between Pairs of Objectives

Note that correlation coefficients can only reflect the linear relations between objectives [13], but they cannot represent nonlinear relations. In order to overcome this limitation, a new metric using the mutual information and correlation coefficient, named interdependence coefficient, is developed to describe the correlation between objectives. This new measure between pairs of objectives is also calculated based on a set of nondominated solutions generated by multiobjective evolutionary procedure via NSGA-II.


### 3.1.1. The Definition of Interdependence Coefficient

For a pair of objectivesfi and fj, its mutual information is defined as I(fi;fj) by Definition 11. Note that mutual information is nonnegative, and thus it cannot distinguish the negative correlation. To overcome the shortcoming, the union of mutual information and correlation coefficient is used to measure the correlation relation between objectives. The new measure named interdependence coefficient, denoted by dfi,fj, is defined as follows:
(7)dfi,fj=1-sign(ρfi,fj)·I(fi;fj)H(fi)·H(fj),
where ρfi,fj and I(fi;fj) represent the correlation coefficient and mutual information between a pair of objectives fi and fj, respectively. sign(ρfi,fj) is a symbolic function used to distinguish the positive and negative correlations between a pair of objectives. In addition, the mutual information is normalized in (7), and its value is limited in the range of [0,1]. Thus, interdependence coefficient dfi,fj∈[0,2] is used to measure the degree of correlation. In this way, we could guarantee that the greater the value of the interdependence coefficient between two objectives is, the more conflict or the less interdependent between them will exist, and vice versa. Value 2 indicates that objectives fi and fj are completely negatively correlated or totally conflict with each other, and Value 0 indicates that the objectives are completely positively correlated or without any conflict with each other:
(8)sign(ρfi,fj)={1ρfi,fj≥0-1ρfi,fj<0.


### 3.1.2. The Approximate Calculation of Entropy and Mutual Information between Two Objectives

In order to facilitate understanding, we will analyze the process of calculating the mutual information between any pair of objectivesfi and fj. A set of nondominated solutions generated by multiobjective evolutionary procedure NSGA-II are taken as original data for calculating the entropy. In (6), the entropy of fi,fj, and fifj, that is, H(fi), H(fj), and H(fifj), must be known before calculating the mutual information I(fi;fj). In (4), for a given objective fi, we take fi as a random variable, denoted by X and the values of fi on the nondominated solutions as the values of random variable X. Meanwhile, we use the maximum and minimum values of fi on these nondominated solutions to construct an interval [minimum, maximum] which can be seen as the region of random variable X and then divide it into many smaller subintervals. Here, we assume that all values of X corresponding to all nondominated solutions fall on arbitrary position of the interval with the same possibility. Then, we count the number of nondominated solutions in each subinterval and calculate the probability of the random variable X falling into each subinterval. This probability can be calculated by P(X∈subintervalk)=Nk/N, where Nk denotes the number of nondominated solutions in the kth subinterval (k=1,2,…) and N denotes the number of nondominated solutions. In order to simplify the problem and calculate the entropy of objectives fi in (4), we assume that if the number of subintervals is sufficiently large, each subinterval can be approximately seen as a point and the variable X can be seen as a discrete random variable. Thus, the probability of the random variable X falling into a subinterval can be approximately regarded as the probability of X taking the middle point xk of this subinterval, where xk=(upperboundk-lowerboundk)/2. In this way, the entropy H(fi) can be calculated based on (4).Similar to the calculation of the entropy of one objective, we need to divide the region in which the nondominated solutions locate into many smaller subregions in two-dimensional space and count the number of nondominated solutions in each subregion and calculate the probability of the two-dimensional random variable falling into each subregion in order to calculateH(fifj).


## 3.1.1. The Definition of Interdependence Coefficient

For a pair of objectivesfi and fj, its mutual information is defined as I(fi;fj) by Definition 11. Note that mutual information is nonnegative, and thus it cannot distinguish the negative correlation. To overcome the shortcoming, the union of mutual information and correlation coefficient is used to measure the correlation relation between objectives. The new measure named interdependence coefficient, denoted by dfi,fj, is defined as follows:
(7)dfi,fj=1-sign(ρfi,fj)·I(fi;fj)H(fi)·H(fj),
where ρfi,fj and I(fi;fj) represent the correlation coefficient and mutual information between a pair of objectives fi and fj, respectively. sign(ρfi,fj) is a symbolic function used to distinguish the positive and negative correlations between a pair of objectives. In addition, the mutual information is normalized in (7), and its value is limited in the range of [0,1]. Thus, interdependence coefficient dfi,fj∈[0,2] is used to measure the degree of correlation. In this way, we could guarantee that the greater the value of the interdependence coefficient between two objectives is, the more conflict or the less interdependent between them will exist, and vice versa. Value 2 indicates that objectives fi and fj are completely negatively correlated or totally conflict with each other, and Value 0 indicates that the objectives are completely positively correlated or without any conflict with each other:
(8)sign(ρfi,fj)={1ρfi,fj≥0-1ρfi,fj<0.


## 3.1.2. The Approximate Calculation of Entropy and Mutual Information between Two Objectives

In order to facilitate understanding, we will analyze the process of calculating the mutual information between any pair of objectivesfi and fj. A set of nondominated solutions generated by multiobjective evolutionary procedure NSGA-II are taken as original data for calculating the entropy. In (6), the entropy of fi,fj, and fifj, that is, H(fi), H(fj), and H(fifj), must be known before calculating the mutual information I(fi;fj). In (4), for a given objective fi, we take fi as a random variable, denoted by X and the values of fi on the nondominated solutions as the values of random variable X. Meanwhile, we use the maximum and minimum values of fi on these nondominated solutions to construct an interval [minimum, maximum] which can be seen as the region of random variable X and then divide it into many smaller subintervals. Here, we assume that all values of X corresponding to all nondominated solutions fall on arbitrary position of the interval with the same possibility. Then, we count the number of nondominated solutions in each subinterval and calculate the probability of the random variable X falling into each subinterval. This probability can be calculated by P(X∈subintervalk)=Nk/N, where Nk denotes the number of nondominated solutions in the kth subinterval (k=1,2,…) and N denotes the number of nondominated solutions. In order to simplify the problem and calculate the entropy of objectives fi in (4), we assume that if the number of subintervals is sufficiently large, each subinterval can be approximately seen as a point and the variable X can be seen as a discrete random variable. Thus, the probability of the random variable X falling into a subinterval can be approximately regarded as the probability of X taking the middle point xk of this subinterval, where xk=(upperboundk-lowerboundk)/2. In this way, the entropy H(fi) can be calculated based on (4).Similar to the calculation of the entropy of one objective, we need to divide the region in which the nondominated solutions locate into many smaller subregions in two-dimensional space and count the number of nondominated solutions in each subregion and calculate the probability of the two-dimensional random variable falling into each subregion in order to calculateH(fifj).


## 3.2. The Process of Objective Clustering and Objective Reduction

### 3.2.1. The Procedure of Objective Clustering

After calculating the interdependence coefficient between every pair of objectives, we get an interdependence coefficient matrix with orderM, named D=(dij)M×M, in which each element dij represents the interdependence coefficient between the ith and the jth objectives. This matrix is used to measure the degree of correlation between each pair of objectives.Then, we use PAM clustering algorithm to group all objectives into some small clusters. The reason of using PAM clustering algorithm is that it only needs a distance matrix between objects as the input, and it does not need the location of the objects or other information. Here, the interdependence coefficient matrix is taken as the distance matrix. The larger the interdependence coefficient is, the farther (less similar) the corresponding pair of objectives will be.According to the procedure of PAM,k objectives are chosen arbitrarily from the original objective set as the initial centers of k clusters, and each of the other (M-k) objectives is classified into a cluster whose center is nearest to this objective. Next, a central objective is replaced by a noncentral objective repeatedly until the quality of the resulting cluster cannot be improved. In this way, the objectives in one cluster show a high degree of correlation, while objectives belonging to different clusters reflect more conflict.


### 3.2.2. The Process of Objective Reduction

In the process of objective reduction, we calculate the interdependence coefficients matrix in each cluster and take the cluster containing the minimum interdependence coefficient as the most highly correlated cluster, and the pair of objectives with the minimum interdependence coefficient can be regarded as the most relevant objectives in the current objective set. Note that the more the minimum interdependence coefficient in the most highly correlated cluster close to zero, the less is the conflict of the corresponding pair of objectives. Here, we use a redundant thresholdθ to remove the redundant objective. If the minimum interdependence coefficient in the most highly correlated cluster is less than a predetermined threshold θ, one of the objectives in this pair will be removed from the current objective set; otherwise, all the objectives will be retained. In the proposed algorithm, the multiobjective evolutionary algorithm and the strategy of objective reduction are executed alternately where at most, one objective is removed in an iteration.The process of objective reduction consists of two steps. Figure2 shows the main skeleton. (1)
Recalculate the interdependence coefficient matrix in each cluster obtained by objective clustering process. Take thetth cluster containing the minimum interdependence coefficient, that is, the cluster with dpqt=minl∈{1,2,⋯k}mini,j∈Cl(dijl), as the most highly correlated cluster, where fp and fq are the objectives with the minimum interdependence coefficient dpqt and are the candidates of redundant objective. Figure 2(a) shows two clusters determined by PAM with total six objectives marked from number 1 to 6, where red triangle represents the central point of the cluster and green circle represents noncentral point. As it can be seen from the figure, d13 is the minimum interdependence coefficient in the left cluster and d45 in the right cluster. Because of d13<d45, the cluster on the left is the most highly correlated cluster, and f1 or f3 is the candidate redundant objective.(2)
Remove one of the candidate redundant objectives. Firstly, identify the value of the minimum interdependence coefficientdpqt. If dpqt>θ, the correlation between fp and fq is weak and all of objectives should be retained; else, check either fp or fq is the central objective in its cluster, if either of the two is central point, the other one can be removed as the redundant objective. If neither of them is the central objective, we could calculate the sum of interdependence coefficients between each of fp and fq and the other objectives in the current objectives set and take the one fp or fq with the smaller sum as the redundant objective, denoted by fredn=argmin{∑fi≠fkdfi,fk∣fk=fp,fq}. As can be seen in Figure 2(b), objective 1 and 3 are the most highly correlated objectives in the cluster, since the 3th objective is the center in the left cluster, it will be retained and the objective 1 is regarded as the redundant objective to be removed.The strategy of the objective reduction method employed.
(a)
(b)Algorithm 12 (OC-ORA).
22222
Step  1  (Initialization). Set an iteration counter t=0; original objective set is Ft={f1,f2,…,fM}, and the number of predefined clusters is k.
Step  2. Initialize a random population Pt, run NSGA-II corresponding to Ft for Ng generations, and obtain a nondominated set At.
Step  3. Calculate the interdependence coefficient matrix based on the nondominated set At, and use the PAM clustering algorithm to divide the objective set Ft into k clusters.
Step  4. According to the clusters of objective set Ft obtained in Step  3, remove one of the redundant or the most interdependent objective from Ft according to the above objective reduction rules, and the remaining objective set is denoted as Ft+1.
Step  5. If Ft=Ft+1, stop; else t:=t+1,Ft:=Ft+1; return to Step  2.


## 3.2.1. The Procedure of Objective Clustering

After calculating the interdependence coefficient between every pair of objectives, we get an interdependence coefficient matrix with orderM, named D=(dij)M×M, in which each element dij represents the interdependence coefficient between the ith and the jth objectives. This matrix is used to measure the degree of correlation between each pair of objectives.Then, we use PAM clustering algorithm to group all objectives into some small clusters. The reason of using PAM clustering algorithm is that it only needs a distance matrix between objects as the input, and it does not need the location of the objects or other information. Here, the interdependence coefficient matrix is taken as the distance matrix. The larger the interdependence coefficient is, the farther (less similar) the corresponding pair of objectives will be.According to the procedure of PAM,k objectives are chosen arbitrarily from the original objective set as the initial centers of k clusters, and each of the other (M-k) objectives is classified into a cluster whose center is nearest to this objective. Next, a central objective is replaced by a noncentral objective repeatedly until the quality of the resulting cluster cannot be improved. In this way, the objectives in one cluster show a high degree of correlation, while objectives belonging to different clusters reflect more conflict.


## 3.2.2. The Process of Objective Reduction

In the process of objective reduction, we calculate the interdependence coefficients matrix in each cluster and take the cluster containing the minimum interdependence coefficient as the most highly correlated cluster, and the pair of objectives with the minimum interdependence coefficient can be regarded as the most relevant objectives in the current objective set. Note that the more the minimum interdependence coefficient in the most highly correlated cluster close to zero, the less is the conflict of the corresponding pair of objectives. Here, we use a redundant thresholdθ to remove the redundant objective. If the minimum interdependence coefficient in the most highly correlated cluster is less than a predetermined threshold θ, one of the objectives in this pair will be removed from the current objective set; otherwise, all the objectives will be retained. In the proposed algorithm, the multiobjective evolutionary algorithm and the strategy of objective reduction are executed alternately where at most, one objective is removed in an iteration.The process of objective reduction consists of two steps. Figure2 shows the main skeleton. (1)
Recalculate the interdependence coefficient matrix in each cluster obtained by objective clustering process. Take thetth cluster containing the minimum interdependence coefficient, that is, the cluster with dpqt=minl∈{1,2,⋯k}mini,j∈Cl(dijl), as the most highly correlated cluster, where fp and fq are the objectives with the minimum interdependence coefficient dpqt and are the candidates of redundant objective. Figure 2(a) shows two clusters determined by PAM with total six objectives marked from number 1 to 6, where red triangle represents the central point of the cluster and green circle represents noncentral point. As it can be seen from the figure, d13 is the minimum interdependence coefficient in the left cluster and d45 in the right cluster. Because of d13<d45, the cluster on the left is the most highly correlated cluster, and f1 or f3 is the candidate redundant objective.(2)
Remove one of the candidate redundant objectives. Firstly, identify the value of the minimum interdependence coefficientdpqt. If dpqt>θ, the correlation between fp and fq is weak and all of objectives should be retained; else, check either fp or fq is the central objective in its cluster, if either of the two is central point, the other one can be removed as the redundant objective. If neither of them is the central objective, we could calculate the sum of interdependence coefficients between each of fp and fq and the other objectives in the current objectives set and take the one fp or fq with the smaller sum as the redundant objective, denoted by fredn=argmin{∑fi≠fkdfi,fk∣fk=fp,fq}. As can be seen in Figure 2(b), objective 1 and 3 are the most highly correlated objectives in the cluster, since the 3th objective is the center in the left cluster, it will be retained and the objective 1 is regarded as the redundant objective to be removed.The strategy of the objective reduction method employed.
(a)
(b)Algorithm 12 (OC-ORA).
22222
Step  1  (Initialization). Set an iteration counter t=0; original objective set is Ft={f1,f2,…,fM}, and the number of predefined clusters is k.
Step  2. Initialize a random population Pt, run NSGA-II corresponding to Ft for Ng generations, and obtain a nondominated set At.
Step  3. Calculate the interdependence coefficient matrix based on the nondominated set At, and use the PAM clustering algorithm to divide the objective set Ft into k clusters.
Step  4. According to the clusters of objective set Ft obtained in Step  3, remove one of the redundant or the most interdependent objective from Ft according to the above objective reduction rules, and the remaining objective set is denoted as Ft+1.
Step  5. If Ft=Ft+1, stop; else t:=t+1,Ft:=Ft+1; return to Step  2.


## 4. Simulation Results

To verify the performance of the proposed algorithm for objective reduction, we employ test functions DTLZ2(M) and DTLZ5 (I,M) [23–25] in the experiments. These test functions are described below. Furthermore, a real practical engineering design problem, storm drainage systems, is also used in the experiments to test the performance of the proposed algorithm.


### 4.1. Test Functions and Simulation Results

#### 4.1.1. Test Functions

DTLZ2
(
M
)
. DTLZ2 is one of the test functions from a scalable test problems suite DTLZ formulated by K. Deb et al. [23], and none of the objectives is redundant in the problem. The motivation of choosing this test problem is to test whether the algorithm will remove any objective. If yes, it will indicate the algorithm is ineffective. We will show in the following experiment that the proposed algorithm does not remove any objective. An M-objective formulation of DTLZ2 is shown as follows.
(9)Minimizef1(x)=r(xM)cos(πx12)⋯cos(πxM-22)cos(πxM-12),f2(x)=r(xM)cos(πx12)⋯cos(πxM-22)sin(πxM-12),⋯fM-1(x)=r(xM)cos(πx12)sin(πx22),fM(x)=r(xM)sin(πx12),
where
(10)r(xM)=1+g(xM)=1+∑xi∈xM(xi-0.5)2,000000000000≤xi≤1,fori=1,2,…,n.The total number of decision variables isn=M+k-1, where k=10 is used in the experiments. The Pareto-optimal solutions correspond to xM*=0.5.DTLZ5
(
I
,
M
). In the DTLZ test suite, DTLZ5 is modified to construct a set of test problems where the dimensionality of the Pareto front is less than the original number of objectives [23–25]. In DTLZ5 (I,M) problems, I represents the actual dimensionality of the Pareto-optimal front and M represents the original number of objectives. The motivation of designing these test problems is to evaluate objective reduction techniques for many-objective optimization problems. The formulation of DTLZ5 (I,M) is given as follows.
(11)Minimizef1(x)=r(xM)cos(θ1)⋯cos(θM-2)cos(θM-1),f2(x)=r(xM)cos(θ1)⋯cos(θM-2)sin(θM-1),f3(x)=r(xM)cos(θ1)⋯sin(θM-2),⋯fM-1(x)=r(xM)cos(θ1)sin(θ2),fM(x)=r(xM)sin(θ1),
where
(12)r(xM)=1+g(xM)=1+∑xi∈xM(xi-0.5)2θi={π2xifori=1,…,I-1π4r(xM)(1+2g(xM)xi)fori=I,…,M-1subjectto∑j=0I-2fM-j2+2pifi2≥1,fori=1,…,(M-I+1),
where
(13)pi={M-Ifori=1(M-I+2)-ifori=2,…,(M-I+1)000000000000000≤xi≤1,fori=1,2,…,n.The total number of decision variables isn=M+k-1, where k=10 is used here. With regards to redundant objectives, all objectives with {f1,…,fM-I+1} are positively correlated, while each objective in {fM-I+2,…,fM} is conflicting with every other objective in the problem; Fτ={fk,fM-I+2,…,fM} defines the true POF [18], where k∈{1,2,…,M-I+1}.


#### 4.1.2. Parameter Setting Used in OC-ORA

The crossover and mutation parameters for OC-ORA used in the experiments are listed in Table1, and the experiments are done on different numbers of objectives for each test problem. The population size and the number of generations in different objective test problems are shown in Table 2. In calculating the self-information or entropy of an objective, we divide the interval on one objective into many subintervals. The number of subintervals is set as 20; that is, we will calculate the self-information or entropy of a discrete variable on 20 possible points, and the number of predefined clusters k is set from 2 to ⌊M⌋. In the process of objective reduction, the threshold θ [26] is set as 0.6.Table 1
Parameters used for OC-ORA algorithm.
Parameter
Value
SBX crossover probability
0.9
Crossover index
20
Polynomial mutation probability
0.1
Mutation index
20Table 2
The pop size and generations in different test problems.
Test problems
Pop size
Generations
DTLZ2(5)
200
300
DTLZ2(10)
300
500
DTLZ2 (20)
300
1000
DTLZ5 (2,5)
200
200
DTLZ5 (3,5)
200
200
DTLZ5 (2,10)
300
300
DTLZ5 (3,10)
300
300
DTLZ5 (5,10)
300
300
DTLZ5 (2,20)
500
500
DTLZ5 (5,20)
500
500For performance assessment, some evaluation criterions, such as computational complexity and the success rate in identifying the true PF, are used here to compare the performance of the different algorithms.


#### 4.1.3. Complexity Comparison of OC-ORA and Other Objective Reduction Algorithms

The computational complexity of the OC-ORA consists of three parts: executing the evolutionary multiobjective algorithm, calculating the interdependence coefficient matrix between pairs of objectives, and implementing the PAM clustering algorithm to reduce redundant objectives. The complexity of the proposed algorithm isO(gn2m)+O(v2m2+km2), where g is the number of generations for each run of NSGA-II, n is the size of the nondominated set, m is the number of objectives in the current nonredundant objective set, k is the number of clusters used in PAM clustering algorithm, and v is the number of subintervals in the calculation of mutual information. Generally, k is much smaller than v2, so the complexity of OC-ORA is simplified as O(gn2m)+O(v2m2). In contrast, the computational complexities of the compared objective reduction approaches are summarized in Table 3. Note that each of the objective reduction algorithm operates on the nondominated set and share the same complexity on obtaining the nondominated set; hence, it is unnecessary to consider the computational complexity O(gn2m) of obtaining the nondominated set in each objective reduction algorithm. Thus, the complexity of OC-ORA is simplified as O(v2m2). It can be seen from Table 3 that (1) the computational complexity of the exact algorithm for δ-MOSS is almost impractical since it is quadratic in n and exponential in m and the computational complexity of the greedy algorithm for δ-MOSS is likely to be more expensive. In summary, the complexity of δ-MOSS is the worst compared with other algorithms. (2) The complexity of the procedure of objective reduction in one iteration is listed in Table 3, which shows that the efficiency of OC-ORA is better than NL-MVU-PCA based reduction method. Besides, the population size and the number of generations of the proposed algorithm in one iteration of objective reduction are much less than those of the compared algorithms. For example, the population size and the number of generations are set to be 800 and 1000 in NL-MVU-PCA, which are much larger than those of the proposed algorithm. Although the iterations used by the proposed algorithm OC-ORA may be more than that used by NL-MVU-PCA because at each iteration, OC-ORA removes one redundant objective, while NL-MVU-PCA removes more than one the total number of individuals used by the proposed algorithm, which is a relatively fair metric to measure the computational complexity of an algorithm, is smaller than that used by NL-MVU-PCA. Thus, the computational complexity of the proposed algorithm is lower than that of the compared algorithms.Table 3
Complexity of the compared objective reduction algorithms.
Algorithm
Complexity
Deb and Saxena
(
1
) PCA based reduction
O
(
n
m
2
+
m
3
)
(
2
) NL-MVU-PCA based reduction
O
(
m
3
q
3
),whereqis  the  neighborhood  size
In  the  most  constrained  case,q=O(m)
δ
-
MOSS
(
1
)  Exact Algorithm
O
(
n
2
m
2
m
)
(
2
)  Greedy Algorithm
O
(
min
{
n
2
m
3
,
n
4
m
2
}
)
OC-ORA
O
(
v
2
m
2
)


#### 4.1.4. The Example Analysis on the Process of Objective Reduction

In order to verify the efficiency of interdependence coefficient matrix [26] in measuring the relation between objectives, we use the interdependence coefficient matrix to implement objective clustering and reduction on both redundant test functions DTLZ5 (3, 5) and nonredundant test functions DTLZ2 (5) problems. The processes of objective clustering and redundant objective removing are presented in Table 4.Table 4
(a) Inter-dependence coefficient matrix on DTLZ5 (3, 5). (b) Interdependence coefficient matrix on DTLZ2(5).
(a)
Interdependence coefficient matrixD based onFt={1,2,3,4,5}
Interdependence coefficient matrixD based onFt’={2,3,4,5}
[
0
0.3889
0.5332
1.2715
1.3065
0.3889
0
0.5031
1.2653
1.2640
0.5332
0.5031
0
1.3029
1.2857
1.2715
1.2653
1.3029
0
1.2245
1.3065
1.2640
1.2857
1.2245
0
]
[
0
0.3526
1.3326
1.3231
0.3526
0
1.3855
1.3430
1.3326
1.3855
0
1.3272
1.3231
1.3430
1.3272
0
]
(b)
Interdependence coefficient matrixD based onFt={1,2,3,4,5}
[
0
1.3222
1.3814
0.6513
1.3323
1.3222
0
0.7199
1.2414
0.7387
1.3814
0.7199
0
1.3630
1.3573
0.6513
1.2414
1.3630
0
1.2798
1.3323
0.7387
1.3573
1.2798
0
]In the original objective set in DTLZ5 (3, 5) isFt={1,2,3,4,5}. In order to estimate the correlation between each pair of objectives, the interdependence coefficient matrix is computed on the nondominated set generated by NSGAII. An interdependence coefficient matrix with order five is presented in the left part of Table 4(a), named D=(dij)5×5. According to the interdependence coefficient matrix, the objective clustering algorithm is carried out to divide the objective set Ft into different k clusters, where k is predetermined and set to 2. Thus, the original objective set Ft is divided into two subsets Ft1={1,2,3} and Ft2={4,5} by using the PAM clustering algorithm. Then, the objective reduction algorithm is performed to remove the redundant objective, where the first objective f1 is the redundant objective which should be removed from the current objective set, and thus the resulting nonredundant objective set is Ft′={2,3,4,5}. Afterwards, the next round of calculating the interdependence coefficient matrix in the new objective set Ft′={2,3,4,5} is started, and the matrix with order four is shown on the right part of Table 4(a). Through the new round of PAM clustering and objective reduction strategy, the second objective f2 satisfies the condition of redundant objective. Finally, after two iterations, the nonredundant objective set is Ft′′={3,4,5}, which is the true nonredundant objective set in DTLZ5 (3, 5).With nonredundant test functions DTLZ2 (5) problems, we calculate the interdependence coefficient matrix on original objective setFt={1,2,3,4,5}, shown in Table 4(b). In the process of objective clustering, the number k of clusters is also set to 2, and the original objective set Ft is divided into two subsets Ft1={1,4} and Ft2={2,3,5}. The minimum interdependence coefficient in two clusters is d14=0.6513, which represents that f1 and f4 are the most highly correlated objectives in Ft. According to the rule of identifying redundant objectives, the value 0.6513 is larger than threshold θ, so neither of them will be removed.


#### 4.1.5. Comparison of Success Rate in Identifying the True Nonredundant Objective SetFt

To test the performance of the proposed algorithm for objective reduction, two different kinds of the test problems with varying number of objectives are studied, including 10 test examples. For each test example, experiments are performed for 20 independent runs. Table5 summarizes the results of the success rate in identifying the true nonredundant objective set Ft with objective number increasing from 5 and 10 to 20. Meanwhile, we also compare the success rates of OC-ORA and linear objective reduction approach L-PCA [18]. The experiment results are shown as follows.Table 5
The success rate in identifying the true nonredundant objective setFt with two algorithms out of 20 runs.
Test problems
Success rate with OC-ORA
Success rate with L-PCA
DTLZ2(5)
20/20
20/20
DTLZ2(10)
20/20
19/20
DTLZ2(20)
19/20
14/20
DTLZ5 (2,5)
20/20
18/20
DTLZ5 (3,5)
20/20
19/20
DTLZ5 (2,10)
19/20
7/20
DTLZ5 (3,10)
20/20
2/20
DTLZ5 (5,10)
17/20
3/20
DTLZ5 (2,20)
18/20
2/20
DTLZ5 (5,20)
15/20
3/20For DTLZ2(M), it can be seen from Table 5 that OC-ORA can identify the true Pareto front accurately with success rate of 100% for 5 and 10 objectives, respectively, and 95% for 20 objectives. The success rates are much higher than those obtained by L-PCA. In nonredundant problems, the threshold θ avoids removing any nonredundant objective and tries to keep all of objectives.For all instances of DTLZ5(I,M), it also can be seen from Table 5 that the success rates obtained by OC-ORA are obviously much higher than those obtained by L-PCA. The superiority of OC-ORA is that it could express more comprehensive correlation between objectives, especially for nonlinear relationships of objectives. The experimental results indicate that OC-ORA could find the true nonredundant objective set efficiently.The limitation of the proposed algorithm is that the number of clustersk must be smaller than the number of nonredundant objective in test problem. When the number of clusters is more than the number of nonredundant objectives, the objective reduction strategy is not applicable.


### 4.2. An Engineering Problem: Storm Drainage Systems

This is an optimal planning problem for storm drainage systems in urban areas, which is proposed by Musselman and Talavage [27]. The problem consists of 5 objectives and 7 constraints. The analytical model of the problem is given in Table 6. In order to identify the redundant objectives of the problem, the proposed algorithm is carried out. The population size is set to 200, and the generation is set to 200. In the original objective set Ft={1,2,3,4,5}, the interdependence coefficient matrix based on the original objective set is shown in Table 7. After calculating the interdependence coefficient matrix, we will execute objective clustering process to divide the original objective set Ft into two subsets Ft1={1,2,3} and Ft2={4,5}. Comparing the minimum interdependence coefficient in each cluster, the cluster Ft1 is identified as the most highly correlated cluster, and the interdependence coefficient between f1 and f3 is the minimum. According to the objective reduction rule, f1 is considered as the redundant objective, and thus the corresponding nonredundant objective set is Ft′={2,3,4,5}. Thus, Ft′ can be used to reconstruct the Pareto front.Table 6
Analytical model of the storm drainage problem.
Name
Function expression
Minimize 5 objectives
(
1
) Drainage network cost
f
1
(
x
)
=
106780.37
(
x
2
+
x
3
)
+
61704.67
(
2
) Storage facility cost
f
2
(
x
)
=
3000
x
1
(
3
) Treatment facility cost
f
3
(
x
)
=
(
305700
/
(
0.06
*
2289
)
∧
0.65
)
*
2289
x
2
(
4
) Expected flood damage cost
f
4
(
x
)
=
250
*
2289
*
exp
(
-
39.75
x
2
+
9.9
x
3
+
2.74
)
(
5
) Expected economic loss cost due to flood
f
5
(
x
)
=
25
*
(
1.39
/
(
x
1
x
2
)
+
4930
x
3
-
80
)
Subject to 7 constraints
(
1
)  Average no. of floods/year
g
1
(
x
)
=
0.00139
/
x
1
x
2
+
4.94
x
3
-
0.08
≤
1
(
2
)  Probability of exceeding a flood depth of 0.01 basin inches
g
2
(
x
)
=
0.0000306
/
x
1
x
2
+
0.1082
x
3
-
0.00986
≤
0.10
(
3
) Average no. of pounds/year of suspended solids
g
3
(
x
)
=
12.307
/
x
1
x
2
+
49408.24
x
3
-
4051.02
≤
50000
(
4
) Average no. of pounds/year of settleable solids
g
4
(
x
)
=
2.098
/
x
1
x
2
+
8046.33
x
3
-
696.71
≤
16000
(
5
) Average no. of pounds/year of  BOD
g
5
(
x
)
=
2.138
/
x
1
x
2
+
7883.39
x
3
-
705.04
≤
10000
(
6
) Average no. of pounds/year of  N
g
6
(
x
)
=
0.417
/
x
1
x
2
+
1721.36
x
3
-
136.54
≤
2000
(
7
) Average no. of pounds/year of  PO4
g
7
(
x
)
=
0.164
/
x
1
x
2
+
631.13
x
3
-
54.48
≤
550
where0.01≤x1≤0.45, 0.01≤x2,x3≤0.10Table 7
The interdependence coefficient matrix based on original objective set of storm drainage problem.
Interdependence coefficient matrix based onFt={1,2,3,4,5}
[
0
1.3093
0.4905
1.4496
1.2137
1.3093
0
0.6419
1.2821
1.2714
0.4905
0.6419
0
1.5131
1.2792
1.4494
1.2821
1.5131
0
0.6340
1.2137
1.2714
1.2792
0.6340
0
]To validate this result, parallel coordinate plot is borrowed here to visualize the nondominated solution set with more objectives in a figure. It involves plotting the normalized objective values of the nondominated solutions onto parallel axes, one per normalized objective. The function values in every objective for each nondominated solution are connected by a line segment. The parallel coordinate plots corresponding to the original set of objectivesFτ={1,2,3,4,5} and the reduced set Fτ′={2,3,4,5} are shown in Figures 3(a) and 3(b), respectively. Figure 3(a) shows the parallel coordinate plot corresponding to the original set of objectives, and Figure 3(b) refers to the reduced set. It can be seen from Figure 3 that parallel coordinate plot corresponding to the reduced set of objectives closely matches with that obtained using the original set of objectives. This illustrates that the omitting objective f1 does not affect non-nominated set, and the reduced set of objectives Fτ′={2,3,4,5} is enough to obtain the Pareto front for this problem.Parallel coordinate plots for storm drainage systems using various combinations of objectives. (a) The original set of objectivesFτ={1,2,3,4,5} are considered. (b) The reduced set Fτ′={2,3,4,5} is considered.
(a)
(b)


## 4.1. Test Functions and Simulation Results

### 4.1.1. Test Functions

DTLZ2
(
M
)
. DTLZ2 is one of the test functions from a scalable test problems suite DTLZ formulated by K. Deb et al. [23], and none of the objectives is redundant in the problem. The motivation of choosing this test problem is to test whether the algorithm will remove any objective. If yes, it will indicate the algorithm is ineffective. We will show in the following experiment that the proposed algorithm does not remove any objective. An M-objective formulation of DTLZ2 is shown as follows.
(9)Minimizef1(x)=r(xM)cos(πx12)⋯cos(πxM-22)cos(πxM-12),f2(x)=r(xM)cos(πx12)⋯cos(πxM-22)sin(πxM-12),⋯fM-1(x)=r(xM)cos(πx12)sin(πx22),fM(x)=r(xM)sin(πx12),
where
(10)r(xM)=1+g(xM)=1+∑xi∈xM(xi-0.5)2,000000000000≤xi≤1,fori=1,2,…,n.The total number of decision variables isn=M+k-1, where k=10 is used in the experiments. The Pareto-optimal solutions correspond to xM*=0.5.DTLZ5
(
I
,
M
). In the DTLZ test suite, DTLZ5 is modified to construct a set of test problems where the dimensionality of the Pareto front is less than the original number of objectives [23–25]. In DTLZ5 (I,M) problems, I represents the actual dimensionality of the Pareto-optimal front and M represents the original number of objectives. The motivation of designing these test problems is to evaluate objective reduction techniques for many-objective optimization problems. The formulation of DTLZ5 (I,M) is given as follows.
(11)Minimizef1(x)=r(xM)cos(θ1)⋯cos(θM-2)cos(θM-1),f2(x)=r(xM)cos(θ1)⋯cos(θM-2)sin(θM-1),f3(x)=r(xM)cos(θ1)⋯sin(θM-2),⋯fM-1(x)=r(xM)cos(θ1)sin(θ2),fM(x)=r(xM)sin(θ1),
where
(12)r(xM)=1+g(xM)=1+∑xi∈xM(xi-0.5)2θi={π2xifori=1,…,I-1π4r(xM)(1+2g(xM)xi)fori=I,…,M-1subjectto∑j=0I-2fM-j2+2pifi2≥1,fori=1,…,(M-I+1),
where
(13)pi={M-Ifori=1(M-I+2)-ifori=2,…,(M-I+1)000000000000000≤xi≤1,fori=1,2,…,n.The total number of decision variables isn=M+k-1, where k=10 is used here. With regards to redundant objectives, all objectives with {f1,…,fM-I+1} are positively correlated, while each objective in {fM-I+2,…,fM} is conflicting with every other objective in the problem; Fτ={fk,fM-I+2,…,fM} defines the true POF [18], where k∈{1,2,…,M-I+1}.


### 4.1.2. Parameter Setting Used in OC-ORA

The crossover and mutation parameters for OC-ORA used in the experiments are listed in Table1, and the experiments are done on different numbers of objectives for each test problem. The population size and the number of generations in different objective test problems are shown in Table 2. In calculating the self-information or entropy of an objective, we divide the interval on one objective into many subintervals. The number of subintervals is set as 20; that is, we will calculate the self-information or entropy of a discrete variable on 20 possible points, and the number of predefined clusters k is set from 2 to ⌊M⌋. In the process of objective reduction, the threshold θ [26] is set as 0.6.Table 1
Parameters used for OC-ORA algorithm.
Parameter
Value
SBX crossover probability
0.9
Crossover index
20
Polynomial mutation probability
0.1
Mutation index
20Table 2
The pop size and generations in different test problems.
Test problems
Pop size
Generations
DTLZ2(5)
200
300
DTLZ2(10)
300
500
DTLZ2 (20)
300
1000
DTLZ5 (2,5)
200
200
DTLZ5 (3,5)
200
200
DTLZ5 (2,10)
300
300
DTLZ5 (3,10)
300
300
DTLZ5 (5,10)
300
300
DTLZ5 (2,20)
500
500
DTLZ5 (5,20)
500
500For performance assessment, some evaluation criterions, such as computational complexity and the success rate in identifying the true PF, are used here to compare the performance of the different algorithms.


### 4.1.3. Complexity Comparison of OC-ORA and Other Objective Reduction Algorithms

The computational complexity of the OC-ORA consists of three parts: executing the evolutionary multiobjective algorithm, calculating the interdependence coefficient matrix between pairs of objectives, and implementing the PAM clustering algorithm to reduce redundant objectives. The complexity of the proposed algorithm isO(gn2m)+O(v2m2+km2), where g is the number of generations for each run of NSGA-II, n is the size of the nondominated set, m is the number of objectives in the current nonredundant objective set, k is the number of clusters used in PAM clustering algorithm, and v is the number of subintervals in the calculation of mutual information. Generally, k is much smaller than v2, so the complexity of OC-ORA is simplified as O(gn2m)+O(v2m2). In contrast, the computational complexities of the compared objective reduction approaches are summarized in Table 3. Note that each of the objective reduction algorithm operates on the nondominated set and share the same complexity on obtaining the nondominated set; hence, it is unnecessary to consider the computational complexity O(gn2m) of obtaining the nondominated set in each objective reduction algorithm. Thus, the complexity of OC-ORA is simplified as O(v2m2). It can be seen from Table 3 that (1) the computational complexity of the exact algorithm for δ-MOSS is almost impractical since it is quadratic in n and exponential in m and the computational complexity of the greedy algorithm for δ-MOSS is likely to be more expensive. In summary, the complexity of δ-MOSS is the worst compared with other algorithms. (2) The complexity of the procedure of objective reduction in one iteration is listed in Table 3, which shows that the efficiency of OC-ORA is better than NL-MVU-PCA based reduction method. Besides, the population size and the number of generations of the proposed algorithm in one iteration of objective reduction are much less than those of the compared algorithms. For example, the population size and the number of generations are set to be 800 and 1000 in NL-MVU-PCA, which are much larger than those of the proposed algorithm. Although the iterations used by the proposed algorithm OC-ORA may be more than that used by NL-MVU-PCA because at each iteration, OC-ORA removes one redundant objective, while NL-MVU-PCA removes more than one the total number of individuals used by the proposed algorithm, which is a relatively fair metric to measure the computational complexity of an algorithm, is smaller than that used by NL-MVU-PCA. Thus, the computational complexity of the proposed algorithm is lower than that of the compared algorithms.Table 3
Complexity of the compared objective reduction algorithms.
Algorithm
Complexity
Deb and Saxena
(
1
) PCA based reduction
O
(
n
m
2
+
m
3
)
(
2
) NL-MVU-PCA based reduction
O
(
m
3
q
3
),whereqis  the  neighborhood  size
In  the  most  constrained  case,q=O(m)
δ
-
MOSS
(
1
)  Exact Algorithm
O
(
n
2
m
2
m
)
(
2
)  Greedy Algorithm
O
(
min
{
n
2
m
3
,
n
4
m
2
}
)
OC-ORA
O
(
v
2
m
2
)


### 4.1.4. The Example Analysis on the Process of Objective Reduction

In order to verify the efficiency of interdependence coefficient matrix [26] in measuring the relation between objectives, we use the interdependence coefficient matrix to implement objective clustering and reduction on both redundant test functions DTLZ5 (3, 5) and nonredundant test functions DTLZ2 (5) problems. The processes of objective clustering and redundant objective removing are presented in Table 4.Table 4
(a) Inter-dependence coefficient matrix on DTLZ5 (3, 5). (b) Interdependence coefficient matrix on DTLZ2(5).
(a)
Interdependence coefficient matrixD based onFt={1,2,3,4,5}
Interdependence coefficient matrixD based onFt’={2,3,4,5}
[
0
0.3889
0.5332
1.2715
1.3065
0.3889
0
0.5031
1.2653
1.2640
0.5332
0.5031
0
1.3029
1.2857
1.2715
1.2653
1.3029
0
1.2245
1.3065
1.2640
1.2857
1.2245
0
]
[
0
0.3526
1.3326
1.3231
0.3526
0
1.3855
1.3430
1.3326
1.3855
0
1.3272
1.3231
1.3430
1.3272
0
]
(b)
Interdependence coefficient matrixD based onFt={1,2,3,4,5}
[
0
1.3222
1.3814
0.6513
1.3323
1.3222
0
0.7199
1.2414
0.7387
1.3814
0.7199
0
1.3630
1.3573
0.6513
1.2414
1.3630
0
1.2798
1.3323
0.7387
1.3573
1.2798
0
]In the original objective set in DTLZ5 (3, 5) isFt={1,2,3,4,5}. In order to estimate the correlation between each pair of objectives, the interdependence coefficient matrix is computed on the nondominated set generated by NSGAII. An interdependence coefficient matrix with order five is presented in the left part of Table 4(a), named D=(dij)5×5. According to the interdependence coefficient matrix, the objective clustering algorithm is carried out to divide the objective set Ft into different k clusters, where k is predetermined and set to 2. Thus, the original objective set Ft is divided into two subsets Ft1={1,2,3} and Ft2={4,5} by using the PAM clustering algorithm. Then, the objective reduction algorithm is performed to remove the redundant objective, where the first objective f1 is the redundant objective which should be removed from the current objective set, and thus the resulting nonredundant objective set is Ft′={2,3,4,5}. Afterwards, the next round of calculating the interdependence coefficient matrix in the new objective set Ft′={2,3,4,5} is started, and the matrix with order four is shown on the right part of Table 4(a). Through the new round of PAM clustering and objective reduction strategy, the second objective f2 satisfies the condition of redundant objective. Finally, after two iterations, the nonredundant objective set is Ft′′={3,4,5}, which is the true nonredundant objective set in DTLZ5 (3, 5).With nonredundant test functions DTLZ2 (5) problems, we calculate the interdependence coefficient matrix on original objective setFt={1,2,3,4,5}, shown in Table 4(b). In the process of objective clustering, the number k of clusters is also set to 2, and the original objective set Ft is divided into two subsets Ft1={1,4} and Ft2={2,3,5}. The minimum interdependence coefficient in two clusters is d14=0.6513, which represents that f1 and f4 are the most highly correlated objectives in Ft. According to the rule of identifying redundant objectives, the value 0.6513 is larger than threshold θ, so neither of them will be removed.


### 4.1.5. Comparison of Success Rate in Identifying the True Nonredundant Objective SetFt

To test the performance of the proposed algorithm for objective reduction, two different kinds of the test problems with varying number of objectives are studied, including 10 test examples. For each test example, experiments are performed for 20 independent runs. Table5 summarizes the results of the success rate in identifying the true nonredundant objective set Ft with objective number increasing from 5 and 10 to 20. Meanwhile, we also compare the success rates of OC-ORA and linear objective reduction approach L-PCA [18]. The experiment results are shown as follows.Table 5
The success rate in identifying the true nonredundant objective setFt with two algorithms out of 20 runs.
Test problems
Success rate with OC-ORA
Success rate with L-PCA
DTLZ2(5)
20/20
20/20
DTLZ2(10)
20/20
19/20
DTLZ2(20)
19/20
14/20
DTLZ5 (2,5)
20/20
18/20
DTLZ5 (3,5)
20/20
19/20
DTLZ5 (2,10)
19/20
7/20
DTLZ5 (3,10)
20/20
2/20
DTLZ5 (5,10)
17/20
3/20
DTLZ5 (2,20)
18/20
2/20
DTLZ5 (5,20)
15/20
3/20For DTLZ2(M), it can be seen from Table 5 that OC-ORA can identify the true Pareto front accurately with success rate of 100% for 5 and 10 objectives, respectively, and 95% for 20 objectives. The success rates are much higher than those obtained by L-PCA. In nonredundant problems, the threshold θ avoids removing any nonredundant objective and tries to keep all of objectives.For all instances of DTLZ5(I,M), it also can be seen from Table 5 that the success rates obtained by OC-ORA are obviously much higher than those obtained by L-PCA. The superiority of OC-ORA is that it could express more comprehensive correlation between objectives, especially for nonlinear relationships of objectives. The experimental results indicate that OC-ORA could find the true nonredundant objective set efficiently.The limitation of the proposed algorithm is that the number of clustersk must be smaller than the number of nonredundant objective in test problem. When the number of clusters is more than the number of nonredundant objectives, the objective reduction strategy is not applicable.


## 4.1.1. Test Functions

DTLZ2
(
M
)
. DTLZ2 is one of the test functions from a scalable test problems suite DTLZ formulated by K. Deb et al. [23], and none of the objectives is redundant in the problem. The motivation of choosing this test problem is to test whether the algorithm will remove any objective. If yes, it will indicate the algorithm is ineffective. We will show in the following experiment that the proposed algorithm does not remove any objective. An M-objective formulation of DTLZ2 is shown as follows.
(9)Minimizef1(x)=r(xM)cos(πx12)⋯cos(πxM-22)cos(πxM-12),f2(x)=r(xM)cos(πx12)⋯cos(πxM-22)sin(πxM-12),⋯fM-1(x)=r(xM)cos(πx12)sin(πx22),fM(x)=r(xM)sin(πx12),
where
(10)r(xM)=1+g(xM)=1+∑xi∈xM(xi-0.5)2,000000000000≤xi≤1,fori=1,2,…,n.The total number of decision variables isn=M+k-1, where k=10 is used in the experiments. The Pareto-optimal solutions correspond to xM*=0.5.DTLZ5
(
I
,
M
). In the DTLZ test suite, DTLZ5 is modified to construct a set of test problems where the dimensionality of the Pareto front is less than the original number of objectives [23–25]. In DTLZ5 (I,M) problems, I represents the actual dimensionality of the Pareto-optimal front and M represents the original number of objectives. The motivation of designing these test problems is to evaluate objective reduction techniques for many-objective optimization problems. The formulation of DTLZ5 (I,M) is given as follows.
(11)Minimizef1(x)=r(xM)cos(θ1)⋯cos(θM-2)cos(θM-1),f2(x)=r(xM)cos(θ1)⋯cos(θM-2)sin(θM-1),f3(x)=r(xM)cos(θ1)⋯sin(θM-2),⋯fM-1(x)=r(xM)cos(θ1)sin(θ2),fM(x)=r(xM)sin(θ1),
where
(12)r(xM)=1+g(xM)=1+∑xi∈xM(xi-0.5)2θi={π2xifori=1,…,I-1π4r(xM)(1+2g(xM)xi)fori=I,…,M-1subjectto∑j=0I-2fM-j2+2pifi2≥1,fori=1,…,(M-I+1),
where
(13)pi={M-Ifori=1(M-I+2)-ifori=2,…,(M-I+1)000000000000000≤xi≤1,fori=1,2,…,n.The total number of decision variables isn=M+k-1, where k=10 is used here. With regards to redundant objectives, all objectives with {f1,…,fM-I+1} are positively correlated, while each objective in {fM-I+2,…,fM} is conflicting with every other objective in the problem; Fτ={fk,fM-I+2,…,fM} defines the true POF [18], where k∈{1,2,…,M-I+1}.


## 4.1.2. Parameter Setting Used in OC-ORA

The crossover and mutation parameters for OC-ORA used in the experiments are listed in Table1, and the experiments are done on different numbers of objectives for each test problem. The population size and the number of generations in different objective test problems are shown in Table 2. In calculating the self-information or entropy of an objective, we divide the interval on one objective into many subintervals. The number of subintervals is set as 20; that is, we will calculate the self-information or entropy of a discrete variable on 20 possible points, and the number of predefined clusters k is set from 2 to ⌊M⌋. In the process of objective reduction, the threshold θ [26] is set as 0.6.Table 1
Parameters used for OC-ORA algorithm.
Parameter
Value
SBX crossover probability
0.9
Crossover index
20
Polynomial mutation probability
0.1
Mutation index
20Table 2
The pop size and generations in different test problems.
Test problems
Pop size
Generations
DTLZ2(5)
200
300
DTLZ2(10)
300
500
DTLZ2 (20)
300
1000
DTLZ5 (2,5)
200
200
DTLZ5 (3,5)
200
200
DTLZ5 (2,10)
300
300
DTLZ5 (3,10)
300
300
DTLZ5 (5,10)
300
300
DTLZ5 (2,20)
500
500
DTLZ5 (5,20)
500
500For performance assessment, some evaluation criterions, such as computational complexity and the success rate in identifying the true PF, are used here to compare the performance of the different algorithms.


## 4.1.3. Complexity Comparison of OC-ORA and Other Objective Reduction Algorithms

The computational complexity of the OC-ORA consists of three parts: executing the evolutionary multiobjective algorithm, calculating the interdependence coefficient matrix between pairs of objectives, and implementing the PAM clustering algorithm to reduce redundant objectives. The complexity of the proposed algorithm isO(gn2m)+O(v2m2+km2), where g is the number of generations for each run of NSGA-II, n is the size of the nondominated set, m is the number of objectives in the current nonredundant objective set, k is the number of clusters used in PAM clustering algorithm, and v is the number of subintervals in the calculation of mutual information. Generally, k is much smaller than v2, so the complexity of OC-ORA is simplified as O(gn2m)+O(v2m2). In contrast, the computational complexities of the compared objective reduction approaches are summarized in Table 3. Note that each of the objective reduction algorithm operates on the nondominated set and share the same complexity on obtaining the nondominated set; hence, it is unnecessary to consider the computational complexity O(gn2m) of obtaining the nondominated set in each objective reduction algorithm. Thus, the complexity of OC-ORA is simplified as O(v2m2). It can be seen from Table 3 that (1) the computational complexity of the exact algorithm for δ-MOSS is almost impractical since it is quadratic in n and exponential in m and the computational complexity of the greedy algorithm for δ-MOSS is likely to be more expensive. In summary, the complexity of δ-MOSS is the worst compared with other algorithms. (2) The complexity of the procedure of objective reduction in one iteration is listed in Table 3, which shows that the efficiency of OC-ORA is better than NL-MVU-PCA based reduction method. Besides, the population size and the number of generations of the proposed algorithm in one iteration of objective reduction are much less than those of the compared algorithms. For example, the population size and the number of generations are set to be 800 and 1000 in NL-MVU-PCA, which are much larger than those of the proposed algorithm. Although the iterations used by the proposed algorithm OC-ORA may be more than that used by NL-MVU-PCA because at each iteration, OC-ORA removes one redundant objective, while NL-MVU-PCA removes more than one the total number of individuals used by the proposed algorithm, which is a relatively fair metric to measure the computational complexity of an algorithm, is smaller than that used by NL-MVU-PCA. Thus, the computational complexity of the proposed algorithm is lower than that of the compared algorithms.Table 3
Complexity of the compared objective reduction algorithms.
Algorithm
Complexity
Deb and Saxena
(
1
) PCA based reduction
O
(
n
m
2
+
m
3
)
(
2
) NL-MVU-PCA based reduction
O
(
m
3
q
3
),whereqis  the  neighborhood  size
In  the  most  constrained  case,q=O(m)
δ
-
MOSS
(
1
)  Exact Algorithm
O
(
n
2
m
2
m
)
(
2
)  Greedy Algorithm
O
(
min
{
n
2
m
3
,
n
4
m
2
}
)
OC-ORA
O
(
v
2
m
2
)


## 4.1.4. The Example Analysis on the Process of Objective Reduction

In order to verify the efficiency of interdependence coefficient matrix [26] in measuring the relation between objectives, we use the interdependence coefficient matrix to implement objective clustering and reduction on both redundant test functions DTLZ5 (3, 5) and nonredundant test functions DTLZ2 (5) problems. The processes of objective clustering and redundant objective removing are presented in Table 4.Table 4
(a) Inter-dependence coefficient matrix on DTLZ5 (3, 5). (b) Interdependence coefficient matrix on DTLZ2(5).
(a)
Interdependence coefficient matrixD based onFt={1,2,3,4,5}
Interdependence coefficient matrixD based onFt’={2,3,4,5}
[
0
0.3889
0.5332
1.2715
1.3065
0.3889
0
0.5031
1.2653
1.2640
0.5332
0.5031
0
1.3029
1.2857
1.2715
1.2653
1.3029
0
1.2245
1.3065
1.2640
1.2857
1.2245
0
]
[
0
0.3526
1.3326
1.3231
0.3526
0
1.3855
1.3430
1.3326
1.3855
0
1.3272
1.3231
1.3430
1.3272
0
]
(b)
Interdependence coefficient matrixD based onFt={1,2,3,4,5}
[
0
1.3222
1.3814
0.6513
1.3323
1.3222
0
0.7199
1.2414
0.7387
1.3814
0.7199
0
1.3630
1.3573
0.6513
1.2414
1.3630
0
1.2798
1.3323
0.7387
1.3573
1.2798
0
]In the original objective set in DTLZ5 (3, 5) isFt={1,2,3,4,5}. In order to estimate the correlation between each pair of objectives, the interdependence coefficient matrix is computed on the nondominated set generated by NSGAII. An interdependence coefficient matrix with order five is presented in the left part of Table 4(a), named D=(dij)5×5. According to the interdependence coefficient matrix, the objective clustering algorithm is carried out to divide the objective set Ft into different k clusters, where k is predetermined and set to 2. Thus, the original objective set Ft is divided into two subsets Ft1={1,2,3} and Ft2={4,5} by using the PAM clustering algorithm. Then, the objective reduction algorithm is performed to remove the redundant objective, where the first objective f1 is the redundant objective which should be removed from the current objective set, and thus the resulting nonredundant objective set is Ft′={2,3,4,5}. Afterwards, the next round of calculating the interdependence coefficient matrix in the new objective set Ft′={2,3,4,5} is started, and the matrix with order four is shown on the right part of Table 4(a). Through the new round of PAM clustering and objective reduction strategy, the second objective f2 satisfies the condition of redundant objective. Finally, after two iterations, the nonredundant objective set is Ft′′={3,4,5}, which is the true nonredundant objective set in DTLZ5 (3, 5).With nonredundant test functions DTLZ2 (5) problems, we calculate the interdependence coefficient matrix on original objective setFt={1,2,3,4,5}, shown in Table 4(b). In the process of objective clustering, the number k of clusters is also set to 2, and the original objective set Ft is divided into two subsets Ft1={1,4} and Ft2={2,3,5}. The minimum interdependence coefficient in two clusters is d14=0.6513, which represents that f1 and f4 are the most highly correlated objectives in Ft. According to the rule of identifying redundant objectives, the value 0.6513 is larger than threshold θ, so neither of them will be removed.


## 4.1.5. Comparison of Success Rate in Identifying the True Nonredundant Objective SetFt

To test the performance of the proposed algorithm for objective reduction, two different kinds of the test problems with varying number of objectives are studied, including 10 test examples. For each test example, experiments are performed for 20 independent runs. Table5 summarizes the results of the success rate in identifying the true nonredundant objective set Ft with objective number increasing from 5 and 10 to 20. Meanwhile, we also compare the success rates of OC-ORA and linear objective reduction approach L-PCA [18]. The experiment results are shown as follows.Table 5
The success rate in identifying the true nonredundant objective setFt with two algorithms out of 20 runs.
Test problems
Success rate with OC-ORA
Success rate with L-PCA
DTLZ2(5)
20/20
20/20
DTLZ2(10)
20/20
19/20
DTLZ2(20)
19/20
14/20
DTLZ5 (2,5)
20/20
18/20
DTLZ5 (3,5)
20/20
19/20
DTLZ5 (2,10)
19/20
7/20
DTLZ5 (3,10)
20/20
2/20
DTLZ5 (5,10)
17/20
3/20
DTLZ5 (2,20)
18/20
2/20
DTLZ5 (5,20)
15/20
3/20For DTLZ2(M), it can be seen from Table 5 that OC-ORA can identify the true Pareto front accurately with success rate of 100% for 5 and 10 objectives, respectively, and 95% for 20 objectives. The success rates are much higher than those obtained by L-PCA. In nonredundant problems, the threshold θ avoids removing any nonredundant objective and tries to keep all of objectives.For all instances of DTLZ5(I,M), it also can be seen from Table 5 that the success rates obtained by OC-ORA are obviously much higher than those obtained by L-PCA. The superiority of OC-ORA is that it could express more comprehensive correlation between objectives, especially for nonlinear relationships of objectives. The experimental results indicate that OC-ORA could find the true nonredundant objective set efficiently.The limitation of the proposed algorithm is that the number of clustersk must be smaller than the number of nonredundant objective in test problem. When the number of clusters is more than the number of nonredundant objectives, the objective reduction strategy is not applicable.


## 4.2. An Engineering Problem: Storm Drainage Systems

This is an optimal planning problem for storm drainage systems in urban areas, which is proposed by Musselman and Talavage [27]. The problem consists of 5 objectives and 7 constraints. The analytical model of the problem is given in Table 6. In order to identify the redundant objectives of the problem, the proposed algorithm is carried out. The population size is set to 200, and the generation is set to 200. In the original objective set Ft={1,2,3,4,5}, the interdependence coefficient matrix based on the original objective set is shown in Table 7. After calculating the interdependence coefficient matrix, we will execute objective clustering process to divide the original objective set Ft into two subsets Ft1={1,2,3} and Ft2={4,5}. Comparing the minimum interdependence coefficient in each cluster, the cluster Ft1 is identified as the most highly correlated cluster, and the interdependence coefficient between f1 and f3 is the minimum. According to the objective reduction rule, f1 is considered as the redundant objective, and thus the corresponding nonredundant objective set is Ft′={2,3,4,5}. Thus, Ft′ can be used to reconstruct the Pareto front.Table 6
Analytical model of the storm drainage problem.
Name
Function expression
Minimize 5 objectives
(
1
) Drainage network cost
f
1
(
x
)
=
106780.37
(
x
2
+
x
3
)
+
61704.67
(
2
) Storage facility cost
f
2
(
x
)
=
3000
x
1
(
3
) Treatment facility cost
f
3
(
x
)
=
(
305700
/
(
0.06
*
2289
)
∧
0.65
)
*
2289
x
2
(
4
) Expected flood damage cost
f
4
(
x
)
=
250
*
2289
*
exp
(
-
39.75
x
2
+
9.9
x
3
+
2.74
)
(
5
) Expected economic loss cost due to flood
f
5
(
x
)
=
25
*
(
1.39
/
(
x
1
x
2
)
+
4930
x
3
-
80
)
Subject to 7 constraints
(
1
)  Average no. of floods/year
g
1
(
x
)
=
0.00139
/
x
1
x
2
+
4.94
x
3
-
0.08
≤
1
(
2
)  Probability of exceeding a flood depth of 0.01 basin inches
g
2
(
x
)
=
0.0000306
/
x
1
x
2
+
0.1082
x
3
-
0.00986
≤
0.10
(
3
) Average no. of pounds/year of suspended solids
g
3
(
x
)
=
12.307
/
x
1
x
2
+
49408.24
x
3
-
4051.02
≤
50000
(
4
) Average no. of pounds/year of settleable solids
g
4
(
x
)
=
2.098
/
x
1
x
2
+
8046.33
x
3
-
696.71
≤
16000
(
5
) Average no. of pounds/year of  BOD
g
5
(
x
)
=
2.138
/
x
1
x
2
+
7883.39
x
3
-
705.04
≤
10000
(
6
) Average no. of pounds/year of  N
g
6
(
x
)
=
0.417
/
x
1
x
2
+
1721.36
x
3
-
136.54
≤
2000
(
7
) Average no. of pounds/year of  PO4
g
7
(
x
)
=
0.164
/
x
1
x
2
+
631.13
x
3
-
54.48
≤
550
where0.01≤x1≤0.45, 0.01≤x2,x3≤0.10Table 7
The interdependence coefficient matrix based on original objective set of storm drainage problem.
Interdependence coefficient matrix based onFt={1,2,3,4,5}
[
0
1.3093
0.4905
1.4496
1.2137
1.3093
0
0.6419
1.2821
1.2714
0.4905
0.6419
0
1.5131
1.2792
1.4494
1.2821
1.5131
0
0.6340
1.2137
1.2714
1.2792
0.6340
0
]To validate this result, parallel coordinate plot is borrowed here to visualize the nondominated solution set with more objectives in a figure. It involves plotting the normalized objective values of the nondominated solutions onto parallel axes, one per normalized objective. The function values in every objective for each nondominated solution are connected by a line segment. The parallel coordinate plots corresponding to the original set of objectivesFτ={1,2,3,4,5} and the reduced set Fτ′={2,3,4,5} are shown in Figures 3(a) and 3(b), respectively. Figure 3(a) shows the parallel coordinate plot corresponding to the original set of objectives, and Figure 3(b) refers to the reduced set. It can be seen from Figure 3 that parallel coordinate plot corresponding to the reduced set of objectives closely matches with that obtained using the original set of objectives. This illustrates that the omitting objective f1 does not affect non-nominated set, and the reduced set of objectives Fτ′={2,3,4,5} is enough to obtain the Pareto front for this problem.Parallel coordinate plots for storm drainage systems using various combinations of objectives. (a) The original set of objectivesFτ={1,2,3,4,5} are considered. (b) The reduced set Fτ′={2,3,4,5} is considered.
(a)
(b)


## 5. Conclusion and Future Work

In this paper, a novel method has been proposed to identify the true nonredundant objective set in many-objective problems. In order to overcome the defects of traditional methods in quantitative representation of the relation between a pair of objectives, we adopt a new metric, interdependence coefficient, by using the union of mutual information and correlation coefficient to measure the correlation between objectives. In addition, a new objective reduction strategy is investigated in accordance with the results of PAM clustering algorithm.The efficiency of the proposed approach is demonstrated by experiments on two kinds of benchmark test problems including 10 test instances and a real engineering practice problem, where the number of objectives tested is from 5 to 20. Moreover, a comparative analysis of computational complexity and success rate between the proposed algorithm and the correlation matrix-based algorithms has been made. All the results show that the proposed algorithm performs well in finding the true nonredundant objective set and outperforms the compared algorithm.A number of future works can be further conducted from current work. First, the strategy of removing redundant objective can be further enhanced by designing a specific method, which should avoid the limitation of the provision of the cluster numberk. Also, it is important to realize that for many-objective problems, different parts of the Pareto front may give different non-redundant objective set. In such a case, the objective space needs to divide many subregions to discuss.



---

*Source: 584909-2013-05-12.xml*