Erweiterte Suche

Automated and Feature-Based Problem Characterization and Algorithm Selection Through Machine Learning

Heutzutage sind zahlreiche Abläufe strukturiert, wodurch sich diese zunächst modellieren und anschliessend sogar optimieren lassen. Selbst Probleme, die nicht durch ein mathematisches Modell repräsentiert werden können (sogenannte "Black-Box Probleme") können optimiert werden. Leider treffen Menschen hierbei tendenziell schlechte Entscheidungen, da diese oftmals auf Versuchs-und-Irrtums-Experimenten oder schlichtweg auf dem "Bauchgefuehl" der Entscheider beruhen. Sinnvoller wäre es jedoch stattdessen Optimierungsalgorithmen zu verwenden. Allerdings gibt es hiervon sehr viele, sodass sich die Frage stellt, welcher Algorithmus am besten für die Optimierung des vorliegenden Problems geeignet ist. Im Rahmen dieser kumulativen Dissertation werden einerseits automatisch berechenbare Kennzahlen zur Charakterisierung der globalen Struktur kontinuierlicher Optimierungsprobleme, und andererseits experimentelle Studien, die die Vorzüge automatisierter, sowie feature-basierter Algorithmenselektion aufzeigen, vorgestellt.

Nowadays, numerous real-world workflows become more and more formalized and structured. One of the advantages of such formal processes is their accessibility for optimization. Even problems without an exact mathematical representation, i.e., so-called black-box problems, can be optimized. Unfortunately, people tend to make rather poor decisions when optimizing problems: most of the decisions are either based on numerous trial-and-error experiments or on "gut-decisions". Instead of these manual approaches, one could make use of computational power and execute an optimization algorithm. However, the plethora of optimizers leaves the user with the task of making a sophisticated guess on which of the available algorithms is best for the application at hand. Within this cumulative dissertation, a set of automatically computable features, which extracts information on the global structure of continuous optimization problems, as well as experimental studies, showing the benefits of automated and feature-based algorithm selection, are presented.

Titel: Automated and Feature-Based Problem Characterization and Algorithm Selection Through Machine Learning
Verfasser: Kerschke, Pascal GND
Dokumenttyp: Verschiedenartige Texte
Medientyp: Text
Erscheinungsdatum: 2017
Publikation in MIAMI: 06.02.2018
Datum der letzten Änderung: 06.02.2018
Quelle: Teilw. zugl.: Münster (Westfalen), Univ., kum. Diss., 2017
Schlagwörter: Algorithm Selection; Black-Box Optimierung; Exploratory Landscape Analysis; Maschinelles Lernen; einkriterielle Optimierung; Travelling Salesperson Problem; Funnel Detection
Algorithm Selection; Black-Box Optimization; Exploratory Landscape Analysis; Machine Learning; Single-Objective Optimization; Travelling Salesperson Problem; Funnel Detection
Fachgebiete: Informatik, Wissen, Systeme; Naturwissenschaften
Lizenz: CC BY-SA 4.0
Sprache: Englisch
Anmerkungen: Vollständige Druckausgabe der kumulativen Dissertation: Kerschke, Pascal: Automated and feature-based problem characterization and algorithm selection through machine learning. (kumulative Dissertation, Westfälische Wilhelms-Universität Münster, 2017) Münster, 2017, S. iii, 227 Seiten
Format: PDF-Dokument
URN: urn:nbn:de:hbz:6-39169612241
Permalink: https://nbn-resolving.org/urn:nbn:de:hbz:6-39169612241
Onlinezugriff:
Inhalt:
Acknowledgements ..... i
Abstract ..... ii
1 Introduction ..... 1
1.1 Benchmarking ..... 3
1.2 Exploratory Landscape Analysis ..... 4
1.3 Algorithm Selection ..... 5
2 Characterizing the Global Structure of Continuous Black-Box Problems ..... 7
2.1 Contributed Material ..... 7
2.2 Cell Mapping Techniques for Exploratory Landscape Analysis ..... 7
2.3 Detecting Funnel Structures by Means of Exploratory Landscape Analysis ..... 9
2.4 Low-Budget Exploratory Landscape Analysis on Multiple Peaks Models ..... 11
3 Flacco – A Toolbox for Exploratory Landscape Analysis with R ..... 13
3.1 Contributed Material ..... 13
3.2 The R-Package FLACCO for Exploratory Landscape Analysis with Applications to Multi-Objective Optimization Problems ..... 13
3.3 flaccogui: Exploratory Landscape Analysis for Everyone ..... 15
3.4 Comprehensive Feature-Based Landscape Analysis of Continuous and Constrained Optimization Problems Using the R-Package flacco ..... 17
4 Feature-Based Algorithm Selection from Optimizer Portfolios ..... 18
4.1 Contributed Material ..... 18
4.2 Improving the State of the Art in Inexact TSP Solving using Per-Instance Algorithm Selection ..... 18
4.3 Leveraging TSP Solver Complementarity through Machine Learning ..... 20
4.4 Automated Algorithm Selection on Continuous Black-Box Problems By Combining Exploratory Landscape Analysis and Machine Learning ..... 22
5 Platforms for Collaborative Research on Algorithm Selection and Machine Learning ..... 26
5.1 Contributed Material ..... 26
5.2 ASlib: A Benchmark Library for Algorithm Selection ..... 26
5.3 OpenML: An R Package to Connect to the Machine Learning Platform OpenML ..... 28
6 Summary and Outlook ..... 30
Bibliography ..... 33
Appendix: Contributed Publications
A Characterizing the Global Structure of Continuous Black-Box Problems ..... 42
A.1 Cell Mapping Techniques for Exploratory Landscape Analysis ..... 42
A.2 Detecting Funnel Structures By Means of Exploratory Landscape Analysis ..... 44
A.3 Low-Budget Exploratory Landscape Analysis on Multiple Peaks Models ..... 45
B Flacco – A Toolbox for Exploratory Landscape Analysis with R ..... 46
B.1 The R-Package FLACCO for Exploratory Landscape Analysis with Applications to Multi-Objective Optimization Problems ..... 46
B.2 flaccogui: Exploratory Landscape Analysis for Everyone ..... 47
B.3 Comprehensive Feature-Based Landscape Analysis of Continuous and Constrained Optimization Problems Using the R-Package flacco ..... 48
C Feature-Based Algorithm Selection from Optimizer Portfolios ..... 49
C.1 Improving the State of the Art in Inexact TSP Solving Using Per-Instance Algorithm Selection ..... 49
C.2 Leveraging TSP Solver Complementarity through Machine Learning ..... 50
C.3 Automated Algorithm Selection on Continuous Black-Box Problems By Combining Exploratory Landscape Analysis and Machine Learning ..... 51
D Platforms for Collaborative Research on Algorithm Selection and Machine Learning ..... 52
D.1 ASlib: A Benchmark Library for Algorithm Selection ..... 52
D.2 OpenML: An R Package to Connect to the Machine Learning Platform OpenML ..... 54