A Gentle Introduction to Multi-Criteria Optimization with SPOT

Schriftenreihe CIplus, Band 1/2013 Herausgeber: T. Bartz-Beielstein, W. Konen, H. Stenzel, B. Naujoks A Gentle Introduction to Multi-Criteria Optimization with SPOT Martin Zaefferer, Boris Naujoks, Thomas Bartz-Beielstein A Gentle Introduction to Multi-Criteria Optimization with SPOT Martin Zaefferer, Boris Naujoks, and Thomas Bartz-Beielstein Faculty for Computer and Engineering Sciences Cologne University of Applied Sciences, 51643 Gummersbach, Germany [email protected] Schriftenreihe CIplus TR 1/2013. ISSN 2194-2870 Abstract. Multi-criteria optimization has gained increasing attention during the last decades. This article exemplifies multi-criteria features, which are implemented in the statistical software package SPOT. It describes related software packages such as mco and emoa and gives a comprehensive introduction to simple multi criteria optimization tasks. Several hands-on examples are used for illustration. The article is wellsuited as a starting point for performing multi-criteria optimization tasks with SPOT. 1 Multi Criteria Optimization: A Simple Example Optimization in general is fully integrated into todays life. We decide for the best prize when comparing similar groceries or choose the best quality when comparing different jackets. However, such decisions are generally more difficult, more complex than just deciding either for the best price or the best quality. Some sort of compromise solution might be preferable. This is where multicriteria optimization comes into play. Of course, the same holds for industrial processes. Input material has to be selected and the process itself can be steered in different directions via controlling some input variables. All these decisions will influence the quality of the final product, whereas quality can be expressed in form of different criteria or objectives (e.g., price, robustness, speed). As a consequence, a decision regarding the above mentioned input parameters can rarely be made without considering multiple criteria at once. There are some aspects that make such decisions more complicated than classical single objective problems. The most apparent one is the loss of total order. Comparing two products or processes just based on their price is easy. The cheaper is the better. If quality comes into play, life is much harder. Several products might exist which represent different compromises between quality and price. For example, let us consider the choice of selecting a car. Car no. 1 may be the cheapest, but also the one with the highest milage, whereas car no. 2 is the one with the least milage but also most expensive one. There may exist several MCO with SPOT 3 more cars which represent different compromises between milage and price. An example of that situation is represented in Fig. 1. Price [€] Milage [l / 100 km] 20.000 30.000 5 15 10 25000 Fig. 1: Graphical comparison of 6 cars, regarding price and milage. These solutions cannot be sorted by their relative quality to each other since the two goals (milage and price) are conflicting. The total order of solutions is lost. Only the car marked by the red dot is clearly worse, because there exist cars which are better with regards to both objectives. Of course, things get more difficult (and even more computationally expensive) if more than just two criteria have to be considered. For example, one could consider additional criteria like environmental sustainability or safety of the car. At the same time, this decision process can be made regarding different input parameters. For the consumer, the choice that affects the different criteria is merely that of the six cars available. For the producer of the cars, the cars can be defined by different parameters like their material, shape or type of motor. The field of Multi Criteria Optimization (MCO) deals with that type of problems. The Sequential Parameter Optimization Toolbox offers methods from that field, which employ surrogate models to speed up the optimization progress. The following Sec. 2introduces the field of MCO as well as the nomenclature. Afterwards, Sec. 3presents the programming environment R and some basic tools for MCO in that environment. To give an easy to use example, Sec. 4 introduces a simple MCO test function, and shows how to optimize this with 4 Zaefferer et al. classical MCO algorithms. The very same test functions is optimized with the Sequential Parameter Optimization Toolbox SPOT in Sec. 5. To give more details on the usage of SPOT additional features are shown in Sec. 6. Finally, the reader can test his understanding of the presented information in Sec. 7. 2 Short overview on MCO Considering only one objective in applied optimization is a simplification that does not mirror the complexity of the underlying application in most (or almost all) cases. Normally, more than one and up to hundreds or thousands of objectives f1, . . . , fnneed to be considered. The most common way to deal with multiple objectives appears to be aggregation, e.g., to a weighted sum f(x) = Piwifi(x). In contrast, multi-criteria or multiobjective optimization (MCO) offers a different way to handle multiple objectives in a more principled, maybe more effective way. In MCO, a well-known concept is Pareto dominance, i.e., a solution xfrom a decision space Adominates another solution y∈Aiff xis better in at least one dimension of the decision space and not worse in all the others. More formally and considering minimization, this reads (A⊂Rn,i, j ∈ {1, . . . , n}): x≺yiff ∀i:fi(x)≤fi(y)∧ ∃j:fj(x)< fj(y). If a solution xis not dominated by any other solution in the search space (or generated by the algorithm), it is said to be nondominated, i.e. ∀y∈A:y6≺ x. This concept allows for ranking sets of solutions in the multi-dimensional objective space. As a consequence, MCO algorithms aim for a set A∗of solutions with the property that every two solutions xand yfrom A∗are mutually nondominated, i.e. y6≺ x∧x6≺ y. A set {x∈A| 6 ∃y∈A:y≺x}of such solutions is also called a Pareto-front. Coming back to the car example from above, all but the car marked in red in Fig. 1are non-dominated, and thus represent the Pareto-front. The red point is dominated by two other dots. 2.1 Evolutionary Multiobjective Optimization Algorithms Beside the sheer number of objectives, there is a structural change in the step from one to more objectives. The strict order of solutions in the single-objective objective space turns to a partial order in the multi-objective objective space (with respect to Pareto dominance). This is one of the reasons why populationbased optimization approaches like EA are very successful in tackling MCO MCO with SPOT 5 problems. This structural change also implies that besides Pareto dominance a secondary quality indicator is required for ranking and thus for rank-based selection in an EA. As a result, evolutionary multiobjective optimization algorithms (EMOA) became very popular over the last decade(Deb,2001a;Coello Coello et al.,2007). Such algorithms always keep a set of solutions, also called a population, during the optimization run and thus provide a decision maker with a set of comparably good, non-dominated solutions, not just one final best like in singleobjective optimization. As a consequence, the decision maker has the chance and the burden to choose the final solution, the one to really implement, from a set of such solutions. In recent years, the hypervolume indicator turned from a frequently used quality indicator to a well-established selection operator for EMOA (Zitzler & Thiele,1998;Zitzler,1999). The hypervolume of a Pareto front A∗is defined as the n-dimensional volume of the space spanned by the Pareto front and a reference point yref, which needs to be defined by the user: Λ [ a∈A∗ {y0|a≺y0≺yref}! with Λ being the Lebesgue measure of the given set. Maximization of the hypervolume covered by the population results in maximization of possible trade-offs. Implicitly this covers the traditional goals of convergence of the solution set to the optimal front as well as good solution spread. Most prominent instances of hypervolume based selection MCO algorithms are SMS-EMOA (Beume et al.,2007a), Hyp-E (Bader & Zitzler,2011), as well as MO-CMA-ES (Igel et al.,2007). The (µ+ 1) selection mechanism in SMS-EMOA (cf. Alg. 1) provides an elegant way to enlarge and diminish the population size online. Therefore this algorithm is used for the present study. Algorithm 1: SMS-EMOA 1P0←init() ; // Initialize µindividuals randomly 2t←0 ; 3repeat 4qt+1 ←generate(Pt) ; // Generate offspring by variation 5Pt+1 ←reduce(Pt∪ {qt+1}) ; // Select new population 6t←t+ 1 7until stopcriterium reached; In Algorithm 2 ∆S(s, RI) := S(RI)− S(RI\ {s}) (1) 6 Zaefferer et al. Algorithm 2: Reduce(Q) 1R ← fast-nondominated-sort(Q) ; // all Inon-dominated fronts of Q 2r←argmins∈RI[∆S(s, RI)] ; // eliminate element with lowest ∆S(s, RI) 3Q0←Q\ {r}return Q0 calculates the sole contribution of a single solution sto the hypervolume of a Pareto front RI. MCO with SPOT 7 3 MCO in R: Language, Packages, Algorithms In R, the open source programming environment for statistical computing, some packages implement functionality for MCO1. We introduce three packages, which implement several important functions and algorithms. There are more MCO-relevant packages, which are not covered here. We encourage additional research for interested users2. 3.1 The mco package The mco package provides several functions concerning MCO with genetic algorithms. Most importantly, it provides an implementation of the NSGA2 algorithm. Several measures of a Pareto fronts quality are available as functions (e.g., Spread, Hypervolume, Epsilon-Indicator). Additionally, several typical MCO test functions are provided (e.g., ZDT1-3). 3.2 The emoa package The emoa package provides several useful functions, including several measures like hypervolume contribution or crowding distance. It also has several test functions that are not in the mco package. 3.3 The SPOT package The SPOT package provides mainly the means to do multi objective surrogate model based optimization. Additionally, it uses the emoa package to construct a very basic SMS-EMOA implementation. More information will be given in section 5. 4 A simple Testfunction: ZDT2 The test function used in the following examples is part of the ”mco” Rpackage3. In this example, it is expected that this package is already installed. To install, uncomment the first two lines below. The mco package also contains the NSGA2 algorithm (Deb,2001b). SPOT should be loaded, too, for the purpose of optimization. > #install.packages("mco") > #install.packages("SPOT") > require("mco") > require(SPOT) 1R, and all packages mentioned in this document, are available from the CRAN platform: http://cran.r-project.org/ 2The http://www.rseek.org/ home page might be a first start point for a search on MCO in R. 3http://cran.r-project.org/web/packages/mco/ 8 Zaefferer et al. The ZDT functions are MCO testfunctions with scalable decision space dimension n(Zitzler et al.,2000). To guarantee a low number of function evaluations as well as easy visualization of results, both, the dimension of the decision and the objective space are set to 2 in following example. The function ZDT2 R2→R2is defined as: f1=x1 g= 1 + 9x2 f2=g 1−x1 g2! 0≤x1≤1 0≤x2≤1 Both objectives f1and f2have to be minimized. In the R-package mean(), the ZDT2 function can be called as follows. > x=c(0.5,0.4) #Input vector > y=zdt2(x) > print(y) [1] 0.500000 4.545652 The objective space of the ZDT2 function can be visualized in separate surface plots. Therefore, we will consider the following function: R2→R: (x1, x2)7→ f1(x1, x2). Note, we will use the apply(x) command to define an anonymous function. > apply(x,1,f) will apply fto rows of x, > apply(x,2,f) will apply fto columns of x. > ## Define function that calls ZDT2 in a vectorized manner > ## but returns only first objective: > ZDT2obj1=function(x)apply(x,1,zdt2)[1,] > ## Plot first objective in given boundaries > ## (lo for lower, up for upper) > spotSurfContour(f=ZDT2obj1,lo=c(0,0),up=c(1,1)) MCO with SPOT 9 0.0 0.2 0.4 0.6 0.8 1.0 0.0 0.2 0.4 0.6 0.8 1.0 0.0 0.2 0.4 0.6 0.8 1.0 x1 x2 To visualize the impact of the second objective, we will consider the following function: R2→R: (x1, x2)7→ f2(x1, x2): > ## Define function that calls ZDT2 in a vectorized manner, > ## but returns only second objective: > ZDT2obj2=function(x)apply(x,1,zdt2)[2,] > ## Plot second objective in given boundaries > ## (lo for lower, up for upper) > spotSurfContour(f=ZDT2obj2,lo=c(0,0),up=c(1,1)) 16 Zaefferer et al. > spot(spotConfig=append(list(report.func="spotReportContour", + report.interactive=FALSE),res2),spotTask="rep") 0 2 4 6 8 10 ● ● ● ●●●●● ● ● ● ●● ● ●● ●●●● 0.0 0.4 0.8 0.0 0.2 0.4 0.6 0.8 1.0 predicted Model: Y.2 VARX1 VARX2 0.0 0.2 0.4 0.6 0.8 1.0 ● ● ● ●●●●● ● ● ● ●● ● ●● ●●●● 0.0 0.4 0.8 0.0 0.2 0.4 0.6 0.8 1.0 predicted Model: Y.1 VARX1 VARX2 In these contour plots, crosses indicate a point sampled on the target function and black dots (here: very close to the horizontal axis) indicate points that belong to the approximated Pareto front. With the above setting of report.interactive = FALSE, the surface plots will always show the behavior of the first two optimized parameters. If more than two are optimized, the user can use a simple GUI (see Fig. 2) to choose two parameters for plotting: > spot(spotConfig=append(list(report.func="spotReportContour", + report.interactive=TRUE),res2),spotTask="rep") Fig. 2: Twiddler interface Here, the user can choose which parameters to plot, using the sliders aand b. Slider Cspecifies which point from the Pareto front should be used to determine the remaining parameters, which are assumed to be constant for the plot. When just two parameters are optimized, this choice has no influence. 6.2 Different models for each objective In the above examples, each objective was modeled by the same chosen surrogate modeling technique. It could however occur, that the user wishes to model MCO with SPOT 17 the first objective with a Kriging model and the second with a Random Forest model. This is possible, by using the following configuration: > config$seq.predictionModel.func="spotPredictMCO" > config$mco.configs=list(list(seq.predictionModel.func="spotPredictForrester"), + list(seq.predictionModel.func="spotPredictRandomForest")) > res3<-spot(spotConfig=config) spot.R::spot started > res3$mco.hvolume [1] 110.097 Here, the mco.configs element is a meta-list containing several configuration lists. Any settings not specified in mco.configs will be taken from the main configuration list (here: config) or set to default values. Instead of selecting different models, one can use the mco.configs meta list to choose different settings for two models of the same type. 7 Tasks Imagine you have two target functions, both with a spherical shape, but with their center at different points. Assume that both functions are defined as: f1(x1, x2)=(x1−2)2+ (x2+ 4)2(2) f2(x1, x2)=(x1+ 1)2+ (x2−3)2(3) Together, these functions form a two-objective optimization problem, where both f1and f2are minimized. Please try to solve the following tasks: 1. Implement the optimization problem in R. 2. Plot the target functions separately. 3. Without using the computer any further, what do you expect the Pareto front to look like? Describe and/or draw your idea. 4. Optimize the problem, using the NSGA2 Algorithm in R. 5. Plot Pareto front and Pareto set of the NSGA2 results. 6. Optimize the problem using SPOT. 7. Plot the Pareto front and set, compare with NSGA2 results. Why do results differ? Also, Compare with expectation from question 3. 8. Plot the surrogate models with SPOT and check whether they represent the actual target functions. If not, why? 9. In your opinion, which is the most suited way to solve this specific optimization problem, and why? 8 Solutions Solutions to the tasks can be requested from the authors via E-Mail. Bibliography Bader, J. & Zitzler, E. (2011). HypE: An Algorithm for Fast Hypervolume-Based Many-Objective Optimization. Evolutionary Computation, 19(1), 45–76. Bartz-Beielstein, T., Lasarczyk, C., & Preuß, M. (2005). Sequential parameter optimization. In B. McKay & others (Eds.), Proceedings 2005 Congress on Evolutionary Computation (CEC’05), Edinburgh, Scotland, volume 1 (pp. 773– 780). Piscataway NJ: IEEE Press. Beume, N., Naujoks, B., & Emmerich, M. (2007a). SMS-EMOA: Multiobjective selection based on dominated hypervolume. European Journal of Operational Research, 181(3), 1653–1669. Beume, N., Naujoks, B., & Emmerich, M. (2007b). SMS-EMOA: Multiobjective selection based on dominated hypervolume. European Journal of Operational Research, 181(3), 1653–1669. Chen, C. H. (1995). An effective approach to smartly allocate computing budget for discrete event simulation. In Proceedings of the 34th IEEE Conference on Decision and Control (pp. 2598–2605). Coello Coello, C. A., Van Veldhuizen, D. A., & Lamont, G. B. (2007). Evolutionary Algorithms for Solving Multi-Objective Problems. Springer, New York, 2nd edition. Deb, K. (2001a). Multi-Objective Optimization using Evolutionary Algorithms. Wiley-Interscience Series in Systems and Optimization. New York NY: Wiley, 1 edition. Deb, K. (2001b). Multi-Objective Optimization using Evolutionary Algorithms. New York NY: Wiley. Friedman, J. H. (1991). Multivariate adaptive regression splines. Ann. Stat., 19(1), 1–141. Igel, C., Hansen, N., & Roth, S. (2007). Covariance Matrix Adaptation for Multi-objective Optimization. Evolutionary Computation, 15(1), 1–28. Zitzler, E. (1999). Evolutionary Algorithms for Multiobjective Optimization: Methods and Applications. PhD thesis, Swiss Federal Institute of Technology (ETH), Zurich, Switzerland. Zitzler, E., Deb, K., & Thiele, L. (2000). Comparison of Multiobjective Evolutionary Algorithms: Empirical Results. Evolutionary Computation, 8(2), 173–195. Zitzler, E. & Thiele, L. (1998). Multiobjective Optimization Using Evolutionary Algorithms—A Comparative Study. In A. E. Eiben (Ed.), Parallel Problem Solving from Nature (PPSN V) (pp. 292–301).: Springer, Berlin. Kontakt/Impressum Diese Ver¨ offentlichungen erscheinen im Rahmen der Schriftenreihe ”CIplus”. Alle Ver¨ offentlichungen dieser Reihe k¨ onnen unter www.ciplus-research.de oder unter http://opus.bsz-bw.de/fhk/index.php?la=de abgerufen werden. K¨ oln, Januar 2012 Herausgeber / Editorship Prof. Dr. Thomas Bartz-Beielstein, Prof. Dr. Wolfgang Konen, Prof. Dr. Horst Stenzel, Dr. Boris Naujoks Institute of Computer Science, Faculty of Computer Science and Engineering Science, Cologne University of Applied Sciences, Steinm¨ ullerallee 1, 51643 Gummersbach url: www.ciplus-research.de Schriftleitung und Ansprechpartner/ Contact editor’s office Prof. Dr. Thomas Bartz-Beielstein, Institute of Computer Science, Faculty of Computer Science and Engineering Science, Cologne University of Applied Sciences, Steinm¨ ullerallee 1, 51643 Gummersbach phone: +49 2261 8196 6391 url: http://www.gm.fh-koeln.de/~bartz/ eMail: [email protected] ISSN (online) 2194-2870