Algorithmen zur Optimierung mit Populationen: Der Algorithmus Simulated Isotropic Annealing (SIA). Teil II
141
0
Inhalt
1. Einführung
2. Der Algorithmus
3. Testergebnisse
1. Einführung
Im ersten Teil haben wir die konventionelle Algorithmusversion des Simulated Annealing (SA), des simulierten Abkühlens, besprochen. Der Algorithmus basiert auf drei Hauptkonzepten: Anwendung des Zufallsprinzips, Treffen schlechterer Entscheidungen und schrittweise Verringerung der Wahrscheinlichkeit schlechterer Entscheidungen. Die Anwendung des Zufallsprinzips ermöglicht es, verschiedene Regionen des Suchraums zu erkunden und zu vermeiden, dass man in lokalen Optima stecken bleibt. Die Annahme schlechterer Entscheidungen mit einer gewissen Wahrscheinlichkeit ermöglicht es dem Algorithmus, vorübergehend aus den lokalen Optima herauszuspringen und an anderer Stelle im Suchraum nach besseren Situationen zu suchen, sodass er den Suchraum zunächst umfassender erkunden und sich dann auf die Verbesserung der Situation konzentrieren kann.
Die Idee des SA-Algorithmus basiert auf der Analogie mit glühendem Metall. Das heiße Metall kühlt allmählich ab, was zu einer Veränderung seiner Struktur führt. In ähnlicher Weise beginnt der Algorithmus des simulierten Abkühlens mit einer hohen Temperatur (hohe Wahrscheinlichkeit, eine schlechtere Entscheidung zu treffen) und senkt die Temperatur allmählich (das verringert die Wahrscheinlichkeit, eine schlechtere Entscheidung zu treffen), was dem Algorithmus helfen soll, zur optimalen Situation zu konvergieren.
Der Algorithmus beginnt seine Arbeit mit einer Anfangssituation, die zufällig sein kann oder aus früheren Iterationen stammt. Dann wendet es 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 die Kühlfunktion „cooling“ bestimmt, die die Wahrscheinlichkeit, eine schlechtere Entscheidung zu treffen, mit der Zeit verringert.
Zur Beschreibung des simulierten Abkühlens werden mehrere einfache Gleichungen verwendet. Die Gleichung zur Berechnung der Energieänderung ermöglicht es, die Differenz der Werte der Fitnessfunktion bei zwei aufeinander folgenden Iterationen zu bestimmen. Die Gleichung zur Berechnung der Wahrscheinlichkeit, eine schlechtere Entscheidung zu treffen, bestimmt die Wahrscheinlichkeit, einen neuen Zustand zu akzeptieren, unter Berücksichtigung der Energiedifferenz und der aktuellen Temperatur.
Die wichtigsten Parameter, die bei Verwendung des simulierten Abkühlens angepasst werden müssen, sind die Anfangstemperatur und das Abkühlungsrate. Die Einstellung dieser Parameter kann sich erheblich auf die Leistung und die Qualität der Situation auswirken und ist eine der Schwächen des Algorithmus - die Schwierigkeit bei der Wahl der Parameter aufgrund ihrer nicht offensichtlichen Auswirkungen auf die Leistung. Darüber hinaus beeinflussen sich diese beiden Parameter gegenseitig: Eine Erhöhung der Temperatur kann fast gleichermaßen durch eine Verringerung des Temperaturabsenkungsverhältnisses ersetzt werden.
Im ersten Teil des Artikels haben wir die Hauptprobleme des Algorithmus aufgezeigt:
- Abstimmung der Parameter: Die Parameter des SA-Algorithmus, wie z. B. die Anfangstemperatur und der Abkühlungsrate, können seine Leistung und Effizienz erheblich beeinflussen. Die Einstellung dieser Parameter kann schwierig sein und erfordert Experimente, um optimale Werte zu erzielen.
- Das Problem, in lokalen Extremen stecken zu bleiben: Um dieses Problem zu lösen, können wir verschiedene Strategien anwenden, wie z. B. die Auswahl der am besten geeigneten Verteilung der Zufallsvariablen bei der Generierung neuer Lösungen in Kombination mit den bestehenden Algorithmus-Strategie-Tools sowie die Prüfung möglicher Situationen zur Verbesserung der kombinatorischen Fähigkeiten.
- Verbesserte Konvergenzgeschwindigkeit: Um die Konvergenz zu beschleunigen, können Änderungen an der Kühlfunktion vorgenommen werden, damit die Systemtemperatur schneller gesenkt werden kann (oder mit einer anderen Form der Kühlfunktion). Wir können auch die Methoden zur Auswahl des nächsten Zustands im Algorithmus überarbeiten, die Informationen über zuvor durchlaufene Zustände berücksichtigen.
- Verbesserung der Effizienz des SA-Algorithmus bei einer großen Anzahl von Variablen: Dies ist eines der schwierigsten Probleme für die große Mehrheit der Algorithmen. Mit zunehmender Anzahl von Variablen wächst die Komplexität des Suchraums sehr viel schneller, als dies durch spezielle Methoden in den Suchstrategien berücksichtigt werden kann.
Eines der Hauptprobleme in mehrdimensionalen Räumen ist die kombinatorische Explosion der möglichen Kombinationen von Variablen. Mit zunehmender Anzahl der Variablen steigt die Anzahl der möglichen Systemzustände, die untersucht werden müssen, exponentiell an. Dies führt dazu, dass Optimierungsalgorithmen mit dem Problem der räumlichen Komplexität konfrontiert sind.
Räumliche Komplexität bedeutet, dass die Größe des Suchraums mit der Anzahl der Variablen exponentiell zunimmt. Wenn wir zum Beispiel 10 Variablen haben, von denen jede 10 Werte annehmen kann, dann ist die Gesamtzahl der möglichen Kombinationen gleich 10^10, was 10 Milliarden entspricht, obwohl wir nur 10 Tausend Versuche haben (die Anzahl der Durchläufe der Fitnessfunktion). Unter so vielen Kombinationen die optimale Situation zu finden, ist eine äußerst schwierige Aufgabe. Unabhängig davon ist es erwähnenswert, dass wir in unseren Tests die Funktionsparameter mit einem Schritt von 0 optimieren. Das bedeutet unglaublich schwierige Bedingungen für die Algorithmen. Diejenigen von ihnen, die mit solch komplexen Testproblemen zufriedenstellend zurechtkommen, werden mit ziemlicher Sicherheit auch bei weniger komplexen realen Problemen besser funktionieren (wenn alle anderen Dinge gleich sind).
2. Der Algorithmus
Das simulierte Abkühlen ist so einfach, dass es wirklich schwierig ist, sich vorzustellen, wie er noch verbessert werden könnte. Es ist, als würde man ein Glas Wasser in einen bezaubernden Wein verwandeln — ein Akt der Magie. Denn was könnte denn verbessert werden, wenn die Erzeugung neuer Werte gleichmäßig verteilt ist und die Idee, die schlechteste Entscheidung zu treffen, die übliche Logik der Konstruktion von Optimierungsalgorithmen völlig verletzt?
Werfen wir einen Blick auf den Ausdruck der Ergebnisse aus dem vorherigen Artikel, um die nachfolgenden experimentellen Ergebnisse mit dem ursprünglichen Referenzergebnis des ursprünglichen simulierten Abkühlens (SA) visuell zu vergleichen:
=============================
5 Rastrigin's; Func runs 10000 result: 65.78409729002105
Score: 0.81510
25 Rastrigin's; Func runs 10000 result: 52.25447043222567
Score: 0.64746
500 Rastrigin's; Func runs 10000 result: 40.40159931988021
Score: 0.50060
=============================
5 Forest's; Func runs 10000 result: 0.5814827554067439
Score: 0.32892
25 Forest's; Func runs 10000 result: 0.23156336186841173
Score: 0.13098
500 Forest's; Func runs 10000 result: 0.06760002887601002
Score: 0.03824
=============================
5 Megacity's; Func runs 10000 result: 2.92
Score: 0.24333
25 Megacity's; Func runs 10000 result: 1.256
Score: 0.10467
500 Megacity's; Func runs 10000 result: 0.33840000000000003
Score: 0.02820
=============================
All score: 2.83750
Versuchen wir, die Ergebnisse zu verbessern, indem wir die Gleichverteilung der Zufallsvariablen durch eine Normalverteilung ersetzen, wenn wir neue Zustände des Systems erzeugen.
Wir werden die Klasse für das simulierte Abkühlen als Grundlage für den neuen SIA-Algorithmus verwenden. Daher verzichten wir auf eine Beschreibung der Methoden und Funktionen dieser Klasse, da dies bereits im ersten Teil des Artikels geschehen ist.
Dann können wir die Methode der Funktionsumkehrung verwenden, um eine Zufallszahl mit einer Normalverteilung zu erzeugen. Angenommen, wir wollen eine Zahl „x“ mit einer Normalverteilung, mu (Mittelwert) und sigma (Standardabweichung) erzeugen. Dann können wir die folgende Gleichung verwenden:
x = z0 * sigma + mu
wobei:- z0 - Berechnung nach der Gleichung:
z0 = sqrt (-2 * log (u1)) * cos(2 * Pi * u2)
wobei:-
u1* - Zufallszahl im Bereich (0.0;1.0] (hier ist 'min' nicht im Bereich enthalten)
-
u2** - Zufallszahl im Bereich [0.0;1.0]
- * und ** - beides sind gleichverteilte Zufallszahlen
Im vorigen Artikel haben wir dem SA-Algorithmus einen Parameter für das Diffusionsverhältnis hinzugefügt, der den Bereich der Zufallszahlengenerierung begrenzt. Genau in diesem Bereich sollten wir Zufallszahlen generieren.
Schreiben wir die Methode der Klasse C_AO_SIA, die die Diffusion simuliert: „Diffusion“. Die Methode erzeugt eine Zufallszahl mit einer Normalverteilung von bis zu zwei Standardabweichungen. Werte, die über diese Grenzen hinausgehen, werden „eingewickelt“, ohne dass die Form der Verteilung verloren geht (wir werden uns in einem der folgenden Artikel eingehender damit befassen).
Da wir den Wert der Standardabweichung (sigma) kennen, können wir diesen Wertebereich in den von uns benötigten Bereich zur Simulation der Diffusion übersetzen. Hierfür verwenden wir die Skalierungsfunktion Scale.
//—————————————————————————————————————————————————————————————————————————————— double C_AO_SIA::Diffusion (const double value, const double rMin, const double rMax, const double step) { double logN = 0.0; double u1 = RNDfromCI (0.0, 1.0); double u2 = RNDfromCI (0.0, 1.0); logN = u1 <= 0.0 ? 0.000000000000001 : u1; double z0 = sqrt (-2 * log (logN))* cos (2 * M_PI * u2); double sigma = 2.0;//Sigma > 8.583864105157389 ? 8.583864105157389 : Sigma; if (z0 >= sigma) z0 = RNDfromCI (0.0, sigma); if (z0 <= -sigma) z0 = RNDfromCI (-sigma, 0.0); double dist = d * (rMax - rMin); if (z0 >= 0.0) return Scale (z0, 0.0, sigma, value, value + dist, false); else return Scale (z0, -sigma, 0.0, value - dist, value, false); } //——————————————————————————————————————————————————————————————————————————————
Bei der gleitenden Methode werden wir die Diffusionsmethode wie folgt anwenden:
for (int i = 0; i < popSize; i++) { for (int c = 0; c < coords; c++) { a [i].c [c] = Diffusion (a [i].c [c], rangeMin [c], rangeMax [c], rangeStep [c]); a [i].c [c] = SeInDiSp (a [i].c [c], rangeMin [c], rangeMax [c], rangeStep [c]); } }Nach Durchführung der Tests mit den vorgenommenen Änderungen (Ersetzen der Gleichverteilung durch eine Normalverteilung) haben wir folgende Ergebnisse erhalten:
=============================
5 Rastrigin's; Func runs 10000 result: 60.999013617749895
Score: 0.75581
25 Rastrigin's; Func runs 10000 result: 47.993562806349246
Score: 0.59467
500 Rastrigin's; Func runs 10000 result: 40.00575378955945
Score: 0.49569
=============================
5 Forest's; Func runs 10000 result: 0.41673083215719087
Score: 0.23572
25 Forest's; Func runs 10000 result: 0.16700842421505407
Score: 0.09447
500 Forest's; Func runs 10000 result: 0.049538421252065555
Score: 0.02802
=============================
5 Megacity's; Func runs 10000 result: 2.7600000000000002
Score: 0.23000
25 Megacity's; Func runs 10000 result: 0.9039999999999999
Score: 0.07533
500 Megacity's; Func runs 10000 result: 0.28
Score: 0.02333
=============================
All score: 2.53305
Wenn wir die Verteilung einer Zufallsvariablen des simulierten Abkühlens, wie in jedem anderen Algorithmus, ändern, wird sich dies mit Sicherheit auf seine Funktionsweise und Ergebnisse auswirken. Die ursprüngliche Gleichung des Algorithmus verwendet eine Gleichverteilung, um Zufallsschritte zur Erkundung des Raums der Situationen zu erzeugen. Diese Verteilung gewährleistet gleiche Wahrscheinlichkeiten für alle möglichen Schritte.
Als wir die Gleichverteilung durch die Normalverteilung ersetzten, änderten sich die probabilistischen Eigenschaften des Algorithmus. Eine Normalverteilung hat ihren Höhepunkt um den Mittelwert herum und nimmt ab, je weiter sie sich vom Mittelwert entfernt. Dies bedeutet, dass die mit einer Normalverteilung erzeugten Zufallsschritte um den Mittelwert herum konzentriert sind. Schritte, die weit vom Mittelwert entfernt sind, sind weniger wahrscheinlich. In unserem Fall ist der „Durchschnittswert“ der ursprüngliche Koordinatenwert, den wir verbessern wollen.
Diese Änderung der Verteilung führt natürlich zu weniger unterschiedlichen Schritten bei der Erkundung des Raums der Situationen. Der Algorithmus scheint immer lokaler zu werden und weniger in der Lage zu sein, weiter entfernte oder weniger wahrscheinliche Regionen des Raums der Situationen zu erkunden.
Die obigen Tests zeigen, dass in diesem Fall die Verwendung der Normalverteilung zu einer leichten, aber statistisch signifikanten Verschlechterung der Endergebnisse im Vergleich zu einer gleichmäßig verteilten Zufallsvariablen führte (wie im ersten Teil des Artikels dargestellt). Diese Ergebnisse wurden mit zwei Standardabweichungen ermittelt, und eine Erhöhung des Sigma-Wertes (Standardabweichung) führt zu einer weiteren statistisch signifikanten Verschlechterung der Ergebnisse.
Daraus schließen wir, dass eine Änderung der Verteilungsform in eine spitzere Form die Ergebnisse in diesem speziellen Fall verschlechtert.
Nachdem wir nun erkannt haben, dass die „Schärfung“ der Verteilungsform im ursprünglichen Algorithmus nicht von Vorteil ist, wollen wir uns einen anderen Ansatz ansehen. Nehmen wir an, dass bei dem ursprünglichen Algorithmus die Moleküle im Metall, oder man könnte sagen, ganze Kristalle innerhalb der Diffusionszone, nicht genügend Gelegenheit haben, Energie auszutauschen, um sie gleichmäßig über das gesamte Volumen des Metalls zu verteilen. In diesem Fall können wir die folgende Idee vorschlagen: Erlauben wir den Kristallen beim Energieaustausch auch Moleküle austauschen.
Der Austausch von Molekülen zwischen Kristallen mit unterschiedlichen Energien ermöglicht die Übertragung von Koordinaten zwischen den Agenten. Auf diese Weise werden die Moleküle zu einer Art Energieträger, der die Energieverteilung im gesamten Volumen des Metalls ausgleicht. Durch diese Wechselwirkung zwischen dem Kristallgitter und den Molekülen wird die Energie gleichmäßiger verteilt, sodass eine stabilere und optimale Systemkonfiguration erreicht werden kann. Mit anderen Worten: Wir werden versuchen, die Isotropie in der Metallstruktur zu erhöhen.
Isotropie ist die Eigenschaft eines Objekts oder Systems, in allen Richtungen die gleichen Merkmale oder Eigenschaften zu haben. Einfacher ausgedrückt: Ein Objekt oder System ist isotrop, wenn es in jeder Richtung gleich aussieht und sich gleich verhält. Isotropie bedeutet also, dass es keine bevorzugte Richtung oder Ausrichtung gibt und das Objekt oder System in allen Richtungen als gleich oder homogen angesehen wird.
Um die Angleichung der Eigenschaften des Metalls in alle Richtungen (zunehmende Isotropie) zu simulieren, müssen wir Änderungen an der Moving-Methode vornehmen.
Die Logik des Codes ist wie folgt: Es wird eine Iteration über jedes Element der Population „popSize“ und jede Koordinate „coords“ durchgeführt:
- erzeuge eine zufällige ganze Zahl „r“ wird im Bereich von 0 bis „popSize“ mit Hilfe der Funktion RNDfromCI, wodurch ein Agent in der Population zufällig ausgewählt wird,
- überprüfe die Bedingung: wenn der Wert der Fitnessfunktion des ausgewählten Agenten größer ist als der Fitnesswert des zu ändernden Agenten, dann kopieren wir die Koordinate des besten Agenten, andernfalls ändert sich die Koordinate des Agenten nicht,
- erzeuge mit der Funktion RNDfromCI eine Zufallszahl „rnd“ im Bereich [-0,1;0,1],
- aktualisiere den Koordinatenwert, indem zu ihm das Produkt aus „rnd“, (rangeMax[c] - rangeMin[c]) und „d“ addiert wird, d. h. es wird ein zufälliger Zuwachs im Diffusionsbereich hinzugefügt,
- überprüfe die sich ergebende Koordinate mit Hilfe der Funktion SeInDiSp, damit sie innerhalb des zulässigen Bereichs und mit dem erforderlichen Schritt liegt.
int r = 0; double rnd = 0.0; for (int i = 0; i < popSize; i++) { for (int c = 0; c < coords; c++) { r = (int)RNDfromCI (0, popSize); if (r >= popSize) r = popSize - 1; if (a [r].fPrev > a [i].fPrev) { a [i].c [c] = a [r].cPrev [c]; } else { a [i].c [c] = a [i].cPrev [c]; } rnd = RNDfromCI (-0.1, 0.1); a [i].c [c] = a [i].c [c] + rnd * (rangeMax [c] - rangeMin [c]) * d; a [i].c [c] = SeInDiSp (a [i].c [c], rangeMin [c], rangeMax [c], rangeStep [c]); } }
Ergebnisse des Abkühlens mit denselben Parametern bei einer gleichmäßigen Verteilung und Isotropie:
C_AO_SIA:50:1000.0:0.1:0.1
=============================
5 Rastrigin's; Func runs 10000 result: 80.52391137534615
Score: 0.99774
25 Rastrigin's; Func runs 10000 result: 77.70887543197314
Score: 0.96286
500 Rastrigin's; Func runs 10000 result: 57.43358792423487
Score: 0.71163
=============================
5 Forest's; Func runs 10000 result: 1.5720970326889474
Score: 0.88926
25 Forest's; Func runs 10000 result: 1.0118351454323513
Score: 0.57234
500 Forest's; Func runs 10000 result: 0.3391169587652742
Score: 0.19182
=============================
5 Megacity's; Func runs 10000 result: 6.76
Score: 0.56333
25 Megacity's; Func runs 10000 result: 5.263999999999999
Score: 0.43867
500 Megacity's; Func runs 10000 result: 1.4908
Score: 0.12423
=============================
All score: 5.45188
Die Verwendung zunehmender Isotropie, bei der Moleküle zwischen Kristallen mit unterschiedlichen Energien ausgetauscht werden, hat zu einer deutlichen Verbesserung der Ergebnisse des Algorithmus geführt. Dies ist ein Anspruch auf die Führung.
Schlussfolgerungen, die auf der Grundlage des beschriebenen Prozesses gezogen werden können:
- Die Übertragung von Koordinaten zwischen Agenten: Der Austausch von Molekülen zwischen Kristallen mit unterschiedlichen Energien ermöglicht die Übertragung von Koordinateninformationen zwischen den Agenten im Algorithmus. Dies trägt zu einer effizienteren und schnelleren Suche nach der optimalen Lösung bei, da Informationen über gute Situation an andere Agenten weitergegeben werden.
- Glättung der Energieverteilung: Der Prozess des Austauschs von Molekülen zwischen Kristallen mit unterschiedlichen Energien ermöglicht eine Glättung der Energieverteilung im gesamten Metallvolumen. Dies bedeutet, dass die Energie gleichmäßiger verteilt wird, was dazu beiträgt, lokale Minima zu vermeiden und eine stabilere und optimale Systemkonfiguration zu erreichen.
Nachdem die Ergebnisse durch die Hinzufügung von Isotropie deutlich verbessert wurden, versuchen wir nun erneut, die Normalverteilung hinzuzufügen (zunächst führen wir die Operation der Erhöhung der Isotropie durch und addieren den Zuwachs mit der Normalverteilung zu den resultierenden Werten).
Ergebnisse des Abkühlens mit zusätzlicher Isotropieverbesserung und Normalverteilung:
C_AO_SIA:50:1000.0:0.1:0.05
=============================
5 Rastrigin's; Func runs 10000 result: 78.39172420614801
Score: 0.97132
25 Rastrigin's; Func runs 10000 result: 66.41980717898778
Score: 0.82298
500 Rastrigin's; Func runs 10000 result: 47.62039509425823
Score: 0.59004
=============================
5 Forest's; Func runs 10000 result: 1.243327107341557
Score: 0.70329
25 Forest's; Func runs 10000 result: 0.7588262864735575
Score: 0.42923
500 Forest's; Func runs 10000 result: 0.13750740782669305
Score: 0.07778
=============================
5 Megacity's; Func runs 10000 result: 6.8
Score: 0.56667
25 Megacity's; Func runs 10000 result: 2.776
Score: 0.23133
500 Megacity's; Func runs 10000 result: 0.46959999999999996
Score: 0.03913
=============================
All score: 4.43177
Die Ergebnisse haben sich deutlich verschlechtert.
Die Erzeugung normalverteilter Inkremente im Algorithmus des simulierten Abkühlens hat keine Verbesserung gebracht. Kann ein normal verteiltes Inkrement nach Anwendung der Isotropieverbesserung die erwartete Wirkung erzielen? Die Erwartungen haben sich nicht bestätigt. Dies lässt sich dadurch erklären, dass nach Anwendung der Isotropieverbesserung die immer noch gleichmäßige Verteilung eine gleichmäßigere Erkundung des Raums der Situationen ermöglicht, sodass der Algorithmus verschiedene Regionen erkunden kann, ohne die Präferenzen stark zu beeinflussen. Ein Versuch, die vorhandenen Koordinaten mit Hilfe der Normalverteilung zu verfeinern, war erfolglos. Dies schränkt eine breitere Erkundung der Algorithmusbereiche ein.
Führen wir das letzte Experiment durch, um schließlich Schlussfolgerungen zugunsten einer gleichmäßigen Verteilung der Inkremente der Zufallsvariablen nach Anwendung einer Erhöhung der Isotropie zu ziehen. Wir werden die Nachbarschaft bekannter Koordinaten noch genauer erkunden, indem wir die quadratische Verteilung dafür verwenden. Wird eine gleichmäßig verteilte Zufallsvariable auf die zweite Potenz angehoben, so wird die resultierende Verteilung als quadratische Verteilung der Zufallsvariablen oder als quadratische Verteilung bezeichnet.
Ergebnisse des simulierten Abkühlens mit denselben Parametern, einschließlich Isotropieverstärkung und scharfer quadratischer Verteilung:
C_AO_SIA:50:1000.0:0.1:0.2
=============================
5 Rastrigin's; Func runs 10000 result: 70.23675927985173
Score: 0.87027
25 Rastrigin's; Func runs 10000 result: 56.86176837508631
Score: 0.70455
500 Rastrigin's; Func runs 10000 result: 43.100825665204596
Score: 0.53404
=============================
5 Forest's; Func runs 10000 result: 0.9361317757226002
Score: 0.52952
25 Forest's; Func runs 10000 result: 0.25320813586138297
Score: 0.14323
500 Forest's; Func runs 10000 result: 0.0570263375476293
Score: 0.03226
=============================
5 Megacity's; Func runs 10000 result: 4.2
Score: 0.35000
25 Megacity's; Func runs 10000 result: 1.296
Score: 0.10800
500 Megacity's; Func runs 10000 result: 0.2976
Score: 0.02480
=============================
All score: 3.29667
Nun wollen wir einen weiteren Nachteil des Simulated Annealing-Algorithmus beseitigen - die Schwierigkeit bei der Wahl der Einstellungen und der Kombination von Temperatur und Temperaturabsenkungsverhältnis, da sich diese beiden Parameter gegenseitig beeinflussen. Um diese beiden Parameter miteinander zu verknüpfen, kombinieren Sie die Funktion der Temperatursenkung und die Funktion der probabilistischen schlechteren Entscheidungsfindung. Verwenden wir die Funktion des hyperbolischen Arkuskosinus:
(1 - delta) * (acosh (-(x^3 - 3))) / 1,765
wobei:
- delta - die Differenz zwischen den Werten der Fitnessfunktion bei den letzten beiden Iterationen, normiert auf den Bereich [0,0;1,0]
- x - normalisierte Algorithmus-Epochenschritte
Bild 1. Graphische Darstellung der Abhängigkeit der schlechtesten Entscheidung von der Energiedifferenz und der Anzahl der aktuellen Epoche (y - Energiedifferenz, x - Epochen)
3. Testergebnisse
Ergebnisse des SIA-Prüfstands:
C_AO_SIA:100:0.01:0.1
=============================
5 Rastrigin's; Func runs 10000 result: 80.49732910930824
Score: 0.99741
25 Rastrigin's; Func runs 10000 result: 78.48411039606445
Score: 0.97246
500 Rastrigin's; Func runs 10000 result: 56.26829697982381
Score: 0.69720
=============================
5 Forest's; Func runs 10000 result: 1.6491133508905373
Score: 0.93282
25 Forest's; Func runs 10000 result: 1.3608802086313785
Score: 0.76978
500 Forest's; Func runs 10000 result: 0.31584037846210056
Score: 0.17866
=============================
5 Megacity's; Func runs 10000 result: 8.6
Score: 0.71667
25 Megacity's; Func runs 10000 result: 6.152
Score: 0.51267
500 Megacity's; Func runs 10000 result: 1.0544
Score: 0.08787
=============================
All score: 5.86552
Die Ergebnisse sind beeindruckend. Außerdem hat sich die Zahl der Parameter um einen verringert.
Die Visualisierung der Funktionsweise des Algorithmus zeigt eine klare Aufteilung in separate Agentengruppen, wobei alle wichtigen lokalen Extrema abgedeckt sind. Das Bild ähnelt der tatsächlichen Kristallisation von erstarrendem Metall. Die ausgezeichnete Konvergenz bei allen Tests, auch bei denen mit vielen Variablen, ist deutlich zu erkennen.
SIA mit der Testfunktion Rastrigin
SIA mit der Testfunktion Forest
SIA mit der Testfunktion Megacity
Der neue Algorithmus zur Simulation des isotropen Abkühlens (SIA, 2023) belegte den zweiten Platz in der Bewertungstabelle und verdrängte SDSm in zwei der schwierigsten Tests („Forest“ und „discrete Megacity“ mit 1000 Variablen).
| # | AO | Description | Rastrigin | Rastrigin final | Forest | Forest final | Megacity (discrete) | Megacity final | Final result | ||||||
| 10 p (5 F) | 50 p (25 F) | 1000 p (500 F) | 10 p (5 F) | 50 p (25 F) | 1000 p (500 F) | 10 p (5 F) | 50 p (25 F) | 1000 p (500 F) | |||||||
| 1 | SDSm | stochastische Diffusionssuche M | 0.99809 | 1.00000 | 0.69149 | 2.68958 | 0.99265 | 1.00000 | 0,84982 | 2,84247 | 1.00000 | 1.00000 | 0,79920 | 2,79920 | 100.000 |
| 2 | SIA | Simuliertes isotropes Abkühlen | 0.99236 | 0.93642 | 0.69858 | 2.62736 | 0.88760 | 0.64655 | 1.00000 | 2.53416 | 0.58695 | 0.74342 | 1.00000 | 2.33038 | 89.524 |
| 3 | SSG | Setzen, Säen und Wachsen | 1.00000 | 0.92761 | 0.51630 | 2.44391 | 0.72120 | 0.65201 | 0.71181 | 2.08502 | 0.54782 | 0.61841 | 0.79538 | 1.96161 | 77.027 |
| 4 | DE | differentielle Evolution | 0.98295 | 0.89236 | 0.51375 | 2.38906 | 1.00000 | 0.84602 | 0.55672 | 2.40274 | 0.90000 | 0.52237 | 0.09615 | 1.51852 | 74.777 |
| 5 | HS | Harmoniesuche | 0.99676 | 0.88385 | 0.44686 | 2.32747 | 0.99148 | 0.68242 | 0.31893 | 1.99283 | 0.71739 | 0.71842 | 0.33037 | 1.76618 | 71.983 |
| 6 | IWO | Optimierung mit invasiven Unkräutern | 0.95828 | 0.62227 | 0.27647 | 1.85703 | 0.70170 | 0.31972 | 0.22616 | 1.24758 | 0.57391 | 0.30527 | 0.26478 | 1.14395 | 49.045 |
| 7 | ACOm | Ameisen-Kolonie-Optimierung M | 0.34611 | 0.16683 | 0.15808 | 0.67103 | 0.86147 | 0.68980 | 0.55067 | 2.10194 | 0.71739 | 0.63947 | 0.04459 | 1.40145 | 48.119 |
| 8 | MEC | Evolutionäre Berechnung des Geistes | 0.99270 | 0.47345 | 0.21148 | 1.67763 | 0.60244 | 0.28046 | 0.18122 | 1.06412 | 0.66957 | 0.30000 | 0.20815 | 1.17772 | 44.937 |
| 9 | SDOm | Optimierung der Spiraldynamik M | 0.69840 | 0.52988 | 0.33168 | 1.55996 | 0.59818 | 0.38766 | 0.31953 | 1.30537 | 0.35653 | 0.15262 | 0.20653 | 0.71568 | 40.713 |
| 10 | NMm | Nelder-Mead-Verfahren M | 0.88433 | 0.48306 | 0.45945 | 1.82685 | 0.46155 | 0.24379 | 0.18613 | 0.89148 | 0.46088 | 0.25658 | 0.13435 | 0.85180 | 40.577 |
| 11 | COAm | Kuckuck-Optimierungsalgorithmus M | 0.92400 | 0.43407 | 0.24120 | 1.59927 | 0.57881 | 0.23477 | 0.11764 | 0.93121 | 0.52174 | 0.24079 | 0.13587 | 0.89840 | 38.814 |
| 12 | FAm | Firefly-Algorithmus M | 0.59825 | 0.31520 | 0.15893 | 1.07239 | 0.50637 | 0.29178 | 0.35441 | 1.15256 | 0.24783 | 0.20526 | 0.28044 | 0.73352 | 32.943 |
| 13 | ABC | Künstliches Bienenvolk (Artificial Bee Colony, ABC) | 0.78170 | 0.30347 | 0.19313 | 1.27829 | 0.53379 | 0.14799 | 0.09498 | 0.77676 | 0.40435 | 0.19474 | 0.11076 | 0.70985 | 30.528 |
| 14 | BA | Fledermaus-Algorithmus | 0.40526 | 0.59145 | 0.78330 | 1.78002 | 0.20664 | 0.12056 | 0.18499 | 0.51219 | 0.21305 | 0.07632 | 0.13816 | 0.42754 | 29.964 |
| 15 | CSS | Suche geladener Systeme | 0.56605 | 0.68683 | 1.00000 | 2.25289 | 0.13961 | 0.01853 | 0.11590 | 0.27404 | 0.07392 | 0.00000 | 0.02769 | 0.10161 | 28.825 |
| 16 | GSA | Algorithmus für die Schwerkraftsuche | 0.70167 | 0.41944 | 0.00000 | 1.12111 | 0.31390 | 0.25120 | 0.23635 | 0.80145 | 0.42609 | 0.25525 | 0.00000 | 0.68134 | 28.518 |
| 17 | BFO | Optimierung der bakteriellen Futtersuche | 0.67203 | 0.28721 | 0.10957 | 1.06881 | 0.39364 | 0.18364 | 0.14700 | 0.72428 | 0.37392 | 0.24211 | 0.15058 | 0.76660 | 27.966 |
| 18 | EM | elektromagnetismusähnlicher Algorithmus | 0.12235 | 0.42928 | 0.92752 | 1.47915 | 0.00000 | 0.02413 | 0.24828 | 0.27240 | 0.00000 | 0.00527 | 0.08689 | 0.09216 | 19.030 |
| 19 | SFL | schlurfender Froschsprung | 0.40072 | 0.22021 | 0.24624 | 0.86717 | 0.19981 | 0.02861 | 0.01888 | 0.24729 | 0.19565 | 0.04474 | 0.05280 | 0.29320 | 13.588 |
| 20 | SA | simuliertes Abkühlen | 0.36938 | 0.21640 | 0.10018 | 0.68595 | 0.20341 | 0.07832 | 0.07964 | 0.36137 | 0.16956 | 0.08422 | 0.08307 | 0.33685 | 13.295 |
| 21 | MA | Affen-Algorithmus | 0.33192 | 0.31029 | 0.13582 | 0.77804 | 0.09927 | 0.05443 | 0.06358 | 0.21729 | 0.15652 | 0.03553 | 0.08527 | 0.27731 | 11.903 |
| 22 | FSS | Fischschulsuche | 0.46812 | 0.23502 | 0.10483 | 0.80798 | 0.12730 | 0.03458 | 0.04638 | 0.20827 | 0.12175 | 0.03947 | 0.06588 | 0.22710 | 11.537 |
| 23 | IWDm | intelligente Wassertropfen M | 0.26459 | 0.13013 | 0.07500 | 0.46972 | 0.28358 | 0.05445 | 0.04345 | 0.38148 | 0.22609 | 0.05659 | 0.04039 | 0.32307 | 10.675 |
| 24 | PSO | Partikelschwarmoptimierung | 0.20449 | 0.07607 | 0.06641 | 0.34696 | 0.18734 | 0.07233 | 0.15473 | 0.41440 | 0.16956 | 0.04737 | 0.01556 | 0.23250 | 8.423 |
| 25 | RND | zufällig | 0.16826 | 0.09038 | 0.07438 | 0.33302 | 0.13381 | 0.03318 | 0.03356 | 0.20055 | 0.12175 | 0.03290 | 0.03915 | 0.19380 | 5.097 |
| 26 | GWO | Grauer-Wolf-Optimierung | 0.00000 | 0.00000 | 0.02093 | 0.02093 | 0.06514 | 0.00000 | 0.00000 | 0.06514 | 0.23478 | 0.05789 | 0.02034 | 0.31301 | 1.000 |
Zusammenfassung
Auf der Grundlage der durchgeführten Experimente und der Analyse der Ergebnisse können wir folgende Schlussfolgerungen ziehen:
- Der neue Algorithmus Simulated Isotropic Annealing (SIA) zeigt beeindruckende Ergebnisse bei der Optimierung von Funktionen mit mehreren Variablen. Dies zeigt, wie effizient der Algorithmus bei der Suche nach optimalen Situationen in hochdimensionalen Räumen ist.
- Der Algorithmus zeigt besonders gute Ergebnisse bei Funktionen mit scharfen und diskreten Merkmalen. Dies könnte darauf zurückzuführen sein, dass die SIA es uns ermöglicht, den Raums der Situationen gleichmäßig zu erkunden und optimale Punkte auch in komplexen und unregelmäßigen Regionen zu finden.
- Insgesamt ist der neue SIA-Algorithmus ein leistungsfähiges Optimierungsinstrument. Dank der gelungenen Kombination von Suchstrategien hat der Algorithmus qualitativ neue Eigenschaften und zeigt eine hohe Effizienz beim Finden optimaler Situationen.
Beim neuen SIA-Algorithmus gibt es neben der Populationsgröße nur noch zwei Parameter (Temperatur und Diffusionsverhältnis) anstelle von drei wie bei SA. Darüber hinaus ist der Temperaturparameter jetzt sehr leicht zu verstehen und wird in Teilen einer abstrakten Temperatur ausgedrückt und ist standardmäßig gleich 0,01.
Auf der Grundlage der Forschung und der Analyse der Ergebnisse können wir den SIA-Algorithmus getrost für das Training neuronaler Netze und für Handelsprobleme mit vielen Parametern und komplexen kombinatorischen Problemen empfehlen.
Bild 2. Farbabstufung der Algorithmen gemäß den einschlägigen Tests
Abb. 3. Das Histogramm der Algorithmus-Testergebnisse (auf einer Skala von 0 bis 100, größer ist besser,
das Archiv enthält das Skript zur Berechnung der Bewertungstabelle nach der im Artikel angewandten Methode).
Vor- und Nachteile der SIA:
- Minimale Anzahl externer Parameter.
- Hohe Effizienz bei der Lösung einer Vielzahl von Problemen.
- Geringe Belastung der Computerressourcen.
- Leichte Umsetzung.
- Widerstandsfähigkeit gegen das Hängenbleiben.
- Vielversprechende Ergebnisse sowohl für glatte als auch für komplexe diskrete Funktionen.
- Hohe Konvergenz.
- Keine gefunden.
Dem Artikel ist ein Archiv mit aktualisierten Versionen der in früheren Artikeln beschriebenen Algorithmuscodes beigefügt. Der Autor des Artikels übernimmt keine Verantwortung für die absolute Richtigkeit der Beschreibung der kanonischen Algorithmen. An vielen von ihnen wurden Änderungen vorgenommen, um die Suchmöglichkeiten zu verbessern. Die in den Artikeln dargelegten Schlussfolgerungen und Urteile beruhen auf den Ergebnissen der Versuche.
Übersetzt aus dem Russischen von MetaQuotes Ltd.
Originalartikel: https://www.mql5.com/ru/articles/13870
Implementierung des Augmented Dickey Fuller-Tests in MQL5
Algorithmen zur Optimierung mit Populationen: Umformen, Verschieben von Wahrscheinlichkeitsverteilungen und der Test auf Smart Cephalopod (SC)
Farbpuffer in Multi-Symbol-Multi-Perioden-Indikatoren
Algorithmen zur Optimierung mit Populationen: der Algorithmus Simulated Annealing (SA). Teil I
- Freie Handelsapplikationen
- Über 8.000 Signale zum Kopieren
- Wirtschaftsnachrichten für die Lage an den Finanzmärkte
Sie stimmen der Website-Richtlinie und den Nutzungsbedingungen zu.