nach oben

Erschienen in:

2019 | OriginalPaper | Buchkapitel

7. Comprehensive Feature-Based Landscape Analysis of Continuous and Constrained Optimization Problems Using the R-Package Flacco

verfasst von : Pascal Kerschke, Heike Trautmann

Erschienen in: Applications in Statistical Computing

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

Choosing the best-performing optimizer(s) out of a portfolio of optimization algorithms is usually a difficult and complex task. It gets even worse, if the underlying functions are unknown, i.e., so-called black-box problems, and function evaluations are considered to be expensive. In case of continuous single-objective optimization problems, exploratory landscape analysis (ELA), a sophisticated and effective approach for characterizing the landscapes of such problems by means of numerical values before actually performing the optimization task itself, is advantageous. Unfortunately, until now it has been quite complicated to compute multiple ELA features simultaneously, as the corresponding code has been—if at all—spread across multiple platforms or at least across several packages within these platforms. This article presents a broad summary of existing ELA approaches and introduces flacco, an R-package for feature-based landscape analysis of continuous and constrained optimization problems. Although its functions neither solve the optimization problem itself nor the related algorithm selection problem (ASP), it offers easy access to an essential ingredient of the ASP by providing a wide collection of ELA features on a single platform—even within a single package. In addition, flacco provides multiple visualization techniques, which enhance the understanding of some of these numerical features, and thereby make certain landscape properties more comprehensible. On top of that, we will introduce the package’s built-in, as well as web-hosted and hence platform-independent, graphical user interface (GUI). It facilitates the usage of the package—especially for people who are not familiar with R—and thus makes flacco a very convenient toolbox when working towards algorithm selection of continuous single-objective optimization problems.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Vorheriges Kapitel Heteroscedastic Discriminant Analysis Using R

Nächstes Kapitel A Note on Artificial Intelligence and Statistics

In this context, an instance is the equivalent to an optimization problem, i.e., it maps the elements of the decision space \(\mathscr {X}\) to the objective space \(\mathscr {Y}\).

The authors intend to extend flacco by any feature set that has not yet been integrated into it.

In case of a 10-dimensional problem in which each input variable is discretized by three blocks, one already needs \(3^{10}\) \(=\) 59,049 observations to have one observation per cell—on average.

If a point is a local optimum the gradient is zero for all dimensions of a sample point, then the ratio of biggest and smallest gradient obviously cannot be computed and therefore results in a missing value (\(=\) NA).

The default classifiers are linear (LDA), quadratic (QDA) and mixture discriminant analysis (MDA) and the default threshold for dividing the data set into two groups are the 10%-, 25%- and 50%-quantile of the objective values.

Here, the “nearest better neighbor” is the observation, which is the nearest neighbor among the set of all observations with a better objective value.

The development version is available on GitHub: https://github.com/kerschke/flacco.

The stable release is published on CRAN: https://cran.r-project.org/package=flacco.

Link to the package’s tutorial: http://kerschke.github.io/flacco-tutorial/.

Link to the package’s GUI: https://flacco.shinyapps.io/flacco/.

Note that the shown numbers, especially the ones for the number of observations per cell, might be different on your machine, as the initial sample is drawn randomly.

The barrier tree features can only be computed if the total number of cells is at least two and the cell mapping convexity features require at least three blocks per dimension.

A more detailed step-by-step example can be found in the documentation of the respective flacco-function plotFeatureImportancePlot.

As many of the features are stochastic, it is highly recommended to compute the features multiple(\(=\) at least 5 to 10) times.

COSEAL is an international group of researchers with a focus on the Configuration and Selection of Algorithms, cf. http://www.coseal.net/.

The European Center of Information Systems (ERCIS) is an international network in the field of Information Systems, cf. https://www.ercis.org/.

Abell, T., Malitsky, Y., & Tierney, K. (2013). Features for exploiting black-box optimization problem structure. In Learning and intelligent optimization (pp. 30–36). Berlin: Springer.

Beachkofski, B. K., & Grandhi, R. V. (2002). Improved distributed hypercube sampling. In 43rd AIAA/ASME/ASCE/AHS/ASC structures, structural dynamics, and materials conference.

