© GreenFlash/Shutterstock.com
Teil 3: Metaheuristiken zur Lösung komplexer Probleme

Algorithmen in der Java-Praxis


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.

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

krypczyk_bochkor_algorithmen_1.tif_fmt1.jpgAbb. 1: Systematisierung von Lösungsverfahren für Optimierungsprobleme

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

Exklusives Abo-Special

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