Algorithmen zur Optimierung mit Populationen: Binärer genetischer Algorithmus (BGA). Teil I

Inhalt

1. Einführung
2. Methoden zur Darstellung von Merkmalen: reell und binär
3. Vorteil der Gray-Binärcode-Darstellung
4. Auswahlmethoden
5. Die Arten der „Crossover“-Methoden
6. Die Arten der „Mutations“-Methoden
7. Zusammenfassung

1. Einführung

In diesem Artikel werden wir die Methoden und Techniken der genetischen Algorithmen näher betrachten, die als Werkzeuge und Bausteine für die Erstellung verschiedener Optimierungsalgorithmen in kundenspezifischen Lösungen dienen können. Der Zweck dieses Artikels ist die Beschreibung und Bereitstellung von Werkzeugen zur Untersuchung von Optimierungsproblemen in allen Optimierungsalgorithmen, nicht nur in genetischen Algorithmen.

2. Methoden zur Darstellung von Merkmalen: reell und binär

Die Parameter von Optimierungsproblemen werden oft als „Merkmale“ bezeichnet und müssen in einer bestimmten Weise dargestellt werden, damit sie in der Logik des Optimierungsalgorithmus verwendet werden können. In der Genetik werden diese Merkmale in Phänotyp und Genotyp unterteilt. Der Phänotyp ist das Erscheinungsbild des zu optimierenden Parameters, und der Genotyp ist die Art und Weise, wie er im Algorithmus dargestellt wird. In den meisten Optimierungsalgorithmen ist der Phänotyp derselbe wie der Genotyp und wird als reelle Zahl dargestellt. Ein Gen ist ein optimierter Parameter, ein Chromosom wiederum ist ein Satz von Genen, d.h. ein Satz von optimierten Parametern.

Die Darstellung von reellen Daten wird zur Darstellung von Bruchzahlen verwendet. Reelle Zahlen können einen Vor- und Nachkommateil haben, die durch einen Dezimalpunkt getrennt sind. „3,14“ und „0,5“ sind beispielsweise reelle Zahlen.

Bei der binären Datendarstellung hingegen wird ein binäres Zahlensystem verwendet, in dem Zahlen durch zwei Symbole dargestellt werden: „0“ und „1“, wobei jede Stelle ein Bit genannt wird. Die Zahl „5“ kann zum Beispiel in binärer Form als „101“ dargestellt werden.

Der Hauptunterschied zwischen der reellen und der binären Darstellung von Daten ist die Art und Weise, wie die Zahlen kodiert werden. Reelle Zahlen werden in der Regel nach Standards wie IEEE 754 kodiert, der Formate für die Darstellung von Gleitkommazahlen definiert. In der Sprache MQL5 wird der Datentyp „double“ für reelle Zahlen verwendet. Sie kann insgesamt 16 signifikante Stellen in einer Zahl beschreiben. Das bedeutet, dass die Gesamtzahl der Stellen sechzehn nicht überschreiten darf, z. B. haben „9 999 999 999 999 999,0“ und „9 999 999,999 999 99“ und „0,999 999 999 999 999 9“ insgesamt sechzehn „9“-Ziffern vor und nach dem Dezimalpunkt. Warum das so wichtig ist, werde ich später noch erklären.

Reelle Zahlen eignen sich zum Schreiben von Programmen und für das tägliche Leben, während binäre Zahlen in Computersystemen und bei der Durchführung von Operationen auf niedriger Ebene, einschließlich logischer und bitweiser Operationen, verwendet werden.

Im Zusammenhang mit Optimierungsalgorithmen, einschließlich genetischer Algorithmen, können Daten als reelle oder binäre Zahlen dargestellt werden, die zur Kodierung von Entscheidungen und zur Durchführung von Operationen mit ihnen verwendet werden.

Der Vorteil der Verwendung reeller Zahlen in Optimierungsalgorithmen ist die Möglichkeit, mit kontinuierlichen Parameterwerten zu arbeiten. Die reelle Darstellung ermöglicht es uns, Zahlen zur Kodierung von Merkmalen zu verwenden und Lösungssuchoperationen direkt mit diesen Zahlen durchzuführen. Handelt es sich bei der Lösung beispielsweise um einen Vektor mit numerischen Werten, so kann jedes Element des Vektors mit einer reellen Zahl kodiert werden.

Die reelle Darstellung hat jedoch Nachteile. Die einzelnen Elemente eines Optimierungsproblems können unabhängig sein und mehrdimensionale, nicht überlappende Räume darstellen. Dies führt zu Schwierigkeiten bei der Lokalisierung einer globalen Lösung, da die Suche aufgrund der Aufteilung des Raums in unabhängige Unterräume schwierig sein kann.

