Besten, Matthijs Leendert den (2005)
Simple Metaheuristics for Scheduling.
Technische Universität Darmstadt
Dissertation, Erstveröffentlichung
Kurzbeschreibung (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.
| Typ des Eintrags: |
Dissertation
|
| Erschienen: |
2005 |
| Autor(en): |
Besten, Matthijs Leendert den |
| Art des Eintrags: |
Erstveröffentlichung |
| Titel: |
Simple Metaheuristics for Scheduling |
| Sprache: |
Englisch |
| Referenten: |
Bibel, Prof.Dr. Wolfgang ; Stützle, Dr. Thomas |
| Berater: |
Bibel, Prof.Dr. Wolfgang ; Stützle, Dr. Thomas |
| Publikationsjahr: |
13 Januar 2005 |
| Ort: |
Darmstadt |
| Verlag: |
Technische Universität |
|
Datum der mündlichen Prüfung: |
6 Oktober 2004 |
| URL / URN: |
urn:nbn:de:tuda-tuprints-5164 |
| Kurzbeschreibung (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. |
|
Alternatives oder übersetztes Abstract: |
|
Alternatives Abstract | Sprache |
|---|
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. | Deutsch |
|
| Freie Schlagworte: |
Stochastische lokale Suche, Metaheuristiken, experimentelle Analyse, Algorithmenkonfiguration |
| Schlagworte: |
| Einzelne Schlagworte | Sprache |
|---|
| stochastic local search, metaheuristics, experimental analysis, algorithm configuration, model selection | Englisch |
|
| Sachgruppe der Dewey Dezimalklassifikatin (DDC): |
000 Allgemeines, Informatik, Informationswissenschaft > 004 Informatik |
| Fachbereich(e)/-gebiet(e): |
20 Fachbereich Informatik |
| Hinterlegungsdatum: |
17 Okt 2008 09:21 |
| Letzte Änderung: |
26 Aug 2018 21:25 |
| PPN: |
|
| Referenten: |
Bibel, Prof.Dr. Wolfgang ; Stützle, Dr. Thomas |
|
Datum der mündlichen Prüfung / Verteidigung / mdl. Prüfung: |
6 Oktober 2004 |
| Schlagworte: |
| Einzelne Schlagworte | Sprache |
|---|
| stochastic local search, metaheuristics, experimental analysis, algorithm configuration, model selection | Englisch |
|
| Export: |
|
| Suche nach Titel in: |
TUfind oder in Google |
 |
Frage zum Eintrag |
Optionen (nur für Redakteure)
 |
Redaktionelle Details anzeigen |
Drucken
Impressum