Frage:
Wie kann überprüft werden, ob der modifizierte genetische Algorithmus signifikant besser ist als das Original?
Levon
2011-02-19 05:34:23 UTC
view on stackexchange narkive permalink

Meine Frage befasst sich mit der Frage, wie man behaupten kann, dass ein "verbesserter" Evolutionsalgorithmus tatsächlich verbessert wird (zumindest aus statistischer Sicht) und nicht nur zufälliges Glück (ein Problem angesichts der elastischen Natur dieser Algorithmen).

Nehmen wir an, ich habe es mit einer Standard-GA (vorher) und einer "verbesserten" GA (nachher) zu tun. Und ich habe eine Reihe von 8 Testproblemen.

Ich führe beide Algorithmen wiederholt aus, zum Beispiel 10 Mal (?) Durch jedes der 8 Testprobleme und notiere, wie viele Generationen es gedauert hat, bis sie aufgetreten sind mit der Lösung. Ich würde mit der gleichen anfänglichen zufälligen Population beginnen (unter Verwendung des gleichen Samens).

Würde ich einen gepaarten t-Test verwenden, um zu überprüfen, ob ein Unterschied (hoffentlich eine Verbesserung) zwischen den Durchschnittswerten für jede Testfrage bestehen würde statistisch signifikant? Sollte ich diese Algorithmen mehr als 10 Mal für jeden Test / jedes Paar ausführen?

Gibt es Fallstricke, die mir bekannt sein sollten? Ich gehe davon aus, dass ich diesen Ansatz für jeden (evolutionären) Algorithmusvergleich verwenden könnte.

Oder bin ich hier wirklich auf dem falschen Weg? Ich suche im Grunde nach einer Möglichkeit, zwei Implementierungen eines evolutionären Algorithmus zu vergleichen und zu berichten, wie gut eine im Vergleich zur anderen funktionieren könnte.

Danke!

@levon9 Ich habe den Titel neu formuliert, um ihn an die aktuelle Politik anzupassen (Satzkapitalisierung usw.). Bitte überprüfen Sie, ob ich die ursprüngliche Bedeutung nicht geändert habe.
@chl - konnte keine Möglichkeit finden, direkt eine Nachricht zu senden (ich lerne hier immer noch) - können Sie mich bitte auf die Richtlinie hinweisen? Ich fand den Teil darüber nicht "nur" Glück etwas relevant, da dies stochastische Prozesse sind und daher nicht deterministisch. Vielen Dank.
@levon9 Ok, ich habe den Titel auf den ursprünglichen zurückgesetzt. Informationen zu allgemeinen Richtlinien zu Titeln und Fragenformulierungen finden Sie in Meta [Gibt es einen Styleguide, der Richtlinien für Fragentitel und Frageninhalte enthält?] (Http://meta.stats.stackexchange.com/questions/575/is- Es gibt einen Styleguide, der Richtlinien für den Fragentitel und die Frage enthält. c).
@levon9 Die allgemeine Idee ist, den Titel zeigen zu lassen, worum es bei der Frage geht, vorzugsweise mit richtigen Worten. Die Satzkapitalisierungspolitik dient nur dazu, ein gewisses Maß an Ordnung herzustellen (die Leute spucken weniger auf saubere Böden).
Fünf antworten:
#1
+5
Boris Gorelik
2011-02-20 17:18:24 UTC
view on stackexchange narkive permalink

Ich habe meinen Algorithmus mit dem gepaarten t-Test mit GA verglichen, obwohl ich ungefähr 200 Testfälle hatte. Sie können eine nicht parametrische Alternative wie den Wilcoxon Ranks Test verwenden. Unabhängig davon, was Sie zum Testen der statistischen Signifikanz verwenden, berücksichtigen Sie die "reale" Signifikanz. Wenn die von Ihrem Algorithmus bereitgestellte Leistungsverbesserung unter den Messgrenzen oder unter einem praktischen Interesse liegt, spielt es keine Rolle, selbst wenn sie statistisch signifikant ist (d. H. "Guter" p-Wert).

Was hast du getestet? Durchschnittliche Anzahl von Generationen, wie vom OP vorgeschlagen? Unterschied zur (falls bekannt) optimalen Lösung? Eine Kombination von beidem? Wie testen Sie, ob ein Algorithmus eher in lokalen Optima stecken bleibt?
Ich habe den Unterschied zur bekannten optimalen Lösung mit ungefähr der gleichen Anzahl von Bewertungsfunktionsberechnungen getestet.
#2
+4
bayerj
2011-02-19 16:03:02 UTC
view on stackexchange narkive permalink

Es ist vielleicht nicht das, was Sie hören möchten, aber nach dem, was ich gesehen habe, wird der neue Algorithmus nur mit dem alten Algorithmus für Benchmark-Funktionen verglichen.

ZB. wie hier gemacht: Effiziente natürliche Evolutionsstrategien (Schaul, Sun Yi, Wierstra, Schmidhuber)

Vielen Dank für die Papierreferenz, ich werde es überprüfen. Lassen Sie mich, ohne das Papier gelesen zu haben, noch einmal betonen, dass auch ich Benchmark-Funktionen verwenden werde (das oben erwähnte Set). Ich möchte nur irgendwie quantifizieren können, dass meine (hoffentlich) besseren Zahlen nicht nur auf " Glück "aber statistisch signifikant. Das heißt, ich habe gesehen, dass Leute nur Zahlen gemeldet haben (wie die Zeit bis zur Ausführung oder die Anzahl der Bewertungen), aber ich bin nicht sicher, ob das ausreicht. Seien Sie neugierig auf andere Kommentare. Vielen Dank.
#3
+4
Matt Munson
2011-02-26 14:56:38 UTC
view on stackexchange narkive permalink

Sie würden keinen gepaarten Beispiel-T-Test verwenden. Der Grund dafür ist, dass nicht angenommen werden kann, dass ein bestimmter zufälliger Startwert das Ergebnis beider Algorithmen auf dieselbe Weise beeinflusst, selbst wenn dieser zufällige Startwert nur zur Erzeugung der Population verwendet wird und nicht für spätere Operationen wie Mutation und Selektion. Mit anderen Worten, es ist logisch möglich, dass sich eine bestimmte Population unter einem Algorithmus besser entwickelt als der Durchschnitt für diesen Algorithmus, unter einem anderen jedoch die entgegengesetzte Leistung erbringt. Wenn Sie Grund zu der Annahme haben, dass für beide Algorithmen ein ähnlicher Zusammenhang zwischen Seed und Leistung besteht, können Sie dies mithilfe eines Pearson-Korrelationskoeffizienten testen, um die Leistung jedes Seeds bei beiden Tests zu vergleichen. Standardmäßig würde ich jedoch davon ausgehen, dass keine Verbindung besteht, insbesondere wenn Sie eine relativ große Population haben.

Bei mehr als zehnmaliger Ausführung sind natürlich immer mehr Stichproben besser, obwohl Ihre Rechenressourcen kann offensichtlich ein begrenzender Faktor sein. Es könnte eine gute Idee sein, eine Leistungskurve zu erstellen, die Ihnen die Beziehung zwischen der Größe der Differenz, die für die statistische Signifikanz auf Alpha-Ebene erforderlich ist, und der SD und n zeigt. Mit anderen Worten, wie groß muss der Unterschied bei einem gegebenen n und SD sein? http://moon.ouhsc.edu/dthompso/CDM/power/hypoth.htm <-- Informationen zur Leistungskurve finden Sie unten auf der Seite.

Wenn Sie es sind Wenn Sie einen genetischen Algorithmus ausführen, der tatsächlich einen definierten Haltepunkt hat, wie Sie es tun, können Sie einfach einen ungepaarten T-Test für die Anzahl der Generationen durchführen, die erforderlich sind, um die Lösung zu finden. Andernfalls wird die Quantifizierung der Algorithmusleistung tendenziell etwas schwieriger

In Bezug auf Fallstricke und die Verallgemeinerbarkeit der Algorithmuseffizienz auf andere Probleme können Sie die Effektivität Ihres Algorithmus nicht als selbstverständlich betrachten, wenn Sie ihn auf andere Probleme portieren. Nach meiner Erfahrung müssen genetische Algorithmen normalerweise für jedes neue Problem, auf das Sie sie anwenden, erheblich angepasst werden. Abhängig davon, wie vielfältig Ihre 8 Tests sind, können sie Ihnen jedoch einen Hinweis darauf geben, wie verallgemeinerbar Ihre Ergebnisse sind und in welchem ​​Anwendungsbereich sie verallgemeinerbar sind.

Tolle Kommentare, sehr hilfreich. Nein, ich stimme Ihnen zu, ich würde keine Verbindung zwischen einem bestimmten Samen und einer Leistung beanspruchen. Ich hätte den Startsamen für jeden * Satz * von Läufen variiert. Ich wusste nichts über die Leistungskurve, klingt sehr nützlich, ich werde Ihren Link überprüfen und auch etwas mehr darüber nachlesen. Ich würde die Leistung meiner Algorithmen nicht über die verwendeten Probleme hinaus verallgemeinern, von denen ich hoffe, dass sie variiert werden, d. H. Unimodal, multimodal usw. Führen Sie die Algorithmen erneut bis zum "Abschluss" aus, sollte ich mir Gedanken über den Start-Seed machen? Wenn ja, warum konnte ich in diesem Fall nicht einfach den gepaarten T-Test verwenden?
.. fuhr fort .. Das heißt, es dauerte so viele Generationen "vor" und jetzt so viele "nach" den am Algorithmus vorgenommenen Änderungen. Ich muss über den ungepaarten T-Test-Ansatz nachdenken - mein Statistikwissen ist nicht sehr tiefgreifend (oder vollständig, daher habe ich festgestellt, dass diese Website sehr nützlich ist). Oh, ich plane, diesen Ansatz auch für PSOs zu verwenden die Linie.
Wenn Sie Seed X mit demselben Algorithmus ausführen, jedoch für unterschiedliche Zeiträume, können Sie den gepaarten t-Test verwenden. Sie können Seed X jedoch nicht mit zwei verschiedenen Algorithmen ausführen. Der Grund dafür ist, dass Seed X möglicherweise nicht auf die gleiche Weise mit Alg.1 interagiert wie mit Alg.2. Gepaarte t-Tests gelten für den Fall, dass ein Ergebnis einer Probe mit einem Ergebnis einer anderen Probe in Beziehung steht. Sie können nicht davon ausgehen, dass seedX (Alg.1) und seedX (Alg.2) verwandt sind. Sie können jedoch anhand eines Korrelationskoeffizienten testen, ob dies der Fall ist. Dies ist sehr einfach.
#4
+1
pocketdora
2011-12-29 06:41:26 UTC
view on stackexchange narkive permalink

Ich habe einen T-Test (nicht gepaart, dh unabhängig) verwendet, um 10 Läufe meines genetischen Algorithmus mit 10 Läufen eines Bergsteigeralgorithmus zu vergleichen. Ich habe einen T-Test durchgeführt, um festzustellen, ob es einen signifikanten Unterschied zwischen der Eignung der besten gefundenen Lösungen gibt, und einen weiteren T-Test, um festzustellen, ob es einen signifikanten Unterschied zwischen den Fertigstellungszeiten gibt. Ich habe diesen Online-Rechner verwendet, um dies zu tun. Die Option zum Ausschneiden und Einfügen ist sehr praktisch.

#5
+1
Patrick Burns
2011-12-29 16:02:27 UTC
view on stackexchange narkive permalink

Ich vermute, dass die Algorithmen nicht sehr unterschiedlich sind, wenn die Besonderheiten des von Ihnen verwendeten statistischen Tests von Bedeutung sind.

Zwei Kommentare:

  • die Tests sollten so eingerichtet werden, dass jeder Algorithmus ungefähr die gleiche Zeit verwendet. Sie können versuchen, die zulässige Zeit zu variieren. Es ist denkbar, dass sich die Reihenfolge mit unterschiedlichen Zeithorizonten ändert.

  • Die Testsuite sollte Probleme enthalten, die von dem Typ sind, den Sie interessieren . Unabhängig davon, über welches Algorithmuspaar Sie verfügen, können Sie Probleme finden, bei denen einer besser ist als der andere.



Diese Fragen und Antworten wurden automatisch aus der englischen Sprache übersetzt.Der ursprüngliche Inhalt ist auf stackexchange verfügbar. Wir danken ihm für die cc by-sa 2.0-Lizenz, unter der er vertrieben wird.
Loading...