Analysis of the distribution of pareto optimal solutions on various multi-objective evolutionary algorithms

Analysis of the Distribution of Pareto Optimal Solutions on various Multi-Objective Evolutionary Algorithms Guido Arnau Antoniucci BSc Computer Science Submission Date: May 18, 2016 Supervisor: Dr. Peter J. Bentley Department of Computer Science University College London This report is submitted as part requirement for the BSc Degree in Computer Science at UCL. It is substantially the result of my own work except where explicitly indicated in the text. The report may be freely copied and distributed provided the source is explicitly acknowledged. Abstract Multi-Objective Evolutionary Algorithms (MOEA) find multiple equally optimal solutions that minimise two or more objective functions at the same time through the usage of evolutionary strategies. The performance of MOEA is evaluated according to the convergence to the optimal solution set of the problem and the assemblage of a diverse collection of solutions. While the convergence rate of MOEA is often compared, comparisons of the diversity of the found solutions set is often overlooked. This project compares the quality of the distributions of solutions produced by various popular and novel MOEA. Additionally, biases that MOEA might have are also identified. Before performing the comparisons, a series of tests are conducted in order to verify the capacity of two standard diversity metrics to accurately measure the diversity of a solution set. The Spread metric is found to convey more information about the distribution of solutions than the Spacing metric and thus, produce a better estimation of the quality. SPEA2, SMPSO, GDE3, AbYSS are found to produce uniform and spread distributions on the tested problems. On the other hand, widely used MOEA such as NSGA-II, -MOEA, IBEA or CMA-ES are found to produce worse distributions than the previously stated algorithms. Contents 1 Introduction 5 1.1 ReportStructure............................ 6 2 Background 8 2.1 Multi-Objective Optimisation . . . . . . . . . . . . . . . . . . . . . 8 2.1.1 Multi-Objective Problem . . . . . . . . . . . . . . . . . . . 9 2.2 ParetoTerminology.......................... 10 2.3 Multi-Objective Evolutionary Algorithms . . . . . . . . . . . . . . 12 2.3.1 Diversity in Multi-Objective Optimisation . . . . . . . . . . 13 2.3.2 Structures of the Tested MOEAs . . . . . . . . . . . . . . . 14 2.4 PreviousResearch........................... 22 3 Methodology 23 3.1 MOEAFramework .......................... 23 3.2 MOPSelection ............................ 24 3.3 MetricSelection............................ 26 3.3.1 Available Diversity Metrics . . . . . . . . . . . . . . . . . 29 3.3.2 Diversity Metric Evaluation . . . . . . . . . . . . . . . . . 32 4 Experiments 39 4.1 Collected Metrics and Data . . . . . . . . . . . . . . . . . . . . . . 39 4.1.1 MOEA Parametrisation . . . . . . . . . . . . . . . . . . . . 41 4.1.2 MOP Parametrisation . . . . . . . . . . . . . . . . . . . . . 41 4.1.3 Experimental Set-up . . . . . . . . . . . . . . . . . . . . . 42 Contents 4 4.2 Difficulties Selecting MOEA . . . . . . . . . . . . . . . . . . . . . 42 4.3 Results................................. 43 4.4 Analysis................................ 44 5 Conclusions 64 5.1 FutureWork.............................. 67 Appendices 69 A Appendices 69 A.1 UserManual.............................. 69 A.1.1 MOEAFramework/ ...................... 69 A.1.2 Comparisons/ ........................ 70 A.2 MOEA Default Parametrisation . . . . . . . . . . . . . . . . . . . . 73 A.3 TunedParameters........................... 73 A.4 CodeListings ............................. 73 A.4.1 SpreadMetric......................... 73 A.4.2 Parameter tuning for NSGA-II . . . . . . . . . . . . . . . . 80 A.4.3 Comparison of MOEA . . . . . . . . . . . . . . . . . . . . 82 A.5 ProjectPlan.............................. 89 A.6 InterimReport............................. 92 Bibliography 95 Chapter 1 Introduction Single-Objective Optimisation refers to finding an optimal solution to an objective function, while Multi-Objective Optimisation finds solutions to two or more objectives at the same time. The objectives are usually at conflict, meaning that optimising one of them might worsen another one. This results in many optimal solutions which present different trade-offs between the objectives. Evolutionary Algorithms (EA) are ideal candidates to solve Multi-Objective Problems (MOP) as they work with multiple solutions at the same time throughout their execution (also referred to as population). EA adapted to solve MultiObjective Problems (MOP) are referred to as Multi-Objective Evolutionary Algorithms (MOEA). How good a MOEA performs when solving a MOP will be judged by the following criteria: •Convergence. In other words, how close the found set of solutions is to the true set of optimal solutions. •MOP’s optimal solution sets are usually uncountable, but EAs can only maintain a finite sized population. The Diversity of the solution set will refer to as how well the solutions are evenly spread out in reference to the true optimal solution set. Having solutions that are clumped in an area of the true optimal solution set hides other potential solutions and thus, does not give a good solution to the MOP. The capacity of a MOEA to generate evenly spread solutions close to the true optimal 1.1. Report Structure 6 solution set will dictate its performance. Past research often which compares different MOEA does not focus solely on diversity [1, 2] or is now outdated [3,4]. Thus, in this project we are going to focus on comparing the quality of the distribution of solutions produced by various MOEA. Additionally, we will classify the biases or irregularities that each MOEA might have. In order to accomplish these tasks we need to: 1. Identify both popular and state-of-the-art MOEA. Research the available implementations for the algorithms. 2. Identify a set of MOPs with varied characteristics and difficulty to run the tests on. 3. Research the literature for diversity metrics and implement the most promising ones. 4. Tune the parameters of the selected MOEA against the chosen diversity metrics. Improvements in the spread of the distribution indicate that the metric correctly measures diversity. The most accurate one will be selected. 5. Test the MOEA on the selected MOPs and compare the diversity scores obtained. The process will be automated in order to generate histograms of the solutions found and box plots of the metrics gathered throughout the multiple runs of the MOEA. Having this information would allow to take informed decisions when choosing a MOEA. One could even use a MOEA in particular in order to generate solutions in a determined range of the solution set. Moreover, the best performing diversity maintaining strategies will be identified. 1.1 Report Structure Chapter 2 formally introduces the concepts and terminology used throughout the report in detail. A brief description of the tested MOEA is also given. Chapter 1.1. Report Structure 7 3 gives an overview of the process followed to achieve the stated objectives. An introduction and a comparison of the diversity metrics used throughout the literature is also performed. One of these metrics will be selected to use in upcoming tests. Additionally, a brief overview of the software framework used to support the development of the project and existing alternatives is performed. Chapter 4 describes the set-up in which the tests were performed alongside an analysis of the results gathered throughout the comparisons of the diversity of the selected MOEA. Finally, Chapter 5 summarises the most significant results obtained throughout the project and outlines possible future work to be done. Chapter 2 Background This chapter introduces the required concepts needed to define the objectives of the project as well as the terminology used throughout the report. The research performed to write it constitutes the first phase of the project in which the MOEA were selected in order to be tested in later stages. 2.1 Multi-Objective Optimisation Single Objective Optimisation refers to finding one or more solutions that minimise or maximise a given objective function. Multi-Objective Optimisation thus refers to the problem of finding solutions which optimise two or more objective functions. The objective functions are usually in conflict: a solution that minimises one of the objectives might worsen another one. Defining a single solution as the optimal one is thus not possible. Instead, there will be multiple optimal solutions defined by the various trade-offs between the objective functions. Many day to day problems posses multi-objective nature, where two objectives are at conflict. For example, when a manufacturer wishes to produce a good he would want to minimise its cost while also maximising its quality. A product with low price and low quality would be placed at one extreme of the set of possible solutions, while a product with high price and high quality would be found in the opposite one. Many "middle-ground" solutions can be found between them. Which solution is the most adequate is a subjective choice and will be decided by the 2.1. Multi-Objective Optimisation 9 preferences of the manufacturer. 2.1.1 Multi-Objective Problem A Multi-Objective Problem (MOP) is defined as the minimisation (or maximisation, since it can be converted to a minimisation problem by multiplying each objective function by -1 [5, p. 14]) of: Definition 2.1.1 (Multi-Objective problem [5]). minimise/maximise xfm(x)m=1,2, ..., M; subject to gj(x)≥0j=1,2, ..., J; hk(x)=0k=1,2, ..., K; x∈Ω A solution xis a vector of ndecision variables x=(x1,x2, ..., xn)>∈Ω.Ω will be referred to as decision space. The vector f(x)=(f1(x),f2(x), ..., fM(x))> captures the values of each of the Mobjective functions w.r.t the solution x. The space containing this vector will be referred to as objective space. 2.1.1.1 An Example The following multi-objective problem (MOP) can be found in [6], referenced throughout the report as Schaffer’s first function: minimise xf1(x)=x2 f2(x)=(x−2)2 A plot of the two functions can be seen in Figure 2.1. In order to solve the problem a value for xwhich minimises both functions must be found. One might assume that x=1is the solution that minimises both objectives. However, x=0 and x=2, which minimise f1and f2respectively, are solutions which also minimise both functions, albeit not in a balanced manner. The solution x=3is clearly not optimal since the value of both objectives can be reduced by choosing x=2, for example. 2.3. Multi-Objective Evolutionary Algorithms 16 Figure 2.5: Crowding distance calculation in NSGA-II calculated between neighbouring solutions. Source: [12]. dominates the parent, the child will replace it in the population and the parent will be inserted into the archive. If the archive is found full, parent and child are compared using an adaptive grid algorithm, which measures the number of solutions which are found inside a grid with as many dimensions as objectives the MOP has. The grid recursively adapts in order to separate both solutions without the need of a niching parameter. The most diverse solution will be kept into the population and pushed into the archive. Other implementations of PAES, such as (1+λ)-ES and (µ+λ)-ES, have been found to perform similarly as the (1+1) version. 2.3.2.4 SPEA2 The Strength Pareto Evolutionary Algorithm 2, introduced by [14], improves on the original SPEA algorithm. SPEA2 evaluates the fitness of a set of solutions comprised by the union of a parent and child population generated by selection and crossover operators. The fitness value of solution iis computed as the summ of R(i)=Pj∈Pp∪Pc,j≺i|{w|w∈Pp ∪Pc ∧j4w}|(where Pp and Pc are the parent and child population, respectively) and the distance to the k-th nearest neighbour. The algorithm then selects greedily the nondominated individuals to form a new population of fixed size. If there are too many nondominated individuals, a truncation operator selects individuals according to the distance to the nearest neighbour of a solution. However, if more individuals are needed to fill the population, dominated individuals are added according to their fitness value. The algorithm then generates the appropriate child population and starts a new iteration. 2.3. Multi-Objective Evolutionary Algorithms 17 2.3.2.5 PESA-II The Pareto Envelope-based Selection Algorithm 2 was introduced by [15] and improves on the original PESA. PESA-II maintains an external archive apart from the current population where the nondominated solutions are stored. All the solutions in the archive are nondominated w.r.t each other, otherwise they will be deleted. The algorithm selects two parents from the external archive to generate a child via crossover and mutation. PESA-II divides the objective space into hyperboxes of fixed size in order to select these parents from low-populated hyperboxes. The solutions are added into the current population until it is filled and the next iteration starts. 2.3.2.6 -NSGAII When using NSGA-II, the user needs to set a population size, number of iterations, crossover probability and mutation probability. -NSGAII, introduced by [16], seeks to improve the already mentioned NSGA-II by automating its parametrisation. The algorithm will run multiple iterations of NSGA-II, selecting into a fixed-size archive the nondominated solutions on each iteration according to an -dominance criteria (See Definition 2.2.4). The updated archive is then injected in the next iteration, and the population size is doubled. The algorithm stops when a user-defined change rate between the previous result and the current one is achieved. 2.3.2.7 -MOEA -MOEA, introduced by [8], uses a method to preserve diversity similar to PAES which consists in the division of the objective space in hyperboxes of size .- MOEA maintains an archive of -nondominated solutions apart from the current population. The algorithm then selects one solution from the current population and one solution from the archive to create a single offspring. The offspring is swapped into the current population if it -dominates any of its individuals. Similarly, the offspring will substitute an individual in the archive if the first -dominates the later. In the case that the offspring is -nondominated w.r.t the archive, the offspring will be accepted only if the hyperbox that contains it has no other solution already in it, 2.3. Multi-Objective Evolutionary Algorithms 18 thus preserving a single solution on each hyperbox. 2.3.2.8 IBEA The Indicator-Based Evolutionary Algorithm, introduced by [17], approaches MOEA design differently and avoids the use of a diversity preserving technique by only using a quality metric to guide the search. The suggested metrics are the I, which quantifies the value with which one soluton -dominance another one, and the Hypervolume indicator [1] (introduced in Section 3.3.1.2). The algorithm starts by assigning a fitness value to the current population based on the the comparisons of each solution using the chosen indicator. The solution with the lowest score is deleted from the population and all the fitness scores are recomputed until the population size is lower than a user defined threshold. A mating pool is selected from the resulting population, over which combination and mutation operators are applied to generate a child population, later added to the current population. 2.3.2.9 MOEA/D The Multi-Objective Evolutionary Algorithm based on Decomposition, introduced by [18], optimises each objective independently according to a user defined decomposition approach. In this project, the MOEA/D variant using the Tchebycheff approach and a Differential Evolution operator is used. MOEA/D maintains an array with the minimum solution for each objective found so far. The algorithm then picks randomly three of these solutions in order to generate a single offspring. The offspring is objective-wise compared against randomly selected solutions from the algorithm’s population and substitutes solutions deemed worse by the Tchebycheff criterion. Diversity in MOEA/D is maintained due to the natural behaviour of the algorithm: by handling each objective separately the competing objectives will promote different solutions. 2.3.2.10 NSGA-III NSGA-III, introduced by [19], seeks to improve on NSGA-II by modifing the selection operators based on the decomposition strategies seen in MOEA/D. NSGA-III thus replaces the crowding distance fitness assignment with an strategy which uses 2.3. Multi-Objective Evolutionary Algorithms 19 a series of dynamically computed, well-spread, reference points to aid in the preservation of diversity in the population. The reference points are used similarly as the weight vectors in MOEA/D. The technique is referred to as multiple targeted search. 2.3.2.11 DBEA The Decomposition-Based Evolutionary Algorithm, introduced by [20], uses a strategy based on decomposition similar to MOEA/D whereby each objective is handled separately. DBEA uses a unique mechanism to preserve diversity whereby two distances are computed for each individual in the population, shown in Figure 2.6: the first one measures the distance between the individual and the origin of the objective space. The second one measures the distance between the previously described line and the solution. DBEA selects two parents randomly from the population and applies a crossover operator to generate an offspring that will compete against the rest of the population. The offspring will replace the previous best solution found for each objective if it has lower values on the previously described distances. Figure 2.6: Distance measures used by DBEA (indicated as d1and d2) to preserve diversity. Source: [20]. 2.3.2.12 OMOPSO OMOPSO, introduced by [21], uses the Particle Swarm Optimisation technique inspired by the behaviour of flocks of birds: a population of solutions is "flown" through the search space, guided by a "leader" solution. OMOPSO selects the leaders from the non-dominated solutions of the current population. These solutions are 2.3. Multi-Objective Evolutionary Algorithms 20 sent to an external archive, which will be returned as the result. If the number of leaders exceeds a user defined threshold, leaders with the highest crowding distance (used also by NSGA-II, described in Section 2.3.2.2) scores will be deleted. Each individual in the population will be updated using a leader selected using a evolutionary selection operator. A parent will be replaced by its offspring in the current population if the later dominates it. 2.3.2.13 SMPSO The Speed-constrained Multi-objective Particle Swarm Optimiser, introduced by [22], is based on and seeks to improve OMOPSO. The main differences are a new formula to update each individual, which constraints the distance travelled by the solution on each update. Additionally, SMPSO now uses polynomial mutation over the generated offspring. 2.3.2.14 MOCell MOCell, introduced by [23], is characterised by the usage of a cellular model: individuals are only able to breed with individuals found nearby. By splitting the search space in various overlapped neighbourhoods a diverse exploration of the search space is achieved while convergence takes place inside each neighbourhood independently. MOCell works by mating and mutating individuals in each neighbourhood to generate offspring. The offspring will replace its parents if it dominates them (Definition 2.2.1). Additionally, MOCell maintains an external archive to store nondominated solutions. The offspring will be inserted into the archive if they are nondominated. If the archive is full, the individual with the lowest crowding distance score (the same measure used by NSGA-II described in Section 2.3.2.2) will be replaced. MOCell also injects a fixed number of solutions from the archive into the current population before starting a new iteration. 2.3.2.15 CellDE CellDE, introduced by [24], improves on the previously mentioned MOCell by using a Differential Evolution operator [25] instead of the regular selection, crossover and mutation operators seen in genetic algorithms. Additionally, CellDE uses the same 2.3. Multi-Objective Evolutionary Algorithms 21 diversity criterion introduced by SPEA2 (which measures the distance to the kth nearest neighbour, Section 2.3.2.4) due to the underperformance of the crowding distance operator used in MOCell [26]. 2.3.2.16 GDE3 The Generalized Differential Evolution 3 algorithm, introduced by [27], is an algorithm characterised by the usage of Differential Evolution (DE) as the mechanism to explore the search space. GDE3 applies a slightly modified DE operator to generate offspring from the current population. If the offspring dominates the parents, the child will replace them. If the offspring and parents are both nondominated, the offspring is still added to the current population. Thus, the population might exceed the user determined size of the population and will be pruned before starting the next iteration. The pruning criterion will eliminate dominated solutions from the population as well as solutions with a low crowding distance (the same criterion used in NSGA-II, seen in Section 2.3.2.2). 2.3.2.17 CMA-ES The Covariance Matrix Adaptation Evolutionary Strategy, introduced by [28], is characterised by the usage of a covariance matrix to guide the search. The algorithm generates new offspring from sampling a normal distribution defined by the covariance matrix of each individual. CMA-ES uses a similar technique to GDE3 in order to check if the offspring are better than the parents: the nondominated solution will be chosen always, but in the case where both parent and child are nondominated to each other the ties are broken based on the value of an indicator. The author suggest either to use the crowding distance criterion used by NSGA-II (Section 2.3.2.2) or the Hypervolume indicator [1] (described in Section 3.3.1.2). 2.3.2.18 AbYSS The Archive-Based hYbrid Scatter Search algorithm, introduced by [29], is characterised by the adaptation of the scatter search framework and the usage of various techniques seen in previous popular MOEAs to build a hybrid evolutionary algorithm. AbYSS maintains a fixed sized external archive of nondominated solutions 2.4. Previous Research 22 which prunes using the NSGA-II crowding distance criterion (see Section 2.3.2.2) in the case the archive becomes full. The current population is split between two sets: one which maintains the best individuals according to the same fitness formula used by SPEA2 (see Section 2.3.2.4), which not only takes into account the number of dominated individuals of each solution but also the distance to the k-th nearest neighbour. The second set stores individuals which are far from the individuals in the first set distance-wise to preserve diversity. Pairs of individuals from both sets have a crossover and mutation operator applied. The offspring will replace the parents if the offspring dominates any of them. If both parents and offspring are nondominated, the parents will be sent to the external archive and will be replaced by the offspring. 2.4 Previous Research Comparisons in the literature usually tend to compare MOEA using either visualisations of the PFknownfound [30], metrics which independently measure convergence and diversity [2] or metrics that try to measure both convergence and diversity [20]. Many of these comparisons are found only as tests performed in the papers which introduce a new MOEA. These tests are made usually only against a small selection of a few past popular MOEA, proving to not be exhaustive tests. Many of these studies also use a small number of MOPs, which can bias the conclusions of the paper due to the tests not being exhaustive enough and lead to the cherry-picking of MOPs were the MOEA perform well. Moreover, previous studies focused on the distribution of the solutions [3] use outdated MOEA. Thus, in this project we are going to fill the gap left in the literature by gathering a comprehensive set of both MOEA and MOPs to test the distribution of solutions generated by these algorithms and bring past researched topics up to date. Chapter 3 Methodology This Chapter gives an overview of the whole process followed in order to develop the method used to compare the previously discussed MOEA. Before starting to research and choose the MOPs and diversity metrics used in the comparisons, implementations of the selected MOEA must be researched and tested. Section 3.1 shows a brief comparison between the available Frameworks which support the software produced in this project. Next, Section 3.2 introduces the MOPs used in the comparisons. Lastly, Section 3.3 gives a brief overview of the available diversity metrics and presents the results obtained from a comparison of the two most promising ones. 3.1 MOEAFramework Many software packages are available to ease both the development of MOEA and to compare them. In order to aid in the development of the software required to compare the algorithms, multiple frameworks were considered. A comparison between the most promising ones is shown in Table 3.1. From the main candidates shown, MOEAFramework 1was chosen due to its numerous advantages over the more mature and tested candidates. Frameworks not shown in the table (like Opt4J 2, Open-BEAGLE 3and HeuristicLab 4) were discarded as these frameworks are focused on the development of Evolutionary 1http://moeaframework.org 2http://opt4j.sourceforge.net/ 3https://chgagne.github.io/beagle/ 4http://dev.heuristiclab.com/ 3.2. MOP Selection 24 Algorithms rather than comparing them. MOEAFramework is written in Java and thus, the language was used throughout the majority of the code. Three small MATLAB scripts were also used to generate the bar plots and histograms from the data generated by MOEAFramework (the code is shown in Appendix A.1). 3.2 MOP Selection In order to test the performance of the existing diversity metrics (shown in Section 3.3) a comprehensive set of problems with multiple characteristics needs to be compiled. Over the last few years there have been multiple attempts at creating an exhaustive MOEA test suit. Out of those attempts the ones that have received more attention by the research community are the ZDT functions [4], the DTLZ suite [34] and the WFG Toolkit [35]. An ideal MOEA Test suite will contain MOPs with different characteristics and features in order to potentially expose situations in which the algorithm might not perform well enough. A MOEA performing well on a particular generic test suite only suggests that the algorithm will perform well in the type of problems included in the suite and does not assure good performance in "real-word" problems. In other words, tests performed with test suites will never give definitive answers. The previously mentioned ZDT, DTLZ and WFG benchmark suites are not exhaustive and thus have shortcomings. The ZDT test suite misses scalable (i.e a variable number of objectives or decision variables) and varied problems with different characteristics [35], DTLZ falls short on providing deceptive and nonseparable problems [35], while the WFG Toolkit only provides hard problems which do not give the necessary information about the diversity of solutions that is needed [7]. The selected MOPs to be used in the comparisons can be seen in Table 3.2 and 3.3. The collection is formed by a varied set of MOPs which try to have easy to solve problems with plottable Ptrue and PFtrue (Schaffer’s 1 and 2, Fonseca’s 1 and 2, Kursawe, DTLZ1 and ZDT1), hard problems (DTLZ4, DTLZ7 and WFG1- 3.2. MOP Selection 25 Framework Advantages Disadvantages MOEAFramework •Great collection of MOEA and MOP implementations. •Newer software. •Multiple metrics implemented. •Focused on the comparison of MOEA. •Interfaces with JMetal and PISA. •Good code quality and well documented. •Actively developed. JMetal v4.5 [31] •Great collection of MOEA and MOP implementations. •Ongoing rewrite of the core, published as v5.0 . •Multiple metrics implemented. •Poor code quality. •Easy visualisation of comparison results. •Well documented. PISA [32] •First framework published, has a mature userbase. •No in-built methods to gather results to compare MOEA. •Has many official implementations of MOEA. •Fragmented codebase in multiple languages. •Widely used in the research community. •No metric implementations. •File poll based communication system between software modules. Paradiseo [33] •Written in C++. •No metrics implemented. •Extensive documentation and tutorials. •Only four old MOEA implementations. •No support for comparison of algorithms. •Few MOPs implemented. Table 3.1: Comparison of Multi-Objective Evolutionary Software frameworks. 3.3. Metric Selection 32 Inverted Generational Distance (IGD): Introduced by [45], the IGD metric measures the average Euclidean distance between each solution of PFtrue and their corresponding closest solution in PFknown. A poor value would be obtained, for example, in the case that the extreme solutions of PFtrue are far apart form PFknown. Other more recent mixed metrics have been developed, such as the G-Metric [46] and the Averaged Hausdorff Distance [47] but, similarly, these metrics have not been adopted by the research literature and are thus not used. 3.3.2 Diversity Metric Evaluation The comparison between the MOEA will be supported mainly by a single metric. Thus, either the Spacing or Spread metric, presented in Section 3.3.1.1, need to be selected. As explained in Section 2.3.1, convergence and diversity are at conflict when solving a MOP. A mixed metric might improve due to an increase of the convergence and not due to an improvement in diversity, providing thus misleading results about the quality of the distribution of solutions. For example, in Figure 4.3(a), the HV metric indicates that CMA-ES and AbYSS generate PFknownwith similar qualities. However, as seen in Figure 4.2, CMA-ES’s distribution is uneven and clumped in the middle of the set, while AbYSS’s distribution is evenly spread. The Mixed metrics presented in 3.3.1.2 are thus not considered for the tests as the inclusion of the evaluation of the convergence interferes with our objective of comparing the diversity. Instead, they will be used to support the results produced by our main metric during the MOEA comparisons. In order to select a metric, a comparison will be performed by tuning the parameters of each MOEA against the Spacing and Spread metrics. Through the visualisation of the resulting distributions conclusions will be made regarding the accuracy of each of them. If none of the tested metrics prove to be good enough to asses the diversity of a solution set, a new metric will have to be designed. Section 3.3.2.1 gives an overview of the process followed to implement the tests in MOEAFramework. Next, Section 3.3.2.2 explains the process followed and the set-up where the experiments were run on. Lastly, in Section 3.3.2.3, the 3.3. Metric Selection 33 effectiveness of both metrics is reviewed. 3.3.2.1 Spread Metric Implementation MOEAFramework will be used to perform the comparison between the Spacing and Spread metrics. While the Spacing metric is already built into the software, the Spread metric needs to be implemented. Algorithm 1 shows the pseudocode used to implement it. The resulting Java code can be seen in Appendix A.4.1. For further details into the classes needed to introduce a new metric into MOEAFramework, see commit d9ef5 5on the GitHub repository of the project. Algorithm 1 Computation of the Spread metric. 1: procedure Spread 2: sort PFknownlexicographically 3: if |PFknown|=0or distance(PFknown[0],PFknown[end])=0then 4: return 2.0 5: else 6: m←number of objectives 7: extremeV alues ←∅ 8: for k∈1. . . mdo 9: sort PFtrue according to the k-th objective 10: extremeV alues ←extremeV alues ∪PFtrue[end] 11: end for 12: dists ←∅ 13: for x∈PFknowndo 14: dists ←dists ∪minj∈PFknown {distance(x,j)} 15: end for 16: distExtremes ←0 17: for x∈extremeV alues do 18: distExtremes ←distExtremes +minj∈PFknown {distance(x,j)} 19: end for 20: sum ←0 21: for d∈dists do 22: sum ←sum +|d−mean(dists)| 23: end for 24: return (distExtremes+sum)/(distExtremes+|PFknown|·mean(dist)) 25: end if 26: end procedure To verify the implementation Unit Tests6have been incorporated into 5https://github.com/Gan0k/MOEAFramework/commit/d9ef5 6Unit Test’s source code at GitHub 3.3. Metric Selection 34 MOEAFramework using JUnit7. The tests run over some edge cases such as an empty Pareto Front, which should return 1.0, and simple cases such as approximation sets with solutions PFknown={(0,1),(0.5,0.5),(1,0)}, which should return 0.0. 3.3.2.2 Tuning Process For each MOEA, a program was developed to easily interact with the algorithm’s parameters from the command line. A snippet of the code can be seen in Appendix A.4.2 and indications on how to run it can be found in Appendix A.1. These programs output, for each indicated metric, the minimum, median and maximum values for achieved by the MOEA with default and tuned parameters, respectively. This setup is designed to exploit the fact that MOEAFramework uses the KruskalWallis and Mann-Whitney methods to test for statistical significance between the two different set-ups in order to compare solutions gathered from the an stochastic process such as an EA. Inequality hypothesis are rejected if p-value <0.05. Thus, MOEAFramework will indicate us when the values produced with the modified parameters are statistically indifferent from those gathered with the default parameters for a particular metric. The MOEA will be tuned by first modifying a single parameter, fixing it to a value which produces the highest increase of the tested metric, and proceeding with the same process for the rest of the parameters. A subset of MOEA and MOPs was selected from the previously introduced collections due to the time consuming nature of the described procedure. The tested MOEA are NSGA-II, MOEA/D, GDE3 and IBEA with Schaffer’s 1 and 2 functions, Fonseca’s first, DTLZ benchmark’s functions and the WFG Toolkit. The visualisation of the found Pareto Fronts will be done through histograms of the solutions. Through these plots we will be able to observe both the distribution of solutions as well as the areas where solutions are clumped. Only two-dimensional spaces can be plotted using this method, thus the DTLZ and WFG Toolkit functions will be used only with two objectives. 7http://junit.org/ 3.3. Metric Selection 35 In order to assure that each MOEA does the same amount of work, the number of function evaluations (that is, the number of times the algorithm evaluates any of the objective functions) was set to 10.000. Moreover, the population of each MOEA was set to 100 individuals. To obtain robust results we need to execute each MOEA with different random seeds in order to discard possible "lucky" results. Thus, each MOEA was executed 100 times with different random seeds. The tuned MOEA parameters can be found in Appendix A.3. 3.3.2.3 Analysis and Conclusions After tuning the MOEA against the Spread and Spacing metrics the following was concluded: 1. Unexpectedly, in few situations the Spread metric gave different assessments than the Spacing metric. One of these cases is shown in Figure 3.3, where a disagreement between the two metrics can be observed. The Spacing metric shows that the distribution of solutions might not be uniform on each run, yet the Spread metric manages to discern a better distribution. However, most situations show that both metrics agree on the improvement or decline in quality of the Front (see Figure 3.5). 2. It was expected that when tuning a MOEA, a metric would increase or decrease based on parameter changes. However, when changing them, an increase in the variance of the metrics throughout the multiple runs was observed instead, complicating the process. 3. The increase in variance was most notably observed in the Spacing metric, as the locations of solutions can vary greatly between runs and skew easily the metric. 4. The metrics have a hard time assessing non-convex Pareto Fronts (see Figure 3.4). Convex Fronts are assessed well (see Figure 3.5). 5. Its easier to compare MOEA using the Spread metric as it is bounded between zero and two. The Spacing metric can be easily mislead when the MOEA 3.3. Metric Selection 36 does not fully converge to PFtrue. 6. In some cases, tuning against diversity metrics also improved convergence (see Figure 3.6). Both metrics gave thus accurate assessments about the quality of the distribution of solutions. However, as stated, the Spread metric gave more consistent results and eases the comparison of results due to being bounded. In the next chapter the Spread metric is going to be used to compare the MOEA. Nonetheless, the Spacing metric is still going to be used to gain insight on the uniformity of the distribution. (a) HV IGD I+Spacing Spread R2 Default 0.0612 0.0058 0.0046 0.0200 0.7779 5.8224 Tuned 0.0612 0.00578 0.0048 0.0203 0.7401 5.5667 (b) Figure 3.3: An improvement of the distribution of solutions is not detected by Spacing when IBEA is run against Fonseca, yet the Spread metric manages to identify it. Table (b) contains the median of each metric gathered throughout 50 runs. Note that Figure (b) contains plots in decision space. 3.3. Metric Selection 37 (a) HV IGD I+Spacing Spread R2 Default 0.153 0.0434 0.0605 0.0314 0.5922 0.405 Tuned 0.1545 0.0422 0.0563 0.027 0.555 0.4037 (b) Figure 3.4: The WFG8 problem contains a concave Pareto Front. The Spread and Spacing metrics detect a better distribution although the histogram in Figure (a) shows that the solutions got clumped towards one extreme. Table (b) contains the median of the metrics over 50 runs. (a) HV IGD I+Spacing Spread R2 Default 0.0613 0.0057 0.00854 0.00837 0.3063 7.1312E-5 Tuned 0.0614 0.00558 0.0084 0.00788 0.2714 5.0355E-5 (b) Figure 3.5: The Spacing and Spread metrics agree that the distribution of solutions is better when running MOEA/D against Fonseca’s first function. Note that Figure (a) is plotted in objective space. Table (b) contains the median of the metrics over 50 runs. 3.3. Metric Selection 38 (a) IGD I+Spacing Spread R2 Default 13.13 12.84 3.01 0.96 3.37 Tuned 8.164 7.32 0.87 0.87 1.96 (b) Figure 3.6: An improvement of both convergence and diversity metrics when running NSGA-II against the DTLZ3 problem with two objectives is shown. Note that PFtrue ={(0.0,0.0)}. Once tuned, NSGA-II produced solutions much closer to PFtrue. Plot (a) contains the histogram of solutions over 50 runs. Table (b) contains the medians of the metrics. Chapter 4 Experiments To compare the quality of the distribution of solutions generated by the selected MOEA presented in Section 2.3.2, they will be executed against the MOPs described in Section 3.2 and the resulting PFknownwill be evaluated using the metrics presented in Section 3.3. This Chapter introduces the experimental set-up followed to perform these tests. In Section 4.1, a series of convergence metrics are presented to further support our analysis. An overview of the data we expect to collect is also given. Additionally, the parametrisation used in each MOEA is stated along with the environment set-up used to run the tests. Section 4.2 contains an overview of the challenges faced when performing the tests. Lastly, in Section 4.3 the results of the tests are presented and in Section 4.4 the performance of each MOEA is analysed alongside the biases and difficulties that each MOEA showed. 4.1 Collected Metrics and Data When mapping the characteristics of PFknowninto a single scalar some information will be inevitably lost. Thus researchers usually use multiple metrics which capture different characteristics of PFknownin order to get more robust results when comparing MOEA. Aside from the metrics described in 3.3, the following convergence metrics will also be used. It should be noted that a set of unary metrics which accurately describes the quality of PFknownhas been proven to be impossible by [39]. 4.1. Collected Metrics and Data 40 •Generational Distance (GD) [48], which measures the distance of each solution of PFknownto the closest solution of PFtrue, contrary to the IGD metric. •Additive -indicator (Ie+) [39], which generalises the concept of -dominance introduced in Definition 2.2.4 between PFtrue and PFknownto a metric containing the value of . •R2Indicator [49], which similarly measures the distance of PFknownto PFtrue. As stated in Section 2.3.1, convergence and diversity are at conflict in the execution of an EA. These metrics will allow us to assess if a good distribution of solutions is caused by a poor convergence to PFtrue. They have been chosen due to their wide usage in the literature and availability inside MOEAFramework. The usage of the Hypervolume, Ie+and R2 indicator are specifically recommended by [38]. A program (see Appendix A.4.3 for the code and Appendix A.1 to find how to use it) was developed in order to automate the process of comparing the selected MOEA, producing the following data when given a series of MOPs on which to test the MOEA on: •The found PFknownby each MOEA through multiple runs. •For each MOP, the minimum, median and maximum value obtained by each MOEA for the stated metrics. Additionally, as stated in Section 3.3.2.2, MOEA statistically indifferent from one another will be indicated by using the Kruskal-Wallis and Mann-Whitney methods. Inequality hypothesis are rejected when p-value <0.05. •Due to the stochastic nature of EA, each MOEA has to be executed multiple times for each MOP in order to gather consistent results. Box plots will be produce in order to observe side-by-side the different results of each MOEA. JFreeChart1was used to produce them. 1http://www.jfree.org/jfreechart/ 4.1. Collected Metrics and Data 41 •The average execution time of each MOEA for each MOP will be gathered in other to further support our comparison. MOEA which have significantly higher execution times will be held to higher standards. Analysing the Pareto Fronts by visualising them directly might be inaccurate. However, as stated in Section 3.3, MOEA metrics do not fully convey all the useful information about the solution sets. Thus, aside from the already mentioned box plots, histograms of the union of the Pareto Fronts found by the MOEA through the multiple tuns will be produced. A simple MATLAB script has been produced to plot them from the printed PFknwon, additionally adding PFtrue into the plot for reference (information about it can be found in Appendix A.1). 4.1.1 MOEA Parametrisation The default parameters of the MOEA shown in Table A.1 were used in all the tests. The values were gathered from the paper which introduced the algorithm when possible, as only some authors do give recommended values for a MOEA’s settings. When not available, the default parameters set by MOEAFramework were used. The previously mentioned program to automatically run the tests also has the ability to read configuration files automatically in order to be able to modify the parametrisation of a MOEA with ease (see Appendix A.4.3). 4.1.2 MOP Parametrisation A MOEA will have more difficulty solving a MOP as the number of objective function increases. Thus, the DTLZ and WFG Toolkit’s functions were run with both 2 and 3 objectives, allowing to observe the performance of the MOEA in situations where the number of objectives was increased. Fonseca’s second function and Kursawe’s function were run with 3 decision variables each. All the MOPs presented in Section 3.2 use Real Numbered-Variables in their problems. Therefore, the MOEA which require them, use the Simulated Binary Crossover Operator [50] and the Polynomial Mutation Operator to be able to emulate the crossover and mutation of bit-string variables seen in regular EA. The 4.4. Analysis 48 dependant, suggesting that rather than CellDE outperforming MOCell in terms of diversity as the authors would have hoped (see Section 2.3.2.15), the algorithms rather complement one another. CellDE scored multiple times really poorly on the Spacing metric, while MOCell tended to average good scores. CellDE also struggled to converge to optimal solutions and was often surpassed by MOCell on the GD metric. Examples of these behaviours can be seen in Figure 4.4, where MOCell shows better a convergence and spread and spacing than CellDE. Both MOEA seem to provide a good balance between diversity and convergence, although they lack the robustness seen in AbYSS: sometimes the MOEA produce the best solutions approximations across all algorithms, while sometimes score really poorly. Although both MOEA use the same underlying cellular strategy, they also showed significantly different results. Most of the time, MOCell performed better than CellDE regarding both diversity and convergence in spite of the fact that CellDE is supposed to be an improved version of the first one (see Figure 4.7). MOCell shows better distributions since CellDE tends to favour individual minimums of the objective functions. Only in WFG’s three-objective problems CellDE saw better results (see Figure 4.13). Moreover, the execution times of CellDE were magnitudes higher than any other MOEA in some particular MOPs such as Fonseca’s and Schaffer’s functions (see Figure 4.5(b) and 4.10(e)) and the DTLZ two-objective problems (see Figure 4.14(e)). GDE3 , on the other hand, performed quite similarly to CellDE, albeit obtaining considerably better scores in some problems. Both MOEA are related in their usage of Differential Evolution as the evolutionary operator. GDE3 showed really promising results regarding both the Spread and Spacing metrics, ranking multiple times among the best MOEA. For example, GDE3 scored the best results on ZDT3 across all metrics (see Figure 4.6). However, as it is expected from such algorithm, convergence scores were really average on the majority of the tests (see Figure 4.7). It is remarkable the low variance between the scores achieved by GDE3, suggesting that the results obtained with the algorithm are really consistent. GDE3 4.4. Analysis 49 (a) Spread values obtained during 50 runs (lower is better). (b) Spacing values obtained during 50 runs (lower is better). (c) GD values obtained during 50 runs (lower is better). (d) Hypervolume values obtained during 50 runs (higher is better). (e) Histogram of the solutions found by MOCell over 50 runs. (f) Histogram of the solutions found by CellDE over 50 runs. Figure 4.4: CellDE shows poor convergence on ZDT3 while MOCell obtains the best scores across all metrics. PFtrue is marked on Figures (e) and (f) with orange. 4.4. Analysis 50 (a) Histogram of the solutions found by -NSGA-II on Schaffer 1 over 50 runs. (b) Average execution times in seconds of various MOEA on Schaffer’s first function. Figure 4.5: (a): -NSGA-II produces an unbalanced distribution for Schaffer’s first function in Figure (a). CellDE and SPEA2 show extremely high execution times in Figure (b). also performed poorly regarding the diversity of solutions on all WFG problems. Nonetheless, the convergence of GDE3 on these MOPs were amongst the best. GDE3, together with AbYSS, seem to produce the most well spread and even distributions of all the MOEA. -NSGA-II did not perform remarkably well in terms of the quality of the distribution in any of the MOPs. -NSGA-II additionally showed multiple times really inconsistent spacing results with high variances, similar to the ones seen in Figure 4.4(b). However, -NSGA-II showed really promising results on the convergence metrics, as seen on Figure 4.2(c). The algorithm also tended to generate solutions away from the individual minimums of the objectives functions, as seen for example in Figure 4.5(a). The MOEA also showed problems solving the ZDT problems, converging to badly distributed solutions far away from PFtrue. 4.4. Analysis 51 (a) Spread values obtained during 50 runs (lower is better). (b) Spacing values obtained during 50 runs (lower is better). (c) GD values obtained during 50 runs (lower is better). (d) Histogram of the solutions found by GDE3 over 50 runs. PFtrue is marked with orange. (e) Average execution times in seconds of the ZDT4 function for each MOEA. Figure 4.6: GDE3 obtains the best results on all metrics for ZDT3. 4.4. Analysis 52 NSGA-II showed really average results on both Spacing and Spread metrics. All the scores obtained were really consistent as the variance between runs was much smaller than the ones seen in other MOEA. In Fonseca’s second, the DTLZ and WFG problems with three objectives, NSGA-II scored low on the Spacing metric due to not generating even distributions. NSGA-II was never found in the top performing algorithms in any of the tests nor the worst one, falling always on the average of the scores consistently. The same behaviour was observed for the convergence metrics as NSGA-II received mediocre scores on all tested MOPs, for example in Schaffer’s first function, seen in Figure 4.2. However, according to the Hypervolume metric in Figure 4.3(a), NSGA-II is one of the worst performing MOEA for this same MOP, indicating that the overall quality of the set might not be as high as indicated in the other metrics. Lastly, NSGA-II seems to generate an over-representation of solutions exactly at the individual minimums of each objective function, as seen for example if Figure 4.7(d). OMOPSO and SMPSO have produced really promising results on the Spread and Spacing metrics. SMPSO seems to constantly obtain a better score on the Spread metric and place amongst the top MOEA, while OMOPSO obtains average scores on it (see for example Figure 4.14(a)). Regarding the Spacing metric, OMOPSO seems to produce really irregular results, sometimes obtaining a better than average result (see Figure 4.13(b)) while in other cases scoring amongst the worst algorithms. A behaviour similar to the one described in MOCell and CellDE was observed: when one of the MOEA would get better than average scores in the Spacing and Spread metrics, the other would then obtain mediocre results. For example, in Figure 4.10, OMOPSO obtains the best GD score amongst MOEA but received the worse diversity scores. On the other hand, SMPSO obtains the best diversity scores and average convergence results. An example can be seen in Figure 4.2 or Figure 4.7, where SMPSO receives favourable diversity scores but poor convergence scores, and OMOPSO produces just the contrary: better than average convergence but a poor distribution. It is interesting to see that despite the difference in performance, 4.4. Analysis 53 (a) Spread values obtained during 50 runs (lower is better). (b) Spacing values obtained during 50 runs (lower is better). (c) GD values obtained during 50 runs (lower is better). (d) Histogram of the solutions found by NSGA-II over 50 runs. Figure 4.7: NSGA-II obtains average results on all metrics for WFG5 with two objectives. The distribution is still quite good albeit skewed towards the minimum of each objective function. 4.4. Analysis 54 the Hypervolume metric assigns similar scores to both MOEA in Figure 4.3(a) for Schaffer’s first function. A comparison of the distributions of solutions for WFG5 with two objectives can be seen in Figure 4.8. OMOPSO also produced very inconsistent results regarding the convergence metrics, sometimes scoring really good scores with low variance (see Figure 4.10(c)) and in other situations obtaining the worst scores. On the other hand, SMPSO received average scores on the convergence metrics most of the time albeit also having problems solving three-objective WFG’s problems, as seen in Figure 4.13(c). This leaves us to conclude that OMOPSO produces really irregular results which are highly dependant on the MOP being solved, while SMPSO produces distributions which balance a good convergence rate and a high quality distribution. (a) Histogram of solutions found by OMOPSO on WFG5 with two objectives over 50 runs. (b) Histogram of solutions found by SMPSO on WFG5 with two objectives over 50 runs. Figure 4.8: The distribution of solutions of SMPSO is much better than the one obtained from OMOPSO, although it has a much better convergence as indicated by Figure 4.7(c). In the same Figure 4.7, Spread and Spacing values for both MOEA can be seen. PFtrue is marked with orange. MOEA/D performed really poorly on both Spread and Spacing metrics, as shown for example in Figure 4.2(a). Moreover, the algorithm was not consistent as the variances of the results obtained in the Spacing metric were larger than average. 4.4. Analysis 55 Convergence metrics also indicated that MOEA/D performs worse than the average score received by all MOEA in each MOP. In Figure 4.7, for example, shows that MOEA/D achieved worse than average Spread and Spacing scores, while scoring a high (i.e. worse) GD value. The histogram of solutions for this MOP can be found in Figure 4.9. Lastly, due to not having an explicit diversity-preserving mechanism, MOEA/D has shown problems distributing solutions on MOPs with disconnected PFtrue like Kursawe. Figure 4.9: Histogram of solutions found by MOEA/D on the WFG5 problem with two objectives. Compared with SMPSO’s distribution in Figure 4.8(b), the distribution is slightly unbalanced towards minimums of each objective function. Metrics results for this problem can be found in Figure 4.7. IBEA ’s generated distributions were amongst the worst seen (see 4.10(a)). The algorithm consistently scored poorly in the Spread and Spacing metrics. Moreover, the variance seen on the values throughout the multiples runs was always greater than average, showing that IBEA produces inconsistent results. Histograms of the distributions showed that IBEA is heavily skewed towards generating solutions on the minimums of each objective functions, as seen on Figure 4.10(d). However, the algorithm was consistently ranked as one of the best in terms of convergence, as seen for example in Figure 4.14(c). IBEA also has shown problems distributing solutions among disconnected areas of the PFtrue in problems like Kursawe. 4.4. Analysis 56 As described in Section 2.3.2.8, IBEA uses the Hypervolume metric to guide the search. Thus, IBEA scored highly constantly in this particular metric despite providing low quality distributions. However, as stated in Section 3.3, the Hypervolume is a computationally expensive metric to compute, thus making it one of the slowest MOEA. For example, in Figure 4.10(e), IBEA ranks amongst the slowest algorithms when running against Fonseca’s first function. Spending so many resources to only obtain solutions slightly closer to PFtrue shows that further development of this MOEA is needed. SPEA2 obtained remarkable scores on both Spread and Spacing metrics, ranking consistently amongst the top algorithms according to these metrics. Moreover, on the majority of MOP tested, the variance of the results was really low, indicating that the algorithm provides consistent results. Surprisingly, SPEA2 consistently provided the best distribution of solutions for the DTLZ and WFG three-objective problems, as seen for example in Figure 4.13. However, SPEA2 did not show high convergence rates on any of the MOPs. The MOEA obtained consistent average values in the GD metric, a similar behaviour also seen in NSGA-II. An example can be seen in Figure 4.10 where SPEA2 did score highly on the Spread and Spacing metrics on Fonseca’s first function, but did not do as good on the GD metric. The resulting distribution of the MOP can be seen in Figure 4.11. SPEA2 and NSGA-II were released on approximately the same time-frame (the year 2001). However, NSGA-II ended-up being considered the "standard" MOEA by the research community up to this day, while SPEA2 did not receive as much attention. Although producing uniform distributions and slightly better results than NSGA-II, SPEA2 showed some of the slowest computational times across all MOEA, as seen for example in Figure 4.10(e), Figure 4.6(e) or Figure 4.5(b). Thus, it can be inferred that the superior performance yielded by NSGA-II is the main reason that drove SPEA2 out of the spotlight. 4.4. Analysis 57 (a) Spread values obtained during 50 runs (lower is better). (b) Spacing values obtained during 50 runs (lower is better). (c) GD values obtained during 50 runs (lower is better). (d) Solutions found by IBEA over 50 runs on Fonseca’s first MOP. PFtrue is marked in orange. (e) Average time of a run in seconds of Fonseca’s first function. Figure 4.10: IBEA obtains poor Spacing and Spread scores while obtaining high GD values. Figure (d) shows an unbalanced distribution. Figure (e) shows that IBEA is amongst the slowest MOEA. Chapter 5 Conclusions In this report, a comparison between various MOEA was performed. The objectives outlined in Section 1 were all accomplished: •In Section 2.3.2 a selection of popular and state-of-the-art MOEA were presented. The MOEA were chosen based on the availability of their implementation and their diversity preserving mechanism. These MOEA were: NSGA-II, DBEA, MOEA/D, GDE3, OMOPSO, SMPSO, SPEA2, VEGA, -MOEA, - NSGAII, AbYSS, PAES, PESA-II, MOCell, CellDE, IBEA, CMA-ES and NSGA-III. •In Section 3.1 MOEAFramework, the software supporting the implementation of the selected MOEA, was presented alongside the considered alternatives. •In Section 3.2 the selected Multi-Objective Problems were presented. •In Section 3.3 the Spread and Spacing metrics were presented alongside the Hypervolume and Inverted Generational Distance metrics. While the first two measure the diversity of a solution set, the second ones also try to estimate the convergence at the same time. In Section 3.3.2.1, the algorithm to implement the Spread metric into MOEAFramework was presented. •In Section 3.3.2 the previously introduced diversity metrics were evaluated in order to test their accuracy. By tuning the parameters of NSGA-II, MOEA/D, GDE3 and IBEA algorithms against the Spread and Spacing metrics improve- 65 ments in the distribution of the found solutions were observed, assuring us that both metrics are able to identify diverse distributions. •In Section 4.1 the program used to automate the testing of the MOEA was presented. The software automatically generates box plots and histograms of the PFtrue found by the MOEA in order to ease the process of comparison. •A summary of the comparisons obtained through running the selected MOEA against the chosen MOPs is presented in Section 4.4. When appropriate, biases of each MOEA have been highlighted alongside MOPs which the MOEA had difficulty solving. From the previously mentioned analysis of the results the following conclusions were gathered: •-MOEA, -NSGA-II and IBEA generated really poor distributions across all the tested problems. This leads us to conclude that selecting solutions based on a -dominance criterion or using a metric such as the Hypervolume in the case of IBEA to guide the search favours convergence versus diversity. •CMA-ES and MOEA/D, although using novel approaches, achieved mediocre results on the diversity metrics and did not produce better distributions than NSGA-II, which is considered to be the baseline. CMA-ES saw extremely high execution times on many problems and, as a result, did not fully converge in many MOPs. •NSGA-II produced average but consistent distributions with really low execution times. SPEA-2, on the other hand, produced much better results than NSGA-II on diversity as well as convergence. However, the execution times of SPEA2 are much higher than the average. •PESA-II produced consistently poor distributions throughout all MOPs. However, the convergence scores of the algorithm, which were amongst the best, are not able to justify the extremely high execution times on MOPs with three objectives. 66 •PAES and VEGA, the two oldest tested MOEA, are known to be outdated and achieved extremely poor diversity results across all MOPs. While VEGA’s results show that in the majority of the cases no true Pareto Optimal solutions are found, PAES produces high variances across all metrics, indicating that the approach is not robust enough. •DBEA and NSGA-III, albeit being the most recently released MOEA out of the ones selected, produced only slightly better than average results, not justifying their high computational times. Both MOEA are explicitly designed to solve MOPs with more than three objectives, which other MOEA might have problems with, and thus perform poorly on the bi-objective and tri-objective MOPs tested. •GDE3 showed really promising results by achieving the top scores on the diversity metrics on some of the tested MOPs. •AbYSS proved to be a robust algorithm, obtaining better than average distribution scores across the majority of MOPs. •OMOPSO and SMPSO, albeit showing inconsistent results throughout MOPs (in some occasions achieving top scores while in others scoring amongst the worst MOEA), showed potential in generating high quality distributions. In particular, SMPSO did not score very high on convergence metrics but achieved the best distributions in many MOPs. •CellDE and MOCell results were also unpredictable across the MOPs. CellDE performed, on average, worse than MOCell although CellDE is supposed to improve on the latter. MOCell produced uniform distributions in some of the MOPs, however, it did not achieve a better performance than NSGA-II in many other MOPs. We expected that MOEA with similar diversity preserving mechanisms would perform similarly. However, we can gather from the results that this is not the case. For example, CellDE uses SPEA2’s diversity estimator but does not see the same 5.1. Future Work 67 success as the later. Nonetheless, the diversity mechanisms used by PAES, PESA-II, MOEA/D (which, incidentally, uses none) and -MOEA and IBEA, each of them described in Section 2.3.2, have been shown to perform worse than the other tested strategies and should be avoided. Regarding the diversity metrics, our introductory statement suggested the usage of a single metric to measure the quality of the distribution of solutions. However, multiple metrics ended-up being used. We can conclude that measuring the quality of a solution set might be even a more difficult task than MOEA design itself due to the difficulties found when mapping information about a solution set into a single number. From the tests conduced in Section 3.3.2.2 we could gather that both Spacing and Spread metrics are able to accurately asses the quality of a distribution of solutions. Although the Spacing metric only assesses the uniformity of the distances between solutions rather than the spread of the set, both characteristics are correlated and thus, both metrics produced, in most cases, similar judgements. Nonetheless, the Spread metric is able to convey more information about the distribution and thus, was given more importance when comparing the MOEA. Lastly, rather than seeing an increase or decrease in a metrics’s value when tuning a MOEA against it, changes in the variance were observed. In other words, tuning the algorithm produced more consistent results rather than lower values. 5.1 Future Work Possible experiment extensions could include the DTLZ and WFG test functions with a higher number of objectives, as only MOPs with two and three objectives were tested. Additionally, transforming MOPs with rotation matrices allows us to create a problem with similar characteristics to the original but with increased difficulty. Thus, testing the selected MOPs with rotations might bring further insight into the performance of MOEA. Other more recently introduced test suites such as the CEC2009 [51] and 5.1. Future Work 68 BBOB2016 [52] have been published and could be included. Additionally, the inclusion of constrained problems such as the C-DTLZ test functions [53] could be considered in order to widen the problem pool even more and observe the behaviour of MOEA in constrained spaces. More versions and configurations of the tested MOEA could be performed. For example, CMA-ES allows the usage of any type of quality indicator to select solutions. In our tests, NSGA-II’s crowding distance indicator was used, but the Hypervolume indicator or Iare also suggested in the introductory paper. Similarly, other indicators could have been used instead of the Hypervolume metric in IBEA. Furthermore, other versions of MOEA/D such as MOEA/DFD [54] and MOEA/DD [53] could also be tested. Other promising MOEA left out due to having problems with their implementations (see Section 4.2) such as HypE and SMS-EMOA could also be included. NSGA-III was a last addition to the collection of MOEA tested due to the implementation of the algorithm not being fully functioning 1. However, NSGA-III was included in order to identify if the strategy used by the algorithm outperforms significantly any of the other tested algorithms. When a complete implementation of NSGA-III is available, tests should be re-run. Using a binary indicator, although more time consuming, might also provide accurate answers to decide if a MOEA is "better" than another one. Binary metrics would also eliminate the need to use multiple indicators to measure different characteristics of the set. Lastly, the Spread metric was implemented using Euclidean distances (see Algorithm 1). It is suggested in the literature [5, p. 328] that Manhattan distances or the crowding distance used in NSGA-II (see Section 2.3.2.2) could be used instead. Implementations using this distances could be tested as well in order to possibly strengthen the accuracy of the metric. 1https://www.researchgate.net/post/Is_there_a_fully_functional_NSGA-III_ implementation Appendix A Appendices A.1 User Manual This section gives a brief overview of the code written throughout the project, along with its location. Indications on how to compile and run the code are also given. The code for the project is found in two separate code bases: modifications made to the source of MOEAFramework are found in the directory MOEAFramework/, while the rest of the code used to perform the tests and build the plots is found in the directory comparisons. A.1.1 MOEAFramework/ The MOEAFramework directory contains all the code and tests created to incorporate the Spread metric into MOEAFramework. The code, also available in its GitHub repository1, can be compiled with: $ ant build-binary The command, which requires Ant2, will produce a in the folder MOEAFramework/dist/ a file named MOEAFramework-2.9.jar, which can be copied to the directory comparisons/lib/ in order to be used in the tests. When running any of the tests, the Spread metric will be automatically included in the results. To compile and run the Unit Tests use the command: 1https://github.com/Gan0k/MOEAFramework 2https://ant.apache.org/ A.1. User Manual 70 $ ant run-tests The code relevant for the Spread metric can be found on the Appendix A.4.1 or in the folder: MOEAFramework/src/org/moeaframework/core/indicator/ GeneralizedSpread.java and the Unit Tests on: MOEAFramework/test/org/moeaframework/core/indicator/ GeneralizedSpreadTest.java All the code changes to include the Spread metric can be viewed in commit d9ef53. The rest of the code found in the folder has not been developed in this project. A.1.2 Comparisons/ The folder comparisons contains all the programs and scripts used to tune the MOEA and generate the plots and data to support the comparisons. All the code is mirrored in its git repository4. Its contents are the following: •pf/ Contains all the PFtrue from the tested MOP. These files were obtained from MOEAFramework. •lib/ Contains all the .jar files which MOEAFramework depends on. •tests/EvalDefParams.java: Program to generate a solution set of a MOEA with the default parametrisation and evaluate it using all the metrics supported by MOEAFramework. Run the program with the -h flag to see its usage. •tests/Gen_PFs.java: Program to print the PFknownfound by a given MOEA. Run the program with the -h flag to see its usage. 3https://github.com/Gan0k/MOEAFramework/commit/d9ef5 4https://bitbucket.org/Ganok/moea-analysis/ A.1. User Manual 71 •tests/plot_funcs.m: MATLAB script to visualise Fonseca’s first and second function and Schaffer’s first function using three-dimensional plots. •tests/plot_tuning.m: MATLAB script to plot the histograms of the PFknownfound in the tests/param_tuning/ folder generated after tuning a MOEA using the programs found in the same folder. •tests/plotHisto.m: MATLAB script to plot the histograms of the PFknown found in the tests/compare/sets folder generated after running each MOEA against the selected MOPs with the CompareDef.java program. The generated plots are saved in tests/compare/plot_sets. •tests/plotTimes.m: MATLAB script to generate the bar plots out of the average execution times found in tests/compare/times, created through the CompareDef.java program. The generated plots are saved in tests/compare/plot_times. •tests/param_tuning/{IBEAParam.java, GDE3Param.java, MOEADParam.java, NSGAIIParam.java SPEA2Param.java}: Programs used to tune the respective MOEA and print the PFknowngenerated by the MOEA over the given runs along with a summary of the scores achieved in the selected metrics. Run the programs with the -h flag to see its usage. The code of NSGAIIParam.java can be found in Appendix A.4.2. •tests/param_tuning/create_pic.sh: Bash script used to generate a side-by-side image of the plots of a tuned an untuned MOEA. The script has to be run on the root of the project (comparisons/ folder) and requires the imagemagick5software package to be installed. To run the script with NSGAII against Schaffer’s first function, for example, use the following command: $ ./create_pic.sh NSGAII Schaffer -sbxr 1.0 \ -sxbd 20.0 -pmidx 1.0 5https://www.imagemagick.org/ A.1. User Manual 72 •tests/param_tuning/histograms/: Contains all of the side-by-side plots generated when tuning the MOEA using the create_pic.sh. These plots are used in Section 3.3.2.3. •tests/compare/CompareDef.java: Program used to generate the box plots, PFknownfound and execution time data produced when testing the selected MOEA. Run the program with the -h flag to see its usage. The source code can be found in Appendix A.4.3. •tests/compare/alg_config/: Contains the parametrisation of the MOEA to be used when running the tests. •tests/compare/analysis/: Contains the summaries of the analysis of the results obtaied by the MOEA when running the tests with the CompareDef.java program. This data is used to plot the box plots found in the folder tests/compare/boxplots/. •tests/compare/sets/: Raw data containing the PFknowngenerated by each MOEA when run against each MOP with the CompareDef.java program. These files are not included in the .zip file attached. •tests/compare/time/: Raw data containing the execution times achieved by each MOEA when run with the CompareDef.java program. All the aforementioned code can be compiled with the following command, which will save all the .class files into the class/ folder: $ javac -cp "lib/*" -d class tests/compare/*.java \ tests/param_tuning/*.java tests/*.java To run any of the classes use the following command and substitute the name of the class by any the program we wish to run along with its parameter flags: $ java -cp "lib/*:class" $NAME_CLASS [$PARAMETERS] A.2. MOEA Default Parametrisation 73 A.2 MOEA Default Parametrisation Table A.1 and A.2 contain the default parametrisation of the MOEA used in the comparisons. A.3 Tuned Parameters Table A.4 and A.5 contain the tuned parameters of each MOEA used to perform the tests in Section 3.3.2.2. Note that due to brevity, parameters which obtained worst results when modifying their default value are omitted. Thus, only parameters which saw changes from the ones given in Table A.1 are included. A.4 Code Listings This section contains the relevant code written for the project. Note that in Section A.4.2 only the class to tune NSGA-II is included as the other classes used to tune the rest of the MOEA only differ on the parameters relevant to each MOEA. MATLAB scripts to produce plots (see Appendix A.1), test programs to easily visualise Pareto Fronts and shell scripts used to automate some task are not included due to being irrelevant to the project. Additionally, the implementation of the Spread metric can be found in the corresponding GitHub repository6, and the programs and plots used to compare the MOEA can be found in the following git repository7. A.4.1 Spread Metric 1package o rg . moeaframework . c or e . i n d i c a t o r ; 2 3import org . apac he . commons . math3 . s t a t . S t a t U t i l s ; 4import o rg . moeaframework . c o r e . N o nd o m i na t ed P op u la t i on ; 5import org . moeaframework . c or e . S o l u t i o n ; 6import o rg . moeaframework . c o r e . c o m pa r a t or . O b j e c t i v e C o m p a r a t o r ; 7import or g . moeaframework . c o r e . c om p ar a to r . L e x i c o g r a p h i c a l C o m p a r a t o r ; 8import o rg . moeaframework . c o r e . P ro blem ; 9 10 /∗ ∗ 11 ∗G e n e r a l i z e d S pr ea d m e t r i c . 12 ∗/ 13 p u b l i c c l a s s GeneralizedSpread extends N o r m a l i z e d I n d i c a t o r { 6https://github.com/Gan0k/MOEAFramework/ 7https://bitbucket.org/Ganok/moea-analysis/ A.4. Code Listings 80 96 } 97 } A.4.2 Parameter tuning for NSGA-II 1import j a v a . u t i l . L i s t ; 2import j a v a . i o . F i l e ; 3 4import org . moeaframework . E x e c u t o r ; 5import org . moeaframework . A nal yze r ; 6import o rg . moeaframework . c o r e . N o nd o m i na t ed P op u la t i on ; 7import org . moeaframework . c or e . S o l u t i o n ; 8import or g . moeaframework . c o r e . v a r i a b l e . E n c o d i n g U t i l s ; 9 10 p u b l i c c l a s s NSGAIIParam { 11 12 p r i v a t e s t a t i c vo id u sa ge ( ) { 13 System . e r r . p r i n t l n ( " Usage : NSGAIIParam " + 14 "−p PROBLEM_NAME −s POPULATION_SIZE " + 15 "−m MAX_FUNCS_EVAL −r NUMBER_SEEDS " + 16 "−s b x r SBX . RATE −sbxd SBX . DISTRIDX " + 17 "−pmidx PM. DISTRIDX −p r i n t v a r −p r i n t o b j " ) ; 18 System . e x i t ( −1) ; 19 } 20 21 p u b l i c s t a t i c vo id main ( S t r i n g [ ] a rg s ) { 22 S t r i n g algName = "NSGAII" ; 23 S t r i n g problemName = "Schaffer"; 24 int s e e d s = 100 , mfe = 1000 0 , p o p u l S i z e = 1 00 ; 25 do ubl e s b x r a t e = 1 . 0 , s bx i d x = 1 5 .0 , pmidx = 2 0 . 0 ; 26 boolean p r i n t v a r = false , p r i n t o b j = f a l s e ; 27 28 / / p ar s e ar gum en ts t o s e t o p t i o n s 29 int n = a r g s . l e n g t h ; 30 f o r (int i = 0; i < n ; ++ i ) { 31 i f ( a r g s [ i ] . e q u a l s ( "−s b x r " ) && i +1 < n ) 32 s b x r a t e = Double . va lueOf ( a r g s [++ i ] ) ; 33 e l s e i f ( a r g s [ i ] . e q u a l s ( "−sbxd " ) && i +1 < n ) 34 s bx i dx = Double . v alu eO f ( a r g s [++ i ] ) ; 35 e l s e i f ( a r g s [ i ] . e q u a l s ( "−p r i n t v a r " ) ) 36 p r i n t v a r = true ; 37 e l s e i f ( a r g s [ i ] . e q u a l s ( "−p r i n t o b j " ) ) 38 p r i n t o b j = true ; 39 e l s e i f ( a r g s [ i ] . e q u a l s ( "−pmidx" ) && i +1 < n ) 40 pmidx = Double . va lue Of ( a r g s [++ i ] ) ; 41 e l s e i f ( a r g s [ i ] . e q u a l s ( "−p " ) && i +1 < n ) A.4. Code Listings 81 42 problemName = a r g s [++ i ] ; 43 e l s e i f ( a r g s [ i ] . e q u a l s ( "−s " ) && i +1 < n ) 44 p o p u l S i z e = I n t e g e r . p a r s e I n t ( a r g s [++ i ] ) ; 45 e l s e i f ( a r g s [ i ] . e q u a l s ( "−m" ) && i +1 < n ) 46 mfe = I n t e g e r . p a r s e I n t ( a rg s [++ i ] ) ; 47 e l s e i f ( a r g s [ i ] . e q u a l s ( "−r " ) && i +1 < n ) 48 s e e d s = I n t e g e r . p a r s e I n t ( a rg s [++ i ] ) ; 49 else usage ( ) ; 50 } 51 52 F i l e f = new File(" . / t e s t s / p ara m _tu nin g / " + algName + "_" + 53 problemName + "_" + S t r i n g . va lu eOf ( se e ds ) ) ; 54 55 An alyz er a n a l y z e r = new Analyzer () 56 . withPro blem ( problemName ) 57 . includeInvertedGenerationalDistance () 58 . includeSpacing () 59 . includeGeneralizedSpread () 60 . includeR2 () 61 . i n c l u d e A d d i t i v e E p s i l o n I n d i c a t o r ( ) 62 . includeHypervolume () 63 . showStatisticalSignificance () ; 64 65 Execu t o r newparams = new E x e c u t o r ( ) 66 . withPro blem ( problemName ) 67 . withProperty ("populationSize" , populSize ) 68 . withProperty (" sbx . r a t e " , sbxrate) 69 . withProperty ("sbx. distributionIndex" , s b x i d x ) 70 . withProperty ("pm. distributionIndex" , pmidx ) 71 . withMaxEvaluations(mfe) 72 . w i t h A l g o r i t h m ( algName ) 73 . d i s t r i b u t e O n A l l C o r e s ( ) ; 74 75 E xe cu to r d e f a u l t p a r a m s = new E x e c u t o r ( ) 76 . withPro blem ( problemName ) 77 . withProperty ("populationSize" , populSize ) 78 . withMaxEvaluations(mfe) 79 . w i t h A l g o r i t h m ( algName ) 80 . d i s t r i b u t e O n A l l C o r e s ( ) ; 81 82 L i s t < Nondominat ed Po pulation > r e s u l t = newparams . ru n See ds ( s ee d s ) ; 83 84 i f ( p r i n t v a r ) { 85 f o r ( NondominatedPopulation pop : result ) { 86 f o r ( S o l u t i o n s o l u t i o n : pop ) { 87 System . o u t . f o r m a t ( " %.10 f " ,/ / d e c i m a l s ca n mod if y r e s u l t s ! A.4. Code Listings 82 88 E n c o d i n g U t i l s . g e t R e a l ( s o l u t i o n . g e t V a r i a b l e ( 0 ) ) ) ; 89 f o r (int i = 1; i < s o l u t i o n . ge tNu mbe rOf Va r ia ble s ( ) ; ++ i ) { 90 System . out . format ( " \ t %.10 f " , 91 E n c o d i n g U t i l s . g e t R e a l ( s o l u t i o n . g e t V a r i a b l e ( i ) ) ) ; 92 } 93 System . ou t . p r i n t l n ( ) ; 94 } 95 } 96 } 97 e l s e i f ( p r i n t o b j ) { 98 f o r ( NondominatedPopulation pop : result ) { 99 f o r ( S o l u t i o n s o l u t i o n : pop ) { 100 System . o u t . f o r m a t ( " %.10 f " , 101 s o l u t i o n . g e t O b j e c t i v e ( 0 ) ) ; 102 f o r (int i = 1; i < s o l u t i o n . ge t Num ber O fO b jec tiv e s ( ) ; ++ i ) { 103 System . out . format ( " \ t %.10 f " , 104 s o l u t i o n . g e t O b j e c t i v e ( i ) ) ; 105 } 106 System . ou t . p r i n t l n ( ) ; 107 } 108 } 109 } 110 111 a n a l y z e r . ad dAl l ( "New " + algName , r e s u l t ) ; 112 a n a l y z e r . ad dAl l ( "Default " + algName , d e f a u l t p a r a m s . run Se ed s ( s e ed s ) ) ; 113 114 try { 115 a n a l y z e r . s a v e A n a l y s i s ( f ) ; 116 }c a t c h ( Exce p t i o n e ) { 117 e . p r i n t S t a c k T r a c e ( ) ; 118 } 119 } 120 } A.4.3 Comparison of MOEA 1import j a v a . u t i l . L i s t ; 2import j a v a . u t i l . A r r a y L i s t ; 3import j a v a . i o . F i l e ; 4import j a va . i o . F i l e I n p u t S t r e a m ; 5import j a v a . i o . P r i n t W r i t e r ; 6import j a va . u t i l . P r o p e r t i e s ; 7import j a v a . u t i l . En ume ra tio n ; 8import j a v a . u t i l . HashMap ; 9import j a v a . u t i l . Map ; 10 A.4. Code Listings 83 11 import org . moeaframework . E x e c u t o r ; 12 import org . moeaframework . A nal yze r ; 13 import o rg . moeaframework . c o r e . N o nd o m i na t ed P op u la t i on ; 14 import org . moeaframework . c or e . S o l u t i o n ; 15 import or g . moeaframework . c o r e . v a r i a b l e . E n c o d i n g U t i l s ; 16 17 import or g . j f r e e . c h a r t . J F r e e C h a r t ; 18 import org . j f r e e . c h a r t . a x i s . Cat e go ry Ax is ; 19 import org . j f r e e . c h a r t . a x i s . NumberAxis ; 20 import org . j f r e e . c h a r t . l a b e l s . BoxAndWhiskerToolTipGenerator ; 21 import org . j f r e e . c h a r t . p l o t . C a t e g o r y P l o t ; 22 import org . j f r e e . c h a r t . r e n d e r e r . c a t e g o r y . BoxAndWhiskerRenderer ; 23 import org . j f r e e . d a t a . s t a t i s t i c s . BoxAndWhiskerCategoryDataset ; 24 import org . j f r e e . d a t a . s t a t i s t i c s . Def a ult B oxA ndW h isk e rCa t ego ryD a tas e t ; 25 import org . j f r e e . c h a r t . C h a r t U t i l i t i e s ; 26 27 p u b l i c c l a s s CompareDef { 28 29 p r i v a t e s t a t i c vo id u sa ge ( ) { 30 System . e r r . p r i n t l n ( " Usage : CompareDef " +"−m MAX_FUNCS_EVAL −r 31 NUMBER_SEEDS " ) ; 32 System . e x i t ( −1) ; 33 } 34 35 p r i v a t e s t a t i c vo id p r i n t S o l u t i o n s ( L i s t < Non dominated Po pu lation > r e s u l t , 36 S t r i n g algName , S t r i n g problemName , int seeds ) { 37 38 S t r i n g o b jS o l = " " ; 39 S t r i n g v a r i a b l e S o l = " " ; 40 boolean p r i n t v a r = t r u e , p r i n t o b j = true ; 41 42 f o r ( NondominatedPopulation pop : result ) { 43 f o r ( S o l u t i o n s o l u t i o n : pop ) { 44 i f ( s o l u t i o n . g etN umb erO fVa ria bl es ( ) > 3) { 45 p r i n t v a r = false ; 46 break ; 47 } 48 49 v a r i a b l e S o l += 50 S t r i n g . v al ue Of ( E n c o d i n g U t i l s . g e t R e a l ( s o l u t i o n . g e t V a r i a b l e ( 0 ) ) ) ; 51 f o r (int i = 1; i < s o l u t i o n . ge tNu mbe rOf Va r ia ble s ( ) ; ++ i ) { 52 v a r i a b l e S o l += " \ t " + 53 S t r i n g . v al ue Of ( E n c o d i n g U t i l s . g e t R e a l ( s o l u t i o n . g e t V a r i a b l e ( i ) ) ) ; 54 } 55 v a r i a b l e S o l += " \ n " ; 56 } A.4. Code Listings 84 57 } 58 59 f o r ( NondominatedPopulation pop : result ) { 60 f o r ( S o l u t i o n s o l u t i o n : pop ) { 61 i f ( s o l u t i o n . ge tNu m ber OfO bje c ti v es ( ) > 3 ) { 62 p r i n t o b j = false ; 63 break ; 64 } 65 66 o bj So l += S t r i n g . v al ue Of ( s o l u t i o n . g e t O b j e c t i v e ( 0 ) ) ; 67 f o r (int i = 1; i < s o l u t i o n . ge t Num ber O fO b jec tiv e s ( ) ; ++ i ) { 68 o b j S o l += " \ t " + S t r i n g . va lu eO f ( s o l u t i o n . g e t O b j e c t i v e ( i ) ) ; 69 } 70 o b j S o l += " \ n " ; 71 } 72 } 73 74 i f ( p r i n t o b j ) { 75 t r y ( P r i n t W r i t e r o u t = new P r i n t W r i t e r ( " . / t e s t s / compare / s e t s / " + 76 problemName + "_" + algName + " _ d e f _ o b j_ " + 77 S t r i n g . va lu eOf ( se e ds ) + " . s e t s " ) ) { 78 o ut . p r i n t l n ( o b j S o l ) ; 79 }c a t c h ( Exce p t i o n e ) { 80 e . p r i n t S t a c k T r a c e ( ) ; 81 } 82 } 83 i f ( p r i n t v a r ) { 84 t r y ( P r i n t W r i t e r o u t = new P r i n t W r i t e r ( " . / t e s t s / compare / s e t s / " + 85 problemName + "_" + algName + " _ d e f _ v a r_ " + 86 S t r i n g . va lu eOf ( se e ds ) + " . s e t s " ) ) { 87 out . p r i n t l n ( v a r i a b l e S o l ) ; 88 }c a t c h ( Exce p t i o n e ) { 89 e . p r i n t S t a c k T r a c e ( ) ; 90 } 91 } 92 } 93 94 p r i v a t e s t a t i c vo id s a v e B o x p l o t s ( A na l yz er problem , S t r i n g problemName , 95 int seeds) { 96 An al yz er . A n a l y z e r R e s u l t s r e s u l t s = problem . g e t A n a l y s i s ( ) ; 97 HashMap< S t r i n g , D e f au l tB o xA n dW h is k er C at e go r yD a ta s et > d a t a s e t m a p = 98 new HashMap< S t r i n g , D ef au lt Bo xA nd Wh is ke rC at eg or yD at as et > ( ) ; 99 100 f o r ( S t r i n g namealgo : r e s u l t s . g e t A l g o r i t h m s ( ) ) { 101 / / p ro du c es n i c e r b o x p l o t s 102 i f ( namealgo . e q u a l s ( "VEGA" ) ) c o n t i n u e ; A.4. Code Listings 85 103 104 A na ly ze r . A l g o r i t h m R e s u l t a l g o r e s = r e s u l t s . g e t ( namealgo ) ; 105 f o r ( S t r i n g n a me i n d i c a t o r : a l g o r e s . g e t I n d i c a t o r s ( ) ) { 106 An a lyz er . I n d i c a t o r R e s u l t i n d r e s = a l g o r e s . g et ( n a m e i n d i c a t o r ) ; 107 L i st <Double > v a l u e s = new A r r a y L i s t < Double > ( ) ; 108 f o r (do ubl e d : i n d r e s . g e t V a l u e s ( ) ) v a l u e s . add ( d ) ; 109 110 i f ( ! d a ta s e tm a p . c on t ai ns K ey ( n a m e i n d i c a t o r ) ) { 111 d a t a s e t m ap . p u t ( n a m e i n d i c a t o r , 112 new DefaultBoxAndWhiskerCategoryDataset () ) ; 113 } 114 d at a s et m ap . g e t ( n a m e i n d i c a t o r ) . add ( v al u es , " " , 115 namealgo . e q u a l s ( "IBEA−JMe t al " ) ? "IBEA" : 116 ( namealgo . e q u a l s ( "OMOPSO" ) ? " omopso " : namealgo ) ) ; 117 } 118 } 119 120 A na ly ze r . A l g o r i t h m R e s u l t a l g o r e s = r e s u l t s . g e t ( "NSGAII" ) ; 121 f o r ( S t r i n g n a me i n d i c a t o r : a l g o r e s . g e t I n d i c a t o r s ( ) ) { 122 Ca t ego r yA x is xAxis = new C a teg ory A xis ( "Algorithms") ; 123 xAxis . s etLowerMargin ( xAxis . getLowerMargin ( ) ∗0 . 2 ) ; 124 xAxis . se tUp pe rMa rg in ( xAxis . getUpperMargin ( ) ∗0 . 2 ) ; 125 NumberAxis yAxis = new NumberAxis ( n a m e i n d i c a t o r + " Value" ) ; 126 BoxAndWhiskerRenderer renderer = new BoxAndWhiskerRenderer () ; 127 r e n d e r e r . s e t M e a n V i s i b l e ( f a l s e ) ; 128 r e n d e r e r . s e t U s e O u t l i n e P a i n t F o r W h i s k e r s ( true ) ; 129 yAxis . setAutoRangeIncludesZero ( false ) ; 130 CategoryPlot plot = 131 new C a t e g o r y P l o t ( d a ta s e tm a p . g e t ( n a m e i n d i c a t o r ) , xAxis , yAxis , 132 r e n d e r e r ) ; 133 J F r e e C h a r t c h a r t = new J F r e e C h a r t ( problemName + " " + 134 n a m e i n d i c a t o r , p l o t ) ; 135 136 F i l e img = new File(" . / t e s t s / compare / b o x p l o t s / " + problemName + 137 " _def_ " + n a m e i n d i c a t o r + "_" + S t r i n g . val ue Of ( s ee ds ) + 138 " . png " ) ; 139 t r y { 140 C h a r t U t i l i t i e s . saveChartAsPNG ( img , c h a r t , 9 6 0 , 6 40 ) ; 141 }c a t c h ( Exce p t i o n e ) { 142 e . p r i n t S t a c k T r a c e ( ) ; 143 } 144 } 145 } 146 147 p u b l i c s t a t i c vo id main ( S t r i n g [ ] a rg s ) { 148 S t r i n g [ ] algNames = { " NSGAII" ,"DBEA" ,"MOEAD" ,"GDE3" ,"OMOPSO" , A.4. Code Listings 86 149 "SMPSO" ,"SPEA2" ,"VEGA" ,"eMOEA" ,"eNSGAII" ," Abyss " ,"PAES" , 150 "PESA2" ,"MOCell" ," CellDE " ,"IBEA−J Met al " ,"CMA−ES" ,"NSGAIII" } ; 151 S t r i n g [ ] problemNames = { "Schaffer" ,"Schaffer2" ," Fonseca " , 152 " Fonseca2 " ," Kursawe " ,"OKA1" ,"OKA2" ,"ZDT1" ,"ZDT2" ,"ZDT3" , 153 "ZDT4" ,"ZDT5" ,"ZDT6" ,"DTLZ1_2" ,"DTLZ2_2" ,"DTLZ3_2" , 154 "DTLZ4_2" ,"DTLZ7_2" ,"DTLZ1_3" ,"DTLZ2_3" ,"DTLZ3_3" ,"DTLZ4_3" , 155 "DTLZ7_3" ,"WFG1_2" ,"WFG2_2" ,"WFG3_2" ,"WFG4_2" ,"WFG5_2" , 156 "WFG6_2" ,"WFG7_2" ,"WFG8_2" ,"WFG9_2" ,"WFG1_3" ,"WFG2_3" , 157 "WFG3_3" ,"WFG4_3" ,"WFG5_3" ,"WFG6_3" ,"WFG7_3" ,"WFG8_3" , 158 "WFG9_3" } ; 159 160 An a lyz er [ ] problems = new A naly zer [ problemNames . l e n g t h ] ; 161 int s e e d s = 100 , mfe = 1 00 00 ; 162 163 / / p ar s e ar gum en ts t o s e t o p t i o n s 164 int n = a r g s . l e n g t h ; 165 f o r (int i = 0; i < n ; ++ i ) { 166 i f ( a r g s [ i ] . e q u a l s ( "−m" ) && i +1 < n ) 167 mfe = I n t e g e r . p a r s e I n t ( a rg s [++ i ] ) ; 168 e l s e i f ( a r g s [ i ] . e q u a l s ( "−r " ) && i +1 < n ) 169 s e e d s = I n t e g e r . p a r s e I n t ( a rg s [++ i ] ) ; 170 else usage ( ) ; 171 } 172 173 / / i n i t i a l i z e a n a l y z e r s 174 f o r (int i = 0; i < problemNames . l e n g t h ; ++ i ) { 175 problem s [ i ] = new Analyzer () 176 . withP ro blem ( problemNames [ i ] ) 177 . includeGenerationalDistance () 178 . includeInvertedGenerationalDistance () 179 . includeSpacing () 180 . includeGeneralizedSpread () 181 . includeR2 () 182 . i n c l u d e A d d i t i v e E p s i l o n I n d i c a t o r ( ) 183 . includeHypervolume () 184 . showStatisticalSignificance () ; 185 } 186 187 / / s t o r e e x e c u t i o n t ime o f a l g o r i t h m s 188 HashMap< S t r i n g , HashMap< S t r i n g , Double >> avgTime = 189 new HashMap< S t r i n g , HashMap< S t r i n g , Double > >() ; 190 191 / / e v a l u a t e eac h a l g o r i t h m f o r eac h problem 192 f o r ( S t r i n g algName : algNames ) { 193 P r o p e r t i e s p r o p e r t i e s = new Properties () ; 194 A.4. Code Listings 87 195 t r y { 196 F i l e p r o p f i l e = new File (" . / t e s t s / compare / a l g _ c o n f i g / " + 197 algName + " _d ef . c o n f i g " ) ; 198 199 i f ( p r o p f i l e . e x i s t s ( ) && ! p r o p f i l e . i s D i r e c t o r y ( ) ) { 200 FileInputStream inp = new F i l e I n p u t S t r e a m ( p r o p f i l e ) ; 201 p r o p e r t i e s . l o a d ( inp ) ; 202 inp . c l o s e ( ) ; 203 } 204 205 }c a t c h ( Exce p t i o n e ) { 206 e . p r i n t S t a c k T r a c e ( ) ; 207 } 208 209 f o r (int i = 0; i < problemNames . l e n g t h ; ++ i ) { 210 / / s ki p pro bl ems t h a t do not s u p p o r t b i n a r y v a r i a b l e s 211 i f ( problemNames [ i ] . e q u a l s ( "ZDT5" ) && 212 ( algName . e q u a l s ( "GDE3" ) | | algName . e q u a l s ( "MOEAD" ) | | 213 algName . e q u a l s ( "SMPSO" ) | | algName . e q u a l s ( " Abyss " ) | | 214 algName . e q u a l s ( "CMA−ES" ) | | algName . e q u a l s ( "OMOPSO" ) | | 215 algName . e q u a l s ( " CellDE " ))) continue ; 216 217 i f ( ( problemNames [ i ] . e q u a l s ( " Fonseca " ) && 218 algName . e q u a l s ( "CMA−ES" ) ) | | 219 ( problemNames [ i ] . c o n t a i n s ( "WFG" ) && 220 problemNames [ i ] . c o n t a i n s ( " _3 " ) && 221 algName . e q u a l s ( "eMOEA" ) ) | | 222 ( problemNames [ i ] . c o n t a i n s ( "WFG" ) && 223 problemNames [ i ] . c o n t a i n s ( " _3 " ) && 224 algName . e q u a l s ( "CMA−ES" ) ) | | 225 ( problemNames [ i ] . c o n t a i n s ( "WFG" ) && 226 problemNames [ i ] . c o n t a i n s ( " _3 " ) && 227 algName . e q u a l s ( "eNSGAII" ))) continue ; 228 229 Execu t o r exec = new E x e c utor ( ) 230 . withP ro blem ( problemNames [ i ] ) 231 . withMaxEvaluations(mfe) 232 . w i t h A l g o r i t h m ( algName ) 233 . d i s t r i b u t e O n A l l C o r e s ( ) ; 234 235 / / l oop thr o u g h s e t p r o p e r t i e s and s e t them 236 Enumeration <?> e = p r o p e r t i e s . prop ert yNames ( ) ; 237 while (e . hasMoreElements () ) { 238 S t r i n g key = ( S t r i n g ) e . n extE leme nt ( ) ; 239 exec . w i t h P r o p e r t y ( key , p r o p e r t i e s . g e t P r o p e r t y ( key ) ) ; 240 } A.4. Code Listings 88 241 242 lo ng s t a r t = System . nanoTime ( ) ; 243 L i s t < Nondominat ed Po pulation > r e s u l t = exec . r u nSe eds ( s e e ds ) ; 244 lo ng el ap s ed Tim e = System . nanoTime ( ) −start ; 245 do ubl e s econ d s = ( ( d oub le ) e la p se dTi me / 1 e9 ) ; 246 i f ( ! avgTime . c o n t a i n s K e y ( problemNames [ i ] ) ) 247 avgTime . p ut ( problemNames [ i ] , 248 new HashMap< S t r i n g , Double > ( ) ) ; 249 avgTime . g e t ( problemNames [ i ] ) . p u t ( algName , s e co n ds / s e e d s ) ; 250 251 p r i n t S o l u t i o n s ( r e s u l t , algName , problemNames [ i ] , s ee d s ) ; 252 problem s [ i ] . ad dAl l ( algName , r e s u l t ) ; 253 254 System . ou t . p r i n t l n ( algName + " " + problemNames[ i ] + 255 " c omp le ted " ) ; 256 } 257 } 258 259 / / s ave a n a l y s i s 260 f o r (int i = 0; i < problemNames . l e n g t h ; ++ i ) { 261 262 s a v e B o x p l o t s ( p ro bl em s [ i ] , problemNames [ i ] , s e e d s ) ; 263 264 / / s ave f i l e a n a l y s i s 265 F i l e f = new F i l e ( " . / t e s t s / compare / a n a l y s i s / " + problemNames[ i ] + 266 " _def_ " + S t r i n g . val ue Of ( s ee ds ) + ". metrics") ; 267 t r y { 268 pr ob lem s [ i ] . s a v e A n a l y s i s ( f ) ; 269 }c a t c h ( Exce p t i o n e ) { 270 e . p r i n t S t a c k T r a c e ( ) ; 271 } 272 273 / / s av e f i l e a v er a ge e l a p s e d ti me 274 t r y ( P r i n t W r i t e r o u t = new P r i n t W r i t e r ( " . / t e s t s / compare / tim e / " + 275 problemNames[ i ] + " _d ef _ " + S t r i n g . v alueO f ( s ee ds ) + 276 " . tim e " ) ) { 277 f o r ( Map . Entr y < S t r i n g , Double > e n t r y : 278 avgTime . g e t ( problemNames [ i ] ) . e n t r y S e t ( ) ) { 279 out . p r i n t l n ( e n t r y . getKey ( ) + " " + e n t r y . g et Va lu e ( ) ) ; 280 } 281 }c a t c h ( Exce p t i o n e ) { 282 e . p r i n t S t a c k T r a c e ( ) ; 283 } 284 } 285 286 } A.5. Project Plan 89 287 } A.5 Project Plan Bibliography 96 [12] Kalyanmoy Deb, Samir Agrawal, Amrit Pratap, and Tanaka Meyarivan. A fast elitist nondominated sorting genetic algorithm for multi-objective optimization: Nsga-ii. In Parallel problem solving from nature PPSN VI, pages 849–858. Springer, 2000. [13] Joshua D Knowles and David W Corne. Approximating the nondominated front using the pareto archived evolution strategy. Evolutionary computation, 8(2):149–172, 2000. [14] Eckart Zitzler, Marco Laumanns, and Lothar Thiele. Spea2: Improving the strength pareto evolutionary algorithm for multiobjective optimization. In Evolutionary Methods for Design, Optimisation, and Control, pages 95–100. CIMNE, Barcelona, Spain, 2002. [15] David W. Corne, Nick R. Jerram, Joshua D. Knowles, Martin J. Oates, and Martin J. Pesa-ii: Region-based selection in evolutionary multiobjective optimization. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 2001), pages 283–290. Morgan Kaufmann Publishers, 2001. [16] Patrick Reed, Barbara S Minsker, and David E Goldberg. Simplifying multiobjective optimization: An automated design methodology for the nondominated sorted genetic algorithm-ii. Water Resources Research, 39(7), 2003. [17] Eckart Zitzler and Simon Künzli. Indicator-based selection in multiobjective search. In in Proc. 8th International Conference on Parallel Problem Solving from Nature (PPSN VIII, pages 832–842. Springer, 2004. [18] Qingfu Zhang and Hui Li. Moea/d: A multiobjective evolutionary algorithm based on decomposition. Evolutionary Computation, IEEE Transactions on, 11(6):712–731, 2007. [19] Kaushik Deb and Himanshu Jain. An evolutionary many-objective optimization algorithm using reference-point-based nondominated sorting approach, part i: Solving problems with box constraints. Evolutionary Computation, IEEE Transactions on, 18(4):577–601, 2014. [20] Md Asafuddoula, Tapabrata Ray, and Ruhul Sarker. A decomposition-based evolutionary algorithm for many objective optimization. Evolutionary Computation, IEEE Transactions on, 19(3):445–460, 2015. [21] Margarita Reyes Sierra and Carlos A. Coello Coello. Improving pso-based multi-objective optimization using crowding, mutation and -dominance. In Proceedings of the Third International Conference on Evolutionary Multi-Criterion Optimization, EMO’05, pages 505–519, Berlin, Heidelberg, 2005. Springer-Verlag. [22] Antonio J Nebro, Juan José Durillo, Jose Garcia-Nieto, C Coello, Francisco Luna, and Enrique Alba. Smpso: A new pso-based metaheuristic for multi-objective optimization. In Computational intelligence in miulti-criteria decision-making, 2009. mcdm’09. ieee symposium on, pages 66–73. IEEE, 2009. Bibliography 97 [23] Antonio J. Nebro, Juan J. Durillo, Francisco Luna, Bernabé Dorronsoro, and Enrique Alba. Mocell: A cellular genetic algorithm for multiobjective optimization. International Journal of Intelligent Systems, pages 25–36, 2007. [24] Juan José Durillo, Antonio Jesús Nebro, Francisco Luna, and Enrique Alba. Solving threeobjective optimization problems using a new hybrid cellular genetic algorithm. In Parallel problem solving from nature–PPSN X, pages 661–670. Springer, 2008. [25] Kenneth Price, Rainer M Storn, and Jouni A Lampinen. Differential evolution: a practical approach to global optimization. Springer Science & Business Media, 2006. [26] Saku Kukkonen and Kalyanmoy Deb. Improved pruning of non-dominated solutions based on crowding distance for bi-objective optimization problems. In Evolutionary Computation, 2006. CEC 2006. IEEE Congress on, pages 1179–1186. IEEE, 2006. [27] Saku Kukkonen and Jouni Lampinen. Gde3: The third evolution step of generalized differential evolution. In Evolutionary Computation, 2005. The 2005 IEEE Congress on, volume 1, pages 443–450. IEEE, 2005. [28] Christian Igel, Nikolaus Hansen, and Stefan Roth. Covariance matrix adaptation for multiobjective optimization. Evol. Comput., 15(1):1–28, March 2007. [29] Antonio J Nebro, Francisco Luna, Enrique Alba, Bernabé Dorronsoro, Juan J Durillo, and Andreas Beham. Abyss: Adapting scatter search to multiobjective optimization. Evolutionary Computation, IEEE Transactions on, 12(4):439–457, 2008. [30] Pradyumn Kumar Shukla and Kalyanmoy Deb. On finding multiple pareto-optimal solutions using classical and evolutionary generating methods. European Journal of Operational Research, 181(3):1630–1652, 2007. [31] Juan J Durillo and Antonio J Nebro. jmetal: A java framework for multi-objective optimization. Advances in Engineering Software, 42(10):760–771, 2011. [32] Stefan Bleuler, Marco Laumanns, Lothar Thiele, and Eckart Zitzler. PISA — a platform and programming language independent interface for search algorithms. In Carlos M. Fonseca, Peter J. Fleming, Eckart Zitzler, Kalyanmoy Deb, and Lothar Thiele, editors, Evolutionary Multi-Criterion Optimization (EMO 2003), Lecture Notes in Computer Science, pages 494 – 508, Berlin, 2003. Springer. [33] Arnaud Liefooghe, Matthieu Basseur, Laetitia Jourdan, and El-Ghazali Talbi. Paradiseo-moeo: A framework for evolutionary multi-objective optimization. In Evolutionary multi-criterion optimization, pages 386–400. Springer, 2007. Bibliography 98 [34] Kalyanmoy Deb, Lothar Thiele, Marco Laumanns, and Eckart Zitzler. Scalable multi-objective optimization test problems. In Evolutionary Computation, 2002. CEC’02. Proceedings of the 2002 Congress on, volume 1, pages 825–830. IEEE, 2002. [35] Simon Huband, Phil Hingston, Luigi Barone, and Lyndon While. A review of multiobjective test problems and a scalable test problem toolkit. Evolutionary Computation, IEEE Transactions on, 10(5):477–506, 2006. [36] Carlos M Fonseca and Peter J Fleming. Multiobjective genetic algorithms made easy: selection sharing and mating restriction. In Genetic Algorithms in Engineering Systems: Innovations and Applications, 1995. GALESIA. First International Conference on (Conf. Publ. No. 414), pages 45–52. IET, 1995. [37] Tatsuya Okabe, Yaochu Jin, Markus Olhofer, and Bernhard Sendhoff. On test functions for evolutionary multi-objective optimization. In Parallel Problem Solving from Nature-PPSN VIII, pages 792–802. Springer, 2004. [38] Carlos M Fonseca, Joshua D Knowles, Lothar Thiele, and Eckart Zitzler. A tutorial on the performance assessment of stochastic multiobjective optimizers. In Third International Conference on Evolutionary Multi-Criterion Optimization (EMO 2005), volume 216, page 240, 2005. [39] Eckart Zitzler, Lothar Thiele, Marco Laumanns, Carlos M Fonseca, and Viviane Grunert Da Fonseca. Performance assessment of multiobjective optimizers: an analysis and review. Evolutionary Computation, IEEE Transactions on, 7(2):117–132, 2003. [40] Jason R Schott. Fault tolerant design using single and multicriteria genetic algorithm optimization. Technical report, DTIC Document, 1995. [41] Aimin Zhou, Yaochu Jin, Qingfu Zhang, Bernhard Sendhoff, and Edward Tsang. Combining model-based and genetics-based offspring generation for multi-objective optimization using a convergence criterion. In Evolutionary Computation, 2006. CEC 2006. IEEE Congress on, pages 892–899. IEEE, 2006. [42] Ali Farhang-Mehr and Shapour Azarm. An information-theoretic entropy metric for assessing multi-objective optimization solution set quality. Journal of Mechanical Design, 125(4):655– 663, 2003. [43] Miqing Li, Shengxiang Yang, and Xiaohui Liu. Diversity comparison of pareto front approximations in many-objective optimization. Cybernetics, IEEE Transactions on, 44(12):2568–2584, 2014. Bibliography 99 [44] Joshua Knowles and David Corne. On metrics for comparing nondominated sets. In Evolutionary Computation, 2002. CEC’02. Proceedings of the 2002 Congress on, volume 1, pages 711–716. IEEE, 2002. [45] Carlos A Coello Coello and Nareli Cruz Cortés. Solving multiobjective optimization problems using an artificial immune system. Genetic Programming and Evolvable Machines, 6(2):163– 190, 2005. [46] Giovanni Lizarraga-Lizarraga, Arturo Hernandez-Aguirre, and Salvador Botello-Rionda. Gmetric: an m-ary quality indicator for the evaluation of non-dominated sets. In Proceedings of the 10th annual conference on Genetic and evolutionary computation, pages 665–672. ACM, 2008. [47] Oliver Schütze, Xavier Esquivel, Adriana Lara, and Carlos A Coello Coello. Using the averaged hausdorff distance as a performance measure in evolutionary multiobjective optimization. Evolutionary Computation, IEEE Transactions on, 16(4):504–522, 2012. [48] David A Van Veldhuizen and Gary B Lamont. Evolutionary computation and convergence to a pareto front. In Late breaking papers at the genetic programming 1998 conference, pages 221–228. Citeseer, 1998. [49] Michael Pilegaard Hansen and Andrzej Jaszkiewicz. Evaluating the quality of approximations to the non-dominated set. IMM, Department of Mathematical Modelling, Technical Universityof Denmark, 1998. [50] Kalyanmoy Deb and Ram B Agrawal. Simulated binary crossover for continuous search space. Complex Systems, 9(3):1–15, 1994. [51] Qingfu Zhang, Aimin Zhou, Shizheng Zhao, Ponnuthurai Nagaratnam Suganthan, Wudong Liu, and Santosh Tiwari. Multiobjective optimization test instances for the cec 2009 special session and competition. University of Essex, Colchester, UK, 264, 2008. [52] Tea Tusar, Dimo Brockhoff, Nikolaus Hansen, and Anne Auger. Coco: The bi-objective black box optimization benchmarking (bbob-biobj) test suite. arXiv preprint arXiv:1604.00359, 2016. [53] Ke Li, Kalyanmoy Deb, Qingfu Zhang, and Sam Kwong. An evolutionary many-objective optimization algorithm based on dominance and decomposition. Evolutionary Computation, IEEE Transactions on, 19(5):694–716, 2015. [54] MD Nasir, Arnab Kumar Mondal, Soumyadip Sengupta, Swagatam Das, and Ajith Abraham. An improved multiobjective evolutionary algorithm based on decomposition with fuzzy dominance. In Evolutionary Computation (CEC), 2011 IEEE Congress on, pages 765–772. IEEE, 2011.