Algorithmen zur Optimierung mit Populationen: Widerstand gegen das Steckenbleiben in lokalen Extremen (Teil I)

Inhalt

1. Einführung
2. Erklärung des Problems
3. Code-Änderungen
4. Algorithmen
5. Vorläufige Schlussfolgerungen

1. Einführung

Es handelt sich um eine einzigartige Untersuchung, deren Idee mir bei der Beantwortung von Fragen kam, die bei der Diskussion über einen meiner Artikel aufkamen. Ich hoffe, dass die Leser den Wert und die Originalität dieses Werkes zu schätzen wissen.

Meine Gedanken und Ideen, die zu dieser Forschung geführt haben, sind das Ergebnis eines tiefen Eintauchens in das Thema und einer Leidenschaft für wissenschaftliche Forschung. Ich glaube, dass diese Arbeit einen wichtigen Beitrag zum Bereich der algorithmischen Optimierung leisten kann, der die Aufmerksamkeit von Forschern und Praktikern auf sich zieht.

In diesem Experiment schlug ich vor, einen Test durchzuführen, der darauf abzielt, die Widerstandsfähigkeit von Algorithmen gegen das Steckenbleiben in lokalen Extrema zu bewerten und die Agenten bei der ersten Iteration nicht zufällig im gesamten Bereich des Suchraums zu platzieren, sondern im globalen Minimum. Das Ziel des Experiments ist die Suche nach dem globalen Maximum.

In einem solchen Szenario, in dem sich alle Suchagenten des Algorithmus an einem Punkt befinden, haben wir es mit einem interessanten Phänomen zu tun - einer degenerierten Population. Dies ist wie ein Moment des Einfrierens der Zeit, in dem die Vielfalt in der Population auf ein Minimum reduziert ist. Obwohl dieses Szenario künstlich ist, ermöglicht es uns, interessante Schlussfolgerungen zu ziehen und die Auswirkungen einer Verringerung der Vielfalt in der Population auf das Ergebnis zu bewerten. Der Algorithmus sollte in der Lage sein, aus einem solchen Engpass herauszukommen und ein globales Maximum zu erreichen.

Bei dieser Art von Stresstest für Optimierungsalgorithmen können wir die Geheimnisse der Interaktion zwischen den Agenten, ihre Zusammenarbeit oder ihren Wettbewerb aufdecken und verstehen, wie sich diese Faktoren auf die Geschwindigkeit der Erreichung des Optimums auswirken. Eine solche Analyse eröffnet neue Horizonte für das Verständnis der Bedeutung der Vielfalt in einer Population für das effiziente Funktionieren von Algorithmen und ermöglicht es uns, Strategien zur Erhaltung dieser Vielfalt zu entwickeln, um bessere Ergebnisse zu erzielen.

Um das Experiment durchzuführen, müssen wir zunächst die Koordinaten der Agenten zwangsweise außerhalb des Algorithmus initialisieren, indem wir die Koordinaten des globalen Minimums verwenden, bevor wir die Fitnessfunktion in der ersten Epoche messen.

Ein solches Experiment wird es uns ermöglichen, die Widerstandsfähigkeit unter extrem schwierigen Bedingungen und die Fähigkeit, Grenzen zu überwinden, zu bewerten.

2. Erklärung des Problems

Stellen Sie sich vor, Sie befinden sich in einem tiefen Tal, umgeben von dichter Dunkelheit. Ihre Augen sind verbunden, sodass Sie die Welt um sich herum nicht sehen können. Sie spüren, wie Ihnen ein kalter Wind ins Gesicht bläst, und Ihr Herz klopft heftig, als wollte es aus Ihrer Brust springen, was Ihre Angst und Unsicherheit noch verstärkt.

Man beginnt mit dem ersten Schritt nach vorn. Deine Füße spüren den Boden, und Sie gehen ich allmählich vorwärts im Tal, mit jedem Schritt näher zur Freiheit, und der Geist ist von Entschlossenheit erfüllt. Wenn Sie schließlich den Rand erreichen, eröffnet sich vor Ihnen ein atemberaubender Ausblick. Die glatte Ebene erstreckt sich vor Ihnen wie eine endlose Leinwand. Die vereinzelten steilen Klippen, die sich in der Ferne erheben, rufen gemischte Gefühle von Erstaunen und Herausforderung hervor. Doch trotz dieses schönen Panoramas können Sie es nicht sehen.

