Naturanaloge Optimierungsverfahren

Naturanaloge Optimierungsverfahren sind Metaheuristiken, deren grundsätzliche Funktionsweise von biologischen oder physikalischen Vorbildern inspiriert ist.

Beteilige dich an der Diskussion!

Dieser Artikel wurde wegen inhaltlicher Mängel auf der Qualitätssicherungsseite der Redaktion Informatik eingetragen. Dies geschieht, um die Qualität der Artikel aus dem Themengebiet Informatik auf ein akzeptables Niveau zu bringen. Hilf mit, die inhaltlichen Mängel dieses Artikels zu beseitigen, und beteilige dich an der Diskussion! (+) Begründung: Es fehlen Klarheit und Struktur -Schwatzwutz !?! 14:35, 6. Aug. 2013 (CEST)

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

→ Hauptartikel: Evolutionärer Algorithmus

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:

• Genetische Programmierung
• Genetische Algorithmen
• Evolutionsstrategien
• Evolutionäre Programmierung

Schwarmintelligente Algorithmen

→ Hauptartikel: Kollektive Intelligenz

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:

• Partikelschwarmoptimierung
• Ameisenalgorithmus

Simulierte Abkühlung

→ Hauptartikel: Simulated Annealing

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

• Oliver Wendt: Tourenplanung durch Einsatz naturanaloger Verfahren. DeutscherUniversitätsVerlag, 1995, ISBN 3-8244-6181-1.