• Zielgruppen
  • Suche
 

Scientific Computing II (SS 2019)

Das Angebot des Instituts für Produktionswirtschaft für die Veranstaltung Scientific Computing II umfasst mehrere Problemstellungen aus dem Bereich des Operations Management. In einigen Themen wird zudem auf Methoden des Maschinellen Lernens zurückgegriffen. Eine ausführliche Vorstellung der angebotenen Themen wird im Rahmen der Einführungsveranstaltung am 8. April 2019 um 11-12:30 Uhr in Raum I-332 (Gebäude 1501) erfolgen. Um die Auswahl eines Fachbereichs für Scientific Computing II zu erleichtern, wird an dieser Stelle bereits ein Überblick über die geplanten Themen gegeben. Die Themenstellungen sind in zwei Blöcke gruppiert:

Themenblock I: Lösungsverfahren für die Planung von ressourcenbeschränkten Projekten

Eine optimale Lösung für das ressourcenbeschränkte Projektplanungsproblem (RCPSP) ist ein kürzester gegenüber der Reihenfolge- und Kapazitätsrestriktionen zulässiger Ablaufplan für ein gegebenes Projekt.

Thema 1: Implementierung eines Genetischen Algorithmus für die ressourcenbeschränkte Projektplanung

Durch die NP-schwere des RCPSP ist eine exakte Lösung von Probleminstanzen mit praxisnaher Größe häufig nicht in annehmbarer Zeit möglich. Daher wurden in der Literatur viele heuristische Lösungsmethoden für das RCPSP vorgestellt. Genetische Algorithmen (GA) sind hierbei besonders wettbewerbsfähig.

Im Rahmen der Hausarbeit soll ein GA für das RCPSP implementiert werden. Dies umfasst die Umsetzung aller Komponenten des GA. Dazu gehört die Erzeugung einer Startpopulation, Paarbildung, Kreuzung, Mutation, Fitnessberechnung und Selektion. Die Eignung des implementierten GA zur Lösung des RCPSP soll anhand der Problembibliothek PSPLIB evaluiert werden.

Dieses Thema wird in zwei Varianten angeboten: Erstens mit Verwendung einer Aktivitätenliste als Lösungsrepräsentation und der Planerzeugung durch das serielle Ablaufplanerzeugungsschema. Zweitens mit Prioritätswerten als Repräsentation und Nutzung des parallelen Planerzeugungsschema.

Thema 2: Implementierung eines Branch&Bound-Verfahrens für die ressourcenbeschränkte Projektplanung

Problemspezifische Branch&Bound-Verfahren (B&B) können genutzt werden, um eine optimale Lösung für eine gegebene Instanz des RCPSP zu ermitteln. Im B&B-Algorithmus wird im Wurzelknoten mit einem leeren Plan begonnen. Es wird über alle Alternativen diesen um einen weiteren Arbeitsgang zu ergänzen verzweigt. Ein Blatt repräsentiert einen Lösungskandidaten, dessen Dauer eine obere Schranke für die kürzeste Projektdauer liefert. Bei der Verzweigung werden Vervollständigungsalternativen ausgelotet, welche unmöglich zu einem kürzeren Plan als dem kürzesten bisher gefundenen Plan führen können. Dadurch können große Teile des Lösungsraums von der Betrachtung ausgeschlossen werden und in kürzerer Zeit eine bewiesen optimale Lösung identifiziert werden. Im Rahmen dieser Hausarbeit soll ein solcher B&B-Algorithmus für das RCPSP implementiert werden. Dies beinhaltet die Umsetzung der rekursiven Verzweigung und der Berechnung von unteren Schranken für Teilpläne. Die Eignung des implementierten B&B-Algorithmus zur Lösung des RCPSP soll anhand der Problembibliothek PSPLIB evaluiert werden.

Dieses Thema wird in drei Varianten angeboten, welche sich im Verzweigungsschema des B&B-Algorithmus unterscheiden (Reihenfolgebäume, Verzögerungs- und Erweiterungsalternativen).


Literatur für Themenblock I:

HARTMANN, Sönke. A competitive genetic algorithm for resource‐constrained project scheduling. Naval Research Logistics (NRL), 1998, 45. Jg., Nr. 7, S. 733-750.

BRUCKER, Peter; KNUST, Sigrid. Complex scheduling. Springer Science & Business Media, 2011.

Themenblock II: Algorithmenauswahl mithilfe von maschinellem Lernen

Das Container Pre-Marshalling Problem (CPMP) besteht in der Suche nach einer optimalen Sequenz von Umsortierungsschritten auf Container-Stapeln, sodass am Ende alle Container in einem Stapel in der geplanten Entnahmereihenfolge übereinander liegen.

