TUD Technische Universität Darmstadt
Universitäts- und Landesbibliothek
ULB Darmstadt

EPDA - Elektronische Publikationen Darmstadt


Autor: Chiarandini, Marco
Titel:Stochastic Local Search Methods for Highly Constrained Combinatorial Optimisation Problems
Dissertation:TU Darmstadt, Fachbereich Informatik, 2005

Die Dokumente in PDF 1.3 (mit Adobe Acrobat Reader 4.0 zu lesen):

ChiarandiniPhD.pdf (5352110 Byte)

Abstract auf Deutsch:


Das Graphenfärbeproblem besteht darin, die Knoten eines Graphen so zu färben, dass keine zwei durch eine Kante verbundenen Knoten die gleiche Farbe erhalten. Zusammen mit Verallgemeinerungen dieser Problemstellung taucht es als Kern vieler Probleme des täglichen Lebens wie der Frequenzzuweisung in Mobilfunknetzen oder bei der Erstellung eines Stundenplans für Vorlesungen an einer Universität auf. Ihre einfache Formulierung als Graphenfärbungsprobleme erlaubt eine systematische Untersuchung durch Reduktion auf den harten Kern dieser Probleme. All diese Probleme sind kombinatorische Optimierungsprobleme, die durch eine Reihe von Bedingungen an Lösungen und durch ein Optimierungskriterium charakterisiert werden.

Die Lösung komplexer Graphenfärbeprobleme kann in effizienter Weise durch Methoden der stochastisch lokalen Suche (SLS) erfolgen. Abstrakt gesehen bestehen viele SLS-Methoden aus mehreren Komponenten, nämlich einem Konstruktionsalgorithmus, einem iterativen Verbesserungsalgorithmus und einer Metakomponente, genannt Metaheuristik, die die beiden ersteren Komponenten steuert. Diese ersten beiden Komponenten sind stark problemabhängig und erfordern das Ausnutzen problemspezifischer Kenntnisse, während die Metaheuristik allgemeiner gehalten ist. Konkrete SLS-Algorithmen enstehen durch die Kombination verschiedener konkreter Komponenten, die wiederum jeweils weiter parametrisiert werden können. Die Konfiguration konkreter SLS-Algorithmen als Auswahl konkreter Komponenten und deren Parametrisierung ist eine komplexe Aufgabe, und muss auf empirischen Tests beruhen, da theoretische Erkenntnisse in diesem Kontext schwer zu erhalten sind.

Der Ausgangspunkt dieser Arbeit ist die Definition statistischer Verfahren für die Analyse von SLS-Algorithmen. Es wird gezeigt, dass die Annahmen bei der Anwendung parametrischer statistischer Tests oft verletzt sind, und dass deshalb oft zwei alternative Methoden, sogenannte Permutationstests und rangbasierte Tests, verwendet werden müssen. Im Rahmen dieser Dissertation werden Permutationstests weiterentwickelt und als weitere Möglichkeit zur Analyse von SLS-Algorithmen eingeführt. Darüberhinaus wird aus der parametrischen Statistik eine graphische Darstellung der Resultate durch simultane Konfidenzintervalle übernommen und hier für nichtparametrische Testverfahren adaptiert. Der Vorteil dieser graphischen Darstellung ist die Vereinigung von Informationen der beschreibenden mit denen der schließenden Statistik in einer einzigen Graphik.

Die entwickelten statistischen Methoden werden beispielhaft zur Analyse von SLS-Algorithmen für das Graphenfärbungsproblem und das Mengen-T-Färbungsproblem, einer wichtigen Verallgemeinerung des Graphenfärbungsproblems, angewendet. Verschiedene SLS-Algorithmen sind in der Literatur zur Lösung des Graphenfärbungsproblems vorgeschlagen worden, aber ein unvoreingenommener, systematischer Vergleich zwischen diesen wurde bisher nicht unternommen. Eine ähnliche Situation gilt für das Mengen-T-Färbungsproblem. In beiden Fällen werden im Rahmen dieser Dissertation sowohl die bekanntesten Algorithmen reimplementiert als auch neue Algorithmen entwickelt und anschließend mittels eines strikten experimentellen Designs verglichen.

In einem letzten Schritt wird untersucht, wie verschiedene allgemeine SLS-Methoden zur Lösung einer Universitätsvorlesungsplanung (engl. course timetabling) angewendet und kombiniert werden können. Das Design von Komponenten für abgeleitete Algorithmen beruht einerseits auf Einsichten, die für die beiden Färbungsprobleme gewonnen wurden, und andererseits auf Anforderungen eines Algorithmenwettbewerbs, in dessen Rahmen die Algorithmen entwickelt wurden. Aus diesem Grunde wird ein spezieller Focus auf die systematische Entwicklung eines Algorithmus gelegt. Die Entwicklung von Algorithmuskomponenten und die Kombination zu einem kontreten SLS-Algorithmus wird als ein ingenieurmäßiger Prozess dargestellt, der aus der Wechselwirkung von Algorithmusdesign und experimentellen Tests besteht. Dieses Verfahren wird als angemessen für die Anwendung von beliebigen SLS-Methoden auf komplexe Probleme aus der realen Welt erachtet und begründet.

