Sprachen

Pareto-Visualisierung - WS 2006/2007, SS 2007

Thema: 
Intuitive Visualisierung und interaktive Auswertung von Paretomengen
Zeitraum: 
WS 2006/2007, SS 2007
Umfang: 
8 SWS pro Semester
Veranstalter: 

Prof. Dr. Heinrich Müller, Informatik VII (Graphische Systeme),
OH16, R.124, Tel.:6324, E-Mail: mueller@ls7.cz.uni-dortmund.de
Dipl.-Inform. Petra Kersting, ISF,
Baroper Str. 301,, R.226, Tel.: 2113, E-Mail: petra.kersting@isf.de
Priv.-Doz. Dr.-Ing. Dipl.-Inform. Jörn Mehnen, ISF,
Baroper Str. 301, Raum 225,, Tel.: 5820, E-Mail: mehnen@isf.de
Dipl.-Inform. Thomas Michelitsch, ISF,
Baroper Str. 301, Raum 226, Tel.: 2113, E-Mail: michelitsch@isf.de

Materialien: 

Kurzvortrag [PDF]
Vortrag
Beschreibung
PG-500 Animation (MPEG, 9MB)
Zum Darstellen der PDF-Dateien ist ein geeigneter PDF-Reader erforderlich. Die MPEG-Datei benötigt einen entsprechenden Player.

Thematik: 

a) Motivation: Bei zahlreichen Optimieraufgaben liegen mehrere und zum Teil widersprüchliche Zielsetzungen vor, beispielsweise das Verringern der Kosten und das Verbessern der Qualität eines Produktionsprozesses. Dabei ist es in der Regel nicht möglich, allen Zielkriterien gleichermaßen gerecht zu werden. Im Gegensatz zu den Optimieraufgaben mit lediglich einem Zielkriterium lässt sich demnach bei der mehrkriteriellen Optimierung in der Regel keine einzelne beste Lösung finden [Coe02, Zit99, Me05a]. Als Ergebnis erhält man vielmehr eine Menge von Lösungen, bei der eine Verbesserung eines Zielfunktionswertes lediglich durch Verschlechtern mindestens eines anderen erreicht werden kann. Es ergibt sich also eine Menge optimaler Kompromisse, welche als Paretofront bezeichnet wird [Deb99, Ehr02, Mie99]. In der Praxis sind Mengen von mehreren hundert oder tausend Lösungen keine Seltenheit (Abbildung 1a).

(a) (b)
(c) (d) (e)

Abbildung 1: (a) Zielfunktionswerte zweier Lösungsmengen (jeder Punkt repräsentiert eine Lösung). Links: Zwei Zielkriterien (Qualität und Kosten). Auf dem schwarzen Streckenzug liegt die Teilmenge der besten Kompromisslösungen (Paretofront). Rechts: Bereits bei drei Zielkriterien ist das Erfassen der Lösungsmenge deutlich schwieriger. (b) Virtual-Reality Labor des ISF. Mit Hilfe einer Polarisationsfilterbrille erhält der Betrachter einen räumlichen Eindruck einer stereoskopisch dargestellten Szene. (c)-(e) Mikromat 6X Hexa Fräsmaschine. Bilder bitte mit Rot-Grün-Filterbrille betrachten (rot: links). Der 3D-Effekt ist zum Teil besser, wenn man einige Meter vom Monitor entfernt steht! Im Einführungsvortrag (1. Juni, 14.00, GB IV, R 219) werden wir 3D-Bilder auch in Echtfarben (mit Polarisationsfilterbrille) zeigen. Zum Vergrössern der Bilder bitte anklicken.

Letztendlich muss aus der Menge von Lösungen die zu realisierende vom Nutzer ausgewählt werden. Aufgrund der hohen Anzahl der Lösungen und ihrer Komplexitat sollen Verfahren zur intuitiven Visualisierung und interaktiven Auswertung von Lösungsmengen entworfen und als Software umgesetzt werden, die dem Nutzer bei dieser Entscheidungsfindung unterstützen. Hierbei besteht die Herausforderung darin, auch hochdimensionale Zielfunktionsräume und anwendungsfallspezifische Charakteristika geeignet darzustellen [Agr05]. Der Einsatz einer stereoskopischen Darstellung (Abbildung 1b) soll dem Anwender auch hochdimensionale Daten leichter zugänglich machen.
Entsprechend wichtig ist die Unterstützung des Nutzers bei der Entscheidungsfindung. Deshalb sollen – zusätzlich zu den Daten aus den Parameter- und Zielfunktionsraumen – die bei der Optimierung nicht direkt berücksichtigten Simulationsergebnisse (Abbildung 2b) sowohl direkt als auch problemspezifisch aufbereitet visualisiert werden. Zur Validierung der Software soll diese auf konkrete Praxisbeispiele angewandt werden. Entsprechend optimierte Lösungsmengen inklusive aller relevanter Simulationsdaten werden den Teilnehmern der PG zur Verfügung gestellt.