Bischl, B., Lang, M., Kotthoff, L., Schiffner, J., Richter, J., & Studerus, E., et al. (2016). mlr: Machine Learning in R. Journal of Machine Learning Research, 17(170), 1–5. R-package version 2.10.

Bischl, B., Mersmann, O., Trautmann, H., & Preuss, M. (2012). Algorithm selection based on exploratory landscape analysis and cost-sensitive learning. In Proceedings of the 14th Annual Conference on Genetic and Evolutionary Computation, GECCO ’12 (pp. 313–320). New York: ACM.

Bossek, J. (2017). smoof: Single-and multi-objective optimization test functions. The R Journal. https://journal.r-project.org/archive/2017/RJ-2017-004/index.html.

Byrd, R. H., Peihuang, L., Nocedal, J., & Zhu, C. (1995). A limited memory algorithm for bound constrained optimization. SIAM Journal on Scientific Computing, 16(5), 1190–1208.

Chang, W., Cheng, J., Allaire, J. J., Xie, Y., & McPherson, J. (2016). Shiny: Web application framework for R. R-package version 0.14.1.

Christoph, F., Hofacker, I. L., Stadler, P. F., & Wolfinger, M. T. (2002). Barrier trees of degenerate landscapes. Zeitschrift für Physikalische Chemie International Journal of Research in Physical Chemistry and Chemical Physics216(2/2002), 155.

Daolio, F., Liefooghe, A., Verel, S., Aguirre, H., & Tanaka, K. (2016). Problem features versus algorithm performance on rugged multi-objective combinatorial fitness landscapes. Evolutionary Computation.

Friedman, J. H. (1997). On bias, variance, 0/1–loss, and the curse-of-dimensionality. Data Mining and Knowledge Discovery, 1(1), 55–77.

Guido VanRossum and The Python Development Team. (2015). The Python Language Reference–Release 3.5.0. Python Software Foundation.

Hansen, N., Auger, A., Finck, S., & Ros, R. (2010). Real-parameter black-box optimization benchmarking 2010: experimental setup. Technical Report RR-7215, INRIA.

Hansen, N., Finck, S., Ros, R., & Auger, A. (2009). Real-parameter black-box optimization benchmarking 2009: noiseless functions definitions. Technical Report RR-6829, INRIA.

Hanster, C., & Kerschke, P. (2017). Flaccogui: Exploratory landscape analysis for everyone.

Hutter, F., Lin, X., Hoos, H. H., & Leyton-Brown, K. (2014). Algorithm runtime prediction: Methods and evaluation. Journal of Artificial Intelligence, 206, 79–111.

Jobson, J. (2012). Applied multivariate data analysis: Volume II: Categorical and multivariate methods. Berlin: Springer.

Jones, T. (1995). Evolutionary algorithms, fitness landscapes and search. Ph.D. thesis, Citeseer.

Jones, T., & Forrest, S. (1995). Fitness distance correlation as a measure of problem difficulty for genetic algorithms. In Proceedings of the 6th international conference on genetic algorithms (pp. 184–192). Morgan Kaufmann Publishers Inc.

Kerschke, P. (2017). Flacco: Feature-based landscape analysis of continuous and constrained optimization problems. R-package version 1.6.

Kerschke, P., & Trautmann, H. (2016). The R-package FLACCO for exploratory landscape analysis with applications to multi-objective optimization problems. In Proceedings of the IEEE congress on evolutionary computation (CEC). IEEE.

Kerschke, P., Preuss, M., Hernández, C., Schütze, O., Sun, J.- Q., Grimme, C., et al. (2014). Cell mapping techniques for exploratory landscape analysis. In EVOLVE—A bridge between probability, set oriented numerics, and evolutionary computation V (pp. 115–131). Berlin: Springer.

Kerschke, P., Preuss, M., Wessing, S., & Trautmann, H. (2015). Detecting funnel structures by means of exploratory landscape analysis. In Proceedings of the 17th annual conference on genetic and evolutionary computation (pp. 265–272). ACM.

Kerschke, P., Preuss, M., Wessing, S., & Trautmann, H. (2016). Low-budget exploratory landscape analysis on multiple peaks models. In Proceedings of the 18th annual conference on genetic and evolutionary computation. ACM.

