Die Rolle der Qualität von Zufallszahlengeneratoren für die Effizienz von Optimierungsalgorithmen

Einführung

Bei der Verwendung von Optimierungsalgorithmen fragen sich viele Leser, wie wichtig es ist, einen hochwertigen Zufallszahlengenerator zu verwenden. Die Antwort auf diese Frage ist nicht so einfach, wie sie auf den ersten Blick erscheinen mag. Es liegt jedoch auf der Hand, dass die Qualität der Zufallszahlen einen erheblichen Einfluss auf die Suchmöglichkeiten von Algorithmen haben kann, da Populationsalgorithmen überwiegend auf stochastischer Suche beruhen.

Lassen Sie uns diese Frage gemeinsam klären. Bevor wir beginnen, müssen wir uns mit den verschiedenen Arten von Zufallszahlengeneratoren befassen, mit ihren Auswirkungen auf die Ergebnisse und mit der Frage, wo Sie zuverlässige Optionen finden können.

Zufallszahlengeneratoren (RNGs) sind Algorithmen oder Geräte, die eine Folge von Zahlen oder Werten erzeugen, wobei die Zahlen zufällig erscheinen. In der Informatik und Mathematik werden solche Sequenzen in der Regel als „pseudozufällig“ bezeichnet, da sie durch deterministische Algorithmen und nicht durch echte Zufallsprozesse erzeugt werden.

Es gibt zwei Haupttypen von Zufallszahlengeneratoren:

1. Pseudozufallsgeneratoren (PRGs). Diese Generatoren verwenden mathematische Gleichungen oder Algorithmen, um eine Folge von Zahlen zu erzeugen, die zufällig erscheinen. Sie werden mit einem Anfangswert initialisiert, der als „Seed“ (Anfangswert) bezeichnet wird, und jedes Mal, wenn der Generator aufgerufen wird, erzeugt er die nächste Zahl in der Folge. Mit der richtigen Wahl eines Algorithmus und eines Seeds kann PRG für viele Anwendungen nützlich sein, bei denen eine pseudozufällige Sequenz erforderlich ist.
2. Echte Zufallszahlengeneratoren (TRNGs). Diese Generatoren verwenden echte Zufallsprozesse, wie radioaktives Zerfallsrauschen oder Quantenrauschen, um Zufallszahlen zu erzeugen. Solche Generatoren werden häufig in der Kryptographie, bei Lotterien und in anderen Bereichen eingesetzt, in denen ein hohes Maß an Zufälligkeit erforderlich ist.

Pseudo-Zufallszahlengeneratoren werden häufig in der Programmierung verwendet, z. B. in den Bibliotheken der Standardprogrammiersprachen.

Die Genauigkeit der in Programmiersprachen eingebauten Zufallszahlengeneratoren hängt von der spezifischen Implementierung und dem Algorithmus ab, der zur Erzeugung der Zufallszahlen verwendet wird. Die meisten modernen Programmiersprachen wie MQL5, Python, C++, C#, Java und andere verfügen über eingebaute Pseudo-Zufallszahlengeneratoren, die für die meisten gängigen Anwendungen Zufallszahlen von recht guter Qualität liefern.

Im Allgemeinen sind die in Programmiersprachen eingebauten Zufallszahlengeneratoren für die meisten gängigen Aufgaben geeignet, aber für Aufgaben, die ein hohes Maß an Zufälligkeit oder Sicherheit erfordern, lohnt es sich, nach speziellen Lösungen zu suchen.

Für Aufgaben, die ein hohes Maß an Zufälligkeit und Sicherheit erfordern, können spezielle Lösungen zur Erzeugung von Zufallszahlen verwendet werden. Einige dieser Lösungen sind:

1. Kryptographische Zufallszahlengeneratoren. Diese Generatoren sind für den Einsatz in kryptografischen Anwendungen vorgesehen, die ein hohes Maß an Sicherheit erfordern. Sie bieten Zufälligkeit, Widerstand gegen Vorhersage und Widerstand gegen Kryptoanalyse.
2. Hardware-Zufallszahlengeneratoren. Diese Generatoren nutzen physikalische Prozesse wie thermisches Rauschen oder Quantenphänomene, um Zufallszahlen zu erzeugen. Sie liefern echte Zufallszahlen und werden häufig in Bereichen eingesetzt, in denen ein hohes Maß an Zufälligkeit erforderlich ist.
3. Bibliotheken zur Erzeugung von Zufallszahlen. Es gibt spezialisierte Bibliotheken, die komplexere Algorithmen zur Erzeugung von Zufallszahlen bereitstellen als die standardmäßig in Programmiersprachen eingebauten Generatoren. Die OpenSSL-Bibliothek bietet zum Beispiel kryptografische Funktionen, einschließlich der Erzeugung von Zufallszahlen.

