

small (250x250 max)
medium (500x500 max)
Large
Extra Large
large ( > 500x500)
Full Resolution


PERFORMANCE METRICS ENSEMBLE FOR MULTIOBJECTIVE EVOLUTIONARY ALGORITHMS By ZHENAN HE Bachelor of Engineering in Automation University of Science and Technology Beijing Beijing, China 2008 Submitted to the Faculty of the Graduate College of the Oklahoma State University in partial fulfillment of the requirements for the Degree of MASTER OF SCIENCE May, 2011 ii PERFORMANCE METRICS ENSEMBLE FOR MULTIOBJECTIVE EVOLUTIONARY ALGORITHMS Thesis Approved: Dr. Gary G. Yen Thesis Adviser Dr. Qi Cheng Dr. Weihua Sheng Dr. Mark E. Payton Dean of the Graduate College iii ACKNOWLEDGMENTS At the outset, I would like to thank my advisor Dr. Gary G. Yen, for his patience and guidance. I enjoy very much working under him and it was an excellent learning experience for me. I appreciate him for teaching me how to think about a problem, how to generate an idea to solve the problem and how to validate my idea through the experiment. I would also like to thank him for helping me out with great patience in writing this thesis, for guiding me and giving me tips on structure, grammar, sentence and words. These lessons will benefit me all my life. I would like to think my committee members, Dr. Qi Cheng and Dr. Weihua Sheng for their timely advice, discussions and feedback. Dr. Cheng’s Stochastic System class made me understand the stochastic concept in a depth way, which helps me much in my research work. Many thanks to my lab mates at the Intelligent Systems and Control Laboratory: Chatkew Jariyatantiwait, Bin Ha and Weiwei Zhang gave me much useful suggestions. I often get inspiration by the group study with them. In summary, I would like to thank my lab mates for providing an intellectually stimulating experience via discussions and presentations throughout my tenure. Then I strongly like to thank my friends Guanglei An and Xiaowei Yang. They often give me many suggestions in my study and life. A note of thanks for my good friends Suling Duan, Bo Xu, Huanyu Zhao, Lianfan Su and Rui Yang along with all my above mentioned friends for a great spare time and for their support and understanding. iv I am forever grateful to my parents for their love, financial and moral support and encouragement. Lastly, but definitely not the least, I dedicate this work in loving memory my grandfather, who was and will continue to be a great source of inspiration to me. I cherish the memory of him forever. v TABLE OF CONTENTS Chapter Page 1 INTRODUCTION 1 1.1 PROBLEM STATEMENT ................................................................................1 1.2 MOTIVATION ..................................................................................................3 1.3 ORGANIZATION OF THESIS ........................................................................4 2 REVIEW OF LITERATURE 5 2.1 MULTIOBJCTIVE OPTIMIZATION PROBLEMS ........................................5 2.1.1 Why Multiobjective Optimization Problems are Considered ...................5 2.1.2 MOP Definition ........................................................................................6 2.1.3 Concept of Domination .............................................................................7 2.1.4 ZDT Problems ...........................................................................................8 2.1.5 Test Problems DTLZ ..............................................................................14 2.2 MULTIOBJCTIVE EVOLUTIONARY ALGORITHMS (MOEAs) .............18 2.2.1 An Introduction to MOEAs ....................................................................18 2.2.2 MOEAs Definition ..................................................................................20 2.2.3 The Main Procedure of MOEAs .............................................................21 2.2.4 Control Parameters of Genetic Algorithms.............................................22 2.2.5 Some Examples of MOEAs ....................................................................23 vi 2.3 PERFORMANCE METRICS ..........................................................................29 2.3.1 Outperformance Relations and Quantitative Comparison Methods .......30 2.3.2 Compatibility and Completeness ............................................................32 2.3.3 Unary Performance Metrics ....................................................................34 2.3.4 Binary Performance Metrics ...................................................................45 3 METHODOLOGY 49 3.1 MOTIVATION ................................................................................................49 3.2 OVERVIEW OF PERFORMANCE METRICS ENSEMBLE .......................50 3.3 ENSEMBLE WITH DOUBLETOURNAMENT SELECTION ....................51 3.3.1 DoubleTournament Selection ................................................................51 3.3.2 Ensemble Method with DoubleTournament Selection ..........................53 4 EXPERIMENTAL FINDINGS 58 4.1 EXPERIEMENT RESULTS ...........................................................................58 4.1.1 ZDT1 .......................................................................................................58 4.1.2 ZDT2 .......................................................................................................62 4.1.3 ZDT3 .......................................................................................................67 4.1.4 ZDT4 .......................................................................................................71 4.1.5 ZDT6 .......................................................................................................75 4.1.6 DTLZ2 ....................................................................................................80 4.2 ANALYSIS OF EXPERIEMENT RESULTS.................................................84 4.2.1 Ensemble Metrics Give the Same Rank Values to Exist Papers ............84 4.2.2 Summary of EAs in Different Characteristics of Test Functions ...........85 vii 4.3 WHY USE DOUBLEELIMINATION METHOD TO ENSEMBLE ............86 5 CONCLUSION 88 REFERENCES 90 viii LIST OF TABLES Table Page 2.1 The main structure of SPEA 2 ...........................................................................24 2.2 The main structure of NSGAII .........................................................................27 2.3 The main structure of IBEA ...............................................................................28 2.4 The main structure of MOEA/D ........................................................................29 3.1 The whole process of ensemble method .............................................................51 ix LIST OF FIGURES 2.1 The Relation between Decision Space and Objective Space ...................................8 2.2 Paretooptimal front of ZDT1 ..................................................................................9 2.3 Paretooptimal front of ZDT2 ................................................................................10 2.4 Paretooptimal front of ZDT3 ................................................................................11 2.5 Paretooptimal front of ZDT4 ................................................................................12 2.6 Paretooptimal front of ZDT6 ................................................................................14 2.7 The Process of MOEAs to solve MOPs .................................................................19 2.8 Basic Structure of MOEAs ....................................................................................20 3.1 The proposed framework .......................................................................................50 3.2 The whole process of doubleelimination ..............................................................55 4.1 Box Plot for Performance Metric Measure in ZDT 1 ............................................58 4.2 Box Plot for Performance Metric Measure in ZDT 2 ............................................63 4.3 Box Plot for Performance Metric Measure in ZDT 3 ............................................67 4.4 Box Plot for Performance Metric Measure in ZDT 4 ............................................71 4.5 Box Plot for Performance Metric Measure in ZDT 6 ............................................76 4.6 Box Plot for Performance Metric Measure in DTLZ 2 ..........................................80 1 CHAPTER ONE INTRODUCTION 1.1 PROBLEM STATEMENT Evolutionary algorithms (EAs) have become established as the approach for exploring the Paretooptimal front in multiobjective optimization problems. EAs usually do not guarantee to identify optimal tradeoffs but attempt to find a good approximation. From No Free Lunch theorem [1], any algorithm elevated performance over one class of problems is exactly paid for in loss over another class. Although various multiobjective EAs (MOEAs) are available today, certainly we are interested in developing a most effective algorithm to search for Pareto solutions for a given problem [2]. Therefore, comparative studies are always conducted. They aim at revealing advantages and weaknesses of the underlying methods and at determining the best performance pertained to specific problem characteristics. The numerous applications of MOEAs boost the significance of performance comparison issues. However, in absence of any established comparison criteria, none of the different sets of estimates based on various metrics for the Paretooptimal solutions generated can be argued to be better than the others. Zitzler [2] proposed three optimization goals to be measured: the distance of the resulting nondominated set to the Paretooptimal front should be minimized, a good (in most cases uniform) distribution of the solutions found in objective space is desirable and the extent of the obtained nondominated front should be maximized. In the literature, there are many unary performance metrics used to compare MOEAs. These metrics can be broadly divided into five 2 categories according to the optimization goals. Each category mainly evaluates the quality of a Paretooptimal set in one aspect only. First, metrics assessing the number of Pareto optimal solutions in the set: Pareto Dominance Indicator (NR) [3] measures the ratio of nondominated solutions contributed by a particular solution set to the nondominated solutions provided by all solution sets; Overall Nondominated Vector Generation and Ratio (ONVG) [4] counts the number of distinct nondominated points generated; Ratio of Nondominated Individuals (RNI) [5] gives the proportion of the useful solutions known as the Paretofront in a given population size; and Error Ratio (ER) [4] checks the proportion of non true Pareto points in the approximation front. Within the second category, metrics measuring the closeness of the solution to the theoretical Pareto front: Generational Distance (GD) [4] measures how far the evolved solution set is from the true Pareto front; and Maximum Pareto Front Error (MPFE) [4] focused on the largest distance between the point in the theoretical Pareto front and the point in the approximation front. Third, metrics focusing on distribution of the solutions: Uniform Distribution (UD) [5] measures the distribution of an approximation front under a predefined parameter σs hare; Spacing [6] measures how evenly the evolved solutions distribute itself; and Number of Distinct Choices (NDCu) [7] identifies solutions that are sufficiently distinct for a special value u. Fourth, metrics concerning spread of the solutions: Maximum Spread (MS) [3] measures how well the true Pareto front is covered by the approximation set. In the last category, metrics considering both closeness and diversity at the same time: Hypervolume Indicator (or Smetric) [11] calculates the volume covered by the approximation front. Furthermore, there are some binary performance metrics used to compare a pair of algorithms. The first type of binary performance metrics based on unary quality indicator. It includes ε indicator. Iε [10] defines a ε dominate relation between algorithms, enclosing hypercube Indicator [10] and coverage difference metrics (Dmetric) [11]. The second type is direct comparison binary metrics: C metrics [9] and R metrics [5]. C metrics [9] consider the 3 dominate relations between algorithms; R metrics [5] use the probability that one algorithm is better than the other over a series of functions. However, the problem arises that no single metric alone can faithfully measure MOEA performance. Every single metric can provide some specific, but incomplete quantification of performance and can only be used effectively under some specified conditions. For example, UD does a poor job when the Pareto front is discontinued, while Hypervolume can be misleading if the Pareto optimal front is nonconvex [4]. This implies one metric cannot entirely evaluate EAs in all conditions. Every metric focuses on some special characteristics while neglects information in others. Also, every metric has its unique characteristic; no metrics can substitute others completely. Therefore, a single metrics cannot provide a comprehensive measure for MOEAs. Moreover, from [11], a fixed number of indicators are not sufficient to evaluate MOEAs because reducing objective space must losing information. Different metrics perform differently in different test problems. For a given MOEA, one metric may show well in one test problem, however, given other test problems, it may mislead the conclusion should the measures show poorly. For a specific test problem, we cannot ascertain which metric should be applied in order to faithfully quantify the performance of MOEAs. We need to exploit every metric to find which one is the best. Apparently, this introduces a heavy computational process. 1.2 MOTIVATION To overcome these disadvantages and arrive at a faithful evaluation of MOEAs, performance metrics ensemble is proposed in this research work. Ensemble methods use multiple metrics to obtain a fair performance than what could be obtained from any of single performance metric alone. Ensemble metrics not only can give the comprehensive comparison between different algorithms, but avoid the choosing process and can be directly used to assessing MOEAs. 4 There exists no publication in the literature, to our best knowledge, regarding performance metrics ensemble. MOEAs are only evaluated and compared in a single metric at a time. In this paper, we propose doubletournament selection operator to compare many approximation fronts from different MOEAs. Double elimination design allows characteristic poor performance of a quality algorithm under the special environment still to be able to win it all. In every competition, one metric is chosen randomly to compare. After the whole process, every metric could be selected multiple times and a final winning algorithm is to be identified. This final winner has been compared under all the metrics considered so that we can make a fair conclusion. 1.3 ORGANIZATION OF THESIS Chapter Two provides the consolidated literature review for this thesis. It presents the essential background with reference to knowledge in the areas of Multiobjective Optimization Problem, Multiobjective Evolutionary Algorithms and Performance Metrics. Chapter Three describes the proposed approach in detail. A novel ensemble method using modified DoubleTournament selection operator is introduced. In Chapter Four, we elaborate on the experiment results for ZDT (16) and DTLZ 2 problems. Finally, conclusion is drawn in Chapter Five along with pertinent observations. 5 CHAPTER TWO REVIEW OF LITERATURE This chapter presents the essential background knowledge on Multiobjective Optimization Problem (MOP), Multiobjective Evolutionary Algorithm (MOEA) and Performance Metrics. 2.1 MULTIOBJECTIVE OPTIMIZATION PROBLEMS (MOP) First, the omnipresent of MOP is discussed. Then, definition of MOP is given. After that, concept of domination is introduced to identify the optimal solution. In addition, the characteristic of reference sets of MOP is summarized. Finally, two series of test problems are presented, which are widely applied to evaluate the performance of multiobjective evolutionary algorithms. 2.1.1 Why Multiobjective Optimization Problems? In real life environments we always strive to optimize a number of parameters in any design and these parameters are usually highly correlated. Hence, some tradeoff between the criteria is needed to ensure a satisfactory design. For example: in bridge construction, a good design is characterized by low total mass and high stiffness; aircraft design requires simultaneous optimization of fuel efficiency, payload, and weight; a good sunroof design in a sport car could aim at minimizing the noise the driver hears and maximizing the ventilation; and the business portfolio management attempts to simultaneously minimize the risk and maximize the fiscal return. In these realworld optimization problems, the objectives often conflict across a highdimensional problem space and may also require extensive computational resources. 6 Neither the problem nor algorithm domains considered within this research is straightforward. Multiobjective Optimization Problems (MOPs) present a possibly uncountable set of solutions that produce vectors whose components represent tradeoffs in objective space. Therefore, for an MOP, a number of tradeoff solutions are optimal. Without further information, such optimal solutions are equally important. 2.1.2 MOP Definition [39] In general, an MOP involves k objectives, mconstraints and ndecision variables: k objectives: Optimizes ( ) ( ( ) ( )) 1 , , k f x = f x K f x (21 A) mequality and inequality constraints: Subject to ( ) 0, 1, , i g x ≤ i = K m (21 B) n decision variables: ( ) 1, , T n x = x K x (21 C) MOP deals with two search spaces: a decision space ( ) plus an objective space ( Λ ). Mapping takes place from an n dimensional decision space to an m dimensional objective space. The MOP's objective function, f : →Λ , maps decision variables ( ) 1, , n x = x K x in decision space to vectors ( ) ( ( ) ( )) 1 , , k f x = f x K f x in objective space. Proximity of two solutions in one space does not imply proximity in the other space and search is performed in the decision space. As stated in [2], the goal of MOPs consists of multiple objectives: the distance of the resulting nondominated set to the Paretooptimal front should be minimized; a good (in most cases uniform) distribution of the solutions found is desirable; and the extent of the obtained nondominated front should be maximized, i.e., for each objective, a wide range of values should be covered by the nondominated solutions. Apparently, while these candidate solutions are 7 progressing towards Paretooptimal front, the convergence process will adversely impact the spread of the solution found. 2.1.3 Concept of Domination [39] Most multiobjective optimization algorithms use the concept of domination. In these algorithms, two solutions are compared on the basis of whether one dominates the other solution or not. Pareto Optimality: A solution x∈ is said to be Pareto optimal with respect to if and only if there is no x' ∈ for which ( ' ) ( ( ' ) ( ' )) 1 , , k v = f x = f x K f x dominates ( ) ( ( ) ( )) 1 , , k u = f x = f x K f x . Pareto Dominance: A vector ( ) ( ) 1, , u k u = f x = u K u is said to dominate ( ) ( ) 1, , v k v = f x = v K v (denoted by upv ) if and only if u is worse than v , {1, , }, and {1, , }, i i i i ∀i∈ K k u pv ∃i∈ K k u p v Pareto Optimal Set: For a given MOP f ( x) , x∈ the Pareto optimal set P∗ is defined as: P∗ := {x∈ ¬∃x' ∈ : f (x' ) ≤ f ( x)} Pareto Front (Nondominated front): For a given MOP f ( x) and Pareto optimal set P∗ , the Pareto front PF∗ is defined as: { ( ) ( ( ) ( )) } 1 : , , k PF∗ = u = f x = f x K f x x∈P∗ Figure 1 explains the relation between decision space and objective space and the corresponding front in each space for a given problem. 8 Fig 2.1 The Relation between Decision Space and Objective Space Moreover, there are some special points in the objective space [39]. Ideal Objective Vector (Reference Solutions Z∗ ) is the lower bound in the Paretooptimal set. The mth component of the ideal objective vector is the constrained minimum solution of the following problem: Minimize fm ( x) , subject to x∈S . ( ) 1 2 , , , T M Z∗ = f ∗ = f ∗ f ∗ K f ∗ . Utopian Objective Vector ( Z∗∗ ) has each of its components marginally smaller than that of the Ideal Objective Vector. i i Z∗∗ = Z∗ −ε with 0 i ε > for all i = 1,2,K ,M and Nadir Objective Vector ( Znad ) is upper bound in the Paretooptimal set. 2.1.4 ZDT problems [2] ZDT problems were proposed by Deb in 1999 and consist of six benchmark functions. ZDT contains several characteristics that cause difficulties for multiobjective evolutionary algorithms: for converging to the Paretooptimal front, multimodality, deception and isolated optima are applied and for maintaining diversity within the population, convexity or nonconvexity, discreteness, and nonuniformity in the front. Each of the test functions is structured in the same manner and consists itself of three functions 1 f , g , h : 9 Minimize ( ) ( ( ) ( )) 1 2 f x = f x , f x (22) Subject to ( ) ( ) ( ( ) ( )) 2 2 1 1 2 , , , , , n n f x = g x K x h f x g x K x , where ( ) 1, , n x = x K x ZDT1 (Convex Paretooptimal front): ( ) 1 1 f x = x (23 A) ( ) ( ) ( ) ( ) 1 2 1 f x f x g x g x = − (23 B) ( ) 2 9 1 1 n i i x g x n = = + − Σ (23 C) ( ) [ ] 1,..., 0,1 T n n x = x x ∈ . Given n = 30 , the Paretooptimal front is convex and formed with g ( x) =1.Figure 2.2 shows the true Paretooptimal front of ZDT1. Fig 2.2 Paretooptimal front of ZDT1 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 10 ZDT2 (Nonconvex Paretooptimal front): f1 ( x) = x1 (24 A) ( ) ( ) ( ) ( ) 2 1 2 1 f x f x g x g x = − (24 B) ( ) 2 9 1 1 n i i x g x n = = + − Σ (24 C) ( ) [ ] 1,..., 0,1 T n n x = x x ∈ . Given n = 30 , the Paretooptimal front is nonconvex and formed with g ( x) =1. Figure 2.3 shows the Paretooptimal front of ZDT2. Fig 2.3 Paretooptimal front of ZDT2 ZDT3 (Discrete Paretooptimal front): ( ) 1 1 f x = x (25 A) 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 11 ( ) ( ) ( ) ( ) ( ) ( ) 1 1 ( ) 2 1 1 sin 10 f x f x f x g x x g x g x π = − − (25 B) ( ) 2 9 1 1 n i i x g x n = = + − Σ (25 C) ( ) [ ] 1,..., 0,1 T n n x = x x ∈ , Given n = 30 , its Paretooptimal front is disconnected and formed with g ( x) =1. The two objectives are disparately scaled in the Paretooptimal front; 1 f is from 0 to 0.852 and 2 f from 0.773 to 1. The introductions of the sine function in h causes discontinuity in the Paretooptimal front. Figure 2.4 shows the Paretooptimal front of ZDT3. Fig 2.4 Paretooptimal front of ZDT3 ZDT4 (Lots of local Paretooptimal front): ( ) 1 1 f x = x (26 A) 12 ( ) ( ) ( ) ( ) 1 2 1 f x f x g x g x = − (26 B) ( ) ( ) 2 ( ) 2 1 10 1 10cos 4 n i i i g x n x π x = = + − +Σ − (26 C) ( ) [ ] [ ] 1 1,..., 0,1 5,5 T n n n x x x − = ∈ × − . Given n =10 . It has many local Paretooptimal fronts. The global Paretooptimal front is formed with g ( x) =1, the best local Paretooptimal front with g ( x) =1.25 . Not all local Paretooptimal sets are distinguishable in the objective space. Figure 2.5 shows the Paretooptimal front of ZDT4. Fig 2.5 Paretooptimal front of ZDT4 ZDT5 (Deceptive problem): ( ) ( ) 1 1 f x =1+ u x (27 A) ( ) ( ) ( ) 2 1 f x = g x f x (27 B) 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 13 ( ) ( ( )) 2 2 ,..., n n i i g x x v u x = =Σ (27 C) ( ) i u x gives the number of ones in the bit vector i x : ( ( )) ( ) ( ) ( ) 2 5 1 5 i i i i u x u x v u x u x + < = = (27 D) Given n =11, { }30 1 x ∈ 0,1 and { }5 2 , , 0,1 n x K x ∈ . The true Paretooptimal front is formed with g ( x) =10 . The global Paretooptimal fronts as well as the local ones are convex. ZDT6 (Paretooptimal solutions are nonuniformity): ( ) ( ) 6 ( ) 1 1 1 f x =1− exp −4x sin 6π x (28 A) ( ) ( ) ( ) ( ) 2 1 2 1 f x f x g x g x = − (28 B) ( ) 0.25 2 1 9 1 n i i x g x n = = + − Σ (28 C) ( ) [ ] 1,..., 0,1 T n n x = x x ∈ . Given n =10 . Its Paretooptimal front is nonconvex. The distribution of the Pareto solutions in the Pareto front is nonuniform, i.e., for a set of uniformly distributed points in the Pareto set in the decision space, their images crowd in a corner of the Pareto front in the objective space. The density of the solutions is lowest near the Paretooptimal front and highest away from the front. Figure 2.6 shows the Paretooptimal front of ZDT6. 14 Fig 2.6 Paretooptimal front of ZDT6 2.1.5 Test Problem DTLZ [12] DTLZ contains seven benchmark functions. All the functions have more than two objectives. Like ZDT problems, DTLZ also contains problem characteristics that present difficulties for multiobjective evolutionary algorithms. Therefore, DTLZ test MOEAs’ ability to deal with highdimension problems. DTLZ 1: An Mobjective problem with a linear Paretooptimal front: ( ) ( ( )) ( ) ( )( ( )) ( ) ( )( ( )) ( ) ( )( ( )) 1 1 2 1 2 1 2 1 1 1 2 1 1 1 2 1 1 1 2 Minimize 1 1 1 2 1 1 1 2 M M M M M M M M f x x x x g x f x x x x g x f x x x g x f x x g x − − − = ⋅ ⋅ ⋅ + = ⋅ ⋅ ⋅ − + = − + = − + K K (29 A) Subject to 0 1 i ≤ x ≤ , i = 1,2,K ,n 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 15 ( ) ( ) ( ( )) 2 100 0.5 cos 20 0.5 i M M M i i x X g x x x π x ∈ = + − − − Σ (29 B) The Paretooptimal solution corresponds to 0.5 i x∗ = ( i M x∗ ∈ x ) and the objective function values lie on the linear hyperplane: 1 0.5 M m m f ∗ = Σ = . k = 5 is suggested here. The total number of variables isM + k −1 . The search space contains (11k −1) local Paretooptimal fronts. The difficulty in this problem is to converge to the hyperplane. DTLZ 2: An Mobjective problem with a Spherical Paretooptimal front: ( ) ( ( )) ( ) ( ) ( ) ( ( )) ( ) ( ) ( ) ( ( )) ( ) 1 1 1 2 1 1 1 1 cos 2 cos 2 1 cos 2 sin 2 Minimize 1 sin 2 M M M M M M f x g x x x f x g x x x f x g x x π π π π π − − = + ⋅⋅ ⋅ = + ⋅⋅ ⋅ = + L L (210 A) Subject to 0 1 i ≤ x ≤ , i = 1,2,K ,n ( ) ( )2 0.5 i M M x X i g X x ∈ =Σ − (210 B) The Paretooptimal solution corresponds to 0.5 i x∗ = ( i M x∗ ∈ x ) and all objective function values must satisfy: ( )2 1 1 M m m f ∗ = Σ = . k =10 is suggested here. The total number of variables isM + k −1 . DTLZ 3: An Mobjective problem with a Global Paretooptimal front: 16 ( ) ( ( )) ( ) ( ) ( ) ( ( )) ( ) ( ) ( ) ( ( )) ( ) 1 1 1 2 1 1 1 1 cos 2 cos 2 1 cos 2 sin 2 Minimize 1 sin 2 M M M M M M f x g x x x f x g x x x f x g x x π π π π π − − = + ⋅⋅ ⋅ = + ⋅⋅ ⋅ = + L L (211 A) Subject to 0 1 i ≤ x ≤ , i = 1,2,K ,n ( ) ( ) ( ( )) 2 100 0.5 cos 20 0.5 i M M M i i x X g x x x π x ∈ = + − − − Σ (211 B) The difficult is that this problem introduces many local Paretooptimal fronts. DTLZ 4: This problem measures MOEA’s ability to maintain a good distribution of solutions: ( ) ( ( )) ( ) ( ) ( ) ( ( )) ( ) ( ) ( ) ( ( )) ( ) 1 1 1 1 1 1 2 1 cos 2 cos 2 1 cos 2 sin 2 Minimize 1 sin 2 M M M M M M f x g x x x f x g x x x f x g x x α α α α α π π π π π − − = + ⋅ ⋅⋅ = + ⋅ ⋅⋅ = + L L (212 A) Subject to 0 1 i ≤ x ≤ , i = 1,2,K ,n ,α =100 . ( ) ( )2 0.5 i M i M x X g x xα ∈ =Σ − (212 B) DTLZ 5: This problem will test an MOEA’s ability to converge to a degenerated curve: Mapping ( ( )) (1 2 ( ) ) 4 1 i i g r x g r π θ = + + (213 A) 17 i = 2,3,K ,M −1, in the test problem of DTLZ 2. ( ) 0.1 i M M x X i g x x ∈ =Σ (213 B) DTLZ 6: This problem has 2M −1 disconnected Paretooptimal regions in the search space: ( ) ( ) ( ) ( ( )) ( ) 1 1 1 1 1 1 1 2 1 Minimize 1 , ,..., , M M M M M M f x x f x x f x g x h f f f g − − − − = = = + L L (214 A) Subject to 0 1 i ≤ x ≤ , i = 1,2,K ,n , ( ) 9 1 i M M x x i M g x x x ∈ = + Σ (214 B) ( ( )) 1 1 1 sin 3 1 M i i i f h M f g π − = = − + + Σ (214 C) k = 20 is suggested here. The total number of variables isM + k −1 .This problem will test an algorithm’s ability to maintain subpopulation in different Paretooptimal regions. DTLZ 7: This problem is constructed by constraint surface approach: Minimize: ( ) ( 1) 1 n j M j n i i j M f x x n M = − = Σ , j =1,K ,M (215 A) Such that ( ) ( ) 4 ( ) 1 0 j M j g x = f x + f x − ≥ , j =1,K ,M −1 (215 B) 18 ( ) ( ) 1 ( ) ( ) , 1 2 minM 1 0 M M i j i j i j g x f x − f x f x = ≠ = + + − ≥ (215 C) subject to space 0 1 i ≤ x ≤ , i = 1,2,K ,n n =10M . There are a total of M constraints. It is difficult for MOEAs to handle these constraints while searching for the optimal solutions. Moreover, there are some nondominated solutions in the final population but not the true Paretooptimal solutions. This problem is called redundant solutions. Because of redundant solutions, the obtained set of solutions may incorrectly find a higherdimensional surface as the Paretooptimal front. 2.2 MULTIOBJECTIVE EVOLUTIONARY ALGORITHMS (MOEAs) This part includes MOEA introduction, MOEA definition, MOEA’s main procedure, and parameters in controlling the behavior of the GA and some examples of MOEAs. 2.2.1 An Introduction to MOEA [39] MOEA is motivated from the conception of evolution in biology, specifically Darwin’s “survival of the fittest” (natural selection) law. Figure 2.7 describes how MOEA works. It includes two steps. In the first step, an ideal Multiobjective Optimizer finds an optimal front consists of multiple tradeoff solutions. Then, in the second step, based on some highlevel information, one solution is chosen for implementation. Evolutionary algorithms (EAs) have become an effective tool for exploring the Paretooptimal front in multiobjective optimization problems that are often too complex to be solved by exact methods, such as linear programming or gradient search. This is because there are few alternatives for searching intractably large spaces for multiple Paretooptimal solutions. Due to their inherent parallelism and their ability to exploit similarities of solutions by recombination, 19 they are able to approximate the Paretooptimal front in a single optimization run. The numerous applications and the rapidly growing interest in the area of MOEAs take this fact into account. Fig 2.7 The Process of MOEAs to solve MOPs From Zitzler and Deb [2], the first pioneering studies on evolutionary multiobjective optimization appeared in the mideighties by Schaffer in 1984 [26] and Fourman in 1985[27]. After that, several different EA implementations were proposed from 1991 to 1994: Kursawe in 1991[28]; Hajela and Lin in 1992 [29]; Fonseca and Fleming in 1993[30]; Horn in 1994 [31]; and Srinivas and Deb in 1994 [32]. Later, these approaches were successfully applied to various multiobjective optimization problems. In recent years, some researchers have investigated particular topics of evolutionary multiobjective search, such as convergence to the Paretooptimal front by Van Veldhuizen and Lamont [33] and Rudolph [34], niching by Obayashi [35], and elitism by Parks and Miller [36]; while others have concentrated on developing new evolutionary techniques, such as Laumanns [37] and Zitzler and Thiele [38]. Today, there are some MOEAs frequently used: SPEA 2 by Zitzler [13], NSGAII by Deb [14], IBEA by Zitzler [15], PESAII by Corne [16] and MOEA/D by Zhang [17]. 20 Also, there are alternatives to EAs [39]: Evolutionary Programming (EP) and Genetic Programming (GP). EP is a mutationbased evolutionary algorithm to discrete search spaces. Similar to EA, a selfadopting rule is used to update the mutation strengths. Therefore, EP is allowed to search anywhere in the real space likes realparameter GAs. In GP, a terminal set T (constants and variables) and a function set F (operators and basic functions) are prespecified to create initial population [41]. 2.2.2 MOEAs Definition [39] The basic structure of MOEA is shown in Fig 2.8. It includes: initialize population, evaluate population, scale population fitnesses, select solutions for next population and perform crossover and mutation. Fig 2.8 Basic Structure of MOEAs It is a generic populationbased metaheuristic algorithm inspired by biological evolution and can be viewed as an evolutionary process. It is characterized by the following components: Initialize population Scale population fitnesses Select solutions for next population perform crossover and mutation Evaluate population 21 A genetic representation (or an encoding) for the feasible solutions to the optimization problem: The genetic representation may differ considerably from the natural form of the parameters of the solutions. Fixedlength and binary encoded strings for representing solutions have dominated GA research since they provide the maximum number of schemata as they are amenable to simple implementation. A population of encoded solutions evolves over a sequence of generations: The population contains not just a sample of n ideas; rather it contains a multitude of notions and rankings of those notions for task performance. Genetic algorithms ruthlessly exploit this wealth of information by reproducing high quality notions according to their performance and crossing these notions with many other highperformance notions from other strings. A fitness function that evaluates the optimality of each solution: During each generation, the fitness of each solution is evaluated, and solutions are selected for reproduction based on their fitness. The ‘goodness’ of a solution is determined from its fitness value. Genetic operators generate a new population from the existing population: The selected solutions then undergo recombination under the action of the crossover and mutation operators. Control parameters: control every step of evolutionary process. 2.2.3 The main procedure of MOEAs [39] The first one is Reproduction or Selection Operator. Reproduction Operator makes duplicates of good solutions and eliminates bad solutions while keeping the whole population size constant. The whole process inscludes three steps: identify good solutions in a population, make multiple copies of good solutions and eliminate bad solutions from the population so that multiple copies of good solutions can be placed in the population. There are three types of Selection Operators to achieve the above task: 22 Tournament selection is played between two solutions and the better solution is chosen and placed in the mating pool. Each solution can be made to participate in exactly two tournaments and any solution in a population has 0, 1 or 2 copies in new populations. Proportionate selection assigns each solution copies, the number of which is proportional to their fitness value. For instance, a solution with a fitness value i f will get i avg f f number of copies. avg f denotes the average fitness of all population members. Therefore, the solution with a higher fitness value represents a large range of cumulative probability values and has a higher probability of being copied into the mating pool. Considering the scaling problem, the outcome of operator is dependent on the true value of the fitness rather than relative fitness values. Ranking selection sorts solutions according to their fitness (true value) from the worst to the best. Each member is assigned a fitness (relative value) equal to the rank of the solution. In most cases, proportionate selection is applied with the ranked fitness values. The second one is Crossover Operator. The power of GAs arises from crossover. Crossover causes a structured, yet randomized exchange of genetic material between solutions, with the possibility that ‘good’ solutions can generate ‘better’ ones. Crossover occurs only with some probability pc (the crossover probability or crossover rate). When the solutions are not subjected to crossover, they remain unmodified. The third one is Mutation Operator. Mutation appears to be more useful than crossover when the population size is small while there is evidence that crossover can be more useful than mutation when the population size is large. Other factors, such as the representation, selection scheme, and the fitness function itself may all have an effect on the relative utility of crossover and mutation. 2.2.4 Control Parameters of Genetic Algorithms [40] 23 To control the behavior of the GA, the role of the parameters pc and pm are often considered. The choice of pc and pm is known to critically affect the behavior and performance of the GA. The crossover probability pc controls the rate at which solutions are subjected to crossover. The higher the value of pc the quicker are the new solutions introduced into the population. As pc increases, however, solutions can be disrupted faster than selection can exploit them. Typical values for pc are in the range [0.5, 1.0]. Mutation is only a secondary operator to restore genetic material. Large values of pm transform the GA into a purely random search algorithm, while some mutation is required to prevent the premature convergence of the GA to suboptimal solutions. Typically pm is chosen in the range [0.005, 0.05]. The balance between converge and spread characteristics of the GA is dictated by the values of pc and pm. Increasing values of pc and pm promotes exploration at the expense of exploitation. Moderately large values of pc (0.51.0) and small values of pm (0.0010.05) are commonly employed in GA practice. Moderately large values of pc, (0.5 < pc < 1.0), and small values of pm (0.001 < pm < 0.05) are essential for the successful working of GAs. The moderately large values of pc promote the extensive recombination of schemata, while small values of pm are necessary to prevent the disruption of the solutions. 2.2.5 Some Examples of MOEAs Today, there are some MOEAs frequently used: SPEA 2 by Zitzler [13], NSGAII by Deb [14], IBEA by Zitzler [15], PESAII by Corne [16] and MOEA/D by Zhang [17]. In the experiment conducted in Chapter 4, these five algorithms are compared under the performance metric ensemble. 24 First, we consider Strength Pareto Evolutionary Algorithm 2 (SPEA 2). SPEA is an effective technique for finding or approximating the Paretooptimal set for multiobjective optimization problems. It has shown very good performance in comparison to other MOEAs. Based on SPEA, SPEA 2 incorporates a finegrained fitness assignment strategy, a density estimation technique, and an enhanced archive truncation method. The main structure of SPEA 2 is presented in Table 2.1. Table 2.1 includes input and output of the algorithm, and the process of the algorithm to deal with MOPs: Given input: N (population size), N (archive size) and T (maximum number of generations) Required output: A (nondominated set) Step1: Initialization: Generate an initial population 0 P and create the empty archive (external set) P0 =φ . Set t = 0. Step2: Fitness assignment: Calculate fitness values of individuals in t P and Pt Step 3:Environmental selection: Copy all nondominated individuals in t P and Pt to Pt+1 . If size of Pt+1 exceeds N then reduce Pt+1 by means of the truncation operator, otherwise if size of Pt+1 is less than N then fill Pt+1 with dominated individuals in t P and Pt . Step 4:Termination: If t ≥ T or another stopping criterion is satisfied then set A to the set of decision vectors represented by the nondominated individuals in Pt+1 . Step 5:Mating selection: Perform binary tournament selection with replacement on Pt+1 in order to fill the mating pool. Step 6: Variation: Apply recombination and mutation operators to the mating pool and set 1 t P + to the resulting population. Increment generation counter (t = t +1) and go to Fitness assignment step again. Table 2.1 The main structure of SPEA 2 25 In fitness assignment, each individual i in t P and t P is assigned a strength value S (i) representing the number of solutions it dominates: ( ) { } t t S i = j j∈P + P ∧ i f j (216 A) ⋅ denotes the cardinality of a set, + stands for multiset union and f corresponds to the Pareto dominance relation. Raw fitness R(i) is determined by the strengths of its dominators in both archive and population: ( ) ( ) j Pt Pt , j i R i S j ∈ + =Σ f (216 B) Density information is incorporated into differentiate individuals having identical raw fitness values: ( ) 1 k 2 i D i σ = + (216 C) where k = N + N is the square root of the sample size and k i σ is the k th element gives the distance sought. Finally, for an individual i , its fitness F (i) = R(i) + D(i) (216 D) In Environmental Selection, first, all nondominated individuals have fitness lower than one are copied to the archive of the next generation: t 1 { t t ( ) 1} P + = i i∈P + P ∧ F i < (217 A) 26 Then, there are three conditions: If Pt+1 = N , the environmental selection step is completed If Pt+1 < N , the best N − Pt+1 dominated individuals with F (i) ≥1 in the previous archive and population are copied to the new archive If Pt+1 > N , procedures are made to remove individuals from Pt+1 until Pt+1 = N At each iteration, individual i is chosen for removal for which d i ≤ j for all j∈Pt+1 : ( ) 1 1 : 0 : 0 : 0 : k k d t i j l l k k t i j i j i j k P k P l k σ σ σ σ σ σ + + ≤ ⇔∀ < < = ∨ ∃ < < ∀ < < = ∧ < (217 B) k i σ denotes the distance of i to its k th nearest neighbor in Pt+1 . The individual with the minimum distance to another individual is preferred. Second, we introduce NonDominated Sorting Genetic AlgorithmII (NSGAII). A nondominated sorting based multiobjective evolutionary algorithm NSGAII, has two advantages: computational complexity is O(mN2 ) ; a selection operator is presented to create a mating pool by combining the parent and child populations and selecting the best (with respect to fitness and spread) N solutions. The main structure of NSGAII is presented in Table 2.2. The third one is Regionbased Selection in Evolutionary Multiobjective Optimization (PESAII). PESAII proposes a new selection technique, called RegionBased selection, for evolutionary multiobjective optimization algorithms in which the unit of selection is a hyperbox 27 in objective space. A hyperbox is selected and the resulting selected individual is randomly chosen from this hyperbox. The fourth one is IndicatorBased Selection in Multiobjective Search (IBEA). IBEA is combined with arbitrary indicators and adapted to the preferences of the user and moreover does not require any additional diversity preservation mechanism to be used. It provides an approach to allow preference information of the decision maker be integrated into multiobjective search. Step1: Generate random parent population 0 P and its child population 0 Q : Initially, a random parent population 0 P is created. The population is sorted based on the nondomination. Each solution is assigned rank equal to its nondomination level where 1 is the best level. Thus, minimization of fitness is assumed. Binary tournament selection, recombination, and mutation operators are used to create a child population 0 Q of size N . Set t = 0 Step2: t t t R = P ∪Q Combine parent and children population. The population t R will have size 2N . Step3: F = nondominatedsort ( t R ) until 1 t P N + < Population t R is sorted based on the nondomination sorting. The new parent population 1 t P + is formed by adding solutions from the first front to the next best front before the size exceeds N . Step4: crowdingdistanceassignment ( i F ) and t 1 t 1 i P P F + + = ∪ Calculate crowding distance in i F and include k th nondominated front in the parent population. Step5: Sort ( 1 t P + , n ≥ ) and [ ] 1 1 0 : t t P P N + + = Sort in descending order and choose the first N elements of 1 t P + . Step6: t 1 Q + =makenewpop ( 1 t P + ) This population of size N is now used for selection, crossover and mutation to create a new population. Table 2.2 The main structure of NSGAII Table 2.3 presents the input and output of the algorithm, and the process of the algorithm to deal with multiobjective problem. 28 The final one is MOEA/D: A Multiobjective Evolutionary Algorithm Based on Decomposition. MOEA/D decomposes a multiobjective optimization problem into a number of scalar optimization subproblems and optimizes them simultaneously. Each subproblem is optimized by only using information from its several neighboring subproblems, which makes MOEA/D with lower computational complexity at each generation. Given input: α (population size), N (maximum number of generations) and κ (fitness scaling factor) Required output: A (Pareto set approximation) Step1: Initialization: Generate an initial population P of sizeα ; set the generation counter m to 0. Step2: Fitness assignment: First scale objective and indicator values, and then use scaled values to assign fitness values. Determine for each objective i f its lower bound min ( ) i x P i b f x ∈ = and upper bound max ( ) i x P i b f x ∈ = Scale each objective to the interval [0, 1], i, e, ' ( ) ( ( ) ) ( ) i i i i i f x = f x − b b − b Calculate indicator values I (x1, x2 ) using the scaled objective values ' i f , instead of the original i f , and determine the maximum absolute indicator value ( ) 1 2 1 2 , max , x x P c I x x ∈ = For all x1∈P set ( ) ({ } { }) ( ) { } 2 1 2 1 1 , \ I x x c x P x F x e − ⋅κ ∈ =Σ − Step3: Environmental selection: Iterate the following three steps until the size of population P does not exceed α : Choose an individual x∗ ∈P with the smallest fitness value, i.e. f (x∗ ) ≤ f ( x) for all x∈P . Remove x∗ from the population. Update the fitness values of the remaining individuals, i.e. ( ) ( ) ({ } { }) I x , x (c ) F x F x e − ∗ ⋅κ = + Step4: Termination: If t ≥T or another stopping criterion is satisfied then set A to the set of decision vectors represented by the nondominated individuals in P . Step5: Mating selection: Perform binary tournament selection with replacement on P in order to fill the mating pool. Step6: Variation: Apply recombination and mutation operators to the mating pool and add the resulting population to P . Increment generation counter ( t = t +1) and go to Fitness assignment step. 29 Table 2.3 The main structure of IBEA Table 2.4 presents the input and output of the algorithm, and the process of the algorithm to deal with multiobjective problem. Input: a stopping criterion; the number of the subproblems considered in MOEA/D; a uniform spread of N weight vectors: λ1,K ,λ N ; and T , the number of the weight vectors in the neighborhood of each weight vector. Output: External Population (EP) Step 1: Initialization: Set EP =∅. Compute the Euclidean distances between any two weight vectors and then work out the closest weight vectors to each weight vector. For each i = 1,K , N , set ( ) { } 1, , T B i = i K i , where λ1,K ,λ iT are the T closest weight vectors to λ i . Generate an initial population x1,K , xN randomly or by a problemspecific method. Set FV i = F (xi ) Initialize ( ) 1, , T m z = z K z by a problemspecific method. Step 2: Update For i = 1,K , N , do Reproduction: Randomly select two indexes k , l from B(i) , and then generate a new solution y from xk and xl by using genetic operators. Improvement: Apply a problemspecific repair/ improvement heuristic on y to produce y' Update of z∗ : for each j =1,K ,m , if ( ' ) j j z < f y , then set ( ' ) j j z = f y . Update of Neighboring Solutions: if gte ( y 'λ j , z ) ≤ gte (x j λ j , z ), for each index j∈B(i), set x j = y' and FV j = F ( y' ) . ( ) { ( ) } 1 te j j , max j i i i i m g x λ z∗ λ f x z∗ ≤ ≤ = − , λ1,K ,λ N be a set of even spread weight vectors and z∗ be the reference point. Update of EP: Remove EP from all the vectors dominated by F ( y' ) and add F ( y' ) to EP if no vectors in EP dominate F ( y' ) . Step 3: Stopping Criteria If stopping criteria is satisfied, then stop and output. Otherwise, go to Step 2. Table 2.4 The main structure of MOEA/D 2.3 Performance Metrics 30 In this part, first some important concepts are introduced. These are applied to define relations between different approximation fronts. Then, we will explain both unary and binary performance metrics in detail. 2.3.1 Outperformance Relations Hansen and Jaszkiewicz [9] have focused on the problem of evaluating approximations to the true Pareto front. They define a number of outperformance relations that classify the relationships between two sets of nondominated objective individuals while the preferences information of the test problem is unknown. Based on these, Knowles and Corne [18] further give two definitions about Monotony and Relativity. Weak Outperformance [9] A weakly outperforms B ( W AO B ): A weakly outperforms B if and only if nondominated points of A∪B are the same as the whole points in A , and A ≠ B . Therefore, each point 2 z ∈B is covered by a point 1 z ∈ A ; ‘cover’ means is equal to or dominates 2 z . Additional, there is at least one point 1 z ∈ A which is not contained in B . Adding to B a new nondominated individual can generate a new approximation front that weakly outperformB . Strong Outperformance [9] A strongly outperforms B ( S AO B ): A strongly outperforms B if and only if nondominated points of A∪B are the same as the whole points in A , and B contains another dominated points. Therefore, each point 2 z ∈B is covered by a point 1 z ∈ A . Additional, there is at least one point 2 z ∈B that is dominated by a point 1 z ∈ A and is not contained in B . Adding to B a new individual that dominates at least one point in B can generate a new approximation front that strongly outperformB . Complete Outperformance [9] 31 A completely outperforms B ( C AO B ): A completely outperforms B if and only if nondominated points of A∪B are the same as the whole points in A , and none of nondominated points of A∪B belongs to B . Therefore, each point 2 z ∈B is dominated by a point 1 z ∈ A . Adding to B a new individual that dominates all points in B can generate a new approximation front that completely outperformB . Incomparable Outperformance [9] A incomparable outperforms B is defined as some points in A dominate points in B and some points in B dominate points in A . In this condition, we cannot state that which one is better. Compatibility and Weak compatibility [9] Let , or W S C O = O O O : Compatibility: A comparison metric R is compatible with an outperformance relationO if for each pair of nondominated sets A and B , such that AOB , R will evaluate A as being better than B . Weak compatibility: A comparison metric R is compatible with an outperformance relation O if for each pair of nondominated sets A and B , such that AOB , R will evaluate A as being no worse than B . Monotony and Weak Monotony [18] Monotony: Given a nondominated set A , adding a nondominated point improves its evaluation. Compatibility with W O is necessary and sufficient for ensuring monotony [18]. Weak Monotony: Given a nondominated set A , adding a nondominated point does not degrade its evaluation. 32 Relativity and Weak Relativity [18] Relativity: The evaluation of Z∗ is uniquely optimal, i.e., all other nondominated sets have a strictly inferior evaluation. Compatibility with W O is sufficient but not necessary for ensuring relativity [18]. Weak Relativity: The evaluation of Z∗ is nonuniquely optimal, i.e., all other nondominated sets have a nonsuperior evaluation. From above theories, we can find AOC B⇒ AOS B⇒ AOW B and C S W O ⊂ O ⊂ O . Complete Outperformance is the strongest of the relation and easiest to be compatible; Weak Outperformance is the weakest of the relation and most difficult to be compatible. 2.3.2 Compatibility and Completeness Zitzler [10] has proposed a method that links Comparison Methods and Dominance Relations to reveal differences in performance between MOEAs, and make the statement that an algorithm outperforms another one. What conclusions can be drawn with respect to the dominance relations is emphasized. Quality Indicator: In order to quantify quality differences between approximation sets, quality measures are necessary used to map approximation sets to the real numbers by applying common metrics to the resulting real numbers. Based on this observation, Zitzler defines what a quality measure is: An m ary quality indicator I is a function I : m →R , which assigns each vector ( ) 1 2 , , , m A A K A of m approximation sets a real value, ( ) 1 2 , , , m I A A K A . 33 Often, not a single indicator but rather a combination of different quality indicators is used in order to assess approximation sets. The combination quality indicator vector can be regarded as a function that assigns each approximation set a vector of multiple real numbers. Comparison Method: Here, we use PseudoBoolean function E to compare different approximation sets. It maps vectors of real numbers to Booleans: E(I ) := (I =1) means E is true if and only if I = 0 . A comparison method I ,E C is based on a combination of one or more quality indicators I and a Boolean function E . Given two approximation sets A, B∈ , ( ) 1 2 , , , k I = I I K I a combination of quality indicators, and E : IRk × IRk →{false,true} a Boolean function, from Zitzler’s theory, If I ,E C is defined by combination of unary indicators and Boolean function E , ( ) ( ( ) ( )) , , , I E C A B = E I A I B ; If I ,E C is defined by combination of binary indicators and Boolean function E , ( ) ( ( ) ( )) , , , , , I E C A B = E I A B I B A Compatibility and Completeness: Compatibility: for any A, B∈ , the result of ( ) , , I E C A B can indicate that A is better than B , or B is better than A . Completeness: for any A, B∈ , the relation that A is better than B , or B is better than A can decide the value of ( ) , , I E C A B . 34 For a particular quality indicator, if there exists a Boolean function such that the resulting comparison method is compatible and in addition complete with respect to the various dominance relations (strong, weak or complete), this quality indicator can be evaluated to be powerful quality indicator. However, Zitzler [10] has proven there exists no comparison method based on a finite combination of unary quality indicators that is compatible and complete at the same time. It means for any combination of a finite number of unary quality indicators, a Boolean function cannot be found such that this comparison method is both compatible and complete. From the above reasons, the number of performance metrics that determine a better approximation set from two sets is infinite. Furthermore, to be able to detect whether an approximation front weakly dominates or dominates another approximation front, the number of performance metrics should be greater than or equal to the number of objectives. 2.3.3 Unary performance metrics The first type of performance metrics concerns about assessing the Number of Pareto Optimal Solutions in the Set. Ratio of Nondominated Individuals (RNI) [5] gives the proportion of the useful solutions known as the Paretofront in a given population size; Error Ratio (ER) [4] evaluates the proportion of non true Pareto points in the approximation front; Overall Nondominated Vector Generation and Ratio (ONVG) [4] counts the number of distinct nondominated points generated; and Pareto Dominance Indicator (NR) [3] measures the ratio of nondominated solutions contributed by a particular solution set to the nondominated solutions provided by all solution sets. Ratio of Nondominated Individuals (RNI) [5] The performance measure is: 35 _ ( ) nondom indiv RNI X P = (218) nondom_ indiv : Nondominated individuals in population X with size P . If RNI =1 , all the individuals in X are nondominated; and if RNI = 0 , none of the individuals in X is nondominated. It is always required to have enough qualified individuals to construct a Pareto front. Therefore, RNI is significant in that it checks the proportion of nondominated individuals in population X . Knowles and Corne in [18] have stated that: RNI is not weakly compatible with any outperformance relation. It exhibits monotony. Clearly, add a nondominated point will make the RNI value better. It violates relativity. True Pareto front cannot be sure to have more numbers of nondominated points than other approximation fronts. Error Ratio (ER) [4] It is defined as the proportion of non true Pareto points in reference set: ( ) ( ) 1 n i i e ER X P = = Σ (219) Individual i is a point in approximation front X . P is the number of individuals in X . 0 i e = means individual i is in true Pareto set; and 1 i e = means individual i is not in true Pareto set. Lower value of ER implies a small proportion of non true Pareto points in X and represents better nondominated sets. It is a reference metric using true Pareto front as reference set. Knowles and Corne in [18] have stated that: ER is only weakly compatible with C O . It is not weakly compatible with S O or W O . If one algorithm generates 100 points, one in the Pareto front, 36 the other 99 points are very far from the Pareto front; its error ratio is 0.99. However, if another algorithm also generates 100 points, all these 100 points are very close to Pareto front, its error ratio is 1. Although the second algorithm’s error ratio is larger than the first one, we can see clearly the second one is better than the first one. ER strongly violates monotony: Add a nondominated but nonPareto optimal points in an approximation set, makes the ER score worse. The advantage is easy to understand and easy to calculate. It is scaling independent. The disadvantage is the true Pareto front information is needed. It is incompatible with the outperformance relations. Overall Nondominated Vector Generation and Ratio (ONVG) [4] It measures the total number of nondominated vectors found in approximation front during MOEA execution. It is defined as: ONVG = PFknown (220) known PF represents approximation front. From [19], too few vectors in known PF make the front’s representation poor and too many vectors may overwhelm the decision maker. Knowles and Corne in [18] have stated that: ONVG is not weakly compatible with any outperformance relation. It does not exhibit either weak monotony or weak relativity. The advantage is easy to calculate and scaling independent while the disadvantage is A outperformance B on this metric does not mean A is clearly better than B . Pareto Dominance Indicator (NR) [3] Considering the different PFs , 1 2 , , n A A K A evolved by algorithms, this metric measures the ratio of nondominated solutions that is contributed by a particular solution set i A to the nondominated solutions provided by all solution: 37 ( ) 1 1 2 , ,..., n B A NR A A A B = I (221 A) { ( ) } 1 2 , ... i i j n i B = b ∀b ¬∃a ∈ A U A U A p b (221 B) 1 A is the solution set under evaluation. Zitzler show that no combinations of unary performance metrics can provide a clear indication of whether an evolved set is better than another in the Pareto dominance sense, this metric can be a complement to another metrics [1]. It is weak compatible with S O and C O . The second type of performance metrics focuses on measuring the closeness of the solution to the True Pareto Front. Generational Distance (GD) [4] measures how far the evolved solution set is from the rue Pareto front; and Maximum Pareto Front Error (MPFE) [4] identifies the largest distance between the point in the theoretical Pareto front and the point in the approximation front. Final Generational Distance (GD) [4] ( )1 1 n p p i i d GD n = = Σ (222) n is the number of vectors in the approximation front, i d is the distance in objective space between individual i and the nearest member of true PF .This metric is a value representing how “far” the approximation front is from true Pareto front. Lower value of GD represents better performance. It measure general process towards true Pareto front [18]. It is a reference metric using true Pareto front as reference set. Knowles and Corne in [18] have proven that GD is not weakly compatible with W O , but is compatible with S O . It violates weak monotony which implies adding a nondominated point to 38 an approximation fronts cannot improve its GD value. It exhibits weak relativity since any subset of Pareto front has an optimal GD. For a constant size of nondominated set, GD is compatible with S O . But it is not used for nondominated sets that are changing in cardinality. It cannot be reliably differentiate between different levels of complete outperformance. The true Pareto front information is needed. Maximum Pareto Front Error (MPFE) [4] It measures the largest distance between any vector in the approximation front and the corresponding closest vector in true Pareto front. It finds the largest distance between individual j in approximation front and individual i in the true Pareto optimal front. ( ( ) ( ) ( ) ( ) )1 1 1 2 2 max min p p p i j i j j i MPFE = f x − f x + f x − f x (223) It is a reference metric using true Pareto front as reference set. In terms of Pareto compatibility, it is not weakly compatible with outperformance relation. It violates weak monotony. It exhibit weak relativity since any subset of Pareto front is optimal. It is cheap to compute. It helps us to focus on how far the worst point is. However, from [19], for a nondominated set, a good performance in MPFE does not ensure it is better than another one with a much worse MPFE. The true Pareto front information is needed. The third type of performance metrics measures distribution of the Solutions. Uniform Distribution (UD) [5] measures the distribution of an approximation front under a predefined parameter share σ ; Spacing [6] measures how evenly the evolved solutions distribute itself; and Number of Distinct Choices (NDCu) [7] identifies solutions that are sufficiently distinct for a special valueu . Uniform Distribution (UD) [5] 39 It measures the distribution of nondominated individuals on the found tradeoff surface. For a given set of nondominated individuals X ' in a population X : ' 1 ( ) 1 nc UD X S = + (224 A) ( ) ' ' ' ( ' ) 1 x N i i nc x nc x nc X S N − − = − Σ (224 B) ( ) ' ' , ( , ) x N i j j i nc x f i j ≠ = Σ (224 C) ( ) {1, ( , ) 0. , dis i j share else f i j 〈δ = (224 D) ( ) ( ) ' ' ' ' x N i i x nc x nc X N − = Σ (224 E) share σ is predefined by decision maker. nc S is the standard deviation of niche count of the overall set of nondominated individuals. ' x N is the size of the set x' . ( ' ) i nc x is the niche count of the ith individual x' and dis (i, j ) is the distance between individual i and j in the objective domain. Knowles and Corne in [18] have proven that: UD is not even weakly compatible with W O . It violates monotony in that an additional point cannot make sure the distribution is improved. It violates relatively. An approximation front far from the Pareto front can have the same UD score to the Pareto front. It has low computational overhead and provides the opportunity for Decision maker to choose well distributed front according to real application need by assigning different value to share σ . However, it is difficult to choose share σ without any reference information. 40 Spacing [6] This metric is a value measuring the distribution of vectors throughout approximation front. It provides information about the distribution of vectors obtained. Because approximation front’s “beginning” and “end” are known, a suitably defined metric judge how well known PF is distributed. 2 1 1 1 n i i S d d n − + = − − Σ (225 A) ( ( ) ( ) ( ) ( ) )2 2 1/ 2 1 1 2 2 min i j i j i j d = f x − f x + f x − f x (225 B) i d is minimum distance between two solutions in the approximation front. Knowles and Corne in [18] have stated that: Spacing is not even weakly compatible with W O . It violates monotony in that an additional point cannot make sure the distribution is improved. It violates relatively. An approximation front far from the Pareto front can have the same Spacing score to the Pareto front. It has low computational overhead and can be generalized to more than two dimensions by extending the definition of i d . But the use of normalized distances may be problematic. Number of Distinct Choices (NDCu) [7] In this metric, only those solutions that are sufficiently distinct from one another should be accounted for as useful design options. The quality ( , ) u NT q P indicates whether or not there is any point k p ∈P that falls into the region. ( ) u T q is decided by 1 um , 0 < u <1.m is the dimension of objectivespace ( ) ( ) {1, , ( ) 0, , , k k u k k u p P p T q u p P p T q NT q P ∃ ∈ ∈ ∀ ∈ ∉ = (226 A) ( ) u NDC P is the number of distinct choices for a prespecified value ofu : 41 ( ) ( ) 2 1 1 1 1 0 0 0 ... , m v v v u u l l l NDC P NT q P − − − = = = = Σ ΣΣ (226 B) From [7], for a prespecified value ofu , an observed Pareto solution set with a higher value of the quantity ( ) u NDC P is preferred to a set with a lower value. In terms of Pareto compatibility: u NDC is not even weakly compatible with W O . It violates monotony in that an additional point cannot make sure the distribution is improved. It violates relatively. An approximation front far from the Pareto front can have the same Spacing score to the Pareto front. It provides the opportunity for Decision maker to choose well distributed front according to real application need by a prespecified value of u . However, it is not easy to compute. The fourth category of performance metrics concerns spread of the solutions. Maximum Spread (MS) [3] measures how well the rue Pareto front is covered by the approximation set. Maximum Spread (MS) [3] It addresses the range of objective function values and takes into account the proximity to true PF . This metric is applied to measure how well the true PF is covered by the known PF . ( ) ( ) ( ) 2 max max min min max min 1 1 M min , max , i i i i i i i f F f F MS M = F F − = − Σ (227) max i f and min i f are the maximum and minimum of the i th objective in known PF , respectively; max i F and min i F are the maximum and minimum of the i th objective in true PF , respectively. If MS ( A) > MS (B) , the solution A is preferred to B . The last type of performance metrics considers both closeness and diversity: 42 Hypervolume Metric [11] The hyperarea difference metric [11] is also called Smetric and can be used to quantitatively evaluate the difference between the size of the objective space dominated by an observed Pareto front and that of the space dominated by the true Pareto front. The true Pareto front set dominates the largest volume in solution space while an approximation front may only dominate a portion of true Pareto front dominated volume. A quantitative measure is obtained as to how much worse an observed Pareto front is when compared to the true Pareto front. Although in real problem, the true Pareto front is usually unknown; it should still be possible to compare an approximation front to another so as to draw a conclusion that which front is better. Let HD(P) represent the hypervolume difference quantity between the inferior regions of the true Pareto solution set t P and the inferior region of the observed Pareto solution set P [7]: ( ) ( ( ) ( )) 1 ( ( )) in t in in HD P = space S P − S P = − space S p (228) In [4], Veldhuizen also propose a Hyperarea Ratio metric defined as: 1 2 H HR H = (229) 1 H is the hyperarea of known PF while 2 H is that of true PF .. In the proposed performance metrics ensemble to be presented in Chapter 3, we adopt this modified Hyperarea Ratio Metric. It is compatible with all the outperformance relations [18]. Each algorithm can be assessed independently of the other algorithms in this metrics. Hypervolume Metric differentiates between different degrees of complete outperformance of two sets, so it can evaluate how much better an 43 approximation set is than the other approximation set. It is scaling independent, noncardinal and its meaning is intuitive. It can be misleading if the Pareto optimal front is nonconvex [3]. Therefore, it focuses on the volume of the objective space dominated by an approximation set and calculates the hypervolume of the multidimensional region enclosed by approximation front and a ‘reference point’ [18]. A reference point is also called the upper boundary of the region. The choice of the upper boundary determines which approximation front has the maximum dominated hypervolume. In many cases, we need to find the reference point to represent the upper boundary of the region. The reference point should be chosen so that it is dominated by all Paretooptimal solutions. Auger and Zitzler [20] have proposed a method to define the reference point r = (r1, r2 ) for a specific problem: Let u be an integer larger than or equal to 2. Assume that f is continuous on[ ] min max x , x , nonincreasing, differentiable on [ ] min max x , x and that f’ is continuous on[ ] min max x , x : The leftmost extremal point: If ( ) min limx x f x → − < +∞: [ ] { ( )( ) ( )} min max ' 2 max , : sup x x x R f x x x f x ∈ = − + (230) When 2 R is finite, the leftmost extremal point is contained in optimal u distributions if the reference point ( ) 1 2 r = r , r is such that 2 r is strictly larger than 2 R . 2 r can be chosen to be 2 R . If ( ) min limx x f x → − = +∞ , the left extremal point of the front is never included in optimal udistributions. So, 2 r = +∞. 44 The rightmost extremal point: when f is strictly negative on[xmin , xmax ] : [ ] ( ) ( ) ( ) min max min 1 ' , : sup x x x f x f x R x ∈ f x − = + (231) When 1 R is finite, the rightmost extremal point is contained in optimal u distributions if the reference point ( ) 1 2 r = r , r is such that r1 is strictly larger than 1 R . 1 r can be chosen to be 1 R . If ( ) max f x = 0 , the right extremal point of the front is never included in optimal u  distributions. So, 1 r = +∞ . Hypervolume metric also has a large computational overhead. Largest computation is defined [21] by Klee’s Measure Problem (KMP) and lowest computation is defined by the UniformGap Problem. KMP is the problem of computing the length of the union of a collection of intervals on the real line and defines the upper boundary of the computation. It can be solved with computational complexity in optimal O(nlog n) time. First, measure of a union of hyperrectangles in d dimensions: O(nd −1 log n)⇒O(nd −1 )⇒O(nd 2 log n) . Second, the weakly dominated hypervolume for a point set 0 P IRd ≥ ⊆ as a special case of Klee’s measure problem: The polytope Πd is patterned by the collection of hyperrectangles { } p p P R ∈ with { } 0 : d : p R x IR x p ≥ = ∈ ≤ spanned by the points in P and the reference point 0 r 0 IRd ≥ = ∈ . Third, the set of hyperrectangles is the input and the desired hypervolume output. Finally, we get an upper bound of computation time in O(nlog n + nd 2 log n) . The best upper bound currently known for d > 3:O(nlog n + nd 2 ) 45 The UniformGap Problem defines the lower boundary of the computation. This problem uses the fixeddegree algebraic decision tree, which is the standard model used in computational geometry and is used to prove lower bounds for (geometric) decision problems. It captures the behavior of a (loopunrolled) algorithm that branches depending on the outcome of evaluations of boundeddegree polynomials. A lower bound on the complexity of a given problem can then be derived by establishing a lower bound on the depth of any such tree resembling any valid algorithm to solve this problem. Moreover, lineartime reduction from problem A to problem B means the lower bound for problem A is a lower bound for problemB . 2.3.4 Binary performance metrics The first type of binary performance metrics based on unary quality indicator. It includes ε  indicator Iε , enclosing hypercube Indicator and coverage difference metrics (Dmetric). First, ε indicator Iε [10] can be used to compare algorithms directly without reference front information. This is defined as: ( , ) inf { 2 1 : 1 2} R I A B z B z A z z ∈ ε∈ ε = ∀ ∈ ∃ ∈ ≥ (232 A) 1 2 1 : 1 2 i i z z i n z z ε ≥ ⇔∀ ≤ ≤ ≤ε ⋅ (232 B) I ( A,B) ∈ reflects the value ofε . For every individual z2 in B , there must exist an individual z1 in A dominateε ⋅ z2 . For any pair A, B∈ , A B I ( A,B) 1 ∈ f f ⇒ < .Therefore, if A is better than B , ε <1 46 However, I ( A, B) 1 ∈ < can only imply that A is not worse than B in strictly dominates and better relations. Second, Enclosing Hypercube Indicator [10] is defined as: ( ) {{( )} } 1 HC sup , ,..., a R I A a a a A ∈ = > (233 A) ( ) {{( )} } 2 HC inf , ,..., b R I A b b b A ∈ = < (233 B) ( ) ( ) 2 1 I HC A < I HC B ⇒ A> B ∀1≤ i ≤ n +1 (233 C) ( ) 2 I HC A is the point that worse than all individuals in A . ( ) 1 I HC B is the point that better than all individuals in B . Finally, coverage difference metrics (Dmetric) [11] is defined as the size of the space dominated by A and not dominated by B (regarding the objective space), A, B ⊆ X be two sets of decision vectors. D( A,B) = S ( A + B) − S (B) (234 A) where S ( A) is the Hypervolume Difference Metric (Smetric). Zitzler [11] suggest that (ideally) the D metric is used in combination with the S metric where the values may be normalized by a reference volume V , where (for a maximization problem) V is given by: ( max min ) 1 k i i i V f f = =Π − (234 B) 47 max i f and min i f represent the maximum respectively minimum value for the objective i f . Thus, the value ( ) ( ) 1 , , D A B D A B V = represents the relative size of the region (in the objective space) dominated by A and not dominated by B . The second type is direct comparison binary metrics: C metrics and R metrics. C metrics [9] maps the ordered pair ( A,B) to the interval[0,1]: ( ) { : } , b B a A a b C A B B ∈ ∃ ∈ ≤ = (235) C( A,B) =1: all decision vectors in B are weakly dominated by A ; C( A,B) = 0 : none of the points in B are weakly dominated by A . It is compatible with S O and C O , but incompatible with W O . Only if C( A,B) =1 andC(B, A) <1 , it is compatible with W O . It is Nonsymmetric: C( A,B) is not necessarily equal to −C(B, A) . It has low computational overhead. Scale and reference point independent. However, there are situations when the metric C cannot decide if an obtained front is better than the other. R metrics [5] consist of three submetrics: R1( A,B,U, p) , R2( A,B,U, p) and R3( A,B,U, p) . R1( A,B,U, p) calculates the probability that approximation A is better than approximation B over an entire set of utility functions. 1( , , , ) ( , , ) ( ) u U R A B U p C A B u p u du ∈ = ∫ (236 A) ( ) ( ) ( ) ( ) ( ) ( ) ( ) 1, , , 1 2, 0, u A u B C A B u u A u B u A u B ∗ ∗ ∗ ∗ ∗ ∗ > = = < (236 B) 48 ( ) max { ( )} z A u∗ A u z ∈ = , ( ) max { ( )} z B u∗ B u z ∈ = and p(u) is an intensity function expressing the probability density of the utility. If R1( A,B,U, p) > 0.5 , A is the winner; if R1( A,B,U, p) < 0.5 , B is the winner. In terms of Pareto compatibility: R1 is only weakly compatible with W O and is not compatible with C O . It has low computational overhead and Scale independent but R1 is cycleinducing. R2( A,B,U, p) calculates the expected difference in the utility of an approximation A with another one B . 2( , , , ) ( ( ) ( )) ( ) u U R A B U p u∗ A u∗ B p u du ∈ = ∫ − (237) R2 is compatible with W O . It can differentiate between different levels of complete outperformance. However, each utility function in U must be appropriately scaled with respect to the others and its relative importance. R3( A,B,U, p) calculates the ratio of the best utility values. That is the expected proportion of superiority. ( ) ( ( ) ( )) ( ) 3 , , , ( ) u U u A u B R A B U p p u du u A ∗ ∗ ∗ ∈ − = ∫ (238) 49 CHAPTER THREE METHODOLOGY This chapter first explains the motivation of the designed performance metrics ensemble. Then, we describe the proposed approach in detail. 3.1 MOTIVATION Chapter 2 has introduced a large number of available performance metrics with different characteristics. However, none of these metrics alone can faithfully measure MOEA performance independently. Every metric can provide some specific but limited information and can only be used effectively in some specified conditions. For example, UD does a poor job when the Pareto front is discontinued and Hypervolume can be misleading if the Pareto optimal front is nonconvex [4]. This means one metric cannot entirely evaluate MOEAs in all conditions. Every metric focuses on some special characteristics while neglects information in others. Also, every metric has its unique character; no metrics can substitute others completely. Therefore, a single metrics cannot provide a comprehensive measure for MOEAs. Moreover, because reduce objective space must losing information, a fixed number of indicators are not sufficient to make a comprehensive measure for MOEAs [11]. Meanwhile, different metrics perform differently in different test problems. For a given MOEA, one metric may do well in one test problem, however, in other test problems, it may be misleading. For a specific test problem, we cannot know which metric is better. We need to try various metric to identify which one is the best. This is a heavy computational process. To overcome these challenge and arrive at a faithful evaluation of a given MOEAs, performance metrics ensemble is necessary. Ensemble fair performance than what Ensemble metrics not only but avoid the choosing process and can be 3.2 OVERVIEW OF PERFORMANCE METRICS ENSEMBLE The proposed framework is shown in Figure 3.1 Table 3.1 explains the whole process of ensemble method in detail. 50 given the same initial populations to each and every candidate MOEAs are performed, resulting 50 approximation fronts from each chosen MOEA for comparison. DoubleTournament Selection, every individual to compete. After one winner is found, identify which algorithm it is 50 method uses multiple metrics to obtain could be obtained from any of single performance can give the comprehensive comparison between different algorithms, he directly used to assessing MOEAs. he Fig 3.1 The proposed framework Then, in (i.e., approximation front) has two from; remove all the fronts a metric alone. independent trials the proposed opportunities 51 of that algorithm and compare others again. Finally, all the algorithms will be assigned a rank value. Input: A number of MOEAs for comparison Output: Rank Value of the chosen MOEAs Step 1: Generate 50 approximation fronts from each MOEA: The selected MOEAs run 50 times for a given benchmark problem under the same initial conditions. Every time, each MOEA generate an approximation fronts while each front represents its algorithm. After that, a single performance metric in the performance metrics ensemble is randomly chosen to measure the quality of each front, and the best approximation front is picked up based on that performance pertained to the chosen benchmark problem at hand. After 50 running times, we get 50 approximation fronts. Step 2: Use DoubleTournament Selection to get the best one individual: i. Every 2 individuals are randomly picked to form competition pair. One performance metric is randomly chosen in each competition. Each pair will generate a winner and a loser. After all the competition, two parts are created: W1 contains all the winners named winner bracket; the other L1 contains all the losers named loser bracket. ii. In both W1 and L1, the same competition is performed again and each package can be divided into two subpackages. One subpackage contains winners, the other losers. W1 is divided into W11 (winners) and W12 (losers); L1 is divided into L11 (winners) and L12 (losers). Then, individual of W12 will compete with individual of L11 one by one. Winners from these competitions consist of a new loser bracket L13. We reserve W11 and L13.Therefore, the population is reduced to an half. iii. In both W11 and L13, do as Step ii again. Every time, reduce the population by half. Finally, only one individual wins at the very end. Step 3: Assign every MOEA a rank value Identify from which MOEA this winner front comes from. Assign this algorithm rank value 1. Then, eliminate all the approximate fronts generated by this algorithm in the 50 approximate fronts. Go back to step 2 and compare remaining fronts from all MOEA (less the winner with rank 1) again. Finally, we will assign each algorithm a rank value implying its ranking order through the proposed performance metrics ensemble. Table 3.1 The Whole Process of Ensemble Method 3.3 ENSEMBLE METHOD WITH DOUBLETOURNAMENT SELECTION 3.3.1 DoubleTournament Selection 52 The Modified Double Tournament algorithm selects an individual using tournament selection: at the initial step, the tournament contestants are chosen at random from the population. Then, at the following step, they are each the winners of last tournament selection. For example, imagine if the tournament has a pool size of 32: first, the 16 “qualifier” tournaments are held as normal in tournament selection, and the whole pool is divided into two parts: winner bracket contains 16 winners and loser part 16 losers. Then, in each of the part, 8 normal tournament selections are processed so that the part is divided again. In both parts, there are 8 new winners and 8 new losers. Afterward, we compete 8 winners from loser bracket with 8 losers from winner bracket. Here, two individuals come into one tournament selection should be from different part, that means, one individual from winner bracket is compared with one individual from loser bracket. Therefore, we get 8 winners from this step. This process reduces the total number of individuals from 32 to 16. Continue to do it, 16→8→4→2→1, finally, we obtain the ultimate winner. This ultimate winner defeats all other 31 competitors. The motivation for applying DoubleTournament Selection is that it gives every individual two chances to take part in the competition. This advantage is helpful to reserve good individual. Because of the stochastic process, one approximation front from a quality MOEA may lose the competition at time when a metric measuring the very deficient aspect of problem characteristics is applied. If this happens in the single elimination tournament, the front will be lost forever and it would not have any chance to compete again. However, in the DoubleTournament Selection, even it loses once, it has an opportunity to compete again and hopefully win at all. For example, in NCAA basketball tournament, the last year’s champion team will versus the winner of the 64th and 65th team. Of course, the probability that the champion team wins is very large, but basketball game bears a huge number of uncertain factors, there exists probability that the 64th team wins. In this condition, if single elimination is used, the last year’s champion team 53 loses at all. We will not see the excellent performance of this team in the following games of this year. This will be a great loss for audience! In DoubleTournament Selection, the champion team will have another chance to compete in the loser bracket; it can make up its mistake in the last game and win again. Therefore, in MOEAs comparison, if a really good front loses its game at one competition, it has the opportunity to win at another time. Double elimination design allows specific characteristicpoor performance of a quality algorithm under the special environment still to be able to survive through competitions and win it all. 3.3.2 Ensemble Method with DoubleTournament Selection The goal of Ensemble Metrics is that Ensemble Metrics can benefit us for its specific ensemble advantages which accomplish the work that single metric cannot. In the following chapter, we choose five stateoftheart MOEAs to compare and five performance metrics to assess, every algorithm need to run 50 times because of the stochastic nature of MOEAs. In every running time, one algorithm produces one approximation front. Given the same initial population, five fronts from five different algorithms go to competition in a pool under evaluation of a randomly chosen performance metric and one best front wins according to this metric. After 50 running times, 50 winners are generated. Here, maybe many of 50 winners come from the same MOEA or none of 50 winners represents a specific algorithm. In every 50 running time, the probability of each metric to be chosen is 0.2, so the average times each metric to be used is 10. This guarantee every metric to be chosen often and the 50 winners are decided by all five metrics collectively. Then, these 50 winners are taken as the input to DoubleTournament Selection. Here, we just consider 50 fronts as 50 individuals without concerning about its representing algorithm. 54 Process: 1) Every 2 of 50 individuals are randomly picked to form a competition pair. For every competition, one metric is randomly chosen. Then, the total 25 pairs generate 25 winners and 25 losers. Create two parts: one contains 25 winners named winner bracket; the other contains 25 losers named loser bracket. 2) In each of the part, first randomly choose an individual, the remaining 24 individuals form 12 pairs of competitions; every pair uses a randomly chosen metric, too. Therefore, every part has 12 new winners and 12 new losers. Put the first chosen individual into both winners and losers. This will make the number of both winners and losers to be 13. 3) 13 losers in winner bracket and 13 winners in loser bracket (i.e., each individual losss only once) are combined together to compete. Every competition contains one individual from winner bracket and one from loser bracket. Then, 13 winners are generated and consist of a new loser bracket. The other 13 losers and 13 losers in original loser part (i.e. each losses twice) are eliminated. 4) Now, both new winner bracket and new loser bracket contain 13 individuals. We finish this step that reduces the number of competitors from 50 to 26 (i.e., 13 winners + 13 losers). 5) Then continue to do Step 2 and Step 3. We reduce the number of competitors from 26 to 14 (7 winners + 7 losers), then from 14 to 8 (4 winners + 4 losers), then from 8 to 4 (2 winners + 2 losers), then from 4 to 2 (1 winners + 1 losers) and finally from 2 down to 1. The last remaining individual is the final champion. 6) Check which evolutionary algorithm regarding the final winner comes from. Then we can conclude which algorithm is the best. 7) Remove all the fronts come from the best algorithm and compare other fronts from Step 1 to Step 6 again. So we can arrive at the second best one. 8) Continue to do Step 7; finally, we obtain the ranking of all the algorithms. The whole process is end. In this modified Double defeat others under all the performance metrics mechanism for choosing metrics in every competition time. Therefore, the rank of all the algorithms is based on all the metrics Figure 3.2 uses graphs to explain each step Fig 3.2 (a) From 50 individuals to 26 individuals Fig 3.2 (b) From 26 individuals to 14 individuals 55 n DoubleTournament Selection, to be the final winner, the MOEA in double elimination because of stochastic collectively. of DoubleTournament Selection , must Selection: Fig 3.2 (c) From 14 individuals to 8 individuals Fig 3.2 (d) From 8 individuals to 4 56 individuals Fig 3.2 (e) From 4 individuals to 2 individuals Fig 3.2 (f) From 2 individuals to 1 individuals 57 58 CHAPTER 4 FINDINGS 4.1 EXPERIEMENT RESULTS This part will show all experiment results in benchmark functions: ZDT1, ZDT2, ZDT3, ZDT4, ZDT6 and DTLZ2, respectively. 4.1.1 ZDT 1 First, box plot for every performance metric measure is presented: GD Metric For each algorithm, the less the GD value, the better the algorithm’s performance: 4.1(a) GD metric value in ZDT 1 Here, in graph’s x axis, ‘1’ represents SPEA 2, ‘2’ represents NSGAII,’3’represents IBEA, ‘4’ represents PESAII and ‘5’ represents MOEA/D. y axis shows the metric value. 0 0.05 0.1 0.15 0.2 0.25 0.3 1 2 3 4 5 59 Spacing Metric For each algorithm, the less the Spacing value, the better the algorithm’s performance: 4.1(b) Spacing metric value in ZDT 1 Here, in graph’s x axis, ‘1’ represents SPEA 2, ‘2’ represents NSGAII,’3’represents IBEA, ‘4’ represents PESAII and ‘5’ represents MOEA/D. y axis shows the metric value. NR Metric For each algorithm, the more the NR value, the better the algorithm’s performance: 4.1(c) NR metric value in ZDT 1 0 0.05 0.1 0.15 0.2 0.25 1 2 3 4 5 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 1 2 3 4 5 60 Here, in graph’s x axis, ‘1’ represents SPEA 2, ‘2’ represents NSGAII,’3’represents IBEA, ‘4’ represents PESAII and ‘5’ represents MOEA/D. y axis shows the metric value. Smetric For each algorithm, the more the S value, the better the algorithm’s performance 4.1(d) Smetric value in ZDT 1 Here, in graph’s x axis, ‘1’ represents SPEA 2, ‘2’ represents NSGAII,’3’represents IBEA, ‘4’ represents PESAII and ‘5’ represents MOEA/D. y axis shows the metric value. MS Metric For each algorithm, the more the MS value, the better the algorithm’s performance 4.1(e) MS metric value in ZDT 1 0.73 0.74 0.75 0.76 0.77 0.78 0.79 0.8 0.81 0.82 0.83 1 2 3 4 5 0.84 0.86 0.88 0.9 0.92 0.94 0.96 0.98 1 2 3 4 5 61 Here, in graph’s x axis, ‘1’ represents SPEA 2, ‘2’ represents NSGAII,’3’represents IBEA, ‘4’ represents PESAII and ‘5’ represents MOEA/D. y axis shows the metric value. Then, experiment results using ensemble performance metrics in ZDT 1 is given: Step 1 generates 50 fronts as the initial population of DoubleTournament Selection: in these 50 winner fronts, SPEA 2 wins 18 times, NSGAII wins 12 times, IBEA wins 2 times, PESAII wins 4 times and MOEA/D wins 14 times. In this step, metrics are totally chosen 50 times: GD is chosen 17 times, NR is 12 times, Spacing is 8 times, Smetric is 6 times and MS is 7 times. Step 2 is the first step of DoubleTournament Selection that 50 fronts are competed to generate 26 winners: in these 26 winner fronts, SPEA 2 wins 10 times, NSGAII wins 7 times, IBEA wins 0 times, PESAII wins 1 time and MOEA/D wins 8 times. In this step, metrics are totally chosen 62 times in two parts: The total 50 fronts are divided into 2 groups in first 25 times: GD is chosen 4 times, NR is 4 times, Spacing is 6 times, Smetric is 6 times and MS is 5 times. 26 winners are generated from both Winner group and Loser group in 37 times: GD is chosen 7 times, NR is 4 times, Spacing is 8 times, Smetric is 8 times and MS is 10 times. Step 3 is the second step of DoubleTournament Selection that 26 fronts are compared to generate 14 winners: in these 14 winner fronts, SPEA 2 wins 5 times, NSGAII wins 4 times, IBEA wins 0 times, PESAII wins 1 time and MOEA/D wins 4 times. In this step, metrics are totally chosen 19 times: GD is chosen 5 times, NR is 4 times, Spacing is 5 times, Smetric is 2 times and MS is 3 times. In the third step (Step 4) of DoubleTournament Selection that 14 fronts are compared to generate 8 winners: in these 8 winner fronts, SPEA 2 wins 3 times, NSGAII wins 3 times, IBEA wins 1 time, PESAII wins 0 times and MOEA/D wins 1 time. In this step, metrics are totally chosen 10 times: GD is chosen 2 times, NR is 2 times, Spacing is 3 times, Smetric is 2 times and MS is 1 time. 62 Step 5 is the fourth step of DoubleTournament Selection that 8 fronts are compared to generate 4 winners: in these 4 winner fronts, SPEA 2 wins 2 times, NSGAII wins 1 time, IBEA wins 0 times, PESAII wins 0 times and MOEA/D wins 1 time. In this step, metrics are totally chosen 6 times: GD is chosen 0 times, NR is 1 time, Spacing is 1 time, Smetric is 2 times and MS is 2 times. In the fifth step (Step 6) of DoubleTournament Selection that 4 fronts are compared to generate 2 winners: in these 2 winner fronts, SPEA 2 wins 1 time, NSGAII wins 1 times, IBEA wins 0 time, PESAII wins 0 times and MOEA/D wins 0 time. In this step, metrics are totally chosen 3 times: GD is chosen 1 time, NR is 1 time, Spacing is 0 times, Smetric is 0 times and MS is 1 time. In the final step (Step 7) of DoubleTournament Selection that 2 fronts are compared to generate 1 winner. The final winner is SPEA 2 and GD is chosen to compare. In Step 8, remove all the fronts from SPEA 2 in 50 fronts obtained in the first step, continue step 1 to step 7, NSGAII is the second best one and MOEA/D is the third one. After all the remaining fronts come from the same algorithm, we get the final rank value for ZDT 1: Rank 1: SPEA 2; Rank 2: NSGAII; Rank 3: MOEA/D; Rank 4: PESAII; Rank 5: IBEA. 4.1.2 ZDT2 First, box plot for every performance metric measure is presented: GD Metric For each algorithm, the less the GD value, the better the algorithm’s performance: 63 4.2(a) GD metric value in ZDT 2 Here, in graph’s x axis, ‘1’ represents SPEA 2, ‘2’ represents NSGAII,’3’represents IBEA, ‘4’ represents PESAII and ‘5’ represents MOEA/D. y axis shows the metric value. Spacing Metric For each algorithm, the less the Spacing value, the better the algorithm’s performance: 4.2(b) Spacing metric value in ZDT 2 Here, in graph’s x axis, ‘1’ represents SPEA 2, ‘2’ represents NSGAII,’3’represents IBEA, ‘4’ represents PESAII and ‘5’ represents MOEA/D. y axis shows the metric value. NR Metric For each algorithm, the more the NR value, the better the algorithm’s performance: 0 0.05 0.1 0.15 0.2 0.25 1 2 3 4 5 0.05 0.1 0.15 0.2 0.25 1 2 3 4 5 64 4.2(c) NR metric value in ZDT 2 Here, in graph’s x axis, ‘1’ represents SPEA 2, ‘2’ represents NSGAII,’3’represents IBEA, ‘4’ represents PESAII and ‘5’ represents MOEA/D. y axis shows the metric value. Smetric For each algorithm, the more the S value, the better the algorithm’s performance: 4.2(d) Smetric value in ZDT 2 Here, in graph’s x axis, ‘1’ represents SPEA 2, ‘2’ represents NSGAII,’3’represents IBEA, ‘4’ represents PESAII and ‘5’ represents MOEA/D. y axis shows the metric value. MS Metric For each algorithm, the more the MS value, the better the algorithm’s performance: 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 1 2 3 4 5 0.76 0.78 0.8 0.82 0.84 0.86 0.88 0.9 0.92 1 2 3 4 5 65 4.2(e) MS metric value in ZDT 2 Here, in graph’s x axis, ‘1’ represents SPEA 2, ‘2’ represents NSGAII,’3’represents IBEA, ‘4’ represents PESAII and ‘5’ represents MOEA/D. y axis shows the metric value. Then, experiment results using ensemble performance metrics in ZDT 2 is given: Step 1 generates 50 fronts as the initial population of DoubleTournament Selection: in these 50 winner fronts, SPEA 2 wins 13 times, NSGAII wins 11 times, IBEA wins 8 times, PESAII wins 5 times and MOEA/D wins 13 times. In this step, metrics are totally chosen 50 times: GD is chosen 9 times, NR is 11 times, Spacing is 10 times, Smetric is 11 times and MS is 9 times. Step 2 is the first step of DoubleTournament Selection that 50 fronts are competed to generate 26 winners: in these 26 winner fronts, SPEA 2 wins 7 times, NSGAII wins 6 times, IBEA wins 3 times, PESAII wins 3 times and MOEA/D wins 7 times. In this step, metrics are totally chosen 62 times in two parts: The total 50 fronts are divided into 2 groups in first 25 times: GD is chosen 6 times, NR is 3 times, Spacing is 4 times, Smetric is 7 times and MS is 5 times. 26 winners are generated from both Winner group and Loser group in 37 times: GD is chosen 9 times, NR is 5 times, Spacing is 6 times, Smetric is 8 times and MS is 9 times. Step 3 is the second step of DoubleTournament Selection that 26 fronts are compared to generate 14 winners: in these 14 winner fronts, SPEA 2 wins 5 times, NSGAII wins 2 times, 0.88 0.89 0.9 0.91 0.92 0.93 0.94 0.95 0.96 0.97 1 2 3 4 5 66 IBEA wins 1 time, PESAII wins 2 times and MOEA/D wins 4 times. In this step, metrics are totally chosen 19 times: GD is chosen 7 times, NR is 4 times, Spacing is 5 times, Smetric is 2 times and MS is 1 time. In the third step (Step 4) of DoubleTournament Selection that 14 fronts are compared to generate 8 winners: in these 8 winner fronts, SPEA 2 wins 2 times, NSGAII wins 1 time, IBEA wins 1 time, PESAII wins 1 time and MOEA/D wins 3 times. In this step, metrics are totally chosen 10 times: GD is chosen 1 time, NR is 3 times, Spacing is 2 times, Smetric is 2 times and MS is 2 times. Step 5 is the fourth step of DoubleTournament Selection that 8 fronts are compared to generate 4 winners: in these 4 winner fronts, SPEA 2 wins 2 times, NSGAII wins 1 times, IBEA wins 0 times, PESAII wins 0 times and MOEA/D wins 1 times. In this step, metrics are totally chosen 6 times: GD is chosen 1 time, NR is 1 time, Spacing is 2 times, Smetric is 2 times and MS is 0 times. In the fifth step (Step 6) of DoubleTournament Selection that 4 fronts are compared to generate 2 winners: in these 2 winner fronts, SPEA 2 wins 1 time and MOEA/D wins 1 time. In this step, metrics are totally chosen 3 times: GD is chosen 0 time, NR is 0 time, Spacing is 1 time, Smetric is 1 time and MS is 1 time. In the final step (Step 7) of DoubleTournament Selection that 2 fronts are compared to generate 1 winner. The final winner is SPEA 2 and NR is chosen to compare. In Step 8, remove all the fronts from SPEA 2 in 50 fronts obtained in the first step, continue step 1 to step 7, NSGAII is the second best one and MOEA/D is the third one. After all the remaining fronts come from the same algorithm, we get the final rank value for ZDT 2: Rank 1: SPEA 2; Rank 2: NSGAII; Rank 3: MOEA/D; Rank 4: IBEA; Rank 5: PESAII. 67 4.1.3 ZDT 3 First, box plot for every performance metric measure is presented: GD Metric For each algorithm, the less the GD value, the better the algorithm’s performance: 4.3(a) GD metric value in ZDT 3 Here, in graph’s x axis, ‘1’ represents SPEA 2, ‘2’ represents NSGAII,’3’represents IBEA, ‘4’ represents PESAII and ‘5’ represents MOEA/D. y axis shows the metric value. Spacing Metric For each algorithm, the less the Spacing value, the better the algorithm’s performance: 0.04 0.06 0.08 0.1 0.12 0.14 0.16 0.18 0.2 0.22 1 2 3 4 5 0.1 0.15 0.2 0.25 1 2 3 4 5 68 4.3(b) Spacing metric value in ZDT 3 Here, in graph’s x axis, ‘1’ represents SPEA 2, ‘2’ represents NSGAII,’3’represents IBEA, ‘4’ represents PESAII and ‘5’ represents MOEA/D. y axis shows the metric value. NR Metric For each algorithm, the more the NR value, the better the algorithm’s performance: 4.3(c) NR metric value in ZDT 3 Here, in graph’s x axis, ‘1’ represents SPEA 2, ‘2’ represents NSGAII,’3’represents IBEA, ‘4’ represents PESAII and ‘5’ represents MOEA/D. y axis shows the metric value. Smetric For each algorithm, the more the S value, the better the algorithm’s performance: 0.05 0.1 0.15 0.2 0.25 0.3 0.35 1 2 3 4 5 0.87 0.88 0.89 0.9 0.91 0.92 0.93 0.94 0.95 0.96 1 2 3 4 5 69 4.3(d) Smetric value in ZDT 3 Here, in graph’s x axis, ‘1’ represents SPEA 2, ‘2’ represents NSGAII,’3’represents IBEA, ‘4’ represents PESAII and ‘5’ represents MOEA/D. y axis shows the metric value. MS Metric For each algorithm, the more the MS value, the better the algorithm’s performance: 4.3(e) MS metric value in ZDT 3 Here, in graph’s x axis, ‘1’ represents SPEA 2, ‘2’ represents NSGAII,’3’represents IBEA, ‘4’ represents PESAII and ‘5’ represents MOEA/D. y axis shows the metric value. Then, experiment results using ensemble performance metrics in ZDT 3 is given: Step 1 generates 50 fronts as the initial population of DoubleTournament Selection: in these 50 winner fronts, SPEA 2 wins 11 times, NSGAII wins 12 times, IBEA wins 9 times, PESAII wins 7 times and MOEA/D wins 11 times. In this step, metrics are totally chosen 50 times: GD is chosen 10 times, NR is 13 times, Spacing is 7 times, Smetric is 12 times and MS is 8 times. Step 2 is the first step of DoubleTournament Selection that 50 fronts are competed to generate 26 winners: in these 26 winner fronts, SPEA 2 wins 6 times, NSGAII wins 6 times, IBEA wins 5 times, PESAII wins 3 times and MOEA/D wins 6 times. In this step, metrics are 0.86 0.88 0.9 0.92 0.94 0.96 0.98 1 2 3 4 5 70 totally chosen 62 times in two parts: the total 50 fronts are divided into 2 groups in first 25 times: GD is chosen 4 times, NR is 5 times, Spacing is 4 times, Smetric is 5 times and MS is 7 times. 26 winners are generated from both Winner group and Loser group in 37 times: GD is chosen 7 times, NR is 6 times, Spacing is 7 times, Smetric is 10 times and MS is 7 times. Step 3 is the second step of DoubleTournament Selection that 26 fronts are compared to generate 14 winners: in these 14 winner fronts, SPEA 2 wins 2 times, NSGAII wins 4 times, IBEA wins 3 times, PESAII wins 2 times and MOEA/D wins 3 times. In this step, metrics are totally chosen 19 times: GD is chosen 4 times, NR is 5 times, Spacing is 3 times, Smetric is 4 times and MS is 3 times. In the third step (Step 4) of DoubleTournament Selection that 14 fronts are compared to generate 8 winners: in these 8 winner fronts, SPEA 2 wins 1 time, NSGAII wins 3 times, IBEA wins 1 time, PESAII wins 1 time and MOEA/D wins 2 times. In this step, metrics are totally chosen 10 times: GD is chosen 2 times, NR is 2 times, Spacing is 3 times, Smetric is 1 time and MS is 2 times. Step 5 is the fourth step of DoubleTournament Selection that 8 fronts are compared to generate 4 winners: in these 4 winner fronts, SPEA 2 wins 0 times, NSGAII wins 2 times, IBEA wins 0 times, PESAII wins 0 times and MOEA/D wins 2 times. In this step, metrics are totally chosen 6 times: GD is chosen 2 times, NR is 0 time, Spacing is 0 times, Smetric is 2 times and MS is 2 times. In the fifth step (Step 6) of DoubleTournament Selection that 4 fronts are compared to generate 2 winners: in these 2 winner fronts, NSGAII wins 2 times. In this step, metrics are totally chosen 3 times: GD is chosen 1 time, NR is 2 times, Spacing is 0 time, Smetric is 0 time and MS is 0 time. 71 In the final step (Step 7) of DoubleTournament Selection that 2 fronts are compared to generate 1 winner. The final winner is NSGAII and Smetric is chosen to compare. In the Step 8, remove all the fronts from NSGAII in 50 fronts obtained in the first step, continue step 1 to step 7, MOEA/D is the second best one and IBEA is the third one. After all the remaining fronts come from the same algorithm, we get the final rank value for ZDT 3: Rank 1: NSGAII; Rank 2: MOEA/D; Rank 3: IBEA; Rank 4: SPEA 2; Rank 5: PESAII. 4.1.4 ZDT 4 First, box plot for every performance metric measure is presented: GD Metric For each algorithm, the less the GD value, the better the algorithm’s performance: 4.4(a) GD metric value in ZDT 4 Here, in graph’s x axis, ‘1’ represents SPEA 2, ‘2’ represents NSGAII,’3’represents IBEA, ‘4’ represents PESAII and ‘5’ represents MOEA/D. y axis shows the metric value. Spacing Metric For each algorithm, the less the Spacing value, the better the algorithm’s performance: 0.05 0.1 0.15 0.2 0.25 0.3 0.35 0.4 1 2 3 4 5 72 4.4(b) Spacing metric value in ZDT 4 Here, in graph’s x axis, ‘1’ represents SPEA 2, ‘2’ represents NSGAII,’3’represents IBEA, ‘4’ represents PESAII and ‘5’ represents MOEA/D. y axis shows the metric value. NR Metric For each algorithm, the more the NR value, the better the algorithm’s performance: 4.4(c) NR metric value in ZDT 4 Here, in graph’s x axis, ‘1’ represents SPEA 2, ‘2’ represents NSGAII,’3’represents IBEA, ‘4’ represents PESAII and ‘5’ represents MOEA/D. y axis shows the metric value. Smetric 0.05 0.1 0.15 0.2 0.25 0.3 1 2 3 4 5 0.05 0.1 0.15 0.2 0.25 0.3 0.35 1 2 3 4 5 73 For each algorithm, the more the S value, the better the algorithm’s performance: 4.4(d) S metric value in ZDT 4 Here, in graph’s x axis, ‘1’ represents SPEA 2, ‘2’ represents NSGAII,’3’represents IBEA, ‘4’ represents PESAII and ‘5’ represents MOEA/D. y axis shows the metric value. MS Metric For each algorithm, the more the MS value, the better the algorithm’s performance: 4.4(e) MS metric value in ZDT 4 Here, in graph’s x axis, ‘1’ represents SPEA 2, ‘2’ represents NSGAII,’3’represents IBEA, ‘4’ represents PESAII and ‘5’ represents MOEA/D. y axis shows the metric value. 0.75 0.8 0.85 0.9 0.95 1 2 3 4 5 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 1 2 3 4 5 74 Then, experiment results using ensemble performance metrics in ZDT 4 is given: Step 1 generates 50 fronts as the initial population of DoubleTournament Selection: in these 50 winner fronts, SPEA 2 wins 0 times, NSGAII wins 15 times, IBEA wins 9 times, PESAII wins 9 times and MOEA/D wins 17 times. In this step, metrics are totally chosen 50 times: GD is chosen 9 times, NR is 15 times, Spacing is 7 times, Smetric is 12 times and MS is 7 times. Step 2 is the first step of DoubleTournament Selection that 50 fronts are competed to generate 26 winners: in these 26 winner fronts, SPEA 2 wins 0 times, NSGAII wins 9 times, IBEA wins 5 times, PESAII wins 5 times and MOEA/D wins 7 times. In this step, metrics are totally chosen 62 times in two parts: the total 50 fronts are divided into 2 groups in first 25 times: GD is chosen 6 times, NR is 4 times, Spacing is 4 times, Smetric is 5 times and MS is 6 times. 26 winners are generated from both Winner group and Loser group in 37 times: GD is chosen 5 times, NR is 7 times, Spacing is 9 times, Smetric is 5 times and MS is 11 times. Step 3 is the second step of DoubleTournament Selection that 26 fronts are compared to generate 14 winners: in these 14 winner fronts, SPEA 2 wins 0 times, NSGAII wins 5 times, IBEA wins 3 times, PESAII wins 2 times and MOEA/D wins 4 times In this step, metrics are totally chosen 19 times: GD is chosen 5 times, NR is 6 times, Spacing is 3 times, Smetric is 4 times and MS is 1 time. In the third step (Step 4) of DoubleTournament Selection that 14 fronts are compared to generate 8 winners: in these 8 winner fronts, SPEA 2 wins 0 time, NSGAII wins 3 times, IBEA wins 1 time, PESAII wins 1 time and MOEA/D wins 3 times. In this step, metrics are totally chosen 10 times: GD is chosen 3 times, NR is 1 time, Spacing is 2 times, Smetric is 2 times and MS is 2 times. Step 5 is the fourth step of DoubleTournament Selection that 8 fronts are compared to generate 4 winners: in these 4 winner fronts, SPEA 2 wins 0 times, NSGAII wins 2 times, IBEA 75 wins 1 time, PESAII wins 0 times and MOEA/D wins 1 time. In this step, metrics are totally chosen 6 times: GD is chosen 1 time, NR is 0 time, Spacing is 1 time, Smetric is 2 times and MS is 2 times. In the fifth step (Step 6) of DoubleTournament Selection that 4 fronts are compared to generate 2 winners: in these 2 winner fronts, NSGAII wins 1 time and MOEA/D wins 1 time. In this step, metrics are totally chosen 3 times: GD is chosen 1 time, NR is 0 times, Spacing is 1 time, Smetric is 0 time and MS is 1 time. In the final step (Step 7) of DoubleTournament Selection that 2 fronts are compared to generate 1 winner. The final winner is MOEA/D and GD is chosen to compare. This result is the same as [14]. In the Step 8, remove all the fronts from MOEA/D in 50 fronts obtained in the first step, continue step 1 to step 7, NSGAII is the second best one and PESAII is the third one. After all the remaining fronts come from the same algorithm, we get the final rank value for ZDT 4: Rank 1: MOEA/D; Rank 2: NSGAII; Rank 3: PESAII; Rank 4: IBEA; Rank 5: SPEA 2. 4.1.5 ZDT 6 First, box plot for every performance metric measure is presented: GD Metric For each algorithm, the less the GD value, the better the algorithm’s performance: 76 4.5(a) GD metric value in ZDT 6 Here, in graph’s x axis, ‘1’ represents SPEA 2, ‘2’ represents NSGAII,’3’represents IBEA, ‘4’ represents PESAII and ‘5’ represents MOEA/D. y axis shows the metric value. Spacing Metric For each algorithm, the less the Spacing value, the better the algorithm’s performance: 4.5(b) Spacing metric value in ZDT 6 Here, in graph’s x axis, ‘1’ represents SPEA 2, ‘2’ represents NSGAII,’3’represents IBEA, ‘4’ represents PESAII and ‘5’ represents MOEA/D. y axis shows the metric value. NR Metric For each algorithm, the more the NR value, the better the algorithm’s performance: 0.05 0.1 0.15 1 2 3 4 5 0.06 0.07 0.08 0.09 0.1 0.11 0.12 0.13 0.14 0.15 1 2 3 4 5 77 4.5(c) NR metric value in ZDT 6 Here, in graph’s x axis, ‘1’ represents SPEA 2, ‘2’ represents NSGAII,’3’represents IBEA, ‘4’ represents PESAII and ‘5’ represents MOEA/D. y axis shows the metric value. Smetric For each algorithm, the more the S value, the better the algorithm’s performance: 4.5(d) S metric value in ZDT 6 Here, in graph’s x axis, ‘1’ represents SPEA 2, ‘2’ represents NSGAII,’3’represents IBEA, ‘4’ represents PESAII and ‘5’ represents MOEA/D. y axis shows the metric value. MS Metric 0.1 0.15 0.2 0.25 0.3 1 2 3 4 5 0.86 0.88 0.9 0.92 0.94 0.96 1 2 3 4 5 78 For each algorithm, the more the MS value, the better the algorithm’s performance: 4.5(e) MS metric value in ZDT 6 Here, in graph’s x axis, ‘1’ represents SPEA 2, ‘2’ represents NSGAII,’3’represents IBEA, ‘4’ represents PESAII and ‘5’ represents MOEA/D. y axis shows the metric value. Then, experiment results using ensemble performance metrics in ZDT 6 is given: Step 1 generates 50 fronts as the initial population of DoubleTournament Selection: in these 50 winner fronts, SPEA 2 wins 8 times, NSGAII wins 11 times, IBEA wins 13 times, PESAII wins 6 times and MOEA/D wins 12 times. In this step, metrics are totally chosen 50 times: GD is chosen 11 times, NR is 12 times, Spacing is 9 times, Smetric is 12 times and MS is 6 times. Step 2 is the first step of DoubleTournament Selection that 50 fronts are competed to generate 26 winners: in these 26 winner fronts, SPEA 2 wins 5 times, NSGAII wins 5 times, IBEA wins 7 times, PESAII wins 2 times and MOEA/D wins 7 times. In this step, metrics are totally chosen 62 times in two parts: the total 50 fronts are divided into 2 groups in first 25 times: GD is chosen 5 times, NR is 7 times, Spacing is 4 times, Smetric is 4 times and MS is 5 times. 26 winners are generated from both Winner group and Loser group in 37 times: GD is chosen 6 times, NR is 5 times, Spacing is 8 times, Smetric is 9 times and MS is 9 times. 0.87 0.88 0.89 0.9 0.91 0.92 0.93 0.94 0.95 0.96 1 2 3 4 5 79 Step 3 is the second step of DoubleTournament Selection that 26 fronts are compared to generate 14 winners: in these 14 winner fronts, SPEA 2 wins 2 times, NSGAII wins 3 times, IBEA wins 4 times, PESAII wins 1 time and MOEA/D wins 4 times. In this step, metrics are totally chosen 19 times: GD is chosen 6 times, NR is 5 times, Spacing is 2 times, Smetric is 4 times and MS is 2 times. In the third step (Step 4) of DoubleTournament Selection that 14 fronts are compared to generate 8 winners: in these 8 winner fronts, SPEA 2 wins 0 time, NSGAII wins 2 times, IBEA wins 3 times, PESAII wins 0 time and MOEA/D wins 3 times. In this step, metrics are totally chosen 10 times: GD is chosen 2 times, NR is 1 time, Spacing is 1 time, Smetric is 2 times and MS is 4 times. Step 5 is the fourth step of DoubleTournament Selection that 8 fronts are compared to generate 4 winners: in these 4 winner fronts, SPEA 2 wins 0 times, NSGAII wins 0 times, IBEA wins 2 times, PESAII wins 0 times and MOEA/D wins 2 times. In this step, metrics are totally chosen 6 times: GD is chosen 3 times, NR is 0 time, Spacing is 1 time, Smetric is 1 time and MS is 1 time. In the fifth step (Step 6) of DoubleTournament Selection that 4 fronts are compared to generate 2 winners: in these 2 winner fronts, IBEA wins 1 time and MOEA/D wins 1 time. In this step, metrics are totally chosen 3 times: GD is chosen 0 time, NR is 0 times, Spacing is 0 time, Smetric is 2 time and MS is 1 time. In the final step (Step 7) of DoubleTournament Selection that 2 fronts are compared to generate 1 winner. The final winner is MOEA/D and Spacing is chosen to compare. In the Step 8, remove all the fronts from MOEA/D in 50 fronts obtained in the first step, continue step 1 to step 7, IBEA is the second best one and NSGAII is the third one. After all the remaining fronts come from the same algorithm, we get the final rank value for ZDT 6: 80 Rank 1: MOEA/D; Rank 2: IBEA; Rank 3: NSGAII; Rank 4: SPEA 2; Rank 5: PESAII. 4.1.6 DTLZ 2 First, box plot for every performance metric measure is presented: GD Metric For each algorithm, the less the GD value, the better the algorithm’s performance: 4.6(a) GD metric value in DTLZ 2 Here, in graph’s x axis, ‘1’ represents SPEA 2, ‘2’ represents NSGAII,’3’represents IBEA, ‘4’ represents PESAII and ‘5’ represents MOEA/D. y axis shows the metric value. Spacing Metric For each algorithm, the less the Spacing value, the better the algorithm’s performance: 0.04 0.06 0.08 0.1 0.12 0.14 0.16 0.18 1 2 3 4 5 81 4.6(b) Spacing metric value in DTLZ 2 Here, in graph’s x axis, ‘1’ represents SPEA 2, ‘2’ represents NSGAII,’3’represents IBEA, ‘4’ represents PESAII and ‘5’ represents MOEA/D. y axis shows the metric value. NR Metric For each algorithm, the more the NR value, the better the algorithm’s performance: 4.6(c) NR metric value in DTLZ 2 Here, in graph’s x axis, ‘1’ represents SPEA 2, ‘2’ represents NSGAII,’3’represents IBEA, ‘4’ represents PESAII and ‘5’ represents MOEA/D. y axis shows the metric value. Smetric 0.07 0.08 0.09 0.1 0.11 0.12 0.13 0.14 0.15 0.16 0.17 1 2 3 4 5 0.05 0.1 0.15 0.2 0.25 0.3 0.35 1 2 3 4 5 82 For each algorithm, the more the S value, the better the algorithm’s performance: 4.6(d) Smetric value in DTLZ 2 Here, in graph’s x axis, ‘1’ represents SPEA 2, ‘2’ represents NSGAII,’3’represents IBEA, ‘4’ represents PESAII and ‘5’ represents MOEA/D. y axis shows the metric value. MS Metric For each algorithm, the more the MS value, the better the algorithm’s performance: 4.6(e) MS metric value in DTLZ 2 Here, in graph’s x axis, ‘1’ represents SPEA 2, ‘2’ represents NSGAII,’3’represents IBEA, ‘4’ represents PESAII and ‘5’ represents MOEA/D. y axis shows the metric value. 0.86 0.88 0.9 0.92 0.94 0.96 1 2 3 4 5 0.88 0.9 0.92 0.94 0.96 0.98 1 2 3 4 5 83 Then, experiment results using ensemble performance metrics in ZDT 6 is given: Step 1 generates 50 fronts as the initial population of DoubleTournament Selection: in these 50 winner fronts, SPEA 2 wins 11 times, NSGAII wins 8 times, IBEA wins 13 times, PESAII wins 6 times and MOEA/D wins 12 times. In this step, metrics are totally chosen 50 times: GD is chosen 7 times, NR is 15 times, Spacing is 9 times, Smetric is 11 times and MS is 8 times. Step 2 is the first step of DoubleTournament Selection that 50 fronts are competed to generate 26 winners: in these 26 winner fronts, SPEA 2 wins 5 times, NSGAII wins 5 times, IBEA wins 7 times, PESAII wins 2 times and MOEA/D wins 7 times. In this step, metrics are totally chosen 62 times in two parts: the total 50 fronts are divided into 2 groups in first 25 times: GD is chosen 6 times, NR is 4 times, Spacing is 7 times, Smetric is 3 times and MS is 5 times. 26 winners are generated from both Winner group and Loser group in 37 times: GD is chosen 6 times, NR is 6 times, Spacing is 7 times, Smetric is 10 times and MS is 8 times. Step 3 is the second step of DoubleTournament Selection that 26 fronts are compared to generate 14 winners: in these 14 winner fronts, SPEA 2 wins 2 times, NSGAII wins 0 times, IBEA wins 6 times, PESAII wins 1 time and MOEA/D wins 5 times. In this step, metrics are totally chosen 19 times: GD is chosen 2 times, NR is 2 times, Spacing is 5 times, Smetric is 4 times and MS is 6 times. In the third step (Step 4) of DoubleTournament Selection that 14 fronts are compared to generate 8 winners: in these 8 winner fronts, SPEA 2 wins 1 time, NSGAII wins 1 time, IBEA wins 3 times, PESAII wins 0 time and MOEA/D wins 3 times. In this step, metrics are totally chosen 10 times: GD is chosen 3 times, NR is 2 times, Spacing is 1 time, Smetric is 2 times and MS is 2 times. Step 5 is the fourth step of DoubleTournament Selection that 8 fronts are compared to generate 4 winners: in these 4 winner fronts, SPEA 2 wins 0 times, NSGAII wins 0 times, IBEA wins 2 time, PESAII wins 0 times and MOEA/D wins 2 times. In this step, metrics are totally 84 chosen 6 times: GD is chosen 2 times, NR is 1 time, Spacing is 1 time, Smetric is 1 time and MS is 1 time. In the fifth step (Step 6) of DoubleTournament Selection that 4 fronts are compared to generate 2 winners: in these 2 winner fronts, IBEA wins 1 time and MOEA/D wins 1 time. In this step, metrics are totally chosen 3 times: GD is chosen 1 time, NR is 0 times, Spacing is 1 time, Smetric is 0 time and MS is 1 time. In the final step (Step 7) of DoubleTournament Selection that 2 fronts are compared to generate 1 winner. The final winner is IBEA and MS is chosen to compare. In the Step 8, remove all the fronts from IBEA in 50 fronts obtained in the first step, continue step 1 to step 7, MOEA/D is the second best one and SPEA 2 is the third one. After all the remaining fronts come from the same algorithm, we get the final rank value for DTLZ 2: Rank 1: IBEA; Rank 2: MOEA/D; Rank 3: SPEA 2; Rank 4: NSGAII; Rank 5: PESAII. 4.2 ANALYSIS OF EXPERIMENT RESULTS 4.2.1 Ensemble Performance Metrics give the same rank values to exist papers In ZDT3, the final rank result is: Rank 1: NSGAII; Rank 2: MOEA/D; Rank 3: IBEA; Rank 4: SPEA 2; Rank 5: PESAII. The experiment result in [14] has also suggested that MOEA/D generate a worse result than NSGAII. In ZDT6, the final rank result is: Rank 1: MOEA/D; Rank 2: IBEA; Rank 3: NSGAII; Rank 4: SPEA 2; Rank 5: PESAII. [12] shows IBEA performs better than NSGAII and SPEA 2 in ZDT 6. [14] gives the same result that MOEA/D is better than NSGAII in ZDT 6. In DTLZ 2, the final rank result is: Rank 1: IBEA; Rank 2: MOEA/D; Rank 3: SPEA 2; Rank 4: NSGAII; Rank 5: PESAII. This result is nearly the same as previous experiment: [10] 85 has suggested that SPEA 2 seems to have advantages over NSGAII in higher dimensional objective space. In [12], IBEA is also better than SPEA 2 and NSGAII. The experiment result in [14] has also identified that MOEA/D generate a better result than NSGAII. 4.2.2 Summary of EAs to Solve Different Characteristics of Test Functions SPEA 2 SPEA 2 is the final winner in problem ZDT 1 and ZDT 2. Although ZDT 1 has a convex Paretooptimal front while ZDT 2 has the nonconvex counterpart to ZDT1, Both ZDT1 and ZDT2 have some common characteristics: they do not have local Paretooptimal fronts and their global Paretooptimal fronts are continuous. From the above reason, we can state that, if the test problem has continues global Paretooptimal fronts and do not have local Paretooptimal fronts, SPEA 2 will perform well in this problem. NSGAII NSGAII has the best performance in ZDT 3, which represents the discreteness feature and has a Paretooptimal front consisting of several noncontiguous convex parts. Therefore, if there is a test problem with discrete Paretooptimal front, we can propose that NSGAII is the best algorithm to solve this problem. MOEA/D MOEA/D wins all other algorithms in both ZDT4 and ZDT6. ZDT4 is difficult to solve because it has many local Paretooptimal fronts, a large number of local Paretooptimal fronts make the global Pareto front is not easy to find and EAs need to exhibit their ability to deal with multimodality. ZDT6’s Paretooptimal solutions are nonuniformly distributed along the global Pareto front. The front is biased for solutions which have a large f1(x) value. Therefore, MOEA/D will exhibit its good performance when encounters the test problem 86 which has lots of local Paretooptimal fronts or Paretooptimal solutions is not uniformly distributed its global Pareto front. IBEA IBEA wins at all in DTLZ 2, which is the only test problem chosen in this experiment has more than two objectives. We may not absolutely say that IBEA is best for solve problems with highdimension objectives. But we can make a comparatively conclusion that IBEA can perform better than others in some test problems with highdimension objectives. In summary, from the above discussion, we can see more clearly that every algorithm can only be superior to another algorithm over some set of test problems, and then it must be inferior in other problems with different characteristics. This is also expected by No Free Lunch Theory. 4.3 WHY USE DOUBLEELIMINATION METHOD TO ENSEMBLE First, we go through experiments in all benchmark functions considering the performance metrics’ values of every algorithm in this benchmark function. In ZDT1, SPEA 2 is the final winner and it wins under all four metrics but is inferior to NSGAII in Smetric. In ZDT2, SPEA 2 is the final winner and it wins under all four metrics but it is a little bit worse than NSGAII in Spacing metric. In ZDT3, NSGAII is the final winner and it wins under all four metrics but is inferior to MOEA/D in Smetric. In ZDT4, MOEA/D is the final winner and it wins under all four metrics but it is a little bit worse than NSGAII in NR metric. In ZDT6, MOEA/D is the final winner but is inferior to IBEA in MS metric and a little bit worse than NSGAII in Spacing metric. In DTLZ 2, IBEA is the final winner and it wins under all four metrics but is inferior to MOEA/D in Spacing metric. From above results, to be a final winner does not mean win others in all performance metrics. In ZDT1, if we use Smetric to compare SPEA 2 and NSGAII in SingleElimination, SPEA 2 87 will be lost and we cannot find the best algorithm for this problem. However, if that condition happens in DoubleElimination, SPEA 2 also has another opportunity to win again. Therefore, DoubleElimination can provide one more chance for every competitor, this helps to find the best one winner. 88 CHAPTER 5 CONCLUSION . There are five types of unary metrics: 1) Metrics assessing the number of Pareto optimal solutions in the set: Pareto Dominance Indicator (NR), Overall Nondominated Vector Generation and Ratio (ONVG), Ratio of Nondominated Individuals (RNI) and Error Ratio (ER). 2) Metrics measuring the closeness of the solution to the theoretical Pareto front: Generational Distance (GD) and Maximum Pareto Front Error (MPFE). 3) Metrics focusing on distribution of the solutions: Uniform Distribution (UD), Spacing and Number of Distinct Choices (NDCu). 4) Metrics concerning spread of the solutions: Maximum Spread (MS). 5) Metrics considering both closeness and diversity: Hypervolume Indicator (or Smetric). There are two types of binary metrics: 1) binary performance metrics based on unary quality indicator: ε indicator Iε , enclosing hypercube Indicator and coverage difference metrics (Dmetric). The second type is direct comparison binary metrics: C metrics and R metrics. An ensemble method is introduced to compare EAs by combining a large number of single metrics using modified Double Tournament Selection. Double elimination design give every individual two chances to competition allows characteristic poor performance of a quality algorithm under the special environment still to be able to win at all. Therefore, this ensemble mechanism can maximum protects the qualified individual from being lost by some stochastic factors in a comparison time. This ensures the final result is the really best one and the whole ensemble process is effective and precise. Ensemble method can overcome the lost information problem by the single metric which on 89 ly provides some specific but limited information and is only used effectively in some specified conditions. The Comprehensive comparison of the proposed algorithms on benchmark test functions under ensemble performance metrics show that: SPEA 2 performs well in the problem has continues global Paretooptimal fronts and do not have local Paretooptimal fronts. NSGAII is the best algorithm to solve this problem with discrete Paretooptimal front. MOEA/D will exhibit its good performance when encounters the test problem which has lots of local Paretooptimal fronts or Paretooptimal solutions is not uniformly distributed its global Pareto front. IBEA can perform better than others in some test problems with highdimension objectives. Furthermore, we are benefit from ensemble method that it is not necessary to spend much time to choose a suitable performance metric for a specific test problem. We do not need to try every metric to find which on
Click tabs to swap between content that is broken into logical sections.
Rating  
Title  Performance Metrics Ensemble for Multiobjective Evolutionary Algorithms 
Date  20110501 
Author  He, Zhenan 
Keywords  Evolutionary Algorithms, Performance Metrics Ensemble 
Department  Electrical Engineering 
Document Type  
Full Text Type  Open Access 
Abstract  There are five types of unary performance metrics and two types of binary performance metrics. However, no single metric can faithfully measure MOEA performance. Moreover, every metric has its unique character; no metrics can substitute others completely. Ensemble method is introduced to compare EAs by combining a large number of single metrics using modified Double Tournament Selection. Double Tournament Selection can maximum protects the qualified individual from being lost by some stochastic factors in a comparison time. This ensures the final result is the really best one and the whole ensemble process is effective and precise. Therefore, performance metrics ensemble can overcome the lost information problem by the single metric which only provides some specific but limited information. Furthermore, ensemble method avoids the choosing process which is a heavy computational process and can be directly used to assessing EAs. Finally, from the experiment results by using performance metrics ensemble, Each MOEA's characteristic is summarized. 
Note  Thesis 
Rights  © Oklahoma Agricultural and Mechanical Board of Regents 
Transcript  PERFORMANCE METRICS ENSEMBLE FOR MULTIOBJECTIVE EVOLUTIONARY ALGORITHMS By ZHENAN HE Bachelor of Engineering in Automation University of Science and Technology Beijing Beijing, China 2008 Submitted to the Faculty of the Graduate College of the Oklahoma State University in partial fulfillment of the requirements for the Degree of MASTER OF SCIENCE May, 2011 ii PERFORMANCE METRICS ENSEMBLE FOR MULTIOBJECTIVE EVOLUTIONARY ALGORITHMS Thesis Approved: Dr. Gary G. Yen Thesis Adviser Dr. Qi Cheng Dr. Weihua Sheng Dr. Mark E. Payton Dean of the Graduate College iii ACKNOWLEDGMENTS At the outset, I would like to thank my advisor Dr. Gary G. Yen, for his patience and guidance. I enjoy very much working under him and it was an excellent learning experience for me. I appreciate him for teaching me how to think about a problem, how to generate an idea to solve the problem and how to validate my idea through the experiment. I would also like to thank him for helping me out with great patience in writing this thesis, for guiding me and giving me tips on structure, grammar, sentence and words. These lessons will benefit me all my life. I would like to think my committee members, Dr. Qi Cheng and Dr. Weihua Sheng for their timely advice, discussions and feedback. Dr. Cheng’s Stochastic System class made me understand the stochastic concept in a depth way, which helps me much in my research work. Many thanks to my lab mates at the Intelligent Systems and Control Laboratory: Chatkew Jariyatantiwait, Bin Ha and Weiwei Zhang gave me much useful suggestions. I often get inspiration by the group study with them. In summary, I would like to thank my lab mates for providing an intellectually stimulating experience via discussions and presentations throughout my tenure. Then I strongly like to thank my friends Guanglei An and Xiaowei Yang. They often give me many suggestions in my study and life. A note of thanks for my good friends Suling Duan, Bo Xu, Huanyu Zhao, Lianfan Su and Rui Yang along with all my above mentioned friends for a great spare time and for their support and understanding. iv I am forever grateful to my parents for their love, financial and moral support and encouragement. Lastly, but definitely not the least, I dedicate this work in loving memory my grandfather, who was and will continue to be a great source of inspiration to me. I cherish the memory of him forever. v TABLE OF CONTENTS Chapter Page 1 INTRODUCTION 1 1.1 PROBLEM STATEMENT ................................................................................1 1.2 MOTIVATION ..................................................................................................3 1.3 ORGANIZATION OF THESIS ........................................................................4 2 REVIEW OF LITERATURE 5 2.1 MULTIOBJCTIVE OPTIMIZATION PROBLEMS ........................................5 2.1.1 Why Multiobjective Optimization Problems are Considered ...................5 2.1.2 MOP Definition ........................................................................................6 2.1.3 Concept of Domination .............................................................................7 2.1.4 ZDT Problems ...........................................................................................8 2.1.5 Test Problems DTLZ ..............................................................................14 2.2 MULTIOBJCTIVE EVOLUTIONARY ALGORITHMS (MOEAs) .............18 2.2.1 An Introduction to MOEAs ....................................................................18 2.2.2 MOEAs Definition ..................................................................................20 2.2.3 The Main Procedure of MOEAs .............................................................21 2.2.4 Control Parameters of Genetic Algorithms.............................................22 2.2.5 Some Examples of MOEAs ....................................................................23 vi 2.3 PERFORMANCE METRICS ..........................................................................29 2.3.1 Outperformance Relations and Quantitative Comparison Methods .......30 2.3.2 Compatibility and Completeness ............................................................32 2.3.3 Unary Performance Metrics ....................................................................34 2.3.4 Binary Performance Metrics ...................................................................45 3 METHODOLOGY 49 3.1 MOTIVATION ................................................................................................49 3.2 OVERVIEW OF PERFORMANCE METRICS ENSEMBLE .......................50 3.3 ENSEMBLE WITH DOUBLETOURNAMENT SELECTION ....................51 3.3.1 DoubleTournament Selection ................................................................51 3.3.2 Ensemble Method with DoubleTournament Selection ..........................53 4 EXPERIMENTAL FINDINGS 58 4.1 EXPERIEMENT RESULTS ...........................................................................58 4.1.1 ZDT1 .......................................................................................................58 4.1.2 ZDT2 .......................................................................................................62 4.1.3 ZDT3 .......................................................................................................67 4.1.4 ZDT4 .......................................................................................................71 4.1.5 ZDT6 .......................................................................................................75 4.1.6 DTLZ2 ....................................................................................................80 4.2 ANALYSIS OF EXPERIEMENT RESULTS.................................................84 4.2.1 Ensemble Metrics Give the Same Rank Values to Exist Papers ............84 4.2.2 Summary of EAs in Different Characteristics of Test Functions ...........85 vii 4.3 WHY USE DOUBLEELIMINATION METHOD TO ENSEMBLE ............86 5 CONCLUSION 88 REFERENCES 90 viii LIST OF TABLES Table Page 2.1 The main structure of SPEA 2 ...........................................................................24 2.2 The main structure of NSGAII .........................................................................27 2.3 The main structure of IBEA ...............................................................................28 2.4 The main structure of MOEA/D ........................................................................29 3.1 The whole process of ensemble method .............................................................51 ix LIST OF FIGURES 2.1 The Relation between Decision Space and Objective Space ...................................8 2.2 Paretooptimal front of ZDT1 ..................................................................................9 2.3 Paretooptimal front of ZDT2 ................................................................................10 2.4 Paretooptimal front of ZDT3 ................................................................................11 2.5 Paretooptimal front of ZDT4 ................................................................................12 2.6 Paretooptimal front of ZDT6 ................................................................................14 2.7 The Process of MOEAs to solve MOPs .................................................................19 2.8 Basic Structure of MOEAs ....................................................................................20 3.1 The proposed framework .......................................................................................50 3.2 The whole process of doubleelimination ..............................................................55 4.1 Box Plot for Performance Metric Measure in ZDT 1 ............................................58 4.2 Box Plot for Performance Metric Measure in ZDT 2 ............................................63 4.3 Box Plot for Performance Metric Measure in ZDT 3 ............................................67 4.4 Box Plot for Performance Metric Measure in ZDT 4 ............................................71 4.5 Box Plot for Performance Metric Measure in ZDT 6 ............................................76 4.6 Box Plot for Performance Metric Measure in DTLZ 2 ..........................................80 1 CHAPTER ONE INTRODUCTION 1.1 PROBLEM STATEMENT Evolutionary algorithms (EAs) have become established as the approach for exploring the Paretooptimal front in multiobjective optimization problems. EAs usually do not guarantee to identify optimal tradeoffs but attempt to find a good approximation. From No Free Lunch theorem [1], any algorithm elevated performance over one class of problems is exactly paid for in loss over another class. Although various multiobjective EAs (MOEAs) are available today, certainly we are interested in developing a most effective algorithm to search for Pareto solutions for a given problem [2]. Therefore, comparative studies are always conducted. They aim at revealing advantages and weaknesses of the underlying methods and at determining the best performance pertained to specific problem characteristics. The numerous applications of MOEAs boost the significance of performance comparison issues. However, in absence of any established comparison criteria, none of the different sets of estimates based on various metrics for the Paretooptimal solutions generated can be argued to be better than the others. Zitzler [2] proposed three optimization goals to be measured: the distance of the resulting nondominated set to the Paretooptimal front should be minimized, a good (in most cases uniform) distribution of the solutions found in objective space is desirable and the extent of the obtained nondominated front should be maximized. In the literature, there are many unary performance metrics used to compare MOEAs. These metrics can be broadly divided into five 2 categories according to the optimization goals. Each category mainly evaluates the quality of a Paretooptimal set in one aspect only. First, metrics assessing the number of Pareto optimal solutions in the set: Pareto Dominance Indicator (NR) [3] measures the ratio of nondominated solutions contributed by a particular solution set to the nondominated solutions provided by all solution sets; Overall Nondominated Vector Generation and Ratio (ONVG) [4] counts the number of distinct nondominated points generated; Ratio of Nondominated Individuals (RNI) [5] gives the proportion of the useful solutions known as the Paretofront in a given population size; and Error Ratio (ER) [4] checks the proportion of non true Pareto points in the approximation front. Within the second category, metrics measuring the closeness of the solution to the theoretical Pareto front: Generational Distance (GD) [4] measures how far the evolved solution set is from the true Pareto front; and Maximum Pareto Front Error (MPFE) [4] focused on the largest distance between the point in the theoretical Pareto front and the point in the approximation front. Third, metrics focusing on distribution of the solutions: Uniform Distribution (UD) [5] measures the distribution of an approximation front under a predefined parameter σs hare; Spacing [6] measures how evenly the evolved solutions distribute itself; and Number of Distinct Choices (NDCu) [7] identifies solutions that are sufficiently distinct for a special value u. Fourth, metrics concerning spread of the solutions: Maximum Spread (MS) [3] measures how well the true Pareto front is covered by the approximation set. In the last category, metrics considering both closeness and diversity at the same time: Hypervolume Indicator (or Smetric) [11] calculates the volume covered by the approximation front. Furthermore, there are some binary performance metrics used to compare a pair of algorithms. The first type of binary performance metrics based on unary quality indicator. It includes ε indicator. Iε [10] defines a ε dominate relation between algorithms, enclosing hypercube Indicator [10] and coverage difference metrics (Dmetric) [11]. The second type is direct comparison binary metrics: C metrics [9] and R metrics [5]. C metrics [9] consider the 3 dominate relations between algorithms; R metrics [5] use the probability that one algorithm is better than the other over a series of functions. However, the problem arises that no single metric alone can faithfully measure MOEA performance. Every single metric can provide some specific, but incomplete quantification of performance and can only be used effectively under some specified conditions. For example, UD does a poor job when the Pareto front is discontinued, while Hypervolume can be misleading if the Pareto optimal front is nonconvex [4]. This implies one metric cannot entirely evaluate EAs in all conditions. Every metric focuses on some special characteristics while neglects information in others. Also, every metric has its unique characteristic; no metrics can substitute others completely. Therefore, a single metrics cannot provide a comprehensive measure for MOEAs. Moreover, from [11], a fixed number of indicators are not sufficient to evaluate MOEAs because reducing objective space must losing information. Different metrics perform differently in different test problems. For a given MOEA, one metric may show well in one test problem, however, given other test problems, it may mislead the conclusion should the measures show poorly. For a specific test problem, we cannot ascertain which metric should be applied in order to faithfully quantify the performance of MOEAs. We need to exploit every metric to find which one is the best. Apparently, this introduces a heavy computational process. 1.2 MOTIVATION To overcome these disadvantages and arrive at a faithful evaluation of MOEAs, performance metrics ensemble is proposed in this research work. Ensemble methods use multiple metrics to obtain a fair performance than what could be obtained from any of single performance metric alone. Ensemble metrics not only can give the comprehensive comparison between different algorithms, but avoid the choosing process and can be directly used to assessing MOEAs. 4 There exists no publication in the literature, to our best knowledge, regarding performance metrics ensemble. MOEAs are only evaluated and compared in a single metric at a time. In this paper, we propose doubletournament selection operator to compare many approximation fronts from different MOEAs. Double elimination design allows characteristic poor performance of a quality algorithm under the special environment still to be able to win it all. In every competition, one metric is chosen randomly to compare. After the whole process, every metric could be selected multiple times and a final winning algorithm is to be identified. This final winner has been compared under all the metrics considered so that we can make a fair conclusion. 1.3 ORGANIZATION OF THESIS Chapter Two provides the consolidated literature review for this thesis. It presents the essential background with reference to knowledge in the areas of Multiobjective Optimization Problem, Multiobjective Evolutionary Algorithms and Performance Metrics. Chapter Three describes the proposed approach in detail. A novel ensemble method using modified DoubleTournament selection operator is introduced. In Chapter Four, we elaborate on the experiment results for ZDT (16) and DTLZ 2 problems. Finally, conclusion is drawn in Chapter Five along with pertinent observations. 5 CHAPTER TWO REVIEW OF LITERATURE This chapter presents the essential background knowledge on Multiobjective Optimization Problem (MOP), Multiobjective Evolutionary Algorithm (MOEA) and Performance Metrics. 2.1 MULTIOBJECTIVE OPTIMIZATION PROBLEMS (MOP) First, the omnipresent of MOP is discussed. Then, definition of MOP is given. After that, concept of domination is introduced to identify the optimal solution. In addition, the characteristic of reference sets of MOP is summarized. Finally, two series of test problems are presented, which are widely applied to evaluate the performance of multiobjective evolutionary algorithms. 2.1.1 Why Multiobjective Optimization Problems? In real life environments we always strive to optimize a number of parameters in any design and these parameters are usually highly correlated. Hence, some tradeoff between the criteria is needed to ensure a satisfactory design. For example: in bridge construction, a good design is characterized by low total mass and high stiffness; aircraft design requires simultaneous optimization of fuel efficiency, payload, and weight; a good sunroof design in a sport car could aim at minimizing the noise the driver hears and maximizing the ventilation; and the business portfolio management attempts to simultaneously minimize the risk and maximize the fiscal return. In these realworld optimization problems, the objectives often conflict across a highdimensional problem space and may also require extensive computational resources. 6 Neither the problem nor algorithm domains considered within this research is straightforward. Multiobjective Optimization Problems (MOPs) present a possibly uncountable set of solutions that produce vectors whose components represent tradeoffs in objective space. Therefore, for an MOP, a number of tradeoff solutions are optimal. Without further information, such optimal solutions are equally important. 2.1.2 MOP Definition [39] In general, an MOP involves k objectives, mconstraints and ndecision variables: k objectives: Optimizes ( ) ( ( ) ( )) 1 , , k f x = f x K f x (21 A) mequality and inequality constraints: Subject to ( ) 0, 1, , i g x ≤ i = K m (21 B) n decision variables: ( ) 1, , T n x = x K x (21 C) MOP deals with two search spaces: a decision space ( ) plus an objective space ( Λ ). Mapping takes place from an n dimensional decision space to an m dimensional objective space. The MOP's objective function, f : →Λ , maps decision variables ( ) 1, , n x = x K x in decision space to vectors ( ) ( ( ) ( )) 1 , , k f x = f x K f x in objective space. Proximity of two solutions in one space does not imply proximity in the other space and search is performed in the decision space. As stated in [2], the goal of MOPs consists of multiple objectives: the distance of the resulting nondominated set to the Paretooptimal front should be minimized; a good (in most cases uniform) distribution of the solutions found is desirable; and the extent of the obtained nondominated front should be maximized, i.e., for each objective, a wide range of values should be covered by the nondominated solutions. Apparently, while these candidate solutions are 7 progressing towards Paretooptimal front, the convergence process will adversely impact the spread of the solution found. 2.1.3 Concept of Domination [39] Most multiobjective optimization algorithms use the concept of domination. In these algorithms, two solutions are compared on the basis of whether one dominates the other solution or not. Pareto Optimality: A solution x∈ is said to be Pareto optimal with respect to if and only if there is no x' ∈ for which ( ' ) ( ( ' ) ( ' )) 1 , , k v = f x = f x K f x dominates ( ) ( ( ) ( )) 1 , , k u = f x = f x K f x . Pareto Dominance: A vector ( ) ( ) 1, , u k u = f x = u K u is said to dominate ( ) ( ) 1, , v k v = f x = v K v (denoted by upv ) if and only if u is worse than v , {1, , }, and {1, , }, i i i i ∀i∈ K k u pv ∃i∈ K k u p v Pareto Optimal Set: For a given MOP f ( x) , x∈ the Pareto optimal set P∗ is defined as: P∗ := {x∈ ¬∃x' ∈ : f (x' ) ≤ f ( x)} Pareto Front (Nondominated front): For a given MOP f ( x) and Pareto optimal set P∗ , the Pareto front PF∗ is defined as: { ( ) ( ( ) ( )) } 1 : , , k PF∗ = u = f x = f x K f x x∈P∗ Figure 1 explains the relation between decision space and objective space and the corresponding front in each space for a given problem. 8 Fig 2.1 The Relation between Decision Space and Objective Space Moreover, there are some special points in the objective space [39]. Ideal Objective Vector (Reference Solutions Z∗ ) is the lower bound in the Paretooptimal set. The mth component of the ideal objective vector is the constrained minimum solution of the following problem: Minimize fm ( x) , subject to x∈S . ( ) 1 2 , , , T M Z∗ = f ∗ = f ∗ f ∗ K f ∗ . Utopian Objective Vector ( Z∗∗ ) has each of its components marginally smaller than that of the Ideal Objective Vector. i i Z∗∗ = Z∗ −ε with 0 i ε > for all i = 1,2,K ,M and Nadir Objective Vector ( Znad ) is upper bound in the Paretooptimal set. 2.1.4 ZDT problems [2] ZDT problems were proposed by Deb in 1999 and consist of six benchmark functions. ZDT contains several characteristics that cause difficulties for multiobjective evolutionary algorithms: for converging to the Paretooptimal front, multimodality, deception and isolated optima are applied and for maintaining diversity within the population, convexity or nonconvexity, discreteness, and nonuniformity in the front. Each of the test functions is structured in the same manner and consists itself of three functions 1 f , g , h : 9 Minimize ( ) ( ( ) ( )) 1 2 f x = f x , f x (22) Subject to ( ) ( ) ( ( ) ( )) 2 2 1 1 2 , , , , , n n f x = g x K x h f x g x K x , where ( ) 1, , n x = x K x ZDT1 (Convex Paretooptimal front): ( ) 1 1 f x = x (23 A) ( ) ( ) ( ) ( ) 1 2 1 f x f x g x g x = − (23 B) ( ) 2 9 1 1 n i i x g x n = = + − Σ (23 C) ( ) [ ] 1,..., 0,1 T n n x = x x ∈ . Given n = 30 , the Paretooptimal front is convex and formed with g ( x) =1.Figure 2.2 shows the true Paretooptimal front of ZDT1. Fig 2.2 Paretooptimal front of ZDT1 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 10 ZDT2 (Nonconvex Paretooptimal front): f1 ( x) = x1 (24 A) ( ) ( ) ( ) ( ) 2 1 2 1 f x f x g x g x = − (24 B) ( ) 2 9 1 1 n i i x g x n = = + − Σ (24 C) ( ) [ ] 1,..., 0,1 T n n x = x x ∈ . Given n = 30 , the Paretooptimal front is nonconvex and formed with g ( x) =1. Figure 2.3 shows the Paretooptimal front of ZDT2. Fig 2.3 Paretooptimal front of ZDT2 ZDT3 (Discrete Paretooptimal front): ( ) 1 1 f x = x (25 A) 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 11 ( ) ( ) ( ) ( ) ( ) ( ) 1 1 ( ) 2 1 1 sin 10 f x f x f x g x x g x g x π = − − (25 B) ( ) 2 9 1 1 n i i x g x n = = + − Σ (25 C) ( ) [ ] 1,..., 0,1 T n n x = x x ∈ , Given n = 30 , its Paretooptimal front is disconnected and formed with g ( x) =1. The two objectives are disparately scaled in the Paretooptimal front; 1 f is from 0 to 0.852 and 2 f from 0.773 to 1. The introductions of the sine function in h causes discontinuity in the Paretooptimal front. Figure 2.4 shows the Paretooptimal front of ZDT3. Fig 2.4 Paretooptimal front of ZDT3 ZDT4 (Lots of local Paretooptimal front): ( ) 1 1 f x = x (26 A) 12 ( ) ( ) ( ) ( ) 1 2 1 f x f x g x g x = − (26 B) ( ) ( ) 2 ( ) 2 1 10 1 10cos 4 n i i i g x n x π x = = + − +Σ − (26 C) ( ) [ ] [ ] 1 1,..., 0,1 5,5 T n n n x x x − = ∈ × − . Given n =10 . It has many local Paretooptimal fronts. The global Paretooptimal front is formed with g ( x) =1, the best local Paretooptimal front with g ( x) =1.25 . Not all local Paretooptimal sets are distinguishable in the objective space. Figure 2.5 shows the Paretooptimal front of ZDT4. Fig 2.5 Paretooptimal front of ZDT4 ZDT5 (Deceptive problem): ( ) ( ) 1 1 f x =1+ u x (27 A) ( ) ( ) ( ) 2 1 f x = g x f x (27 B) 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 13 ( ) ( ( )) 2 2 ,..., n n i i g x x v u x = =Σ (27 C) ( ) i u x gives the number of ones in the bit vector i x : ( ( )) ( ) ( ) ( ) 2 5 1 5 i i i i u x u x v u x u x + < = = (27 D) Given n =11, { }30 1 x ∈ 0,1 and { }5 2 , , 0,1 n x K x ∈ . The true Paretooptimal front is formed with g ( x) =10 . The global Paretooptimal fronts as well as the local ones are convex. ZDT6 (Paretooptimal solutions are nonuniformity): ( ) ( ) 6 ( ) 1 1 1 f x =1− exp −4x sin 6π x (28 A) ( ) ( ) ( ) ( ) 2 1 2 1 f x f x g x g x = − (28 B) ( ) 0.25 2 1 9 1 n i i x g x n = = + − Σ (28 C) ( ) [ ] 1,..., 0,1 T n n x = x x ∈ . Given n =10 . Its Paretooptimal front is nonconvex. The distribution of the Pareto solutions in the Pareto front is nonuniform, i.e., for a set of uniformly distributed points in the Pareto set in the decision space, their images crowd in a corner of the Pareto front in the objective space. The density of the solutions is lowest near the Paretooptimal front and highest away from the front. Figure 2.6 shows the Paretooptimal front of ZDT6. 14 Fig 2.6 Paretooptimal front of ZDT6 2.1.5 Test Problem DTLZ [12] DTLZ contains seven benchmark functions. All the functions have more than two objectives. Like ZDT problems, DTLZ also contains problem characteristics that present difficulties for multiobjective evolutionary algorithms. Therefore, DTLZ test MOEAs’ ability to deal with highdimension problems. DTLZ 1: An Mobjective problem with a linear Paretooptimal front: ( ) ( ( )) ( ) ( )( ( )) ( ) ( )( ( )) ( ) ( )( ( )) 1 1 2 1 2 1 2 1 1 1 2 1 1 1 2 1 1 1 2 Minimize 1 1 1 2 1 1 1 2 M M M M M M M M f x x x x g x f x x x x g x f x x x g x f x x g x − − − = ⋅ ⋅ ⋅ + = ⋅ ⋅ ⋅ − + = − + = − + K K (29 A) Subject to 0 1 i ≤ x ≤ , i = 1,2,K ,n 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 15 ( ) ( ) ( ( )) 2 100 0.5 cos 20 0.5 i M M M i i x X g x x x π x ∈ = + − − − Σ (29 B) The Paretooptimal solution corresponds to 0.5 i x∗ = ( i M x∗ ∈ x ) and the objective function values lie on the linear hyperplane: 1 0.5 M m m f ∗ = Σ = . k = 5 is suggested here. The total number of variables isM + k −1 . The search space contains (11k −1) local Paretooptimal fronts. The difficulty in this problem is to converge to the hyperplane. DTLZ 2: An Mobjective problem with a Spherical Paretooptimal front: ( ) ( ( )) ( ) ( ) ( ) ( ( )) ( ) ( ) ( ) ( ( )) ( ) 1 1 1 2 1 1 1 1 cos 2 cos 2 1 cos 2 sin 2 Minimize 1 sin 2 M M M M M M f x g x x x f x g x x x f x g x x π π π π π − − = + ⋅⋅ ⋅ = + ⋅⋅ ⋅ = + L L (210 A) Subject to 0 1 i ≤ x ≤ , i = 1,2,K ,n ( ) ( )2 0.5 i M M x X i g X x ∈ =Σ − (210 B) The Paretooptimal solution corresponds to 0.5 i x∗ = ( i M x∗ ∈ x ) and all objective function values must satisfy: ( )2 1 1 M m m f ∗ = Σ = . k =10 is suggested here. The total number of variables isM + k −1 . DTLZ 3: An Mobjective problem with a Global Paretooptimal front: 16 ( ) ( ( )) ( ) ( ) ( ) ( ( )) ( ) ( ) ( ) ( ( )) ( ) 1 1 1 2 1 1 1 1 cos 2 cos 2 1 cos 2 sin 2 Minimize 1 sin 2 M M M M M M f x g x x x f x g x x x f x g x x π π π π π − − = + ⋅⋅ ⋅ = + ⋅⋅ ⋅ = + L L (211 A) Subject to 0 1 i ≤ x ≤ , i = 1,2,K ,n ( ) ( ) ( ( )) 2 100 0.5 cos 20 0.5 i M M M i i x X g x x x π x ∈ = + − − − Σ (211 B) The difficult is that this problem introduces many local Paretooptimal fronts. DTLZ 4: This problem measures MOEA’s ability to maintain a good distribution of solutions: ( ) ( ( )) ( ) ( ) ( ) ( ( )) ( ) ( ) ( ) ( ( )) ( ) 1 1 1 1 1 1 2 1 cos 2 cos 2 1 cos 2 sin 2 Minimize 1 sin 2 M M M M M M f x g x x x f x g x x x f x g x x α α α α α π π π π π − − = + ⋅ ⋅⋅ = + ⋅ ⋅⋅ = + L L (212 A) Subject to 0 1 i ≤ x ≤ , i = 1,2,K ,n ,α =100 . ( ) ( )2 0.5 i M i M x X g x xα ∈ =Σ − (212 B) DTLZ 5: This problem will test an MOEA’s ability to converge to a degenerated curve: Mapping ( ( )) (1 2 ( ) ) 4 1 i i g r x g r π θ = + + (213 A) 17 i = 2,3,K ,M −1, in the test problem of DTLZ 2. ( ) 0.1 i M M x X i g x x ∈ =Σ (213 B) DTLZ 6: This problem has 2M −1 disconnected Paretooptimal regions in the search space: ( ) ( ) ( ) ( ( )) ( ) 1 1 1 1 1 1 1 2 1 Minimize 1 , ,..., , M M M M M M f x x f x x f x g x h f f f g − − − − = = = + L L (214 A) Subject to 0 1 i ≤ x ≤ , i = 1,2,K ,n , ( ) 9 1 i M M x x i M g x x x ∈ = + Σ (214 B) ( ( )) 1 1 1 sin 3 1 M i i i f h M f g π − = = − + + Σ (214 C) k = 20 is suggested here. The total number of variables isM + k −1 .This problem will test an algorithm’s ability to maintain subpopulation in different Paretooptimal regions. DTLZ 7: This problem is constructed by constraint surface approach: Minimize: ( ) ( 1) 1 n j M j n i i j M f x x n M = − = Σ , j =1,K ,M (215 A) Such that ( ) ( ) 4 ( ) 1 0 j M j g x = f x + f x − ≥ , j =1,K ,M −1 (215 B) 18 ( ) ( ) 1 ( ) ( ) , 1 2 minM 1 0 M M i j i j i j g x f x − f x f x = ≠ = + + − ≥ (215 C) subject to space 0 1 i ≤ x ≤ , i = 1,2,K ,n n =10M . There are a total of M constraints. It is difficult for MOEAs to handle these constraints while searching for the optimal solutions. Moreover, there are some nondominated solutions in the final population but not the true Paretooptimal solutions. This problem is called redundant solutions. Because of redundant solutions, the obtained set of solutions may incorrectly find a higherdimensional surface as the Paretooptimal front. 2.2 MULTIOBJECTIVE EVOLUTIONARY ALGORITHMS (MOEAs) This part includes MOEA introduction, MOEA definition, MOEA’s main procedure, and parameters in controlling the behavior of the GA and some examples of MOEAs. 2.2.1 An Introduction to MOEA [39] MOEA is motivated from the conception of evolution in biology, specifically Darwin’s “survival of the fittest” (natural selection) law. Figure 2.7 describes how MOEA works. It includes two steps. In the first step, an ideal Multiobjective Optimizer finds an optimal front consists of multiple tradeoff solutions. Then, in the second step, based on some highlevel information, one solution is chosen for implementation. Evolutionary algorithms (EAs) have become an effective tool for exploring the Paretooptimal front in multiobjective optimization problems that are often too complex to be solved by exact methods, such as linear programming or gradient search. This is because there are few alternatives for searching intractably large spaces for multiple Paretooptimal solutions. Due to their inherent parallelism and their ability to exploit similarities of solutions by recombination, 19 they are able to approximate the Paretooptimal front in a single optimization run. The numerous applications and the rapidly growing interest in the area of MOEAs take this fact into account. Fig 2.7 The Process of MOEAs to solve MOPs From Zitzler and Deb [2], the first pioneering studies on evolutionary multiobjective optimization appeared in the mideighties by Schaffer in 1984 [26] and Fourman in 1985[27]. After that, several different EA implementations were proposed from 1991 to 1994: Kursawe in 1991[28]; Hajela and Lin in 1992 [29]; Fonseca and Fleming in 1993[30]; Horn in 1994 [31]; and Srinivas and Deb in 1994 [32]. Later, these approaches were successfully applied to various multiobjective optimization problems. In recent years, some researchers have investigated particular topics of evolutionary multiobjective search, such as convergence to the Paretooptimal front by Van Veldhuizen and Lamont [33] and Rudolph [34], niching by Obayashi [35], and elitism by Parks and Miller [36]; while others have concentrated on developing new evolutionary techniques, such as Laumanns [37] and Zitzler and Thiele [38]. Today, there are some MOEAs frequently used: SPEA 2 by Zitzler [13], NSGAII by Deb [14], IBEA by Zitzler [15], PESAII by Corne [16] and MOEA/D by Zhang [17]. 20 Also, there are alternatives to EAs [39]: Evolutionary Programming (EP) and Genetic Programming (GP). EP is a mutationbased evolutionary algorithm to discrete search spaces. Similar to EA, a selfadopting rule is used to update the mutation strengths. Therefore, EP is allowed to search anywhere in the real space likes realparameter GAs. In GP, a terminal set T (constants and variables) and a function set F (operators and basic functions) are prespecified to create initial population [41]. 2.2.2 MOEAs Definition [39] The basic structure of MOEA is shown in Fig 2.8. It includes: initialize population, evaluate population, scale population fitnesses, select solutions for next population and perform crossover and mutation. Fig 2.8 Basic Structure of MOEAs It is a generic populationbased metaheuristic algorithm inspired by biological evolution and can be viewed as an evolutionary process. It is characterized by the following components: Initialize population Scale population fitnesses Select solutions for next population perform crossover and mutation Evaluate population 21 A genetic representation (or an encoding) for the feasible solutions to the optimization problem: The genetic representation may differ considerably from the natural form of the parameters of the solutions. Fixedlength and binary encoded strings for representing solutions have dominated GA research since they provide the maximum number of schemata as they are amenable to simple implementation. A population of encoded solutions evolves over a sequence of generations: The population contains not just a sample of n ideas; rather it contains a multitude of notions and rankings of those notions for task performance. Genetic algorithms ruthlessly exploit this wealth of information by reproducing high quality notions according to their performance and crossing these notions with many other highperformance notions from other strings. A fitness function that evaluates the optimality of each solution: During each generation, the fitness of each solution is evaluated, and solutions are selected for reproduction based on their fitness. The ‘goodness’ of a solution is determined from its fitness value. Genetic operators generate a new population from the existing population: The selected solutions then undergo recombination under the action of the crossover and mutation operators. Control parameters: control every step of evolutionary process. 2.2.3 The main procedure of MOEAs [39] The first one is Reproduction or Selection Operator. Reproduction Operator makes duplicates of good solutions and eliminates bad solutions while keeping the whole population size constant. The whole process inscludes three steps: identify good solutions in a population, make multiple copies of good solutions and eliminate bad solutions from the population so that multiple copies of good solutions can be placed in the population. There are three types of Selection Operators to achieve the above task: 22 Tournament selection is played between two solutions and the better solution is chosen and placed in the mating pool. Each solution can be made to participate in exactly two tournaments and any solution in a population has 0, 1 or 2 copies in new populations. Proportionate selection assigns each solution copies, the number of which is proportional to their fitness value. For instance, a solution with a fitness value i f will get i avg f f number of copies. avg f denotes the average fitness of all population members. Therefore, the solution with a higher fitness value represents a large range of cumulative probability values and has a higher probability of being copied into the mating pool. Considering the scaling problem, the outcome of operator is dependent on the true value of the fitness rather than relative fitness values. Ranking selection sorts solutions according to their fitness (true value) from the worst to the best. Each member is assigned a fitness (relative value) equal to the rank of the solution. In most cases, proportionate selection is applied with the ranked fitness values. The second one is Crossover Operator. The power of GAs arises from crossover. Crossover causes a structured, yet randomized exchange of genetic material between solutions, with the possibility that ‘good’ solutions can generate ‘better’ ones. Crossover occurs only with some probability pc (the crossover probability or crossover rate). When the solutions are not subjected to crossover, they remain unmodified. The third one is Mutation Operator. Mutation appears to be more useful than crossover when the population size is small while there is evidence that crossover can be more useful than mutation when the population size is large. Other factors, such as the representation, selection scheme, and the fitness function itself may all have an effect on the relative utility of crossover and mutation. 2.2.4 Control Parameters of Genetic Algorithms [40] 23 To control the behavior of the GA, the role of the parameters pc and pm are often considered. The choice of pc and pm is known to critically affect the behavior and performance of the GA. The crossover probability pc controls the rate at which solutions are subjected to crossover. The higher the value of pc the quicker are the new solutions introduced into the population. As pc increases, however, solutions can be disrupted faster than selection can exploit them. Typical values for pc are in the range [0.5, 1.0]. Mutation is only a secondary operator to restore genetic material. Large values of pm transform the GA into a purely random search algorithm, while some mutation is required to prevent the premature convergence of the GA to suboptimal solutions. Typically pm is chosen in the range [0.005, 0.05]. The balance between converge and spread characteristics of the GA is dictated by the values of pc and pm. Increasing values of pc and pm promotes exploration at the expense of exploitation. Moderately large values of pc (0.51.0) and small values of pm (0.0010.05) are commonly employed in GA practice. Moderately large values of pc, (0.5 < pc < 1.0), and small values of pm (0.001 < pm < 0.05) are essential for the successful working of GAs. The moderately large values of pc promote the extensive recombination of schemata, while small values of pm are necessary to prevent the disruption of the solutions. 2.2.5 Some Examples of MOEAs Today, there are some MOEAs frequently used: SPEA 2 by Zitzler [13], NSGAII by Deb [14], IBEA by Zitzler [15], PESAII by Corne [16] and MOEA/D by Zhang [17]. In the experiment conducted in Chapter 4, these five algorithms are compared under the performance metric ensemble. 24 First, we consider Strength Pareto Evolutionary Algorithm 2 (SPEA 2). SPEA is an effective technique for finding or approximating the Paretooptimal set for multiobjective optimization problems. It has shown very good performance in comparison to other MOEAs. Based on SPEA, SPEA 2 incorporates a finegrained fitness assignment strategy, a density estimation technique, and an enhanced archive truncation method. The main structure of SPEA 2 is presented in Table 2.1. Table 2.1 includes input and output of the algorithm, and the process of the algorithm to deal with MOPs: Given input: N (population size), N (archive size) and T (maximum number of generations) Required output: A (nondominated set) Step1: Initialization: Generate an initial population 0 P and create the empty archive (external set) P0 =φ . Set t = 0. Step2: Fitness assignment: Calculate fitness values of individuals in t P and Pt Step 3:Environmental selection: Copy all nondominated individuals in t P and Pt to Pt+1 . If size of Pt+1 exceeds N then reduce Pt+1 by means of the truncation operator, otherwise if size of Pt+1 is less than N then fill Pt+1 with dominated individuals in t P and Pt . Step 4:Termination: If t ≥ T or another stopping criterion is satisfied then set A to the set of decision vectors represented by the nondominated individuals in Pt+1 . Step 5:Mating selection: Perform binary tournament selection with replacement on Pt+1 in order to fill the mating pool. Step 6: Variation: Apply recombination and mutation operators to the mating pool and set 1 t P + to the resulting population. Increment generation counter (t = t +1) and go to Fitness assignment step again. Table 2.1 The main structure of SPEA 2 25 In fitness assignment, each individual i in t P and t P is assigned a strength value S (i) representing the number of solutions it dominates: ( ) { } t t S i = j j∈P + P ∧ i f j (216 A) ⋅ denotes the cardinality of a set, + stands for multiset union and f corresponds to the Pareto dominance relation. Raw fitness R(i) is determined by the strengths of its dominators in both archive and population: ( ) ( ) j Pt Pt , j i R i S j ∈ + =Σ f (216 B) Density information is incorporated into differentiate individuals having identical raw fitness values: ( ) 1 k 2 i D i σ = + (216 C) where k = N + N is the square root of the sample size and k i σ is the k th element gives the distance sought. Finally, for an individual i , its fitness F (i) = R(i) + D(i) (216 D) In Environmental Selection, first, all nondominated individuals have fitness lower than one are copied to the archive of the next generation: t 1 { t t ( ) 1} P + = i i∈P + P ∧ F i < (217 A) 26 Then, there are three conditions: If Pt+1 = N , the environmental selection step is completed If Pt+1 < N , the best N − Pt+1 dominated individuals with F (i) ≥1 in the previous archive and population are copied to the new archive If Pt+1 > N , procedures are made to remove individuals from Pt+1 until Pt+1 = N At each iteration, individual i is chosen for removal for which d i ≤ j for all j∈Pt+1 : ( ) 1 1 : 0 : 0 : 0 : k k d t i j l l k k t i j i j i j k P k P l k σ σ σ σ σ σ + + ≤ ⇔∀ < < = ∨ ∃ < < ∀ < < = ∧ < (217 B) k i σ denotes the distance of i to its k th nearest neighbor in Pt+1 . The individual with the minimum distance to another individual is preferred. Second, we introduce NonDominated Sorting Genetic AlgorithmII (NSGAII). A nondominated sorting based multiobjective evolutionary algorithm NSGAII, has two advantages: computational complexity is O(mN2 ) ; a selection operator is presented to create a mating pool by combining the parent and child populations and selecting the best (with respect to fitness and spread) N solutions. The main structure of NSGAII is presented in Table 2.2. The third one is Regionbased Selection in Evolutionary Multiobjective Optimization (PESAII). PESAII proposes a new selection technique, called RegionBased selection, for evolutionary multiobjective optimization algorithms in which the unit of selection is a hyperbox 27 in objective space. A hyperbox is selected and the resulting selected individual is randomly chosen from this hyperbox. The fourth one is IndicatorBased Selection in Multiobjective Search (IBEA). IBEA is combined with arbitrary indicators and adapted to the preferences of the user and moreover does not require any additional diversity preservation mechanism to be used. It provides an approach to allow preference information of the decision maker be integrated into multiobjective search. Step1: Generate random parent population 0 P and its child population 0 Q : Initially, a random parent population 0 P is created. The population is sorted based on the nondomination. Each solution is assigned rank equal to its nondomination level where 1 is the best level. Thus, minimization of fitness is assumed. Binary tournament selection, recombination, and mutation operators are used to create a child population 0 Q of size N . Set t = 0 Step2: t t t R = P ∪Q Combine parent and children population. The population t R will have size 2N . Step3: F = nondominatedsort ( t R ) until 1 t P N + < Population t R is sorted based on the nondomination sorting. The new parent population 1 t P + is formed by adding solutions from the first front to the next best front before the size exceeds N . Step4: crowdingdistanceassignment ( i F ) and t 1 t 1 i P P F + + = ∪ Calculate crowding distance in i F and include k th nondominated front in the parent population. Step5: Sort ( 1 t P + , n ≥ ) and [ ] 1 1 0 : t t P P N + + = Sort in descending order and choose the first N elements of 1 t P + . Step6: t 1 Q + =makenewpop ( 1 t P + ) This population of size N is now used for selection, crossover and mutation to create a new population. Table 2.2 The main structure of NSGAII Table 2.3 presents the input and output of the algorithm, and the process of the algorithm to deal with multiobjective problem. 28 The final one is MOEA/D: A Multiobjective Evolutionary Algorithm Based on Decomposition. MOEA/D decomposes a multiobjective optimization problem into a number of scalar optimization subproblems and optimizes them simultaneously. Each subproblem is optimized by only using information from its several neighboring subproblems, which makes MOEA/D with lower computational complexity at each generation. Given input: α (population size), N (maximum number of generations) and κ (fitness scaling factor) Required output: A (Pareto set approximation) Step1: Initialization: Generate an initial population P of sizeα ; set the generation counter m to 0. Step2: Fitness assignment: First scale objective and indicator values, and then use scaled values to assign fitness values. Determine for each objective i f its lower bound min ( ) i x P i b f x ∈ = and upper bound max ( ) i x P i b f x ∈ = Scale each objective to the interval [0, 1], i, e, ' ( ) ( ( ) ) ( ) i i i i i f x = f x − b b − b Calculate indicator values I (x1, x2 ) using the scaled objective values ' i f , instead of the original i f , and determine the maximum absolute indicator value ( ) 1 2 1 2 , max , x x P c I x x ∈ = For all x1∈P set ( ) ({ } { }) ( ) { } 2 1 2 1 1 , \ I x x c x P x F x e − ⋅κ ∈ =Σ − Step3: Environmental selection: Iterate the following three steps until the size of population P does not exceed α : Choose an individual x∗ ∈P with the smallest fitness value, i.e. f (x∗ ) ≤ f ( x) for all x∈P . Remove x∗ from the population. Update the fitness values of the remaining individuals, i.e. ( ) ( ) ({ } { }) I x , x (c ) F x F x e − ∗ ⋅κ = + Step4: Termination: If t ≥T or another stopping criterion is satisfied then set A to the set of decision vectors represented by the nondominated individuals in P . Step5: Mating selection: Perform binary tournament selection with replacement on P in order to fill the mating pool. Step6: Variation: Apply recombination and mutation operators to the mating pool and add the resulting population to P . Increment generation counter ( t = t +1) and go to Fitness assignment step. 29 Table 2.3 The main structure of IBEA Table 2.4 presents the input and output of the algorithm, and the process of the algorithm to deal with multiobjective problem. Input: a stopping criterion; the number of the subproblems considered in MOEA/D; a uniform spread of N weight vectors: λ1,K ,λ N ; and T , the number of the weight vectors in the neighborhood of each weight vector. Output: External Population (EP) Step 1: Initialization: Set EP =∅. Compute the Euclidean distances between any two weight vectors and then work out the closest weight vectors to each weight vector. For each i = 1,K , N , set ( ) { } 1, , T B i = i K i , where λ1,K ,λ iT are the T closest weight vectors to λ i . Generate an initial population x1,K , xN randomly or by a problemspecific method. Set FV i = F (xi ) Initialize ( ) 1, , T m z = z K z by a problemspecific method. Step 2: Update For i = 1,K , N , do Reproduction: Randomly select two indexes k , l from B(i) , and then generate a new solution y from xk and xl by using genetic operators. Improvement: Apply a problemspecific repair/ improvement heuristic on y to produce y' Update of z∗ : for each j =1,K ,m , if ( ' ) j j z < f y , then set ( ' ) j j z = f y . Update of Neighboring Solutions: if gte ( y 'λ j , z ) ≤ gte (x j λ j , z ), for each index j∈B(i), set x j = y' and FV j = F ( y' ) . ( ) { ( ) } 1 te j j , max j i i i i m g x λ z∗ λ f x z∗ ≤ ≤ = − , λ1,K ,λ N be a set of even spread weight vectors and z∗ be the reference point. Update of EP: Remove EP from all the vectors dominated by F ( y' ) and add F ( y' ) to EP if no vectors in EP dominate F ( y' ) . Step 3: Stopping Criteria If stopping criteria is satisfied, then stop and output. Otherwise, go to Step 2. Table 2.4 The main structure of MOEA/D 2.3 Performance Metrics 30 In this part, first some important concepts are introduced. These are applied to define relations between different approximation fronts. Then, we will explain both unary and binary performance metrics in detail. 2.3.1 Outperformance Relations Hansen and Jaszkiewicz [9] have focused on the problem of evaluating approximations to the true Pareto front. They define a number of outperformance relations that classify the relationships between two sets of nondominated objective individuals while the preferences information of the test problem is unknown. Based on these, Knowles and Corne [18] further give two definitions about Monotony and Relativity. Weak Outperformance [9] A weakly outperforms B ( W AO B ): A weakly outperforms B if and only if nondominated points of A∪B are the same as the whole points in A , and A ≠ B . Therefore, each point 2 z ∈B is covered by a point 1 z ∈ A ; ‘cover’ means is equal to or dominates 2 z . Additional, there is at least one point 1 z ∈ A which is not contained in B . Adding to B a new nondominated individual can generate a new approximation front that weakly outperformB . Strong Outperformance [9] A strongly outperforms B ( S AO B ): A strongly outperforms B if and only if nondominated points of A∪B are the same as the whole points in A , and B contains another dominated points. Therefore, each point 2 z ∈B is covered by a point 1 z ∈ A . Additional, there is at least one point 2 z ∈B that is dominated by a point 1 z ∈ A and is not contained in B . Adding to B a new individual that dominates at least one point in B can generate a new approximation front that strongly outperformB . Complete Outperformance [9] 31 A completely outperforms B ( C AO B ): A completely outperforms B if and only if nondominated points of A∪B are the same as the whole points in A , and none of nondominated points of A∪B belongs to B . Therefore, each point 2 z ∈B is dominated by a point 1 z ∈ A . Adding to B a new individual that dominates all points in B can generate a new approximation front that completely outperformB . Incomparable Outperformance [9] A incomparable outperforms B is defined as some points in A dominate points in B and some points in B dominate points in A . In this condition, we cannot state that which one is better. Compatibility and Weak compatibility [9] Let , or W S C O = O O O : Compatibility: A comparison metric R is compatible with an outperformance relationO if for each pair of nondominated sets A and B , such that AOB , R will evaluate A as being better than B . Weak compatibility: A comparison metric R is compatible with an outperformance relation O if for each pair of nondominated sets A and B , such that AOB , R will evaluate A as being no worse than B . Monotony and Weak Monotony [18] Monotony: Given a nondominated set A , adding a nondominated point improves its evaluation. Compatibility with W O is necessary and sufficient for ensuring monotony [18]. Weak Monotony: Given a nondominated set A , adding a nondominated point does not degrade its evaluation. 32 Relativity and Weak Relativity [18] Relativity: The evaluation of Z∗ is uniquely optimal, i.e., all other nondominated sets have a strictly inferior evaluation. Compatibility with W O is sufficient but not necessary for ensuring relativity [18]. Weak Relativity: The evaluation of Z∗ is nonuniquely optimal, i.e., all other nondominated sets have a nonsuperior evaluation. From above theories, we can find AOC B⇒ AOS B⇒ AOW B and C S W O ⊂ O ⊂ O . Complete Outperformance is the strongest of the relation and easiest to be compatible; Weak Outperformance is the weakest of the relation and most difficult to be compatible. 2.3.2 Compatibility and Completeness Zitzler [10] has proposed a method that links Comparison Methods and Dominance Relations to reveal differences in performance between MOEAs, and make the statement that an algorithm outperforms another one. What conclusions can be drawn with respect to the dominance relations is emphasized. Quality Indicator: In order to quantify quality differences between approximation sets, quality measures are necessary used to map approximation sets to the real numbers by applying common metrics to the resulting real numbers. Based on this observation, Zitzler defines what a quality measure is: An m ary quality indicator I is a function I : m →R , which assigns each vector ( ) 1 2 , , , m A A K A of m approximation sets a real value, ( ) 1 2 , , , m I A A K A . 33 Often, not a single indicator but rather a combination of different quality indicators is used in order to assess approximation sets. The combination quality indicator vector can be regarded as a function that assigns each approximation set a vector of multiple real numbers. Comparison Method: Here, we use PseudoBoolean function E to compare different approximation sets. It maps vectors of real numbers to Booleans: E(I ) := (I =1) means E is true if and only if I = 0 . A comparison method I ,E C is based on a combination of one or more quality indicators I and a Boolean function E . Given two approximation sets A, B∈ , ( ) 1 2 , , , k I = I I K I a combination of quality indicators, and E : IRk × IRk →{false,true} a Boolean function, from Zitzler’s theory, If I ,E C is defined by combination of unary indicators and Boolean function E , ( ) ( ( ) ( )) , , , I E C A B = E I A I B ; If I ,E C is defined by combination of binary indicators and Boolean function E , ( ) ( ( ) ( )) , , , , , I E C A B = E I A B I B A Compatibility and Completeness: Compatibility: for any A, B∈ , the result of ( ) , , I E C A B can indicate that A is better than B , or B is better than A . Completeness: for any A, B∈ , the relation that A is better than B , or B is better than A can decide the value of ( ) , , I E C A B . 34 For a particular quality indicator, if there exists a Boolean function such that the resulting comparison method is compatible and in addition complete with respect to the various dominance relations (strong, weak or complete), this quality indicator can be evaluated to be powerful quality indicator. However, Zitzler [10] has proven there exists no comparison method based on a finite combination of unary quality indicators that is compatible and complete at the same time. It means for any combination of a finite number of unary quality indicators, a Boolean function cannot be found such that this comparison method is both compatible and complete. From the above reasons, the number of performance metrics that determine a better approximation set from two sets is infinite. Furthermore, to be able to detect whether an approximation front weakly dominates or dominates another approximation front, the number of performance metrics should be greater than or equal to the number of objectives. 2.3.3 Unary performance metrics The first type of performance metrics concerns about assessing the Number of Pareto Optimal Solutions in the Set. Ratio of Nondominated Individuals (RNI) [5] gives the proportion of the useful solutions known as the Paretofront in a given population size; Error Ratio (ER) [4] evaluates the proportion of non true Pareto points in the approximation front; Overall Nondominated Vector Generation and Ratio (ONVG) [4] counts the number of distinct nondominated points generated; and Pareto Dominance Indicator (NR) [3] measures the ratio of nondominated solutions contributed by a particular solution set to the nondominated solutions provided by all solution sets. Ratio of Nondominated Individuals (RNI) [5] The performance measure is: 35 _ ( ) nondom indiv RNI X P = (218) nondom_ indiv : Nondominated individuals in population X with size P . If RNI =1 , all the individuals in X are nondominated; and if RNI = 0 , none of the individuals in X is nondominated. It is always required to have enough qualified individuals to construct a Pareto front. Therefore, RNI is significant in that it checks the proportion of nondominated individuals in population X . Knowles and Corne in [18] have stated that: RNI is not weakly compatible with any outperformance relation. It exhibits monotony. Clearly, add a nondominated point will make the RNI value better. It violates relativity. True Pareto front cannot be sure to have more numbers of nondominated points than other approximation fronts. Error Ratio (ER) [4] It is defined as the proportion of non true Pareto points in reference set: ( ) ( ) 1 n i i e ER X P = = Σ (219) Individual i is a point in approximation front X . P is the number of individuals in X . 0 i e = means individual i is in true Pareto set; and 1 i e = means individual i is not in true Pareto set. Lower value of ER implies a small proportion of non true Pareto points in X and represents better nondominated sets. It is a reference metric using true Pareto front as reference set. Knowles and Corne in [18] have stated that: ER is only weakly compatible with C O . It is not weakly compatible with S O or W O . If one algorithm generates 100 points, one in the Pareto front, 36 the other 99 points are very far from the Pareto front; its error ratio is 0.99. However, if another algorithm also generates 100 points, all these 100 points are very close to Pareto front, its error ratio is 1. Although the second algorithm’s error ratio is larger than the first one, we can see clearly the second one is better than the first one. ER strongly violates monotony: Add a nondominated but nonPareto optimal points in an approximation set, makes the ER score worse. The advantage is easy to understand and easy to calculate. It is scaling independent. The disadvantage is the true Pareto front information is needed. It is incompatible with the outperformance relations. Overall Nondominated Vector Generation and Ratio (ONVG) [4] It measures the total number of nondominated vectors found in approximation front during MOEA execution. It is defined as: ONVG = PFknown (220) known PF represents approximation front. From [19], too few vectors in known PF make the front’s representation poor and too many vectors may overwhelm the decision maker. Knowles and Corne in [18] have stated that: ONVG is not weakly compatible with any outperformance relation. It does not exhibit either weak monotony or weak relativity. The advantage is easy to calculate and scaling independent while the disadvantage is A outperformance B on this metric does not mean A is clearly better than B . Pareto Dominance Indicator (NR) [3] Considering the different PFs , 1 2 , , n A A K A evolved by algorithms, this metric measures the ratio of nondominated solutions that is contributed by a particular solution set i A to the nondominated solutions provided by all solution: 37 ( ) 1 1 2 , ,..., n B A NR A A A B = I (221 A) { ( ) } 1 2 , ... i i j n i B = b ∀b ¬∃a ∈ A U A U A p b (221 B) 1 A is the solution set under evaluation. Zitzler show that no combinations of unary performance metrics can provide a clear indication of whether an evolved set is better than another in the Pareto dominance sense, this metric can be a complement to another metrics [1]. It is weak compatible with S O and C O . The second type of performance metrics focuses on measuring the closeness of the solution to the True Pareto Front. Generational Distance (GD) [4] measures how far the evolved solution set is from the rue Pareto front; and Maximum Pareto Front Error (MPFE) [4] identifies the largest distance between the point in the theoretical Pareto front and the point in the approximation front. Final Generational Distance (GD) [4] ( )1 1 n p p i i d GD n = = Σ (222) n is the number of vectors in the approximation front, i d is the distance in objective space between individual i and the nearest member of true PF .This metric is a value representing how “far” the approximation front is from true Pareto front. Lower value of GD represents better performance. It measure general process towards true Pareto front [18]. It is a reference metric using true Pareto front as reference set. Knowles and Corne in [18] have proven that GD is not weakly compatible with W O , but is compatible with S O . It violates weak monotony which implies adding a nondominated point to 38 an approximation fronts cannot improve its GD value. It exhibits weak relativity since any subset of Pareto front has an optimal GD. For a constant size of nondominated set, GD is compatible with S O . But it is not used for nondominated sets that are changing in cardinality. It cannot be reliably differentiate between different levels of complete outperformance. The true Pareto front information is needed. Maximum Pareto Front Error (MPFE) [4] It measures the largest distance between any vector in the approximation front and the corresponding closest vector in true Pareto front. It finds the largest distance between individual j in approximation front and individual i in the true Pareto optimal front. ( ( ) ( ) ( ) ( ) )1 1 1 2 2 max min p p p i j i j j i MPFE = f x − f x + f x − f x (223) It is a reference metric using true Pareto front as reference set. In terms of Pareto compatibility, it is not weakly compatible with outperformance relation. It violates weak monotony. It exhibit weak relativity since any subset of Pareto front is optimal. It is cheap to compute. It helps us to focus on how far the worst point is. However, from [19], for a nondominated set, a good performance in MPFE does not ensure it is better than another one with a much worse MPFE. The true Pareto front information is needed. The third type of performance metrics measures distribution of the Solutions. Uniform Distribution (UD) [5] measures the distribution of an approximation front under a predefined parameter share σ ; Spacing [6] measures how evenly the evolved solutions distribute itself; and Number of Distinct Choices (NDCu) [7] identifies solutions that are sufficiently distinct for a special valueu . Uniform Distribution (UD) [5] 39 It measures the distribution of nondominated individuals on the found tradeoff surface. For a given set of nondominated individuals X ' in a population X : ' 1 ( ) 1 nc UD X S = + (224 A) ( ) ' ' ' ( ' ) 1 x N i i nc x nc x nc X S N − − = − Σ (224 B) ( ) ' ' , ( , ) x N i j j i nc x f i j ≠ = Σ (224 C) ( ) {1, ( , ) 0. , dis i j share else f i j 〈δ = (224 D) ( ) ( ) ' ' ' ' x N i i x nc x nc X N − = Σ (224 E) share σ is predefined by decision maker. nc S is the standard deviation of niche count of the overall set of nondominated individuals. ' x N is the size of the set x' . ( ' ) i nc x is the niche count of the ith individual x' and dis (i, j ) is the distance between individual i and j in the objective domain. Knowles and Corne in [18] have proven that: UD is not even weakly compatible with W O . It violates monotony in that an additional point cannot make sure the distribution is improved. It violates relatively. An approximation front far from the Pareto front can have the same UD score to the Pareto front. It has low computational overhead and provides the opportunity for Decision maker to choose well distributed front according to real application need by assigning different value to share σ . However, it is difficult to choose share σ without any reference information. 40 Spacing [6] This metric is a value measuring the distribution of vectors throughout approximation front. It provides information about the distribution of vectors obtained. Because approximation front’s “beginning” and “end” are known, a suitably defined metric judge how well known PF is distributed. 2 1 1 1 n i i S d d n − + = − − Σ (225 A) ( ( ) ( ) ( ) ( ) )2 2 1/ 2 1 1 2 2 min i j i j i j d = f x − f x + f x − f x (225 B) i d is minimum distance between two solutions in the approximation front. Knowles and Corne in [18] have stated that: Spacing is not even weakly compatible with W O . It violates monotony in that an additional point cannot make sure the distribution is improved. It violates relatively. An approximation front far from the Pareto front can have the same Spacing score to the Pareto front. It has low computational overhead and can be generalized to more than two dimensions by extending the definition of i d . But the use of normalized distances may be problematic. Number of Distinct Choices (NDCu) [7] In this metric, only those solutions that are sufficiently distinct from one another should be accounted for as useful design options. The quality ( , ) u NT q P indicates whether or not there is any point k p ∈P that falls into the region. ( ) u T q is decided by 1 um , 0 < u <1.m is the dimension of objectivespace ( ) ( ) {1, , ( ) 0, , , k k u k k u p P p T q u p P p T q NT q P ∃ ∈ ∈ ∀ ∈ ∉ = (226 A) ( ) u NDC P is the number of distinct choices for a prespecified value ofu : 41 ( ) ( ) 2 1 1 1 1 0 0 0 ... , m v v v u u l l l NDC P NT q P − − − = = = = Σ ΣΣ (226 B) From [7], for a prespecified value ofu , an observed Pareto solution set with a higher value of the quantity ( ) u NDC P is preferred to a set with a lower value. In terms of Pareto compatibility: u NDC is not even weakly compatible with W O . It violates monotony in that an additional point cannot make sure the distribution is improved. It violates relatively. An approximation front far from the Pareto front can have the same Spacing score to the Pareto front. It provides the opportunity for Decision maker to choose well distributed front according to real application need by a prespecified value of u . However, it is not easy to compute. The fourth category of performance metrics concerns spread of the solutions. Maximum Spread (MS) [3] measures how well the rue Pareto front is covered by the approximation set. Maximum Spread (MS) [3] It addresses the range of objective function values and takes into account the proximity to true PF . This metric is applied to measure how well the true PF is covered by the known PF . ( ) ( ) ( ) 2 max max min min max min 1 1 M min , max , i i i i i i i f F f F MS M = F F − = − Σ (227) max i f and min i f are the maximum and minimum of the i th objective in known PF , respectively; max i F and min i F are the maximum and minimum of the i th objective in true PF , respectively. If MS ( A) > MS (B) , the solution A is preferred to B . The last type of performance metrics considers both closeness and diversity: 42 Hypervolume Metric [11] The hyperarea difference metric [11] is also called Smetric and can be used to quantitatively evaluate the difference between the size of the objective space dominated by an observed Pareto front and that of the space dominated by the true Pareto front. The true Pareto front set dominates the largest volume in solution space while an approximation front may only dominate a portion of true Pareto front dominated volume. A quantitative measure is obtained as to how much worse an observed Pareto front is when compared to the true Pareto front. Although in real problem, the true Pareto front is usually unknown; it should still be possible to compare an approximation front to another so as to draw a conclusion that which front is better. Let HD(P) represent the hypervolume difference quantity between the inferior regions of the true Pareto solution set t P and the inferior region of the observed Pareto solution set P [7]: ( ) ( ( ) ( )) 1 ( ( )) in t in in HD P = space S P − S P = − space S p (228) In [4], Veldhuizen also propose a Hyperarea Ratio metric defined as: 1 2 H HR H = (229) 1 H is the hyperarea of known PF while 2 H is that of true PF .. In the proposed performance metrics ensemble to be presented in Chapter 3, we adopt this modified Hyperarea Ratio Metric. It is compatible with all the outperformance relations [18]. Each algorithm can be assessed independently of the other algorithms in this metrics. Hypervolume Metric differentiates between different degrees of complete outperformance of two sets, so it can evaluate how much better an 43 approximation set is than the other approximation set. It is scaling independent, noncardinal and its meaning is intuitive. It can be misleading if the Pareto optimal front is nonconvex [3]. Therefore, it focuses on the volume of the objective space dominated by an approximation set and calculates the hypervolume of the multidimensional region enclosed by approximation front and a ‘reference point’ [18]. A reference point is also called the upper boundary of the region. The choice of the upper boundary determines which approximation front has the maximum dominated hypervolume. In many cases, we need to find the reference point to represent the upper boundary of the region. The reference point should be chosen so that it is dominated by all Paretooptimal solutions. Auger and Zitzler [20] have proposed a method to define the reference point r = (r1, r2 ) for a specific problem: Let u be an integer larger than or equal to 2. Assume that f is continuous on[ ] min max x , x , nonincreasing, differentiable on [ ] min max x , x and that f’ is continuous on[ ] min max x , x : The leftmost extremal point: If ( ) min limx x f x → − < +∞: [ ] { ( )( ) ( )} min max ' 2 max , : sup x x x R f x x x f x ∈ = − + (230) When 2 R is finite, the leftmost extremal point is contained in optimal u distributions if the reference point ( ) 1 2 r = r , r is such that 2 r is strictly larger than 2 R . 2 r can be chosen to be 2 R . If ( ) min limx x f x → − = +∞ , the left extremal point of the front is never included in optimal udistributions. So, 2 r = +∞. 44 The rightmost extremal point: when f is strictly negative on[xmin , xmax ] : [ ] ( ) ( ) ( ) min max min 1 ' , : sup x x x f x f x R x ∈ f x − = + (231) When 1 R is finite, the rightmost extremal point is contained in optimal u distributions if the reference point ( ) 1 2 r = r , r is such that r1 is strictly larger than 1 R . 1 r can be chosen to be 1 R . If ( ) max f x = 0 , the right extremal point of the front is never included in optimal u  distributions. So, 1 r = +∞ . Hypervolume metric also has a large computational overhead. Largest computation is defined [21] by Klee’s Measure Problem (KMP) and lowest computation is defined by the UniformGap Problem. KMP is the problem of computing the length of the union of a collection of intervals on the real line and defines the upper boundary of the computation. It can be solved with computational complexity in optimal O(nlog n) time. First, measure of a union of hyperrectangles in d dimensions: O(nd −1 log n)⇒O(nd −1 )⇒O(nd 2 log n) . Second, the weakly dominated hypervolume for a point set 0 P IRd ≥ ⊆ as a special case of Klee’s measure problem: The polytope Πd is patterned by the collection of hyperrectangles { } p p P R ∈ with { } 0 : d : p R x IR x p ≥ = ∈ ≤ spanned by the points in P and the reference point 0 r 0 IRd ≥ = ∈ . Third, the set of hyperrectangles is the input and the desired hypervolume output. Finally, we get an upper bound of computation time in O(nlog n + nd 2 log n) . The best upper bound currently known for d > 3:O(nlog n + nd 2 ) 45 The UniformGap Problem defines the lower boundary of the computation. This problem uses the fixeddegree algebraic decision tree, which is the standard model used in computational geometry and is used to prove lower bounds for (geometric) decision problems. It captures the behavior of a (loopunrolled) algorithm that branches depending on the outcome of evaluations of boundeddegree polynomials. A lower bound on the complexity of a given problem can then be derived by establishing a lower bound on the depth of any such tree resembling any valid algorithm to solve this problem. Moreover, lineartime reduction from problem A to problem B means the lower bound for problem A is a lower bound for problemB . 2.3.4 Binary performance metrics The first type of binary performance metrics based on unary quality indicator. It includes ε  indicator Iε , enclosing hypercube Indicator and coverage difference metrics (Dmetric). First, ε indicator Iε [10] can be used to compare algorithms directly without reference front information. This is defined as: ( , ) inf { 2 1 : 1 2} R I A B z B z A z z ∈ ε∈ ε = ∀ ∈ ∃ ∈ ≥ (232 A) 1 2 1 : 1 2 i i z z i n z z ε ≥ ⇔∀ ≤ ≤ ≤ε ⋅ (232 B) I ( A,B) ∈ reflects the value ofε . For every individual z2 in B , there must exist an individual z1 in A dominateε ⋅ z2 . For any pair A, B∈ , A B I ( A,B) 1 ∈ f f ⇒ < .Therefore, if A is better than B , ε <1 46 However, I ( A, B) 1 ∈ < can only imply that A is not worse than B in strictly dominates and better relations. Second, Enclosing Hypercube Indicator [10] is defined as: ( ) {{( )} } 1 HC sup , ,..., a R I A a a a A ∈ = > (233 A) ( ) {{( )} } 2 HC inf , ,..., b R I A b b b A ∈ = < (233 B) ( ) ( ) 2 1 I HC A < I HC B ⇒ A> B ∀1≤ i ≤ n +1 (233 C) ( ) 2 I HC A is the point that worse than all individuals in A . ( ) 1 I HC B is the point that better than all individuals in B . Finally, coverage difference metrics (Dmetric) [11] is defined as the size of the space dominated by A and not dominated by B (regarding the objective space), A, B ⊆ X be two sets of decision vectors. D( A,B) = S ( A + B) − S (B) (234 A) where S ( A) is the Hypervolume Difference Metric (Smetric). Zitzler [11] suggest that (ideally) the D metric is used in combination with the S metric where the values may be normalized by a reference volume V , where (for a maximization problem) V is given by: ( max min ) 1 k i i i V f f = =Π − (234 B) 47 max i f and min i f represent the maximum respectively minimum value for the objective i f . Thus, the value ( ) ( ) 1 , , D A B D A B V = represents the relative size of the region (in the objective space) dominated by A and not dominated by B . The second type is direct comparison binary metrics: C metrics and R metrics. C metrics [9] maps the ordered pair ( A,B) to the interval[0,1]: ( ) { : } , b B a A a b C A B B ∈ ∃ ∈ ≤ = (235) C( A,B) =1: all decision vectors in B are weakly dominated by A ; C( A,B) = 0 : none of the points in B are weakly dominated by A . It is compatible with S O and C O , but incompatible with W O . Only if C( A,B) =1 andC(B, A) <1 , it is compatible with W O . It is Nonsymmetric: C( A,B) is not necessarily equal to −C(B, A) . It has low computational overhead. Scale and reference point independent. However, there are situations when the metric C cannot decide if an obtained front is better than the other. R metrics [5] consist of three submetrics: R1( A,B,U, p) , R2( A,B,U, p) and R3( A,B,U, p) . R1( A,B,U, p) calculates the probability that approximation A is better than approximation B over an entire set of utility functions. 1( , , , ) ( , , ) ( ) u U R A B U p C A B u p u du ∈ = ∫ (236 A) ( ) ( ) ( ) ( ) ( ) ( ) ( ) 1, , , 1 2, 0, u A u B C A B u u A u B u A u B ∗ ∗ ∗ ∗ ∗ ∗ > = = < (236 B) 48 ( ) max { ( )} z A u∗ A u z ∈ = , ( ) max { ( )} z B u∗ B u z ∈ = and p(u) is an intensity function expressing the probability density of the utility. If R1( A,B,U, p) > 0.5 , A is the winner; if R1( A,B,U, p) < 0.5 , B is the winner. In terms of Pareto compatibility: R1 is only weakly compatible with W O and is not compatible with C O . It has low computational overhead and Scale independent but R1 is cycleinducing. R2( A,B,U, p) calculates the expected difference in the utility of an approximation A with another one B . 2( , , , ) ( ( ) ( )) ( ) u U R A B U p u∗ A u∗ B p u du ∈ = ∫ − (237) R2 is compatible with W O . It can differentiate between different levels of complete outperformance. However, each utility function in U must be appropriately scaled with respect to the others and its relative importance. R3( A,B,U, p) calculates the ratio of the best utility values. That is the expected proportion of superiority. ( ) ( ( ) ( )) ( ) 3 , , , ( ) u U u A u B R A B U p p u du u A ∗ ∗ ∗ ∈ − = ∫ (238) 49 CHAPTER THREE METHODOLOGY This chapter first explains the motivation of the designed performance metrics ensemble. Then, we describe the proposed approach in detail. 3.1 MOTIVATION Chapter 2 has introduced a large number of available performance metrics with different characteristics. However, none of these metrics alone can faithfully measure MOEA performance independently. Every metric can provide some specific but limited information and can only be used effectively in some specified conditions. For example, UD does a poor job when the Pareto front is discontinued and Hypervolume can be misleading if the Pareto optimal front is nonconvex [4]. This means one metric cannot entirely evaluate MOEAs in all conditions. Every metric focuses on some special characteristics while neglects information in others. Also, every metric has its unique character; no metrics can substitute others completely. Therefore, a single metrics cannot provide a comprehensive measure for MOEAs. Moreover, because reduce objective space must losing information, a fixed number of indicators are not sufficient to make a comprehensive measure for MOEAs [11]. Meanwhile, different metrics perform differently in different test problems. For a given MOEA, one metric may do well in one test problem, however, in other test problems, it may be misleading. For a specific test problem, we cannot know which metric is better. We need to try various metric to identify which one is the best. This is a heavy computational process. To overcome these challenge and arrive at a faithful evaluation of a given MOEAs, performance metrics ensemble is necessary. Ensemble fair performance than what Ensemble metrics not only but avoid the choosing process and can be 3.2 OVERVIEW OF PERFORMANCE METRICS ENSEMBLE The proposed framework is shown in Figure 3.1 Table 3.1 explains the whole process of ensemble method in detail. 50 given the same initial populations to each and every candidate MOEAs are performed, resulting 50 approximation fronts from each chosen MOEA for comparison. DoubleTournament Selection, every individual to compete. After one winner is found, identify which algorithm it is 50 method uses multiple metrics to obtain could be obtained from any of single performance can give the comprehensive comparison between different algorithms, he directly used to assessing MOEAs. he Fig 3.1 The proposed framework Then, in (i.e., approximation front) has two from; remove all the fronts a metric alone. independent trials the proposed opportunities 51 of that algorithm and compare others again. Finally, all the algorithms will be assigned a rank value. Input: A number of MOEAs for comparison Output: Rank Value of the chosen MOEAs Step 1: Generate 50 approximation fronts from each MOEA: The selected MOEAs run 50 times for a given benchmark problem under the same initial conditions. Every time, each MOEA generate an approximation fronts while each front represents its algorithm. After that, a single performance metric in the performance metrics ensemble is randomly chosen to measure the quality of each front, and the best approximation front is picked up based on that performance pertained to the chosen benchmark problem at hand. After 50 running times, we get 50 approximation fronts. Step 2: Use DoubleTournament Selection to get the best one individual: i. Every 2 individuals are randomly picked to form competition pair. One performance metric is randomly chosen in each competition. Each pair will generate a winner and a loser. After all the competition, two parts are created: W1 contains all the winners named winner bracket; the other L1 contains all the losers named loser bracket. ii. In both W1 and L1, the same competition is performed again and each package can be divided into two subpackages. One subpackage contains winners, the other losers. W1 is divided into W11 (winners) and W12 (losers); L1 is divided into L11 (winners) and L12 (losers). Then, individual of W12 will compete with individual of L11 one by one. Winners from these competitions consist of a new loser bracket L13. We reserve W11 and L13.Therefore, the population is reduced to an half. iii. In both W11 and L13, do as Step ii again. Every time, reduce the population by half. Finally, only one individual wins at the very end. Step 3: Assign every MOEA a rank value Identify from which MOEA this winner front comes from. Assign this algorithm rank value 1. Then, eliminate all the approximate fronts generated by this algorithm in the 50 approximate fronts. Go back to step 2 and compare remaining fronts from all MOEA (less the winner with rank 1) again. Finally, we will assign each algorithm a rank value implying its ranking order through the proposed performance metrics ensemble. Table 3.1 The Whole Process of Ensemble Method 3.3 ENSEMBLE METHOD WITH DOUBLETOURNAMENT SELECTION 3.3.1 DoubleTournament Selection 52 The Modified Double Tournament algorithm selects an individual using tournament selection: at the initial step, the tournament contestants are chosen at random from the population. Then, at the following step, they are each the winners of last tournament selection. For example, imagine if the tournament has a pool size of 32: first, the 16 “qualifier” tournaments are held as normal in tournament selection, and the whole pool is divided into two parts: winner bracket contains 16 winners and loser part 16 losers. Then, in each of the part, 8 normal tournament selections are processed so that the part is divided again. In both parts, there are 8 new winners and 8 new losers. Afterward, we compete 8 winners from loser bracket with 8 losers from winner bracket. Here, two individuals come into one tournament selection should be from different part, that means, one individual from winner bracket is compared with one individual from loser bracket. Therefore, we get 8 winners from this step. This process reduces the total number of individuals from 32 to 16. Continue to do it, 16→8→4→2→1, finally, we obtain the ultimate winner. This ultimate winner defeats all other 31 competitors. The motivation for applying DoubleTournament Selection is that it gives every individual two chances to take part in the competition. This advantage is helpful to reserve good individual. Because of the stochastic process, one approximation front from a quality MOEA may lose the competition at time when a metric measuring the very deficient aspect of problem characteristics is applied. If this happens in the single elimination tournament, the front will be lost forever and it would not have any chance to compete again. However, in the DoubleTournament Selection, even it loses once, it has an opportunity to compete again and hopefully win at all. For example, in NCAA basketball tournament, the last year’s champion team will versus the winner of the 64th and 65th team. Of course, the probability that the champion team wins is very large, but basketball game bears a huge number of uncertain factors, there exists probability that the 64th team wins. In this condition, if single elimination is used, the last year’s champion team 53 loses at all. We will not see the excellent performance of this team in the following games of this year. This will be a great loss for audience! In DoubleTournament Selection, the champion team will have another chance to compete in the loser bracket; it can make up its mistake in the last game and win again. Therefore, in MOEAs comparison, if a really good front loses its game at one competition, it has the opportunity to win at another time. Double elimination design allows specific characteristicpoor performance of a quality algorithm under the special environment still to be able to survive through competitions and win it all. 3.3.2 Ensemble Method with DoubleTournament Selection The goal of Ensemble Metrics is that Ensemble Metrics can benefit us for its specific ensemble advantages which accomplish the work that single metric cannot. In the following chapter, we choose five stateoftheart MOEAs to compare and five performance metrics to assess, every algorithm need to run 50 times because of the stochastic nature of MOEAs. In every running time, one algorithm produces one approximation front. Given the same initial population, five fronts from five different algorithms go to competition in a pool under evaluation of a randomly chosen performance metric and one best front wins according to this metric. After 50 running times, 50 winners are generated. Here, maybe many of 50 winners come from the same MOEA or none of 50 winners represents a specific algorithm. In every 50 running time, the probability of each metric to be chosen is 0.2, so the average times each metric to be used is 10. This guarantee every metric to be chosen often and the 50 winners are decided by all five metrics collectively. Then, these 50 winners are taken as the input to DoubleTournament Selection. Here, we just consider 50 fronts as 50 individuals without concerning about its representing algorithm. 54 Process: 1) Every 2 of 50 individuals are randomly picked to form a competition pair. For every competition, one metric is randomly chosen. Then, the total 25 pairs generate 25 winners and 25 losers. Create two parts: one contains 25 winners named winner bracket; the other contains 25 losers named loser bracket. 2) In each of the part, first randomly choose an individual, the remaining 24 individuals form 12 pairs of competitions; every pair uses a randomly chosen metric, too. Therefore, every part has 12 new winners and 12 new losers. Put the first chosen individual into both winners and losers. This will make the number of both winners and losers to be 13. 3) 13 losers in winner bracket and 13 winners in loser bracket (i.e., each individual losss only once) are combined together to compete. Every competition contains one individual from winner bracket and one from loser bracket. Then, 13 winners are generated and consist of a new loser bracket. The other 13 losers and 13 losers in original loser part (i.e. each losses twice) are eliminated. 4) Now, both new winner bracket and new loser bracket contain 13 individuals. We finish this step that reduces the number of competitors from 50 to 26 (i.e., 13 winners + 13 losers). 5) Then continue to do Step 2 and Step 3. We reduce the number of competitors from 26 to 14 (7 winners + 7 losers), then from 14 to 8 (4 winners + 4 losers), then from 8 to 4 (2 winners + 2 losers), then from 4 to 2 (1 winners + 1 losers) and finally from 2 down to 1. The last remaining individual is the final champion. 6) Check which evolutionary algorithm regarding the final winner comes from. Then we can conclude which algorithm is the best. 7) Remove all the fronts come from the best algorithm and compare other fronts from Step 1 to Step 6 again. So we can arrive at the second best one. 8) Continue to do Step 7; finally, we obtain the ranking of all the algorithms. The whole process is end. In this modified Double defeat others under all the performance metrics mechanism for choosing metrics in every competition time. Therefore, the rank of all the algorithms is based on all the metrics Figure 3.2 uses graphs to explain each step Fig 3.2 (a) From 50 individuals to 26 individuals Fig 3.2 (b) From 26 individuals to 14 individuals 55 n DoubleTournament Selection, to be the final winner, the MOEA in double elimination because of stochastic collectively. of DoubleTournament Selection , must Selection: Fig 3.2 (c) From 14 individuals to 8 individuals Fig 3.2 (d) From 8 individuals to 4 56 individuals Fig 3.2 (e) From 4 individuals to 2 individuals Fig 3.2 (f) From 2 individuals to 1 individuals 57 58 CHAPTER 4 FINDINGS 4.1 EXPERIEMENT RESULTS This part will show all experiment results in benchmark functions: ZDT1, ZDT2, ZDT3, ZDT4, ZDT6 and DTLZ2, respectively. 4.1.1 ZDT 1 First, box plot for every performance metric measure is presented: GD Metric For each algorithm, the less the GD value, the better the algorithm’s performance: 4.1(a) GD metric value in ZDT 1 Here, in graph’s x axis, ‘1’ represents SPEA 2, ‘2’ represents NSGAII,’3’represents IBEA, ‘4’ represents PESAII and ‘5’ represents MOEA/D. y axis shows the metric value. 0 0.05 0.1 0.15 0.2 0.25 0.3 1 2 3 4 5 59 Spacing Metric For each algorithm, the less the Spacing value, the better the algorithm’s performance: 4.1(b) Spacing metric value in ZDT 1 Here, in graph’s x axis, ‘1’ represents SPEA 2, ‘2’ represents NSGAII,’3’represents IBEA, ‘4’ represents PESAII and ‘5’ represents MOEA/D. y axis shows the metric value. NR Metric For each algorithm, the more the NR value, the better the algorithm’s performance: 4.1(c) NR metric value in ZDT 1 0 0.05 0.1 0.15 0.2 0.25 1 2 3 4 5 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 1 2 3 4 5 60 Here, in graph’s x axis, ‘1’ represents SPEA 2, ‘2’ represents NSGAII,’3’represents IBEA, ‘4’ represents PESAII and ‘5’ represents MOEA/D. y axis shows the metric value. Smetric For each algorithm, the more the S value, the better the algorithm’s performance 4.1(d) Smetric value in ZDT 1 Here, in graph’s x axis, ‘1’ represents SPEA 2, ‘2’ represents NSGAII,’3’represents IBEA, ‘4’ represents PESAII and ‘5’ represents MOEA/D. y axis shows the metric value. MS Metric For each algorithm, the more the MS value, the better the algorithm’s performance 4.1(e) MS metric value in ZDT 1 0.73 0.74 0.75 0.76 0.77 0.78 0.79 0.8 0.81 0.82 0.83 1 2 3 4 5 0.84 0.86 0.88 0.9 0.92 0.94 0.96 0.98 1 2 3 4 5 61 Here, in graph’s x axis, ‘1’ represents SPEA 2, ‘2’ represents NSGAII,’3’represents IBEA, ‘4’ represents PESAII and ‘5’ represents MOEA/D. y axis shows the metric value. Then, experiment results using ensemble performance metrics in ZDT 1 is given: Step 1 generates 50 fronts as the initial population of DoubleTournament Selection: in these 50 winner fronts, SPEA 2 wins 18 times, NSGAII wins 12 times, IBEA wins 2 times, PESAII wins 4 times and MOEA/D wins 14 times. In this step, metrics are totally chosen 50 times: GD is chosen 17 times, NR is 12 times, Spacing is 8 times, Smetric is 6 times and MS is 7 times. Step 2 is the first step of DoubleTournament Selection that 50 fronts are competed to generate 26 winners: in these 26 winner fronts, SPEA 2 wins 10 times, NSGAII wins 7 times, IBEA wins 0 times, PESAII wins 1 time and MOEA/D wins 8 times. In this step, metrics are totally chosen 62 times in two parts: The total 50 fronts are divided into 2 groups in first 25 times: GD is chosen 4 times, NR is 4 times, Spacing is 6 times, Smetric is 6 times and MS is 5 times. 26 winners are generated from both Winner group and Loser group in 37 times: GD is chosen 7 times, NR is 4 times, Spacing is 8 times, Smetric is 8 times and MS is 10 times. Step 3 is the second step of DoubleTournament Selection that 26 fronts are compared to generate 14 winners: in these 14 winner fronts, SPEA 2 wins 5 times, NSGAII wins 4 times, IBEA wins 0 times, PESAII wins 1 time and MOEA/D wins 4 times. In this step, metrics are totally chosen 19 times: GD is chosen 5 times, NR is 4 times, Spacing is 5 times, Smetric is 2 times and MS is 3 times. In the third step (Step 4) of DoubleTournament Selection that 14 fronts are compared to generate 8 winners: in these 8 winner fronts, SPEA 2 wins 3 times, NSGAII wins 3 times, IBEA wins 1 time, PESAII wins 0 times and MOEA/D wins 1 time. In this step, metrics are totally chosen 10 times: GD is chosen 2 times, NR is 2 times, Spacing is 3 times, Smetric is 2 times and MS is 1 time. 62 Step 5 is the fourth step of DoubleTournament Selection that 8 fronts are compared to generate 4 winners: in these 4 winner fronts, SPEA 2 wins 2 times, NSGAII wins 1 time, IBEA wins 0 times, PESAII wins 0 times and MOEA/D wins 1 time. In this step, metrics are totally chosen 6 times: GD is chosen 0 times, NR is 1 time, Spacing is 1 time, Smetric is 2 times and MS is 2 times. In the fifth step (Step 6) of DoubleTournament Selection that 4 fronts are compared to generate 2 winners: in these 2 winner fronts, SPEA 2 wins 1 time, NSGAII wins 1 times, IBEA wins 0 time, PESAII wins 0 times and MOEA/D wins 0 time. In this step, metrics are totally chosen 3 times: GD is chosen 1 time, NR is 1 time, Spacing is 0 times, Smetric is 0 times and MS is 1 time. In the final step (Step 7) of DoubleTournament Selection that 2 fronts are compared to generate 1 winner. The final winner is SPEA 2 and GD is chosen to compare. In Step 8, remove all the fronts from SPEA 2 in 50 fronts obtained in the first step, continue step 1 to step 7, NSGAII is the second best one and MOEA/D is the third one. After all the remaining fronts come from the same algorithm, we get the final rank value for ZDT 1: Rank 1: SPEA 2; Rank 2: NSGAII; Rank 3: MOEA/D; Rank 4: PESAII; Rank 5: IBEA. 4.1.2 ZDT2 First, box plot for every performance metric measure is presented: GD Metric For each algorithm, the less the GD value, the better the algorithm’s performance: 63 4.2(a) GD metric value in ZDT 2 Here, in graph’s x axis, ‘1’ represents SPEA 2, ‘2’ represents NSGAII,’3’represents IBEA, ‘4’ represents PESAII and ‘5’ represents MOEA/D. y axis shows the metric value. Spacing Metric For each algorithm, the less the Spacing value, the better the algorithm’s performance: 4.2(b) Spacing metric value in ZDT 2 Here, in graph’s x axis, ‘1’ represents SPEA 2, ‘2’ represents NSGAII,’3’represents IBEA, ‘4’ represents PESAII and ‘5’ represents MOEA/D. y axis shows the metric value. NR Metric For each algorithm, the more the NR value, the better the algorithm’s performance: 0 0.05 0.1 0.15 0.2 0.25 1 2 3 4 5 0.05 0.1 0.15 0.2 0.25 1 2 3 4 5 64 4.2(c) NR metric value in ZDT 2 Here, in graph’s x axis, ‘1’ represents SPEA 2, ‘2’ represents NSGAII,’3’represents IBEA, ‘4’ represents PESAII and ‘5’ represents MOEA/D. y axis shows the metric value. Smetric For each algorithm, the more the S value, the better the algorithm’s performance: 4.2(d) Smetric value in ZDT 2 Here, in graph’s x axis, ‘1’ represents SPEA 2, ‘2’ represents NSGAII,’3’represents IBEA, ‘4’ represents PESAII and ‘5’ represents MOEA/D. y axis shows the metric value. MS Metric For each algorithm, the more the MS value, the better the algorithm’s performance: 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 1 2 3 4 5 0.76 0.78 0.8 0.82 0.84 0.86 0.88 0.9 0.92 1 2 3 4 5 65 4.2(e) MS metric value in ZDT 2 Here, in graph’s x axis, ‘1’ represents SPEA 2, ‘2’ represents NSGAII,’3’represents IBEA, ‘4’ represents PESAII and ‘5’ represents MOEA/D. y axis shows the metric value. Then, experiment results using ensemble performance metrics in ZDT 2 is given: Step 1 generates 50 fronts as the initial population of DoubleTournament Selection: in these 50 winner fronts, SPEA 2 wins 13 times, NSGAII wins 11 times, IBEA wins 8 times, PESAII wins 5 times and MOEA/D wins 13 times. In this step, metrics are totally chosen 50 times: GD is chosen 9 times, NR is 11 times, Spacing is 10 times, Smetric is 11 times and MS is 9 times. Step 2 is the first step of DoubleTournament Selection that 50 fronts are competed to generate 26 winners: in these 26 winner fronts, SPEA 2 wins 7 times, NSGAII wins 6 times, IBEA wins 3 times, PESAII wins 3 times and MOEA/D wins 7 times. In this step, metrics are totally chosen 62 times in two parts: The total 50 fronts are divided into 2 groups in first 25 times: GD is chosen 6 times, NR is 3 times, Spacing is 4 times, Smetric is 7 times and MS is 5 times. 26 winners are generated from both Winner group and Loser group in 37 times: GD is chosen 9 times, NR is 5 times, Spacing is 6 times, Smetric is 8 times and MS is 9 times. Step 3 is the second step of DoubleTournament Selection that 26 fronts are compared to generate 14 winners: in these 14 winner fronts, SPEA 2 wins 5 times, NSGAII wins 2 times, 0.88 0.89 0.9 0.91 0.92 0.93 0.94 0.95 0.96 0.97 1 2 3 4 5 66 IBEA wins 1 time, PESAII wins 2 times and MOEA/D wins 4 times. In this step, metrics are totally chosen 19 times: GD is chosen 7 times, NR is 4 times, Spacing is 5 times, Smetric is 2 times and MS is 1 time. In the third step (Step 4) of DoubleTournament Selection that 14 fronts are compared to generate 8 winners: in these 8 winner fronts, SPEA 2 wins 2 times, NSGAII wins 1 time, IBEA wins 1 time, PESAII wins 1 time and MOEA/D wins 3 times. In this step, metrics are totally chosen 10 times: GD is chosen 1 time, NR is 3 times, Spacing is 2 times, Smetric is 2 times and MS is 2 times. Step 5 is the fourth step of DoubleTournament Selection that 8 fronts are compared to generate 4 winners: in these 4 winner fronts, SPEA 2 wins 2 times, NSGAII wins 1 times, IBEA wins 0 times, PESAII wins 0 times and MOEA/D wins 1 times. In this step, metrics are totally chosen 6 times: GD is chosen 1 time, NR is 1 time, Spacing is 2 times, Smetric is 2 times and MS is 0 times. In the fifth step (Step 6) of DoubleTournament Selection that 4 fronts are compared to generate 2 winners: in these 2 winner fronts, SPEA 2 wins 1 time and MOEA/D wins 1 time. In this step, metrics are totally chosen 3 times: GD is chosen 0 time, NR is 0 time, Spacing is 1 time, Smetric is 1 time and MS is 1 time. In the final step (Step 7) of DoubleTournament Selection that 2 fronts are compared to generate 1 winner. The final winner is SPEA 2 and NR is chosen to compare. In Step 8, remove all the fronts from SPEA 2 in 50 fronts obtained in the first step, continue step 1 to step 7, NSGAII is the second best one and MOEA/D is the third one. After all the remaining fronts come from the same algorithm, we get the final rank value for ZDT 2: Rank 1: SPEA 2; Rank 2: NSGAII; Rank 3: MOEA/D; Rank 4: IBEA; Rank 5: PESAII. 67 4.1.3 ZDT 3 First, box plot for every performance metric measure is presented: GD Metric For each algorithm, the less the GD value, the better the algorithm’s performance: 4.3(a) GD metric value in ZDT 3 Here, in graph’s x axis, ‘1’ represents SPEA 2, ‘2’ represents NSGAII,’3’represents IBEA, ‘4’ represents PESAII and ‘5’ represents MOEA/D. y axis shows the metric value. Spacing Metric For each algorithm, the less the Spacing value, the better the algorithm’s performance: 0.04 0.06 0.08 0.1 0.12 0.14 0.16 0.18 0.2 0.22 1 2 3 4 5 0.1 0.15 0.2 0.25 1 2 3 4 5 68 4.3(b) Spacing metric value in ZDT 3 Here, in graph’s x axis, ‘1’ represents SPEA 2, ‘2’ represents NSGAII,’3’represents IBEA, ‘4’ represents PESAII and ‘5’ represents MOEA/D. y axis shows the metric value. NR Metric For each algorithm, the more the NR value, the better the algorithm’s performance: 4.3(c) NR metric value in ZDT 3 Here, in graph’s x axis, ‘1’ represents SPEA 2, ‘2’ represents NSGAII,’3’represents IBEA, ‘4’ represents PESAII and ‘5’ represents MOEA/D. y axis shows the metric value. Smetric For each algorithm, the more the S value, the better the algorithm’s performance: 0.05 0.1 0.15 0.2 0.25 0.3 0.35 1 2 3 4 5 0.87 0.88 0.89 0.9 0.91 0.92 0.93 0.94 0.95 0.96 1 2 3 4 5 69 4.3(d) Smetric value in ZDT 3 Here, in graph’s x axis, ‘1’ represents SPEA 2, ‘2’ represents NSGAII,’3’represents IBEA, ‘4’ represents PESAII and ‘5’ represents MOEA/D. y axis shows the metric value. MS Metric For each algorithm, the more the MS value, the better the algorithm’s performance: 4.3(e) MS metric value in ZDT 3 Here, in graph’s x axis, ‘1’ represents SPEA 2, ‘2’ represents NSGAII,’3’represents IBEA, ‘4’ represents PESAII and ‘5’ represents MOEA/D. y axis shows the metric value. Then, experiment results using ensemble performance metrics in ZDT 3 is given: Step 1 generates 50 fronts as the initial population of DoubleTournament Selection: in these 50 winner fronts, SPEA 2 wins 11 times, NSGAII wins 12 times, IBEA wins 9 times, PESAII wins 7 times and MOEA/D wins 11 times. In this step, metrics are totally chosen 50 times: GD is chosen 10 times, NR is 13 times, Spacing is 7 times, Smetric is 12 times and MS is 8 times. Step 2 is the first step of DoubleTournament Selection that 50 fronts are competed to generate 26 winners: in these 26 winner fronts, SPEA 2 wins 6 times, NSGAII wins 6 times, IBEA wins 5 times, PESAII wins 3 times and MOEA/D wins 6 times. In this step, metrics are 0.86 0.88 0.9 0.92 0.94 0.96 0.98 1 2 3 4 5 70 totally chosen 62 times in two parts: the total 50 fronts are divided into 2 groups in first 25 times: GD is chosen 4 times, NR is 5 times, Spacing is 4 times, Smetric is 5 times and MS is 7 times. 26 winners are generated from both Winner group and Loser group in 37 times: GD is chosen 7 times, NR is 6 times, Spacing is 7 times, Smetric is 10 times and MS is 7 times. Step 3 is the second step of DoubleTournament Selection that 26 fronts are compared to generate 14 winners: in these 14 winner fronts, SPEA 2 wins 2 times, NSGAII wins 4 times, IBEA wins 3 times, PESAII wins 2 times and MOEA/D wins 3 times. In this step, metrics are totally chosen 19 times: GD is chosen 4 times, NR is 5 times, Spacing is 3 times, Smetric is 4 times and MS is 3 times. In the third step (Step 4) of DoubleTournament Selection that 14 fronts are compared to generate 8 winners: in these 8 winner fronts, SPEA 2 wins 1 time, NSGAII wins 3 times, IBEA wins 1 time, PESAII wins 1 time and MOEA/D wins 2 times. In this step, metrics are totally chosen 10 times: GD is chosen 2 times, NR is 2 times, Spacing is 3 times, Smetric is 1 time and MS is 2 times. Step 5 is the fourth step of DoubleTournament Selection that 8 fronts are compared to generate 4 winners: in these 4 winner fronts, SPEA 2 wins 0 times, NSGAII wins 2 times, IBEA wins 0 times, PESAII wins 0 times and MOEA/D wins 2 times. In this step, metrics are totally chosen 6 times: GD is chosen 2 times, NR is 0 time, Spacing is 0 times, Smetric is 2 times and MS is 2 times. In the fifth step (Step 6) of DoubleTournament Selection that 4 fronts are compared to generate 2 winners: in these 2 winner fronts, NSGAII wins 2 times. In this step, metrics are totally chosen 3 times: GD is chosen 1 time, NR is 2 times, Spacing is 0 time, Smetric is 0 time and MS is 0 time. 71 In the final step (Step 7) of DoubleTournament Selection that 2 fronts are compared to generate 1 winner. The final winner is NSGAII and Smetric is chosen to compare. In the Step 8, remove all the fronts from NSGAII in 50 fronts obtained in the first step, continue step 1 to step 7, MOEA/D is the second best one and IBEA is the third one. After all the remaining fronts come from the same algorithm, we get the final rank value for ZDT 3: Rank 1: NSGAII; Rank 2: MOEA/D; Rank 3: IBEA; Rank 4: SPEA 2; Rank 5: PESAII. 4.1.4 ZDT 4 First, box plot for every performance metric measure is presented: GD Metric For each algorithm, the less the GD value, the better the algorithm’s performance: 4.4(a) GD metric value in ZDT 4 Here, in graph’s x axis, ‘1’ represents SPEA 2, ‘2’ represents NSGAII,’3’represents IBEA, ‘4’ represents PESAII and ‘5’ represents MOEA/D. y axis shows the metric value. Spacing Metric For each algorithm, the less the Spacing value, the better the algorithm’s performance: 0.05 0.1 0.15 0.2 0.25 0.3 0.35 0.4 1 2 3 4 5 72 4.4(b) Spacing metric value in ZDT 4 Here, in graph’s x axis, ‘1’ represents SPEA 2, ‘2’ represents NSGAII,’3’represents IBEA, ‘4’ represents PESAII and ‘5’ represents MOEA/D. y axis shows the metric value. NR Metric For each algorithm, the more the NR value, the better the algorithm’s performance: 4.4(c) NR metric value in ZDT 4 Here, in graph’s x axis, ‘1’ represents SPEA 2, ‘2’ represents NSGAII,’3’represents IBEA, ‘4’ represents PESAII and ‘5’ represents MOEA/D. y axis shows the metric value. Smetric 0.05 0.1 0.15 0.2 0.25 0.3 1 2 3 4 5 0.05 0.1 0.15 0.2 0.25 0.3 0.35 1 2 3 4 5 73 For each algorithm, the more the S value, the better the algorithm’s performance: 4.4(d) S metric value in ZDT 4 Here, in graph’s x axis, ‘1’ represents SPEA 2, ‘2’ represents NSGAII,’3’represents IBEA, ‘4’ represents PESAII and ‘5’ represents MOEA/D. y axis shows the metric value. MS Metric For each algorithm, the more the MS value, the better the algorithm’s performance: 4.4(e) MS metric value in ZDT 4 Here, in graph’s x axis, ‘1’ represents SPEA 2, ‘2’ represents NSGAII,’3’represents IBEA, ‘4’ represents PESAII and ‘5’ represents MOEA/D. y axis shows the metric value. 0.75 0.8 0.85 0.9 0.95 1 2 3 4 5 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 1 2 3 4 5 74 Then, experiment results using ensemble performance metrics in ZDT 4 is given: Step 1 generates 50 fronts as the initial population of DoubleTournament Selection: in these 50 winner fronts, SPEA 2 wins 0 times, NSGAII wins 15 times, IBEA wins 9 times, PESAII wins 9 times and MOEA/D wins 17 times. In this step, metrics are totally chosen 50 times: GD is chosen 9 times, NR is 15 times, Spacing is 7 times, Smetric is 12 times and MS is 7 times. Step 2 is the first step of DoubleTournament Selection that 50 fronts are competed to generate 26 winners: in these 26 winner fronts, SPEA 2 wins 0 times, NSGAII wins 9 times, IBEA wins 5 times, PESAII wins 5 times and MOEA/D wins 7 times. In this step, metrics are totally chosen 62 times in two parts: the total 50 fronts are divided into 2 groups in first 25 times: GD is chosen 6 times, NR is 4 times, Spacing is 4 times, Smetric is 5 times and MS is 6 times. 26 winners are generated from both Winner group and Loser group in 37 times: GD is chosen 5 times, NR is 7 times, Spacing is 9 times, Smetric is 5 times and MS is 11 times. Step 3 is the second step of DoubleTournament Selection that 26 fronts are compared to generate 14 winners: in these 14 winner fronts, SPEA 2 wins 0 times, NSGAII wins 5 times, IBEA wins 3 times, PESAII wins 2 times and MOEA/D wins 4 times In this step, metrics are totally chosen 19 times: GD is chosen 5 times, NR is 6 times, Spacing is 3 times, Smetric is 4 times and MS is 1 time. In the third step (Step 4) of DoubleTournament Selection that 14 fronts are compared to generate 8 winners: in these 8 winner fronts, SPEA 2 wins 0 time, NSGAII wins 3 times, IBEA wins 1 time, PESAII wins 1 time and MOEA/D wins 3 times. In this step, metrics are totally chosen 10 times: GD is chosen 3 times, NR is 1 time, Spacing is 2 times, Smetric is 2 times and MS is 2 times. Step 5 is the fourth step of DoubleTournament Selection that 8 fronts are compared to generate 4 winners: in these 4 winner fronts, SPEA 2 wins 0 times, NSGAII wins 2 times, IBEA 75 wins 1 time, PESAII wins 0 times and MOEA/D wins 1 time. In this step, metrics are totally chosen 6 times: GD is chosen 1 time, NR is 0 time, Spacing is 1 time, Smetric is 2 times and MS is 2 times. In the fifth step (Step 6) of DoubleTournament Selection that 4 fronts are compared to generate 2 winners: in these 2 winner fronts, NSGAII wins 1 time and MOEA/D wins 1 time. In this step, metrics are totally chosen 3 times: GD is chosen 1 time, NR is 0 times, Spacing is 1 time, Smetric is 0 time and MS is 1 time. In the final step (Step 7) of DoubleTournament Selection that 2 fronts are compared to generate 1 winner. The final winner is MOEA/D and GD is chosen to compare. This result is the same as [14]. In the Step 8, remove all the fronts from MOEA/D in 50 fronts obtained in the first step, continue step 1 to step 7, NSGAII is the second best one and PESAII is the third one. After all the remaining fronts come from the same algorithm, we get the final rank value for ZDT 4: Rank 1: MOEA/D; Rank 2: NSGAII; Rank 3: PESAII; Rank 4: IBEA; Rank 5: SPEA 2. 4.1.5 ZDT 6 First, box plot for every performance metric measure is presented: GD Metric For each algorithm, the less the GD value, the better the algorithm’s performance: 76 4.5(a) GD metric value in ZDT 6 Here, in graph’s x axis, ‘1’ represents SPEA 2, ‘2’ represents NSGAII,’3’represents IBEA, ‘4’ represents PESAII and ‘5’ represents MOEA/D. y axis shows the metric value. Spacing Metric For each algorithm, the less the Spacing value, the better the algorithm’s performance: 4.5(b) Spacing metric value in ZDT 6 Here, in graph’s x axis, ‘1’ represents SPEA 2, ‘2’ represents NSGAII,’3’represents IBEA, ‘4’ represents PESAII and ‘5’ represents MOEA/D. y axis shows the metric value. NR Metric For each algorithm, the more the NR value, the better the algorithm’s performance: 0.05 0.1 0.15 1 2 3 4 5 0.06 0.07 0.08 0.09 0.1 0.11 0.12 0.13 0.14 0.15 1 2 3 4 5 77 4.5(c) NR metric value in ZDT 6 Here, in graph’s x axis, ‘1’ represents SPEA 2, ‘2’ represents NSGAII,’3’represents IBEA, ‘4’ represents PESAII and ‘5’ represents MOEA/D. y axis shows the metric value. Smetric For each algorithm, the more the S value, the better the algorithm’s performance: 4.5(d) S metric value in ZDT 6 Here, in graph’s x axis, ‘1’ represents SPEA 2, ‘2’ represents NSGAII,’3’represents IBEA, ‘4’ represents PESAII and ‘5’ represents MOEA/D. y axis shows the metric value. MS Metric 0.1 0.15 0.2 0.25 0.3 1 2 3 4 5 0.86 0.88 0.9 0.92 0.94 0.96 1 2 3 4 5 78 For each algorithm, the more the MS value, the better the algorithm’s performance: 4.5(e) MS metric value in ZDT 6 Here, in graph’s x axis, ‘1’ represents SPEA 2, ‘2’ represents NSGAII,’3’represents IBEA, ‘4’ represents PESAII and ‘5’ represents MOEA/D. y axis shows the metric value. Then, experiment results using ensemble performance metrics in ZDT 6 is given: Step 1 generates 50 fronts as the initial population of DoubleTournament Selection: in these 50 winner fronts, SPEA 2 wins 8 times, NSGAII wins 11 times, IBEA wins 13 times, PESAII wins 6 times and MOEA/D wins 12 times. In this step, metrics are totally chosen 50 times: GD is chosen 11 times, NR is 12 times, Spacing is 9 times, Smetric is 12 times and MS is 6 times. Step 2 is the first step of DoubleTournament Selection that 50 fronts are competed to generate 26 winners: in these 26 winner fronts, SPEA 2 wins 5 times, NSGAII wins 5 times, IBEA wins 7 times, PESAII wins 2 times and MOEA/D wins 7 times. In this step, metrics are totally chosen 62 times in two parts: the total 50 fronts are divided into 2 groups in first 25 times: GD is chosen 5 times, NR is 7 times, Spacing is 4 times, Smetric is 4 times and MS is 5 times. 26 winners are generated from both Winner group and Loser group in 37 times: GD is chosen 6 times, NR is 5 times, Spacing is 8 times, Smetric is 9 times and MS is 9 times. 0.87 0.88 0.89 0.9 0.91 0.92 0.93 0.94 0.95 0.96 1 2 3 4 5 79 Step 3 is the second step of DoubleTournament Selection that 26 fronts are compared to generate 14 winners: in these 14 winner fronts, SPEA 2 wins 2 times, NSGAII wins 3 times, IBEA wins 4 times, PESAII wins 1 time and MOEA/D wins 4 times. In this step, metrics are totally chosen 19 times: GD is chosen 6 times, NR is 5 times, Spacing is 2 times, Smetric is 4 times and MS is 2 times. In the third step (Step 4) of DoubleTournament Selection that 14 fronts are compared to generate 8 winners: in these 8 winner fronts, SPEA 2 wins 0 time, NSGAII wins 2 times, IBEA wins 3 times, PESAII wins 0 time and MOEA/D wins 3 times. In this step, metrics are totally chosen 10 times: GD is chosen 2 times, NR is 1 time, Spacing is 1 time, Smetric is 2 times and MS is 4 times. Step 5 is the fourth step of DoubleTournament Selection that 8 fronts are compared to generate 4 winners: in these 4 winner fronts, SPEA 2 wins 0 times, NSGAII wins 0 times, IBEA wins 2 times, PESAII wins 0 times and MOEA/D wins 2 times. In this step, metrics are totally chosen 6 times: GD is chosen 3 times, NR is 0 time, Spacing is 1 time, Smetric is 1 time and MS is 1 time. In the fifth step (Step 6) of DoubleTournament Selection that 4 fronts are compared to generate 2 winners: in these 2 winner fronts, IBEA wins 1 time and MOEA/D wins 1 time. In this step, metrics are totally chosen 3 times: GD is chosen 0 time, NR is 0 times, Spacing is 0 time, Smetric is 2 time and MS is 1 time. In the final step (Step 7) of DoubleTournament Selection that 2 fronts are compared to generate 1 winner. The final winner is MOEA/D and Spacing is chosen to compare. In the Step 8, remove all the fronts from MOEA/D in 50 fronts obtained in the first step, continue step 1 to step 7, IBEA is the second best one and NSGAII is the third one. After all the remaining fronts come from the same algorithm, we get the final rank value for ZDT 6: 80 Rank 1: MOEA/D; Rank 2: IBEA; Rank 3: NSGAII; Rank 4: SPEA 2; Rank 5: PESAII. 4.1.6 DTLZ 2 First, box plot for every performance metric measure is presented: GD Metric For each algorithm, the less the GD value, the better the algorithm’s performance: 4.6(a) GD metric value in DTLZ 2 Here, in graph’s x axis, ‘1’ represents SPEA 2, ‘2’ represents NSGAII,’3’represents IBEA, ‘4’ represents PESAII and ‘5’ represents MOEA/D. y axis shows the metric value. Spacing Metric For each algorithm, the less the Spacing value, the better the algorithm’s performance: 0.04 0.06 0.08 0.1 0.12 0.14 0.16 0.18 1 2 3 4 5 81 4.6(b) Spacing metric value in DTLZ 2 Here, in graph’s x axis, ‘1’ represents SPEA 2, ‘2’ represents NSGAII,’3’represents IBEA, ‘4’ represents PESAII and ‘5’ represents MOEA/D. y axis shows the metric value. NR Metric For each algorithm, the more the NR value, the better the algorithm’s performance: 4.6(c) NR metric value in DTLZ 2 Here, in graph’s x axis, ‘1’ represents SPEA 2, ‘2’ represents NSGAII,’3’represents IBEA, ‘4’ represents PESAII and ‘5’ represents MOEA/D. y axis shows the metric value. Smetric 0.07 0.08 0.09 0.1 0.11 0.12 0.13 0.14 0.15 0.16 0.17 1 2 3 4 5 0.05 0.1 0.15 0.2 0.25 0.3 0.35 1 2 3 4 5 82 For each algorithm, the more the S value, the better the algorithm’s performance: 4.6(d) Smetric value in DTLZ 2 Here, in graph’s x axis, ‘1’ represents SPEA 2, ‘2’ represents NSGAII,’3’represents IBEA, ‘4’ represents PESAII and ‘5’ represents MOEA/D. y axis shows the metric value. MS Metric For each algorithm, the more the MS value, the better the algorithm’s performance: 4.6(e) MS metric value in DTLZ 2 Here, in graph’s x axis, ‘1’ represents SPEA 2, ‘2’ represents NSGAII,’3’represents IBEA, ‘4’ represents PESAII and ‘5’ represents MOEA/D. y axis shows the metric value. 0.86 0.88 0.9 0.92 0.94 0.96 1 2 3 4 5 0.88 0.9 0.92 0.94 0.96 0.98 1 2 3 4 5 83 Then, experiment results using ensemble performance metrics in ZDT 6 is given: Step 1 generates 50 fronts as the initial population of DoubleTournament Selection: in these 50 winner fronts, SPEA 2 wins 11 times, NSGAII wins 8 times, IBEA wins 13 times, PESAII wins 6 times and MOEA/D wins 12 times. In this step, metrics are totally chosen 50 times: GD is chosen 7 times, NR is 15 times, Spacing is 9 times, Smetric is 11 times and MS is 8 times. Step 2 is the first step of DoubleTournament Selection that 50 fronts are competed to generate 26 winners: in these 26 winner fronts, SPEA 2 wins 5 times, NSGAII wins 5 times, IBEA wins 7 times, PESAII wins 2 times and MOEA/D wins 7 times. In this step, metrics are totally chosen 62 times in two parts: the total 50 fronts are divided into 2 groups in first 25 times: GD is chosen 6 times, NR is 4 times, Spacing is 7 times, Smetric is 3 times and MS is 5 times. 26 winners are generated from both Winner group and Loser group in 37 times: GD is chosen 6 times, NR is 6 times, Spacing is 7 times, Smetric is 10 times and MS is 8 times. Step 3 is the second step of DoubleTournament Selection that 26 fronts are compared to generate 14 winners: in these 14 winner fronts, SPEA 2 wins 2 times, NSGAII wins 0 times, IBEA wins 6 times, PESAII wins 1 time and MOEA/D wins 5 times. In this step, metrics are totally chosen 19 times: GD is chosen 2 times, NR is 2 times, Spacing is 5 times, Smetric is 4 times and MS is 6 times. In the third step (Step 4) of DoubleTournament Selection that 14 fronts are compared to generate 8 winners: in these 8 winner fronts, SPEA 2 wins 1 time, NSGAII wins 1 time, IBEA wins 3 times, PESAII wins 0 time and MOEA/D wins 3 times. In this step, metrics are totally chosen 10 times: GD is chosen 3 times, NR is 2 times, Spacing is 1 time, Smetric is 2 times and MS is 2 times. Step 5 is the fourth step of DoubleTournament Selection that 8 fronts are compared to generate 4 winners: in these 4 winner fronts, SPEA 2 wins 0 times, NSGAII wins 0 times, IBEA wins 2 time, PESAII wins 0 times and MOEA/D wins 2 times. In this step, metrics are totally 84 chosen 6 times: GD is chosen 2 times, NR is 1 time, Spacing is 1 time, Smetric is 1 time and MS is 1 time. In the fifth step (Step 6) of DoubleTournament Selection that 4 fronts are compared to generate 2 winners: in these 2 winner fronts, IBEA wins 1 time and MOEA/D wins 1 time. In this step, metrics are totally chosen 3 times: GD is chosen 1 time, NR is 0 times, Spacing is 1 time, Smetric is 0 time and MS is 1 time. In the final step (Step 7) of DoubleTournament Selection that 2 fronts are compared to generate 1 winner. The final winner is IBEA and MS is chosen to compare. In the Step 8, remove all the fronts from IBEA in 50 fronts obtained in the first step, continue step 1 to step 7, MOEA/D is the second best one and SPEA 2 is the third one. After all the remaining fronts come from the same algorithm, we get the final rank value for DTLZ 2: Rank 1: IBEA; Rank 2: MOEA/D; Rank 3: SPEA 2; Rank 4: NSGAII; Rank 5: PESAII. 4.2 ANALYSIS OF EXPERIMENT RESULTS 4.2.1 Ensemble Performance Metrics give the same rank values to exist papers In ZDT3, the final rank result is: Rank 1: NSGAII; Rank 2: MOEA/D; Rank 3: IBEA; Rank 4: SPEA 2; Rank 5: PESAII. The experiment result in [14] has also suggested that MOEA/D generate a worse result than NSGAII. In ZDT6, the final rank result is: Rank 1: MOEA/D; Rank 2: IBEA; Rank 3: NSGAII; Rank 4: SPEA 2; Rank 5: PESAII. [12] shows IBEA performs better than NSGAII and SPEA 2 in ZDT 6. [14] gives the same result that MOEA/D is better than NSGAII in ZDT 6. In DTLZ 2, the final rank result is: Rank 1: IBEA; Rank 2: MOEA/D; Rank 3: SPEA 2; Rank 4: NSGAII; Rank 5: PESAII. This result is nearly the same as previous experiment: [10] 85 has suggested that SPEA 2 seems to have advantages over NSGAII in higher dimensional objective space. In [12], IBEA is also better than SPEA 2 and NSGAII. The experiment result in [14] has also identified that MOEA/D generate a better result than NSGAII. 4.2.2 Summary of EAs to Solve Different Characteristics of Test Functions SPEA 2 SPEA 2 is the final winner in problem ZDT 1 and ZDT 2. Although ZDT 1 has a convex Paretooptimal front while ZDT 2 has the nonconvex counterpart to ZDT1, Both ZDT1 and ZDT2 have some common characteristics: they do not have local Paretooptimal fronts and their global Paretooptimal fronts are continuous. From the above reason, we can state that, if the test problem has continues global Paretooptimal fronts and do not have local Paretooptimal fronts, SPEA 2 will perform well in this problem. NSGAII NSGAII has the best performance in ZDT 3, which represents the discreteness feature and has a Paretooptimal front consisting of several noncontiguous convex parts. Therefore, if there is a test problem with discrete Paretooptimal front, we can propose that NSGAII is the best algorithm to solve this problem. MOEA/D MOEA/D wins all other algorithms in both ZDT4 and ZDT6. ZDT4 is difficult to solve because it has many local Paretooptimal fronts, a large number of local Paretooptimal fronts make the global Pareto front is not easy to find and EAs need to exhibit their ability to deal with multimodality. ZDT6’s Paretooptimal solutions are nonuniformly distributed along the global Pareto front. The front is biased for solutions which have a large f1(x) value. Therefore, MOEA/D will exhibit its good performance when encounters the test problem 86 which has lots of local Paretooptimal fronts or Paretooptimal solutions is not uniformly distributed its global Pareto front. IBEA IBEA wins at all in DTLZ 2, which is the only test problem chosen in this experiment has more than two objectives. We may not absolutely say that IBEA is best for solve problems with highdimension objectives. But we can make a comparatively conclusion that IBEA can perform better than others in some test problems with highdimension objectives. In summary, from the above discussion, we can see more clearly that every algorithm can only be superior to another algorithm over some set of test problems, and then it must be inferior in other problems with different characteristics. This is also expected by No Free Lunch Theory. 4.3 WHY USE DOUBLEELIMINATION METHOD TO ENSEMBLE First, we go through experiments in all benchmark functions considering the performance metrics’ values of every algorithm in this benchmark function. In ZDT1, SPEA 2 is the final winner and it wins under all four metrics but is inferior to NSGAII in Smetric. In ZDT2, SPEA 2 is the final winner and it wins under all four metrics but it is a little bit worse than NSGAII in Spacing metric. In ZDT3, NSGAII is the final winner and it wins under all four metrics but is inferior to MOEA/D in Smetric. In ZDT4, MOEA/D is the final winner and it wins under all four metrics but it is a little bit worse than NSGAII in NR metric. In ZDT6, MOEA/D is the final winner but is inferior to IBEA in MS metric and a little bit worse than NSGAII in Spacing metric. In DTLZ 2, IBEA is the final winner and it wins under all four metrics but is inferior to MOEA/D in Spacing metric. From above results, to be a final winner does not mean win others in all performance metrics. In ZDT1, if we use Smetric to compare SPEA 2 and NSGAII in SingleElimination, SPEA 2 87 will be lost and we cannot find the best algorithm for this problem. However, if that condition happens in DoubleElimination, SPEA 2 also has another opportunity to win again. Therefore, DoubleElimination can provide one more chance for every competitor, this helps to find the best one winner. 88 CHAPTER 5 CONCLUSION . There are five types of unary metrics: 1) Metrics assessing the number of Pareto optimal solutions in the set: Pareto Dominance Indicator (NR), Overall Nondominated Vector Generation and Ratio (ONVG), Ratio of Nondominated Individuals (RNI) and Error Ratio (ER). 2) Metrics measuring the closeness of the solution to the theoretical Pareto front: Generational Distance (GD) and Maximum Pareto Front Error (MPFE). 3) Metrics focusing on distribution of the solutions: Uniform Distribution (UD), Spacing and Number of Distinct Choices (NDCu). 4) Metrics concerning spread of the solutions: Maximum Spread (MS). 5) Metrics considering both closeness and diversity: Hypervolume Indicator (or Smetric). There are two types of binary metrics: 1) binary performance metrics based on unary quality indicator: ε indicator Iε , enclosing hypercube Indicator and coverage difference metrics (Dmetric). The second type is direct comparison binary metrics: C metrics and R metrics. An ensemble method is introduced to compare EAs by combining a large number of single metrics using modified Double Tournament Selection. Double elimination design give every individual two chances to competition allows characteristic poor performance of a quality algorithm under the special environment still to be able to win at all. Therefore, this ensemble mechanism can maximum protects the qualified individual from being lost by some stochastic factors in a comparison time. This ensures the final result is the really best one and the whole ensemble process is effective and precise. Ensemble method can overcome the lost information problem by the single metric which on 89 ly provides some specific but limited information and is only used effectively in some specified conditions. The Comprehensive comparison of the proposed algorithms on benchmark test functions under ensemble performance metrics show that: SPEA 2 performs well in the problem has continues global Paretooptimal fronts and do not have local Paretooptimal fronts. NSGAII is the best algorithm to solve this problem with discrete Paretooptimal front. MOEA/D will exhibit its good performance when encounters the test problem which has lots of local Paretooptimal fronts or Paretooptimal solutions is not uniformly distributed its global Pareto front. IBEA can perform better than others in some test problems with highdimension objectives. Furthermore, we are benefit from ensemble method that it is not necessary to spend much time to choose a suitable performance metric for a specific test problem. We do not need to try every metric to find which on 



A 

B 

C 

D 

E 

F 

I 

J 

K 

L 

O 

P 

R 

S 

T 

U 

V 

W 