(a) (b)

Abbildung 2:  (a) Anwendungsbeispiel. Gießwerkzeug mit eingebrachtem Bohrungssystem. Die Struktur des Kühlsystems spiegelt sich in den Oberflächentemperaturen der Form wider (dargestellt in Fehlfarben). (b) Eine Lösung wird eindeutig durch ihre Parameterwerte definiert. Mit Hilfe von Simulatoren lassen sich entsprechende (meist zahlreiche) Simulationswerte ermitteln. Aus diesen werden dann die (deutlich wenigeren) Zielfunktionswerte abgeleitet. Nur letztere fließen in die Optimierung ein. Für die Analyse und den Vergleich der Lösungen jedoch können alle Werte herangezogen werden.

 

b) Aufgabenbeschreibung: Die Aufgabe der PG besteht aus den folgenden Punkten:

  • Visualisierung (AP 1): Paretofronten mit zwei-, drei und mehrdimensionalen Zielfunktionsräumen sollen geeignet dargestellt werden. Hierzu soll jeweils ein in der Literatur beschriebenes Verfahren ausgewählt, angepasst und implementiert werden. Die Möglichkeiten einer stereoskopischen Darstellungen sollen dabei ausgenutzt werden. Dazu steht den PG-Teilnehmern das Virtual-Reality-Labor des Instituts zur Verfügung (Abbildung 1b).
  • Auswahl und Analyse einzelner Lösungen (AP 2): Dem Nutzer der Software soll die Möglichkeit gegeben werden, einzelne Lösungen interaktiv auszuwählen, um detaillierte Informationen zu dieser zu erhalten. Neben der beliebige Anwendungsfälle einsetzbaren Darstellung der Lösung im Zielfunktionsraum ist eine problemspezifische Visualisierung der Lösung vorgesehen. Hierzu soll eine offene Schnittstelle spezifiziert und realisiert werden, an die sich problemspezifische Visualisierungsmodule anbinden lassen. Diese soll für ausgewählte Anwendungsfälle implementiert werden.
  • Auswahl und Analyse von Lösungsmengen (AP 3): Für die Strukturierung des Lösungsraums soll der Nutzer die Möglichkeit erhalten, Lösungsteilmengen komfortabel auszuwählen und einer Analyse zu unterziehen. Das Identifizieren einer repräsentativen Lösung für eine Lösungsteilmenge oder das Aufzeigen der durch die Lösungen der Teilmenge abgedeckten Wertebereiche können beispielsweise für die Analyse eingesetzt werden.
  • Vergleich von Lösungen beziehungsweise Lösungsmengen (AP 4): Zur Entscheidungsfindung soll eine Gegenüberstellung von Lösungen beziehungsweise Lösungsmengen an geboten werden. Eine intuitive Darstellung der Gemeinsamkeiten und Unterschiede der Lösungen soll sowohl allgemein auf Grundlage des Parameter- beziehungsweise Zielfunktionsraums als auch problemspezifisch unter Ausnutzung der Simulationswerte ermöglicht werden.
  • Automatisches Strukturieren der Lösungsmenge (AP 5): Zur automatischen Partitionierung der Lösungsmenge soll ein geeignetes Clusterverfahren [Jai99, Xu05] ausgewählt und eingesetzt werden.

 

c) Anwendungsfälle: Folgende Anwendungsfälle sind denkbar:

  • Optimieren von Temperierbohrungssystemen: Gießverfahren zählen zu den wichtigsten Verfahren der industriellen Massenfertigung [Men99]: Geschmolzenes Material wird in eine Form eingebracht. Dort kühlt es ab und wird als fertiges Produkt der Form entnommen, sobald es erstarrt ist. In das Werkzeug kann ein System vernetzter Bohrungen eingebracht werden, durch das eine Kühlflüssigkeit geleitet wird. Sind die Bohrungen geeignet positioniert, lässt sich so die Fertigung deutlich beschleunigen. Ein Kreislaufsystem von Bohrungen kann eindeutig durch die Lage entsprechender Stützpunkte im R3 beschrieben werden (Abbildung 2a). Aufgrund der Komplexität des Problems werden moderne mehrkriterielle Optimierverfahren eingesetzt. Wichtige Optimierziele sind dabei das effektive Kühlen des Werkzeugs, das Reduzieren mechanischer Spannungen und das Verringern der Fertigungskosten des Bohrungssystems [Me05a].