Einige der gebräuchlichsten Algorithmen, die in integrierten Zufallszahlengeneratoren in Programmiersprachen verwendet werden können, sind:

1. Linearer Kongruenzgenerator (LCG). Dies ist einer der einfachsten und am häufigsten verwendeten Algorithmen zur Erzeugung von Pseudozufallszahlen. Er hat Nachteile, wie z. B. eine kurze Periode und einen geringen Grad an Zufälligkeit.
2. Mersenne-Twister. Dieser Algorithmus hat eine lange Periode und einen hohen Grad an Zufälligkeit und wird häufig in vielen Programmiersprachen verwendet.
3. Xorshift. Hierbei handelt es sich um eine Familie von Algorithmen zur Erzeugung von Pseudozufallszahlen, die einen hohen Grad an Zufälligkeit und eine hohe Geschwindigkeit aufweisen.
4. PCG (Permutierter Kongruenzgenerator). Diese relativ neue Klasse von Generatoren bietet ein gutes Gleichgewicht zwischen Zufallsqualität und Leistung.

Die Wahl eines Zufallszahlengenerators hängt von den spezifischen Anforderungen Ihrer Aufgaben ab. Im Folgenden finden Sie einige Überlegungen, die Ihnen bei Ihrer Entscheidung helfen können:

1. Qualität der Zufälligkeit. Wenn Ihre Anwendung ein hohes Maß an Zufälligkeit erfordert, insbesondere für kryptografische Zwecke, sollten Sie spezielle kryptografische Zufallszahlengeneratoren verwenden, z. B. kryptografisch sichere Pseudo-Zufallszahlengeneratoren (CSPRNGs).
2. Leistung. Wenn Ihnen die Geschwindigkeit der Zufallszahlengenerierung wichtig ist, sind leistungsfähigere Algorithmen wie Xorshift oder PCG möglicherweise vorzuziehen.
3. Periode und Qualität. Einige Algorithmen, wie z. B. Mersenne Twister, haben eine lange Periode und eine gute Qualität der Zufälligkeit.
4. Nutzerfreundlichkeit. Für einige Entwickler ist es wichtig, dass der Zufallszahlengenerator leicht zugänglich und einfach zu bedienen ist. Integrierte Generatoren, wie sie von Standardprogrammiersprachenbibliotheken bereitgestellt werden, können in solchen Fällen praktisch sein.

Wenn Sie ein kryptografisches Sicherheitsniveau benötigen, empfiehlt es sich, spezialisierte kryptografische Zufallszahlengeneratoren zu verwenden, z. B. CryptoRandom in Python oder SecureRandom in Java. Wenn Sie ein Gleichgewicht zwischen Leistung und Qualität der Zufälligkeit wünschen, sind Algorithmen wie Mersenne Twister oder PCG eine gute Wahl.

Es ist auch wichtig, daran zu denken, dass Sicherheit und Zufälligkeit eine Schlüsselrolle bei der Systemzuverlässigkeit und -sicherheit spielen, sodass die Wahl des Generators durchdacht und auf die Anforderungen der spezifischen Anwendung abgestimmt sein sollte. In diesem Artikel interessieren wir uns jedoch für den Einfluss der RNG-Qualität auf die Ergebnisse von Optimierungsalgorithmen. Ich werde meine Forschung ausschließlich in diesem Kontext durchführen.

Mersenne-Twister

Unter den vielen verfügbaren Zufallszahlengeneratoren ist es nicht einfach, einen zu finden, der eine hohe Qualität der Generierung und gleichzeitig eine akzeptable Geschwindigkeit bietet. Schließlich hat die Generierungsgeschwindigkeit einen erheblichen Einfluss auf die Gesamtausführungszeit des Optimierungsprozesses.

Daher ist die Wahl eines zuverlässigen Generators eine wichtige Frage, die ein Gleichgewicht zwischen der Qualität der Zufallszahlen und ihrer Generierungsgeschwindigkeit erfordert. Es muss eine optimale Lösung gefunden werden, die eine ausreichende Qualität der Erzeugung gewährleistet, ohne unnötig viel Zeit für diesen Prozess aufzuwenden.