Der Vorteil der binären Darstellung von Merkmalen liegt in der Möglichkeit, alle Merkmale zu einer Gesamtbeschreibung mehrdimensionaler, sich nicht überlappender Räume zu kombinieren. Auf diese Weise lassen sich einzelne mehrdimensionale Räume zu einem gemeinsamen Suchraum verknüpfen. Die binäre Darstellung erleichtert auch die Durchführung elementarer bitweiser Operationen, wie z. B. des „Mutations“-Operators, im Gegensatz zu reellen Zahlen, bei denen zusätzliche zeitaufwändige Operationen zur Durchführung solcher Operationen erforderlich sind.

Die Nachteile der binären Darstellung im Optimierungsalgorithmus sind die Notwendigkeit der Umwandlung in reelle Zahlen, mit denen die Optimierungsaufgabe letztlich arbeitet, sowie zusätzliche zeitaufwändige Operationen, wie die Speicherung der Bitdarstellung in Form einer signifikanten Array-Länge.

So bieten reelle Zahlen die Flexibilität, mit kontinuierlichen Werten zu arbeiten, während die binäre Darstellung die Kombination von Merkmalen zu einem Ganzen und die Durchführung bitweiser Operationen auf ihnen effizienter ermöglicht. Optimierungsalgorithmen können zusätzlich zu genetischen Algorithmen auch beide Darstellungsmethoden verwenden, um die Vorteile beider zu nutzen.

3. Vorteil der Gray-Binärcode-Darstellung

Trotz aller Vorteile der Binärdarstellung hat sie einen entscheidenden Nachteil: Zwei nahe beieinander liegende Dezimalzahlen in der Binärdarstellung können sich gleich um mehrere Bits unterscheiden. Bei einem Binärcode beispielsweise ändert der Wechsel von 7 (0111) zu 8 (1000) alle vier Bits. Dies bedeutet, dass eine unterschiedliche Anzahl von Bit-Operationen zwischen verschiedenen nahe beieinander liegenden Zahlen erforderlich ist, was zu einer ungleichmäßigen Wahrscheinlichkeit von Ergebnissen im Suchraum, dem Auftreten von besonderen „Bändern erhöhter Wahrscheinlichkeit“ und umgekehrt zu „blinden Flecken“ in den optimierten Parametern führt.

Wenn wir beispielsweise eine arithmetische Operation an zwei Zahlen durchführen wollen, die sich in der Dezimalschreibweise nur um eine Einheit unterscheiden, kann es in der Binärschreibweise erforderlich sein, mehrere Bits zu ändern. Folglich ist die Wahrscheinlichkeit, nach der Operation die gewünschte Zahl zu erhalten, im Gegensatz zu einem anderen Zahlenpaar ungerade, da die Änderung jedes Bits das Endergebnis beeinflusst. Dieses Phänomen kann besonders bei der Durchführung von Fließkommaberechnungen problematisch sein, wo die Genauigkeit der Zahlendarstellung von großer Bedeutung ist und kleine Änderungen in der Dezimaldarstellung der Zahlen zu großen Änderungen in ihrer Binärdarstellung und folglich in den Berechnungsergebnissen führen können.

Bei der Gray-Code-Binärdarstellung (auch bekannt als reflektierender Binärcode) wird jede Zahl als eine Reihe von Bits dargestellt, wobei sich jede nachfolgende Zahl von der vorherigen nur durch ein geändertes Bit unterscheidet. Dies gewährleistet einen reibungslosen Übergang der Zahlen, eine Eigenschaft, die als „unit distance property“ (Einheitsabstandseigenschaft) bezeichnet wird.

Ich habe bereits erwähnt, dass die „double“-Zahl nur mit 16 signifikanten Stellen dargestellt werden kann. Schauen wir uns ein Beispiel an, um besser zu verstehen, welche Auswirkungen dies haben kann.

Nehmen wir an, wir haben eine Zahl mit 15 signifikanten „0“ und „1“ in der 16ten Stelle: „0.0000000000000001“. Nun addieren wir 1,0 zu dieser Zahl und erhalten „1.0000000000000000“. Beachten Sie, dass die „1“ in der 16. Stelle verschwunden ist, sodass wir 15 signifikante Stellen nach dem Komma haben. Wenn eine neue Ziffer zum ganzzahligen Teil eines „double“ hinzugefügt wird, werden die signifikanten Ziffern nach links verschoben. Wenn wir also einen ganzzahligen Teil haben, der nicht Null ist, können wir keine Genauigkeit auf die 16.

