Naturanaloge Optimierungsverfahren

In der Informatik versteht man unter naturanalogen Optimierungsverfahren Metaheuristiken, deren grundsätzliche Funktionsweise von biologischen oder physikalischen Vorbildern inspiriert ist. 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. Zu den Anwendungsgebieten gehören unter anderem viele kombinatorische Aufgaben wie die Anordnungsplanung, die Tourenplanung oder Schedulingaufgaben wie z. B. Produktionsplanung, Fahrplanerstellung oder Reihenfolgeplanung. Weitere Anwendungsfelder sind Aufgabenstellungen aus den Bereichen Designoptimierung, Energie- und Ressourceneffizienz, Routing, Clustering, Partitioning oder Finanzportfolio-Optimierung.

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,
• die Partikelschwarmoptimierung, die das kollektiven Verhalten dezentralisierter und selbstorganisierender Elemente wie bei Vogel- oder Fischschwärmen zum Vorbild haben,
• die Ameisen- oder Bienenalgorithmen, deren kooperatives Verhalten bei der Nahrungssuche imitiert wird, 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.

Zu den naturanalogen Optimierungsverfahren, welche durch thermodynamische Prozesse motiviert sind, zählen

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

Die Vorteile vieler naturanaloger Optimierungsverfahren bestehen vor allem darin, dass sie

• auch bei nichtlinearen, nicht differenzierbaren oder diskreten Problemen eingesetzt werden können,
• kein oder nur wenig Vorwissen über das Problem benötigen oder
• auch bei NP-Problemen anwendbar sind und
• dass sie gut parallelisierbar sind, 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.

1. Martin Feldmann: Naturanaloge Verfahren. Deutscher Universitätsverlag, Wiesbaden 1999, ISBN 3-8244-6890-5, doi:10.1007/978-3-322-95217-2. 
   1. 1 2 3 Geleitwort, S. V-VI
   2. ↑ Naturanaloge Verfahren zur Lösung des Open Shop Problems, S.281-322
   3. ↑ Naturanaloge Verfahren im Überblick, S. 71-78
2. Ralf Hollstein: Optimierungsmethoden: Einführung in die klassischen, naturanalogen und neuronalen Optimierungen. Springer Fachmedien Wiesbaden, Wiesbaden 2023, ISBN 978-3-658-39854-5, doi:10.1007/978-3-658-39855-2. 
   1. 1 2 3 4 5 Vorwort, S. VII-IX
   2. ↑ Komplexität und heuristische/metaheuristische Verfahren, S. 125-134
   3. ↑ Kombinatorische Optimierungsprobleme, S. 17-50
   4. 1 2 Einführung, S. 3-4
   5. ↑ Künstliche Immunsysteme, S. 253-278
   6. ↑ Physikbasierte Algorithmen, S.137-146
3. Rudolf Kruse, Sanaz Mostaghim, Christian Borgelt, Christian Braune, Matthias Steinbrecher: Computational Intelligence: A Methodological Introduction (= Texts in Computer Science). Springer International Publishing, Cham 2022, ISBN 978-3-03042226-4, doi:10.1007/978-3-030-42227-1. 
   1. 1 2 3 4 S. 229
   2. 1 2 Computational Intelligence, S. 2-3
   3. ↑ The Traveling Salesman Problem, S. 253–256
4. Stephan Olariu, Albert Y. Zomaya (Hrsg.): Handbook of Bioinspired Algorithms and Applications (= CRC Computer and Information Science series. Nr. 7). Chapman & Hall / CRC, Boca Raton 2006, ISBN 1-58488-475-4. 
   1. ↑ Section II: Application Domains, S. 179–649
   2. ↑ A Unified View on Metaheuristics and Their Hybridization, S. 147-156
5. Leandro de Castro: Fundamentals of Natural Computing: An Overview. In: Physics of Life Reviews. Band 4, Nr. 1, März 2007, S. 1–36, doi:10.1016/j.plrev.2006.10.002. 
   1. ↑ Evolutionary computing, S. 7-9
   2. 1 2 Swarm intelligence, S. 9-13
   3. ↑ Artificial immune systems, S.13-16
6. Zoran Jakšić, Swagata Devi, Olga Jakšić, Koushik Guha: A Comprehensive Review of Bio-Inspired Optimization Algorithms Including Applications in Microelectronics and Nanophotonics. In: Biomimetics. Band 8, Nr. 3, 28. Juni 2023, ISSN 2313-7673, S. 278, doi:10.3390/biomimetics8030278, PMID 37504166, PMC 10807478 (freier Volltext). 
   1. ↑ Selected algorithms mimicking human or zoological physiological functions, S. 26-28; Table 11, S. 56
   2. ↑ Hybridization Methods, S. 34-36
7. ↑ Oliver Wendt: Tourenplanung durch Einsatz naturanaloger Verfahren - Integration von Genetischen Algorithmen und Simulated Annealing. Deutscher Universitätsverlag, Wiesbaden 1995, ISBN 3-8244-6181-1, doi:10.1007/978-3-663-09046-5. 
   1. ↑ Simulated Annealing, S. 115-136
8. ↑ Christina Klüver, Jürgen Klüver, Jörn Schmidt: Modeling Complex Processes Through Nature-Analogous Methods: Artificial Intelligence and Artificial Life. Springer Fachmedien Wiesbaden, Wiesbaden 2025, ISBN 978-3-658-46509-4, Hybridizations of the Basic Models, S. 301–342, doi:10.1007/978-3-658-46510-0. 
9. Russell Eberhart, Yuhui Shi: Computational Intelligence. Elsevier, 2007, ISBN 978-1-55860-759-0, doi:10.1016/b978-1-55860-759-0.x5000-8. 
   1. 1 2 S. 93
   2. ↑ S. 393
10. Andries P. Engelbrecht: Computational Intelligence: An Introduction. 2nd ed Auflage. John Wiley & Sons, Chichester, England; Hoboken, NJ 2007, ISBN 978-0-470-03561-0. 
    1. ↑ S. 207
    2. ↑ S. 52, S. 131
11. Nazmul Siddique: Computational Intelligence: Synergies of Fuzzy logic, Neural Networks, and Evolutionary Computing. J. Wiley & Sons, Chichester, U.K 2013, ISBN 978-1-118-53481-6. 
    1. ↑ S. 5