Forschungsprojekte
Im Folgenden finden Sie Informationen zu Forschungsprojekten am Institut, die über das Forschungsinformationssystem der TU Dresden bereitgestellt werden. Für nähere Informationen zu Forschungstätigkeiten im Rahmen von Projekten besuchen Sie bitte die Seiten der jeweiligen Professuren.
Methoden zur Analyse und Erweiterung bestehender multikriterieller Optimierungsalgorithmen
Titel (Englisch)
GUIDES - Generalized Support and Investigation Design for Nested Systems
Kurzbeschreibung (Deutsch)
Motivation:
Aktuelle Datensätze sind im allgemeinen groß, hochdimensional und heterogen (-> Big Data). Methoden des Unsupervised Machine Learning (z.B. Cluster Analysis) oder der Optimierung (z.B. Local Searches) müssen also entweder aufwendig angepasst werden oder die Daten selbst, bzw. die Darstellungen müssen angepasst werden. Dazu zählen Ansätze wie Sampling, Single Scaning, Feature Selection / Reduction und Co-Clustering usw. oder gleich ganze Domänentransformationen, sog. Principal Component Analysis oder Multi-Dimensional Scaling (MDS). MDS-Verfahren sind vergleichsweise mächtige Werkzeuge, da sie viele der aktuellen Probleme mit großen Datensätzen abdecken, jedoch sind sie selbst komplex und skalieren i.A. schlecht. Unser Ziel war also die Entwicklung eines allg. MDS mit geringer (linearer) Zeitkomplexität und hoher Äquivalenzerhaltung.
Umsetzung:
Möglich wurde das durch einen iterativen / kräfte-basierten Ansatz mit allgemeinen Vergleichsoperatoren für die Features der Datenelemente. Das Verfahren ordnet die n Datenelemente initial zufällig in einem k-dimensionalen Zielraum R^k an (k = 2 oder 3) und verschiebt diese so lange, bis ein Gleichgewicht hergestellt ist. Die euklidischen Distanzen entsprechen dann den Ähnlichkeiten der Datenelemente im Ursprungsraum und die nachfolgende Clusteranalse kann direkt auf dieser Darstellung arbeiten.
Die geringe Zeitkomplexität wird durch Vor- bzw. Zwischenverarbeitungsschritte erreicht, die die Datenelemente in einen (zufälligen) Clusterbaum einbetten und diesen aktualisieren, sodass die Anzahl der nötigen Vergleiche von n^2 auf n*log(n)*c reduziert wird.
Tests / Anwendung:
Es wurden umfangreiche Tests an generischen Datenmodellen durchgeführt, um das Verhalten und die Ergebnisse des MDS mit unterschiedlichen Datengrößen und -komplexitäten zu testen. Die Transformationsqualität, also die Erhaltung der Datenähnlichkeiten ausgedrückt durch die Distanzen, war durchgängig hoch, die Laufzeitkomplexität war nahezu linear. Durch die einfache Darstellung der Daten in einem Raum R^k werden viele bekannte Datenanalyseverfahren mit wenig Adaption anwendbar. Es wurden weiterhin 2 "akademische" Anwendungsfälle betrachtet, wo das MDS und ausgewählte CA-Verfahren in einem allgemeinen Ansatz für Multi-Objective Optimization (MOO) eingesetzte wurden. Die Ergebnisse waren ebenfalls gut.
Ausblick:
Der Ansatz des MDS ist ausbaubar und gut parallelisierbar. Der allgemeine MOO-Ansatz (incl. dem MDS) zeigt Potential für große und aufwendige (z.B. kombinatorische) Optimierungsprobleme und soll im GUIDES-Projekt zum Einsatz kommen um Scheduling und Resource-Allocation Aufgaben zu bearbeiten.
Aktuelle Datensätze sind im allgemeinen groß, hochdimensional und heterogen (-> Big Data). Methoden des Unsupervised Machine Learning (z.B. Cluster Analysis) oder der Optimierung (z.B. Local Searches) müssen also entweder aufwendig angepasst werden oder die Daten selbst, bzw. die Darstellungen müssen angepasst werden. Dazu zählen Ansätze wie Sampling, Single Scaning, Feature Selection / Reduction und Co-Clustering usw. oder gleich ganze Domänentransformationen, sog. Principal Component Analysis oder Multi-Dimensional Scaling (MDS). MDS-Verfahren sind vergleichsweise mächtige Werkzeuge, da sie viele der aktuellen Probleme mit großen Datensätzen abdecken, jedoch sind sie selbst komplex und skalieren i.A. schlecht. Unser Ziel war also die Entwicklung eines allg. MDS mit geringer (linearer) Zeitkomplexität und hoher Äquivalenzerhaltung.
Umsetzung:
Möglich wurde das durch einen iterativen / kräfte-basierten Ansatz mit allgemeinen Vergleichsoperatoren für die Features der Datenelemente. Das Verfahren ordnet die n Datenelemente initial zufällig in einem k-dimensionalen Zielraum R^k an (k = 2 oder 3) und verschiebt diese so lange, bis ein Gleichgewicht hergestellt ist. Die euklidischen Distanzen entsprechen dann den Ähnlichkeiten der Datenelemente im Ursprungsraum und die nachfolgende Clusteranalse kann direkt auf dieser Darstellung arbeiten.
Die geringe Zeitkomplexität wird durch Vor- bzw. Zwischenverarbeitungsschritte erreicht, die die Datenelemente in einen (zufälligen) Clusterbaum einbetten und diesen aktualisieren, sodass die Anzahl der nötigen Vergleiche von n^2 auf n*log(n)*c reduziert wird.
Tests / Anwendung:
Es wurden umfangreiche Tests an generischen Datenmodellen durchgeführt, um das Verhalten und die Ergebnisse des MDS mit unterschiedlichen Datengrößen und -komplexitäten zu testen. Die Transformationsqualität, also die Erhaltung der Datenähnlichkeiten ausgedrückt durch die Distanzen, war durchgängig hoch, die Laufzeitkomplexität war nahezu linear. Durch die einfache Darstellung der Daten in einem Raum R^k werden viele bekannte Datenanalyseverfahren mit wenig Adaption anwendbar. Es wurden weiterhin 2 "akademische" Anwendungsfälle betrachtet, wo das MDS und ausgewählte CA-Verfahren in einem allgemeinen Ansatz für Multi-Objective Optimization (MOO) eingesetzte wurden. Die Ergebnisse waren ebenfalls gut.
Ausblick:
Der Ansatz des MDS ist ausbaubar und gut parallelisierbar. Der allgemeine MOO-Ansatz (incl. dem MDS) zeigt Potential für große und aufwendige (z.B. kombinatorische) Optimierungsprobleme und soll im GUIDES-Projekt zum Einsatz kommen um Scheduling und Resource-Allocation Aufgaben zu bearbeiten.
Zeitraum
01.09.2015 - 30.11.2017
Art der Finanzierung
Drittmittel
Projektleiter
- Herr Prof. Dr. rer. nat. habil. Uwe Aßmann
Projektmitarbeiter
- Herr Dr.-Ing. Karsten Wendt
- Herr Msc. Dmytro Pukhkaiev
Finanzierungseinrichtungen
- SAB
Kooperationspartnerschaft
regional
Externe Kooperationspartner
- Dualis IT Solution GmbH, KMU (Deutschland)
Website zum Projekt
Zugeordnete Profillinie
Informationstechnologien und Mikroelektronik
Relevant für den Umweltschutz
Nein
Relevant für Multimedia
Nein
Relevant für den Technologietransfer
Ja
Schlagwörter
Multiobjective Optimization; Scheduling; Resource Allocation; Mutlidimensional Scaling, Cluster Analysis; Modeltransformation
Berichtsjahr
2016