Sie beschließen, sich auf Ihre Sinne und Ihre Intuition zu verlassen, um die Richtung zu bestimmen, in die Sie sich bewegen müssen, um die Spitze der höchsten Klippe zu erreichen. Stellen Sie sich nun vor, dass diese schwierige Aufgabe von einem Algorithmus bewältigt wird, der auf der diskreten Funktion des Megacity-Tests basiert. Dieser Algorithmus ist ebenso wie Sie durch seine Fähigkeiten begrenzt und kann die Umgebung nicht direkt sehen oder wahrnehmen. Er muss seine Rechenfähigkeiten und seine Logik einsetzen, um den besten Weg zur Spitze der höchsten Klippe zu finden. Daher ist dieses Problem der diskreten Funktion des Test mit „Megacity“ eine schwierige Herausforderung für einen Algorithmus, der wie Sie mit Unsicherheiten konfrontiert ist.

Aber auch die Funktionen „Hilly“ und „Forest“ stellen unter diesen Umständen ein schwieriges Problem dar. Schauen wir uns diese bekannten Funktionen an, um die Komplexität der bevorstehenden Aufgabe für die Algorithmen zu verstehen.

Die Funktion „Hilly“

Die Funktion „Forest“

Die Funktion der Megacity

Stellen Sie sich vor, Sie sind ein Algorithmus, die Verkörperung von Rechenleistung und logischem Denken. Sie sind nicht nur trockene Codefolgen oder Gleichungen auf dem Papier, Sie werden lebendig und schlüpfen in die Rolle eines Forschers. Ihr Kopf ist voller Fragen und Hypothesen, und Sie versuchen, das Rätsel zu lösen, das vor Ihnen liegt. Sie tauchen in eine Welt von Daten und Informationen ein, analysieren, vergleichen und heben Schlüsselfaktoren hervor, während Ihre Computerfähigkeiten auf allen Zylindern laufen. Sie beginnen, verschiedene Modelle und Szenarien zu entwerfen, mögliche Wege zur Lösung eines Problems zu erkunden und verschiedene Kombinationen und Optionen auszuprobieren, und Ihre Kreativität führt zu neuen Entdeckungen. Doch der Weg zu einer Lösung ist nicht immer einfach. Sie stehen vor Herausforderungen, die unüberwindbar scheinen, aber Sie geben nicht auf. Sie überwinden Hindernisse und Ablenkungen, eine nach der anderen, und kommen Ihrem Ziel mit jedem Schritt näher. Und schließlich, wenn man eine Lösung gefunden hat, ist das wie ein Moment der Erleuchtung. Ihr Geist wird vom hellen Licht des Verstehens erhellt, und Sie sehen, wie alle Teile an ihren Platz fallen.

Im Kontext dieses Bildes steht der Optimierungsalgorithmus vor der Aufgabe, eine Funktion zu maximieren, die eine komplexe Topologie mit vielen lokalen Maxima aufweist. Hier finden Sie eine genauere Beschreibung des Problems:

• Lokale Maxima. Auf dem Weg vom Startpunkt (ist mit „min“ gekennzeichnet) zum Endpunkt (ist mit „max“ gekennzeichnet) trifft der Algorithmus auf viele lokale Maxima. Dies kann dazu führen, dass der Algorithmus in einer lokalen Falle stecken bleibt, ohne das globale Extremum zu erreichen. Dies ist ein großes Problem bei Optimierungsproblemen. So neigen beispielsweise Algorithmen, die auf dem Gradientenabstieg basieren, dazu, zum nächstgelegenen Maximum zu „klettern“, und wenn es sich dabei um ein lokales Maximum handelt, bleiben sie „stecken“.

• Hohe Dimension. Betrachtet man eine Funktion in einem mehrdimensionalen Raum, so nimmt die Zahl der lokalen Maxima stark zu, was das Problem verkompliziert. In hohen Dimensionen wird der Raum „leer“, was das Problem noch schwieriger macht, da der Algorithmus nichts hat, woran er sich festhalten kann.
  

• Komplexität der Funktionsoberfläche. Die Funktionsoberfläche kann sehr komplex sein, mit vielen Spitzen und Tälern, was den Optimierungsprozess zeitaufwändiger macht. Dazu muss der Algorithmus in der Lage sein, lokale Maxima zu überspringen und zum globalen Maximum aufzusteigen. 

