Algorithmen in der Java-Praxis: Teil 3

Metaheuristiken zur Lösung komplexer Probleme

Olena Bochkor, Dr. Veikko Krypczyk

©Shutterstock / asharkyu

Einige Probleme sind derartig komplex, dass man mit herkömmlichen Algorithmen keine brauchbare Lösung ermitteln kann. Das würde viel zu lange dauern. Um dennoch eine gute Lösung zu finden, werden Metaheuristiken eingesetzt. Sie steuern die problemspezifischen Algorithmen zielgerichtet durch den Lösungsraum.

Algorithmen in der Java-Praxis

Teil 1: Algorithmen, Entwicklung und formale Kriterien, Systematisierung

Teil 2: Suche und Sortieren, auch mit paralleler Verarbeitung

Teil 3: Metaheuristiken zur Lösung komplexer Probleme

Teil 4: Metaheuristiken in Java – Programmierung eines Fallbeispiels

Teil 5: Ausgewählte Bibliotheken für Java – schneller in der Praxis

Viele Probleme aus Wirtschaft und Natur sind so komplex, dass man sie nicht durch einen herkömmlichen Algorithmus lösen kann. Zumindest würde die dafür benötigte Zeit den verfügbaren Rahmen sprengen. Mit anderen Worten: Der Lösungsraum ist so umfassend, dass ein vollständiges Durchsuchen nicht möglich ist. Um nun dennoch eine brauchbare Lösung zu ermitteln, setzt man dazu Metaheuristiken ein. Diese steuern das konkrete Lösungsverfahren (problemspezifischer Algorithmus) durch den Lösungsraum. Dabei kann nicht garantiert werden, dass man die beste Lösung findet. Man ist jedoch auf der Suche nach einer guten Lösung.

Anwendungen von Metaheuristiken sind zum Beispiel die Losgrößenplanung in der Produktion, die Ermittlung kürzester Wege bei der Transportoptimierung, die Planung von Szenarien in Computerspielen usw. Wir geben hier einen Überblick über diese Verfahren.

Metaheuristiken

Abbildung 1 zeigt eine Übersicht zur Einteilung von Lösungsverfahren. Im unteren Teil findet sich die Konkretisierung für Tourenplanungsprobleme, zum Beispiel das Travelling Salesman Problem (Kasten: „Tourenplanung als Paradebeispiel für die Anwendung von Metaheuristiken“).

Abb. 1: Systematisierung von Lösungsverfahren für Optimierungsprobleme

Abb. 1: Systematisierung von Lösungsverfahren für Optimierungsprobleme

Tourenplanung als Paradebeispiel für die Anwendung von Metaheuristiken

Das Travelling Salesman Problem (TSP) ist eines der bekanntesten Optimierungsprobleme. Ein Handlungsreisender soll in einer Rundreise (Tour) n vorgegebene Orte besuchen. Er startet dazu an einem Ort, besucht nacheinander die restlichen Orte und kehrt schließlich zu seinem Ausgangspunkt zurück. Das Ziel ist eine Tour mit minimaler Gesamtstrecke. Die Entfernungen zwischen allen Orten sind gegeben. Statt um Entfernungen kann es sich auch um Reisezeiten oder um andere Kosten, zum Beispiel Treibstoff, handeln. Das TSP gilt gewissermaßen als Standardproblem der Tourenplanung. In der Praxis wird es um realitätsnahe Konkretisierungen erweitert, zum Beispiel dass die Zahl der Orte auch während der laufenden Abarbeitung variiert, beispielsweise wenn weitere Kunden kurzfristig einen Auftrag ordern (dynamische Tourenplanung). Die Problemstellung bleibt gleichermaßen komplex und kann heutzutage nur über Optimierungsverfahren näherungsweise gelöst werden.

 
Die Lösungsverfahren können wir in exakte Verfahren, problemspezifische Heuristiken und Metaheuristiken einteilen. Exakte Verfahren setzen voraus, dass der Lösungsraum überschaubar ist und man in einer vertretbaren Zeit zum Ergebnis kommt. Das bekannteste Verfahren ist das A*-Verfahren. Problemspezifische Heuristiken kann man kaum verallgemeinern, denn sie sind auf die Problemstellung zugeschnitten. Wir haben in Abbildung 1 einige Verfahren aus dem Bereich der Tourenplanung aufgeführt. Muss ein anderes Problem gelöst werden, gibt es andere Lösungsansätze. Interessant für unsere Betrachtungen sind die Verfahren unter dem Punkt „Metaheuristiken“. Sie können eingesetzt werden, um lokale Suchverfahren, d. h. „normale“ Heuristiken, zu steuern. Was unterscheidet eine Metaheuristik von einer problemspezifischen Heuristik? Der Nachteil von lokalen Suchverfahren ist, dass sie nur die unmittelbare Nachbarschaft einer gegebenen Startlösung nach Verbesserungen durchsuchen. Diese lokale Suche führt oft dazu, dass ausschließlich ein lokales Optimum ermittelt wird. Im Gegensatz dazu lassen Metaheuristiken während der laufenden Suche auch Verschlechterungen der gefundenen Lösungen zu, um das Festlaufen in lokalen Optima zu vermeiden (Abb. 2).