Bei der Binärdarstellung und insbesondere bei der Verwendung des Gray-Codes kann das Problem des Verlusts der Zifferngenauigkeit vermieden werden, wenn dies als Ziel vorgegeben oder im Rahmen einer bestimmten Aufgabe erforderlich ist. Gehen wir näher auf diesen Aspekt ein.

Computer arbeiten mit Programmen und Zahlen in binärer Darstellung, weil dies die effizienteste und natürlichste Art der maschinellen Verarbeitung von Informationen ist. Um jedoch das Verständnis und das Schreiben von Optimierungsalgorithmen auf höchster Ebene zu erleichtern, müssen wir einige zusätzliche Anstrengungen unternehmen, um mit Zahlen in binärer Form zu arbeiten, insbesondere im Fall von negativen Zahlen und Zahlen mit einem Nachkommateil.

Um mit Zahlen in binärer Form auf höchstem Niveau zu arbeiten, gibt es verschiedene Bibliotheken und Werkzeuge, die die Verarbeitung und Darstellung von negativen Zahlen und Zahlen mit einem Nachkommateil erleichtern. Aber wir werden alles als Teil des Optimierungsalgorithmus in MQL5 implementieren.

Die Methode des Zusatzcodes wird verwendet, um negative Zahlen im Binärsystem darzustellen. Sie ermöglicht es, eine negative Zahl anzuzeigen, indem alle Bits der Zahl invertiert werden und zum Ergebnis eine Eins addiert wird. Aber wir werden einen kleinen Trick anwenden und zusätzliche Operationen für die Arbeit mit negativen Zahlen vermeiden, indem wir sie einfach loswerden. Gehen wir davon aus, dass einer der optimierten Parameter Grenzen hat:

min = -156,675 und max = 456,6789

dann ist der Abstand (distance) zwischen „max“ und „min“:

distance = max - min = 456,6789 - (-156,675) = 613,3539

Die im Optimierungsproblem geforderte Zahl wird also immer positiv sein. Sie befindet sich rechts von 0,0 auf der Zahlengeraden und hat einen Höchstwert von 613,3539. Nun geht es darum, die Kodierung einer reellen Zahl sicherzustellen. Dazu teilen wir diese Zahl in den ganzzahligen und den Nachkommateil auf. Der gesamte Teil wird im Gray-Code wie folgt dargestellt (die Darstellungsmethode ist in Klammern angegeben):

613 (dezimal) = 1 1 0 1 0 1 0 1 1 1 (binary Gray)

Dann sieht der Nachkommateil wie folgt aus:

3539 (dezimal) = 1 0 1 1 0 0 1 1 1 1 0 1 0 (binary Gray)

Wir können den ganzzahligen und den Nachkommateil in einer Zeichenkette speichern und uns dabei die Anzahl der für beide Teile verwendeten Zeichen merken, was uns eine einfache Umkehrung ermöglicht. Infolgedessen sieht die reelle Zahl wie folgt aus (das Zeichen „:“ trennt den ganzzahligen vom Nachkommateil):

613.3539 (dezimal) =  1 1 0 1 0 1 0 1 1 1  :  1 0 1 1 0 0 1 1 1 0 1 0 (binary Gray)

So können wir jede reelle Zahl mit bis zu 16 Dezimalstellen in ihrem ganzzahligen Teil und 16 Dezimalstellen für Zahlen vom Typ „double“ umwandeln. Außerdem können wir so mehr als 16 signifikante Stellen in der Gesamtzahl der Stellen haben, sogar bis zu 32 signifikante Stellen oder mehr (begrenzt durch die Länge der ulong-Zahl, die in Funktionen zur Umwandlung ganzer Dezimalzahlen in Gray-Code und umgekehrt verwendet wird).

Um sicherzustellen, dass der Nachkommateil auf die 16. Stelle genau ist, müssen wir die Zahl „9 999 999 999 999 999“ (den maximal möglichen Nachkommateil) umrechnen:

9999999999999999 (decimal) = 1 1 0 0 1 0 0 1 0 0 0 1 0 1 1 0 0 0 1 0 1 1 0 1 0 1 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 (binary Gray)

Der endgültige Datensatz für unsere Zahl 613,9999999999999999 (mit 16 Dezimalstellen) sieht dann so aus:

613.9999999999999999 (dezimal) = 1 1 0 1 0 1 0 1 1 1:  1 1 0 0 1 0 0 0 1 0 0 1 1 0 0 0 1 0 1 0 1 0 1 0 0 0 1 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 (binäres Grau)

Wie wir sehen können, kann der Nutzer eine beliebige Genauigkeit nach dem Dezimalpunkt innerhalb der Länge des Typs ulong einstellen.

