Klaus Varrentrapp

A Practical Framework for Adaptive Metaheuristics Klaus Varrentrapp

Local search methods (LSM) such as metaheuristics are useful tools to solve hard combinatorial optimization problems (COP). LSM can be further improved by identifying and exploiting regularities. This can be achieved by means of machine learning (ML) techniques to extend existing LSM. The author overviews how to integrate ML techniques into LSM to solve COP where only evaluative instead of constructive feedback can be obtained. A theoretical framework called Guided Adaptive Iterated Local Search (GAILS) is developed and investigated which demonstrates how to apply Reinforcement Learning (RL) to adaptively solve COP. The framework extends the well known and powerful metaheuristic Iterated Local Search and establishes the notion of a Local Search Agent that can be considered as an agent in a RL problem. An accompanying practical implementation framework for arbitrary GAILS algorithms is presented and theoretically as well as experimentally investigated. This book is written for readers interested in adaptive local search methods and the application of ML techniques in combinatorial optimization.