Item Type: |
Ph.D. Thesis |
Type of entry: |
Primary publication |
Title: |
Simple Metaheuristics for Scheduling |
Language: |
English |
Referees: |
Bibel, Prof.Dr. Wolfgang ; Stützle, Dr. Thomas |
Advisors: |
Bibel, Prof.Dr. Wolfgang ; Stützle, Dr. Thomas |
Date: |
13 January 2005 |
Place of Publication: |
Darmstadt |
Date of oral examination: |
6 October 2004 |
Abstract: |
This dissertation is concerned with configuring stochastic local search for combinatorial optimization problems by means of new automatic experimental procedures. The configuration and selection of stochastic local search is determined by an univocally specified computer-based evaluation of various variants of stochastic local search by means of racing. Depending on the amount of effort that is needed to generate a solution, the quality of the solution and the run time that is required to obtain the solution are taken into account in a specific way: If the effort required to generate the solutions is more or less equal for all candidates, then the solution quality is the main criterion for selection among the candidates; if there are big differences, then the run time is explicitly taken account of as well; and in cases where the search algorithms can generate a series of solutions with increasing quality, the quality of every new solution is taken into account together with the associated run time in order to select among the candidates. The application of these selection procedures is illustrated in this dissertation with the application of construction heuristics, the application of iterative improvement and the application of iterated local search to twelve distinct scheduling problems. Each time, the final result is a search algorithm whose performance is on a par with the state-of-the-art for the problem domain. In addition, new insights could be obtained on the influence of search algorithm components on algorithm performance in relation to the structure of the optimization problems that were investigated. |
Alternative Abstract: |
Alternative Abstract | Language |
---|
Diese Dissertation behandelt die Konfiguration stochastisch lokaler Suchverfahren für kombinatorische Optimierungsprobleme mittels neuer, automatischer experimentellen Prozeduren. Die Konfiguration and Selektion des Suchverfahrens wird aufgrund einer genau spezifizierten, vom Rechner durchgeführten Evaluation der Performanz von verschiedenen Varianten des Suchverfahrens mittels Racingverfahren bestimmt. In Abhängigkeit des Aufwands der Erzeugung von Lösungen, werden die Lösungsgüte und der Berechnungsaufwand, d.h. die Rechenzeit zur Erzeugung der Lösungen, unterschiedlich berücksichtigt. Können Lösungen mit ungefähr gleichem Aufwand generiert werden, ist die Güte der Lösungen das Hauptkriterium für die Auswahl. Gibt es erhebliche Unterschiede im Aufwand der Erzeugung von Lösungen, wird die Rechenzeit explizit in der Auswahl berücksichtigt. Falls die Suchverfahren eine Serie von Lösungen steigender Güte generieren können, wird die Güte jeder neuen solchen Lösung zusammen mit der entsprechenden Rechenzeit im Auswahlverfahren berücksichtigt. Die Anwendung dieser Auswahlverfahren wird in dieser Dissertation anhand von Konstruktionsheuristiken, Varianten von iterierten Verbesserungsverfahren und der iterierten lokalen Suche für deren jeweilige Anwendung auf zwölf unterschiedliche Schedulingprobleme dargestellt. Das Endergebnis ist jeweils ein Suchverfahren, dessen Performanz oft dem ``State-of-the-Art'' im Problembereich entspricht. Zusätzlich konnten durch eine eingehende, statistische Analyse der Versuchsdaten neue Einsichten in den Einfluss der Komponenten von Suchverfahren auf die Performanz in Abhängigkeit der Struktur der untersuchten Optimierungsprobleme gewonnen werden. | German |
|
Uncontrolled Keywords: |
Stochastische lokale Suche, Metaheuristiken, experimentelle Analyse, Algorithmenkonfiguration |
Alternative keywords: |
Alternative keywords | Language |
---|
Stochastische lokale Suche, Metaheuristiken, experimentelle Analyse, Algorithmenkonfiguration | German | stochastic local search, metaheuristics, experimental analysis, algorithm configuration, model selection | English |
|
URN: |
urn:nbn:de:tuda-tuprints-5164 |
Classification DDC: |
000 Generalities, computers, information > 004 Computer science |
Divisions: |
20 Department of Computer Science |
Date Deposited: |
17 Oct 2008 09:21 |
Last Modified: |
07 Dec 2012 11:50 |
URI: |
https://tuprints.ulb.tu-darmstadt.de/id/eprint/516 |
PPN: |
|
Export: |
|