Eine Generation eines genetischen Algorithmus

Ein genetischer Algorithmus verbessert eine Population von Lösungskandidaten so, wie es die Evolution tut: fitte Eltern auswählen, sie kombinieren und zufällige Mutationen hinzufügen. Hier sind die Kandidaten Bitstrings und die Fitness ist die Anzahl der 1en (das OneMax-Problem).

Damit es testbar ist, wird jede Zufallsentscheidung vorgegeben. Bei N Strings (N ist gerade) werden N Kinder paarweise erzeugt. Für Paar k = 0, 1, …, N/2 - 1:

1. Selektion: parent1 gewinnt das Turnier tournaments[2k] und parent2 gewinnt tournaments[2k + 1]. Ein Turnier [i, j] gewinnt derjenige von population[i] und population[j], der mehr 1en hat; bei Gleichstand gewinnt population[i].
2. Crossover bei c = crossover_points[k]: Kind 2k = parent1[0:c] + parent2[c:] und Kind 2k + 1 = parent2[0:c] + parent1[c:].

Wende dann jede Mutation [child, position] der Reihe nach an, indem du dieses Bit dieses Kindes umkehrst.

Implementiere ga_generation(population, tournaments, crossover_points, mutations).

Eingabe

population: N Bitstrings gleicher Länge L.

tournaments: N Paare von Populationsindizes.

crossover_points: N/2 Schnittpunkte, jeweils zwischen 1 und L - 1.

mutations: Paare [child, position] (kann leer sein).

Ausgabe

Gib die N Kinder in Reihenfolge zurück.

Einschränkungen

2 ≤ N ≤ 200 (N gerade), 2 ≤ L ≤ 64

0 ≤ Anzahl der Mutationen ≤ 1.000

Beispiele

Eingabe:
mutations = [
    [0, 0]
]
population = ["0000", "1111", "1100", "0011"]
tournaments = [
    [0, 1],
    [2, 3],
    [1, 2],
    [0, 3]
]
crossover_points = [2, 1]

Erwartete Ausgabe:
expected = ["0100", "1111", "1011", "0111"]

Eingabe:
std::vector<std::vector<long long>> mutations = {
    {0, 0}
};
std::vector<std::string> population = {"0000", "1111", "1100", "0011"};
std::vector<std::vector<long long>> tournaments = {
    {0, 1},
    {2, 3},
    {1, 2},
    {0, 3}
};
std::vector<long long> crossover_points = {2, 1};

Erwartete Ausgabe:
std::vector<std::string> expected = {"0100", "1111", "1011", "0111"};

Eingabe:
long[][] mutations = new long[][] {
    new long[] {0, 0}
};
string[] population = new string[] {"0000", "1111", "1100", "0011"};
long[][] tournaments = new long[][] {
    new long[] {0, 1},
    new long[] {2, 3},
    new long[] {1, 2},
    new long[] {0, 3}
};
long[] crossover_points = new long[] {2, 1};

Erwartete Ausgabe:
string[] expected = new string[] {"0100", "1111", "1011", "0111"};

Eingabe:
mutations = []
population = ["10", "01"]
tournaments = [
    [0, 1],
    [1, 0]
]
crossover_points = [1]

Erwartete Ausgabe:
expected = ["11", "00"]

Eingabe:
std::vector<std::vector<long long>> mutations = {};
std::vector<std::string> population = {"10", "01"};
std::vector<std::vector<long long>> tournaments = {
    {0, 1},
    {1, 0}
};
std::vector<long long> crossover_points = {1};

Erwartete Ausgabe:
std::vector<std::string> expected = {"11", "00"};

Eingabe:
long[][] mutations = new long[][] {};
string[] population = new string[] {"10", "01"};
long[][] tournaments = new long[][] {
    new long[] {0, 1},
    new long[] {1, 0}
};
long[] crossover_points = new long[] {1};

Erwartete Ausgabe:
string[] expected = new string[] {"11", "00"};

Referenzen

Diese Aufgabe wurde für CodeUtility angepasst. Beachte die oben genannten Vorgaben und Einschränkungen.

• Melanie Mitchell, An Introduction to Genetic Algorithms
• Russell and Norvig, Artificial Intelligence: A Modern Approach