Multiobjective Differential Evolution Enhanced with Principle Component Analysis for Constrained Optimization Wei Huang a, Tao Xu b, Kangshun Li c, Jun He d, a Tianjin Key Laboratory of Intelligent and

•0 views•17 pages

Previous

Next

All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.

Documenttranscript

Multiobjective Differential Evolution Enhanced with Principle Component Analysis for Constrained Optimization Wei Huang a, Tao Xu b, Kangshun Li c, Jun He d, a Tianjin Key Laboratory of Intelligent and Novel Software Technology, and School of Computer Science and Engineering, Tianjin University of Technology, China b Department of Computer Science, Aberystwyth University, Aberystwyth SY23 3DB, UK c College of Mathematics and Informatics, South China Agricultural University, Guangzhou 50642, China d School of Science and Technology, Nottingham Trent University, Nottingham NG 8NS, UK arxiv: v2 [cs.ne] 24 Aug 209 Abstract Multiobjective evolutionary algorithms (MOEAs) have been successfully applied to a number of constrained optimization problems. Many of them adopt mutation and crossover operators from differential evolution. However, these operators do not explicitly utilise features of fitness landscapes. To improve the performance of algorithms, this paper aims at designing a search operator adapting to fitness landscapes. Through an observation, we find that principle component analysis (PCA) can be used to characterise fitness landscapes. Based on this finding, a new search operator, called PCA-projection, is proposed. In order to verify the effectiveness of PCA-projection, we design two algorithms enhanced with PCA-projection for solving constrained optimization problems, called PMODE and HECO-PDE, respectively. Experiments have been conducted on the IEEE CEC 207 competition benchmark suite in constrained optimisation. PMODE and HECO-PDE are compared with the algorithms from the IEEE CEC 208 competition and another recent MOEA for constrained optimisation. Experimental results show that an algorithm enhanced with PCA-projection performs better than its corresponding opponent without this operator. Furthermore, HECO-PDE is ranked first on all dimensions according to the competition rules. This study reveals that decomposition-based MOEAs, such as HECO-PDE, are competitive with best single-objective and multiobjective evolutionary algorithms for constrained optimisation, but MOEAs based on non-dominance, such as PMODE, may not. Keywords: constrained optimization; multiobjective optimization; principle component analysis; differential evolution; fitness landscape.. Introduction Optimization problems in the real world often contain different types of constraints. In mathematics, a constrained optimization problem (COP) can be formulated as min f(x), x = (x,, x n ) R n, () x Ω = {x L i x i U i, i =,, n}, subject to g i (x) 0, i =,, q, (2) h j (x) = 0, j =,, r, where x Ω is the bounded constraint. L i and R i denote lower and upper boundaries respectively. g i (x) 0 is the ith inequality constraint. h j (x) = 0 is the jth equality constraint. This work was supported by the National Natural Science Foundation of China under Grant Corresponding author addresses: (Wei Huang), (Tao Xu), (Kangshun Li), (Jun He) Preprint submitted to Swarm and Evolutionary Computation August 27, 209 There exist a variety of evolutionary algorithms (EAs) for solving COPs, which employ different constraint handling techniques, such as the penalty function method, feasibility rule, repair method and multiobjective optimization [, 2, 3]. This paper focuses on the multi-objective optimization method [4], which is to convert a COP into a multi-objective optimization problem without any constraint. The advantage of using this method is no need to handle constraints in a special way, because constraints themselves are converted into objectives and a COP will be solved by MOEAs. The converted problem often is a bi-objective optimization problem [5, 6]: min f = (f(x), v(x)), (3) in which one objective is the original objective function f(x) and the other is the degree of violating the constraints v(x). v(x) = i v g i (x) + j v h j (x). (4) The first part in the formula is the sum of the degree of violating an inequality constraint, given by v g i (x) = max{0, g i(x)}, i =,, q. (5) The second part is the sum of the degree of violating an equal constraint, given by v h j (x) = max{0, h j(x) δ}, j =,, r, (6) where δ is a tolerance allowed for the equality constraint. Many MOEAs have been proposed for solving constrained optimisation problems [4]. Most of them adopt mutation and crossover operators from differential evolution (DE). However, these operators do not explicitly utilise characteristics of fitness landscapes. Intuitively, a search operator which adapts to fitness landscapes may be more efficient than those without adaptation. A recent theoretical study also claims that in terms of the time-based fitness landscape, unimodal functions are the easiest and deceptive functions to EAs are the hardest [7]. Therefore, it is important to design a landscape-adaptive search operator which may improve the performance of EAs. Our idea is to enhance EAs with principle component analysis (PCA). There exist a suite of studies which have shown PCA may improve the performance of EAs. Munteanu and Lazarescu [8] designed a PCA-mutation operator and claimed that PCA-mutation is more successful in maintaining population diversity during search. Because of PCA s inherent capability of rebuilding a new coordinate system, Li et al. [9] applied PCA to the design of crossover for reducing correlations among variables. PCA was used in particle swam optimization (PSO) to mine population information for promising principal component directions [0,, 2]. This information is utilized in velocity vectors of particles. Because PCA is a powerful tool in dimensional reduction, it helped EAs solve high dimensional optimization problems [3, 4]. Besides its application in designing search operators, local principal component analysis is used for building a regularity model in multiobjective estimation of distribution algorithms [5, 6]. However, the number of references of applying PCA to EAs is still very small and it is worth making further investigations. In this paper, we design a new search operator adapting to fitness landscapes with the aid of PCA. PCA is used to identify the maximal variance direction in a population. Given a valley fitness landscape in the 3-dimensional space, we observe that the direction obtained by PCA is consistent with the valley direction. Based on this observation, we design a new search operator, called PCA-projection. The research question of this paper is whether a MOEA enhanced with PCA-projection is able to outperform its rival without this operator or other state-of-arts EAs. To answer this question, we design two MOEAs enhanced with PCA-projection, conduct experiments on the IEEE CEC 207 benchmark suit for constrained optimisation competition [7] and compare them with EAs from the CEC 208 competition [8]. The remainder of this paper is organised as follows. Section 2 reviews MOEAs for constrained optimisation. Section 3 introduces related work in differential evolution and PCA s applications in EAs. Section 4 explains PCA-projection in detail. Section 5 designs two EAs enhanced with PCA-projection. Section 6 reports comparative experimental results. Section 7 concludes this paper. 2 2. Literature Review of Multiobjective Evolutionary Algorithms for Constrained Optimisation The idea of applying MOEAs to constrained optimisation has attracted researchers interest in last two decades. Surry and Radcliff [5] proposed constrained optimization by multi-objective genetic algorithms. They considered a COP in a dual perspective, as a constraint satisfaction problem and an unconstrained optimization problem. Coello [9] introduced the concept of non-dominance to handle constraints into the fitness function of a genetic algorithm. Feasible individuals are ranked higher than infeasible ones, while infeasible individuals with a lower degree of constraint violation is ranked higher than those with a higher degree. Zhou et al. [6] converts a COP to a two-objective optimization model composed of the original objective function and the degree function violating the constraints. Then they designed a real-coded genetic algorithm based on Pareto strength and Minimal Generation Gap model. Most MOEAs for constrained optimisation belong to the category of MOEAs based on non-dominance or Pareto ranking. Venkatraman and Yen [20] proposed a two-phase genetic algorithm framework for solving COPs. In the first phase, a COP is treated as a constraint satisfaction problem. In the second phase, a COP is treated as a bi-objective optimization problem with the simultaneous optimization of the objective function and the satisfaction of the constraints. Then the Non-Dominated Sorting Genetic Algorithm (NSGA-II) is used. Cai and Wang [2, 22] combined multiobjective optimization with differential evolution (CMODE) to solve COPs which is based on the two-objective model. The search is guided by infeasible solution archiving and replacement mechanism. Furthermore, they provided a dynamic hybrid framework [23], which consists of global search and local search models. More recently, Gao and Yen et al. [24] considered COPs as a bi-objective optimization problem, where the first objective is the reward function or actual cost to be optimized, while the second objective is the constraint violations degree. Gao et al. [25] proposed a reverse comparison strategy based on multi-objective dominance concept. That strategy converted the original COPs to a multi-objective problem with one constraint, and weeds out worse solutions with smaller fitness value regardless of its constraints violation. Li et al. [26] and Zeng et al. [27] converted a COP into a dynamic constrained many-objective optimization problem, and considered three types of MOEAs, i.e., Pareto ranking-based, decomposition-based, and hype-volume indicator-based to instantiate the framework. Recently, MOEAs based on objective decomposition have been applied to constrained optimisation. Xu et al. [28] constructed several helper objective functions using the weighted sum method but with static weights. Then they employed DE for optimising optimisation subproblems. Wang et al. [29] considered the weighted sum approach with dynamical weight to decompose the problem (2) and also applied DE to solve them. Peng et al. [30] adopted the Chebyshev approach in objective decomposition with biased dynamic weights. The purpose of using MOEAs for constrained optimisation is to seek the optimal feasible solution, but not to generate a uniformly distributed Pareto front. Therefore, we guess that decomposition-based MOEAs are more flexible than MOEAs based on non-dominance or Pareto ranking, because through biased dynamic weights, we may adjust the search direction of decomposition-based MOEAs. At the beginning, a MOEA searches different directions, but at the later stage, it focuses more on the direction towards the optimal feasible solution. 3. Two Pieces of Related Work Our work is linked to classical DE [3] and the application of PCA in EAs [8]. This section reviews them one by one. 3.. Differential Evolution DE is a popular EA for solving continuous optimization problems [3]. represented by µ n-dimensional vectors: In DE, a population P is P = {x,, x µ }, (7) x i = (x i,, x i,2,, x i,n ) T, i =, 2,, µ, (8) 3 where µ is the population size. Initial individuals are chosen randomly from [L i, U i ] n. An initial individual x = (x,, x n ) T is generated at random as follows: x i = L i + (U i L i ) rand, i =,, n, (9) where rand is the random number [0, ]. The DE algorithm consists of three operations: mutation, crossover and selection, which are described as follows [3, 28]. Mutation: for each individual x i where i =,, µ, a mutant vector v i = (v i,, v i,2,, v i,n ) is generated by v i = x r + F (x r2 x r3 ) (0) where individuals x r, x r2, x r3 are chosen from P at random but mutually different. They are also chosen to be different from x i. F is a real and constant factor from [0, 2] which controls the amplification of the differential variation x r2 x r3. In case v i is out of the interval [L i, U i ], the mutation operation is repeated until v i falls in [L i, U i ]. Crossover: in order to increase population diversity, crossover is also used in DE. The trial vector u i is generated by mixing the target vector x i with the mutant vector v i. Trial vector u i = (u i,, u i,2,, u i,n ) is constructed as follows: { v i,j, if rand j (, 0) CR or j = j rand, u i,j = j =,, n, () x i,j, otherwise, where rand j (0, ) is a uniform random number from [0, ]. Index j rand is randomly chosen from {,, n}. CR [0, ] denotes the crossover constant which has to be determined by the user. In addition, the condition j = j rand is used to ensure the trial vector u i gets at least one parameter from vector v i. Selection: a greedy criterion is used to decide whether the offspring generated by mutation and crossover should replace its parent. Trail vector u i is compared to target vector x i, then the better one will be reserved to the next generation. Notice that both mutation and crossover operators do not explicitly utilise features of fitness landscapes. There exist several variants of DE algorithms. A classical DE algorithm is the DE/Rand//bin DE [32] which is illustrated below. : initialize a population P = {x,, x µ }; 2: calculate fitness values of each individual in P ; 3: while the terminal condition is not satisfied do 4: for i =,, µ do 5: randomly select three individuals x r, x r2, x r3 from P at random, such that r r 2 r 3 i; 6: implement mutation and crossover and generate a child u i of x i ; 7: calculate fitness value f(u i ); 8: if f(u i ) f(x i ) then 9: x i u i ; 0: end if : end for 2: end while 3.2. Application of Principle Component Analysis in Evolutionary algorithms It is an interesting idea to apply PCA to the design of EAs but so far only a few research papers can be found on this topic. Munteanu and Lazarescu s work [8] designed a mutation operator based on PCA. They claimed that a PCA-mutation genetic algorithm (GA) is more successful in maintaining population diversity 4 during search. Their experimental results show that a GA with the PCA-mutation obtained better solutions compared to solutions found using GAs with classical mutation operators for a filter design problem. Munteanu and Lazarescu [8] designed a new mutation operator on a projection search space generated by PCA, rather than the original space. Their PCA mutation is described as follows. A population with µ individuals is represented by an n µ matrix X = [x,, x µ ] where n is the space dimension and µ the population size. Each x is an individual represented by a column vector. : From the data set X, calculate the n n covariance matrix Σ: Σ = E[(x m)(x m) T ] (2) where m = E[x] which is the mean over x,, x µ. 2: Given the co-variance matrix Σ, compute its eigenvectors v,, v n and sort them in the order of the corresponding eigenvalues of these eigenvectors from high to low. Form a n n matrix V = [v,, v n ]. 3: Calculate the projection of the data set X using the orthogonal basis v,, v n and obtain a projected population, represented by the matrix Y = [y,, y n ] T : y i = V T (x i m). (3) 4: Compute the squared length of the projections along each direction v i, that is, L i (x j ) 2 = y 2 i,j, i =,, n, j =,, µ. (4) 5: Choose quantities c i,j randomly between 0 and c max where c max is a constant parameter of the mutation operator such that c i,j c i,j for i =,, n. 6: The mutation operator adds the quantities c i,j to each projected squared coordinate as follows: L i(x j ) 2 = L i (x j ) 2 +c i,j. (5) 7: Compute the sign of each element in the matrix Y, which is represented by the matrix signum(y). 8: Generate the child y i from y i as follows: y i,j equals to the square roots of the mutated square projections L i (x j) 2 multiplied by the corresponding sign signum(y i,j ). 9: Obtain the mutated point in the original search space: x i = Vy i + m. (6) Notice that the above PCA-mutation doesn t reduce the data set X into a lower dimension space, instead X and Y have the same dimension. This PCA-mutation aims to conduct mutation in the projection space rather than the original space. However the dimensions of the projection space and original space are the same. 4. A New Search Operator: PCA-projection In order to improve the performance of EAs, we propose a new search operator, called PCA-projection, which is able to adapt to fitness landscapes. 4.. Principle Component Analysis and Valley Direction Although PCA-mutation proposed in [8] was efficient for a filter design problem, it has a disadvantage. PCA-mutation still acts on the same dimension space as the original search space. Thus, as the population size increases, the calculation of eigenvalues and eigenvectors in PCA becomes more and more expensive. In this paper, we propose a different PCA-search operator in which PCA is only applied to several selected points. A question is how to select points from a population for implementing PCA? The solution relies on the valley concept. In the 3-dimensional space, a valley is intuitive which means a low area between two hills or mountains. However, this definition is really fuzzy in high-dimensional spaces. What does a valley in a higher dimensional 5 space mean? How to identify the location of a valley? So far there exist no clear mathematical definition about the valley. In this paper, we study the valley landscape using PCA and find that PCA provides a statistic method of identifying the valley direction. Let s explain our idea using the well-known Rosenbrock function: f(x, y) = ( x) (y x 2 ), x 2, y 2 (7) Its minimum point is at (, ) with f(, ) = 0. Fig. a shows the contour graph of Rosenbrock function. From Fig. a, it is obvious that a deep valley exists on this landscape. But how to identify the valley? In the following we show a statistical method of calculating the valley direction. First we sample 20 points at random and select 6 points with smallest function values from the population. Fig. b depicts that these 6 points (labelled by squared points) are closer to the valley than other points (a) (b) (c) (d) Figure : PCA and the valley landscape Next we identify the valley direction. Since the selected 6 points distribute along the valley, the valley direction can be regarded as a direction along which the variance of the 6 points is maximal. This direction can be identified by PCA. Assume that the valley direction is a linear line, the valley in fact can be approximated by the first principle component found by PCA. Let s project the 6 selected points onto the first principle component. Fig. c shows that the projected points (labeled by dotted points) approximately represent the valley direction. But it should be pointed out if we apply PCA to the whole population and project all 20 points onto the first principle component, we cannot obtain the valley direction. Fig. d shows that the mapped points 6 (labeled by dotted points)) don t distribute along the valley direction. The mapped points could represent any direction if these 20 points are sampled at random Proposed PCA Projection Based on the observation in the above subsection, we propose a new search operator. Here is our idea: Given a population, we select a group of points with smaller function values from the population and apply PCA to calculate principle components; then project the points onto the principle components; at the end, reconstruct the projected points in the original search space. These points are taken as the children. The procedure is described in detail as follows: PCA-projection: Given a population P and a fitness function f(x), : Select k individuals {x,, x k } with smaller fitness values from the population P (k is a small constant). Denote these individuals by X. 2: Calculate the n mean vector m and n n covariance matrix Σ: m = k k i= x i, Σ = k k (x i m)(x i m) T. (8) 3: Calculate

We Need Your Support

Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

Thanks to everyone for your continued support.

No, Thanks

SAVE OUR EARTH

We need your sign to support Project to invent "SMART AND CONTROLLABLE REFLECTIVE BALLOONS" to cover the Sun and Save Our Earth.

More details...Sign Now!

We are very appreciated for your Prompt Action!

x