Wie kann die Leistung eines genetischen Algorithmus experimentell analysiert werden?

7

Ich habe einen genetischen Algorithmus für ein Optimierungsproblem. Ich habe die Laufzeit des Algorithmus in mehreren Läufen mit derselben Eingabe und denselben Parametern (Populationsgröße, Generationsgröße, Crossover, Mutation) aufgezeichnet.

Die Ausführungszeit ändert sich zwischen den Ausführungen. Ist das normal?

Ich habe auch festgestellt, dass die Laufzeit entgegen meiner Erwartung manchmal abnimmt, anstatt zuzunehmen, wenn ich sie mit einem größeren Eingang ausführe. Wird das erwartet?

Wie kann ich die Leistung meines genetischen Algorithmus experimentell analysieren?

Raphael
quelle
5
GAs und Heuristiken sind oft unvorhersehbar und es kann sehr schwierig sein, sie theoretisch zu verstehen oder zu analysieren. Aufgrund der von Ihnen angegebenen Daten kann wohl niemand eine bessere Antwort geben als "Es ist wahrscheinlich normal, ich weiß es nicht." Sie können versuchen, Ihre GA mehrmals mit denselben Parametern auszuführen und beispielsweise die durchschnittliche Anzahl von Iterationen aufzuzeichnen. Passen Sie dann die Parameter an und versuchen Sie es erneut.
Juho
2
Ja, es ist normal, es ist ein heuristischer Algorithmus (es ist kein nichtdeterministischer Algorithmus, der eine technische Bedeutung hat, dies sind verschiedene Konzepte). Es ist auch normal, dass ein Algorithmus bei einigen größeren Eingaben eine bessere Leistung erzielt als bei einigen kleineren Eingaben, da sie möglicherweise einfacher zu lösen sind, wobei die Größe nicht der einzige bestimmende Faktor ist. Man kann nicht viel über die Leistung eines Algorithmus in praktischen Fällen sagen, die normalerweise anders sind als die Leistung und bestimmte Datensätze und wie sie mit anderen Algorithmen für das Problem in diesen Datensätzen verglichen werden.
Kaveh
Sie haben nicht erwähnt, wie Sie Ihre Laufzeit überwachen. Abgesehen davon, was alle über schwer vorhersehbare Heuristiken sagten, ist es sehr wahrscheinlich, dass Sie unangenehme Ergebnisse erzielen, wenn Sie den tatsächlichen Rechenaufwand nicht messen (z. B. indem Sie die Laufzeit anhand der Uhr des Computers bestimmen) ...
Ron Teller
1
Ich verstehe den Kern der Frage nicht ganz. Was ist das Leistungsmaß, an dem Sie interessiert sind? Was für ein Ergebnis können Sie danach nicht erzielen, wenn Sie N-mal laufen und mitteln?
Raphael

Antworten:

8

Der typische Ansatz besteht darin, mehrere Läufe des Evolutionsalgorithmus (EA) durchzuführen und die durchschnittliche Leistung über die Zeit zu zeichnen (durchschnittliche Leistung des Best-of-Run-Individuums, NICHT des Populationsdurchschnitts).

Eine gute Faustregel ist, mindestens 30 Läufe durchzuführen (natürlich sind 50-100 Läufe besser).

Der Durchschnitt ist besser als der beste Wert, der in einer Reihe von Läufen erzielt wird, aber auch die Varianz sollte berücksichtigt werden.

Es gibt einige schöne Beispiele auf der Website von Randy Olson :


durchschnittliche Fitness beider Algorithmen über mehrere Wiederholungen

Die durchschnittliche Fitness beider Algorithmen über mehrere Wiederholungen. Aus diesem Diagramm würden wir schließen, dass unser Algorithmus im Durchschnitt besser abschneidet als der derzeit beste Algorithmus.

durchschnittliche Fitness mit einem Konfidenzintervall von 95%

Die durchschnittliche Fitness mit einem 95% -Konfidenzintervall für jeden Algorithmus. Diese Grafik zeigt uns, dass unser Algorithmus nicht wirklich besser abschneidet als der derzeit beste Algorithmus und nur aufgrund des Zufalls im Durchschnitt besser abschneidet.