Hardware-Generatoren sind für die meisten Nutzer nur schwer zugänglich, sodass wir sie an dieser Stelle gleich ausklammern. Unter den Software-Generatoren ist der hochwertige Mersenne-Generator weithin bekannt.

Mersenne Twister ist ein Algorithmus zur Erzeugung pseudozufälliger Zahlen, der 1997 von Makoto Matsumoto und Takuji Nishimura entwickelt wurde. Er ist einer der am häufigsten verwendeten Algorithmen zur Erzeugung von Zufallszahlen, da er eine gute Kombination aus langer Periode, guter Zufallsqualität und relativ hoher Leistung bietet.

Die wichtigsten Merkmale des Mersenne Twisters:

• Lange Periode. Der Mersenne Twister hat eine sehr lange Periode, d. h. er kann eine große Anzahl eindeutiger Pseudozufallszahlen erzeugen, bevor die Folge beginnt, sich zu wiederholen.
• Gute Qualität des Zufalls. Der Algorithmus gewährleistet eine gute Qualität der Zufälligkeit, d. h. die erzeugten Zahlen sollten den statistischen Eigenschaften von Zufallszahlen entsprechen.
• Leistung. Der Mersenne Twister hat eine gute Leistung, die ihn für viele Anwendungen attraktiv macht.

Das Funktionsprinzip des Mersenne-Twisters basiert auf einer linear rekurrenten Methode zur Erzeugung von Pseudo-Zufallszahlen. Der Algorithmus verwendet eine große Zahl (in der Regel 32- oder 64-Bit) als Zustand des Generators, die dann mit Hilfe komplexer Operationen umgewandelt wird, um die nächste Pseudozufallszahl zu erzeugen. In unserem Fall werden wir einen 64-Bit-Generator verwenden.

Betrachten wir die Klasse MersenneTwister64, die einen Pseudo-Zufallszahlengenerator auf der Grundlage des Mersenne-Twister-Algorithmus für 64-Bit-Zahlen implementiert. Nachfolgend finden Sie eine kurze Beschreibung der Methoden und Funktionen des Programms:

• Init - Methode zur Initialisierung des Zufallszahlengenerators. Sie nimmt einen Seed (Anfangswert) als Argument und setzt die internen Variablen der Klasse. Das MT-Array (Mersenne-Array) wird mit Werten gefüllt, die auf dem Seed basieren.
• RND_ulong - Methode, die eine zufällige 64-Bit-Ganzzahl ohne Vorzeichen zurückgibt. Wenn der aktuelle Index größer als 312 ist, wird die Methode twist() aufgerufen, um die Werte im MT-Array zu aktualisieren. Dann werden mehrere bitweise Schiebe- und XOR-Operationen durchgeführt, um eine Zufallszahl zu erzeugen. Der Indexwert wird um 1 erhöht, bevor das Ergebnis zurückgegeben wird.
• RND_ulong_In_Range - Methode, die eine zufällige 64-Bit-Ganzzahl ohne Vorzeichen innerhalb eines bestimmten Bereichs (einschließlich der Grenzen) zurückgibt. Wenn min und max gleich sind, wird min zurückgegeben. Wenn min größer als max ist, werden die Werte von min und max vertauscht. Anschließend wird die Methode RND_ulong() aufgerufen, um eine Zufallszahl zu erzeugen, die so verschoben und skaliert wird, dass sie in den angegebenen Bereich fällt.
• twist - interne Methode, die die „Misch“-Operation des MT-Arrays durchführt. Für jedes Array-Element erfolgt eine Kombination benachbarter Elemente durch bitweises Verschieben und bitweise XOR-Operationen. Der Indexwert wird auf 0 gesetzt, nachdem die Schiebeoperation durchgeführt wurde.

//——————————————————————————————————————————————————————————————————————————————
class MersenneTwister64
{
public: //--------------------------------------------------------------------

  void Init (ulong seed)
  {
    index = 312;

    MT [0] = seed;
    for (int i = 1; i < 312; i++)
    {
      MT [i] = (6364136223846793005 * (MT [i - 1] ^ (MT [i - 1] >> 62)) + i) & 0xFFFFFFFFFFFFFFFF;
    }
  }

  //from 0 to 18 446 744 073 709 551 615
  ulong RND_ulong ()
  {
    if (index >= 312)
    {
      twist ();
    }

    ulong y = MT [index];
    y = y ^ (y >> 29) & 0x5555555555555555;
    y = y ^ (y << 17) & 0x71D67FFFEDA60000;
    y = y ^ (y << 37) & 0xFFF7EEE000000000;
    y = y ^ (y >> 43);

    index++;
    return y;
  }