Abb. 2: Verhältnis von lokalen und globalen Optima, dargestellt an einem Minimum

Abb. 2: Verhältnis von lokalen und globalen Optima, dargestellt an einem Minimum

Zu den Metaheuristiken gehören Tabu Search, Guided Local Search, Ameisenalgorithmus, Evolutionäre Strategien und Genetische Algorithmen und das Simulated Annealing. Wir stellen einige Ansätze daraus vor.

A*-Algorithmus

Der A*-Algorithmus ist ein Basisverfahren zur Suche nach dem kürzesten Weg zwischen Start und Ziel [1] (Kasten: „Ein Beispiel zur Pfadsuche mit A*“). Typischerweise wird er in Computerspielen oder bei der kartenbasierten Routenplanung angewendet. Auf diese Weise kann z. B. der computergesteuerte Gegner den kürzesten Weg zur Spielfigur suchen. Auch für die Pfadsuche in sozialen Netzwerken kann der A*-Algorithmus eingesetzt werden (Abb. 3).

Abb. 3: Prinzip der Pfadsuche in sozialen Netzwerken

Abb. 3: Prinzip der Pfadsuche in sozialen Netzwerken

Grundsätzlich gehört der A*-Algorithmus in die Verfahrensklasse der informierten Suchalgorithmen. Informiert bedeutet, dass mit Hilfe einer Schätzfunktion gearbeitet wird. Die Eigenschaften sind:

  • Korrektheit: Eine Lösung garantiert auch eine Lösung des Suchproblems, d. h. folgt man dem vorgeschlagenen Pfad vom Start zum Ziel, kommt man mit Sicherheit an.

  • Vollständig: Existiert eine Lösung, wird sie auch mit Hilfe des A*-Verfahrens ermittelt. Es kann also nicht sein, dass ein Pfad zwischen Start- und Ziel existiert, jedoch nicht entdeckt wird.

  • Optimal: Die ermittelte Lösung ist optimal. Der Einsatz von Heuristiken führt nicht immer zur optimalen Lösung.

  • Effizient: Die Anwendung eines anderen Algorithmus muss mindestens genauso viele Knoten untersuchen, um eine Lösung des Suchproblems zu finden.

Ein Nachteil des Verfahrens ist u. a. eine hohe Speicherplatzkomplexität. Für ein Verständnis des A*-Algorithmus werden Begriffe aus der Graphentheorie benötigt (Kasten: „Graphentheorie“). Der A*-Algorithmus untersucht immer zuerst diejenigen Knoten, die wahrscheinlich auf dem kürzesten Weg zum Ziel führen. Um eine Bewertung möglicher Alternativen vorzunehmen, wird allen Knoten ein Kostenwert f mit Hilfe einer Funktion f = F(x) zugeordnet. Der Wert dieser Funktion gibt an, wie lang der Weg (Pfad) vom Start zum Ziel unter Verwendung dieses Knotens im kürzesten Fall höchstens ist. Mit anderen Worten: Der Wert von f ist ein Maß dafür, mit welcher Entfernung bestenfalls zu rechnen ist.

Graphentheorie

Einige Begriffe aus der Graphentheorie [2]:

  • Graph: eine nichtleere Menge von Knoten und Kanten; jede Kante hat einen Anfangs- und einen Endknoten

  • Knoten: ein Element der Knotenmenge eines Graphen

  • Nachbar: ein Knoten ist mit einem anderen Knoten durch eine Kante verbunden

  • Netzwerk: ein gerichteter, kantenbewerteter Graph mit Quelle und Senke; die Kanten dürfen nur positiv bewertet sein

 
Der Knoten mit dem niedrigsten f-Wert wird als Nächstes untersucht. Der f-Wert setzt sich aus zwei Komponenten zusammen:

  • der tatsächlichen Länge vom Startknoten bis zum aktuell betrachteten Knoten; dieser Wert wird mit g bezeichnet und über die Funktion G(x) ermittelt.

  • dem Schätzwert h vom betrachteten Knoten x zum Zielknoten; die zugehörige Berechnungsvorschrift wird durch die Funktion H(x) ausgedrückt: f = F(x) = g + h = G(x) + H(x)