Schauen wir uns die Funktionen an, mit denen man Dezimalzahlen in Gray-Code umwandeln kann und umgekehrt. Für die Kodierung und Dekodierung des Gray-Codes werden zusätzliche Funktionen zur Umwandlung in den regulären Binärcode verwendet.

Die Funktion DecimalToGray benötigt als Parameter die „decimalNumber“ und den Verweis auf das „array“, in dem das Konvertierungsergebnis gespeichert werden soll. Sie wandelt eine Zahl von Dezimalzahlen in Gray-Code um. Dazu wird zunächst der Wert von „grayCode“ durch eine bitweise XOR-Verknüpfung von „decimalNumber“ berechnet und um ein Bit nach rechts verschoben. Anschließend wird die Funktion IntegerToBinary aufgerufen, um den resultierenden „grayCode“-Wert in eine binäre Darstellung umzuwandeln und im „array“ zu speichern. Für das Array wird der geringste Speicherplatz für Ganzzahlen verwendet, der Typ char.

Die Funktion IntegerToBinary akzeptiert als Parameter „number“ und den Verweis auf das „array“, in dem das Konvertierungsergebnis gespeichert werden soll. Sie konvertiert eine Zahl vom dezimalen in das binäre Zahlensystem. In der Schleife wird der Rest von „number“ durch 2 geteilt und zu „array“ addiert. Anschließend wird „number“ durch 2 geteilt und der Zähler „cnt“ erhöht. Die Schleife wird fortgesetzt, so lange „number“ größer als Null ist. Nach der Schleife wird das „array“ umgekehrt, um die richtige Bitreihenfolge zu erhalten.

Die Funktion GrayToDecimal akzeptiert die Verknüpfung mit dem Array „grayCode“, den Anfangsindex „startInd“ und den Endindex „endInd“ als Parameter. Sie wandelt eine Zahl vom Gray-Code in das Dezimalsystem um. Zunächst wird die Funktion BinaryToInteger aufgerufen, um das Array „grayCode“ in eine binäre Darstellung zu konvertieren und in der Variablen „grayCodeS“ zu speichern. Anschließend wird die Variable „result“ mit dem Wert „grayCodeS“ initialisiert. Dann wird die Schleife ausgeführt, in der „grayCodeS“ um ein Bit nach rechts verschoben und die bitweise XOR-Operation mit „result“ durchgeführt wird. Die Schleife wird so lange fortgesetzt, wie „grayCodeS“ sich nach rechts verschiebt und größer als Null ist. Am Ende gibt die Funktion den Wert von „result“ zurück.

Die Funktion BinaryToInteger akzeptiert die Verknüpfung mit dem Array „binaryStr“, den Anfangsindex „startInd“ und den Endindex „endInd“ als Parameter. Sie wandelt eine Zahl vom binären in das dezimale Zahlensystem um. Die Funktion initialisiert die Variable „result“ mit Null. Anschließend wird eine Schleife ausgeführt, in der „result“ um ein Bit nach links verschoben und der Wert von „binaryStr[i]“ (Bit) zu „result“ addiert wird. Die Schleife läuft von „startInd“ bis „endInd“. Am Ende gibt die Funktion den Wert von „result“ zurück.

Beachten Sie, dass die Indizes der Anfangs- und Endposition bei der Rückkonvertierung aus dem Gray-Code verwendet werden. Dies ermöglicht es, nur eine bestimmte Anzahl von optimierten Parametern aus der „row“ zu extrahieren, in der alle optimierten Parameter gespeichert sind. Wir kennen die Gesamtlänge der Zeichenkette, einschließlich der ganzzahligen und gebrochenen Teile, und können daher die spezifische Position der Zahlen in der allgemeinen Zeichenkette des Chromosoms bestimmen, einschließlich der Verbindung der ganzzahligen und Nachkommateile.

//——————————————————————————————————————————————————————————————————————————————
//Converting a decimal number to a Gray code
void DecimalToGray (ulong decimalNumber, char &array [])
{
  ulong grayCode = decimalNumber ^(decimalNumber >> 1);
  IntegerToBinary(grayCode, array);
}

//Converting a decimal number to a binary number
void IntegerToBinary (ulong number, char &array [])
{
  ArrayResize(array, 0);
  ulong temp;
  int cnt = 0;
  while (number > 0)
  {
    ArrayResize (array, cnt + 1);
    temp = number % 2;
    array [cnt] = (char)temp;
    number = number / 2;
    cnt++;
  }

  ArrayReverse (array, 0, WHOLE_ARRAY);
}
//——————————————————————————————————————————————————————————————————————————————

