Naturanaloge Optimierungsverfahren sind Metaheuristiken, deren grundsätzliche Funktionsweise von biologischen oder physikalischen Vorbildern inspiriert ist.
Bei Problemen, zu denen kein Algorithmus bekannt ist, der das globale Optimum in akzeptabler Zeit (oder überhaupt) findet, werden Heuristiken genutzt, um in kürzerer Zeit eine hinreichend gute Lösung zu finden. Typische natürliche Phänomene, die hierzu als Idee herangezogen werden, sind zum Beispiel Evolution, Schwarmintelligenz, Abkühlung und das Immunsystem von Wirbeltieren.
Evolutionäre Algorithmen Bearbeiten
Die Idee zu diesen Algorithmen stammt aus der biologischen Evolution, in deren Rahmen sich Organismen an Umweltbedingungen anpassen; daher werden algorithmische Analoga von Selektion, Mutation und Rekombination zur Lösung komplexer Optimierungsprobleme verwendet.
Zu den Evolutionären Algorithmen zählt man:
Schwarmintelligente Algorithmen Bearbeiten
Motiviert durch das Verhalten von Schwärmen/Völkern aus der Biologie (Vögel- oder Fischschwärme, Bienen- oder Ameisenvölker) wird eine Problemlösung gesucht. Die Fähigkeiten einzelner Schwarmelemente sind sehr begrenzt. Erst das Zusammenwirken vieler Elemente ermöglicht das Finden einer guten Lösung im Problemraum.
Beispiele sind unter anderem:
Simulierte Abkühlung Bearbeiten
Grundidee ist die Nachbildung eines Abkühlungsprozesses, etwa beim Glühen in der Werkstoffkunde. Nach Erhitzen eines Metalls sorgt die langsame Abkühlung dafür, dass die Atome ausreichend Zeit haben, sich zu ordnen und stabile Kristalle zu bilden. Dadurch wird ein energiearmer Zustand, nahe am Optimum erreicht. Auch diese Klasse von Algorithmen wird insbesondere für komplexe, schwer kategorisierbare Optimierungsaufgaben eingesetzt.
Varianten der Grundidee finden sich unter
- Schwellenakzeptanz (threshold accepting)
- Deterministic Annealing
- Sintflutalgorithmus
- Metropolisalgorithmus
Literatur Bearbeiten
- Oliver Wendt: Tourenplanung durch Einsatz naturanaloger Verfahren. DeutscherUniversitätsVerlag, 1995, ISBN 3-8244-6181-1.