Abbildung 3: testAbbildung 3: Fräser bei der Bearbeitung eines Schmiedegesenks. Die Anstellwinkel des Fräsers werden optimiert. Die Parameter einer Lösung stellt eine Liste von Winkelpaaren (für jede Position des Fräsers) dar.

  • Fräsprozessoptimierung: Fräsen ist ein Bearbeitungsverfahren, bei welchem ein Werkzeug Material von einem Werkstück in Form von Spänen abträgt [Wei00]. Ein wichtiges Einsatzgebiete stellt die Herstellung von Werkzeugformen für die industrielle Fertigung dar. Während des Fertigungsprozesses wird der Fräser entlang einer vorgegebenen Fräsbahn bewegt. Moderne Maschinen erlauben es zusätzlich, den Fräser im Raum zu rotieren (vergleiche Winkel α und γ. in Abbildung 3). Da sich die Wahl geeigneter Winkel in der Praxis als schwierig erweist, werden in dem vorliegenden Anwendungsfall mehrkriterielle Optimierverfahren zum Bestimmen dieser Anstellwinkel eingesetzt [Zab05]. Als Optimierziele werden unter anderem die Reduktion der Fertigungszeit, das Verbessern der Oberflächenqualität und das Verringern von Verschleißerscheinungen eingesetzt. Wie beim Optimieren von Temperierbohrungssystemen werden auch bei der Fräsprozessoptimierung mehrkriterielle evolutionäre Optimierverfahren eingesetzt.
Minimalziele: 
Minimalziele sind sowohl die Visualisierung von Paretomengen in hochdimensionalen Zielfunktionsräumen, die Möglichkeit zur interaktiven Auswahl und Analyse einzelner Lösungen und Lösungsteilmengen als auch deren Vergleich. Die Funktionalität ist anhand ausgesuchter Anwendungsfälle zu demonstrieren. Sowohl die Ergebnisse als auch die Implementierung sind zu dokumentieren.
Teilnahmevorraussetzungen: 
  • Vorlesung Mensch-Maschine-Interaktion (bzw. Graphische Systeme). [V]
  • Datenvisualisierung, Digitale Bildverarbeitung oder Digitale Bilderzeugung. [W]
  • Kenntnisse einer objektorientierten Programmiersprache (zum Beispiel C++ oder Java) [V]
  • Clusteranalyse. [W]
  • Softwaretechnologie [W]

Legende: [V] vorausgesetzt, [W] wünschenswert

Literatur: 

[Agr05] G. Agrawal, C. L. Bloebaum und K. Lewis. Intuitive Design Selection Using Visualized n-Dimensional Pareto Frontier. 1st AIAA Multidisciplinary Design Optimization Specialist Conference, 2005.
[Bal00] H. Balzert. Lehrbuch der Software-Technik. Spektrum Akademischer Verlag, 2000.
[Coe02] C. A. Coello Coello, D. A. Van Veldhuizen und G. B. Lamont. Evolutionary Algorithms for Solving Multi-Objective Problems. Kluwer Academic Publishers, ISBN 0-3064-6762-3, 2002.
[Deb99] K. Deb. Multi-Objective genetic algorithms: Problem difficulties and construction of test problems. Evolutionary Computation, Vol. 7, Nr. 4, S. 205-230, 1999.
[Ehr02] M. Ehrgott und X. Gandibleux. Multicriteria Optimization. State of the Art Annotated Bibliography, Kluwer’s International Series, Kluwer Academic Publishers, Boston, 2002.
[Jai99] A. K. Jain, M. N. Murty und P. J. Flynn. Data Clustering: A Review. ACM Computing Surveys, Vol. 31, Nr. 3, 1999.
[Me05a] J. Mehnen, Th. Michelitsch und M. Stautner. Multiobjective Optimization of Mold Temperature Control Designs and Milling Strategies. Proceedings of the First Invited COST 526 (APOMAT), 2005.
[Me05b] J. Mehnen, Mehrkriterielle Optimierverfahren für produktionstechnische Prozesse, Habilitationsschrift, 2005.
[Mie99] K. Miettinen. Nonlinear Multiobjective Optimization. Kluwer Academic Publishers, Boston, 1999.
[Wei00] K. Weinert. Skriptum zur Vorlesung "Fertigungslehre I". Vorlesungsskript Universität Dortmund, 2000.
[Xu05] R. Xu. Survey of Clustering Algorithms. IEEE Transactions on Neural Networks, Vol. 16, Nr. 3, 2005.
[Zab05] A. Zabel und M. Stautner. Optimizing the Multi-Axis Milling Process via Evolutionary Algorithms. Proceedings of the 8th CIRP International Workshop on Modeling of Machining Operations, 2005, S. 363-370.
[Zit99] E. Zitzler. Evolutionary Algorithms for Multiobjective Optimization: Methods and Applications. Berichte aus der Informatik, Shaker Verlag, Aachen - Maastricht, 1999.

Rechtliche Hinweise: 
Die Ergebnisse der Projektarbeit inklusive der dabei erstellten Software sollen der Fakultät für Informatik uneingeschränkt zur freien Forschung zur Verfügung stehen. Darüber hinaus sind keine Einschränkungen der Verwertungsrechte an den Ergebnissen der Projektgruppe und keine Vertraulichkeitsvereinbarungen vorgesehen.