Arts and Sciences, Irving K. Barber School of (Okanagan)
Computer Science, Mathematics, Physics and Statistics, Department of (Okanagan)
DSpace
UBCO
Nadeau, Patrick Charles
Master of Science - MSc
University of British Columbia
An algorithm for finding approximations to Pareto fronts in the optimization of multiple objective functions is presented. A mesh of weighted sums of the multiple objective functions serves as a model to approximate the Pareto front. The Nelder-Mead algorithm then solves these individual weighted sums without the use of derivatives. This multiobjective Nelder-Mead algorithm was found to be competitive with current algorithms on convex problems.
Multiobjective Nelder-MeadAlgorithm Using a Mesh-Map ofWeighted SumsbyPatrick Charles NadeauB.Mat. Hons., Carleton University, 2009A THESIS SUBMITTED IN PARTIAL FULFILLMENT OFTHE REQUIREMENTS FOR THE DEGREE OFMASTER OF SCIENCEinTHE COLLEGE OF GRADUATE STUDIES(Computer Science)THE UNIVERSITY OF BRITISH COLUMBIA(Okanagan)June 2020© Patrick Charles Nadeau, 2020The following individuals certify that they have read, and recommendto the College of Graduate Studies for acceptance, a thesis/dissertation en-titled:Multiobjective Nelder-Mead Algorithm Using a Mesh-Map of Weighted Sumssubmitted by Patrick Charles Nadeau in partial fulfilment of the re-quirements of the degree of Master of ScienceWarren Hare, Irving K. Barber School of Arts and SciencesSupervisorWayne Broughton, Irving K. Barber School of Arts and SciencesSupervisory Committee MemberApurva Narayan, Irving K. Barber School of Arts and SciencesSupervisory Committee MemberAbbas Milani, School of EngineeringUniversity ExamineriiAbstractAn algorithm for finding approximations to Pareto fronts in the opti-mization of multiple objective functions is presented. A mesh of weightedsums of the multiple objective functions serves as a model to approximatethe Pareto front. The Nelder-Mead algorithm then solves these individualweighted sums without the use of derivatives. This multiobjective Nelder-Mead algorithm was found to be competitive with current algorithms onconvex problems.iiiLay SummaryThis work tries to get to the bottom of many things at once using trian-gles.ivTable of ContentsAbstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iiiLay Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ivTable of Contents . . . . . . . . . . . . . . . . . . . . . . . . . . . vList of Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viiList of Figures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viiiAcknowledgements . . . . . . . . . . . . . . . . . . . . . . . . . . xDedication . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xiChapter 1: Introduction . . . . . . . . . . . . . . . . . . . . . . . 11.1 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . 21.1.1 Multiobjective Optimization . . . . . . . . . . . . . . 31.1.2 The Weighted Sum Method . . . . . . . . . . . . . . . 41.1.3 Simplices . . . . . . . . . . . . . . . . . . . . . . . . . 41.1.4 Motivation and Contribution . . . . . . . . . . . . . . 4Chapter 2: Multiobjective Nelder-Mead Algorithm . . . . . . 52.1 The Original Nelder-Mead Algorithm . . . . . . . . . . . . . . 52.2 The Mesh-Map . . . . . . . . . . . . . . . . . . . . . . . . . . 72.3 The Multiobjective Nelder-Mead Algorithm . . . . . . . . . . 9Chapter 3: Test Environment . . . . . . . . . . . . . . . . . . . 113.1 Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113.1.1 Random Search . . . . . . . . . . . . . . . . . . . . . . 113.1.2 Grid Search . . . . . . . . . . . . . . . . . . . . . . . . 123.1.3 Multi-Objective Particle Swarm Optimization . . . . . 12vTABLE OF CONTENTS3.1.4 Non-dominated Sorting Genetic Algorithm Version 2 . 133.2 Metrics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133.2.1 Set Domination . . . . . . . . . . . . . . . . . . . . . . 133.2.2 Hypervolume . . . . . . . . . . . . . . . . . . . . . . . 143.2.3 Contribution . . . . . . . . . . . . . . . . . . . . . . . 143.2.4 Epsilon Indicator . . . . . . . . . . . . . . . . . . . . . 153.3 Test Sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 163.3.1 Wikipedia . . . . . . . . . . . . . . . . . . . . . . . . . 163.3.2 DTLZ . . . . . . . . . . . . . . . . . . . . . . . . . . . 173.3.3 Quadratics . . . . . . . . . . . . . . . . . . . . . . . . 173.3.4 Quadratics PSD . . . . . . . . . . . . . . . . . . . . . 173.3.5 Sine Polynomials . . . . . . . . . . . . . . . . . . . . . 173.4 Data Sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 183.4.1 Quadratics PSD Data Sets . . . . . . . . . . . . . . . 183.4.2 Quadratics Data Sets . . . . . . . . . . . . . . . . . . 193.4.3 Sine Polynomials Data Sets . . . . . . . . . . . . . . . 193.4.4 Wikipedia Data Set . . . . . . . . . . . . . . . . . . . 193.4.5 DTLZ Data Sets . . . . . . . . . . . . . . . . . . . . . 193.4.6 Summary of Data Sets . . . . . . . . . . . . . . . . . . 20Chapter 4: Test Results . . . . . . . . . . . . . . . . . . . . . . . 214.1 Time and Failure Results . . . . . . . . . . . . . . . . . . . . 214.2 Metric Results . . . . . . . . . . . . . . . . . . . . . . . . . . 224.2.1 Accuracy Profiles . . . . . . . . . . . . . . . . . . . . . 234.2.2 Quadratics PSD Data Sets . . . . . . . . . . . . . . . 244.2.3 Summary of Convex Data Sets . . . . . . . . . . . . . 264.2.4 Quadratics . . . . . . . . . . . . . . . . . . . . . . . . 274.2.5 Sine Polynomials . . . . . . . . . . . . . . . . . . . . . 274.2.6 Summary of Higher Dimension Data Sets . . . . . . . 284.2.7 Wikipedia . . . . . . . . . . . . . . . . . . . . . . . . . 294.2.8 DTLZ . . . . . . . . . . . . . . . . . . . . . . . . . . . 304.2.9 Summary of Non-convex Data Sets . . . . . . . . . . . 314.3 Mesh-Map Results . . . . . . . . . . . . . . . . . . . . . . . . 31Chapter 5: Conclusion . . . . . . . . . . . . . . . . . . . . . . . . 32Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34viList of TablesTable 3.1 A summary of the data sets used for analysis in Chap-ter 4. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20Table 4.1 A summary of the running time statistics for the mergeddata of sets 1, 2, and 3, the combination of convexQuadratics PSD data sets. . . . . . . . . . . . . . . . . 22Table 4.2 A summary of the running time statistics for the mergeddata of sets 4 to 17, the combination of non-convexdata sets. . . . . . . . . . . . . . . . . . . . . . . . . . 22viiList of FiguresFigure 2.1 Illustrations of mesh-maps on a sphere with two rings,four rings, six rings, and eight rings. . . . . . . . . . . 8Figure 3.1 Illustrations of the Hypervolume, Contribution, andEpsilon Indicator metrics. . . . . . . . . . . . . . . . . 16Figure 4.1 Examples of Accuracy profiles with labelled axes. . . 23Figure 4.2 Accuracy profiles of the metrics applied to data set1 from the Quadratics PSD test set with (n,m) =(1–3, 2). . . . . . . . . . . . . . . . . . . . . . . . . . . 24Figure 4.3 Accuracy profiles of the metrics applied to data set2 from the Quadratics PSD test set with (n,m) =(1–3, 3). . . . . . . . . . . . . . . . . . . . . . . . . . . 25Figure 4.4 Accuracy profiles of the metrics applied to data set3 from the Quadratics PSD test set with (n,m) =(1–10, 2–10). . . . . . . . . . . . . . . . . . . . . . . . 25Figure 4.5 Accuracy profiles of the metrics applied to the mergeddata of sets 1, 2, and 3 from the Quadratics PSD testset, a convex data set. . . . . . . . . . . . . . . . . . . 26Figure 4.6 Accuracy profiles of the metrics applied to the mergeddata of sets 4, 5, and 6 from the Quadratics test set. . 27Figure 4.7 Accuracy profiles of the metrics applied to the mergeddata of sets 7, 8, and 9 from the Sine Polynomials testset. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28Figure 4.8 Accuracy profiles of the metrics applied to the mergeddata of sets 3, 6, and 9 with (n,m) = (1–10, 2–10). . . 29Figure 4.9 Accuracy profiles of the metrics applied to data set10 from the Wikipedia test set. . . . . . . . . . . . . . 30Figure 4.10 Accuracy profiles of the metrics applied to the mergeddata of sets 11 to 17 from the DTLZ test set. . . . . . 30viiiLIST OF FIGURESFigure 4.11 Accuracy profiles of the metrics applied to the mergeddata of sets 4 to 17, a mostly non-convex data set. . . 31ixAcknowledgementsNadeau’s research is partially funded by NSERC of Canada, DiscoverGrant #2018-03865 and the University of British Colubmia.xDedicationTo AnnexiChapter 1IntroductionOn January 1st, 1965, The Computer Journal published an article byJ. A. Nelder and R. Mead entitled A simplex method for function mini-mization. In this article, Nelder and Mead proposed an algorithm usingsequences of simplices to find the minimum value of a mathematical func-tion of several variables [NM65]. This algorithm was adapted from the workof Spendley, Hext, and Himsworth who used simplices and a reflection ofone of its points through a hyperplane of the remaining points to solve anoptimization problem [SHH62]. In the decades since its publication, thesimplex method proposed by Nelder and Mead came to be known as theNelder-Mead algorithm.The minimization of a mathematical function is part of the field of singleobjective optimization. A related field of study is that of multiple objectiveoptimization. The set of multiple objective functions form a vector-valuedfunction whose range is a vector space. The vectors in this range, or objectivespace, are then compared using the concept of Pareto optimality. The vectorsin the objective space that are Pareto optimal form the Pareto front, andthis Pareto front is the solution to the problem.In the decades that followed Nelder and Mead’s publication, researchersalso made progress in multiple objective optimization. The method of properequality constraints to solve multiple objective problems was presented byLin in 1976 [Lin76]. This method reduces a multiple objective problem intoa set of single objective problems with equality constraints. The equalityconstraints are made by fixing an equality on all but one of the multipleobjective functions. The method was then used to find the solution toseveral multiobjective problems in various fields of research.The use of convex weighted sums of the objective functions later be-came a standard technique in multiobjective optimization. Das and Dennisexplored the geometric perspectives of weighted sums in 1997 noting thetechnique’s drawbacks on non-convex Pareto fronts and in Pareto front dis-tributions [DD97].Recently, Audet and Tribes used an adapted Nelder-Mead algorithm inbi-objective optimization problems [AT18] and Mehta and Dasgupta used1INTRODUCTIONthe Nelder-Mead algorithm in a population-based multiobjective method[MD20]. In Audet and Tribes’ work, the single objective function problemwas linked to a second objective function made from a progressive barrierconstraint function. When the algorithm minimized the two functions intoa feasible region where the constraints were satisfied, the problem returnedto its original single objective form to be solved by another part of the algo-rithm. In Mehta and Dasgupta’s work, a number of simplices are initializedfrom an initial population of points in the search space. These simplicesindividually perform iterations of the Nelder-Mead algorithm with simplexvertices compared using the concepts of domination and crowding distance.The algorithms from Audet and Tribes, from Mehta and Dasgupta, andfrom Nelder and Mead optimize problems without the use of gradient in-formation. Simlex methods may provide an approximation of the local cur-vature that can guide the choice of the next candidate trial point. Thesederivative-free methods are desirable for problems in which gradient infor-mation may not be available. Following the work that has preceded it, thisthesis adapts the Nelder-Mead algorithm to solve unconstrained derivative-free multiobjective optimization problems using weighted sums.The thesis is structured as follows. The following section, Section 1.1,provides terminology necessary for understanding the work herein. Chapter2 presents the multiobjective version of the Nelder-Mead algorithm. Chapter3 describes the environment in which the multiobjective Nelder-Mead algo-rithm was tested and the data sets that were produced. Chapter 4 presentsthe results of the analysis of the data sets. Finally, a conclusion summarizesthe important points of this thesis and suggests possible avenues of research.1.1 PreliminariesThe following terminology is adopted for the description of the multi-objective version of the Nelder-Mead algorithm. The first subsection in-troduces multiobjective optimization and the associated concept of Paretodominance. The second subsection explains the method of weighted sums.Finally, the third section defines simplices used in the Nelder-Mead algo-rithm and simplifies notation for evaluating a simplex.2INTRODUCTION1.1.1 Multiobjective OptimizationA multiobjective optimization problem with no constraints and the goalof minimizing the objective functions has the formminx∈Ωfi(x) i ∈ {1, 2, ...,m}where Ω ⊆ Rn is the search space and the functions fi are the objectivefunctions to be minimized. The objective functions fi are combined into avector-valued functionF : Rn → Rm such that F (x) = (f1(x), f2(x), ..., fm(x)).Pareto dominance is defined on the objective space Rm to obtain a subsetof Pareto optimal points in the image of F that form the solution to themultiobjective problem. A point b ∈ Rm is said to be dominated by a pointa ∈ Rm if ai ≤ bi for each index i ∈ {1, 2, ...,m} with at least one inequalitybeing strict.The Pareto front of a multiobjective optimization problem is the setF = {F (x∗) ∈ Rm | x∗ ∈ Ω ∀x ∈ Ω F (x∗) is not dominated by F (x)}and represents the solution to the multiobjective problem. Given sets Vx ⊂Ω and VF ⊂ Rm representing the visited domain and objective space pointsof an algorithm on a problem, the approximation set defined asA = {F (xk) ∈ VF | xk ∈ Vx ∀x ∈ Vx F (xk) is not dominated by F (x)}is the subset of the algorithm’s visited points that best approximates thePareto front. This approximation set represents the algorithm’s solution tothe problem. That is, an algorithm working on a multiobjective problemwith a Pareto front of F tries to approximate F with A.A Pareto front F is said to be convex when the set D = {x ∈ Rm | ∃p ∈F p dominates x} of points dominated by F is convex [ED18, p. 591].Furthermore, a Pareto front F is said to have a locally convex region atx ∈ F when ∃ > 0 such that B(x) ∩D is convex, where D is as above andB(x) = {x˜ ∈ Rm | ||x− x˜|| < } is the ball around x of radius .Lastly, two important definitions connected to Pareto fronts and ap-proximation sets are the utopia and anti-utopia points (also called ideal andnadir points). Given a non-empty set of points S ∈ Rm, the utopia and anti-utopia points of S are, respectively, the tightest lower and upper bounds ofS with respect to Pareto dominance [Ehr08, p 49 – 50].3INTRODUCTION1.1.2 The Weighted Sum MethodThe weighted sum method for solving multiobjective optimization prob-lems uses a set of weights wi applied to each objective function fi to minimizethe single objective function w1f1(x)+w2f2(x)+ ...+wmfm(x). For a set ofweights w = (w1, w2, ..., wm), this can be expressed as w ·F (x). The solutionto the single objective optimization problem w · F coincides with one pointon the surface of the Pareto front F. However as Das and Dennis remarked[DD97], the points that lie on non-convex portions of a Pareto front F cannot be reached using weighted sums.1.1.3 SimplicesA simplex Y ∈ Rn is a bounded convex polytope with a non-emptyinterior and exactly n + 1 vertices [AH, p 25]. That is, a simplex is a linesegment in R, a triangle in R2, a tetrahedron in R3, and so on. For thepurpose of the Nelder-Mead algorithm, only the vertices of the polytopeare required. Let Y = {y0, y1, ..., yn} be the vertices of a simplex in Rn sothat the objective function evaluation of a vertex yi of Y is f(yi). Then theevaluation of the simplex Y using the function f is defined asf(Y) = {f(y0), f(y1), ..., f(yn)} ∀yi ∈ Y.From this follows the multiobjective evaluation of the simplex Y using thevector-valued function F defined asF (Y) = {F (y0), F (y1), ..., F (yn)} ∀yi ∈ Y.1.1.4 Motivation and ContributionThe motivation behind this thesis was to use the Nelder-Mead algorithmin an efficient way to search the solutions to many weighted sum problemsin an adaptive way. It was believed that the solutions to two approximatelyequal weighted sums would likely be near each other in the search space.The contribution of this thesis is the mesh-map discussed in Section 2.2.The mesh-map is an example of a possible ordering of weighted sums andthe Multiobjective Nelder-Mead algorithm is an example of how to use it.4Chapter 2Multiobjective Nelder-MeadAlgorithmThe original Nelder-Mead (NM) algorithm is extended to a multiobjec-tive optimization algorithm through the use of weighted sums and a modelof a section of the unit hypersphere. The model serves as an approxima-tion of the Pareto optimal front that guides the choices of weighted sums.The combination of the model and choices of weighted sums is called themesh-map. The NM algorithm remains at the core of the MultiobjectiveNelder-Mead (MNM) algorithm and is presented below. The mesh-map andthe MNM algorithm are explained afterward.2.1 The Original Nelder-Mead AlgorithmAlgorithm MNM’s main iteration sequence makes use of the originalNelder-Mead algorithm. At the highest level, the original NM algorithmiterates on the simplex Y, produces a new simplex, and then tests the stop-ping condition on that new simplex. If the algorithm does not stop, theprocess is repeated. This is presented below in Algorithm 1.The version of Nelder-Mead used in MNM is a slight modification ofthe original. In the original NM algorithm [NM65], there is a single con-traction variable and the shrink parameter is fixed at a value of 12 . In theNM algorithm used by MNM, the contraction parameter has been dividedinto two separate inner and outer contraction parameters, and the shrinkparameter is not bound to a value of 12 . The NM parameters used by MNMare as follows: the outer contraction and shrink parameters were set to 12 ;the inner contraction was set to −12 ; and the expansion parameter was setto 2. A stopping condition was also explicitly written into the pseudocodeas an input parameter and is discussed in Section 2.3 as part of the MNMalgorithm.Finally, while the NM algorithm used by MNM can take the multiobjec-tive functions input as a single objective weighted sum, the frequent evalu-5MULTIOBJECTIVE NELDER-MEAD ALGORITHMation of the weighted sum would obscure the individual objective functions’values. For this reason, the NM algorithm was modified to accept a multiob-jective vector function, record the objective functions’ values individually,and then construct the weighted sums internally to determine the algo-rithm’s next step. In this way, the NM algorithm returns all visited pointsand their individual objective functions’ values to MNM after terminating.Algorithm 1 Nelder-Mead (NM)Input: f , Y, stopConditionOutput: Y∗1: initialize parameters δe, δoc, δic, γ2: while evaluations remain ∧ ¬ stopCondition(Y)3: reorder Y so that f(y0) ≤ f(y1) ≤ ... ≤ f(yn)4: set centroid xc = 1n∑n−1i=0 yi5: set reflection xr = xc + (xc − yn)6: if f(y0) ≤ f(xr) < f(yn−1)7: Y∗ = {y0, y1, ..., yn−1, xr}8: elseif f(xr) < f(y0)9: set expansion xe = xc + δe(xc − yn)10: if f(xe) < f(xr)11: Y∗ = {y0, y1, ..., yn−1, xe}12: else13: Y∗ = {y0, y1, ..., yn−1, xr}14: elseif f(yn−1) ≤ f(xr) < f(yn)15: set outside contraction xoc = xc + δoc(xc − yn)16: if f(xoc) < f(xr)17: Y∗ = {y0, y1, ..., yn−1, xoc}18: else19: Y∗ = {y0, y1, ..., yn−1, xr}20: else (f(yn) ≤ f(xr))21: set inside contraction xic = xc + δic(xc − yn)22: if f(xic) < f(yn)23: Y∗ = {y0, y1, ..., yn−1, xic}24: else (shrink)25: Y∗ = {y0, y0 + γ(y1 − y0), ..., y0 + γ(yn − y0)}26: Y = Y∗27: end while6MULTIOBJECTIVE NELDER-MEAD ALGORITHM2.2 The Mesh-MapThe mesh-map is a sequence of vectors in the objective space Rm repre-senting the weights used in the weighted sums. Consider the non-negativesection of a hypersphere S+ ={x ∈ Rm | xi ≥ 0 and ‖x‖2 = 1}. The setS+ represents a dense set of potential weights for the weighted sums on them objective functions. The mesh-map is a finite ordered subset of S+. Thepurpose of the ordering is to be able to quickly solve a weighted sum usingthe solution of a previously solved weighted sum. This is explained below.With the supposition that the Pareto front is convex, two solutions to twoslightly different weighted sums are presumed to be near one another in thedomain space. For example in a multiobjective optimization problem withtwo objective functions, the solution to the weighted sum w1·f1(x)+w2·f2(x)is presumed to be close to the solution of the weighted sum (w1 + ) ·f1(x)+w2 · f2(x) for some small value . Given the output simplex Y∗ to thesolution of the former weighted sum, a warm-start from Y∗ to the solutionof the latter weighted sum may be only a few iterations away.The vectors in the mesh-map were chosen so as to cover S+ with evenlyspaced points, distance being measured on the surface of the hypersphere.The mesh-map is a set of concentric rings of simplices in the objective spaceRm on the unit hypersphere. These rings are centred about the weighted sum(1√m, 1√m, ..., 1√m)and expand outwardly from this centre to the coordinatevectors.The two parameters for constructing a mesh-map are the number ofrings and the dimension of the objective space m. The first ring has density1 and is constructed from the coordinate vectors, which correspond to theweighted sums of solving each objective function individually. This ring isthen scaled down toward the origin O by one divided by the number ofrings. The second ring has density 2 and is constructed from the coordinatevectors and the midpoint of each pair of vectors. This ring is then scaleddown toward the origin O by two divided by the number of rings. The thirdring trisects each pair of vectors, and so on. The ordering of the points inthe mesh is left unchanged after the construction.Three orderings of mesh-maps were used: the original ordering namedInToOutMM, a random ordering named RandMM, and the reverse order-ing named OutToInMM. The mesh-maps are compared in Chapter 4. Thesubroutine that generates the mesh-map is given in Subroutine 2 and mesh-maps with different numbers of rings are shown in Figure 2.1 below.7MULTIOBJECTIVE NELDER-MEAD ALGORITHMSubroutine 2 Mesh-MapInput: number of rings num rings, number of objective functions mOutput: mesh map1: initialize the origin O =(1√m, 1√m, ..., 1√m)m×12: add O to the mesh map3: for ring num = 1 to num rings4: set density = ring num and radius = ring num/num rings5: construct mesh ring with given density and radius:6: initialize the identity matrix I7: for each pair of vectors ui and uj in I8: build a line segment from ui to uj with given density:(kdensity)· uj +(density−kdensity)· ui for k ∈ {0, 1, 2, ..., density}9: end for10: contract the ring to the desired radius11: add mesh ring to the mesh-map12: end for13: reorder meshFigure 2.1: Illustrations of mesh-maps on a sphere with two rings (top left),four rings (top-right), six rings (bottom-left), and eight rings (bottom-right)with grey-scaling with grey-scaling to show individual rings. 8MULTIOBJECTIVE NELDER-MEAD ALGORITHM2.3 The Multiobjective Nelder-Mead AlgorithmThe Multiobjective Nelder-Mead algorithm takes as inputs the multiob-jective vector-valued function F to be minimized, an initial prime numberand a larger maximum prime number, a minimum convergence tolerance ,a maximum number of evaluations, and a search space Ω. The algorithmfirst initializes a prime number p = pinit. This prime number determines thenumber of rings in the first mesh-map that will be constructed. When themesh-map has been fully traversed, a new simplex and a denser mesh-mapwill be initialized with p equal to the next smallest prime. The purpose of theprime numbers is to prevent rings of different mesh-maps from overlapping.Once a starting simplex and a mesh-map have been built, the algorithmloops through the weights in the mesh-map. For each set of weights w inthe mesh-map, a new weighted sum function fw = w · F is constructed.This single objective weighted sum function is then solved by the originalNelder-Mead algorithm. The stopping condition for the NM algorithm isthe distance between the values of fw(Y):|fw(yi)− fw(yj)| <  ∀yi, yj ∈ Y.The supposition made here is that the simplex has reached the Pareto frontwhen the weighted objective function values of the vertices of Y have con-verged to within a given . The simplex Y∗ at the end of a Nelder-Meaditeration is then used as the input simplex Y for the NM algorithm in thenext iteration.When the NM algorithm returns no new visited points on a given setof weights, the stopping condition was satisfied before any work was done.The epsilon value is then shrunk to test at a higher accuracy on the nextiteration. The epsilon value is reset to the initial epsilon before each newmesh-map is constructed.The NM algorithm may also fail to return visited points on single-pointPareto fronts. This causes the MNM algorithm to cycle through larger andlarger mesh-maps, stalling on needless computation. To prevent this, theprime number p is updated after this iteration’s mesh-map has been tra-versed. When the prime number p exceeds some maximum prime pmax, p isreset to the initial small prime. The Multiobjective Nelder-Mead algorithmis presented in Algorithm 3 below.The MNM algorithm was coded in Matlab version R2019a. Copies ofthe code are available upon request to the author.9MULTIOBJECTIVE NELDER-MEAD ALGORITHMAlgorithm 3 Multiobjective Nelder-Mead (MNM)Input: F , pinit, pmax, init, max evaluations, hyper-rectangularsearch space Ω ⊂ RnOutput: data of visited points1: initialize p = pinit2: while evaluations remain3: construct a simplex Y in Ω4: evaluate the simplex F (Y)5: store visited yj and F (yj) for each yj ∈ Y6: construct a mesh map with num rings = p7: set  = init8: initialize i ∈ N9: while evaluations remain ∧ ¬(mesh map traversed)10: w = mesh map(i)11: fw(x) = w · F (x)12: set  for stopCondition13: [Y∗, visited points] = NM(fw, Y, stopCondition)14: Y = Y∗15: i← i+ 116: if NM did not return any new points17: set  = 218: end while19: if p > pmax20: reset p = pinit21: else22: p← next prime23: end while10Chapter 3Test EnvironmentThe performance of algorithm MNM was assessed in a test environmentthat included a number of algorithms, metrics, and test sets. The detailsof each are below. The test environment was then used to create data setsfor analysis. The details of the data sets are given in the last section of thischapter.3.1 AlgorithmsIn addition to the three variants of MNM, the test environment in-cluded four algorithms: Random Search, Grid Search, Multi-Objective Par-ticle Swarm Optimization (MOPSO), and the second version of the Non-dominated Sorting Genetic Algorithm (NSGA-II). The details of each aregiven below.3.1.1 Random SearchThe Random Search algorithm is a finite and probabilistic version ofthe Exhaustive Search algorithm ([AH, p 33–35]). The Random Searchalgorithm constructs a set of points chosen at random within the searchspace. It then evaluates the objective functions’ values for each point in theset and outputs the data. The pseudocode for this algorithm is given inAlgorithm 4.Algorithm 4 Random SearchInput: F , max evals, hyper-rectangular search space Ω ⊂ RnOutput: data of visited points1: initialize a set S of random uniformly distributed points in Ω2: for each point x in S3: evaluate F (x)4: store visited x and F (x)5: end for11TEST ENVIRONMENT3.1.2 Grid SearchThe Grid Search algorithm constructs a hyper-rectangular grid of equallyspaced points inside the search space as described by Audet and Hare [AH,p 35–37]. A modification was made to the pseudocode to handle cases wherethe dimension of the search space was too large. No such cases arose in thedata sets however. The pseudocode for this algorithm is given in Algorithm5.Algorithm 5 Grid SearchInput: F , max evals, hyper-rectangular search space Ω ⊂ RnOutput: data of visited points1: determine maximum num parts for (num parts+ 1)n ≤ max evals2: construct grid G:3: if 2n > max evals4: set G to be a subset of the corners of Ω5: else for Ω = [`i, ui] for i ∈ {1, 2, ..., n}6: define δi = (ui − `i)/(num parts− 1)7: set G = {x | xi = `i + kδi} for k ∈ {0, 1, ..., num parts− 1}8: for each point x in G9: evaluate F (x)10: store visited x and F (x)11: end for3.1.3 Multi-Objective Particle Swarm OptimizationThe Multi-Objective Particle Swarm Optimization (MOPSO) algorithmwas first published by Alvarez-Benitez et al. [ABEF05]. The algorithmwas downloaded from the MathWorks File Exchange website [MC19]. Thefile was modified to work as a function that inputs a set of parametersand outputs the data of all visited domain points and their correspondingobjective functions’ evaluations. The visual output was also disabled. Thealgorithm-specific parameters of MOPSO were left as their default valueswith the exception of population size which was set to be one hundredth ofthe maximum number of function evaluations of the given problem. It wasnoted that MOPSO never once crashed in any test performed.12TEST ENVIRONMENT3.1.4 Non-dominated Sorting Genetic Algorithm Version 2The Non-dominated Sorting Genetic Algorithm version 2 (NSGA-II) wasfirst published by Deb et al. [DAPM00]. The algorithm was downloadedfrom the MathWorks File Exchange website [Ses09]. The files were modifiedin a number of ways. The NSGA-II algorithm was modified to work as afunction that inputs a set of parameters and outputs the data of all visiteddomain points and their corresponding objective functions’ evaluations. Thevisual output and repeated trials were both disabled. The algorithm-specificparameters of NSGA-II were left as their default values with the exception ofpopulation size which was set to be one hundredth of the maximum numberof function evaluations of the given problem.Frequent crashes on some types of problems led to code corrections intwo places. Firstly, in the process of creating offspring, certain occasionswould arise when the maximum number of offspring would not be generated.To prevent the errors that followed, random point offspring were includedto fill the population to its capacity. Secondly, a comparison of equalitybetween two member points occasionally created divisions by zero whenmember points were unequal but equal in some component. This was fixedby checking the individual components of the member points for equalityinstead.3.2 MetricsThe data generated from the test environment was analyzed using somesimple statistics on times and failures (discussed in Chapter 4) and was fur-ther analyzed using metrics taken and adapted from the literature, namelyHypervolume, Contribution, and the Epsilon Indicator metrics. These met-rics are discussed below after a brief explanation of set domination necessaryto discuss their theoretical properties.3.2.1 Set DominationThe metrics used below were chosen in part because of their theoreticalproperties as discussed by Zitzler et al. [ZTL+03]. In this publication, theconcept of set domination was used to study several metrics. Set dominationbetween approximation sets is similar to domination between vectors asdescribed in Section 1.1.1. A set A is said to dominate a set B when everyelement of B is dominated by some element of A. Furthermore, A is saidto weakly dominate B when every element of B is dominated by or equal to13TEST ENVIRONMENTsome element of A. These definitions will be used to explain the theoreticalproperties of the metrics below.3.2.2 HypervolumeThe Hypervolume metric takes an approximation set and a referencepoint and calculates the hypervolume contained therein by separating itinto a series of polytopes (see the left side of Figure 3.1). The code for theHypervolume metric was downloaded from the MathWorks File Exchangewebsite [Sim15]. This code is a simplification of the original hypervolumefirst discussed by Zitzler and Thiele [ZT99] as the volume of the space thatis dominated by a set of points.The Hypervolume approximation metric has four input parameters: anapproximation set, a utopia point, an anti-utopia point, and a number ofsample points with which to estimate the hypervolume. The utopia andanti-utopia points in the test environment were chosen to be the utopia andanti-utopia points from the set of all combined solutions of the test data ofthe given problem. The metric approximates the hypervolume by creating anumber of randomly sampled points in the space bounded by the utopia andanti-utopia points and then determining whether each point is dominatedor not dominated by the input approximation set. The Hypervolume ap-proximation is the number of dominated sample points divided by the totalnumber of sample points.Testing of the Hypervolume metric determined that one hundred thou-sand sample points was the suitable size as it could be computed in reason-able time to within approximately 0.1% accuracy. The metric was chosen forits simplicity and accuracy as well as its -compatibility and .-completenessas described by Zitzler et al. [ZTL+03]. That is, for two approximation setsA and B, the following statements are true. If A weakly dominates but isnot equal to B, then the hypervolume of A is strictly greater than the hyper-volume of B (.-completeness), and if the hypervolume of A is greater thanthe hypervolume of B, then B cannot weakly dominate A (-compatibility).3.2.3 ContributionThe Contribution metric counts the number of optimal points from analgorithm’s solution used in the combined solution of all algorithms. Itis an adaptation of the Purity metric developed by Bandyopadhyay, Pal,and Aruna [BPA04]. The metric was chosen for its simplicity and -compatibility and was chosen instead of Purity because of its .-completeness14TEST ENVIRONMENTcompared to Purity’s -completeness as described by Zitzler et al. [ZTL+03].That is for two approximation sets A and B where B ⊂ A, the Purity metricreturns the same measure for both A and B, while the Contribution metricgives A a higher measure than B. The Contribution metric is illustrated inthe centre of Figure 3.1.3.2.4 Epsilon IndicatorThe Epsilon Indicator was defined by Zitzler et al. [ZTL+03] in their as-sessment of multiobjective optimizers. It measures the minimum value of thescalar  required to make the Pareto front dominated by the approximationset. In practice, the solution set of all the individual algorithms’ solutionsets combined was used as an approximation of the Pareto front instead.The approximation and solution sets are first translated to Rm+ so that theutopia point of the solution set is located at the vector 1 = (1, 1, ..., 1)m×1.Then the infimum is sought that satisfies the following condition:(∀s ∈ S)(∃a ∈ A) a dominates s.The value of epsilon will lie in the range of [1,∞). If the approximation setA is empty, then a value of 109 is used instead. The output of the epsilonindicator function is 1 , a value in the range of (0, 1] with values near 1representing a close fit with the solution set. The Epsilon Indicator metricis illustrated on the right of Figure 3.1.To improve the Epsilon Indicator’s performance, an approximation of theindicator was implemented similar to that used for the Hypervolume metric.When a given approximation set is 500 vectors or less, the Epsilon Indicatoris measured directly. However when the approximation set is larger than 500vectors, a random sample of 500 vectors is extracted and measured instead.Preliminary testing suggested that the approximation should be close to theexact value.15TEST ENVIRONMENTFigure 3.1: Illustrations of the Hypervolume metric (left) showing the com-bined area of individual polytopes between set A and a reference point, theContribution metric (centre) showing the contributions of sets A and B tothe undominated points of A∪B with dominated points struck out, and theEpsilon Indicator metric (right) showing the minimum distance required forthe Pareto front to be dominated by a set A.3.3 Test SetsThe algorithms were run on a variety of test sets. The test sets includefunctions from the literature such as the DTLZ problems, a list of problemstaken from Wikipedia, and randomly generated test sets with fixed seedsfor reproducibility. The test sets are detailed below.3.3.1 WikipediaThe Wikipedia test set is a set of problems taken from the Wikipediaarticle Test Functions for Optimization [Wik20] on December 5, 2019. ThisWikipedia article has a section, Test Functions for Multiobjective Optimiza-tion, containing seventeen test problems. One of these test problems, theFonseca-Fleming function, is a functional that was used to create three testproblems with different dimensions for the domain. In total, the Wikipediaproblems were mostly bi-objective with a mixture of both convex and non-convex solutions; had dimensions for the domain varying from one to thirty;and had some problems where the Pareto front was a union of disconnectedsets.16TEST ENVIRONMENT3.3.2 DTLZThe DTLZ test set is a set of seven scalable multi-objective optimizationtest problems presented by Deb, Thiele, Laumanns, and Zitzler [DTLZ02].The objective functions are determined by the dimension of the search spaceand the number of objective functions chosen. The test problems with lowersearch space dimension and number of objective functions were used, asdetailed in Section 3.4.5 below. It is noted that four of the problems fromthe Wikipedia test set were taken from this DTLZ test set, however thoseproblems use different search space dimensions.3.3.3 QuadraticsThe Quadratics test set is a randomly generated test set fixed to a seednumber for reproducibility. The problem number selected is used as theseed to make the randomized problem. The test set is fixed based on thechoices of the number of objective functions and the dimensions of thosefunctions. The objective functions are all of the form 12xTAx+ bx+ c wherethe components of A, b, and c are random numbers in the range [−1, 1]. Notethat A is not a symmetric matrix in this definition of quadratic. While thetest set may contain some convex functions, it is regarded as a non-convextest set.3.3.4 Quadratics PSDThe Quadratics PSD (Positive Semi-Definite) test set is a randomly gen-erated test set fixed to a seed number for reproducibility. The test set isidentical to the Quadratics test set with one exception: the objective func-tions are of the form 12xTATAx+bx+c. The use of ATA instead of A ensuresthat the objective functions are all convex. A set of convex objective func-tions guarantees a convex Pareto front, and so this test set is regarded as aconvex test set.3.3.5 Sine PolynomialsThe Sine Polynomials test set is a set of randomly generated problemsfixed to a seed number for reproducibility. The test set is generated inthe same way as the Quadratics test set above. The objective functionsare of the form ||x|| · sin(p(x) · e−||x||2), where p(x) is a polynomial. Thepolynomials p(x) are of the form p1(x1) · p2(x2) · ... · pn(xn) where n isthe dimension of the search space. The functions pi(xi) are of the form17TEST ENVIRONMENT(xi − r1) · (xi − r2) · (xi − r3) · (xi − r4) where the roots rj are randomnumbers in the range [−3, 3]. The objective functions are unpredictablymountainous near the origin and quickly approach a function value of 0further away from the origin. Multiobjective problems in this test set oftenhave Pareto fronts with multiple disjoint locally convex regions.3.4 Data SetsThe test environment was used to create seventeen data sets for analysis.The seven algorithms that participated in these tests were Random Search,Grid Search, MOPSO, NSGA-II, MNM-InToOutMM, MNM-RandMM, andMNM-OutToInMM. The problems on which these algorithms were testedwere taken from the Wikipedia, DTLZ [DTLZ02], Quadratics, QuadraticsPSD, and Sine Polynomials test sets, as detailed in Section 3.3. The testsets were then merged in different ways to investigate structures.The algorithms were tested with a limit on the number of function eval-uations. The maximum number of function evaluations on a given problemwas chosen to be 100nm2 where n is the dimension of the search space ofthe problem and m is the number of objective functions. The details of eachtest set’s problems are given below.3.4.1 Quadratics PSD Data SetsOf the seventeen data sets created, the first three were randomly gen-erated from the Quadratics PSD test set. The first data set contains fivehundred problems with search spaces of dimension one to three evenly spreadand two objective functions; the second data set contains five hundred prob-lems with dimension one to three and three objective functions; and the thirdcontains twenty-five problems of dimension one to ten and between two andten objective functions. In this third set, the explicit number of dimensionsand objectives of the twenty-five problems are(n,m) ∈ {(1, 4), (1, 6), (1, 8), (1, 9), ...(2, 2), (2, 8), ...(3, 6), (3, 6), (3, 6), (3, 9), ...(5, 2), (5, 8), ...(6, 8), (6, 8), (6, 10), (6, 10), ...(7, 6), ...(8, 2), (8, 4), ...(9, 3), (9, 4), (9, 7), (9, 10), ...18TEST ENVIRONMENT(10, 6), (10, 8)}.Notice that the pairs (6, 8) and (6, 10) are duplicated and (3, 6) is tripli-cated. This is the result of the seeds used to generate the problems.3.4.2 Quadratics Data SetsThe next three data sets, that is data sets four to six, were randomlygenerated from the Quadratics test set. The first data set contains twohundred twenty-five problems with search spaces of dimension one to threeevenly spread and two objective functions; the second data set containstwo hundred twenty-five problems with dimension one to three and threeobjective functions; and the third contains ten problems of dimension oneto ten and between two and ten objective functions. In this third set, theexplicit number of dimensions and objectives of the ten problems are(n,m) ∈ {(1, 6), (1, 9), (3, 9), (5, 2), (5, 8), (6, 8), (8, 2), (9, 4), (9, 10), (10, 6)}.3.4.3 Sine Polynomials Data SetsData sets seven to nine were randomly generated from the Sine Polyno-mials test set. The first data set contains two hundred twenty-five problemswith search spaces of dimension one to three evenly spread and two objectivefunctions; the second data set contains two hundred twenty-five problemswith dimension one to three and three objective functions; and the thirdcontains eleven problems of dimension one to ten and between two and tenobjective functions. In this third set, the explicit number of dimensions andobjectives of the eleven problems are(n,m) ∈ {(1, 6), (1, 9), (2, 2), (3, 9), (5, 2), (5, 8), (6, 8), (8, 2), (9, 4), ...(9, 10), (10, 6)}.3.4.4 Wikipedia Data SetThe tenth data set comes from the Wikipedia test set. There were noadditional input parameters for this test set.3.4.5 DTLZ Data SetsThe eleventh to the seventeenth data sets come from the DTLZ testset. The DTLZ test set contains seven problems, from DTLZ-1 to DTLZ-7, and each of these test problems was used to create five problems for19TEST ENVIRONMENTthat data set. For each problem style DTLZ-i, the search space dimensionsand number of objective functions were chosen to be low, such as (n,m) ∈{(2, 2), (2, 3), (3, 2), (3, 3), (3, 4)}.3.4.6 Summary of Data SetsThe seventeen data sets contain a total of two thousand problems. Asummary of the problems is presented in Table 3.1 below.Data Set # Problem Set (n,m) # of Problems1 (1-3,2) 5002 Quadratics PSD (1-3,3) 5003 (1-10,2-10) 254 (1-3,2) 2255 Quadratics (1-3,3) 2256 (1-10,2-10) 107 (1-3,2) 2258 Sine Polynomials (1-3,3) 2259 (1-10,2-10) 1110 Wikipedia ({1-3,5,6,10,30},2-3) 1911 DTLZ-1 (2-3,2-4) 512 DTLZ-2 (2-3,2-4) 513 DTLZ-3 (2-3,2-4) 514 DTLZ-4 (2-3,2-4) 515 DTLZ-5 (2-3,2-4) 516 DTLZ-6 (2-4,2-3) 517 DTLZ-7 (2-4,2-3) 5Table 3.1: A summary of the data sets used for analysis in Chapter 4.20Chapter 4Test ResultsThe test environment was used to produce seventeen data sets collectedfrom the outputs of seven algorithms run on two thousand test problems.The Random Search and Grid Search algorithms were intended to providea baseline with which to compare the MOPSO, NSGA-II, and MNM algo-rithms. The Grid Search algorithm varied too significantly in its numberof evaluations used. In some of the data sets, the total number of functionevaluations used by the Grid Search algorithm was significantly below themaximum while those of all other algorithms was close to the maximum.This resulted in irregular results for the Grid Search algorithm. The Ran-dom Search algorithm demonstrated more regularity, and so the RandomSearch algorithm alone is taken to be the baseline.The algorithms are analyzed in the sections below. A brief summaryof algorithm running times and failures is given first. The results of theapplication of the Hypervolume, Contribution, and Epsilon Indicator metricsare then shown and discussed. Finally, some observations are made on thethree mesh-maps used by MNM.4.1 Time and Failure ResultsData on algorithm running times was compiled along with other data.The times relative to the fastest algorithm on each problem were calculated.The average and standard deviations of the relative times were then deter-mined for each algorithm. As mentioned above, the Grid Search algorithmoften used significantly less than the maximum number of function evalua-tions. This resulted in the Grid Search algorithm often completing fastestand skewing the data. Relative times compared to the Random Search al-gorithm were therefore also calculated separately without the Grid Searchalgorithm’s running times. The statistics for the merged convex and non-convex sets are written in Tables 4.1 and 4.2 below while the remainingrunning time statistics are omitted for brevity.The running time statistics show that the MOPSO algorithm had thelongest running times on average and the largest deviations in times. The21TEST RESULTSNSGA-II and MNM algorithms usually had shorter and similar times anddeviations, with MNM a little faster.Algorithm Avg Rel T Std Dev Rel T Avg to Rand Std Dev to RandRandom Search 1.4601 6.2904 1 0Grid Search 1.0339 0.076266 - -MOPSO 9.1578 8.8037 8.1395 3.6604NSGA-II 3.6925 7.6683 2.9944 1.2388MNM-InToOutMM 2.8889 7.6029 2.2561 1.0495MNM-RandMM 2.7882 7.5032 2.17 0.84418MNM-OutToInMM 2.8677 7.6553 2.2352 0.8899Table 4.1: A summary of the running time statistics for the merged data ofsets 1, 2, and 3, the combination of convex Quadratics PSD data sets.Algorithm Avg Rel T Std Dev Rel T Avg to Rand Std Dev to RandRandom Search 1.8254 9.4171 1 0.00019513Grid Search 1.0325 0.049626 - -MOPSO 10.9132 28.566 8.3347 3.9304NSGA-II 4.1787 11.3007 2.9879 1.1167MNM-InToOutMM 3.5116 11.3418 2.4048 2.1283MNM-RandMM 3.2042 10.9393 2.1498 0.81857MNM-OutToInMM 3.398 13.1318 2.1889 0.90229Table 4.2: A summary of the running time statistics for the merged data ofsets 4 to 17, the combination of non-convex data sets.The data did not contain any crashed algorithms or not-a-number (NaN)values in all the sets of visited points returned. It is noted however that allalgorithms were tested repeatedly on the test sets until no failures arose.4.2 Metric ResultsThe algorithms’ solutions from the seventeen data sets were measuredusing the Hypervolume, Contribution, and Epsilon Indicator metrics. Therelative metric values of each algorithm on each problem were then computedto normalize the results. The metric data is presented through accuracyprofiles that are defined below. The accuracy profiles and the discussionsthereof are sectioned afterwards. Note that accuracy profiles for all datasets combined could not be obtained because the merged data file was toolarge to save.22TEST RESULTS4.2.1 Accuracy ProfilesThe data sets were analyzed with the use of accuracy profiles, as de-scribed by Beiranvand et al. [BHL17, p 831]. The accuracy profiles serve tosummarize the results of large data sets by plotting the number of problemssuccessfully solved with a given accuracy. The x-axis represents the rangeof accuracies and the y-axis the percentage of problems solved at a givenaccuracy x.The solution of each problem was computed from the non-dominatedpoints of the union of all algorithms’ solutions. This combined solution wasthen used by the Hypervolume, Contribution, and Epsilon Indicator metricsto produce an accuracy measure γp,a in the range of [0, 1] for each problemp and algorithm a from the data’s set of problems P, as detailed in Section3.2. The percentage of problems solved was then calculated asRa(τ) =1|P| |{γp,a | γp,a ≥ τ ∀p ∈ P}|,that is, the portion of problems in P solved by algorithm a with accuracyτ ∈ [0, 1]. Examples of accuracy profiles are given in Figure 4.1 below.Figure 4.1: Examples of Accuracy profiles with labelled axes.Note that the accuracy profiles shown below are sometimes zoomed into the area of interest, as seen in the left figure of Figure 4.1.23TEST RESULTS4.2.2 Quadratics PSD Data SetsThe accuracy profiles of the first data set from the Quadratics PSD testset are shown below in Figure 4.2. This data set has search space dimensionsbetween one and three and two objective functions.Figure 4.2: Accuracy profiles of the metrics applied to data set 1 from theQuadratics PSD test set with (n,m) = (1–3, 2).The Hypervolume metric’s accuracy profile from Figure 4.2 shows thatthe Random Search algorithm performed the most poorly though still well.That is, the Random Search algorithm solved approximately ninety-five per-cent of problems with an accuracy of zero point seven or higher but onlysolved approximately thirty percent of problems with an accuracy of zeropoint ninety-nine. The Grid Search algorithm performed slightly better thanthe Random Search algorithm. The MOPSO, NSGA-II, and MNM algo-rithms are close together with the three variants of MNM between MOPSOand NSGA-II. All five of these algorithms solved approximately ninety-ninepercent of problems with an accuracy of at least zero point ninety-nine.On the Contribution metric’s accuracy profile, the three variants ofMNM perform significantly better with MNM-InToOutMM performing best.It may be that the MNM algorithms are exploring a certain part of thePareto front more accurately than the MOPSO and NSGA-II algorithms.The Epsilon Indicator metric’s accuracy profile resembles the Hyper-volume’s with the Grid Search algorithm performing significantly betterthan the Random Search algorithm, and the MNM-OutToInMM algorithmslightly ahead of the other algorithms. It is not clear why these resulted onthe Epsilon Indicator metric.The accuracy profiles of the second data set, also from the Quadratics24TEST RESULTSPSD test set, are shown below in Figure 4.3. This data set has searchspace dimensions between one and three and three objective functions. Theresults are similar to the first data set with NSGA-II performing oddly belowthe Random Search algorithm on the Hypervolume and Epsilon Indicatormetrics.Figure 4.3: Accuracy profiles of the metrics applied to data set 2 from theQuadratics PSD test set with (n,m) = (1–3, 3).The accuracy profiles of the third data set, also from the QuadraticsPSD test set, are shown below in Figure 4.4. This data set has searchspace dimensions between one and ten and between two and ten objectivefunctions.Figure 4.4: Accuracy profiles of the metrics applied to data set 3 from theQuadratics PSD test set with (n,m) = (1–10, 2–10).25TEST RESULTSThe Random Search and Grid Search algorithms perform more poorlyin these problems with larger search space dimensions and number of ob-jective functions. The Grid Search algorithm solves very few or no testswith high accuracy. This may be a consequence of the grid size require-ments limiting the number of function evaluations. The MNM-RandMMalgorithm performed best on the Hypervolume metric. The MOPSO algo-rithm performed poorly on the Contribution metric but very well on theEpsilon Indicator metric. The NSGA-II and MNM algorithms performedsimilarly to Figure 4.2 on the Contribution metric, with MNM-OutToInMMdoing more poorly and MNM-InToOutMM doing better. The NSGA-II andMNM algorithms performed as or more poorly than the Random Searchalgorithm on the Epsilon Indicator metric. It is not clear why this resultedon the Epsilon Indicator metric.4.2.3 Summary of Convex Data SetsThe accuracy profiles of the combined one thousand twenty-five testproblems from the three data sets of the Quadratics PSD test set are shownin Figure 4.5 below.Figure 4.5: Accuracy profiles of the metrics applied to the merged data ofsets 1, 2, and 3 from the Quadratics PSD test set, a convex data set.The accuracy profiles resemble those of Figure 4.2 with the NSGA-IIalgorithm below on the Hypervolume and Epsilon Indicator metrics, likelyfrom the data set with three objective functions. These three data setsdemonstrate the performance of the MNM algorithm on a set of convexproblems, and it appears to be competitive with current algorithms.26TEST RESULTS4.2.4 QuadraticsThe accuracy profiles of the three merged data sets of the Quadraticstest set, that is data sets four, five, and six, are shown below in Figure 4.6.Figure 4.6: Accuracy profiles of the metrics applied to the merged data ofsets 4, 5, and 6 from the Quadratics test set.The Grid Search and MOPSO algorithms performed very well on theHypervolume and the Epsilon Indicator metrics. The Grid Search algorithmmay have performed well when the Pareto fronts were on the boundary of thesearch space. The NSGA-II and MNM algorithms performed comparably tothe Random Search algorithm on the Hypervolume and Epsilon Indicatormetrics, with NSGA-II performing a little better than MNM. The NSGA-IIand MOPSO algorithms did much better on Contribution than the threevariants of MNM. It is not clear why this resulted on the Contributionmetric. The accuracy profiles of the individual data sets show that theNSGA-II and MNM algorithms performed better on the Hypervolume andEpsilon Indicator metrics on problems with fewer objective functions andbetter on Contribution on problems with more objective functions. Theaccuracy profiles of the individual data sets are omitted for brevity.4.2.5 Sine PolynomialsThe accuracy profiles of the three merged data sets of the Sine Polyno-mials test set, that is data sets seven, eight, and nine, are shown below inFigure 4.7.27TEST RESULTSFigure 4.7: Accuracy profiles of the metrics applied to the merged data ofsets 7, 8, and 9 from the Sine Polynomials test set.The Grid Search algorithm performed more poorly than the RandomSearch algorithm on the Hypervolume and Epsilon Indicator metrics. It isnot clear why this resulted. The MOPSO and NSGA-II algorithms per-formed similarly well with MOPSO below NSGA-II on the Contributionmetric and above on the Epsilon Indicator metric. The MNM algorithmsperformed similarly to the Random Search algorithm on the Hypervolumemetric, well on the Contribution metric, and similarly to the Grid Searchalgorithm on the Epsilon Indicator metric. It may be that the MNM algo-rithms are exploring only some of the multiple locally convex regions of thePareto front. The accuracy profiles of the individual data sets show that theMNM algorithms performed poorly on the eighth data set with three objec-tive functions, but comparatively well with search spaces of higher dimen-sions and more objective functions. The accuracy profiles of the individualdata sets are omitted for brevity.4.2.6 Summary of Higher Dimension Data SetsThe accuracy profiles of the three merged data sets with search spacedimensions between one and ten and between two and ten objective func-tions, that is data sets three, six, and nine, are shown below in Figure 4.8.Of the forty-six problems from this merged data set, twenty-five are from theQuadratics PSD test set, ten are from the Quadratics test set, and elevenare from the Sine Polynomials test set.28TEST RESULTSFigure 4.8: Accuracy profiles of the metrics applied to the merged data ofsets 3, 6, and 9 with (n,m) = (1–10, 2–10).The MOPSO algorithms performed well on the Hypervolume and Ep-silon Indicator metrics while the NSGA-II algorithm performed well on theHypervolume and Contribution metrics. The MNM algorithms performed alittle better than the Random Search algorithm on the Hypervolume metric,well on the Contribution metric, but a little below Random Search on theEpsilon Indicator metric.4.2.7 WikipediaThe accuracy profiles of the Wikipedia data set, that is data set ten, areshown below in Figure 4.9. The MOPSO and NSGA-II algorithms performedwell on this data set. The MNM algorithms performed slightly better thanthe Random Search algorithm but below NSGA-II and MOPSO on the Hy-pervolume metric, a little above but comparable to NSGA-II and MOPSOon the Contribution metric, and a little below but comparable to NSGA-IIand MOPSO on the Epsilon Indicator metric. It it noted that some of theproblems in this test set are convex.29TEST RESULTSFigure 4.9: Accuracy profiles of the metrics applied to data set 10 from theWikipedia test set.4.2.8 DTLZThe accuracy profiles of the merged data sets of the DTLZ test set, thatis data sets ten through seventeen, are shown below in Figure 4.10.Figure 4.10: Accuracy profiles of the metrics applied to the merged data ofsets 11 to 17 from the DTLZ test set.The MOPSO algorithm performed well on all metrics while the MNMalgorithms performed poorly on all metrics. The NSGA-II algorithm per-formed poorly on the Hypervolume and Epsilon Indicator metrics but wellon the Contribution metric. The accuracy profiles of the individual datasets’ accuracy profiles are omitted for brevity.30TEST RESULTS4.2.9 Summary of Non-convex Data SetsFinally, the accuracy profiles of the merged non-convex data sets, thatis data sets four to seventeen, are shown below in Figure 4.11. This figure isin contrast to the accuracy profiles of the convex data set from Figure 4.5.Figure 4.11: Accuracy profiles of the metrics applied to the merged data ofsets 4 to 17, a mostly non-convex data set.The Grid Search algorithm performed similarly to the Random Searchalgorithm on the Hypervolume and Contribution metrics and well on theEpsilon Indicator. The MOPSO algorithm performed well on the Hypervol-ume and Epsilon Indicator metrics and a little below NSGA-II and MNM onthe Contribution metric. The NSGA-II algorithm performed well on the Hy-pervolume metric and slightly better than Random Search on the EpsilonIndicator metric. The MNM algorithms performed similarly to RandomSearch on the Hypervolume and Epsilon Indicator metrics and comparablyto NSGA-II on the Contribution metric.4.3 Mesh-Map ResultsThe three variants of the mesh-map, InToOutMM, RandMM, and Out-ToInMM, appear to have similar results in most of the figures presented.This suggests that the ordering may have a small or moderate effect on theperformance of the MNM algorithm. The MNM-InToOutMM algorithmappears to perform better than the other mesh-maps on the Contributionmetric, but had the highest average running time and standard deviation ofthe three mesh-map variants. It is not clear why these resulted.31Chapter 5ConclusionAn algorithm for finding approximations to Pareto fronts in the opti-mization of multiple objective functions was presented. A section of thehypersphere served to construct a mesh-map of weights for the objectivefunctions. The Nelder-Mead algorithm was used to solve individual weightedsums from the mesh-map without the use of derivatives. The multiobjectiveNelder-Mead algorithm was found to be competitive with current algorithmson convex problems and comparable to Random Search on non-convex prob-lems. Caution may be taken in comparing MOPSO, NSGA-II, and MNMtoo strictly: the parameters for MOPSO and NSGA-II were not changedafter their initial settings.Further research directions for the MNM algorithm include the mesh-map, non-convex problems, metric analyses, convergence, and the simplexconstruction. First, the mesh-map is not yet properly understood. Whilethe ordering of the points on the mesh-map may not be so significant, manyquestions remain about the possible designs and implementations of themesh-map. For example, the results may improve when the mesh-map isdense where the problem’s Pareto front curvature is low, and sparse wherethe curvature is high. A dynamic approach that chooses the current weightedsum based on the approximate curvrature of the global Pareto front mayimprove results considerably. In a similar way to how Mehta and Dasgupta[MD20] compared the function values of the multiple simplices that workedthrough a population’s iteration, perhaps the final simplices of some localweighted sums could be used to determine how much a problem’s Paretofront is curving locally and then decide on an appropriate weighted sumaccordingly for the next step.The remaining research directions mentioned are commented on below.For the non-convex test problems, the adaptive weighted-sum method pre-sented by Kim and de Weck [KdW05] could be useful to progressively boundthe search space around the relevant non-convex regions. The metrics couldbe further analyzed, particularly to understand why the MNM algorithmsare performing so well on the Contribution metric, but less well on the Hy-pervolume and Epsilon Indicator metrics. Metrics on time could also be32CONCLUSIONmore thoroughly investigated such as how long it takes to traverse a mesh-map. The convergence of the MNM algorithm could be improved usingproperties of the DFMO algorithm by Liuzzi, Lucidi, and Rinaldi [LLR16]where points individually check for convergence. Finally, the simplex con-struction of the MNM algorithm could make use of the uniform simplexdescribed by Jarry-Bolduc, Nadeau, and Singh [JBNS19] to improve sim-plex approximations of the local search space.33Bibliography[ABEF05] J. E. Alvarez-Benitez, R. M. Everson, and J. E. Fieldsend.A MOPSO algorithm based exclusively on pareto dominanceconcepts. Evolutionary Multi-Criterion Optimization, 459–473,2005. → pages 12[AH] C. Audet and W. Hare. Derivative-Free and Blackbox Opti-mization. Springer. Springer International Publishing, 25,33–37,2017. → pages 4, 11, 12[AT18] C. Audet and C. Tribes. Mesh-based Nelder-Mead algorithm forinequality constrained optimization. Computational Optimiza-tion and Applications, 71:331–352, 2018. → pages 1[BHL17] V. Beiranvand, W. Hare, and Y. Lucet. Best practices for com-paring optimization algorithms. Optimization and Engineering,18:815–848, 2017. → pages 23[BPA04] Bandyopadhyay, Pal, and Aruna. Multi-objective gas, quanti-tative indices and pattern classifcation. IEEE Transactions onSystems, Man and Cybernetics - B, 34(5):2088–2099, 2004. →pages 14[DAPM00] K. Deb, S. Agrawal, A Pratap, and T. Meyarivan. A fast eli-tist non-dominated sorting genetic algorithm for multi-objectiveoptimization: NSGA-II. Parallel Problem Solving from Nature,1917:849–858, 2000. → pages 13[DD97] I. Das and J. E. Dennis. A closer look at drawbacks of mini-mizing weighted sums of objectives for pareto set generation inmulticriteria optimization problems. Structural Optimization,14:63–69, 1997. → pages 1, 4[DTLZ02] K. Deb, L. Thiele, M. Laumanns, and E. Zitzler. Scalablemulti-objective optimization test problems. Proceedings of the34BIBLIOGRAPHY2002 Congress on Evolutionary Computation. CEC’02 (Cat.No.02TH8600), 2002. → pages 17, 18[ED18] M. T. M. Emmerich and A. H. Deutz. A tutorial on multiob-jective optimization: fundamentals and evolutionary methods.Natural Computing, 17:585–609, 2018. → pages 3[Ehr08] M. Ehrgott. Multiobjective optimization. AI Magazine,29(4):47–57, 2008. → pages 3[JBNS19] G. Jarry-Bolduc, P. Nadeau, and S. Singh. Uniform simplex ofan arbitrary orientation. Optimization Letters, 2019. → pages33[KdW05] I. Y. Kim and O. L. de Weck. Adaptive weighted-sum method forbi-objective optimization: Pareto front generation. StructuralMultidisciplinary Optimization, 29:149–158, 2005. → pages 32[Lin76] J. G. Lin. Multiple-objective problems: Pareto-optimal solutionsby method of proper equality constraints. IEEE Transactionson Automatic Control, 21(5):641–650, 1976. → pages 1[LLR16] G. Liuzzi, S. Lucidi, and F. Rinaldi. A derivative-free approachto contrained multiobjective nonsmooth optimization. SIAMJournal on Optimization, 26(4):2744–2774, 2016. → pages 33[MC19] V. Mart´ınez-Cagigal. Multi-objective particle swarm opti-mization (MOPSO). 2019. https://www.mathworks.com/matlabcentral/fileexchange/62074-multi-objective-particle-swarm-optimization-mopso. → pages 12[MD20] V. K. Mehta and B. Dasgupta. A multi-objective optimizationmethod based on simplex search method. Advances in AppliedMechanical Engineering, pages 655–668, 2020. → pages 2, 32[NM65] J. A. Nelder and R. Mead. A simplex method for function mini-mization. The Computer Jounral, 63(2):308–313, 1965. → pages1, 5[Ses09] A. Seshadri. NSGA-II: A multi-objective optimization algo-rithm, 2009. https://www.mathworks.com/matlabcentral/fileexchange/10429-nsga-ii-a-multi-objective-optimization-algorithm. → pages 1335BIBLIOGRAPHY[SHH62] W. Spendley, G. R. Hext, and F. R. Himsworth. Sequentialapplication of simplex designs in optimisation and evolutionaryoperation. Technometrics, 4(4):441–461, 1962. → pages 1[Sim15] Simone. Hypervolume approximation, 2015. https://uk.mathworks.com/matlabcentral/fileexchange/50517-hypervolume-approximation. → pages 14[Wik20] Test functions for optimization, 2020. https://en.wikipedia.org/wiki/Test functions for optimization.→ pages 16[ZT99] E. Zitzler and L. Thiele. Multiobjective evolutionary algorithms:A comparative case study and the strength pareto approach.IEEE Transactions on Evolutionary Computation, 3(4):257–271,1999. → pages 14[ZTL+03] Zitzler, Thiele, Laumanns, Fonseca, and da Fonseca. Per-formance assessment of multiobjective optimizers: an analysisand review. IEEE Transactions on Evolutionary Computation,7(2):117–132, 2003. → pages 13, 14, 1536
Thesis/Dissertation
eng
Computer Science
Vancouver : University of British Columbia Library
Attribution-NonCommercial-NoDerivatives 4.0 International
Graduate
Multiobjective Nelder-Mead algorithm using a mesh-map of weighted sums
Text