MetaTrader 5 herunterladen

Genetische Algorithmen - Mathematik

18 Januar 2016, 08:54
MetaQuotes Software Corp.
0
411

     Genetische Algorithmen sind für die Lösung der Optimierungsaufgaben vorgesehen. Als Beispiel für eine solche Aufgabe, können wir das Lernen in Neuronet nehmen, das heißt, es werden solche Gewichtswerte ausgewählt, die den minimalen Fehler zulassen. Im Grunde des genetischen Algorithmus liegt ein Zufallssuchverfahren. Der Hauptnachteil des Zufallssuchverfahrens ist das, dass es uns unbekannt ist, wie viel Zeit für die Lösung einer Aufgabe gebraucht wird. Um die erhebliche Zeitverschwendung zu vermeiden, werden in der Biologie entwickelte Methoden verwendet, und nämlich die Methoden, die durch die Studien der Entstehung der Arten und der Entwicklung programmiert wurden. Man weißt, dass nur die Stärksten während der Evolution überleben. Das führt dazu, dass die Population anpassungsfähiger wird, was ihr ermöglicht, in der dynamischen Umwelt besser zu überleben.

     Das erste mal, ein solcher Algorithmus wurde in 1975 von John Holland in der Michigan Universität angeboten. Es wurde als «Hollands Reproduktive-Plan» genannt und jetzt sind fast alle Varianten des genetischen Algorithmus darauf basierend. Doch bevor wir den Pan besser betrachten, muss man begreifen, wie die Objekte von der Realität für die Anwendung in Genetischen Algorithmen kodiert werden können.

Objekts Präsentation

     Aus der Biologie wissen wir, dass jeder Objekt mit seinem Phänotyp dargestellt werden kann, der eigentlich auch bestimmt, wer dieser Objekt in der Realität ist, und es kann noch durch den Genotyp des Objektes dargestellt werden, der die ganze Information über den Chromosomensatz des Objektes enthält. Hierbei ist jedes Gen, das heißt jedes Informationselement des Genotyps drückt im Phänotyp aus. Nach dieser Weise müssen wir ein Kennzeichen des Objektes für jede Lösung in der Form darstellen, die in einem genetischen Algorithmus verwendet werden kann. Die ganze weitere Funktionalität der Mechanismen des genetischen Algorithmus wird an der Genotyp-Ebene laufen, das ermöglicht ohne Informationen über den inneren Struktur des Objektes arbeiten, was die breite Verwendung dieser Algorithmen in unterschiedlichen Aufgaben anbieten kann.

     Um den Genotyp des Objektes in den meisten vorkommenden Variationen vom genetischen Algorithmus darzustellen, werden Bitfolgen verwendet. Dabei entspricht jedem Attribut des Objektes im Phänotyp ein Gen im Genotyp des Objektes. Das Gen ist selber eine Bitfolge, meistens mit einer festgestellten Lange, die den Wert des Kennzeichens darstellt.

Codierung der Kennzeichen, die mit ganzen Zahlen dargestellt wurden

     Die einfachste Variante für die Codierung solcher Kennzeichen ist die Verwendung des Wertes eines solchen Kennzeichens. Dann wird es uns sehr einfach, ein Gen mit einer bestimmten Lange zu verwenden, welches ausreichend aller möglichen Werte von einem solchen Kennzeichen anbietet. Aber diese Codierung hat leider auch einige Nachteile. Der Hauptnachteil besteht darin, dass die benachbarte Zahlen in ihren Werten voneinander um ein paar Bits unterschiedlich sind, zum Beispiel die Zahlen 7 und 8 in ihrer Bit-Darstellung unterscheiden sich in 4 Positionen, was im Gegenzug die Funktionalität des genetischen Algorithmus erschwert und erhöht die Zeit, die für die Konvergenz gebraucht wird. Um das Problem zu vermeiden, ist es besser, die Codierung zu verwenden, in der die benachbarte Zahlen voneinander um weniger Positionen unterschiedlich sind, idealerweise um einen Wert in einem Bit. Ein solcher Code ist der Gray-Code, den man besser bei der Realisierung des genetischen Algorithmus verwenden soll. Die Werte des Gray-Codes sind unten in der Tabelle angegeben:

Binäre Kodierung Gray Codierung
Dezimal
Code
Binär
Code
Hexadezimal
Code
Dezimal
Code
Binär
Code
Hexadezimal
Code
0 0000 0h 0 0000 0h
1 0001 1h 1 0001 1h
2 0010 2h 3 0011 3h
3 0011 3h 2 0010 2h
4 0100 4h 6 0110 6h
5 0101 5h 7 0111 7h
6 0110 6h 5 0101 5h
7 0111 7h 4 0100 4h
8 1000 8h 12 1100 Ch
9 1001 9h 13 1101 Dh
10 1010 Ah 15 1111 Fh
11 1011 Bh 14 1110 Eh
12 1100 Ch 10 1010 Ah
13 1101 Dh 11 1011 Bh
14 1110 Eh 9 1001 9h
15 1111 Fh 8 1000 8h
Tabelle 1. Konkordanz der Binäre Codes und Gray-Codes.

     So teilen wir das Kennzeichen aus ganzen Zahlen während der Codierung in Tetraden und jede Tetrade umwandeln wir nach dem Gray-Code.

     In der praktischen Realisierung der genetischen Algorithmen entsteht normalerweise keine Notwendigkeit, den Wert des Kennzeichens in den Wert des Gens umzuwandeln. In der Tat hat man im Gegenteil die Aufgabe, dass man nach dem Wert des Gens den Wert des Kennzeichens bestimmen muss.

     Hierdurch stellt es sich heraus, dass der Sinn der Decodierung des Genen-Wertes, welchen die Kennzeichen aus ganzen Zahlen entsprechen, ist trivial.

Codierung der Kennzeichen, welche die Zahlen mit Gleitkomma entsprechen

     Die einfachste Codierungsweise, die verwendet werden kann, ist die Bit-Darstellung. Obwohl diese Variante die gleichen Nachteile hat, wie es bei ganzen Zahlen ist. Deshalb wird es in der Praxis die folgende Reihe von Operationen verwendet:

  1. Das gesamte Intervall von den zulässigen Werten des Kennzeichens wird in Teile mit der gewünschten Genauigkeit aufgeteilt.
  2. Der Gen-Wert wird als eine ganze Zahl angenommen, welche die Nummer des Intervalls (mit dem Gray-Code) bestimmt.
  3. Die Zahl, welche in der Mitte dieses Intervalls ist, wird als Parameterwert angenommen.

     Lassen Sie uns die obige Reihe von Operationen im folgenden Beispiel verwenden:

     Nehmen wir an, dass der Wert des Kennzeichens im Bereich von [0,1] liegt. Während der Codierung wurde der Abschnitt auf 256 Intervallen geteilt. Somit wir für die Codierung ihrer Nummer 8 Bits brauchen. Zum Beispiel der Gen-Wert ist: 00100101bG (der Großbuchstabe G bedeutet, dass die Codierung nach dem Gray-Code verwendet wird). Zuerst mit dem Gray-Code finden wir die entsprechenden Intervallnummer: 25hG->36h->54d. Nun lassen Sie überprüfen, welches Intervall ihm entspricht. Durch einfache Berechnungen erhalten wir das Intervall [0,20703125, 0,2109375]. Das heißt der Wert unseres Parameters wird (0,20703125+0,2109375)/2=0,208984375.

Codierung von nicht numerischen Daten

     Bevor die nicht numerischen Daten codiert werden, müssen sie in Zahlen umgewandelt werden. Dies wurde mehr in Details in den Artikeln auf unserer Website beschrieben, die der Verwendung der neuronalen Netze gewidmet sind.

Die Bestimmung des Phänotyps des Objektes nach seinem Genotyp

     Um den Phänotyp des Objektes (das heißt die Werte der Kennzeichen, die das Objekt beschreiben) zu bestimmen, müssen wir nur die Werte der Gene kennen, die diesen Kennzeichen entsprechen, das heißt den Genotyp des Objekts kennen. Dabei die Integrität von Genen, die den Genotyp des Objektes beschreiben, ist ein Chromosom. In einigen Realisierungen nennt man es auch als Probe. Somit wird das Chromosom in der Realisierung der genetischen Algorithmus eine Bitzeile mit der bestimmten Länge darstellen. Hierbei jedem Intervall der Zeile entspricht ein Gen. Die Länge der Gene innerhalb eines Chromosoms kann gleich oder unterschiedlich sein. Die Gene der gleichen Länge werden häufiger verwendet. Betrachten wir ein Beispiel eines Chromosoms und die Interpretationen von ihrem Wert. Zum Beispiel haben wir ein Objekt mit 5 Kennzeichen, und jedes von ihnen wurde mit dem Gen in Länge von 4 Elementen codiert. Dann ist die Länge des Chromosoms 5 * 4 = 20-Bit:

0010 1010 1001 0100 1101

     Nun können wir die Werte von Kennzeichen bestimmen

Kennzeichen Der Wert des Gens Binary Wert des Kennzeichens Dezimal Wert des Kennzeichens
Kennzeichen 1 0010 0011 3
Kennzeichen 2 1010 1100 12
Kennzeichen 3 1001 1110 14
Kennzeichen 4 0100 0111 7
Kennzeichen 5 1101 1001 9

Die grundlegende genetische Operatoren

     Es ist schon bekannt, dass die Weise in der Evolutionstheorie eine wichtige Rolle spielt, mit der die Eltern die Kennzeichen an die Nachkommen weitergeben. In genetischen Algorithmen ist der Operator für die Übergabe der Kennzeichen von Eltern an die Nachkommen verantwortlich, den nennt man kreuzen (den nennt man noch "crossover"). Dieser Operator funktioniert auf folgende Weise:

  1. Es werden zwei Einheiten aus der Population ausgewählt, sie werden die Eltern sein;
  2. Es wird der Haltepunkt bestimmt(in der Regel nach dem Zufallsprinzip);
  3. Die Nachkommenschaft wird durch die Verkettung von Teilen des ersten und des zweiten Elternteils bestimmt.

     Lassen Sie uns bitte betrachten, wie dieser Operator funktioniert:

Chromosoma_1: 0000000000
Chromosoma_2: 1111111111

     Nehmen wir an, dass der Haltepunkt beispielsweise nach dem 3-en Bit des Chromosoms kommt, dann:

Chromosoma_1: 0000000000 >> 000 1111111  Resultierendes_Chromosoma_1
Chromosoma_2: 1111111111 >> 111 0000000  Resultierendes_Chromosoma_2

     Dann wird eines von den resultierenden Chromosomen mit einer Wahrscheinlichkeit von 0,5 als Nachkommen bestimmt.

     Der nächste genetische Operator ist für die Vielfalt in der Population vorgesehen. Der heißt Mutationsoperator. Während der Verwendung dieses Operators wird jedes Bit im Chromosom mit einer bestimmten Wahrscheinlichkeit invertiert.

     Außerdem wird noch so genannter Inversion-Operator verwendet, deren Zweck darin besteht, dass das Chromosom in zwei Teile geteilt wird und danach wechseln sie mit ihren Plätzen. Schematisch kann es so dargestellt werden:

000 1111111 >> 1111111 000

     Im Prinzip sind diese 2 genetische Operators genug, damit der genetische Algorithmus funktioniert, aber praktisch werden noch einige zusätzliche Operators oder Modifikationen von diesen 2 Operatoren verwendet. Beispielsweise kann es nicht nur eine Ein-Punkt-Crossover (oben beschrieben) sein, sondern wird sie mit mehreren Punkten, wenn dabei mehrere Haltepunkte sich bilden(meistens zwei). Außerdem wird der Mutationsoperator während der Realisierung des Algorithmus als nur eine Inversion von einem zufälligen Bit des Chromosemens dargestellt.

