© GreenFlash/Shutterstock.com
Teil 4: Optimierungsverfahren und Metaheuristiken in Java

Algorithmen in der Java-Praxis


Die Theorie zu den Optimierungsverfahren und Metaheuristiken haben wir im letzten Teil der Serie thematisiert. In diesem Artikel sehen wir uns die Praxis an. Wie kann man das A*-Verfahren oder Simulated Annealing in der Praxis programmieren?

Im letzten Teil der Artikelserie haben wir uns die theoretischen Grundlagen von Optimierungsverfahren und Metaheuristiken angesehen. Diese Verfahren und Algorithmen stellen Lösungsansätze bereit, um komplexe Probleme zu bearbeiten. Grob lassen sie sich in exakte Verfahren, problemspezifische Algorithmen und Metaheuristiken einteilen. Exakte Verfahren ermitteln die beste Lösung – ein Beispiel ist der A*-Algorithmus – für die Suche nach einem Pfad vom Start- zum Zielpunkt in einer Matrix, wie er u. a. in Computerspielen angewendet wird. Problemspezifische Algorithmen sind auf die Lösung eines Problems zugeschnitten. Aufgrund der Komplexität einiger Probleme sind derartige Verfahren jedoch nicht in der Lage, das Auffinden einer optimalen Lösung zu garantieren. Den gesamten Lösungsraum zu durchsuchen, ist einfach zu aufwendig und kann in Bezug auf die verfügbare Zeit nicht geleistet werden. An dieser Stelle kommen die Metaheuristiken zum Einsatz, die die Suche gewissermaßen von übergeordneter Position aus steuern. Sie versuchen, die problemspezifischen Algorithmen durch den Lösungsraum zu navigieren und suchen nach einer möglichst guten Lösung, sie können nicht das Auffinden der besten Lösung garantieren. Ein Ziel ist es, das sogenannte Festlaufen in lokalen Optima zu verhindern. Metaheuristiken orientieren sich an Ansätzen aus der Natur, zum Beispiel der Physik (Simulated Annealing), Biologie (Ameisenalgorithmus, Genetische Algorithmen) usw.

In diesem Artikel zeigen wir anhand von konkreten Beispielen die Implementierung derartiger Algorithmen in Java. Die Lösungen kann man auf eigene Probleme übertragen und anpassen. Zunächst wollen wir jedoch zwei interessante Metaheuristiken vorstellen: Tabu Search und Guided Local Search.

Tabu Search

Tabu Search ist eine Metaheuristik zur Steuerung einer Nachbarschaftssuche. Das Verfahren geht auf Glover [1] zurück und ist in verschiedene Richtungen modifiziert worden. Es ist ein adaptives Verfahren mit der Möglichkeit, andere Heuristiken einzubinden. Ausgangspunkt ist eine zulässige Startlösung x. In jeder Iteration wird die Nachbarschaft NB der Lösung nach Verbesserungsmöglichkeiten durchsucht. Dazu wird aus den gefundenen Lösungen eine Lösung für den weiteren Suchprozess ausgewählt. Unter einem Zug z versteht man die Veränderung einer Lösung x zu einer Nachbarschaftslösung x’. Ein Zug z heißt komplementärer Zug, wenn er die Wirkung von z unmittelbar rückgängig macht. Die Grundform des Tabu-Search-Verfahrens verwendet die Best Acceptance Strategy, die besagt, dass diejenige Lösung aus der Menge der Nachbarschaftslösungen ausgewählt wird, die den besten Zielfunktionswert aufweist. Zur Vermeidung von Zyklen wird die Menge der Nachbarschaftslösungen auf diejenigen beschränkt, die eine bestimmte Zeitlang nicht ausgewählt wurden. Um besuchte Lösungen zu identifizieren, werden sie tabu gesetzt, d. h. auf einer Tabuliste notiert. Jedes Tabu ist in seiner Gültigkeit zeitlich begrenzt, die Dauer wird durch die Länge der Tabuliste und das Tabulistenmanagement bestimmt. Statt Lösungen tabu zu setzen, kann man alternativ auch den komplementären Zug verbieten. Ein Tabu kann unter bestimmten Bedingungen, sogenannten Aspirationskriterien, durchbrochen werden. Das können die folgenden sein:

  • Aspiration by Objective: Das gängigste Aspirationskriterium hebt den Tabustatus eines Schritts auf, falls dieser zu einer neuen besten Lösung führt.

  • Aspiration by default: Wenn sonst kein Schritt mehr ausgeführt werden kann.

  • Aspiration by influence: Um Schritte von geringem Einfluss zu ermöglichen.

Die fortlaufende Bewertung aller Nachbarlösungen in jeder Iteration der Suche erfordert viel Rechenzeitaufwand. Alternativ kann auch nur eine Auswahl von Lösungen betrachtet und bewertet werden (Kandidatenmenge). Beispielsweise kann eine Kandidatenmenge durch zufällige Auswahl der Lösungen erfolgen. Das hat den Vorteil, dass die Gefahr eines zyklischen Suchverlaufs verringert wird, was wiederum kürzere Tabulisten bzw. Tabudauern ermöglicht. Andererseits besteht die Gefahr, gute Lösungen zu übersehen. Das Prinzip der Metaheuristik Tabu Search finden Sie als Ablaufschema in Abbildung 1. Dieses Verfahren wurde u. a. erfolg...

Neugierig geworden? Wir haben diese Angebote für dich:

Angebote für Teams

Für Firmen haben wir individuelle Teamlizenzen. Wir erstellen Ihnen gerne ein passendes Angebot.

Das Library-Modell:
IP-Zugang

Das Company-Modell:
Domain-Zugang