Battiti / Brunato / Mascia Reactive Search and Intelligent Optimization

1. Auflage 2008
ISBN: 978-0-387-09624-7
Verlag: Springer
Format: PDF
Kopierschutz: 1 - PDF Watermark

E-Book, Englisch, Band 45, 196 Seiten

Reihe: Operations Research/Computer Science Interfaces Series

Reactive Search and Intelligent Optimization is an excellent introduction to the main principles of reactive search, as well as an attempt to develop some fresh intuition for the approaches. The book looks at different optimization possibilities with an emphasis on opportunities for learning and self-tuning strategies. While focusing more on methods than on problems, problems are introduced wherever they help make the discussion more concrete, or when a specific problem has been widely studied by reactive search and intelligent optimization heuristics. Individual chapters cover reacting on the neighborhood; reacting on the annealing schedule; reactive prohibitions; model-based search; reacting on the objective function; relationships between reactive search and reinforcement learning; and much more. Each chapter is structured to show basic issues and algorithms; the parameters critical for the success of the different methods discussed; and opportunities for the automated tuning of these parameters.

Autoren/Hrsg.

Battiti, Roberto

Brunato, Mauro

Mascia, Franco

Inhaltsverzeichnis

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