Ein wichtiger Bestandteil des Algorithmus ist die verwendete Heuristik. Wie bereits ausgeführt, dient sie dazu, die Kosten zwischen den aktuellen Knoten und dem Zielknoten zu schätzen. Für eine optimale Lösung muss die Schätzfunktion H(x) zulässig sein. Das bedeutet, dass die Schätzfunktion die Kosten (Entfernung) vom aktuellen Knoten bis zum Zielknoten niemals überschätzen darf, d. h. die wahre Entfernung vom aktuellem Knoten x zum Zielknoten muss größer oder gleich der geschätzten Entfernung sein. Die Erfüllung dieser Forderung ist notwendig, damit der kürzeste Weg gefunden wird. Ansonsten wird die Suche ggf. in die falsche Richtung gelenkt, d. h. mögliche Pfade auf den Weg zum Ziel werden wegen einer falschen Einschätzung nicht untersucht. In einem solchen Fall kann das Auffinden der optimalen Lösung nicht garantiert werden. Welche Art von Schätzfunktion zum Einsatz kommt, ist abhängig von der Problemstellung und muss angepasst werden. Mögliche Optionen sind:

  • Euklidischer Abstand (Luftlinie): Diese Variante ist anwendbar, wenn der Abstand zwischen zwei Orten unter geografischen Gesichtspunkten zu schätzen ist. Der Abstand berechnet sich mit Hilfe des Satzes des Pythagoras. Die Straßenverbindung (Entfernung) ist zwangsweise länger, da hier die örtlichen Gegebenheiten zu berücksichtigen sind.

  • Manhattan-Abstand: Die Manhattan-Metrik (Manhattan-Distanz, Mannheimer-, Taxi- oder Cityblockmetrik) ist eine Metrik, in der die Distanz zwischen zwei Punkten als die Summe der absoluten Differenzen ihrer Einzelkoordinaten definiert wird. Bei der Anwendung des Manhattan-Abstands wird berücksichtigt, dass sich die Objekte auf der Matrix lediglich im rechten Winkel, also entlang der Achsenparallelen bewegen.

  • Diagonalabstand: Falls sich die Objekte auch diagonal innerhalb der Matrix bewegen können, ist die Berechnung auf der Basis des Diagonalabstands möglich.

Das Suchverfahren läuft nach einem einheitlichen Schema ab. Dabei können die Knoten jeweils einer der folgenden Kategorien zugeordnet werden:

  • Unbekannte Knoten: Diese Knoten sind während der Suche noch unbekannt. Auch der Weg zu diesen Standorten ist noch nicht erforscht. Zu Beginn der Suche gehören alle Knoten – außer dem Startknoten – in diese Kategorie.

  • Bekannte Knoten: Zu diesen Knoten ist zum aktuellen Zeitpunkt bereits ein Weg bekannt. Dieser muss jedoch noch nicht optimal sein. Alle bekannten Knoten werden zusammen mit ihrem f-Wert in der Open List gespeichert. Zum Start des Algorithmus ist lediglich der Startknoten bekannt. Während der eigentlichen Suche werden die Nachfolgeknoten des aktuell untersuchten Knotens aus der Liste der unbekannten Knoten entnommen und in die Liste der bekannten Knoten aufgenommen. Der Weg vom Startknoten bis zu diesem Knoten wird errechnet. Ebenfalls wird mittels der Schätzheuristik der f-Wert bestimmt. Es gibt dabei folgende Konstellationen: (1) Wenn der betreffende Knoten keinen weiteren Nachfolgeknoten hat und auch der f-Wert nicht der minimale Wert ist, wird dieser Knoten wieder aus der Liste der bekannten Knoten entfernt und in die Closed List übernommen. (2) Hat der Knoten jedoch Nachfolgeknoten oder der f-Wert ist minimal, bleibt der Knoten in der Open List.

  • Abschließend untersuchte Knoten: Zu diesen Knoten ist der kürzeste Weg bekannt. Die Suche ist abgeschlossen, wenn der Zielknoten in diese Liste aufgenommen wurde.

Grundsätzlich werden in der Closed List alle abschließend untersuchten Knoten gespeichert. Damit soll vermieden werden, dass ein Knoten mehrfach untersucht wird. Die Knoten der Closed List beschreiben nicht den kürzesten Weg. Knoten, die untersucht wurden, enthalten einen Zeiger auf ihren Vorgängerknoten. Mit dessen Hilfe kann der Weg bis zum Startknoten zurückverfolgt werden. Damit wird der Weg rückwärts ausgegeben. Wird ein Knoten abschließend untersucht, werden seine Nachfolgeknoten in die Open List eingefügt und der betreffende Knoten wird auf die Closed List gesetzt. Ist ein Nachfolgeknoten bereits auf der Closed List, verbleibt er dort. Ist ein Nachfolgeknoten bereits auf der Open List, werden lediglich ggf. sein f-Wert und der Vorgängerzeiger aktualisiert. Voraussetzung: Der neue Weg ist kürzer als bisher.