Die grundlegende Aufschlüsselung zur Berechnung eines Konfidenzintervalls für einen Populationsmittelwert lautet wie folgt:

  1. Identifizieren Sie den Stichprobenmittelwert . Während sich von , dem Mittelwert der Grundgesamtheit, unterscheidet, werden sie immer noch auf die gleiche Weise berechnet:x¯x¯μ

    x¯=xin
  2. Identifizieren Sie die (korrigierte) Standardabweichung der Stichprobe : ist eine Schätzung der Populationsstandardabweichung .s

    s=i=1n(xix¯)2n1
    sσ
  3. Berechnen Sie den kritischen Wert , , der Student-t - Verteilung. Dieser Wert ist abhängig vom Konfidenzniveau und der Anzahl der Beobachtungen .tCn

    Der kritische Wert wird aus der T-Verteilungstabelle ermittelt (in den meisten statistischen Lehrbüchern ist er aufgeführt). In dieser Tabelle wird als wobei die Freiheitsgrade sind (ermittelt durch Subtrahieren von eins von der Anzahl der Beobachtungen) und ist das Signifikanzniveau .t

    t(α,r)
    r=n1α=1C2

    Ein besserer Weg zu einem vollständig präzisen kritischen -Wert ist die statistische Funktion, die in Tabellenkalkulationen (z. B. Funktion ), wissenschaftlichen Computerumgebungen (z. B. SciPy ) und Sprachbibliotheken (z. B. C ++ und ) implementiert ist .tT.INV.2Tstats.t.ppfboost::math::students_t

  4. Stecken Sie die gefundenen Werte in die entsprechenden Gleichungen:

    (x¯tsn,x¯+tsn)
  5. Der letzte Schritt ist die Interpretation der Antwort . Da die gefundene Antwort ein Intervall mit einer Ober- und Untergrenze ist, sollte angegeben werden, dass basierend auf den angegebenen Daten der wahre Mittelwert der Population zwischen der Untergrenze und der Obergrenze mit dem gewählten Konfidenzniveau liegt.


Je mehr sich die Konfidenzintervalle zweier Algorithmen überschneiden, desto wahrscheinlicher ist es, dass die Algorithmen dieselbe Leistung erbringen (oder wir haben nicht genug Stichproben abgetastet, um zwischen den beiden zu unterscheiden). Wenn sich die 95% -Konfidenzintervalle nicht überschneiden, ist die Leistung des Algorithmus mit der höchsten durchschnittlichen Leistung erheblich besser.

In EA ist die Quellverteilung im Wesentlichen nie normal und was bisher gesagt wurde, gilt formal nur, wenn es sich um eine Normalverteilung handelt!

In der Tat sagt es immer noch viele Dinge. Die folgende Tabelle fasst die Leistung der t-Intervalle in vier Situationen zusammen:

                             Normal curve | Not Normal curve
Small sample size (n < 30)      Good      |       Poor
Larger sample size (n ≥ 30)     Good      |       Fair

Für genauere Antworten sind nichtparametrische Statistiken der richtige Weg ( weitere Informationen finden Sie unter Eine Einführung in die Statistik für die experimentelle Analyse der EG von Mark Wineberg und Steffen Christensen).

Manlio
quelle
Diese Antwort sollte akzeptiert werden und verdient weitaus mehr Stimmen.
Kevin Dreßler
1

Antwort: Sie analysieren die Leistung statistisch.

Siehe beispielsweise Abbildung 3 dieses Dokuments : Eine königliche Bausteinstraße, auf der Crossover nachweislich unerlässlich ist, wenn die Leistung verschiedener GA miteinander verglichen wird.

Das Diagramm zeigt Änderungen der Fitness (Y-Achse) gegenüber der Iterationszahl (X-Achse). Jeder Algorithmus wird mehrmals ausgeführt und die durchschnittliche, minimale und maximale Fitness wird im Diagramm angezeigt . Daher zeigt sich deutlich, dass einige GA-Variationen eine bessere Leistung aufweisen als andere.

Die asymptotische Konvergenz von Fitness über Iteration, wie in der Antwort von vzn vorgeschlagen, ist in den meisten Fällen ebenfalls sehr nützlich.

...

(Außer wenn die Fitness nicht konvergiert, wenn Sie eine sich entwickelnde Fitnessfunktion haben.)

Apiwat Chantawibul
quelle
0

Die grundlegende Strategie besteht darin, die Fitnessfunktion über die Zeit grafisch darzustellen. man kann die Eignung der besten Lösung oder die durchschnittliche Eignung von Lösungen, die schlechteste Lösung usw. grafisch darstellen. Die besten / schlechtesten weisen treppenstufenartige Eigenschaften auf und der Durchschnitt zeigt eine asymptotische Konvergenz in Richtung des durch die GA erreichbaren Optimums. Es gibt im Allgemeinen keine a priori "Ausführungszeit", die mit dem Finden einer Lösung für GAs verbunden ist. Normalerweise wird der Algorithmus an einem Punkt beendet, der "gut genug" ist, indem diese asymptotische Kurve untersucht wird.

siehe zB Grafiken am Ende dieser Diashow:

vzn
quelle
Wie kann man die Zeit bestimmen, die benötigt wird, um auf der Grundlage der Eingabegröße auf eine "gut genug" -Lösung zu konvergieren?
Soandos