Reactive Search and Intelligent Optimization (eBook)

Contents 6
Acknowledgments 9
Introduction: Machine Learning for Intelligent Optimization 11
1.1 Parameter Tuning and Intelligent Optimization 14
1.2 Book Outline 17
Reacting on the Neighborhood 19
2.1 Local Search Based on Perturbations 19
2.2 Learning How to Evaluate the Neighborhood 23
2.3 Learning the Appropriate Neighborhood in Variable Neighborhood Search 24
2.4 Iterated Local Search 28
Reacting on the Annealing Schedule 34
3.1 Stochasticity in Local Moves and Controlled Worsening of Solution Values 34
3.2 Simulated Annealing and Asymptotics 35
3.3 Online Learning Strategies in Simulated Annealing 38
Reactive Prohibitions 43
4.1 Prohibitions for Diversification 43
4.2 Reactive Tabu Search: Self-Adjusted Prohibition Period 57
4.3 Implementation: Storing and Using the Search History 60
Reacting on the Objective Function 67
5.1 Dynamic Landscape Modifications to Influence Trajectories 67
5.2 Eliminating Plateaus by Looking Inside the Problem Structure 74
Model-Based Search 76
6.1 Models of a Problem 76
6.2 An Example 78
6.3 Dependent Probabilities 80
6.4 The Cross-Entropy Model 82
6.5 Adaptive Solution Construction with Ant Colonies 84
6.6 Modeling Surfaces for Continuous Optimization 86
Supervised Learning 89
7.1 Learning to Optimize, from Examples 89
7.2 Techniques 90
7.3 Selecting Features 108
7.4 Applications 112
Reinforcement Learning 122
8.1 Reinforcement Learning Basics: Learning from a Critic 122
8.2 Relationships Between Reinforcement Learning and Optimization 130
Algorithm Portfolios and Restart Strategies 134
9.1 Introduction: Portfolios and Restarts 134
9.2 Predicting the Performance of a Portfolio from its Component Algorithms 135
9.3 Reactive Portfolios 139
9.4 Defining an Optimal Restart Time 140
9.5 Reactive Restarts 143
Racing 145
10.1 Exploration and Exploitation of Candidate Algorithms 145
10.2 Racing to Maximize Cumulative Reward by Interval Estimation 146
10.3 Aiming at the Maximum with Threshold Ascent 148
10.4 Racing for Off-Line Configuration of Metaheuristics 149
Teams of Interacting Solvers 154
11.1 Complex Interaction and Coordination Schemes 154
11.2 Genetic Algorithms and Evolution Strategies 155
11.3 Intelligent and Reactive Solver Teams 159
11.4 An Example: Gossiping Optimization 162
Metrics, Landscapes, and Features 166
12.1 How to Measure and Model Problem Difficulty 166
12.2 Phase Transitions in Combinatorial Problems 167
12.3 Empirical Models for Fitness Surfaces 168
12.4 Measuring Local Search Components: Diversification and Bias 173
Open Problems 180
References 183
Index 196