Innerhalb der industriellen Praxis begleitet der Wunsch zur
Optimierung fast jeden Herstellungsprozess, angefangen von der Planung
über die Fertigung bis hin zur Auslieferung von Produkten und deren
täglichen Verwendung. Die alleinige Verwendung klassischer
mathematischer Verfahren ist jedoch oftmals nicht geeignet, um
diese komplexen Problemstellungen zu lösen. Heuristische
Optimierungsverfahren - in den unterschiedlichsten Ausprägungen - stellen
hierbei eine oft benutzte Alternative dar. In diesem Projekt soll erstmals
eine möglichst plattformunabhängige Arbeitsumgebung geschaffen werden,
die in der Lage ist, mit unterschiedlichen heuristischen und
meta-heuristischen Verfahren praxisrelevante Problemstellungen zu bearbeiten.
Reale Optimierungsaufgaben weisen häufig neben der Existenz mehrerer
lokaler Optima zusätzliche Schwierigkeiten auf, welche beispielsweise durch die
Struktur der Variablenmenge (kontinuierliche/diskret) oder
verschiedener zusätzlicher Nebenbedingungen gegeben sind. Zur Lösung
dieser Probleme sind in den letzten Jahren moderne heuristische
Verfahren vorgeschlagen worden, welche unter dem Begriff der
Meta-Heuristiken zusammengefasst werden. Hierbei weisen die
zugrundeliegenden Strategien jedoch teilweise ,,geniale bis
abstruse`` [Sch02] Merkmale auf. Die Analyse und der Vergleich der
unterschiedlichen Verfahren ist ein notwendiger erster Schritt.
Meta-Heuristische Verfahren
Zu einem generellen Charakteristikum einer Meta-Heuristik kann die
Kombination unterschiedlicher Suchstrategien zu einer übergeordneten
Suchheuristik gezählt werden. Lokale Suchverfahren werden
beispielsweise mit globalen kombiniert, um mit Hilfe der
gewonnenen Informationen möglichst schnell ein gutes lokales Optimum
zu finden. Die Wahl der zu kombinierenden
Strategien stellt hierbei einen Balanceakt zwischen der Ausnutzung
der gefundenen Informationen und der Durchmusterung des
Suchraums dar. Ein erster Klassifikationsversuch, welcher die
bekanntesten meta-heuristischer Verfahren umfasst, ist in [BR01] zu
finden. Abhängig von der zugrundeliegenden Sichtweise
unterteilen sie die Verfahren entweder in:
Naturinspirierte vs. nicht naturinspirierte Verfahren oder
Populationsbasierte vs. Einpunkt-Suche oder
Dynamische vs. statische Zielfunktionsbehandlung oder
Ein vs. verschiedene Nachbarschaftsstrukturen oder
Speicherbasierte Methoden vs. speicherlose Methoden.
Einige der Methoden setzen auf den klassischen lokalen Suchverfahren
auf und versuchen, darauf aufbauend lokale Minima zu verlassen um
evtl. bessere Lösungen zu finden. Tabu Search [GL97],
Iterated Local Search [LMS99], Variable Neighborhood
Search [HM99], GRASP [FR95] und Simulated
Annealing [KGS83] sind die bekanntesten Vertreter dieser Gruppe.
Neben diesen Methoden werden Verfahren, die auf natürlichen oder
biologischen Vorbildern beruhen, in der Praxis
erfolgreich eingesetzt.
Evolutionäre Algorithmen basieren auf dem
Grundgedanken des evolutiven Vorbildes. Eine Menge möglicher Lösungen,
die sog. Elternpopulation, wird variiert, wodurch eine neue
Menge von Lösungen, die sog. Nachkommenpopulation, generiert wird. Aus
der Eltern- und der Nachkommenpopulation werden die besten Lösungen
ausgewählt. Diese bilden eine neue Elternpopulation,
mit der das Verfahren solange wiederholt wird, bis hinreichend gute
Lösungen gefunden worden sind.
Weitere naturinspirierte Ansätze sind
u.a.: Partikel-Schwärme (PSO), deren Ursprung auf die Modellierung des
Sozialverhaltens von Vogelschwärmen zurückgeht, Ameisenkolonien, memetische
Algorithmen [CHH$^+$02] oder coevolutive Ansätze.
Industrielle Anwendungen
Im Folgenden werden drei Beispiele aus der industriellen Praxis
vorgestellt, in denen heuristische Optimierungsverfahren eingesetzt
werden können. Diese Beispiele werden der Projektgruppe als Black Box
mit genau definierten Schnittstellen zur Verfügung gestellt, ohne dass
hier eine Analyse, Modellierung oder Implementation von den
Projektteilnehmern geleistet werden muss.
Als erstes wird die optimale Auslegung von Temperierbohrungen
von Druckgusswerkzeugen vorgestellt. In der Industrie tritt dieses Problem
bei der Herstellung von aus Aluminium gegossenen Formteilen auf.
Beim Druckgießen wird flüssiges Aluminium
unter hohem Druck in einen Hohlraum einer Stahlform
eingespritzt. Dieser Hohlraum wird durch das Aluminium ausgefüllt und bildet
so das Formteil.
Durch die hohe Temperatur des Werkstoffs wird eine hohe Temperatur
in die Stahlhohlform eingebracht, die sich in Form von Spannungen äußert.
Zum Ausgleich werden in die Hohlformen Temperierbohrungen eingebracht,
durch die ein Wasser-Öl-Gemisch strömt.
Das dabei entstehende Bohrungsnetz muss die Hohlformen geeignet kühlen, gleichzeitig jedoch
einer Reihe technischer Anforderungen genügen (minimale Bohrungszahl, kurze
Kreislauflänge, etc.).
Die optimale Positionierung der Bohrungen ist somit
ein komplexes Problem und kann mit
Hilfe eines heuristischer Verfahren gelöst werden.
Die nebenstehende Abbildung zeigt Wisma 46, das höchste Gebäude in Indonesien:
23 Fahrstühle sorgen dafür, dass die Passagiere 50 Stockwerke
möglichst schnell und sicher erreichen. Das Fahrstuhlsteuerungsproblem
ist im Kern ein Zuordnungsproblem: Fahrstühle sollen Passagieren zugeordnet werden,
so dass möglichst geringe Wartezeiten im Gebäude zu verzeichnen
sind. Obwohl dieses Problem seit vielen Jahren bearbeitet wird, ist es
immer noch Gegenstand aktueller Forschung.
Tourenplanungsprobleme lassen sich generell wie folgt umreißen:
Ausgehend von einem einzelnen oder mehreren Depots sind mit einem
vorhandenen Fuhrpark
eine gewisse Anzahl von Kunden entsprechend einer gegebenen
Auftragsmenge mit Gütern zu beliefern. Die beschränkte Kapazität der
Fahrzeuge und das Wegenetz werden als bekannt vorausgesetzt.
Im Sinne vorgegebener Zielkriterien und gegebenenfalls unter Beachtung
weiterer Nebenbedingungen ist ein optimaler Belieferungsplan zu
ermitteln, der für jedes eingesetzte Fahrzeug die zu beliefernden
Kunden sowie die Reihenfolge der Belieferung enthält. Hinsichtlich der
zu berücksichtigenden Nebenbedingungen und des zu verwendenden
Optimierungsziels können verschiedene Ausprägungen von
Tourenplanungsproblemen unterschieden werden. Zur Bearbeitung von
insbesondere größeren Probleminstanzen können und wurden bereits verschiedene
Meta-Heuristiken eingesetzt, so dass eine Vergleichsbasis vorhanden ist.
Hauptziel der Projektgruppe ist die Entwicklung einer Optimierungsumgebung (Toolbox)
zur Behandlung komplexer Probleme mit meta-heuristischen
Verfahren.
Neben der Auswahl und der Einarbeitung in die jeweiligen Verfahren
müssen dazu alle Stufen der Softwareproduktentwicklung
durchlaufen werden. Das resultierende Softwareprodukt muss
speziell für die Gegebenheiten der Meta-Heuristiken objektorientiert entworfen werden.
Ferner muss
die Software implementiert, dokumentiert und getestet werden.
Die Implementierung soll in der Programmiersprache Java erfolgen.
Eine möglichst allgemeine Schnittstelle zu verschiedenen
Anwendungsproblemen ist zu entwerfen und anhand einiger gegebener Probleme
zu verifizieren. Hier werden sowohl theoretische Testfälle als auch reale
Anwendungen einbezogen.
Da viele Optimierungsprobleme eine hohe Zeitkomplexität aufweisen (bis
zu einigen Wochen), soll der Anwender einen möglichst umfassenden
Einblick in den Stand des Optimierungslaufes erhalten.
Verschiedene algorithmische Ansätze (siehe
Abschnitt 5.3) sollen effizient
miteinander verglichen werden können. Eine grafische Oberfläche zur
Eingabe der Parameter und zur Steuerung des Optimierungslaufs ist
erforderlich.
Als Minimalziel wird der konzeptionelle Entwurf, die Implementierung und
Dokumentation einer Optimierungsumgebung mit grafischer
Bedienoberfläche zur Optimierung mittels Meta-Heuristischer
Verfahren angesehen. Dazu wird mindestens ein
evolutionärer Ansatz, ein coevolutionärer Ansatz und eine klassische
Heuristik zu Vergleichszwecken
erwartet. Die Arbeiten sind ferner an mindestens zwei verschiedenen
Problemen, einem theoretischen Testfall ( [Sch95])
und einer in Abschnitt 5.4 beschriebenen Anwendung,
zu verifizieren.
Christian Blum and Andrea Roli.
Metaheuristics in combinatorial optimization: Overview and conceptual
comparison.
Technical Report TR/IRIDIA/2001-13, Universite Libre de Bruxelles,
IRIDIA, October, 23 2001.
Daniel Chernuchin, Dirk Hoppe, Rafael Hosenberg, Mutlu Özdemir, Marc Pompl,
Alexander Schluck, and Frank Schubmann.
Seminar: Metaheuristiken für die Optimierung.
Seminarbooklet, Dortmund, 2002.
H. Ramalhino Lourenco, O. Martin, and T. Stützle.
Iterated local search.
In F. Glover and G. Kochenberger, editors, Handbook of
Metaheuristics. Kluwer Academic Press, 1999.
http://www.intellektik.informatik.tu-darmstadt/ tom/pub.html,.
Das erste Treffen soll am 3.2.2003 stattfinden. Dies ist der Beginn der
Vorbereitungsphase, in der die Themen- und Aufgabenverteilung stattfindet.
Daran schließt sich folgende, auf Kalenderwochen (KW) basierende, PG-Arbeit
an:
17. KW:
Kompaktseminar mit Seminarvorträgen aller PG-Teilnehmer (,,Kennlernphase``).
18. KW:
Tutorial
Kleingruppen (2-3 Personen) sollen zu den wichtigsten Methoden
und Tools Tutorials abhalten, die die anderen PG-Teilnehmer
anhand leicht zu realisierender Übungen auf einen einheitlichen
Wissensstand bringt (z.B. Java, CVS, Meta-Heuristiken , etc.). Dabei ist an eine Vertiefung in spezielle Teilgebiete für einzelne Teilnehmer gedacht, jeder Teilnehmer sollte jedoch einen Überblick
über die gesamte Thematik haben.
Überarbeitung und Fertigstellung der Dokumentation.
6. - 7. KW:
Fertigstellung des Endberichts.
Im Wesentlichen sollte eine Zweiteilung der PG-Arbeit erfolgen. Im
ersten PG-Semester sollte die Wissens- und
Erfahrungsakquisition / Konzeption, im
zweiten PG-Semester die Umsetzung des PG-Ziels und die Testphase
durchgeführt werden.
Das erste PG-Semester schließt mit der Abgabe der Dokumentation zu den
einzelnen Komponenten und dem Zwischenbericht ab. Die Erkenntnisse und
Ergebnisse sollen soweit wie möglich in die Umsetzung der PG-Aufgabe im
zweiten PG-Semester einfließen. Im Gegensatz zu einer statischen
Softwareentwicklung legen wir Wert auf ein dynamisches Zusammenspiel
zwischen Entwurf und Programmierung. Die Entwurfsphase soll
dabei einen großen Stellenwert erhalten. Vorgesehen ist eine UML-basierte
Entwicklung. Ferner soll sichergestellt
werden, dass:
die Problematik möglichst umfassend verstanden wurde,
Feedback zwischen den unterschiedlichen Entwicklungsstadien möglich
ist,
die Teilnehmer nicht nur ihre Spezialaufgaben bewältigen, sondern
Projektgruppenarbeit und somit Techniken der Zusammenarbeit
zur Anwendung bringen.
Ferner ist eine enge Kooperation mit folgenden Institutionen abgesprochen:
Institut für Spanende Fertigung: Dr. J. Mehnen
Universität Dortmund
Baroper Str. 301, Geschossbau IV, Raum 235
D-44227 Dortmund
Die Auslegung von Temperierbohrungen ist ein stark praxisorientiertes Problemfeld,
bei dem sowohl technologische als auch softwaretechnische Lösungen
aufeinander abzustimmen sind. Die beiden Fragestellungen können durch die
Kooperation mit dem Institut für Spanende Fertigung (ISF,
Fakultät Maschinenbau, Prof. K. Weinert)
genau spezifiziert und so eine gezielte Planung und Umsetzung durch
eine umfangreiche Unterstützung gewährleistet werden.
Im Rahmen der Projektgruppe ist eine Besichtigung des Werks geplant,
in dem Druck- und Spritzgusswerkzeuge hergestellt und genutzt werden.
Auf diese Weise können die Teilnehmern echte
,,Industrieluft`` schnuppern und einen Eindruck von der
hohen Relevanz des Problems bekommen.
Sonderforschungsbereich 559: Teilprojekt M8 - Ganzheitliche Optimierung: Andreas Reinholz
Joseph-von-Fraunhoferstr. 20
D-44221 Dortmund
Der Sonderforschungsbereich 559: Modellierung großer Netze in
der Logistik verfolgt das Ziel eine Theorie zur Beherrschung
großer Netze in der Logistik zu entwickeln. Hierbei wurde im
Teilprojekt M8 (Ganzheitliche Optimierung) ein breites Spektrum
Meta-Heuristischer Verfahren analysiert und auf ihre
praktische Tauglichkeit getestet. Hier können die im Teilprojekt M8
erlangten Erfahrungen im Umgang mit theoretischen und
praktischen Optimierungsproblemen den PG-Teilnehmern zugänglich
gemacht werden.
Erweiterungsmöglichkeiten
Die Optimierungsumgebung kann durch klassische heuristische Optimierungsverfahren
ergänzt werden.
Erstrebenswert ist eine Weiterentwicklung, z.B. die Integration von
parallelen Verfahren sowie zur statistischen Auswertung und
Performanzanalyse.
Ferner möchten wir die Optimierungsumgebung als ,,freie Software`` zur
Verfügung stellen.