• Konvergenz und Konvergenzgeschwindigkeit. Die Konvergenz des Algorithmus zum Funktionsmaximum kann sich aufgrund der Entfernung des Zielpunkts vom Startpunkt verlangsamen, sodass zusätzliche Iterationen erforderlich sein können, um das Ziel zu erreichen.

• Bereich Forschung. Der Algorithmus muss möglicherweise zusätzlich die Region auf der Suche nach einem globalen Maximum erkunden, was zu einer erhöhten Rechenkomplexität führen kann.

Um die Beschreibung des Problems zusammenzufassen, können wir den Unterschied zwischen einer typischen Optimierungssituation, in der die Agenten ihre Bewegung im Suchraum gleichmäßig verteilt beginnen, und einer Situation hervorheben, in der es notwendig ist, nicht nur vorhandene Informationen „aufzudecken“, sondern vielmehr ihr Wissen und ihre Erfahrung zu erforschen und in unerforschte Bereiche zu erweitern. Diese Art der Problemstellung ist besonders wertvoll in Fällen, in denen wir bereits einige Lösungen aus früheren Optimierungssitzungen haben und von diesem „Lösungspunkt“ ausgehen wollen, anstatt einfach nur die vorhandenen Informationen herauszukristallisieren.

3. Code-Änderungen

Um Agenten an einem Punkt zu platzieren, weisen Sie die Koordinaten des globalen Minimums der Testfunktion den entsprechenden Populationsagenten zu. Im Allgemeinen sieht dieses Verfahren wie folgt aus:

if (epochCNT == 1)
{
  for (int set = 0; set < ArraySize (AO.a); set++)
  {
    for (int i = 0; i < funcCount; i++)
    {
      AO.a [set].c [i * 2]     = f.GetMinFuncX ();
      AO.a [set].c [i * 2 + 1] = f.GetMinFuncY ();
    }
  }
}

Bei einigen Algorithmen reicht es nicht aus, Agenten einfach an einem Punkt im Suchraum zu platzieren. Es sollten zusätzliche Informationen eingegeben werden. Im Falle des SDSm-Algorithmus muss beispielsweise auch der entsprechende Sektor für jede Koordinate angegeben werden. Bei der Verwendung des BGA-Algorithmus hingegen müssen die Koordinatenwerte von einer reellen in eine binäre Darstellung umgewandelt werden, was zusätzliche Änderungen im Code des Algorithmus nach sich zieht. Bei BGA sieht der Standort der Agenten an einem bestimmten Punkt wie folgt aus:

//==================
if (epochCNT == 1)
{
  for (int set = 0; set < ArraySize (AO.a); set++)
  {
    for (int i = 0; i < funcCount; i++)
    {
      AO.a [set].DoubleToGene (f.GetMinFuncX (), i * 2);
      AO.a [set].DoubleToGene (f.GetMinFuncY (), i * 2 + 1);
    }

    AO.a [set].ExtractGenes ();
  }
}
//==================

Wie aus diesem Code ersichtlich ist, erfolgt hier die notwendige Umwandlung der Koordinaten in den binären Code der Gene. Ich arbeite derzeit an der Vereinheitlichung des Prozesses der Platzierung von Agenten an den gewünschten Koordinaten. In dieser Studie werden die Quellcodes in ihrem aktuellen Zustand vorgestellt. Nahezu jeder Algorithmus erforderte aufgrund der Art seiner Architektur einen eigenen Testumgebung. Bleiben Sie auf dem Laufenden, um neue Artikel zu den Algorithmen zu erhalten. Die Vereinfachung der Platzierung von Koordinaten in der Population sowie ihre Vereinheitlichung werden auf einen gemeinsamen Standard gebracht.

4. Algorithmen

Wir gehen nun zur Analyse des Verhaltens der Algorithmen in unseren einzigartigen Tests über und beginnen mit der Diskussion der Algorithmen, die die schlechtesten Ergebnisse gezeigt haben. Besonders überraschend ist, dass einige von ihnen, die in den Standardtests zuvor recht hohe Platzierungen erreicht hatten, in unserem ungewöhnlichen Test schlecht abgeschnitten haben. Dies deutet darauf hin, dass der Erfolg von Algorithmen nicht nur von ihrer Gesamteffizienz abhängt, sondern auch von ihrer Fähigkeit, sich an spezifische Bedingungen und Merkmale des Problems anzupassen. Solche unerwarteten Ergebnisse machen deutlich, wie wichtig es ist, eine Vielzahl von Tests und Studien durchzuführen, um ein tieferes Verständnis der Leistung von Optimierungsalgorithmen in verschiedenen Kontexten zu gewinnen.