Die Hauptergebnisse sind die folgenden:

  1. Beim Graphenfärbungsproblem bleibt die einfache Tabu-Suche mit einer Eineraustauschnachbarschaft ein sehr konkurrenzfähiger Ansatz; die Anwendung einer sehr großen Nachbarschaft ist nicht nutzbringend.

  2. Beim Mengen-T-Färbungsproblem gibt es zwei gute Algorithmen, die auf der Eineraustauschnachbarschaft beruhen und jeweils auf einzelnen Instanzklassen die besten Algorithmen sind: ein adaptiver, iterativer greedy-Algorithmus für Graphen und ein Tabu-Suchalgorithmus, der durch eine eingeschränkte, exakte Zuweisung von Farben an Knoten erweitert wurde. Diese zwei Algorithmen können auch kombiniert werden.

  3. Der Einsatz eines ingenieurmäßigen Prozesses zur Entwicklung von Algorithmen, der auf sequentiellem Tests beruhen, ist besonders geeignet für die erfolgreiche Anwendung von SLS-Methoden. Der Einsatz eines solchen Prozesses hat die Entwicklung eines Algorithmus für die Universitätsvorlesungsplanung erleichtert, der bei einem internationalen Wettbewerb unter 24 eingereichten Lösungen der beste war.




Abstract auf Englisch:

Graph colouring is a combinatorial optimisation problem consisting in colouring the vertices of a graph such that no vertices connected by an edge receive the same colour. The minimal number of colours for which such a colouring exists is an intrinsic property of the graph and is called chromatic number. Many real life situations, such as the frequency assignment in mobile networks or the scheduling of courses at a university, can be modelled in this way. Colouring planar graphs, such as maps can be easy, and four colours suffice, but real life systems are much more complex. When modelled by graph colouring, they entail general graphs of large size and include more sophisticated constraints than those representable by simple unweighted edges.

Stochastic Local Search (SLS) methods are approximate techniques for efficiently solving these complex combinatorial optimisation problems. They typically consist of construction algorithms, iterative improvement algorithms, and meta-components, better known as metaheuristics. The first two are strongly problem dependent and require the exploitation of problem-specific knowledge, while the last are more general concepts to guide the first two components. The instantiation of SLS algorithms arises from the combination of concrete algorithmic components. This task is complex due to the many possible combinations and the need of determining a certain number of parameters. Empirical tests become then necessary to take the correct decisions.

The starting point of this work is the definition of the statistical methods that are appropriate for the analysis of SLS algorithms. We argue that the assumptions for the application of parametric tests are often violated and opt for two alternative methods: permutation and rank-based tests. Our work contributes to the development of permutation tests and to their introduction in the analysis of SLS algorithms. In addition, we transfer a graphical representation of results through simultaneous confidence intervals from the parametric to the non-parametric cases. This representation has the advantage of conveying in one single graph both descriptive and inferential statistics.

The developed statistical methods serve for the analysis of SLS algorithms on the graph colouring problem and one of its many possible generalisations, the set T-colouring problem. Several SLS algorithms have been proposed in the literature for the graph colouring problem but no ``unbiased'' comparison has been attempted. A similar situation holds for the set T-colouring problem. In both cases, we design new algorithms, re-implement the most prominent methods, and finally compare them in a rigorous experimental analysis.

As the final step, we study SLS algorithms for solving a university course timetabling problem. The design of algorithm components stems from the knowledge gained on the graph colouring problems but the assemblage and configuration of these components is carried out with a systematic methodology. The focus in this context was on the selection of one single algorithm to submit to an algorithm competition. The methodology is presented as an engineering process characterised by the interaction of SLS components design and empirical tests. We deem that this methodological approach is appropriate for the application of SLS methods to complex real life problems.

The main results are the following:

  1. on the graph colouring problem, the simple Tabu Search with one-exchange neighbourhood remains a very competitive approach and the use of a very large scale neighbourhood is not profitable;

  2. on the set T-colouring problem, the best overall algorithm is an Adaptive Iterated Greedy also based on Tabu Search with one-exchange neighbourhood which, under certain circumstances, can be further improved by a restricted exact reassignment of colours;

  3. the use of an engineering methodology based on sequential testing is particularly suitable for the application of SLS methods, as it led us to devise the algorithm whose solutions for course timetabling ranked the best out of 24 feasible submissions at the International Timetabling Competition held in 2003.



Dokument aufgenommen :2005-08-19
URL:http://elib.tu-darmstadt.de/diss/000595