Allgemein gibt es für ein kombinatorisches Optimierungsproblem wie das CPMP häufig mehrere in der Literatur vorgestellte Lösungsmethoden. Dabei dominiert selten eine Methode alle anderen Methoden auf allen bekannten Testinstanzen verschiedener Instanzenbibliotheken. Stattdessen gibt es für jedes Lösungsverfahren ein Cluster von Instanzen, für welches dieses Verfahren besser als die anderen Verfahren abschneidet. Das Algorithmenauswahlproblem besteht in der Wahl des „besten“ Lösungsalgorithmus aus einem Portfolio an Algorithmen für eine gegebene Probleminstanz.

In der Literatur wurden die Methoden des maschinellen Lernens (ML) bereits erfolgreich eingesetzt, um auf Basis von Erfahrungsdaten bei der Lösung von Problemen mit verschiedenen Algorithmen eine Vorhersage des besten Algorithmus für eine gegebene Instanz mit hoher Treffergenauigkeit zu treffen. Die Prognose der besten Lösungsmethode für eine Testinstanz ist eine Klassifikationsproblemstellung aus dem Bereich des überwachten Lernens.

Thema 3: Implementierung des kostensensitiven hierarchischen Clustering zur Algorithmenauswahl für das Container Pre-Marshalling Problem

Ensembles aus Entscheidungsbäumen, welche für Teilmengen der Stichproben und Features gebildet werden, konnten in der Vergangenheit erfolgreich für das überwachte Lernen eingesetzt werden. Für Datensätze zum Algorithmenauswahlproblem gibt es mit dem kostensensitiven hierarchischen Clustering (CSHC) eine maßgeschneiderte Variante dieser sogenannten Random Forests. Ein einzelner Entscheidungsbaum wird durch einen CART-Algorithmus aus einem Datensatz induziert, indem die Menge der Stichproben sukzessive anhand von Ausprägungen der Features in zwei disjunkte Teilmengen zerlegt wird. Im Idealfall sollten die Stichproben in den Blättern des Baums einheitlich einer Klasse angehören.

Das CSHC unterscheidet sich vom klassischen Random Forest nur dahingehend, dass bei der Induzierung eines Entscheidungsbaums aus einem Datensatz die Bewertung einer Zerlegung mit einem speziellen Unreinheitsmaß erfolgt, nämlich den Kosten für eine Fehlklassifikation. Im Laufe dieser Hausarbeit soll das CSHC implementiert werden. Daraufhin soll ein Teil des Datensatzes aus der ASLib für das CPMP für Training und Validierung genutzt werden.

Thema 4: Implementierung eines Ansatzes zur Algorithmenauswahl für das Container Pre-Marshalling Problem mittels Deep Learning

Sogenannte „Deep Neural Networks“ werden in der Bildverarbeitung erfolgreich eingesetzt, um bspw. Objekte und Muster in Bildern automatisiert erkennen zu können. Ein Neuronales Netz besteht aus einer Menge von Neuronen, welche eine gewichtete Summe ihrer Eingänge bilden und in eine Aktivierungsfunktion einsetzen. Der Wert der Funktion wird dann an die nächste Schicht weitergegeben. Bei hinreichender Größe des Netzes lässt sich über die Anpassung der Gewichte jede beliebige Funktion approximieren. Das Training besteht in einer Anpassung der Gewichte, welche die Vorhersagegenauigkeit des Netzes für einen Trainingsdatensatz maximiert.

Tatsächlich können DNN genutzt werden, um das Algorithmenauswahlproblem zu lösen. Dazu müssen Instanzen einer Problemstellung zunächst in Bilder umgewandelt werden. Die Architektur des DNN selbst kann zunächst auf Basis der Literatur gebildet werden. Teil der Arbeit wird eine Hyperparameteroptimierung sein. Hier geht es darum, einige der Stellschrauben des Netzes derart anzupassen, dass möglichst eine möglichst hohe Vorhersagegenauigkeit auf den Validierungsdaten erreicht wird.


Literatur für Themenblock II:

BISCHL, Bernd, et al. Aslib: A benchmark library for algorithm selection. Artificial Intelligence, 2016, 237. Jg., S. 41-58.

TIERNEY, Kevin; MALITSKY, Yuri. An algorithm selection benchmark of the container pre-marshalling problem. In: International Conference on Learning and Intelligent Optimization. Springer, Cham, 2015. S. 17-22.

LOREGGIA, Andrea, et al. Deep learning for algorithm portfolios. In: Thirtieth AAAI Conference on Artificial Intelligence. 2016.