  ulong RND_ulong_In_Range (ulong min, ulong max)
  {
    if (min == max) return min;
    if (min > max)
    {
      ulong temp = min;
      min = max;
      max = temp;
    }
    return min + RND_ulong () % (max - min + 1);
  }

private: //-------------------------------------------------------------------
  ulong MT [312];
  int index;

  void twist ()
  {
    for (int i = 0; i < 312; i++)
    {
      ulong y = (MT [i] & 0x8000000000000000) + (MT [(i + 1) % 312] & 0x7FFFFFFFFFFFFFFF);
      MT [i] = MT [(i + 156) % 312] ^ (y >> 1);
      if (y % 2 != 0)
      {
        MT [i] = MT [i] ^ 0xB5026F5AA96619E9;
      }
    }
    index = 0;
  }
};
//——————————————————————————————————————————————————————————————————————————————

Vergleich von Zufallszahlengeneratoren und Testergebnissen

Versuchen wir, die Arbeit von zwei Zufallszahlengeneratoren visuell zu vergleichen: den in MQL5 eingebauten (im Folgenden „Standard“ genannt) und den Mersenne Twister. Zu diesem Zweck haben wir zwei Bilder erstellt und ihr Aussehen analysiert. Auf den ersten Blick sind beide Bilder frei von Mustern und Periodizität, und ihr Design ist homogen. Wir können keine offensichtlichen optischen Unterschiede zwischen den Generatoren feststellen.

Das mit dem Standardgenerator erzeugte Bild

Das vom Mersenne-Twister-Generator erzeugte Bild

Für einen objektiveren Vergleich von Zufallszahlengeneratoren empfiehlt es sich jedoch, statistische Tests zu verwenden, mit denen der Grad der Zufälligkeit und die statistischen Eigenschaften der generierten Zahlen bewertet werden können. Es ist wichtig zu beachten, dass die visuelle Bewertung begrenzt sein kann und nicht immer in der Lage ist, versteckte systematische Abweichungen von der echten Zufälligkeit zu erkennen.

Für einen genaueren Vergleich der Generatoren werden wir daher eine zusätzliche Analyse mit einem statistischen Test durchführen, um zuverlässigere Ergebnisse zu erhalten. Wir interessieren uns für die Gleichmäßigkeit und verwenden daher den Chi-Quadrat-Test, einen statistischen Test, der die Gleichmäßigkeit der zufällig generierten Zahlen bewertet. In diesem Fall gab es 10.000 Beobachtungen, die jeweils 10.000 generierte Werte enthielten.

Der Chi-Quadrat-Test (χ²-Test) wird zur Prüfung der Gleichmäßigkeit der Datenverteilung verwendet. Damit lässt sich feststellen, wie genau die beobachteten Häufigkeiten denen entsprechen, die bei einer gleichmäßigen Verteilung zu erwarten wären.

Der kritische Wert für das Signifikanzniveau von 0,05 beim Chi-Quadrat-Test (χ²-Test) mit 9999 Freiheitsgraden (10.000 Beobachtungen minus 1) beträgt 10232,73727. Dieser Wert ist eine Konstante, die zum Vergleich der erwarteten Häufigkeiten mit den beobachteten Häufigkeiten im Chi-Quadrat-Test verwendet wird. Er wird aus der Chi-Quadrat-Tabelle der Verteilung entnommen und hilft zu bestimmen, wie signifikant die Unterschiede zwischen beobachteten und erwarteten Werten sind.

Bei der Durchführung des Chi-Quadrat-Tests wird die berechnete Statistik mit dem kritischen Wert verglichen. Wenn die berechnete Statistik größer als der kritische Wert ist, kann die Nullhypothese, dass die Verteilung mit der erwarteten übereinstimmt, zurückgewiesen werden. Andernfalls wird die Nullhypothese akzeptiert.

Schauen wir uns einen Abschnitt des Testskript-Codes an (im Allgemeinen erstellt das Skript Bilder, misst die Ausführungszeit von Generatoren und berechnet den Chi-Quadrat-Test).

Es werden zwei Arrays erstellt und initialisiert: „observed“ und „expected“. Das Array „observed“ wird verwendet, um die beobachtete Anzahl von Zufallszahlen in jedem der BoxesNumber-Intervalle zu speichern. Das Array „expected“ enthält die erwartete Anzahl der Zufallszahlen in jedem Intervall, wenn die Generatoren mit einer perfekten Gleichverteilung arbeiten würden.