Nachstehend finden Sie Berichte über die Algorithmen, die wie folgt zu lesen sind:

• C_AO_FSS:50;0.01;0.8             - Algorithmusname und externe Parameter
  
• 5 Hilly's                                   - Name der Testfunktion und ihre Nummer im Test
  
•  Func runs: 10000                   - Anzahl der Durchläufe
  
• result: 0.32457068874346456  - erzieltes Ergebnis, wobei 0,0 das Minimum der Testfunktion und 1,0 das Maximum ist. Je höher der Wert, desto besser
  
• All score: 1.33084                   - Gesamtwert der erzielten Punkte. Je höher der Wert, desto besser
  

Differenzielle Evolution (DE)

C_AO_DE:50;0.2;0.8
=============================
5 Hilly's; Func runs: 10000; result: 0.0
25 Hilly's; Func runs: 10000; result: 0.0
500 Hilly's; Func runs: 10000; result: 0.0
=============================
5 Forest's; Func runs: 10000; result: 0.0
25 Forest's; Func runs: 10000; result: 0.0
500 Forest's; Func runs: 10000; result: 0.0
=============================
5 Megacity's; Func runs: 10000; result: 0.0
25 Megacity's; Func runs: 10000; result: 0.0
500 Megacity's; Func runs: 10000; result: 0.0
=============================
All score: 0.00000

Leider ist auch einer der leistungsfähigsten Algorithmen in der Rangliste bei unserem Test völlig durchgefallen. In diesem Fall befanden sich die Agenten in einer Sackgasse und konnten sich nicht bewegen. Der Grund für diesen Misserfolg ist, dass jede neue Position eines Agenten von den Positionen dreier anderer Agenten abhängt, und wenn diese alle am selben Punkt landen, kann keiner von ihnen seine Koordinaten aktualisieren. Diese Situation zeigt, wie wichtig es ist, die Interaktionen zwischen den Agenten sorgfältig zu analysieren und ihre Bewegungen angemessen zu steuern, um das Optimierungsproblem erfolgreich zu lösen. Solche unerwarteten Ausfälle können zu weiteren Forschungen und Verbesserungen bei der Entwicklung von Algorithmen motivieren, die mit solchen Komplexitäten wirksam umgehen können.

Für andere Algorithmen, die den Test komplett nicht bestanden haben, werde ich die Testergebnisse nicht vorstellen.

Elektromagnetischer Algorithmus (EM)

Der EM-Algorithmus stieß auf das Problem, dass die Koordinaten der Agenten während der Optimierung nicht aktualisiert werden konnten. In diesem Fall kollabierten die Teilchen unter dem Einfluss der elektromagnetischen Anziehung, wodurch sich die Stoffe zu einem Klumpen vereinigten.

Schwerkraft-Suchalgorithmus (GSA)

Die Schwerkraft führte dazu, dass sich alle Objekte an einem Punkt befanden und dort blieben - sie wurden vom Zentrum angezogen, ähnlich wie von einem Schwarzen Loch.

Künstlicher Ameisenkolonie-Algorithmus (ACOm)

Das Problem bei diesem Algorithmus war das Fehlen von Pfaden für die Bewegung der Ameisen, die sich auf der Grundlage des Geruchs von Pheromonen bewegen würden. Da die Ameisen in diesem Fall von einem Punkt aus starteten, wurden die Pfade zwischen ihnen nicht gebildet, was zu Schwierigkeiten bei der Bewegung und der Koordination der Aktionen der Ameisen führte.

Suche nach Fischschulen (FSS)

C_AO_FSS:50;0.01;0.8
=============================
5 Hilly's; Func runs: 10000; result: 0.32457068874346456
25 Hilly's; Func runs: 10000; result: 0.27938488291267094
500 Hilly's; Func runs: 10000; result: 0.2343201202260512
=============================
5 Forest's; Func runs: 10000; result: 0.18964347858030822
25 Forest's; Func runs: 10000; result: 0.16146315945349987
500 Forest's; Func runs: 10000; result: 0.14145987387955847
=============================
5 Megacity's; Func runs: 10000; result: 0.0
25 Megacity's; Func runs: 10000; result: 0.0
500 Megacity's; Func runs: 10000; result: 0.0
=============================
All score: 1.33084