Der Schaltungsbetrieb des genetischen Algorithmus

     Jetzt mit dem Wissen, wie die Gen-Werte interpretiert werden können, können wir die Funktionalität des genetischen Algorithmus beschreiben. Lassen Sie uns einen Schaltungsbetrieb des genetischen Algorithmus in seiner klassischen Darstellung betrachten.

  1. Initialisieren Sie die Startzeit t=0. Bilden Sie eine ursprüngliche Population, die aus k-Einheiten besteht. B0 = {A1,A2,…,Ak)
  2. Berechnen Sie, wie anpassungsfähig jede Einheit ist FAi = fit(Ai) , i=1…k und die Population insgesamt Ft = fit(Bt) (wird manchmal auch als Fitness genannt). Der Wert dieser Funktion bestimmt, wie gut die Einheit passt, die vom Chromosom beschrieben ist, zur Lösung einer Aufgabe.
  3. Wählen Sie die AC-Einheit aus der Population. Ac = Get(Bt)
  4. Wählen Sie die zweite Einheit aus der Population mit einer bestimmten Wahrscheinlichkeit (die Crossover-Pc Wahrscheinlichkeit), Ac1 = Get(Bt) und erstellen Sie den Operator des Crossovers Ac = Crossing(Ac,Ac1).
  5. Erstellen Sie den Mutationsoperator mit einer bestimmten Wahrscheinlichkeit (die Mutation Wahrscheinlichkeit Pm). Ac = mutation(Ac).
  6. Erstellen Sie den Inversionsoperator mit einer bestimmten Wahrscheinlichkeit (die Inversion Pi Wahrscheinlichkeit), Ac = inversion(Ac).
  7. Legen Sie das erhaltende neue Chromosom in die neue Population insert(Bt+1,Ac).
  8. Schritte von 3 bis 7 sollen k-mal wiederholt werden.
  9. Erhöhen Sie die Nummer der Epochen t=t+1.
  10. Wenn die Stoppbedingung erfüllt wurde, beendet die Loop der Arbeit, andernfalls geht es mit dem 2-en Schritt weiter.

     Nun lassen Sie uns besser einige Schritte des Algorithmus betrachten.

     Die wichtigste Rolle in der erfolgreichen Funktionalität des Algorithmus spielt der Auswahl-Schritt der Eltern-Chromosomen in den Stufen 3 und 4. Dabei sind verschiedene Alternativen möglich. Die am häufigsten verwendeten Selektions-Methoden nennt man Roulette. Wenn eine solche Methode verwendet wird, wird die Auswahlwahrscheinlichkeit des Chromosoms durch seine Fitness bestimmt, das heißt PGet(Ai) ~ Fit(Ai)/Fit(Bt). Die Anwendung dieser Methode führt zu der Erhöhung der Wahrscheinlichkeit, dass Kennzeichen von den anpassungsfähigen Einheiten zu den Nachkommen weitergegeben werden. Die andere häufig verwendete Methode ist - Turnierauswahl. Sie besteht darin, dass ein Paar Einheiten (in der Regel 2) aus der Population ausgewählt werden und davon wird die anpassungsfähigste Einheit als Gewinner ausgewählt. Außerdem, in einigen Realisierungen des Algorithmus wird die so genannte Elitestrategie verwendet, was bedeutet, dass die besten anpassungsfähigsten Einheiten sind garantiert, in die neue Population zu überspringen. Die Verwendung der Elitestrategie ermöglicht die Konvergenz des genetischen Algorithmus zu beschleunigen. Der Nachteil dieser Strategie ist die erhöhte Wahrscheinlichkeit, dass der Algorithmus im lokalen Minimum wird.

     Ein weiterer wichtiger Punkt ist die Bestimmung der Stopp-Kriteriums. Entweder wird es für die Begrenzung der Epochen im Algorithmus verwendet oder es wird der Konvergenz bestimmen, normalerweise wird es durch einen Fitness-Vergleich der Population in mehreren Epochen durchgeführt und wenn dieser Parameter stabilisiert wird, wird der Prozess beendet.

Im Original: Starikov Alexey, BaseGroup Labs

Übersetzt aus dem Russischen von MetaQuotes Software Corp.
Originalartikel: https://www.mql5.com/ru/articles/1408

Wie die Testergebnisse des Experten selbstständig  bewerten Wie die Testergebnisse des Experten selbstständig bewerten

Im Artikel wurden Formel und die Berechnungsmethode der Daten angeboten, die im Testerbericht angezeigt werden.

MQL4 wie ein Traders Werkzeug oder Advanced Technical Analysis MQL4 wie ein Traders Werkzeug oder Advanced Technical Analysis

Trading ist vor allem eine Wahrscheinlichkeitsrechnung. Und das Sprichwort «Faulheit ist der Motor für den Fortschritt» zeigt uns den Grund, warum all diese Indikatoren und Handelssysteme entwickelt worden sind. Daraus folgt, dass der größte Teil von neuen Tradern schon die entwickelten Handelstheorien lernt. Aber es gibt immer noch Markt-Geheimnisse, und Werkzeuge für die Analyse der Preisbewegungen, existieren meistens in der Form von realisierten technischen Indikatoren, mathematischen und statistischen Paketen. Vielen Dank Bill Williams für seinen Beitrag in der Marktbewegungen-Theorie. Aber man soll damit nicht aufhören.

Genetische Algorithmen in MetaTrader 4. Im Vergleich zur direkten Sortierung des Optimizers Genetische Algorithmen in MetaTrader 4. Im Vergleich zur direkten Sortierung des Optimizers

Im Artikel wurden die Schnelligkeit und Ergebnisse der Advisors-Optimierung mit den genetischen Algorithmen im Vergleich zur direkten Sortierung durchgeführt.

Mehrmalige Neuberechnungen des nullwertigen Bars in einigen Indikatoren Mehrmalige Neuberechnungen des nullwertigen Bars in einigen Indikatoren

Der Artikel widmet sich dem Problem bei einer Neuberechnung des Indikator-Wertes im Client-Terminal MetaTrader 4, wenn das nullwertige Bar sich ändert. Es handelt sich da um die allgemeine Idee, dass zusätzliche Programm-Elementen im Indikator-Code hinzugefügt werden können, welche die Wiederherstellung des Programmen-Codes ermöglichen, der bis zu mehrmaligen Neuberechnungen gespeichert werden muss.