Der Code prüft dann den Wert der Variablen StandardRND, die angibt, welcher Zufallszahlengenerator zu verwenden ist. Wenn StandardRND 'true' ist, wird der Standard-Zufallszahlengenerator in MQL5 verwendet. Ansonsten wird der Mersenne-Twister-Generator verwendet. Die Schleife erzeugt Zufallszahlen und inkrementiert das entsprechende Element des Arrays „observed“ für das Intervall.

Nachdem die Zufallszahlen generiert wurden, wird die Chi-Quadrat-Statistik berechnet. Für jedes Intervall wird der Wert „(beobachtet - erwartet)^2 / erwartet“ berechnet und in der Variablen „chiSquareStatistic“ summiert. Der kritische Wert „chiSquareCriticalValue“ wird dann für das Signifikanzniveau von 0.05* festgelegt.

Die Vergleichsergebnisse werden am Ende des Codes angezeigt. Wenn der Wert von „chiSquareStatistic“ größer ist als „chiSquareCriticalValue“, wird eine Meldung angezeigt, dass die Nullhypothese abgelehnt wird: Die Verteilung weicht von den Erwartungen ab. Andernfalls wird eine Meldung angezeigt, dass die Nullhypothese nicht zurückgewiesen wird: Die Verteilung stimmt mit der erwarteten Verteilung überein.

* - Das Signifikanzniveau von 0,05 (oder 5 %) ist eines der gängigsten Signifikanzniveaus und wird in vielen Bereichen der wissenschaftlichen Forschung verwendet. Das bedeutet, dass wir bei der Durchführung eines statistischen Tests mit einem Signifikanzniveau von 0,05 eine 5 %ige Chance eines Fehlers vom Typ I zulassen. Das Signifikanzniveau in der Statistik ist ein Schwellenwert, der verwendet wird, um Entscheidungen über die statistische Signifikanz von Ergebnissen zu treffen. Sie wird in der Regel als α (alpha) bezeichnet und stellt die Wahrscheinlichkeit eines Fehlers vom Typ I dar, d. h. die Wahrscheinlichkeit der Zurückweisung einer wahren Nullhypothese.

int observed [];
ArrayResize     (observed, BoxesNumber);
ArrayInitialize (observed, 0);

int expected [];
ArrayResize     (expected, BoxesNumber);
ArrayInitialize (expected, ThrowsNumber / BoxesNumber);

if (StandardRND)
{
  Print ("Standard, ", ThrowsNumber, " throws, ", BoxesNumber, " boxes");
  for (int i = 0; i < ThrowsNumber; i++)
  {
    observed [rndS.RNDintInRange (0, BoxesNumber - 1)]++;
  }
}
else
{
  Print ("Mersenne, ", ThrowsNumber, " throws, ", BoxesNumber, " boxes");
  for (int i = 0; i < ThrowsNumber; i++)
  {
    observed [(int)rndM.RND_ulong_In_Range (0, BoxesNumber  - 1)]++;
  }
}

// Calculate the chi-square statistic
double chiSquareStatistic = 0;
for (int i = 0; i < ArraySize(observed); i++)
{
  chiSquareStatistic += MathPow(observed[i] - expected[i], 2) / expected[i];
}

// Critical value for the significance level of 0.05
double chiSquareCriticalValue = 10232.73727; //10000

// Output results
if (chiSquareStatistic > chiSquareCriticalValue)
{
  Print("We reject the null hypothesis: The distribution differs from the expected one.");
}
else
{
  Print("We do not reject the null hypothesis: The distribution is consistent with the expected one.");
}

Lassen Sie das Skript 5 Mal laufen, um Statistiken und die Ausführungszeit eines Standardgenerators zu berechnen. Die Ausführungszeit des Mersenne-Twister-Generators wird zur gleichen Zeit gemessen. Berechnen wir den Unterschied in der Ausführungszeit als Quotient aus der Ausführungszeit des Twister und des Standardgenerators.

