In vielen Bereichen der Wirtschaft und Technik gibt es Problemstellungen, bei denen
eine Lösung aus einer großen Menge von möglichen Lösungen herausgesucht werden muß.
Ein Großlager für Mineralöl steht vor der Problematik, jeden Tag eine gute Route für
die Belieferung der Tankstellen zu finden. Eine optimale Route ist hierbei die kürzeste
Verbindung zwischen den einzelnen Tankstellen. Sie erlaubt die effektivste schnellste
Auslieferung der Öle, wobei allerdings berücksichtigt werden muß, daß bei den heutigen
Verkehrsbedingungen oft ein kleiner Umweg die schnellere Verbindung zwischen zwei Orten
sein kann. Die möglichen Variationen für die Route lasse sich mit der Formel (N-1)!/2
ausdrücken, wobei N die Anzahl der Tankstellen ist. Mit wachsenden N steigt die Anzahl
der zu untersuchenden Routen extrem stark an; z.B. sind das bei vier Tankstellen 3 Routen,
bei N=8 bereits 2520 Routen und bei N=16 sind es 6,54*1011 Routen.
Zum Herausfinden der besten Lösung benötigt auch ein Computer, in der PC- oder
Workstation-Kategorie, bei großen N zwischen einigen Minuten und ein paar Stunden
Rechenzeit. Oft ist es notwendig, ein oder mehrere Lösungen in recht kurzer Zeit zur
Verfügung zu haben, um einen großen Fuhrpark zu verwalten oder kurzfristige
Umdisponierungen vornehmen zu können. Deshalb akzeptieren die Anwender häufig Lösungen,
die nicht die beste, aber eine Lösung in der Nähe der optimalen Lösung ist. Dieses
Eingeständnis wird unter der Voraussetzung gemacht, daß das Berechnen einer fast
optimalen Lösung in einem Bruchteil der Zeit erfolgt, die für das Finden der optimalen
Lösung gebraucht wird.
Das globale Optimum kann mit der Implementierung eines iterativen Algorithmus erreicht
werden. Das Programm arbeitet hierbei nach festgelegten Regeln, die bei der Ausführung
mit den gleichen Eingabeparametern immer das gleiche Ergebnis liefern. Hierbei werden alle
möglichen Varianten untersucht. Die mit der besten Bewertung ist das globale Optimum. Die
dabei benötigte Rechenzeit steigt mit der Anzahl der Lösungsmöglichkeiten, so daß der
iterative Algorithmus selten zum Einsatz kommt. Ferner ist es oft der Fall, daß diese
Verfahren im lokalen Optimum hängenbleiben und sich nicht mehr daraus befreien können,
um ein besseres Ergebnis zu finden.
Im Gegensatz dazu ergeben die heuristischen Algorithmen in fast allen Durchläufen andere
Ergebnisse, auch wenn immer die gleichen Eingabeparameter verwendet werden. Der
signifikante Unterschied liegt in der Benutzung des Zufallselements zur Bestimmung der
Ausgabe. Eine Zufallszahl nimmt im Ablauf des Algorithmus den entscheidenden Einfluß auf
das Endergebnis, in dem sie Teillösungen auswählt oder verwirft.
Die IBM-Forscher Lirkpatrick, Gelatt und Vecchi fanden im Jahre 1993 eine Analogie aus
der Werkstoffphysik. Beim Erstarren von Metallen, die gerade aus der Schmelze genommen
sind, bilden die Atomen regelmäßige Anordnungen. Ein ideales Kristall ist ein Kristall
mit der günstigsten Energiebilanz. Das Problem beim Abkühlen der Metalle an der Luft
oder im Wasser ist, daß meistens keine perfekten Kristalle gebildet werden. Es kommt
immer zu Fehlern in der Anordnung, die die Energiebilanz erhöhen. Das zu schnelle
Entziehen der Bewegungsenergie läßt die Atome in ihrer ungünstigen Position verbleiben.
Sie haben nicht mehr die notwendige Energie, um eine bessere Position einnehmen zu
können. Beim Produzieren von perfekten Kristallen ist ein anderer Abkühlungsvorgang zu
benutzen. Unter ständiger Zufuhr von abnehmender Wärme werden die Kristalle abgekühlt.
Dadurch gibt man den Kristallen genügend Bewegungsenergie, um eine schlechte Position
verlassen und eine günstigere Stelle einnehmen zu können.
Die Forscher setzen das Erzeugen von perfekten Kristallen einem heuristischen und das
Produzieren von nicht perfekten Kristallen mit einem iterativen Algorithmus gleich. Sie
nahmen den Metropolis-Algorithmus als Basis, der für die Simulation von physikalischen
Systemen auf Computern erstellt wurde. Er beschreibt Systeme im thermischen Gleichgewicht.
Eine Änderung der Atomanordnung wird nur dann angenommen, wenn dadurch die Gesamtenergie
verkleinert wird. Eine Erhöhung der Energie wird nur mit einer gewissen
Wahrscheinlichkeit akzeptiert.
Die Übertragung des Vorgangs aus der Werkstoffphysik in das Fachgebiet der Operation
Research erfolgt, indem an Stelle der Temperatur der zu optimierende Wert eingesetzt wird.
Im speziellen Fall der Wegoptimierung wird der Temperaturwert durch die zu minimierende
Streckenlänge substituiert. Die Suche nach dem besten Weg ist dann analog zur Abkühlung
der Metallschmelze. Am Anfang werden noch fast alle Veränderungen mit einer hohen
Wahrscheinlichkeit angenommen. Mit sinkender Temperatur werden nur noch kleine
Modifikationen akzeptiert. Ist die Temperatur auf 0 gesunken, ist der Vorgang beendet. Es
sollte jetzt eine beinahe optimale Lösung gefunden worden sein.
Zwei andere Vertreter heuristischer Algorithmen sind die Evolutionsstrategie und der Genetische Algorithmus. Sie versuchen den Prozeß der natürlichen Auslese - nur die Starken oder Guten überleben - von der Natur zu kopieren und in ein technisches Lösungsverfahren zu integrieren. Analog zum Vorbild wird der Übergang von einer Konfiguration in eine neuere durch drei Schritte vollzogen: Mutation, Rekombination und Selektion der Chromosomen, wobei ein Chromosom eine vollständige Konfiguration im technischen Verfahren darstellt. Die Mutation bedeutet, daß ein Teilbereich eines Chromosoms geändert wird, die Rekombination vertauscht je einen Teilbereich eines Chromosoms mit dem Teilbereich eines anderen. Die manipulierten Chromosomen durchlaufen die Selektion, die entscheidet, welche von ihnen überleben und in die nächste Generation übernommen werden.
Die Unterschiede zwischen beiden Algorithmen sind einerseits in der unterschiedlichen Betrachtung der Chromosomen und einer anderen Codierung der Lösungsvektoren in einem Chromosom zu sehen. Der Genetische Algorithmus gliedert ein Chromosom in Gene auf, die ihrerseits in Allele aufgeteilt sind. Die Analogie zur Optimierungsaufgabe ist, daß ein Chromosom eine Gesamtlösung als ein Bitstring repräsentiert, ein Gen eine Teillösung, also einen definierten Ausschnitt, und das Allele ein einziges Bit darstellt. Aus der Sicht der Evolutionsstrategie erfolgt die letzte Aufteilung nicht mehr und ein Gen wird als Fließkommazahl kodiert. Andererseits liegen die Schwerpunkte hinsichtlich der Variation der Chromosomen anders. Der Genetische Algorithmus legt mehr Wert auf die Rekombination und die Evolutionsstrategie baut mehr auf die Mutation der Chromosomen. Beide Suchfunktionen haben das Fehlen einer Abbruchfunktion gemeinsam, z.B. das Erreichen einer Temperatur, bei dem die Metallschmelze erstarrt. Die Algorithmen terminieren beim Erreichen einer vorher festgelegten Genertionszahl.
Der folgende Abschnitt stellt einige heuristische Algorithmen vor. Darunter sind die Verfahren "Simuliertes Ausglühen" und "Toleranzschwellen". Es wurden bewußt die einfachen Algorithmen ausgewählt, da hier mit der Visualisierung die Mächtigkeit der heuristischen Verfahren gezeigt werden soll, was auch mit diesen möglich ist.
Dieser Abschnitt stellt die Algorithmen dar, mit denen die Optimierung der zu untersuchenden Funktionen vorgenommen werden. Neben der verbalen Erklärung ist der Grobablauf in einem Struktogramm wiedergegeben. Die Diagramme basieren auf dem Pseudocode aus der Zeitschrift c’t. Der Pseudocode geht davon aus, daß die Algorithmen in einer Funktion mit einmaligem Aufruf durchgeführt werden. Der Kontext dieser Arbeit verlangt aber ein mehrmaliges Aufrufen der Funktionen innerhalb eines Optimierungsdurchgangs, um ein quasi-paralleles Arbeiten aller Algorithmen zu gewährleisten. Aus diesem Grund weichen die Struktogramme etwas von dem Pseudocode ab.
2.1 Zufallsverfahren
Ein sehr einfacher Algorithmus (Abbildung 2.1-1) ist die vollkommen zufällige Suche
nach dem globalen Optimum. Eine Bewertung und Selektion einer neuen Konfiguration erfolgt
hierbei nicht, sondern es wird jede neue Variante akzeptiert. Da eine Kontrollfunktion
fehlt, die ein Terminieren des Algorithmus nach einer endlichen Zeit gewährleistet, ist
das Abbruchkriterium durch die Anzahl der Optimierungsdurchläufe gegeben.
Zum einen ergibt sich daraus, daß lokale Optima zu Gunsten einer besseren Konfiguration
verlassen werden können. Zusätzlich stellt es ein schnelles Verfahren dar. Zum anderen
ist nach der Beendigung des Verfahrens überhaupt keine Aussage über die erreichte
Qualität der gefundenen Lösung möglich.
: die aktuelle Konfiguration (Suchwert)
: eine neue Konfiguration
Die schematische Vorgehensweise des Verfahren wird an Hand des Funktionsgraphen 2.1-2
demonstriet. Neben dem aktuellen Suchwert sind mehrere neue Werte wiedergegeben, von denen im realen Ablauf nur
ein Wert existiert. Das Suchverfahren wird den Punkt durch einen der Punkte austauschen und die Optimierung
fortsetzen, bis die Anzahl der vorgegebenen Optimierungsdurchläufen erreicht ist.
2.2 Simulated Annealing
Wie in der Einleitung beschrieben, ist das "Simulierte Ausglühen" ein heuristischer Algorithmus, dem der Metropolis-Algorithmus zugrunde liegt. Die Wahrscheinlichkeit, mit dem ein energetisch schlechterer Zustand akzeptiert wird, läßt sich mit der Formel beschreiben:
Wobei DB der Bnergieunterschied, T die Temperatur und k die Boltzmann-Konstante ist. Der Wert DB wird durch den zu optimierenden Wert substituiert. Zur Vereinfachung wird die Boltzmann-Konstante weggelassen. Eine Zufallszahl im Intervall [0,1] übernimmt die Entscheidung, ob ein schlechterer Zustand eingenommen werden kann. Ist die Zahl kleiner als P(DE), wird die energetisch schlechtere Konfiguration akzeptiert. Im anderen Fall wird sie verworfen. In der Praxis kommen für die Abkühlungsfunktion auch andere als die Exponentialfunktion zum Einsatz.
Der Algorithmus (Abbildung 2.2-1) startet mit einer hohen Temperatur, bei der durch die große Wahrscheinlichkeit P(DE) viele Konfigurationen akzeptiert werden, die eine Verschlechterung in Bezug auf die aktuelle Konfiguration darstellen. Sind einige Konfigurationen besser als die aktuelle, oder wurde eine gewisse Anzahl von neuen Konfigurationsvarianten ohne Verbesserung durchlaufen, führt das Verfahren eine Verringerung der Temperatur durch. Anschließend wird die Optimierung mit der neuen Temperatur fortgesetzt. Tritt bei einer Temperatur keine Verbesserung der Lösung mehr ein, ist die Metallschmelze erstarrt und die Optimierung beendet. Jetzt sollte ein Lösung gefunden worden sein, die in der Nähe des absoluten Optimums liegt, wie weit davon entfernt, läßt sich nicht feststellen. Wie nah die Lösung an der besten ist, wird durch die Geschwindigkeit des Abkühlens und der Verweildauer bei einer Temperatur festgelegt. Diese Parameter sind durch Probieren zu variieren, um einen Eindruck von dem gefundenen Optimum zu bekommen.
Die Abbildung 2.2-2 zeigt einen Graphen einer Funktion, die von dem Verfahren "Simuliertes Ausglühen" auf ihre globales Maximum hin untersucht werden soll. Der Algorithmus akzeptiert nur dann eine andere Konfiguration, wenn die neue Konfiguration eine unterhalb der aktuellen Temperatur liegt oder die Wahrscheinlichkeit das Akzeptieren der schlechteren Konfiguration erlaubt. Die Symbole in der Abbildung 2.2-2 haben folgende Bedeutung:
: eine mögliche neue Konfiguration, mit schlechterer Eigenschaft
Der hier dargestellte Graph soll die schematische Vorgehensweise des Verfahrens
demonstrieren. Aus diesem Grund sind neben dem aktuellen Suchwert mehrere neue Werte und wiedergegeben,
von denen im realen Ablauf nur ein Wert existieren würde. Das Optimierungsverfahren wird
auf jeden Fall den Punkt durch einen der Punkte austauschen. Wenn es die Wahrscheinlichkeit
zuläßt, könnte auch ein schlechterer Wert vom Typ den aktuellen Suchwert ersetzen. Dieses
Verhalten kann das Verfahren aus einem lokalen Optimum am Anfang der Optimierung befreien,
da die Wahrscheinlichkeit in Bezug auf die abkühlende Temperatur gesetzt wird.
2.3 Thresbold Accepting
Da Probleme, die in die Kategorie der Verbindungsprobleme gehören, häufig in der Wirtschaft anfallen, gibt es von deren Seite aus eine starke Nachfrage, effiziente Lösungsverfahren zu entwickeln. Die Mitarbeiter Dueck und Scheuer des IBM-Forschungszentrums in Heidelberg haben am Anfang der ,90er Jahre eine Variante des Simulated Annealing erarbeitet, genannt Threshold Accepting (Abbildung 2.3-1). Es bedeutet die Akzeptanz einer Lösung gemäß eines Schwellenwertes. Die Modifikation ist nur minimal. Im Gegensatz zum Simulierten Ausglühen wird eine energetisch schlechtere Variation nicht mit einer gewissen Wahrscheinlichkeit als neue Konfiguration akzeptiert. Eine Lösung wird nur dann übernommen, wenn sie unterhalb einer Temperatur liegt.
Die Verbesserung der Ablaufgeschwindigkeit kommt durch das Wegfallen der Wahrscheinlichkeitsfunktion und der Bestimmung der Zufallszahl zustande. Neben der Senkung der Rechenzeit kommt ein weiterer Vorteil dazu. Dueck und Scheuer stellten fest, daß in der Regel der Toleranzschwellen-Algorithmus ein besseres Ergebnis als das Simulierte Ausglühen liefert. Da es sich hier um heuristische Verfahren handelt, ist diese Aussage nicht beweisbar.
Die Arbeitsweise des "Toleranzschwellen"-Algorithmus wird am Beispiel der Abbildung 2.3-2 gezeigt. Das Ziel der Optimierung ist das globale Maximum der Funktion. Der Algorithmus akzeptiert nur dann eine andere Konfiguration, wenn die neue Konfiguration eine unterhalb der aktuellen Temperatur liegt. Der Unterschied zum "Simulierten Ausglühen" ist, daß keine Wahrscheinlichkeit für ein alternatives Akzeptieren einer schlechteren Konfiguration berücksichtigt wird. Die Symbole in der Abbildung 2.3-2 haben folgende Bedeutung:
Der hier dargestellte Graph soll die schematische Vorgehensweise des Verfahrens
demonstrieren. Aus diesem Grund sind neben dem aktuellen Suchwert mehrere neue Werte und wiedergegeben,
von denen im realen Ablauf nur ein Wert existieren würde. Das Optimierungsverfahren wird
auf jeden Fall den Punkt durch einen der Punkte austauschen. Alle schlechteren Werte werden vom
Optimierungsvorgang ignoriert.
Bedienungsanleitung
Als erstes ist die Applikation mit dem auf der Diskette befindlichen Installations-Programm auf den Rechner zu kopieren. Die Benutzerführung während der Installation ist in englischer Sprache und verlangt nur die Eingabe des Zielverzeichnisses.
Die Anleitung soll dem Anwender die schnelle und problemlose Bedienung des Programms dieser Arbeit ermöglichen. Dafür werden die Erläuterungen mit einigen Bildschirmabbildungen ergänzt. Ein erster optischer Eindruck des Programms ist mit dem unten abgedruckten Screenshot möglich, das alle verfügbaren Algorithmen mit ihren Darstellungsbereichen wiedergibt.
Die Visualisierung von Optimierungsverfahren ist die Aufgabe des Programms. Für die
visuelle Darstellung des Vorgangs sind zwei-dimensionale Funktionen vorgegeben, auf denen
die Suchfunktionen das Optimum der dargestellten Funktion finden soll. Es können alle zur
Verfügung stehenden Algorithmen gleichzeitig oder einzeln betrachtet werden. Ein
mehrfaches Starten eines Optimierungsvorgangs ist nicht vorgesehen. Die Art und Weise der
Abbildung der untersuchten Funktion kann pro Optimierungsverfahren individuell eingestellt
werden. Jedes Fenster besitzt neben der Darstellungsfläche für den Funktionsgraphen drei
Schieberegler. Der oben links plazierte Regler erlaubt die Größenänderung des Graphen
in der Darstellungsfläche. Die anderen drei Schieberegler dienen zur Drehung des
Funktionsgraphen um die Raumachsen: Der linke ist für die Z-Achse, der rechte für die
X-Achse und der untere Regler für die Rotation um die Y-Achse zuständig. Die aktuellen
Faktoren der Regler können oberhalb der Zeichenfläche abgelesen werden.
Sind alle gewünschten Verfahren selektiert, erfolgt die Bedienung des Suchvorgangs über
das Steuerzentrum der Applikation. Die Farben-Legende informiert über die Bedeutung der
Farbpunkte in den Funktionsgraphen. Das Fenster "Werte der Algorithmen" zeigt
die aktuellen Optima und den Zustand der Verfahren.
Die Änderung der Parameter für die Funktionen und der Optimierungsverfahren erlaubt ein
Experimentieren mit den einzelnen Algorithmen. Eine besondere Option stellt der
Funktionseditor dar. Er erlaubt die Eingabe von Funktionen, die mit den
Optimierungsalgorithmen untersucht werden sollen. Abschließend können die Graphen der
Funktionen kopiert und in andere Applikationen eingefügt oder für eine spätere
Verwendung gespeichert werden. Vor dem Beenden des Programms wird überprüft, ob an den
Parametern eine Modifikation vorgenommen wurde. Trifft dies zu, wird dem Anwender
überlassen die Änderungen zu sichern, die bei einem erneuten Programmstart automatisch
eingelesen werden.
Optimierungsverfahren
In dem ersten Menü "Optimierung" sind alle Algorithmen aufgelistet, die für
die Untersuchung der Funktionen zur Verfügung stehen, wobei alle Suchverfahren auf der
gleichen Funktion arbeiten. Die Auswahl eines Menüpunktes bewirkt, daß ein Fenster für
diesen Algorithmus geöffnet wird, in dem die selektierte Funktion aus dem Menü
"Funktion" wiedergegeben wird. Ein nochmaliges Selektieren wird durch das
Deaktivieren des gerade ausgewählten Menüpunktes unterbunden. Das Ändern der meisten
Funktionsparameter und aller Optimierungswerte ist nur möglich, wenn kein Algorithmus
aktiv ist, d.h. kein Fenster mit einem Funktionsgraphen im Applikationsfenster geöffnet
wurde. Bei der Auswahl des ersten Verfahrens werden zusätzlich zwei andere Fenster
erzeugt: Das Steuerzentrum und die Farben-Legende. Letzteres kann nach Bedarf wieder
geschlossen werden. Sollte es danach benötigt werden, kann es durch den Menüeintrag im
"Fenster"-Menü erneut erstellt werden. Ist eines dieser Fenster durch eins mit
einem Funktionsgraphen überdeckt, ist durch das Ausführen des entsprechenden Eintrags im
"Fenster"-Menü das jeweilige verborgene in den Vordergrund zu bringen.
Die Funktionen des Menüs "Grafik" wirken immer auf das aktive Fenster. Ein
aktives Fenster ist immer eines, in dem ein Funktionsgraph wiedergegeben wird. Die
Zusatzfenster können nicht zum aktiven Fenster gemacht, aber jederzeit benutzt werden.
Funktionen
Die vom Programm vorgegebenen Testfunktionen können durch das gleichnamige Menü ausgewählt werden. Definiert der Benutzer eigene Funktionen, erscheinen diese am Ende des Menüs und werden durch eine Linie von den anderen getrennt. Die Selektion ist nur möglich wenn noch kein Optimierungsverfahren gestartet wurde. Folgende Funktion sind im Programm integriert:
f1(x,z) = 20 * sin (0.1 * (x2 + z2)1/2)
f2(x,z) = x2 + z2
f3(x,z) = log (100 * (x2 - z)2 + (1 - x)2)
f4(x,z) = integer(x) + integer(z)
f5(x,z) = x4 + 20 * Gauß(x) + z4 + 20 * Gauß(z)
f6(x,z) = -x * sin(|x|1/2) -z * sin(|z|1/2)
Funktions-Editor
Der Funktionseditor ist für zwei Aufgabenbereiche zuständig. Für die Auflistung aller festverdrahteten Funktionen mit ihren Wertebereichen. Die Parameter für der Darstellung und die Farben sind auch von hier aus modifizierbar. Da alle Funktionen erreichbar sind, ist die Änderung ihrer Parameter schnell möglich. Der zweite Anwendungszweck ist die Eingabe anwenderdefinierter Funktionen, die mit den Optimierungsalgorithmen untersucht werden sollen.
In der Liste werden die Funktionen, die vom Programm vorgegeben werden, durch einen Kreis vor ihrem Funktionsstring gekennzeichnet. Bei selbstdefinierten Funktionen fehlt diese Kennzeichnung.
Das Auslösen des Buttons "Neu" bringt den Dialog "Formel-Editor" auf den Bildschirm. Mit ihm ist dem Anwender die Möglichkeit gegeben, eigene Funktionen einzugeben. Dabei stehen einige mathematische Funktionen bereit:
- sin - Sinus
Einige Funktionen sind an bestimmten Stellen des Wertebereichs mathematisch nicht definiert. Aus diesem Grund sind im Programm Einschränkungen für diese Funktionen vorgenommen worden. Die Funktionen sqrt(), ln(), log() sind nur für Argumente größer gleich null definiert. Argumente kleiner null werden abgefangen und als Funktionswert wird die Zahl Null zurückgegeben. Zur Vermeidung der Polstelle von tan() bei p/2 wird das Argument etwas manipuliert:
tan (p /2 * n), wobei n zu der Menge der natürlichen Zahlen gehört
=>Die Eingabe der Funktion ist entweder über die maus- oder die tastaturorientierte Eingabe vorgesehen. Bei der Eingabe mit der Maus finden die entsprechenden Buttons des Dialogs Verwendung. Dabei wird bei der Auswahl eines Funktion-Buttons die notwendige nachfolgende Klammer automatisch mit in die Eingabezeile übernommen. Zum Löschen des letzten Zeichens in der Eingabezeile ist der Button mit dem nach links gerichteten Pfeil vorgesehen. Die alternative Eingabe ist mit der Tastatur möglich. Dafür ist die Eingabezeile zu aktivieren und die Funktion direkt einzugeben. Die Benutzung beider Vorgehensweisen kann natürlich auch kombiniert werden. Die Überprüfung der Funktion auf korrekte Syntax ist sowohl mit dem Button "Prüfen" als auch mit dem positiven Abschuß des Dialogs realisiert worden. Die erste Variante erlaubt zusätzlich die Eingabe der Werte für x und z, aus denen das Programm den Funktionswert f(x,z) berechnet.
Die neu eingegebene Funktion wird der Liste im Dialog "Formel Bearbeiten"
hinzugefügt. Dort ist als nächstes die Eingabe der Intervall-Grenzen der neuen Funktion
vorzunehmen. Eventuell können auch die anderen Parameter der Funktion angepaßt werden.
Das Löschen und Bearbeiten von selbstdefinierten Funktionen ist mit den dafür
gekennzeichneten Buttons vorgesehen.
Das Aktivieren einer benutzerdefinierten Funktion erfolgt über das Menü
"Funktionen" im Hauptmenü.
Tips und Anregungen an: emiel@informatik.fh-augsburg.de