Bei diesem Algorithmus verwenden die Fische den Unterschied in der Fitness zwischen der letzten und der vorherigen Iteration, um ihre Bewegungsrichtung zu bestimmen. Während die Fische bei den Funktionen „Hilly“ und „Forest“ Veränderungen in der Landschaft wahrnehmen, verwirrt die Ausführung des Algorithmus auf der flachen Oberfläche von Megacity die Fische, sodass sie sich nicht mehr orientieren können. Erstaunlich ist das Verhalten der Fische, wenn sie auf glatten Oberflächen mit einem Gefälle starten. Befindet sich der Startpunkt jedoch am oberen Ende des lokalen Extremwerts und nicht im Loch, ist es unwahrscheinlich, dass sich die Fische auch bei den Funktionen „Hilly“ und „Forest“ bewegen.

Simuliertes isotropes Abkühlen (SIA)

C_AO_SIA:100:0.01:0.1
=============================
5 Hilly's; Func runs: 10000; result: 0.32958446477979136
25 Hilly's; Func runs: 10000; result: 0.32556359155723036
500 Hilly's; Func runs: 10000; result: 0.27262289744765306
=============================
5 Forest's; Func runs: 10000; result: 0.1940720887058382
25 Forest's; Func runs: 10000; result: 0.1935893813273654
500 Forest's; Func runs: 10000; result: 0.16409411642496857
=============================
5 Megacity's; Func runs: 10000; result: 0.0
25 Megacity's; Func runs: 10000; result: 0.0
500 Megacity's; Func runs: 10000; result: 0.0
=============================
All score: 1.47953

Der Algorithmus des simulierten isotropen Abkühlens zeichnet sich durch eine einzigartige Kombination von Merkmalen aus, die an den FSS-Betrieb erinnern, jedoch erhebliche Unterschiede aufweisen. Bei diesem Algorithmus erfolgt die Bewegung in verschiedene Richtungen vom Ausgangspunkt aus energischer und aktiver als beim FSS, was ein Gefühl von lebhafter Kreativität bei der Suche nach der optimalen Lösung vermittelt. Ähnlich wie FSS verwendet der Simulationsalgorithmus des isotropen Glühens Unterschiede in den Werten der Fitnessfunktionen, um die Bewegung zu steuern. Hier wird die Bewegung jedoch durch einen allmählichen Temperaturabfall beeinflusst, der mit der Zeit zum „Einfrieren“ der Teilchen an bestimmten Punkten im Raum führt.

Evolutionäre Strategien ((PO)ES)

C_AO_(PO)ES:100:10:0.025:8.0
=============================
5 Hilly's; Func runs: 10000; result: 0.32231823718105856
25 Hilly's; Func runs: 10000; result: 0.3228736374003839
500 Hilly's; Func runs: 10000; result: 0.2797261292300971
=============================
5 Forest's; Func runs: 10000; result: 0.19410491957153192
25 Forest's; Func runs: 10000; result: 0.1875135077472832
500 Forest's; Func runs: 10000; result: 0.15801830580073034
=============================
5 Megacity's; Func runs: 10000; result: 0.1292307692307692
25 Megacity's; Func runs: 10000; result: 0.12553846153846154
500 Megacity's; Func runs: 10000; result: 0.08198461538461577
=============================
All score: 1.80131

Dieser Algorithmus war der erste auf der Liste, der alle Tests erfolgreich abschließen konnte. Obwohl die Verwendung des Begriffs „erfolgreich abgeschlossen“ ziemlich wertend erscheint, wurde tatsächlich jede dieser Tests mit mindestens einem anderen Ergebnis als Null bestanden. Es ist bemerkenswert, dass die Population dazu neigt, sich in verschiedene Gruppen aufzuteilen. Der anfängliche Enthusiasmus des Algorithmus hält jedoch nur kurz an - die Agenten brechen die Suche am ersten nächstgelegenen Hügel schnell ab, wahrscheinlich in der Annahme, dass sie bereits erfolgreich waren.