2024.03.18 20:54:33.456    stand: 120353 mcs
2024.03.18 20:54:33.456    mers : 397920 mcs
2024.03.18 20:54:33.456    diff : 3.3062740438543283
2024.03.18 20:54:33.459    Standard, 100000000 throws, 10000 boxes
2024.03.18 20:54:33.854    We reject the null hypothesis: The distribution differs from the expected one.
2024.03.18 20:54:38.802    stand: 121670 mcs
2024.03.18 20:54:38.802    mers : 403180 mcs
2024.03.18 20:54:38.802    diff : 3.3137174323991125
2024.03.18 20:54:38.805    Standard, 100000000 throws, 10000 boxes
2024.03.18 20:54:39.194    We reject the null hypothesis: The distribution differs from the expected one.
2024.03.18 20:54:43.767    stand: 121222 mcs
2024.03.18 20:54:43.767    mers : 400986 mcs
2024.03.18 20:54:43.767    diff : 3.3078649090099157
2024.03.18 20:54:43.770    Standard, 100000000 throws, 10000 boxes
2024.03.18 20:54:44.156    We reject the null hypothesis: The distribution differs from the expected one.
2024.03.18 20:54:48.476    stand: 119246 mcs
2024.03.18 20:54:48.476    mers : 400319 mcs
2024.03.18 20:54:48.476    diff : 3.3570853529678146
2024.03.18 20:54:48.479    Standard, 100000000 throws, 10000 boxes
2024.03.18 20:54:48.873    We reject the null hypothesis: The distribution differs from the expected one.
2024.03.18 20:54:53.144    stand: 119309 mcs
2024.03.18 20:54:53.144    mers : 404502 mcs
2024.03.18 20:54:53.144    diff : 3.390372897266761
2024.03.18 20:54:53.148    Standard, 100000000 throws, 10000 boxes
2024.03.18 20:54:53.553    We reject the null hypothesis: The distribution differs from the expected one.

Leider fiel der Standard-Zufallszahlengenerator bei allen fünf Tests durch, als er mit dem Chi-Quadrat-Test getestet wurde, was darauf hindeutet, dass es systematische Abweichungen von der erwarteten gleichmäßigen Zufallsverteilung gab.

Nun werden wir den Mersenne Twister testen, während wir weiterhin die Ausführungszeit beider Generatoren messen.

2024.03.18 20:55:48.133    stand: 115447 mcs
2024.03.18 20:55:48.133    mers : 413258 mcs
2024.03.18 20:55:48.133    diff : 3.57963394458063
2024.03.18 20:55:48.138    Mersenne, 100000000 throws, 10000 boxes
2024.03.18 20:55:49.504    We do not reject the null hypothesis: The distribution is consistent with the expected one.
2024.03.18 20:55:56.340    stand: 117433 mcs
2024.03.18 20:55:56.340    mers : 402337 mcs
2024.03.18 20:55:56.340    diff : 3.4260982858310696
2024.03.18 20:55:56.346    Mersenne, 100000000 throws, 10000 boxes
2024.03.18 20:55:57.717    We do not reject the null hypothesis: The distribution is consistent with the expected one.
2024.03.18 20:56:05.837    stand: 120129 mcs
2024.03.18 20:56:05.837    mers : 400705 mcs
2024.03.18 20:56:05.837    diff : 3.3356225391037966
2024.03.18 20:56:05.843    Mersenne, 100000000 throws, 10000 boxes
2024.03.18 20:56:07.219    We do not reject the null hypothesis: The distribution is consistent with the expected one.
2024.03.18 20:56:12.206    stand: 119980 mcs
2024.03.18 20:56:12.206    mers : 397436 mcs
2024.03.18 20:56:12.206    diff : 3.312518753125521
2024.03.18 20:56:12.211    Mersenne, 100000000 throws, 10000 boxes
2024.03.18 20:56:13.582    We do not reject the null hypothesis: The distribution is consistent with the expected one.
2024.03.18 20:56:18.837    stand: 118140 mcs
2024.03.18 20:56:18.837    mers : 397565 mcs
2024.03.18 20:56:18.837    diff : 3.3652023023531403
2024.03.18 20:56:18.842    Mersenne, 100000000 throws, 10000 boxes
2024.03.18 20:56:20.220    We do not reject the null hypothesis: The distribution is consistent with the expected one.

Der Mersenne-Wirbel bewältigte die Aufgabe in allen fünf Tests (Durchläufe des Chi-Quadrat-Tests). Gleichzeitig sehen wir, dass der Generator einen erheblichen Nachteil hat - Twister ist etwa 3,4-mal langsamer als der Standardgenerator, was die Geschwindigkeit von Optimierungsalgorithmen erheblich beeinträchtigen kann.

