GUIDES – Generalized Support and Investigation Design for Nested Systems

Ein Projekt der DUALIS GmbH IT Solution und dem Lehrstuhl für Softwaretechnologie der TU Dresden (LS für SWT)

Verallgemeinert lässt sich die Feinplanung als multikriterielle Optimierungsaufgabe beschreiben, welche das Lösen einer kombinatorischen Aufgabe mit mehreren widerstrebenden Zielen unter Berücksichtigung vieler Nebenbedingungen beinhaltet. Diese Klasse von Problemen hat eine nichtlineare Komplexität, was besonders für sehr große Probleme zu sehr langen Laufzeiten führen kann.

Ausgangssituation

Intuitive und häufig genutzte Ansätze zur Lösung dieser Aufgaben, die dem Oberbegriff MOO zugeordnet werden, nutzen Heuristiken, um sich unter teilweise massivem Einsatz von IT iterativ dem Optimierungsergebnis anzunähern. Die über lange Zeit entwickelten, spezialisierten Methoden vereinen das Erzeugen valider Lösungen und das schrittweise Verbessern dieser, agieren deshalb jedoch innerhalb eines eng begrenzten Bereichs des möglichen Lösungsraums, ohne Informationen über das gesamte Ergebnispotential.

Zielstellung des Projektes

Es werden daher neue Wege zur allgemeinen Erfassung (Generalized) von MOO-Aufgaben gesucht, um diese in einem integrierenden Ansatz mit den bestehenden eingebetteten Heuristiken (Nested) zu vereinen. Innovative Algorithmen zur Modelltransformationen und der Clusteranalyse ermöglichen hierbei einen den gesamten Lösungsraum umfassenden Blick auf das Problem (Bird’s Eye) und unterstützen die spezialisierten bestehenden Algorithmen bei ihren Aufgaben, verbessern deren Ergebnisse und machen diese evaluierbar (Support und Investigation). Der Ansatz des GUIDES-Projekts setzt sich aus diesen Aspekten zusammen.

Umsetzung/Nutzen

Auf diese Weise wird eine hybrides Verfahren erstellt, welches in einem Vorverarbeitungsschritt große und inhomogene Datenmodelle effizient analysiert, d.h. durch moderne Verfahren der Knowledge Discovery in Databases (zu dt. Wissensentdeckung in Datenbanken) (KDD) zunächst transformiert und strukturiert, um jene Bereich des gesamten Lösungsraums einzugrenzen, in welchen die jeweiligen globalen Optima zu vermuten sind. Anschließend werden diese Informationen der spezialisierten Feinplanungs-Heuristik über dedizierte Schnittstellen zur Verfügung gestellt, sodass der Scheduling-Algorithmus um Funktionen zur frühzeitigen Erkennung von suboptimalen Teillösungen erweitert wird, was die Stagnation in lokalen Optima verhindert und globale Optimierungspotentiale abschätzbar macht. Geeignete Verfahren der KDD sind bereits im Vorfeld getestet worden, um eine ausreichend niedrige Zeitkomplexität sicherzustellen.