Besonders interessant ist, dass die Agenten, nachdem sie sich in Gruppen aufgeteilt haben, zu Beginn beim Beobachter Optimismus wecken, indem sie sich in verschiedene Richtungen bewegen, aber die Enttäuschung kommt schnell: Sobald eine der Gruppen eine spürbare Verbesserung ihrer Position erreicht, ändern alle anderen Gruppen sofort die Richtung und eilen auf den Anführer zu. Diese Momente lösen gemischte Gefühle und Emotionen aus - von Freude bis Enttäuschung. Die Interaktion der Agenten in diesem Algorithmus ähnelt dem Leben mit all seinen Überraschungen und seiner Wandelbarkeit.

Affen-Algorithmus (MA)

C_AO_MA:50;0.01;0.9;50
=============================
5 Hilly's; Func runs: 10000; result: 0.32874856274894027
25 Hilly's; Func runs: 10000; result: 0.30383823957660194
500 Hilly's; Func runs: 10000; result: 0.2475564907358033
=============================
5 Forest's; Func runs: 10000; result: 0.20619304546795353
25 Forest's; Func runs: 10000; result: 0.1733511102614089
500 Forest's; Func runs: 10000; result: 0.14786586882293234
=============================
5 Megacity's; Func runs: 10000; result: 0.17538461538461542
25 Megacity's; Func runs: 10000; result: 0.1436923076923077
500 Megacity's; Func runs: 10000; result: 0.09555384615384681
=============================
All score: 1.82218

Im Rahmen dieses Algorithmus bewegen sich die Affen ziemlich isoliert in die gewählte Richtung, auch wenn sich diese Richtung als falsch herausstellt. Dieses einzigartige Verhalten ermöglicht es den Agenten, den Raum effizienter zu erkunden und sich weiter von ihrem Ausgangspunkt auszubreiten. Sie machen weite „Sprünge ins Unbekannte“, besonders eindrucksvoll bei der diskreten Funktion Megacity, bei der es auf horizontalen Flächen keinen Fitnesszuwachs gibt, was das Erreichen weit entfernter Gebiete erleichtert.

Trotz dieser Explorationsfähigkeit erweist sie sich jedoch als unzureichend, um das Hauptziel zu erreichen, da die Anzahl der verfügbaren Iterationen zu Ende geht. Es ist wichtig, das faszinierende visuelle Verhalten des Algorithmus zu erwähnen, das wirklich der chaotischen Bewegung von Affen in einem Schwarm ähnelt, was ein erstaunliches Spektakel schafft und das Interesse an seiner weiteren Erforschung und Verbesserung weckt.

Simuliertes Abkühlen (SA)

C_AO_SA:50:1000.0:0.1:0.2
=============================
5 Hilly's; Func runs: 10000; result: 0.3266993983850477
25 Hilly's; Func runs: 10000; result: 0.30166692301946135
500 Hilly's; Func runs: 10000; result: 0.2545648344562219
=============================
5 Forest's; Func runs: 10000; result: 0.1939959116807614
25 Forest's; Func runs: 10000; result: 0.17721159702946082
500 Forest's; Func runs: 10000; result: 0.15159936395874307
=============================
5 Megacity's; Func runs: 10000; result: 0.2584615384615384
25 Megacity's; Func runs: 10000; result: 0.15292307692307697
500 Megacity's; Func runs: 10000; result: 0.10135384615384675
=============================
All score: 1.91848

Im Gegensatz zu seinem „Verwandten“, dem SIA-Algorithmus (der übrigens eine viel höhere Position in der Rangliste einnimmt), ist das Verhalten des Algorithmus des Simulierten-Abkühlens chaotischer, was in den Visualisierungen sogar mit bloßem Auge erkennbar ist. Diese chaotische Natur der Simulation des „Abkühlens“ trägt jedoch dazu bei, dass etwas bessere Ergebnisse erzielt werden. Diese Leistungen sind jedoch nicht groß genug, um diesen Algorithmus in der Ruhmeshalle der herausragenden Algorithmen zu verewigen, aber die Verbesserung ist spürbar und verdient Anerkennung.

Firefly-Algorithmus (FAm)