Lunacek, M., & Whitley, D. (2006). The dispersion metric and the CMA evolution strategy. In Proceedings of the 8th annual conference on genetic and evolutionary computation (pp. 477–484). ACM.

Malan K. M., Oberholzer, J. F., & Engelbrecht, A. P. (2015). Characterising constrained continuous optimisation problems. In Proceedings of the IEEE congress on evolutionary computation (CEC) (pp. 1351–1358). IEEE.

Malan, K. M., & Engelbrecht, A. P. (2009). Quantifying ruggedness of continuous landscapes using entropy. In Proceedings of the IEEE congress on evolutionary computation (CEC) (pp. 1440–1447). IEEE.

MATLAB. (2013). Version 8.2.0 (R2013b). The MathWorks Inc., Natick, Massachusetts.

McKay, M. D., Beckman, R. J., & Conover, W. J. (2000). A comparison of three methods for selecting values of input variables in the analysis of output from a computer code. Technometrics, 42(1), 55–61.

Mersmann, O. (2014). Microbenchmark: Accurate timing functions. R-package version 1.4-2.

Mersmann, O., Bischl, B., Trautmann, H., Preuss, M., Weihs, C., & Rudolph, G. (2011). Exploratory landscape analysis. In Proceedings of the 13th annual conference on genetic and evolutionary computation, GECCO ’11 (pp. 829–836). New York: ACM.

Mersmann, O., Bischl, B., Trautmann, H., Wagner, M., Bossek, J., & Neumann, F. (2013). A novel feature-based approach to characterize algorithm performance for the traveling salesperson problem. Annals of Mathematics and Artificial Intelligence, 69(2), 151–182.

Morgan, R., & Gallagher, M. (2015). Analysing and characterising optimization problems using length scale. Soft Computing, 1–18.

Müller, C. L., & Sbalzarini, I. F. (2011). Global characterization of the CEC 2005 fitness landscapes using fitness-distance analysis. In Applications of evolutionary computation (pp. 294–303). Berlin: Springer.

Muñoz, M. A., Kirley, M., & Halgamuge, S. K. (2012). Landscape characterization of numerical optimization problems using biased scattered data. In 2012 IEEE congress on evolutionary computation (CEC) (pp. 1–8). IEEE.

Muñoz, M. A., Kirley, M., & Halgamuge, S. K. (2015a). Exploratory landscape analysis of continuous space optimization problems using information content. IEEE transactions on evolutionary computation, 19(1), 74–87.

Muñoz, M. A., Sun, Y., Kirley, M., & Halgamuge, S. K. (2015b). Algorithm selection for black-box continuous optimization problems: A survey on methods and challenges. Information Sciences, 317, 224–245.

Ochoa, G., Verel, S., Daolio, F., & Tomassini, M. (2014). Local optima networks: A new model of combinatorial fitness landscapes. In Recent advances in the theory and application of fitness landscapes (pp. 233–262). Berlin: Springer.

Pihera, J., & Musliu, N. (2014). Application of machine learning to algorithm selection for TSP. In Proceedings of the IEEE 26th international conference on tools with artificial intelligence (ICTAI). IEEE press.

R Core Team. (2018). R: A language and environment for statistical computing. R foundation for statistical computing. Vienna, Austria.

Rice, J. R. (1976). The algorithm selection problem. Advances in Computers, 15, 65–118.

Shirakawa, S., & Nagao, T. (2016). Bag of local landscape features for fitness landscape analysis. Soft Computing, 20(10), 3787–3802.

Sievert, C., Parmer, C., Hocking, T., Chamberlain, S., Ram, K., Corvellec, M., et al. (2016). Plotly: Create interactive web graphics via ‘plotly.js’. R-package version 4.5.6.

Titel: Comprehensive Feature-Based Landscape Analysis of Continuous and Constrained Optimization Problems Using the R-Package Flacco
verfasst von: Pascal Kerschke
Heike Trautmann
Verlag: Springer International Publishing
Buch: Applications in Statistical Computing
Print ISBN: 978-3-030-25146-8

Electronic ISBN: 978-3-030-25147-5

Copyright-Jahr: 2019
DOI: https://doi.org/10.1007/978-3-030-25147-5_7

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner