Vergleich zweier genetischer Algorithmen

9

Ich habe zwei Implementierungen eines genetischen Algorithmus, die sich gleichwertig verhalten sollen. Aufgrund technischer Einschränkungen, die nicht gelöst werden können, ist ihre Ausgabe bei gleicher Eingabe jedoch nicht exakt gleich.

Trotzdem möchte ich zeigen, dass es keinen signifikanten Leistungsunterschied gibt.

Ich habe 20 Läufe mit der gleichen Konfiguration für jeden der beiden Algorithmen, wobei unterschiedliche anfängliche Zufallszahlen verwendet werden. Für jeden Lauf und jede Generation wurde die minimale Fehlerfähigkeit des besten Individuums in der Population aufgezeichnet. Der Algorithmus verwendet einen Elite-Erhaltungsmechanismus, so dass die Fitness des besten Individuums monoton abnimmt. Ein Lauf besteht aus 1000 Generationen, also habe ich 1000 Werte pro Lauf. Ich kann nicht mehr Daten erhalten, da die Berechnungen sehr teuer sind.

Welchen Test soll ich anwenden? Ein einfacher Weg wäre wahrscheinlich, nur den Fehler in den letzten Generationen zu vergleichen (wieder, welchen Test würde ich hier verwenden)? Man könnte aber auch darüber nachdenken, das Konvergenzverhalten im Allgemeinen zu vergleichen.

nisc
quelle
Nur zur Klarstellung: Ist es nicht so, dass ein genetischer Algorithmus zufällig nach einer Lösung sucht, so dass das erste Segment eines Laufs wahrscheinlich keine lohnende Lösung ergibt? Was genau meinen Sie mit "dem minimalen Fehler in der Bevölkerung"? Wenn Sie die minimale Differenz zwischen einem bekannten wahren Wert und einer Lösung aus den 1000 Werten in einem Lauf meinen, ist das dann nicht eine voreingenommene Anzeige des Laufergebnisses? Schließlich würden Sie in der Praxis die endgültige Lösung in jedem Lauf akzeptieren und alles ablehnen, was davor steht, oder?
whuber
Mit Fehler meine ich im Grunde 1 / Fitness, also spreche ich über den Wert des besten Individuums in einer Generation. Ich habe den Fitnesswert des besten Individuums für jede Generation aufgezeichnet. Ich habe also 1000 * 20 * 2 Zahlen, die jeweils der "Fitness" des besten Individuums in einer bestimmten Generation eines bestimmten Laufs entsprechen.
Nisc
Ich denke, die anfängliche Frage war schlecht gestellt, ich habe einige Klarstellungen hinzugefügt ..
Nisc

Antworten:

9

Das Testen stochastischer Algorithmen kann ziemlich schwierig sein!

Ich arbeite in der Systembiologie und es gibt viele stochastische Simulatoren, mit denen ein Modell simuliert werden kann. Das Testen dieser Simulatoren ist schwierig, da zwei Realisierungen aus einem einzelnen Modell normalerweise unterschiedlich sind.

In den dsmts haben wir (analytisch) den erwarteten Wert und die Varianz eines bestimmten Modells berechnet. Anschließend führen wir einen Hypothesentest durch, um festzustellen, ob ein Simulator von der Wahrheit abweicht. Abschnitt 3 des Benutzerhandbuchs enthält die Einzelheiten. Im Wesentlichen führen wir einen t-Test für die Mittelwerte und einen Chi-Quadrat-Test für Varianzen durch.

In Ihrem Fall vergleichen Sie zwei Simulatoren, daher sollten Sie stattdessen nur einen T-Test mit zwei Stichproben verwenden.

csgillespie
quelle
Wie würde ich die Informationen aller Generationen nutzen?
Nisc
Am einfachsten ist es, mehrere Tests durchzuführen, dh Tests bei jeder Generation, und dann eine Bonferroni- oder fdr-Korrektur zu verwenden.
Csgillespie
Beim Vergleich bei jeder Generation müsste ich bei einem Signifikanzniveau von 1/1000 * 0,05 testen? Ist das nicht ein bisschen hart?
Nisc
Stimmt, aber Sie führen auch viele Tests durch - können nicht alles haben;) Sie können die p-Werte einstufen und sie als Richtlinie verwenden, um festzustellen, wo mögliche Fehler auftreten können.
Csgillespie
1
Anstelle der Bonferroni-Korrektur können Sie auch immer das stärkere Bonferroni-Holm verwenden. Siehe meine Antwort hier: stats.stackexchange.com/questions/575/…
Henrik
4

Vielleicht könnten Sie die durchschnittliche Differenz zwischen zwei Läufen desselben Algorithmus zur durchschnittlichen Differenz zwischen zwei Läufen verschiedener Algorithmen messen. Löst nicht das Problem, wie dieser Unterschied gemessen werden kann, könnte aber ein leichter zu handhabendes Problem sein. Und die einzelnen Werte der Zeitreihen würden in die Differenzberechnung einfließen, anstatt als einzelne Datenpunkte behandelt werden zu müssen, um gegeneinander ausgewertet zu werden (ich denke auch nicht, dass der besondere Unterschied im n-ten Schritt das ist, was Sie wirklich wollen Aussagen machen über).

Update Bezüglich Details - Nun, welche Funktionen der Zeitreihe interessieren Sie über den endgültigen Fehler hinaus? Ich denke, Sie haben tatsächlich drei verschiedene Fragen zu lösen:

  1. Was bedeutet Ähnlichkeit für Sie, dh was meinen Sie, wenn Sie sagen, dass Sie nicht glauben, dass die beiden Methoden unterschiedlich sind?
  2. Wie quantifizieren Sie es - kann nach 1 beantwortet werden, und
  3. Wie können Sie auf signifikante Unterschiede zwischen Ihren beiden Methoden testen?

Alles, was ich im ersten Beitrag gesagt habe, war, dass die Antwort auf (1) wahrscheinlich nicht die individuellen Unterschiede bei jeder der 1000 Generationen berücksichtigt. Und dass ich empfehlen würde, einen Skalarwert für jede Zeitreihe oder zumindest eine Ähnlichkeit zwischen Zeitreihen zu erstellen. Erst dann gelangen Sie zur eigentlichen Statistikfrage (von der ich am wenigsten über alle drei Punkte weiß, aber mir wurde empfohlen, bei einer ähnlichen Frage, die ich gerade gestellt habe, einen gepaarten t-Test zu verwenden, wenn Sie einen Skalarwert pro Element haben).

user979
quelle
klingt vernünftig, noch mehr Details?
Nisc