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