//——————————————————————————————————————————————————————————————————————————————
//Converting from Gray's code to a decimal number
ulong GrayToDecimal (const char &grayCode [], int startInd, int endInd)
{
  ulong grayCodeS = BinaryToInteger(grayCode, startInd, endInd);
  ulong result = grayCodeS;

  while ((grayCodeS >>= 1) > 0)
  {
    result ^= grayCodeS;
  }
  return result;
}

//Converting a binary string to a decimal number
ulong BinaryToInteger (const char &binaryStr [], const int startInd, const int endInd)
{
  ulong result = 0;
  if (startInd == endInd) return 0;

  for (int i = startInd; i <= endInd; i++)
  {
    result = (result << 1) + binaryStr [i];
  }
  return result;
}
//——————————————————————————————————————————————————————————————————————————————

4. Auswahlmethoden

Bei Optimierungsalgorithmen ist die Auswahl der besten Lösungen aus einer Population oder einem Satz von Kandidaten der Prozess der Erstellung der nächsten Generation. Sie spielt eine entscheidende Rolle bei Optimierungsmethoden. Die Wahl einer bestimmten Auswahloption wirkt sich nicht nur auf die Suchmöglichkeiten des Algorithmus, sondern auch auf die Geschwindigkeit seiner Konvergenz aus. Alle Auswahlmethoden haben ihre Vor- und Nachteile und können bei einigen Algorithmen effektiver und bei anderen weniger effektiv sein. Die Verwendung jeder dieser Methoden hängt von der jeweiligen Suchstrategie ab.

Es gibt verschiedene Arten der Selektion, um Elterntiere auszuwählen und eine neue Generation zu bilden. Betrachten wir jede einzelne von ihnen im Detail:

• Gleichmäßige Auswahl ist eine Methode der Elternauswahl, bei der jedes Individuum die gleiche Chance hat, ausgewählt zu werden. Bei dieser Methode hat jedes Individuum in einer Population die gleiche Wahrscheinlichkeit, für die Reproduktion ausgewählt zu werden. Der Vorteil der gleichmäßigen Auswahl besteht darin, dass alle Individuen die gleiche Chance haben, ausgewählt zu werden. Diese Methode berücksichtigt jedoch nicht die Fitness der Individuen, sodass sie bei der Suche nach der optimalen Lösung weniger effektiv sein kann, vor allem, wenn einige Individuen eine deutlich höhere Fitness als andere haben. Eine einheitliche Auswahl kann in einigen Fällen nützlich sein, z. B. wenn Sie verschiedene Regionen des Lösungsraums erforschen oder ein hohes Maß an Diversität in einer Population aufrechterhalten möchten.

• Bei der Rangauswahl werden die Individuen nach ihrer Fitness eingestuft, und die Wahrscheinlichkeit der Auswahl eines Individuums hängt von seinem Rang ab. Je höher der Rang einer Person ist, desto wahrscheinlicher ist es, dass sie ausgewählt wird. Die Rangauswahl kann vollständig proportional sein, d. h. die Wahrscheinlichkeit, ein Individuum zu wählen, ist proportional zu seinem Rang (Ordnungszahl), oder teilweise proportional, d. h. die Wahrscheinlichkeit, ein Individuum zu wählen, steigt mit zunehmendem Rang nach einem nichtlinearen Gesetz. Die Rangfolgeauswahl hat eine Reihe von Vorteilen. Erstens trägt es dazu bei, die Vielfalt in der Population zu erhalten, da auch weniger geeignete Individuen eine Chance haben, ausgewählt zu werden. Zweitens wird das Problem der vorzeitigen Konvergenz vermieden, bei dem die Population zu schnell zu einem lokalen Optimum konvergiert. Die Rangfolgeauswahl trägt dazu bei, die Vielfalt zu erhalten und einen größeren Lösungsraum zu erkunden. Die Rangselektion ähnelt der gleichmäßigen Selektion, legt aber mehr Wert auf die Auswahl der fittesten Individuen und lässt die Chance, dass auch weniger fitte Individuen ausgewählt werden.
  

• Bei der Turnierauswahl wird eine kleine Teilmenge von Personen nach dem Zufallsprinzip ausgewählt (Turnier genannt). Aus dieser Teilmenge wird das Individuum mit der höchsten Fitness ausgewählt. Die Größe des Turniers bestimmt, wie viele Personen an jedem Turnier teilnehmen werden. Die Turnierselektion ermöglicht die Erhaltung der Vielfalt in der Population, da auch weniger geeignete Individuen durch Zufall ausgewählt werden können. Die Auswahl von Turnieren hat mehrere Vorteile. Erstens kann der Zufall bei der elterlichen Auswahl berücksichtigt werden, was die Vielfalt der Nachkommen fördert. Zweitens können die Eltern aus einem beliebigen Teil der Bevölkerung ausgewählt werden, wobei sowohl die besten als auch die weniger geeigneten Personen berücksichtigt werden. Die Turnierauswahl ist eine der wichtigsten Elternauswahlmethoden in evolutionären Algorithmen und wird oft in Kombination mit anderen Operatoren wie Crossover und Mutation verwendet, um neue Nachkommen zu erzeugen und die Evolution einer Population fortzusetzen.
  

• Bei der Roulette-Rad-Auswahl wird jedes Individuum auf einem imaginären Roulette-Rad im Verhältnis zu seiner Fitness dargestellt. Das Rouletterad „dreht“ sich und die Person, auf die der „Zeiger“ zeigt, wird ausgewählt. Je höher die Fitness eines Individuums ist, desto größer ist der Sektor des Rouletterades, den es belegt, und desto größer ist die Chance, ausgewählt zu werden. Bei der Roulette-Auswahl werden die Eltern mit Wahrscheinlichkeiten ausgewählt, die proportional zu ihrer Fitness sind. Individuen mit höherer Fitness haben eine größere Chance, ausgewählt zu werden, aber auch weniger fitte Individuen haben eine Wahrscheinlichkeit ungleich Null, ausgewählt zu werden. Dadurch kann die genetische Vielfalt in der Population erhalten und verschiedene Regionen des Lösungsraums erforscht werden. Bei der Auswahl mit dem Rouletterad kann es jedoch zu einem Problem mit vorzeitiger Konvergenz kommen, insbesondere wenn die Fitness der Individuen stark schwankt. Individuen mit hoher Fitness haben eine viel größere Chance, ausgewählt zu werden, was zu einem Verlust an genetischer Vielfalt führen kann, wodurch die Population mit ähnlichen Lösungen „verstopft“ wird und in lokalen Optima stecken bleibt.

Die „Elitismus“-Methode kann in Verbindung mit jeder Auswahlmethode als zusätzliche Maßnahme eingesetzt werden. Sie besteht darin, die besten Individuen der aktuellen Population zu erhalten und sie unverändert der nächste Generation zu übertragen. Durch die Anwendung der „Elitismus“-Methode können die besten Individuen von Generation zu Generation erhalten werden, was dazu beiträgt, eine hohe Fitness zu bewahren und den Verlust nützlicher Informationen zu verhindern. Dadurch kann die Konvergenz des Algorithmus beschleunigt und die Qualität der gefundenen Lösung verbessert werden.

Es sollte jedoch berücksichtigt werden, dass der Einsatz von „Elitismus“ zu einem Verlust an genetischer Vielfalt führen kann, insbesondere wenn der Elitismus auf einem hohen Niveau angesiedelt ist. Daher ist es wichtig, einen geeigneten Elitismuswert zu wählen, um ein Gleichgewicht zwischen der Erhaltung der besten Individuen und der Erkundung des Lösungsraums zu wahren.

5. Arten von „Crossover“-Methoden

Crossover ist eine der wichtigsten Operationen in genetischen Algorithmen, die die Kreuzung in der natürlichen Evolution nachahmt. Sie besteht darin, die genetische Information zweier Elternteile zu kombinieren, um Nachkommen zu erzeugen und vererbbare Merkmale auf die Tochter zu übertragen. Crossover ist nicht nur als Mittel zur Informationsübertragung sinnvoll, sondern hat auch einen großen Einfluss auf die kombinatorischen Eigenschaften des Algorithmus.

Crossover funktioniert auf der Ebene des Genotyps und ermöglicht die Kombination der Gene der Elterntiere, um neue Nachkommen zu erzeugen.

Das allgemeine Prinzip der Crossover-Methode ist wie folgt:

1. Auswahl der übergeordneten Personen: Zwei oder mehrere Individuen werden aus einer Population ausgewählt, um miteinander gekreuzt zu werden.
   
2. Bestimmung des Crossover-Punktes: Der Crossover-Punkt bestimmt die Stelle, an der die Chromosomen der Eltern getrennt werden, um Nachkommen zu erzeugen.
3. Erzeugung von Nachkommen: Die Chromosomen der Eltern werden an der Crossover-Punkt getrennt, und Teile der Chromosomen beider Elternteile werden kombiniert, um einen neuen Genotyp des Nachkommen zu schaffen. Der Crossover führt zu einem oder mehreren Nachkommen, die eine Kombination von Genen beider Elternteile aufweisen können.

Abbildung 1. Das allgemeine Prinzip der Crossover-Methode

Im Folgenden werden die wichtigsten Arten von binärem Crossover aufgeführt:

• Single-Point-Crossover - zwei Chromosomen trennen sich an einem zufälligen Punkt und zwei Nachkommen werden durch den Austausch von Segmenten der Chromosomen der Eltern nach diesem Punkt erzeugt.
• Multi-Point Crossover - ähnlich dem Single-Point-Crossover, jedoch mit mehreren Breakpoints, zwischen denen Chromosomensegmente ausgetauscht werden.
  
• Uniform-Crossover - jedes Kindbit wird unabhängig von einem seiner Elternteile mit gleicher Wahrscheinlichkeit ausgewählt.
  
• Cycle-Crossover - definiert Zyklen von Positionen, die zwischen den Eltern ausgetauscht werden, wobei die Einzigartigkeit der Elemente erhalten bleibt.
• PMX (Partially Mapped Crossover) - bewahrt die relative Reihenfolge und Position der Elemente aus den Elternchromosomen, wird bei Problemen verwendet, bei denen die Reihenfolge wichtig ist, wie z. B. beim „Travelling Salesman“ Problem.
• ОX (Order-Crossover) - erzeugt einen Nachkommen, indem die Reihenfolge der Gene eines Elternteils beibehalten wird und die fehlenden Gene vom anderen Elternteil in der Reihenfolge geerbt werden, in der sie erscheinen.
  

Crossover werden nicht nur für die binäre, sondern auch für die reelle Darstellung verwendet. Zu den wichtigsten Arten von echten Crossovers gehören:

• Blend-Crossover (BLX-α) - erzeugt Kinder, deren Werte zufällig innerhalb des Bereichs gewählt werden, der durch die Werte der Eltern und den Parameter „α“, der diesen Bereich erweitert, definiert ist.
• Symmetrischer Blend-Crossover (SBX) - verwendet verschiedene Wahrscheinlichkeitsverteilungen, um Kinder zu erzeugen, deren Werte zwischen den Werten der Eltern liegen, wobei der Grad der Differenz zwischen den Eltern berücksichtigt wird.
  
• Real-Coded Crossover - wendet arithmetische Operationen auf reelle Zahlen an, z. B. durch Mittelwertbildung oder gewichtete Summierung der übergeordneten Werte.
  
• Differentielles Crossover - wird z. B. in der differentiellen Evolution verwendet, bei der ein neuer Vektor erzeugt wird, indem die gewichtete Differenz zwischen zwei Individuen zum dritten addiert wird.
  
• Interpolations-Crossover - erzeugt Kinder durch Interpolation zwischen Elternwerten, was eine lineare oder nichtlineare Interpolation beinhalten kann.
  
• Normal Distribution Crossover - Kinder werden unter Verwendung einer Normalverteilung um die Werte der Eltern generiert, wodurch der Lösungsraum um die Elternpunkte herum erforscht werden kann.
  

6. Die Arten der „Mutations“-Methoden

Der Mutationsoperator ist eine der wichtigsten Operationen in genetischen Algorithmen und wird verwendet, um zufällige Änderungen an der genetischen Information von Individuen in einer Population vorzunehmen. Er hilft, neue Lösungen zu erforschen und zu vermeiden, dass man in lokalen Optima stecken bleibt.

In der Biologie ist eine Mutation äußerst selten und hat in der Regel nur begrenzte Auswirkungen auf die Nachkommenschaft. Die Anzahl der Individuen jeder Art in der Natur geht in die Millionen, sodass das genetische Material der Population sehr vielfältig ist, es sei denn, es handelt sich um gefährdete Arten (es gibt sogar den Begriff „Flaschenhals“ - die Mindestanzahl von Individuen, unter der eine Art ausstirbt). Anders als in der lebenden Natur sind Mutationen in den meisten Implementierungen genetischer Algorithmen ein seltenes Phänomen (ca. 1-2 %). Dies ist besonders wichtig bei genetischen Algorithmen, wo die Populationsgrößen in der Regel klein sind und Inzucht ein Problem darstellen kann, sodass evolutionäre Sackgassen häufiger vorkommen als in der biologischen Evolution. In der Biologie spricht man gewöhnlich von Populationen, die aus Millionen von Individuen bestehen, während wir es bei genetischen Algorithmen (und Optimierungsalgorithmen im Allgemeinen) mit nur einigen Dutzend oder Hunderten von Individuen zu tun haben und Mutation die einzige Möglichkeit ist, dem Genpool der Population neue Informationen hinzuzufügen.

Wenn also bestimmte genetische Informationen in der Population fehlen, bietet eine Mutation die Möglichkeit, diese einzuführen.

Die Mutation spielt also mehrere wichtige Rollen:

1. Suche nach neuen Lösungen - dies ermöglicht dem Algorithmus die Suche nach neuen potenziellen Lösungen für das Problem, die möglicherweise außerhalb des durch Crossover erforschten Lösungsraums liegen. Die Mutation ermöglicht es dem Algorithmus, durch den Lösungsraum zu „springen“ und neue Optionen zu entdecken.
2. Erhaltung der genetischen Vielfalt - ohne Mutation kann der Algorithmus auf das Problem stoßen, dass er zu einem lokalen Optimum konvergiert, bei dem alle Individuen ähnliche genetische Informationen haben. Die Mutation ermöglicht zufällige Veränderungen, die dazu beitragen, eine vorzeitige Konvergenz zu vermeiden und die Vielfalt in der Population zu erhalten.
3. Überwindung evolutionärer Sackgassen - während der Evolution können genetische Algorithmen manchmal in evolutionären Sackgassen stecken bleiben, wo der Lösungsraum erschöpft ist und keine bessere Lösung erreicht werden kann. Mutation kann helfen, diese Sackgassen zu überwinden, indem zufällige Änderungen eingeführt werden, die neue Möglichkeiten eröffnen und den Algorithmus vorwärts bringen.

Eine zu hohe Mutationswahrscheinlichkeit kann dazu führen, dass der Algorithmus zu einer Zufallssuche degeneriert, und eine zu niedrige Wahrscheinlichkeit kann zu Konvergenzproblemen und einem Verlust an Vielfalt führen.

Bei Algorithmen mit binärer Darstellung lassen sich folgende Arten von Mutationsmethoden unterscheiden:

• Ein-Punkt-Mutation - der Wert eines zufällig ausgewählten Bits in der binären Zeichenfolge wird invertiert. Wenn wir zum Beispiel die Zeichenkette „101010“ haben, kann eine Ein-Punkt-Mutation sie in „100010“ ändern.
• Mehrpunktmutation - mehrere zufällige Positionen in einer binären Zeichenfolge werden ausgewählt und die Werte an diesen Positionen werden invertiert. Wenn wir zum Beispiel die Zeichenkette „101010“ haben, dann kann eine Mehrpunktmutation sie in „100000“ oder „001010“ ändern.
  
• Wahrscheinlichkeitsbasierte (stochastische) Mutation - jedes Bit hat eine bestimmte Wahrscheinlichkeit, sich bei einer Mutation zu verändern.
  
• Vollständige Invertierung - eine vollständige Invertierung der Bits in der binären Zeichenfolge. Wenn wir zum Beispiel die Zeichenkette „101010“ haben, wird sie durch Inversion in „010101“ geändert.
• Punktinversion - eine Bruchstelle in der Gensequenz wird zufällig ausgewählt, das Chromosom wird an dieser Stelle in zwei Teile geteilt und die Teile werden vertauscht.  

Bild 2. Wahrscheinlichkeitsbedingte Mutation

In Optimierungsalgorithmen mit Darstellung reeller Daten werden folgende Arten von Mutationen unterschieden. Ich werde aber nicht im Detail auf sie eingehen:

• Zufallsmutations-Operator.
• Gaußscher Mutationsoperator.
• Arithmetischer Kriechoperator für reelle Zahlen.
• Geometrischer Kriechoperator für reeller Zahlen.
• Power-Mutationsoperator.
• Michalewiczs nicht-einheitlicher Operator.
• Dynamischer Mutationsoperator.

Im Allgemeinen kann bei allen Optimierungsalgorithmen jede Operation, die darauf abzielt, die Komponenten des Suchraums zu verändern, als Mutation bezeichnet werden, wenn kein Informationsaustausch zwischen Agenten (Individuen) stattfindet. Sie sind oft sehr spezifisch und entsprechen einer bestimmten Suchstrategie des Algorithmus.

7. Zusammenfassung

Dies ist der erste Teil des Artikels über den „Binären Genetischen Algorithmus“, in dem wir fast alle Methoden betrachtet haben, die nicht nur in diesem Algorithmus, sondern auch in anderen Algorithmen zur Optimierung von Populationen verwendet werden, auch wenn sie die Begriffe „Selektion“, „Crossover“ und „Mutation“ nicht verwenden. Wenn wir diese Methoden gut studieren und verstehen, werden wir in der Lage sein, Optimierungsprobleme bewusster anzugehen, und es können neue Ideen für die Implementierung und Modifizierung bekannter Algorithmen sowie für die Entwicklung neuer Algorithmen entstehen. Wir haben auch verschiedene Möglichkeiten der Informationsdarstellung in Optimierungsalgorithmen sowie deren Vor- und Nachteile untersucht, die zu neuen Ideen und neuen Ansätzen führen können.