Pascal Kerschke
Mike Preuss
ABSTRACT
When selecting the best suited algorithm for an unknown optimization problem, it is useful to possess some a priori knowledge of the problem at hand. In the context of single-objective, continuous optimization problems such knowledge can be retrieved by means of Exploratory Landscape Analysis (ELA), which automatically identifies properties of a landscape, e.g., the so-called funnel structures, based on an initial sample. In this paper, we extract the relevant features (for detecting funnels) out of a large set of landscape features when only given a small initial sample consisting of 50 x D observations, where D is the number of decision space dimensions. This is already in the range of the start population sizes of many evolutionary algorithms. The new Multiple Peaks Model Generator (MPM2) is used for training the classifier, and the approach is then very successfully validated on the Black-Box Optimization Benchmark (BBOB) and a subset of the CEC 2013 niching competition problems.
- T. Abell, Y. Malitsky, and K. Tierney. Features for Exploiting Black-Box Optimization Problem Structure. In Learning and Intelligent Optimization, pages 30--36. Springer, 2013. Google Scholar
Digital Library
- B. Beachkofski and R. Grandhi. Improved distributed hypercube sampling. In Proceedings of the 43rd AIAA/ASME/ASCE/AHS/ASC Structures, Structural Dynamics, and Materials Conference. AIAA paper 2002--1274, American Institute of Aeronautics and Astronautics, 2002.Google ScholarCross Ref
- B. Bischl, O. Mersmann, H. Trautmann, and M. Preuss. 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, pages 313--320, New York, NY, USA, 2012. ACM. Google ScholarDigital Library
- J. Bossek. smoof: Single and Multi-Objective Optimization Test Functions, 2015. R package version 1.0.9000.Google Scholar
- R. Carnell. lhs: Latin Hypercube Samples, 2016. R package version 0.13.Google Scholar
- M. Gallagher. Multi-Layer Perceptron Error Surfaces: Visualization, Structure and Modelling. PhD thesis, University of Queensland, 2000.Google Scholar
- M. Gallagher and B. Yuan. A general-purpose tunable landscape generator. IEEE Transactions on Evolutionary Computation, 10(5):590--603, 2006. Google ScholarDigital Library
- N. Hansen, S. Finck, R. Ros, and A. Auger. Real-parameter black-box optimization benchmarking 2009: Noiseless functions definitions. Technical Report RR-6829, INRIA, 2009.Google Scholar
- A. Karatzoglou, A. Smola, K. Hornik, and A. Zeileis. kernlab -- An S4 Package for Kernel Methods in R. Journal of Statistical Software, 11(9):1--20, 2004.Google ScholarCross Ref
- S. A. Kauffman. The Origins of Order: Self-Organization and Selection in Evolution. Oxford University Press, 1993.Google Scholar
- P. Kerschke and J. Dagefoerde. flacco: Feature-Based Landscape Analysis of Continuous and Constraint Optimization Problems, 2015. R package version 1.2.Google Scholar
- P. Kerschke, M. Preuss, C. Hernández, O. Schütze, J.-Q. Sun, C. Grimme, G. Rudolph, B. Bischl, and H. Trautmann. Cell Mapping Techniques for Exploratory Landscape Analysis. In EVOLVE - A Bridge between Probability, Set Oriented Numerics, and Evolutionary Computation V, pages 115--131. Springer, 2014.Google Scholar
- P. Kerschke, M. Preuss, S. Wessing, and H. Trautmann. Detecting Funnel Structures by Means of Exploratory Landscape Analysis. In Proceedings of the 17th Annual Conference on Genetic and Evolutionary Computation, pages 265--272. ACM, 2015. Google ScholarDigital Library
- X. Li, A. Engelbrecht, and M. G. Epitropakis. Benchmark functions for CEC'2013 special session and competition on niching methods for multimodal function optimization. Technical report, RMIT University, Evolutionary Computation and Machine Learning Group, Australia, 2013.Google Scholar
- M. Lunacek and D. Whitley. The Dispersion Metric and the CMA Evolution Strategy. In Proceedings of the 8th Annual Conference on Genetic and Evolutionary Computation, pages 477--484. ACM, 2006. Google ScholarDigital Library
- O. Mersmann, B. Bischl, H. Trautmann, M. Preuss, C. Weihs, and G. Rudolph. Exploratory Landscape Analysis. In Proceedings of the 13th Annual Conference on Genetic and Evolutionary Computation, GECCO '11, pages 829--836, New York, NY, USA, 2011. ACM. Google ScholarDigital Library
- R. Morgan and M. Gallagher. Analysing and Characterising Optimization Problems Using Length Scale. Soft Computing, pages 1 -- 18, 2015.Google Scholar
- M. A. Munoz, M. Kirley, and S. K. Halgamuge. Exploratory Landscape Analysis of Continuous Space Optimization Problems using Information Content. Evolutionary Computation, IEEE Transactions on, 19(1):74--87, 2015.Google Scholar
- M. A. Munoz, Y. Sun, M. Kirley, and S. K. Halgamuge. Algorithm selection for black-box continuous optimization problems: A survey on methods and challenges. Information Sciences, 317:224 -- 245, 2015. Google ScholarDigital Library
- M. Preuss. Improved topological niching for real-valued global optimization. In Applications of Evolutionary Computation, volume 7248 of Lecture Notes in Computer Science, pages 386--395. Springer, 2012. Google ScholarDigital Library
- M. Preuss and C. Lasarczyk. On the importance of information speed in structured populations. In X. Yao, E. K. Burke, J. A. Lozano, J. Smith, J. J. Merelo-Guervos, J. A. Bullinaria, J. E. Rowe, P. Tino, A. Kaban, and H.-P. Schwefel, editors, Parallel Problem Solving from Nature -- PPSN VIII, volume 3242 of Lecture Notes in Computer Science, pages 91--100. Springer, 2004.Google Scholar
- J. Rönkkönen, X. Li, V. Kyrki, and J. Lampinen. A generator for multimodal test functions with multiple global optima. In X. Li, M. Kirley, M. Zhang, D. Green, V. Ciesielski, H. Abbass, Z. Michalewicz, T. Hendtlass, K. Deb, K. Tan, J. Branke, and Y. Shi, editors, Simulated Evolution and Learning, volume 5361 of Lecture Notes in Computer Science, pages 239--248. Springer, 2008. Google ScholarDigital Library
- Y. Saka, M. Gunzburger, and J. Burkardt. Latinized, improved LHS, and CVT point sets in hypercubes. International Journal of Numerical Analysis and Modeling, 4(3--4):729--743, 2007.Google Scholar
- S. Wessing. Two-stage methods for multimodal optimization. PhD thesis, Technische Universit\"at Dortmund, 2015.Google Scholar
- S. Wessing. optproblems: Infrastructure to define optimization problems and some test problems for black-box optimization, 2016. Python package version 0.6. https://pypi.python.org/pypi/optproblems.Google Scholar
- S. Wessing, M. Preuss, and G. Rudolph. Niching by multiobjectivization with neighbor information: Trade-offs and benefits. In IEEE Congress on Evolutionary Computation (CEC), pages 103--110, 2013.Google ScholarCross Ref
Index Terms
- Low-Budget Exploratory Landscape Analysis on Multiple Peaks Models
Recommendations
Detecting Funnel Structures by Means of Exploratory Landscape Analysis
GECCO '15: Proceedings of the 2015 Annual Conference on Genetic and Evolutionary ComputationIn single-objective optimization different optimization strategies exist depending on the structure and characteristics of the underlying problem. In particular, the presence of so-called funnels in multimodal problems offers the possibility of applying ...
Advanced fitness landscape analysis and the performance of memetic algorithms
Special issue on magnetic algorithmsMemetic algorithms (MAs) have demonstrated very effective in combinatorial optimization. This paper offers explanations as to why this is so by investigating the performance of MAs in terms of efficiency and effectiveness. A special class of MAs is used ...
Is "best-so-far" a good algorithmic performance metric?
GECCO '08: Proceedings of the 10th annual conference on Genetic and evolutionary computationIn evolutionary computation, experimental results are commonly analyzed using an algorithmic performance metric called best-so-far. While best-so-far can be a useful metric, its use is particularly susceptible to three pitfalls: a failure to establish a ...
Comments