Jetzt kommt der interessanteste Teil - der Höhepunkt dieser Studie: Wir werden Tests durchführen, um herauszufinden, wie sehr die Qualität der Zufallszahlengeneratoren die Optimierungsergebnisse beeinflusst. Wie Sie sich vielleicht erinnern, erzeugt der Standardgenerator Zahlen im Bereich [0;32.767], während der 64-Bit Mersenne Twister - im Bereich [0;18.446.744.073.709.551.615].

Zur Durchführung des Experiments wurden 50 Hilly-Funktionen ausgewählt und 10.000 Iterationen für jede Funktion durchgeführt. Warum habe ich mich für die 50 Merkmale von Hilly entschieden und warum Hilly? Erstens wurde diese Zahl so gewählt, dass der Algorithmus in einer begrenzten Anzahl von Durchläufen der Fitnessfunktion keine 100%ige Konvergenz erreichen kann. Auf diese Weise konnten die Unterschiede bei der Verwendung der verschiedenen Arten von Zufallszahlengeneratoren festgestellt werden. Zweitens ist die Wahl der Hilly-Funktionen auf ihre Glattheit zurückzuführen, die es uns ermöglicht, die natürliche Streuung der Ergebnisse zu vermeiden, die bei der Erzeugung von Zufallszahlen nicht auftreten würde, wenn wir eine diskrete Testfunktion verwenden würden. Ich habe das Experiment 20 Mal wiederholt und die Ergebnisse gemittelt, um zuverlässigere und statistisch signifikante Daten zu erhalten. Als Optimierungsalgorithmus haben wir BGA gewählt, der in unserer Bewertungstabelle an erster Stelle steht und gleichzeitig eine sehr geringe Streuung der Ergebnisse bei glatten Funktionen aufweist.

Aus dem Ausdruck der Ergebnisse ist ersichtlich, dass die Optimierungsergebnisse für den BGA-Algorithmus bei Verwendung eines Standard-Zufallszahlengenerators und eines Mersenne-Generators fast gleich sind. Die Unterschiede sind nur in der dritten Dezimalstelle zu beobachten, die für unsere Zwecke unkritisch sind und als recht gering angesehen werden.

//Standard
C_AO_BGA:50:50:1.0:3:0.001:0.7:16
=============================
50 Hilly's; Func runs: 10000; result: 0.9257245560389498
=============================
All score: 0.92572

//Mersenne
C_AO_BGA:50:50:1.0:3:0.001:0.7:16
=============================
50 Hilly's; Func runs: 10000; result: 0.9221148477644971
=============================
All score: 0.92211

Bei der Visualisierung der Funktionsweise des Algorithmus konnten wir keine signifikanten Abweichungen feststellen, wenn zwei verschiedene Arten von Zufallszahlengeneratoren innerhalb der Algorithmuslogik verwendet wurden. Der Unterschied in der Streuung der Ergebnisse liegt im Rahmen der Variabilität des Algorithmus selbst.

BGA mit dem Standardgenerator 

BGA mit Mersenne Twister

Die vorläufige Schlussfolgerung lautet: Die Qualität der Zufallszahlengeneratoren hat keinen Einfluss auf die Leistung der Optimierungsalgorithmen.

Wir gehen davon aus, dass der leichte Unterschied in den Ergebnissen bei Verwendung der oben genannten Generatoren im BGA-Optimierungsalgorithmus darauf zurückzuführen ist, dass bei BGA jedes Bit im Chromosom unabhängig von den anderen Bits erzeugt wird. Die Rolle der Zufallsgeneratoren beschränkt sich nämlich auf die boolesche „Ja/Nein“-Operation, und der Unterschied zwischen der Anzahl der „Ja“- und „Nein“-Ereignisse beträgt nur Tausendstel Prozent.

Für einen binären genetischen Algorithmus gibt es also keinen Unterschied bei der Verwendung von Zufallszahlengeneratoren, obwohl diese Schlussfolgerung auf den ersten Blick gar nicht so offensichtlich war, aber gilt das auch für andere Optimierungsalgorithmen, insbesondere für solche, die kontinuierliche Wahrscheinlichkeiten in dem durch [min, max] begrenzten Raum durch Koordinaten verwenden?

Versuchen wir, einige weitere Experimente durchzuführen, um die gewonnene Aussage zu bestätigen oder zu widerlegen. Diesmal nehmen wir den (P_O)ES-Algorithmus, der zu den Spitzenreitern in unserer Bewertungstabelle gehört und in seiner Logik eine große Anzahl von Operationen mit Zufallszahlen verwendet sowie kontinuierliche Wahrscheinlichkeiten auf den gesamten Suchraum anwendet.

(P_O)ES on five test runs with the standard random generator:

