Memetic algorithms for tree decomposition

Abstract

Baumzerlegungen kleiner Breite stellen ein mächtiges Werkzeug dar, um der Komplexität schwieriger Probleme entgegenzutreten. Instanzen des Bedingungserfüllungsproblems können beispielsweise in polynomieller Zeit gelöst werden, wenn der zugrundeliegende Graph eine geringe Baumweite aufweist. Es gibt bereits mehrere exakte Algorithmen und Heuristiken, die gute obere Schranken für die natürliche Baumweite eines Graphen finden können. Da der Abstand zwischen unterer und oberer Schranke für viele Instanzen aber noch sehr groß ist, sind solche Algorithmen nachwievor Gegenstand aktueller Forschung. Diese Arbeit untersucht die Brauchbarkeit memetischer Algorithmen in Bezug auf dieses Problem. Diese Arbeit präsentiert drei neue memetische Algorithmen für das Finden von Baumzerlegungen möglichst kleiner Breite. Die erste Variante verwendet eine zufällig gewählte Ringstruktur, um eine Population von Lösungen zu organisieren. Die Auswahl und Kombination der Individuen hängt von ihrer Umgebung in der Ringstruktur ab. Der zweite Algorithmus ist ein Hybrid zwischen einem genetischen Algorithmus, der mit einer Plus Strategie und Elitarismus arbeitet, und einer Heuristik, die auf lokaler Suche basiert, und in jeder Generation für das Verbessern der besten Lösungen verwendet wird. Die letzte Variante verwendet einen bestehenden genetischen Algorithmus, erweitert um lokale Suche, mit der in jeder Generation ein zufällig gewählter Teil der Population verbessert wird. Alle drei Varianten wurden mit aktueller Parameter Tuning Software auf die Instanzen der Second DIMACS Implementation Challenge optimiert. Um den Einfluss der Parameter besser verstehen zu können, wurden die Korrelationen zwischen Parametereinstellungen und der Qualität der Ergebnisse untersucht und visualisiert. Um die Leistung der Algorithmen abseits der Benchmark Instanzen bewerten zu können, wurden sie in einem umfassenden Experiment mit einem separaten Satz Instanzen getestet und verglichen. Die Ergebnisse wurden mit statistischen Tests auf ihre Signifikanz hin überprüft. Auch wenn unsere memetischen Algorithmen die aktuell besten Heuristiken nicht dominieren, erweisen sie sich für die meisten Instanzen durchaus als kompetitiv. Weiters konnten die bis dato besten oberen Schranken für 8 DIMACS Instanzen von den memetischen Algorithmen verbessert werden.

A tree decomposition of small width represents a valuable tool for tackling hard problems. For example, instances of constraint satisfaction problems can be solved in polynomial time if their underlying graph can be transformed into a tree decomposition of small width. There exist several exact algorithms and heuristics for finding tree decompositions of small widths for a given graph. However, developing new methods for finding good upper bounds for tree decompositions is still an important research issue. This thesis investigates the application of memetic algorithms, which have, to the best of our knowledge, not yet been applied to tree decompositions. We propose and implement three new memetic algorithms for finding tree decompositions of small width. The first algorithm organizes its population of solutions in a randomly initialized ring structure, which is used to employ selection and recombination among the individual solutions according to their vicinity. Each generation is collectively improved using iterated local search. The second algorithm is a hybrid between a genetic algorithm that uses elitism for selection, and iterated local search, which is used to improve the best individuals of every generation. Finally, the third algorithm implements an existing genetic algorithm design and also incorporates iterated local search, which is applied to a random fraction of each generation. All three variants have been tuned using state-of-the-art parameter tuning software on instances of the Second DIMACS Implementation Challenge. In order to achieve a better understanding of the algorithms, the correlation between parameter settings and solution quality has been examined. We offer an extensive comparison, which relates the performance of our memetic algorithms to state-of-the-art solvers for tree decomposition. Featuring a set of instances different to those used for parameter tuning, the comparison aims at providing real-world validity. The results have been confirmed using statistical significance tests. We show that our memetic algorithms do not dominate the state-of-the-art algorithms for this problem, but they prove to be competitive on most instances. Furthermore, one of our algorithms has been able to improve 8 best known upper bounds for the benchmark instances of the Second DIMACS Implementation Challenge.