Ein Beispiel zur Pfadsuche mit A*

Gesucht wird der kürzeste Weg zwischen dem Startknoten A und dem Zielknoten H. Die Entfernungen zwischen den Knoten sind gegeben. Weiterhin ist innerhalb des Knotens die geschätzte Entfernung zum Ziel angegeben. Der Ablauf des Algorithmus ist in Abbildung 4 dargestellt: beginnend mit der Ausgangssituation (Abb. 4a), d. h. Orte und Entfernungen und dem Ergebnis (Abb. 4g), d. h. dem gefundenen kürzesten Pfad. Zur Erläuterung:

  • Rote Knoten: Noch nicht bekannte Knoten, d. h. untersuchte Wege zu diesen Standorten.

  • Blaue Knoten: Bekannte Knoten, die sich auf der Open List befinden.

  • Grüne Knoten: Bekannte und abschließend untersuchte Knoten, die sich auf der Closed List befinden.

Die Suche nach dem kürzesten Weg läuft wie folgt ab:

  • Abbildung 4b: Es beginnt beim Startknoten A. Dieser wird auf die Closed List gesetzt. Die Nachfolgeknoten sind B und C. Innerhalb der Knoten wird der F-Wert (F = G + H) notiert. Für den Knoten B ergibt das:
    F(B) = G(A) + G(A-B) + H(B) F(B) = 0 + 164 + 385 = 549
    Der F-Wert des Knotens B wird innerhalb von B notiert. Für den Knoten C ergibt sich:
    F(C) = G(A) + G(A-C) + H(C) F(C) = 0 + 260 + 355 = 615
    Die Knoten B und C werden in die Open List eingetragen. Der Weg über B ist schätzungsweise 549, der über C 615 Einheiten lang. Knoten A wird als Vorgänger der Knoten B und C notiert.

  • Abbildung 4c: Da Knoten B einen geringeren F-Wert aufweist, wird er als nächster untersucht. Nachfolger sind die Knoten E und F. Die Berechnungen der F-Werte ergeben:
    F(E) = 164 + 275 + 255 = 694
    F(F) = 164 + 309 + 150 = 623

    Knoten B wird als Vorgängerknoten gespeichert und auf die Closed List gesetzt.

  • Abbildung 4d: Knoten C weist (im Vergleich zu E und F) den geringsten F-Wert auf und wird als Nächstes untersucht. Nachfolger ist Knoten D. Für D ergibt sich:
    F(D) = 260 + 141 + 325 = 726
    D wird der Open List, C der Closed List hinzugefügt.

  • Abbildung 4e: Die Suche geht mit Knoten F weiter, da er den geringsten F-Wert (gegenüber D und E) hat. Nachfolgeknoten ist Knoten H (der Zielknoten). Um Knoten H über diesen Weg zu erreichen, beträgt die Gesamtstrecke: F(H) = 164 + 309 + 169 = 642. Knoten H ist zwar das Ziel, dennoch steht zum aktuellen Zeitpunkt noch nicht fest, dass dies schon der kürzeste Weg ist. Knoten F wird auf die Closed List gesetzt; Knoten H auf die Open List.

  • Abbildung 4f: Im nächsten Schritt wird Knoten E untersucht. Die Wegstrecke: A – B – E – H beträgt schätzungsweise F(E) = 164 + 275 + 255 = 694 und ist damit auf jeden Fall länger als der schon ermittelte tatsächliche Weg über F mit einem Wert von 642. Damit scheidet Knoten E aus und wird auf die Closed List gesetzt. Die tatsächliche Lösung über E muss also nicht berechnet werden. Nun befinden sich noch die Knoten H und D in der Open List. Knoten H hat einen F-Wert von 642 und Knoten D einen F-Wert von 726. H wird damit im nächsten Schritt betrachtet und auf die Closed List gesetzt. H ist auch der Zielknoten, und damit ist der Suchvorgang abgeschlossen. Die weiteren Knoten der Open List und die noch nicht untersuchten Knoten müssen nicht mehr betrachtet werden.

  • Abbildung 4g: Als kürzester Weg ergibt sich die Knotenfolge A – B – F – H. Diese hat eine Länge von 842 Einheiten.

