Diskussion zum Artikel "Algorithmen zur Optimierung mit Populationen: der Algorithmus Simulated Annealing (SA). Teil I"
Sie verpassen Handelsmöglichkeiten:
- Freie Handelsapplikationen
- Über 8.000 Signale zum Kopieren
- Wirtschaftsnachrichten für die Lage an den Finanzmärkte
Registrierung
Einloggen
Sie stimmen der Website-Richtlinie und den Nutzungsbedingungen zu.
Wenn Sie kein Benutzerkonto haben, registrieren Sie sich
Neuer Artikel Algorithmen zur Optimierung mit Populationen: der Algorithmus Simulated Annealing (SA). Teil I :
Der Algorithmus des Simulated Annealing ist eine Metaheuristik, die vom Metallglühprozess inspiriert ist. In diesem Artikel führen wir eine gründliche Analyse des Algorithmus durch und räumen mit einer Reihe von weit verbreiteten Überzeugungen und Mythen rund um diese weithin bekannte Optimierungsmethode auf. Der zweite Teil des Artikels befasst sich mit dem nutzerdefinierten Algorithmus Simulated Isotropic Annealing (SIA).
Der Algorithmus des Simulated Annealing, der simulierten Abkühlung, wurde 1983 von Scott Kirkpatrick, George Gelatt und Mario Vecchi entwickelt. Bei der Untersuchung der Eigenschaften von Flüssigkeiten und Feststoffen bei hohen Temperaturen wurde festgestellt, dass das Metall in einen flüssigen Zustand übergeht und die Teilchen zufällig verteilt sind, während der Zustand mit minimaler Energie unter der Bedingung einer ausreichend hohen Anfangstemperatur und einer ausreichend langen Abkühlzeit erreicht wird. Wenn diese Bedingung nicht erfüllt ist, befindet sich das Material in einem metastabilen Zustand mit nicht minimaler Energie - dies wird als Aushärtung bezeichnet, die in einer starken Abkühlung des Materials besteht. In diesem Fall hat die atomare Struktur keine Symmetrie (anisotroper Zustand oder ungleichmäßige Eigenschaften des Materials innerhalb des Kristallgitters).
Während des langsamen Abkühlens geht das Material ebenfalls in einen festen Zustand über, allerdings mit geordneten Atomen und mit Symmetrie, sodass vorgeschlagen wurde, diesen Prozess zu nutzen, um einen Optimierungsalgorithmus zu entwickeln, der bei komplexen Problemen ein globales Optimum finden kann. Der Algorithmus wurde auch als Methode zur Lösung von kombinatorischen Optimierungsproblemen vorgeschlagen.
Die Grundidee des Algorithmus basiert also auf einem mathematischen Prozessanalogon von glühendem Metall. Während des Abkühlens wird das Metall auf eine hohe Temperatur erhitzt und dann langsam abgekühlt, damit sich die Metallmoleküle bewegen und in stabilere Zustände überführen können, während innere Spannungen im Metall abgebaut und interkristalline Defekte beseitigt werden. Der Begriff „annealing“ (Abkühlen) wird auch mit der thermodynamischen freien Energie in Verbindung gebracht, die eine Eigenschaft des Materials ist und von seinem Zustand abhängt.
Der Optimierungsalgorithmus des simulierten Abkühlens verwendet ein ähnliches Verfahren. Der Algorithmus wendet Vorgänge an, die dem Aufheizen und Abkühlen des Materials ähneln. Der Algorithmus beginnt seine Arbeit mit einer Anfangssituation, die zufällig sein kann oder aus früheren Iterationen stammt. Dann wendet er Operationen an, um den Zustand der Situation zu ändern, die zufällig oder kontrolliert sein können, um einen neuen Zustand zu erhalten, auch wenn dieser schlechter ist als der aktuelle. Die Wahrscheinlichkeit, eine schlechtere Entscheidung zu treffen, wird durch eine „Abkühlungsfunktion“ bestimmt, die die Wahrscheinlichkeit, eine schlechtere Entscheidung zu treffen, im Laufe der Zeit verringert und es dem Algorithmus ermöglicht, vorübergehend aus lokalen Optima „herauszuspringen“ und anderswo im Suchraum nach besseren Lösungen zu suchen.
Autor: Andrey Dik