Naturanaloge Optimierungsverfahren
Unterklasse von Metaheuristiken
From Wikipedia, the free encyclopedia
In der Informatik versteht man unter naturanalogen Optimierungsverfahren Metaheuristiken, deren grundsätzliche Funktionsweise von biologischen oder physikalischen Vorbildern inspiriert ist.[1.1][2.1][3.1] Ihr Einsatzgebiet ist durch Aufgabenstellungen gekennzeichnet, für die keine exakten Lösungsverfahren bekannt sind oder deren Anwendung zu einem nicht vertretbaren Aufwand führen würde. Die Verfahren können nicht garantieren, das Optimum zu finden, liefern aber bei Erfolg eine hinreichend gute Lösung, was in der Praxis vor allem bei NP-vollständigen Problemen bereits als wünschenswertes Ergebnis betrachtet werden kann.[2.1][2.2][3.2] Zu den Anwendungsgebieten gehören unter anderem viele kombinatorische Aufgaben wie die Anordnungsplanung, die Tourenplanung oder Schedulingaufgaben wie z. B. Produktionsplanung, Fahrplanerstellung oder Reihenfolgeplanung.[1.1][1.2][2.3][2.4] Weitere Anwendungsfelder sind Aufgabenstellungen aus den Bereichen Designoptimierung, Energie- und Ressourceneffizienz, Routing, Clustering, Partitioning oder Finanzportfolio-Optimierung.[2.4][4.1]
Es gibt große Überschneidungen zwischen den naturanalogen Optimierungsverfahren einerseits und den Methoden der Computational Intelligence (CI) und des Soft Computing andererseits. Zu den Verfahren, die allen drei Gebieten zugerechnet werden können, zählen
- die evolutionären Algorithmen, die grundlegende Aspekte der Informationsverarbeitung der biologische Evolution nachahmen,[1.1][2.1][3.1][5.1]
- die Partikelschwarmoptimierung, die das kollektiven Verhalten dezentralisierter und selbstorganisierender Elemente wie bei Vogel- oder Fischschwärmen zum Vorbild haben,[2.1][3.1][5.2]
- die Ameisen- oder Bienenalgorithmen, deren kooperatives Verhalten bei der Nahrungssuche imitiert wird,[2.1][3.1][5.3] oder
- künstliche Immunsysteme, die von der Funktionsweise des biologischen Immunsystems inspiriert sind und im Gegensatz zu etlichen anderen metaheuristischen Optimierungsmethoden lokale Extremstellen des Suchraums bewahren.[2.5][5.4][6.1]
Zu den naturanalogen Optimierungsverfahren, welche durch thermodynamische Prozesse motiviert sind, zählen[1.3][2.6][7.1]
- der Metropolis-Algorithmus, welcher auf der Boltzmann-Verteilung der Thermodynamik beruht,
- die daraus abgeleitete simulierte Abkühlung (engl. simulated annealing), die das Verhalten von Atomen bei Abkühlungsprozessen zum Vorbild hat,
- die Threshold-Accepting-Methode, der eine Abwandlung der simulierten Abkühlung darstellt oder
- der Sintflutalgorithmus, der ebenfalls als eine Variante der simulierten Abkühlung angesehen werden kann.
Außerdem gibt es zahlreiche hybride Systeme, bei denen mehrere naturanaloge Verfahren so kombiniert werden, dass sie sich ergänzen.[4.2][6.2][7][8]
Die Vorteile vieler naturanaloger Optimierungsverfahren bestehen vor allem darin, dass sie
- auch bei nichtlinearen, nicht differenzierbaren oder diskreten Problemen eingesetzt werden können,[3.2][9.1]
- kein oder nur wenig Vorwissen über das Problem benötigen[9.1] oder
- auch bei NP-Problemen anwendbar sind[3.3][9.2][10.1] und
- dass sie gut parallelisierbar sind,[10.2][11.1] was moderne Rechnerressourcen effektiv nutzt.
Nachteilig ist, dass die meisten Verfahren relativ lange Rechenzeiten benötigen und keine Optimalität der Lösung garantieren können.
Kritik
In letzter Zeit konnte eine sehr große Zunahme an naturinspirierten Metaheuristiken beobachtet werden, die häufig die Partner- oder Futtersuche von einer Vielzahl von Arten zum Vorbild haben.[6.3] Dies hat zu Kritik in der Forschungsgemeinschaft geführt, da es vielen diesbezüglichen Publikationen an wissenschaftlicher Tiefe, Neuheit oder dem Nachweis der Tauglichkeit oder Überlegenheit über ältere und erprobte Verfahren mangelt.[12][13][14][15] Als Konsequenz wurden die Veröffentlichungsrichtlinien von etlichen Fachzeitschriften entsprechend angepasst.[16][17][18]