Es wird deutlich, dass nicht alle möglichen Verbindungen betrachtet werden, d. h. sobald klar ist, dass eine mögliche Verbindung auf jeden Fall länger ist, kann sie von der weiteren Suche ausgenommen werden.

Abb. 4: Fallbeispiele für den A*-Algorithmus

Abb. 4: Fallbeispiele für den A*-Algorithmus

Evolutionäre Strategien und genetische Algorithmen

Diese Klasse von Verfahrensansätzen wird aus den natürlichen Prozessen der Natur abgeleitet. Grundgedanke ist die Nachbildung der natürlichen Evolution mit den Prozessen Weiterentwicklung, Verbesserung und Eliminierung. Die Konzeption der genetischen Algorithmen geht auf Holland und Goldberg zurück [3], [4]. Genetische Algorithmen werden zur Steuerung von Nachbarschaftssucheverfahren und Konstruktionsheuristiken eingesetzt. Konstruktionsheuristiken dienen dazu, eine erste zulässige Lösung zu erzeugen, die dann für eine spätere Verbesserung zur Verfügung steht. Nachbarschaftssucheverfahren durchsuchen den Lösungsraum nach verbesserten Ergebnissen. Für die Anwendung wird zunächst eine Ausgangspopulation, d. h. eine Menge von zulässigen, aber verbesserungsbedürftigen Lösungen benötigt. Diese können z. B. mit Hilfe einer problemspezifischen Heuristik erzeugt werden. Die Individuen der Ausgangspopulation (Elterngeneration) werden durch eine Fitnessfunktion bewertet, die sich im Regelfall aus der Zielfunktion des Optimierungsproblems ableitet und den Grad der Erreichung des Ziels angibt. Die Elterngeneration dient der Erzeugung von Nachkommen mit Hilfe der Operatoren Selektion, Rekombination und Mutation. Auf die erzeugten Nachkommen wird ebenfalls die Fitnessfunktion angewandt. Die Güte einer Lösung ist auch ausschlaggebend für den Einfluss der erzeugten Lösung auf den nachfolgenden Reproduktionsprozess. Ziel ist es, nach Möglichkeit erwünschte Eigenschaften zu vererben und nicht erwünschte Eigenschaften frühzeitig auszusortieren. Selektion, Reproduktion und Bewertung werden so lange wiederholt, bis ein Abbruchkriterium erreicht ist. Das kann zum Beispiel eine bestimmte Anzahl von Iterationen, eine maximale Rechenzeit oder ein bestimmtes Niveau des Zielfunktionswerts sein (Abb. 5).

Abb. 5: Arbeitsweise des genetischen Algorithmus [5]

Abb. 5: Arbeitsweise des genetischen Algorithmus [5]

Genetische Algorithmen arbeiten mit codierten Lösungen, die als Chromosomen bezeichnet werden. Die Suche erfolgt durch eine wiederholte Anwendung von Operationen auf die codierten Lösungen. Ein wichtiger Operator ist der so genannte Crossover-Operator, der durch Austausch codierter Lösungsbestandteile zwischen zwei Lösungen eine neue Lösung erzeugt. Die Wahrscheinlichkeit, dass eine erzeugte Lösung im weiteren Reproduktionsprozess verwendet wird, steigt mit der individuellen Fitness dieser Lösung.

Das Konzept der evolutionären Strategien wurde von Reichenberg und Schwefel entwickelt [6], [7]. Auch hier wird mit Populationen von Lösungen gearbeitet. Dabei erfolgt keine Codierung der Lösungen. In einer ersten Initialisierungsphase wird eine Elterngeneration mit einer bestimmten Zahl μ von Individuen erzeugt. Es schließt sich der eigentliche Reproduktions- und Selektionsprozess an, der wiederholt ausgeführt wird und sich in mehrere Schritte gliedert: In einem ersten Schritt erfolgt die Auswahl der Eltern aus der Ausgangspopulation, aus der die Nachkommen gebildet werden. Das geschieht stochastisch mit der gleichen Wahrscheinlichkeit für alle Individuen. Ist eine Rekombination vorgesehen, wird sie auf die ausgewählten Lösungen angewendet. Im nächsten Schritt wird auf die entstandenen Lösungen ein Mutationsoperator angewendet. Dabei handelt es sich um eine zufällige und geringfügige Veränderung. Der Umfang der Mutation wird durch die Mutationsschrittweite bestimmt, die selbst einer dynamischen Anpassung während des Suchprozesses unterliegen sollte (Selbstadaption). Die durch die Mutation erzeugten Nachkommen werden mit Hilfe der Fitnessfunktion bewertet und einer vorläufigen Zwischenpopulation zugeordnet. Der Vorgang aus Auswahl, Rekombination und Mutation wird so lange wiederholt, bis die Zwischenpopulation λ Nachkommen enthält. Der folgende Selektionsprozess wählt aus diesen λ Nachkommen wieder eine Zahl von μ Individuen für die Erzeugung der nächsten Generation aus. Die gewählte Selektionsstrategie legt fest, welche Lösungen die nächste Elternpopulation bilden. Eine typische Vorgehensweise ist die (μ, λ)-Strategie. Hier werden λ (mit λ ≥ μ) Kinder erzeugt, die die Elternpopulation vollständig ersetzen. Sicherzustellen ist, dass die bisher beste bekannte Lösung (mit dem höchsten Fitnesswert) separat gespeichert wird. Damit soll vermieden werden, dass diese durch das teilweise zufallsbasierte Selektionsverfahren verloren geht.