C_AO_FAm:50;0.1;0.3;0.1
=============================
5 Hilly's; Func runs: 10000; result: 0.32461162859403175
25 Hilly's; Func runs: 10000; result: 0.31981492599317524
500 Hilly's; Func runs: 10000; result: 0.25932958993768923
=============================
5 Forest's; Func runs: 10000; result: 0.2124297717365277
25 Forest's; Func runs: 10000; result: 0.21595138588924906
500 Forest's; Func runs: 10000; result: 0.1577543024576405
=============================
5 Megacity's; Func runs: 10000; result: 0.2246153846153846
25 Megacity's; Func runs: 10000; result: 0.1987692307692308
500 Megacity's; Func runs: 10000; result: 0.12084615384615457
=============================
All score: 2.03412

FA ist einer meiner Lieblingsalgorithmen. Seine Anziehungskraft zeigt sich nicht nur in dem schönen Namen selbst, sondern auch in der eleganten Idee, die dahinter steckt, sowie in dem eleganten Verhalten der Glühwürmchen (fireflies). Diese mystischen, leuchtenden Wesen sind in der Lage, sich mit einer solchen Geschwindigkeit den nächstgelegenen lokalen Extremen zu nähern, dass es wirklich schwierig ist, sie im Auge zu behalten. Auf diese großartige Show folgt jedoch eine Stagnation, wenn die Agenten in lokalen Maxima stecken bleiben und nicht in der Lage sind, weiter zu forschen und ein globales Optimum zu erreichen.

Auch wenn es frustrierend erscheinen mag, eröffnet dieser Moment der Stagnation die Möglichkeit, den Algorithmus zu verbessern. Durch die Einführung von Mechanismen zur Überwindung lokaler Fallstricke kann der FA neue Horizonte der Effizienz und Genauigkeit erreichen. So sehen wir auch in den Momenten, in denen die Glühwürmchen aufhören, nicht nur das Ende, sondern einen neuen Anfang - die Gelegenheit, diesen erstaunlichen Algorithmus zu verbessern und weiterzuentwickeln.

Optimierung der bakteriellen Nahrungssuche (BFO)

C_AO_BFO:50;0.01;0.3;100
=============================
5 Hilly's; Func runs: 10000; result: 0.3226339934200066
25 Hilly's; Func runs: 10000; result: 0.2925193012197403
500 Hilly's; Func runs: 10000; result: 0.2554221763445149
=============================
5 Forest's; Func runs: 10000; result: 0.2111053636851011
25 Forest's; Func runs: 10000; result: 0.20536292110181784
500 Forest's; Func runs: 10000; result: 0.15743855819242952
=============================
5 Megacity's; Func runs: 10000; result: 0.27999999999999997
25 Megacity's; Func runs: 10000; result: 0.19415384615384618
500 Megacity's; Func runs: 10000; result: 0.11735384615384695
=============================
All score: 2.03599

Die Fähigkeit der Bakterien, ihre Mobilität aufrechtzuerhalten, auch ohne ihre Fitness zu steigern, ist ein Schlüsselfaktor, der es ihnen ermöglicht, sich effizient über große Entfernungen auszubreiten und die oben diskutierten Algorithmen in diesem Punkt zu übertreffen. Dieses erstaunliche Phänomen wird besonders in der Megacity-Umgebung deutlich, wo Bakterien erstaunliche Mobilitäts- und Überlebensfähigkeiten zeigen, die es ihnen ermöglichen, sich erfolgreich an unterschiedliche und komplexe Umgebungen anzupassen. In diesem Zusammenhang werden die Bakterien zu echten Pionieren, die neue Gebiete erforschen und besiedeln, was ihre einzigartigen Fähigkeiten und ihre Bedeutung in der Welt der lebenden Organismen unterstreicht.

Ladesystem-Suche (CSS)

C_AO_CSS:50;0.1;0.7;0.01
=============================
5 Hilly's; Func runs: 10000; result: 0.38395827586082376
25 Hilly's; Func runs: 10000; result: 0.3048219687002418
500 Hilly's; Func runs: 10000; result: 0.2895158695448419
=============================
5 Forest's; Func runs: 10000; result: 0.2699906934238054
25 Forest's; Func runs: 10000; result: 0.19451237087137088
500 Forest's; Func runs: 10000; result: 0.18498127715987073
=============================
5 Megacity's; Func runs: 10000; result: 0.16923076923076924
25 Megacity's; Func runs: 10000; result: 0.13846153846153847
500 Megacity's; Func runs: 10000; result: 0.12276923076923094
=============================
All score: 2.05824