C_AO_(P_O)ES:100:150:0.02:8.0:10
=============================
50 Hilly's; Func runs: 10000; result: 0.9611258962207798
=============================
All score: 0.96113

C_AO_(P_O)ES:100:150:0.02:8.0:10
=============================
50 Hilly's; Func runs: 10000; result: 0.9515388684155862
=============================
All score: 0.95154

C_AO_(P_O)ES:100:150:0.02:8.0:10
=============================
50 Hilly's; Func runs: 10000; result: 0.9374143219597522
=============================
All score: 0.93741

C_AO_(P_O)ES:100:150:0.02:8.0:10
=============================
50 Hilly's; Func runs: 10000; result: 0.9408961932771648
=============================
All score: 0.94090

C_AO_(P_O)ES:100:150:0.02:8.0:10
=============================
50 Hilly's; Func runs: 10000; result: 0.9533447716768805
=============================
All score: 0.95334

(P_O)ES on five test runs with Mersenne Twister generator:

C_AO_(P_O)ES:100:150:0.02:8.0:10

=============================
50 Hilly's; Func runs: 10000; result: 0.9726583883537465
=============================
All score: 0.97266

C_AO_(P_O)ES:100:150:0.02:8.0:10
=============================
50 Hilly's; Func runs: 10000; result: 0.9699307111435692
=============================
All score: 0.96993

C_AO_(P_O)ES:100:150:0.02:8.0:10
=============================
50 Hilly's; Func runs: 10000; result: 0.9864631937799934
=============================
All score: 0.98646

C_AO_(P_O)ES:100:150:0.02:8.0:10
=============================
50 Hilly's; Func runs: 10000; result: 0.9608040257741147
=============================
All score: 0.96080

C_AO_(P_O)ES:100:150:0.02:8.0:10
=============================
50 Hilly's; Func runs: 10000; result: 0.9540192199550924
=============================
All score: 0.95402

Wie aus den Ergebnissen der durchgeführten Experimente ersichtlich ist, bezog sich die erste Versuchsreihe auf die Verwendung des Standard-Zufallszahlengenerators im Algorithmus. Wir sehen, dass der durchschnittliche Ergebniswert bei etwa 0,95 liegt, und der durchschnittliche Ergebniswert bei Verwendung des Mersenne Twisters bei 0,96, was keinen signifikanten Unterschied macht, aber uns zeigt, dass die Ergebnisse der Experimente immer noch höher sind, wenn der Mersenne Twister vorhanden ist. Beachten Sie jedoch, dass der Zeitaufwand für diesen Algorithmus die Laufzeit des Standardalgorithmus um das 3,5-fache übersteigt.

Zusammenfassung

Daher haben wir ein interessantes Experiment durchgeführt, um die Frage zu klären, die viele Händler beschäftigt: Ist die Qualität von Zufallszahlengeneratoren wichtig, wenn sie in Verbindung mit Optimierungsalgorithmen verwendet werden? Ich habe noch nie eine solche Studie im öffentlichen Bereich gesehen.

Bei einigen Algorithmen, die boolesche Operationen verwenden, wie z. B. BGA, und bei Algorithmen, die Zufallszahlen in einem kleinen diskreten Bereich verwenden, wie z. B. DE (differentielle Evolution, bei der Zufallszahlen zur Auswahl der Eltern in einer Population verwendet werden), spielt die RNG-Qualität fast keine Rolle.

Bei anderen Algorithmen, die Zufallszahlen verwenden, um neue Lösungen über den gesamten Bereich der optimierten Parameter zu generieren, wie z. B. (P_O)ES (die meisten Populationsalgorithmen sind ähnlich), spielt der RNG eine untergeordnete Rolle bei der Anpassung an den Messfehler. Wichtig ist, dass der höherwertige Mersenne-Twister-Generator 3,5 Mal langsamer ist als der Standardgenerator.

Bei Optimierungsproblemen spielt das Gleichgewicht zwischen Qualität und Berechnungszeit sicherlich eine wichtige Rolle. Letztendlich entscheiden wir uns in diesem Fall für die Geschwindigkeit. Der Anstieg der Algorithmusergebnisse durch die Verwendung hochwertiger Generatoren liegt innerhalb des Messfehlers, während die Geschwindigkeit deutlich sinkt.

Das Archiv mit den Codes der durchgeführten Tests ist unten beigefügt. Die in dem Artikel dargelegten Schlussfolgerungen und Urteile beruhen auf den Ergebnissen der Versuche.