Ameisenalgorithmus

Beim Ameisenalgorithmus handelt es sich um ein Verfahren aus dem Jahr 1991, das von Dorigo u. a. vorgestellt wurde [8]. Das Verfahren bildet das natürliche Verhalten von Ameisen bei der Futtersuche nach (Abb. 6).

Abb. 6: Prinzip des Ameisenalgorithmus

Abb. 6: Prinzip des Ameisenalgorithmus

Um potenzielle Futterstellen zu finden, suchen die Ameisen ihre Nachbarschaft ab. Auf dem Weg vom Nest zur Futterstelle hinterlässt jede Ameise eine Duftspur (Pheromonspur). Diese Pheromonspur kann von der Ameise selbst auf dem Rückweg, aber auch von anderen Ameisen erkannt werden. Gibt es mehrere mögliche Wege zwischen Nest und Futterstelle, wird mit der Zeit auf dem kürzesten Weg eine höhere Konzentration des Duftstoffs vorliegen, sodass die Ameisen bevorzugt diesen Weg wählen. Im Kontext der Tourenplanung lässt sich die Nachbarschaft, durch die sich die künstlichen Ameisen bewegen, als Graph bezeichnen. Die Punkte sind dabei die Knoten und die Verbindungen die Kanten eines gegebenen Tourenplanungsproblems. Damit die Ameisen den Weg zum Ziel finden, müssen sie bei jeder Iteration einen Schritt innerhalb ihrer unmittelbaren Nachbarschaft durchführen. Am Anfang wird auf allen Kanten die identische Menge Pheromon platziert. Die Entscheidung über alternative Wege wird anhand der Pheromonmenge getroffen. Ist eine Ameise am nächsten Knoten angekommen, wird die Pheromonmenge der zuletzt zurückgelegten Strecke erhöht. Dabei steigt auf Wegen mit einer kürzeren Strecke die Pheromonkonzentration schneller. Dieser Prozess wird so lange wiederholt, bis eine künstliche Ameise den Zielort gefunden hat und wieder zum Ausgangsort zurückgekehrt ist. Zur Vermeidung lokaler Optima wird mit Hilfe einer sogenannten Verdunstungsfunktion die Pheromonmenge bei jeder Iteration um eine vorgegebene Menge reduziert.

Simulated Annealing

