ABSTRACT
Exploratory Landscape Analysis is a powerful technique for numerically characterizing landscapes of single-objective continuous optimization problems. Landscape insights are crucial both for problem understanding as well as for assessing benchmark set diversity and composition. Despite the irrefutable usefulness of these features, they suffer from their own ailments and downsides. Hence, in this work we provide a collection of different approaches to characterize optimization landscapes. Similar to conventional landscape features, we require a small initial sample. However, instead of computing features based on that sample, we develop alternative representations of the original sample. These range from point clouds to 2D images and, therefore, are entirely feature-free. We demonstrate and validate our devised methods on the BBOB testbed and predict, with the help of Deep Learning, the high-level, expert-based landscape properties such as the degree of multimodality and the existence of funnel structures. The quality of our approaches is on par with methods relying on the traditional landscape features. Thereby, we provide an exciting new perspective on every research area which utilizes problem information such as problem understanding and algorithm design as well as automated algorithm configuration and selection.
- Charu C Aggarwal, Alexander Hinneburg, and Daniel A Keim. 2001. On the surprising behavior of distance metrics in high dimensional space. In International conference on database theory. Springer, 420--434.Google ScholarDigital Library
- Mohamad Alissa, Kevin Sim, and Emma Hart. 2019. Algorithm Selection using Deep Learning without Feature Extraction. In Proceedings of the Genetic and Evolutionary Computation Conference. 198--206.Google ScholarDigital Library
- Jakob Bossek, Carola Doerr, and Pascal Kerschke. 2020. Initial Design Strategies and Their Effects on Sequential Model-based Optimization: An Exploratory Case Study Based on BBOB. In Proc. of the 22nd Annual Conference on Genetic and Evolutionary Computation (GECCO). 778--786.Google ScholarDigital Library
- Meng-Hao Guo, Jun-Xiong Cai, Zheng-Ning Liu, Tai-Jiang Mu, Ralph R Martin, and Shi-Min Hu. 2021. PCT: Point Cloud Transformer. Computational Visual Media 7, 2 (2021), 187--199.Google ScholarCross Ref
- Nikolaus Hansen, Anne Auger, Raymond Ros, Olaf Mersmann, Tea Tušar, and Dimo Brockhoff. 2021. COCO: A Platform for Comparing Continuous Optimizers in a Black-Box Setting. Optimization Methods and Software 36, 1 (2021), 114 -- 144.Google ScholarCross Ref
- Nikolaus Hansen, Steffen Finck, Raymond Ros, and Anne Auger. 2009. Real-Parameter Black-Box Optimization Benchmarking 2009: Noiseless Functions Defnitions. Technical Report RR-6829. INRIA. https://hal.inria.fr/inria-00362633/documentGoogle Scholar
- Sergey Ioffe and Christian Szegedy. 2015. Batch Normalization: Accelerating Deep Network Training by Reducing Internal Covariate Shift. In International conference on machine learning. PMLR, 448--456.Google Scholar
- Anja Jankovic, Tome Eftimov, and Carola Doerr. 2021. Towards Feature-Based Performance Regression Using Trajectory Data. In Applications of Evolutionary Computation (EvoApplications 2021), Vol. 12694. Springer, 601 -- 617.Google ScholarDigital Library
- Terry Jones and Stephanie Forrest. 1995. Fitness Distance Correlation as a Measure of Problem Difficulty for Genetic Algorithms. In Proceedings of the 6th International Conference on Genetic Algorithms (ICGA). Morgan Kaufmann Publishers Inc., 184 -- 192.Google Scholar
- Pascal Kerschke, Mike Preuss, Simon Wessing, and Heike Trautmann. 2015. Detecting Funnel Structures by Means of Exploratory Landscape Analysis. In Proceedings of the 17th Annual Conference on Genetic and Evolutionary Computation (GECCO) (Madrid, Spain). ACM, 265 -- 272.Google ScholarDigital Library
- Pascal Kerschke and Heike Trautmann. 2019. Automated Algorithm Selection on Continuous Black-Box Problems By Combining Exploratory Landscape Analysis and Machine Learning. Evolutionary Computation (ECJ) 27, 1 (2019), 99 -- 127.Google ScholarDigital Library
- Pascal Kerschke and Heike Trautmann. 2019. Comprehensive Feature-Based Landscape Analysis of Continuous and Constrained Optimization Problems Using the R-package flacco. In Applications in Statistical Computing. Springer, 93 -- 123. Google ScholarCross Ref
- Ying Li, Lingfei Ma, Zilong Zhong, Fei Liu, Michael A Chapman, Dongpu Cao, and Jonathan Li. 2020. Deep Learning for LiDAR Point Clouds in Autonomous Driving: A Review. IEEE Transactions on Neural Networks and Learning Systems 32, 8 (2020), 3412--3432.Google ScholarCross Ref
- Li Liu, Wanli Ouyang, Xiaogang Wang, Paul Fieguth, Jie Chen, Xinwang Liu, and Matti Pietikäinen. 2020. Deep Learning for Generic Object Detection: A Survey. International journal of computer vision 128, 2 (2020), 261--318.Google ScholarDigital Library
- Yongcheng Liu, Bin Fan, Shiming Xiang, and Chunhong Pan. 2019. Relation-Shape Convolutional Neural Network for Point Cloud Analysis. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition. 8895--8904.Google ScholarCross Ref
- Ilya Loshchilov and Frank Hutter. 2017. Decoupled Weight Decay Regularization. arXiv preprint arXiv:1711.05101 (2017).Google Scholar
- Monte Lunacek and L. Darrell Whitley. 2006. The Dispersion Metric and the CMA Evolution Strategy. In Proceedings of the 8th Annual Conference on Genetic and Evolutionary Computation (GECCO) (Seattle, WA, USA). ACM, 477 -- 484. Google ScholarDigital Library
- Ningning Ma, Xiangyu Zhang, Hai-Tao Zheng, and Jian Sun. 2018. Shufflenet v2: Practical Guidelines for Efficient CNN Architecture Design. In Proceedings of the European conference on computer vision (ECCV). 116--131.Google ScholarDigital Library
- Katherine Mary Malan and Andries Petrus Engelbrecht. 2009. Quantifying Ruggedness of Continuous Landscapes Using Entropy. In Proceedings of the IEEE Congress on Evolutionary Comp. (CEC). IEEE, 1440--1447.Google ScholarCross Ref
- Katherine Mary Malan and Andries Petrus Engelbrecht. 2013. A Survey of Techniques for Characterising Fitness Landscapes and Some Possible Ways Forward. Information Sciences (JIS) 241 (2013), 148 -- 163.Google ScholarDigital Library
- Olaf Mersmann, Bernd Bischl, Heike Trautmann, Mike Preuss, Claus Weihs, and Günter Rudolph. 2011. Exploratory Landscape Analysis. In Proceedings of the 13th Annual Conference on Genetic and Evolutionary Computation (GECCO) (Dublin, Ireland). ACM, 829 -- 836. Recipient of the 2021 ACM SigEVO Impact Award.Google ScholarDigital Library
- Olaf Mersmann, Mike Preuss, and Heike Trautmann. 2010. Benchmarking Evolutionary Algorithms: Towards Exploratory Landscape Analysis. In Proceedings of the 11th International Conference on Parallel Problem Solving from Nature (PPSN XI) (Krakow, Poland). Springer, 71--80. Google ScholarCross Ref
- Mario Andrés Muñoz Acosta, Michael Kirley, and Saman K. Halgamuge. 2015. Exploratory Landscape Analysis of Continuous Space Optimization Problems Using Information Content. IEEE Transactions on Evolutionary Computation (TEVC) 19, 1 (2015), 74 -- 87.Google ScholarDigital Library
- Christian L. Müller and Ivo F. Sbalzarini. 2011. Global Characterization of the CEC 2005 Fitness Landscapes Using Fitness-Distance Analysis. In European Conference on the Applications of Evolutionary Computation. Springer, 294 -- 303.Google Scholar
- Vinod Nair and Geoffrey E Hinton. 2010. Rectified Linear Units Improve Restricted Boltzmann Machines. In Icml.Google Scholar
- KJTL Pearson. 1901. On Lines and Planes of Closest Fit to System of Points in Space, Philos. Mug 6th ser. 2: 559 572 (1901).Google ScholarCross Ref
- F. Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, P. Prettenhofer, R. Weiss, V. Dubourg, J. Vanderplas, A. Passos, D. Cournapeau, M. Brucher, M. Perrot, and E. Duchesnay. 2011. Scikit-learn: Machine Learning in Python. Journal of Machine Learning Research 12 (2011), 2825 -- 2830.Google ScholarDigital Library
- Raphael Patrick Prager, Moritz Vinzent Seiler, Heike Trautmann, and Pascal Kerschke. 2021. Towards Feature-Free Automated Algorithm Selection for Single-Objective Continuous Black-Box Optimization. In Proceedings of the IEEE Symposium Series on Computational Intelligence. Orlando, Florida, USA.Google ScholarCross Ref
- Raphael Patrick Prager, Heike Trautmann, Hao Wang, Thomas H. W. Bäck, and Pascal Kerschke. 2020. Per-Instance Configuration of the Modularized CMA-ES by Means of Classifier Chains and Exploratory Landscape Analysis. In Proceedings of the IEEE Symposium Series on Computational Intelligence (SSCI) (Canberra, Australia). IEEE, 996 -- 1003.Google ScholarCross Ref
- Charles R Qi, Li Yi, Hao Su, and Leonidas J Guibas. 2017. Pointnet++: Deep Hierarchical Feature Learning on Point Sets in a Metric Space. arXiv preprint arXiv:1706.02413 (2017).Google Scholar
- Sebastian Raschka. 2018. MLxtend: Providing Machine Learning and Data Science Utilities and Extensions to Python's Scientific Computing Stack. The Journal of Open Source Software (JOSS) 3, 24 (April 2018).Google ScholarCross Ref
- Moritz Seiler, Janina Pohl, Jakob Bossek, Pascal Kerschke, and Heike Trautmann. 2020. Deep Learning as a Competitive Feature-Free Approach for Automated Algorithm Selection on the Traveling Salesperson Problem. In International Conference on Parallel Problem Solving from Nature. Springer, 48--64.Google ScholarDigital Library
- Peter Shaw, Jakob Uszkoreit, and Ashish Vaswani. 2018. Self-Attention with Relative Position Representations. arXiv preprint arXiv:1803.02155 (2018).Google Scholar
- Marina Sokolova and Guy Lapalme. 2009. A Systematic Analysis of Performance Measures for Classification Tasks. Information processing & management 45, 4 (2009), 427--437.Google Scholar
- Hugues Thomas, Charles R Qi, Jean-Emmanuel Deschaud, Beatriz Marcotegui, François Goulette, and Leonidas J Guibas. 2019. KPConv: Flexible and Deformable Convolution for Point Clouds. In Proceedings of the IEEE/CVF International Conference on Computer Vision. 6411--6420.Google ScholarCross Ref
- Vesselin K Vassilev, Terence C Fogarty, and Julian F Miller. 2000. Information Characteristics and the Structure of Landscapes. Evolutionary Computation (ECJ) 8, 1 (March 2000), 31 -- 60.Google ScholarDigital Library
- Peng-Shuai Wang, Yang Liu, Yu-Xiao Guo, Chun-Yu Sun, and Xin Tong. 2017. O-CNN: Octree-based Convolutional Neural Networks for 3d Shape Analysis. ACM Transactions On Graphics (TOG) 36, 4 (2017), 1--11.Google ScholarDigital Library
- Yue Wang, Yongbin Sun, Ziwei Liu, Sanjay E Sarma, Michael M Bronstein, and Justin M Solomon. 2019. Dynamic Graph CNN for Learning on Point Clouds. Acm Transactions On Graphics (tog) 38, 5 (2019), 1--12.Google ScholarDigital Library
- Sewall Wright. 1932. The Roles of Mutation, Inbreeding, Crossbreeding and Selection in Evolution. In Proceedings of the 6th International Congress of Genetics, Vol. 1. 356 -- 366.Google Scholar
- Min-Ling Zhang, Yu-Kun Li, Xu-Ying Liu, and Xin Geng. 2018. Binary Relevance for Multi-Label Learning: An Overview. Frontiers of Computer Science 12, 2 (2018), 191--202.Google ScholarDigital Library
Index Terms
- A collection of deep learning-based feature-free approaches for characterizing single-objective continuous fitness landscapes
Recommendations
Global characterization of the CEC 2005 fitness landscapes using fitness-distance analysis
EvoApplications'11: Proceedings of the 2011 international conference on Applications of evolutionary computation - Volume Part IWe interpret real-valued black-box optimization problems over continuous domains as black-box landscapes. The performance of a given optimization heuristic on a given problem largely depends on the characteristics of the corresponding landscape. ...
Fitness landscapes and graphs: multimodularity, ruggedness and neutrality
GECCO '12: Proceedings of the 14th annual conference companion on Genetic and evolutionary computationOne of the most commonly-used metaphors to describe the process of heuristic search methods in solving combinatorial optimization problems is that of a fitness landscape. The landscape metaphor appears most commonly in work related to evolutionary ...
Fitness landscapes and graphs: multimodularity, ruggedness and neutrality
GECCO '13 Companion: Proceedings of the 15th annual conference companion on Genetic and evolutionary computationOne of the most commonly-used metaphors to describe the process of heuristic search methods in solving combinatorial optimization problems is that of a fitness landscape. The landscape metaphor appears most commonly in work related to evolutionary ...
Comments