Local search methods are useful tools for tackling hard problems such as many combinatorial optimization problems (COP). Experience from mathematics has shown that exploiting regularities in problem solving is beneficial. Consequently, identifying and exploiting regularities in the context of local search methods is deemed to be desirable, too. Due to the complexity of the COPs tackled, regularities might better be detected and learned automatically. This can be achieved by means of machine learning techniques to extend existing local search methods. Learning requires feedback, but in the context of local search methods, instructive feedback is not available. Instead, evaluative feedback can be derived from the cost function of COPs evaluating single solutions, for example. Reinforcement learning (RL) is a machine learning technique that only needs evaluative feedback. A particular RL method is called Q-learning. The present thesis attempts to develop learning local search methods in a general and practical manner. One possibility to enhance local search methods with learning capabilities is by using RL methods. The direct application of existing RL techniques for extending existing local search methods is enabled by the concept of a local search agent (LSA). The advancement of a trajectory-based local search method can be regarded as the interaction of a virtual agent whose states basically consist of solutions and whose actions are composed of arbitrary hierarchical compositions of local search operators. The resulting LSA using RL can then be called a learning LSA. The changes in cost for each move of a learning LSA can be used as reward. Based on these, returns can be computed such that maximizing the return reflects the goal of finding a global or a very good local optimum. The hierarchical structure of LSA actions allows to use so-called ILS-actions. ILS-actions coincide with the application of one iteration of the well-known Iterated Local Search (ILS) metaheuristic. The advantage of this metaheuristic and this kind of action is that only solutions from the subset of local optima -- which must contain any acceptable solution -- are considered and thus introduces a search space abstraction which in turn can improve performance. A learning LSA that employs ILS-actions iteratively will visit local optima in a guided and adaptive manner. The resulting theoretical framework is called Guided Adaptive Iterated Local Search (GAILS). In order to evaluate randomized GAILS algorithms, empirical experiments have to be conducted. Each GAILS algorithm thereby consists of three, mainly independent parts. The first part comprises the actions of a learning LSA which are specific to a problem type. The LSA actions being arbitrary hierarchical compositions of local search operators are implemented through basic local search operators. The second part represents the RL techniques used, which in turn transparently use actions and hence are problem type independent. The third part consists of the function approximators used by RL techniques. The function approximators only require as input a vector of real-valued features and this way are independent from the first two parts. Empirical experiments can be supported by providing a framework that can decouple these three main parts in any GAILS algorithm program instantiation, thus allowing for an arbitrary reuse and combination enabling rapid prototyping. The GAILS implementation framework is such an application framework which is designed to rapidly implement learning LSAs reflecting the separation of a learning LSA into its three main parts. It provides generic interfaces between components of the three parts and this way provides for a separation of problem type specific states from search control. It also provides for a separation of search control from the state of the search control unit. Hierarchically built actions are mapped to object hierarchies. Two GAILS algorithms according to Q-learning algorithm Q(0) and Q(λ) that are based on ILS-actions were developed, built and compared to corresponding standard implementations of the ILS metaheuristic. These so-called Q-ILS algorithms were tested for two problems using different function approximators. The results showed that learning useful policies and transfer of what was learned across multiple problem instances, even of different sizes, is possible and useful.
| Typ des Eintrags: |
Dissertation
|
| Erschienen: |
2005 |
| Autor(en): |
Varrentrapp, Klaus E. |
| Art des Eintrags: |
Erstveröffentlichung |
| Titel: |
A Practical Framework for Adaptive Metaheuristics |
| Sprache: |
Englisch |
| Referenten: |
Bibel, Prof. Dr. Wolfgang ; Fürnkranz, Prof. Dr. Johannes |
| Berater: |
Bibel, Prof. Dr. Wolfgang |
| Publikationsjahr: |
7 Juni 2005 |
| Ort: |
Darmstadt |
| Verlag: |
Technische Universität |
|
Datum der mündlichen Prüfung: |
30 Mai 2005 |
| URL / URN: |
urn:nbn:de:tuda-tuprints-5675 |
| Kurzbeschreibung (Abstract): |
Local search methods are useful tools for tackling hard problems such as many combinatorial optimization problems (COP). Experience from mathematics has shown that exploiting regularities in problem solving is beneficial. Consequently, identifying and exploiting regularities in the context of local search methods is deemed to be desirable, too. Due to the complexity of the COPs tackled, regularities might better be detected and learned automatically. This can be achieved by means of machine learning techniques to extend existing local search methods. Learning requires feedback, but in the context of local search methods, instructive feedback is not available. Instead, evaluative feedback can be derived from the cost function of COPs evaluating single solutions, for example. Reinforcement learning (RL) is a machine learning technique that only needs evaluative feedback. A particular RL method is called Q-learning. The present thesis attempts to develop learning local search methods in a general and practical manner. One possibility to enhance local search methods with learning capabilities is by using RL methods. The direct application of existing RL techniques for extending existing local search methods is enabled by the concept of a local search agent (LSA). The advancement of a trajectory-based local search method can be regarded as the interaction of a virtual agent whose states basically consist of solutions and whose actions are composed of arbitrary hierarchical compositions of local search operators. The resulting LSA using RL can then be called a learning LSA. The changes in cost for each move of a learning LSA can be used as reward. Based on these, returns can be computed such that maximizing the return reflects the goal of finding a global or a very good local optimum. The hierarchical structure of LSA actions allows to use so-called ILS-actions. ILS-actions coincide with the application of one iteration of the well-known Iterated Local Search (ILS) metaheuristic. The advantage of this metaheuristic and this kind of action is that only solutions from the subset of local optima -- which must contain any acceptable solution -- are considered and thus introduces a search space abstraction which in turn can improve performance. A learning LSA that employs ILS-actions iteratively will visit local optima in a guided and adaptive manner. The resulting theoretical framework is called Guided Adaptive Iterated Local Search (GAILS). In order to evaluate randomized GAILS algorithms, empirical experiments have to be conducted. Each GAILS algorithm thereby consists of three, mainly independent parts. The first part comprises the actions of a learning LSA which are specific to a problem type. The LSA actions being arbitrary hierarchical compositions of local search operators are implemented through basic local search operators. The second part represents the RL techniques used, which in turn transparently use actions and hence are problem type independent. The third part consists of the function approximators used by RL techniques. The function approximators only require as input a vector of real-valued features and this way are independent from the first two parts. Empirical experiments can be supported by providing a framework that can decouple these three main parts in any GAILS algorithm program instantiation, thus allowing for an arbitrary reuse and combination enabling rapid prototyping. The GAILS implementation framework is such an application framework which is designed to rapidly implement learning LSAs reflecting the separation of a learning LSA into its three main parts. It provides generic interfaces between components of the three parts and this way provides for a separation of problem type specific states from search control. It also provides for a separation of search control from the state of the search control unit. Hierarchically built actions are mapped to object hierarchies. Two GAILS algorithms according to Q-learning algorithm Q(0) and Q(λ) that are based on ILS-actions were developed, built and compared to corresponding standard implementations of the ILS metaheuristic. These so-called Q-ILS algorithms were tested for two problems using different function approximators. The results showed that learning useful policies and transfer of what was learned across multiple problem instances, even of different sizes, is possible and useful. |
|
Alternatives oder übersetztes Abstract: |
|
Alternatives Abstract | Sprache |
|---|
Lokale Suchmethoden sind nützliche Werkzeuge zum Lösen schwieriger kombinatorischer Optimierungsprobleme (KOP). Generelle Erfahrung aus dem Bereich der Mathematik haben gezeigt, dass es bei der Problemlösung sehr hilfreich ist, Regelmäßigkeiten und die ihnen zugrunde liegenden Gestzmäßigkeiten zu identifizieren und auch auszunutzen. Folglich erscheint es sinnvoll, dies auch für lokale Suchmethoden zu versuchen. Aufgrund der Komplexität der bearbeiteten KOP erscheint es besser, diesen Vorgang zu automatisieren, z.B. durch Anwendung von Techniken des maschinellen Lernens zur Erweiterung von lokalen Suchmethoden. Lernen braucht allerdings gewisse Rückmeldungen. Im Bereich von lokalen Suchmethoden kann so eine Rückmeldung aber nicht instruktiv sein, sondern nur bewertender Natur. Verstärkungslernen (VL) ist eine maschinelle Lerntechnik, die mit bewertenden Rückmeldungen arbeiten kann. Eine VL Methode ist das sogenannte Q-Lernen. Diese Arbeit entwickelt Ansätze für allgemeine, praktisch einsetzbare und automatisch lernende lokale Suchmethoden. Eine Möglichkeit lokale Suchmethoden mit Techniken des maschinellen Lernens zu erweitern besteht in der Anwendung von VL Methoden. Die direkte Anwendung von VL Methoden auf existierende lokale Suchmethoden wird durch das Konzept eines lokalen Suchagenten (LSA) ermöglicht. Das schrittweise Vorgehen einer trajektorien-basierten lokalen Suchmethode kann als Interaktion eines virtuellen Agenten mit der zu lösenden Instanz aufgefasst werden. Die Agentenzustände entsprechen hierbei den Lösungen und die Agentenaktionen bestehen aus beliebig hierarchisch aufgebauten Komposititionen von lokalen Suchoperatoren. Ein solcher durch VL Methoden erweiterter LSA kann als lernender LSA bezeichnet werden. Kostenveränderungen bzgl. der beteiligten Lösungen von Zustandstransitionen können als Belohnung verwendet werden and darauf basierend können Gewinnberechnungen erdacht werden, so dass eine Gewinnmaximierung mit dem langfristigen Ziel, eine globales oder ein sehr gutes lokales Optimum zu finden, übereinstimmt. Der hierarchische Aufbau von Agentenaktionen ermöglicht zudem die Verwendung von sogenannten ILS-Aktionen. Diese stimmen mit der Anwendung einer Iteration der bekannten iterierten lokalen Suche Metaheurstik (ILS) überein. Der Vorteil der ILS Metaheuristik und der Verwendung von ILS-Aktionen ist, dass nur Lösungen aus der relevanten Menge der lokalen Optima betrachtet werden müssen und führt somit eine Suchraumabstraktion ein. Ein lernender LSA, der ILS-Aktionen anwendet, wird dann, geführt durch seine Suchstrategie, adaptiv und iterativ lokale Optima besuchen. Die theoretische Methode, die eben skizziert wurde, wird dementsprechend geführte adaptive iterative lokale Suche genannt (GAILS, engl. Guided Adaptive Iterated Local Search). Um randomisierte GAILS-Algorithmen zu evaluieren, müssen empirische Experimente durchgeführt werden. Jeder GAILS-Algorithmus besteht aus drei größtenteils unabhängigen Teilen. Der erste Teil umfasst die Aktionen eines lerndenden LSA und sind spezifisch für einen Problemtyp. Die hierarchisch aufgebauten Aktionen werden schließlich durch elementare lokale Suchoperatoren realisiert. Der zweite Teil repräsentiert die benutzte VL Technik. Diese benutzt die Aktionen so, dass alle Eigenheiten, die spezifisch für einen Problemtyp sind, transparent für sie sind und ist demgemäß unabhängig vom Problemtyp. Der dritte Teil besteht aus Funktionsapproximatoren, die von den VL Techniken verwendet werden. Die Funktionsapproximatoren benötigen als Eingabe einen reellwertigen Vektor von einzelnen Features und sind damit auch unabhängig von den ersten beiden Teilen. Empirische Experimente können nun praktisch unterstützt werden, indem man ein Applikationsrahmenwerk entwickelt, welches die Trennung der drei Teile bei der Implementierung von GAILS-Algorithmen unterstützt, indem konkrete einzelne Teile beliebig wiederverwendet und kombiniert werden können. Insgesamt ermöglicht dies einen schnellen Prototypenbau. Das GAILS-Rahmenwerk ist solch ein Applikationsrahmenwerk, das die Trennung von GAILS-Algorithmen in drei unabhängige Teile berücksichtigt und das entwickelt wurde, um schnell GAILS-Algorithmen zu Experimentierzwecken zu implementieren. Es bietet generische Schnittstellen zwischen Komponenten aus den drei Teilen und somit auch eine Trennung zwischen Zuständen, die spezifischen für einen Problemtyp sind, und der Suchkontrolle. Außerdem ermöglicht das GAILS-Rahmenwerk die Trennung der Suchkontrolle von dem akutellen Zustand der Suchkontrolleinheit. Hierarchisch aufgebaute Aktionen werden auf Objekthierarchien abgebildet. Zwei konkrete GAILS-Algorithmen gemäß zweier Q-Lernen Algorithmen, Q(0) and Q(λ), die ILS-Aktionen verwenden, wurden entwickelt, implementiert und mit vergleichbaren ILS Metaheuristiken verglichen. Diese sogenannten Q-ILS Algorithmen wurden auf zwei verschiedenen Problemtypen und mit zwei verschiedenen Funktionsapproximatoren getestet. Die Resultate zeigen, dass das Lernen sinnvoller Suchstrategien möglich ist und dass das Gelernte auch über mehrere Probleminstanzen hinweg transferiert und eingesetzt werden kann. | Deutsch |
|
| Freie Schlagworte: |
Verstärkungslernen, Adaptiv, Lokale Suche, Iterierte Lokale Suche, Lokaler Suchagent, Geführte Adaptive Iteratierte Lokale Suche, GAILS, Aktionshierarchie |
| Schlagworte: |
| Einzelne Schlagworte | Sprache |
|---|
| Reinforcement Learning, Machine Learning, Feature, Adaptive, Metaheuristic, Local Search, Iterated Local Search, Combinatorial Optimization, Object-Oriented Framework, Local Search Agent, Guided Adaptive Iterated Local Search, GAILS, Action Hierarchy, Heuristic | Englisch |
|
| Sachgruppe der Dewey Dezimalklassifikatin (DDC): |
000 Allgemeines, Informatik, Informationswissenschaft > 004 Informatik |
| Fachbereich(e)/-gebiet(e): |
20 Fachbereich Informatik |
| Hinterlegungsdatum: |
17 Okt 2008 09:22 |
| Letzte Änderung: |
26 Aug 2018 21:25 |
| PPN: |
|
| Referenten: |
Bibel, Prof. Dr. Wolfgang ; Fürnkranz, Prof. Dr. Johannes |
|
Datum der mündlichen Prüfung / Verteidigung / mdl. Prüfung: |
30 Mai 2005 |
| Schlagworte: |
| Einzelne Schlagworte | Sprache |
|---|
| Reinforcement Learning, Machine Learning, Feature, Adaptive, Metaheuristic, Local Search, Iterated Local Search, Combinatorial Optimization, Object-Oriented Framework, Local Search Agent, Guided Adaptive Iterated Local Search, GAILS, Action Hierarchy, Heuristic | Englisch |
|
| Export: |
|
| Suche nach Titel in: |
TUfind oder in Google |
 |
Redaktionelle Details anzeigen |
Drucken
Impressum