Simulated Annealing (SA) ist eine Metaheuristik, die zur Steuerung der Nachbarschaftssuche eingesetzt wird und von Kirkpatrick u. a. entwickelt wurde [9]. Es handelt sich um ein stochastisches Verfahren, dessen Ursprung in der Thermodynamik liegt. Simuliert wird das energetische Verhalten von Teilchen bei einer gegebenen Temperatur. SA bezeichnet den Erstarrungsvorgang eines aufgeheizten Körpers in einem Molekülgitter. Die Idee besteht darin, einen solchen Kühlungsprozess zu simulieren. Das Prinzip wird in der Metaheuristik SA zur Lösung kombinatorischer Optimierungsprobleme verwendet. SA steuert eine Nachbarschaftssuche nach dem folgenden Muster: Ausgehend von einer zulässigen Lösung x wird eine weitere zulässige Lösung x‘ in der Nachbarschaft von x ausgewählt. Besitzt x‘ einen besseren Zielfunktionswert als x, wird im nächsten Schritt die Suche mit x‘ fortgesetzt. Besitzt x‘ jedoch einen schlechteren Zielfunktionswert, wird x‘ nicht unter allen Umständen abgelehnt. Ob die schlechtere Lösung akzeptiert wird, hängt vom Ausmaß der Verschlechterung und einem weiteren Parameter, der in Anlehnung an die Herkunft des Verfahrens mit Temperatur bezeichnet wird, ab. Die Berechnung der Akzeptanzwahrscheinlichkeit p erfolgt unter Anwendung der Gleichung p = e^ ( ∆ f / T). Dabei ist ∆f die Änderung des Zielfunktionswerts und T die aktuelle Temperatur. T dient somit als Steuerungsparameter der Akzeptanzwahrscheinlichkeit. Der Ausgangswert wird am Anfang des Verfahrens so gewählt, dass durchaus auch Verschlechterungen des Zielfunktionswerts der neuen Lösung x‘ gegenüber der bisher besten Lösung x als zulässig erachtet werden. Im Laufe des Verfahrens wird die Temperatur nach einem vorher festzulegenden Abkühlungsplan sukzessive reduziert. Damit sinkt die Wahrscheinlichkeit im Laufe des Verfahrens, dass Verschlechterungen in den Lösungen akzeptiert werden. Die Schwierigkeit der Konfiguration des Verfahrens liegt in der Festlegung der Parameter. Die Starttemperatur sollte am Anfang hoch sein, denn nur dann wird ein bestimmtes Ausmaß an „schlechten“ Lösungen akzeptiert, was eine breitere Lösungssuche garantiert. Das wiederum soll verhindern, dass das Verfahren nur auf ein lokales Optimum zusteuert. Zur Berechnung der Starttemperatur wird vorgegeben, mit welcher durchschnittlichen Wahrscheinlichkeit eine Lösung akzeptiert wird, die um einen bestimmten Prozentsatz schlechter ist als die bislang beste Lösung. Das Struktogramm in Abbildung 7 zeigt, in welcher Form ein SA-Algorithmus abläuft.

Abb. 7: Struktogramm für die Metaheuristik Simulated Annealing [10]

Abb. 7: Struktogramm für die Metaheuristik Simulated Annealing [10]

Deutlich wird, dass die Entscheidung über die Akzeptanz einer neuen Lösung sowohl von deren Güte als auch von einem sich anpassenden Zufallsfaktor abhängt. Als Nachteil des SA wird der hohe Rechenaufwand des Verfahrens genannt, der hauptsächlich durch die Exponentialfunktion hervorgerufen wird. Diese Aussage muss differenziert betrachtet werden: Zum einem sind natürlich Rechenoperationen unter Einbeziehung von Exponentialfunktionen deutlich aufwendiger, als wenn nur die elementaren Grundrechenarten zur Anwendung gelangen. Dies gilt insbesondere dann, wenn für die Ausführung einer Lösungssuche und Lösungsverbesserung der Algorithmus vielfach durchlaufen wird. Anfänglich sehr marginal erscheinende Zeitdifferenzen können sich dann sehr schnell zu messbaren Verzögerungen summieren. Anderseits muss man sagen, dass selbst komplexe Berechnungen durch die heutigen Prozessoren schnell ausgeführt werden.

Es existieren verschiedene Varianten des SA-Verfahrens. Zwei bekannte Verfahren sind das Threshold-Accepting-Verfahren und die Sintflutstrategie. Die Sintflutstrategie kann für Maximierungsprobleme, zum Beispiel die Suche nach einem größtmöglichen Wert, leicht erläutert werden: Bei dieser Metaheuristik werden Lösungen akzeptiert, solange der Zielfunktionswert den aktuell gültigen Akzeptanzwert nicht unterschreitet. Dieser Akzeptanzwert steigt – bildlich wie der Wasserspiegel einer Sintflut – bis zum Abbruch des Verfahrens. Das Threshold-Accepting-Verfahren wurde 1990 von Dueck und Scheuer entwickelt [11]. Akzeptiert werden neue Lösungen, deren Zielfunktionswert entweder besser ist oder bei denen die Verschlechterung eine vorgegebene Akzeptanzschwelle (Threshold) nicht überschreitet. Die Akzeptanzschwelle wird im Laufe des Suchprozesses gesenkt. Erfolgskritisch sind die Festlegung des Ausgangsschwellenwerts und der Prozess des Absenkens des Schwellenwerts. In Abbildung 8 ist die grundsätzliche Arbeitsweise grafisch – ebenfalls in Form eines Struktogramms – wiedergegeben. Deutlich wird hier gegenüber dem SA-Algorithmus der Verzicht auf die Verwendung der Exponentialfunktion. Die Änderung wurde farblich hervorgehoben.

Abb. 8: Struktogramm für die Metaheuristik Threshold Accepting [10]

Abb. 8: Struktogramm für die Metaheuristik Threshold Accepting [10]

Bibliotheken für Java