Überraschenderweise zeigte sich dieser Algorithmus in diesem Test völlig unerwartet und übertraf seine üblichen Indikatoren, bei denen er unter den Außenseitern in der Bewertung an vorletzter Stelle steht. Dieses Mal landete CSS im Mittelfeld (Zwölfter von unten). Das Geheimnis dieser Umwandlung hat seine eigene Erklärung: Elektrostatische Ladungen, die den Gleichungen des Algorithmus gehorchen, beginnen mit abstoßenden Kräften zu interagieren, wenn sie in den Radius der Ladung fallen, wodurch sie sich explosionsartig im umgebenden Suchraum ausbreiten können. Dieses Verfahren ist nicht nur optisch ansprechend, sondern hat auch das Potenzial für praktische Anwendungen.

Die Fähigkeit, wie ein Feuerwerkskörper zu feuern, eröffnet neue Möglichkeiten für CSS. Wir können diesen Algorithmus beispielsweise als Quelle von Lösungsideen für die Bestimmung der optimalen Position von Agenten für andere Optimierungsalgorithmen betrachten, oder wir können ihn erfolgreich in hybride Lösungen integrieren, bei denen CSS dazu beiträgt, eine Degeneration der Population zu vermeiden. Der unerwartete Erfolg von CSS in diesem Test ist also nicht nur inspirierend, sondern eröffnet auch neue Perspektiven für seine Anwendung.

Algorithmus zur Aussaat und Aufzucht von Setzlingen (SSG)

C_AO_SSG:50;0.3;0.5;0.4;0.1
=============================
5 Hilly's; Func runs: 10000; result: 0.3284133103606342
25 Hilly's; Func runs: 10000; result: 0.3246280774155864
500 Hilly's; Func runs: 10000; result: 0.2808547975998361
=============================
5 Forest's; Func runs: 10000; result: 0.194115963123826
25 Forest's; Func runs: 10000; result: 0.19754974771110584
500 Forest's; Func runs: 10000; result: 0.17111478002239264
=============================
5 Megacity's; Func runs: 10000; result: 0.25846153846153846
25 Megacity's; Func runs: 10000; result: 0.23353846153846156
500 Megacity's; Func runs: 10000; result: 0.14158461538461614
=============================
All score: 2.13026

Dieser Algorithmus zeigt sein Potenzial bei Gradientenfunktionen wie Hilly oder Forest und rangiert im Standard-Ranking weit oben. Seine Wirksamkeit kommt jedoch nur bei einer positiven Veränderung des Gradienten voll zum Tragen. Andernfalls verschlechtert sich die Population schnell, und die Individuen konvergieren an einem besten, lokalen Punkt, was die Möglichkeit eröffnet, die SSG-Methode zur Verfeinerung der Ergebnisse von Optimierungsalgorithmen einzusetzen.

5. Vorläufige Schlussfolgerungen

In diesem einzigartigen Forschungsexperiment, bei dem die Algorithmen strengen Anfangsbedingungen unterworfen wurden, entdeckten wir viele faszinierende Eigenschaften der verschiedenen Algorithmen, die unter der standardmäßigen zufälligen gleichmäßigen Platzierung von Agenten im Suchraum verborgen blieben. Wie im richtigen Leben entfalten Organismen ihr inneres Potenzial unter extremen Bedingungen.

Bei einigen Algorithmen kam es zu unerwarteten Testergebnissen, unter anderem fielen sie von der Spitze auf den letzten Platz. Auf diese Weise können wir besser verstehen, wie Algorithmen auf der Grundlage ihrer Fähigkeiten bei speziellen Optimierungsproblemen eingesetzt werden können, und ein tieferes Verständnis für ihre Stärken und Schwächen gewinnen. Außerdem wurden die positiven und negativen Seiten der einzelnen Algorithmen deutlicher herausgestellt, sodass sie ihre Stärken besser nutzen und ihre Schwächen ausgleichen können. Darüber hinaus trägt diese Forschung zu einem besseren Verständnis der Entwicklung hybrider Algorithmen bei, die es ermöglichen, die Stärken verschiedener Methoden zu kombinieren, um optimale Ergebnisse zu erzielen.

Im nächsten Artikel werden wir uns weiter mit den Eigenschaften und dem Verhalten von Algorithmen befassen und Schlussfolgerungen ziehen.