Genetische Algorithmen - Mathematik

     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