Meta-Heuristiken für Graph Partitionierung

In vielen wichtigen Anwendungen der Informatik werden große Graphen verarbeitet, z.B. beim Lösen großer Gleichungssystem oder etwa in der Parallelverarbeitung. Bei einigen Anwendungen der Parallelverarbeitung modellieren die Knoten Last und Kanten Kommunikation. Um die Last nun gleichmäßig auf k Prozessoren zu verteilen benötigt man Graph Partitionierung. Das Ziel der Graphpartitionierung ist es dann, einen gegebenen Graph G in k möglichst gleichgroße Blöcke zu unterteilen, so dass wenig Kanten zwischen den Blöcken verlaufen. Im Falle der Parallelverarbeitung möchte man also die Kommunikation zwischen den k Prozessoren minimieren.

Thema der Bachelor- / Masterarbeit

Dieses Problem ist NP-vollständig, daher werden wir nicht von Ihnen fordern das Problem exakt zu lösen. In manchen Anwendung jedoch, z.B. VLSI Design, möchte man sehr gute Partitionen berechnen wobei die Laufzeit weniger relavant ist. Eine Möglichkeit gegebene Algorithmen in diesem Sinne zu verbessern besteht in der Verwendung von sogenannten genetischen Algorithmen. Die Grundidee gentischer Algorithmen ist es eine Menge bzw. Population von Individuen zu erzeugen und iterativ diejenigen auszuwählen, die einem bestimmten Gütekriterium am besten entsprechen (in unsem Fall der Kantenschnitt). Um eine neue Generation von Lösungskandidaten zu erzeugen werden die Parameter der Individuen leicht gestört (Mutation) oder miteinander kombiniert (Rekombination). Ziel der Arbeit ist es basierend auf KaFFPa einen genetischen Algorithmus zu entwerfen und zu implementieren. Da die genetischen Algorithmen sehr lange Ausführungszeiten haben, ist eine Parallelsierung des Verfahrens wünschenswert.

Vorraussetzungen

• Interesse und solide Kenntnisse über Algorithmen und Datenstrukturen
• Gute Programmierkentnisse in C++, MPI

Gebotenes

• Kennenlernen modernster Algorithmen der Graphpartitionierung
• Die Arbeit an einem sehr spannenden Thema

Das hier aufgeführte Thema ist nur ein Beispiel für eine offene Fragestellung. Es gibt (fast) immer weitere interessante Fragestellungen. Interessierte Studenten melden sich bitte bei Christian Schulz.