© Excellent backgrounds/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?

Algorithmen – State of the Art und Praxis mit Java

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: Optimierungsverfahren und Metaheuristiken in Java

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

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...

Neugierig geworden?

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