Um Algorithmen wie A* oder Metaheuristiken in der Praxis einzusetzen, ist eine Eigenentwicklung möglich, doch man kann auch erst einmal nach existierenden Bibliotheken Ausschau halten.

  • JGAP (Java Genetic Algorithms Package) [12] ist ein Open Source Framework, das kostenfrei für private Projekte erhältlich ist.

  • A-Star-Shortest-Pathfinding-Algorithm-Square-Grid in Java [13] ist eine Java-basierte Lösung, um den kürzesten Weg zwischen zwei Gitterzellen zu ermitteln. Die Koordinaten des Grid (x, y) kennzeichnen dabei also die Orte, die den möglichen Weg vom Start zum Ziel beschreiben. Ein solches System könnte man zum Beispiel bei einem Computerspiel anwenden. Die virtuelle Karte mit den Orten bezeichnet man dann als Tile Map.

  • Simulated Annealing in Java [14]: Hier ist die Implementierung des SA-Algorithmus für ein Tourenplanungsproblem beschrieben. Eine Übertragung auf andere Probleme ist denkbar.

Beim Einsatz einer Bibliothek muss man beachten, dass die Algorithmen dokumentiert sind, und prüfen, in welchem Umfang sich die Verfahren über Parameter konfigurieren lassen.

Ausblick und Fazit

Umfassende Hintergrundkenntnisse sind notwendig, um Metaheuristiken zur Lösung von komplexen Problemen einzusetzen. Man darf dabei nicht vergessen, dass diese Algorithmen zur Steuerung von problemspezifischen Algorithmen eingesetzt werden, damit diese zielgerichtet gesteuert werden. Die konkrete Umsetzung in Java (selbst implementiert, Bibliotheken und Konfiguration) ist Gegenstand des kommenden Artikels dieser Serie.

Weitere Informationen zu diesen und anderen Themen der IT finden Sie unter http://larinet.com.

Links & Literatur

[1] https://www.spieleprogrammierer.de/wiki/Wegfindung_mit_A*[2] https://www.enzyklopaedie-der-wirtschaftsinformatik.de/lexikon/technologien-methoden/Informatik–Grundlagen/Graphentheorie/

[3] Holland, John Henry: „Adaptation in Natural and Artificial Systems. An Introductory Analysis with Applications to Biology, Control, and Artificial Intelligence“, The MIT Press, 1975

[4] Goldberg, David Edward: „Genetic Algorithms in Search, Optimization, and Machine Learning“, Addison-Wesley, 1989

[5] http://emergenz.hpfsc.de/html/node33.html

[6] Rechenberg, Ingo: „Evolutionsstrategie. Optimierung technischer Systeme nach Prinzipien der biologischen Evolution“, Fromman-Holzboog Verlag, 1973

[7] Schwefel, Hans-Paul: „Evolution and Optimum Seeking“, Wiley, 1995

[8] Doriigo, Marco; Maniezzo, Vittorio; Colorni, Alberto: „Ant System. An autocatalytic optimizing process, working paper No. 91-016 Revised“, IEEE, 1996

[9] Kirkpatrick, Scott; Gelatt Jr, C. D.; Vecchi, Mario P.: „Optimization by Simulated Annealing“, in: Science, Vol. 220, Issue 4598, 1983

[10] http://www.hs-augsburg.de/informatik/projekte/mebib/emiel/entw_inf/or_verf/2d_vis.html

[11] Dueck, Gunter; Scheuer, Tobias: „Threshold Accepting: a general purpose optimization algorithm appearing superior to simulated annealing“, in: Journal of Computational Physics, 90(1), 1990

[12] https://sourceforge.net/projects/jgap/files/

[13] https://github.com/Suwadith/A-Star-Shortest-Pathfinding-Algorithm-Square-Grid-Java/blob/FinalizedVersion/src/PathFindingOnSquaredGrid.java

[14] https://stackabuse.com/simulated-annealing-optimization-algorithm-in-java/

 

Verwandte Themen:

Geschrieben von
Olena Bochkor
Olena Bochkor
Olena Bochkor studierte Betriebswirtschaftslehre u. a. mit dem Schwerpunkt Wirtschaftsinformatik. Weitere Informationen zu diesen und anderen Themen der IT finden Sie unter http://it-fachartikel.de.
Dr. Veikko Krypczyk
Dr. Veikko Krypczyk
Dr. Veikko Krypczyk studierte und promovierte in Betriebswirtschaftslehre mit dem Schwerpunkt Wirtschaftsinformatik. Er ist Entwickler und Fachautor. Aktuell beschäftigt er sich mit der App-Programmierung für Windows Phone und Android.
Kommentare

Hinterlasse einen Kommentar

avatar
4000
  Subscribe  
Benachrichtige mich zu: