Automatic algorithm selection for complex simulation problems

Annotation To select the most suitable simulation algorithm for a given task is often difficult. This is due to intricate interactions between model features, implementation details, and runtime environment, which may strongly affect the overall performance. An automated selection of simulation algorithms supports users in setting up simulation experiments without demanding expert knowledge on simulation. Roland Ewald analyzes and discusses existing approaches to solve the algorithm selection problem in the context of simulation. He introduces a framework for automatic simulation algorithm selection and describes its integration into the open-source modelling and simulation framework James II. Its selection mechanisms are able to cope with three situations: no prior knowledge is available, the impact of problem features on simulator performance is unknown, and a relationship between problem features and algorithm performance can be established empirically. The author concludes with an experimental evaluation of the developed methods Automatic Algorithm Selection for Complex Simulation Problems Foreword Preface Contents List of Figures List of Tables List of Listings 1 Introduction 1.1 Motivation 1.2 Terminology 1.3 Examples 1.3.1 Simulation of Chemical Reaction Networks 1.3.2 Parallel and Distributed Discrete-Event Simulation 1.4 Epistemological Viewpoint 1.5 Structure Part I Background 2 Algorithm Selection 2.1 The Algorithm Selection Problem 2.1.3 Further ASP Properties 2.1.4 ASP in a Simulation Context 2.2 Analytical Algorithm Selection 2.3 Algorithm Selection as Learning 2.3.1 Error Sources, Error Types, and the Bias-Variance Trade-Off 2.3.2 Reinforcement Learning 2.3.3 Further Aspects of Learning 2.4 Algorithm Selection as Adaptation to Complexity 2.4.1 Complex Simulation Problems 2.4.2 Complex Adaptive Systems 2.4.3 Self-Adaptive Software and Autonomous Computing 2.5 Algorithm Portfolios 2.5.1 Identifying Efficient Portfolios 2.5.2 From Financial to Algorithmic Portfolios 2.5.3 Algorithm Portfolio Variants 2.5.4 Portfolios for Simulation Algorithm Selection 2.6 Categorization of Algorithm Selection Methods 2.6.1 Categorization Aspects 2.6.2 Summary 2.7 Applications of Algorithm Selection 2.8 Summary 3 Simulation Algorithm Performance Analysis 3.1 Challenges in Experimental Algorithmics 3.1.1 Efficient Implementations and Comparability 3.1.2 Reproducibility 3.1.3 Simulation Experiment Descriptions 3.2 Experiment Design 3.2.1 Variance Reduction 3.2.2 Optimization, Sensitivity Analysis, and Meta-Modeling 3.2.3 Further Aspects of Performance Experiments 3.3 Simulator Performance Analysis and Prediction 3.3.1 Analytical Methods 3.3.2 Empirical Methods 3.4 Summary Part II Methods and Implementation 4 A Framework for Simulation Algorithm Selection 4.1 Requirements Analysis: Use Cases 4.2 Brief Introduction to JAMES II 4.2.1 Fundamentals 4.2.2 Relation to Self-Adaptive Software 4.2.3 Limitations of Algorithm Selection in JAMES II 4.3 Technical Requirements for Algorithm Selection in JAMES II 4.4 A Simulation Algorithm Selection Framework 4.4.1 Related Software Systems 4.4.2 General Architecture 4.5 Summary 5 Storage of Performance Data 5.1 The SASF Performance Database 5.1.1 Entities 5.1.2 Generality 5.1.3 Implementation Details 5.2 Performance Recording & Feature Extraction 5.3 Summary 6 Selection Mapping Generation 6.1 Learning Algorithm Selection Mappings 6.2 A Framework for Simulator Performance Data Mining 6.2.1 Selector Generation 6.2.2 Selector Evaluation 6.2.3 Additional Components and Overview 6.2.4 Current Limitations 6.3 Summary 7 Experimentation Methodology 7.1 The Experimentation Layer of JAMES II 7.2 An Adaptive Simulation Runner 7.2.1 Implementation 7.2.2 Simulation Algorithm Portfolios 7.3 Automated Runtime Performance Exploration 7.3.1 Benchmark Modeling 7.3.2 Simulation End Time Calibration 7.3.3 Automated Performance Exploration with JAMES II 7.3.4 Automatic Experimentation for Standard Tasks 7.4 Summary 8 Automatic Simulation Algorithm Selection in JAMES II 8.1 An Algorithm Selection Registry for JAMES II 8.1.1 The Plug-in Life Cycle and the Plug-in Data Storage 8.1.2 Automated Failure Detection 8.1.3 Integration of Selection Mappings 8.2 Testing the Effectiveness of the Overall Approach 8.2.1 Test Setup 8.2.2 Results 8.3 Revisiting the SASF Requirements 8.3.1 Use Cases & User Interfaces 8.3.2 Technical Requirements 8.3.3 Summary Part III Examples and Conclusion 9 Case Study I: Chemical Reaction Networks 9.1 Algorithms under Consideration 9.1.1 A Sample Approach to SSA Performance Analysis 9.2 Experimental Evaluation 9.2.1 Setup 9.2.2 Simulation Space Exploration 9.2.3 Adaptive Replication 9.2.4 Selector Generation 9.3 Summary 10 Case Study II: Parallel Discrete-Event Simulation 10.1 Algorithms under Consideration 10.2 Experimental Evaluation 10.2.1 Setup 10.2.2 Simulation Space Exploration 10.2.3 Adaptive Replication 10.2.4 Selector Generation 10.3 Summary 11 Conclusions 11.1 Summary 11.2 Outlook A Appendix A.1 Theses A.2 Proof: Average and Adaptive Effectiveness A.3 Categorization of Algorithm Selection Approaches A.4 Performance Database: Tables A.5 Evaluating Simulation Algorithm Portfolio Selection with Synthetic Data A.5.1 Portfolio Performance Metrics A.5.2 Performance Data Generation A.5.3 Experiments A.5.4 Results A.6 Sample Listings Bibliography Index