Una generazione di un algoritmo genetico

Un algoritmo genetico migliora una popolazione di soluzioni candidate come fa l'evoluzione: seleziona genitori adatti, li combina e aggiunge mutazioni casuali. Qui i candidati sono stringhe di bit e la fitness è il numero di 1 (il problema OneMax).

Per renderlo verificabile, ogni scelta casuale viene fornita. Con N stringhe (N pari), costruisci N figli a coppie. Per la coppia k = 0, 1, …, N/2 - 1:

1. Selezione: parent1 vince il torneo tournaments[2k] e parent2 vince tournaments[2k + 1]. Un torneo [i, j] lo vince quella tra population[i] e population[j] che ha più 1; in caso di parità vince population[i].
2. Crossover in c = crossover_points[k]: figlio 2k = parent1[0:c] + parent2[c:] e figlio 2k + 1 = parent2[0:c] + parent1[c:].

Poi applica ogni mutazione [child, position] in ordine invertendo quel bit di quel figlio.

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

Input

population: N stringhe di bit della stessa lunghezza L.

tournaments: N coppie di indici della popolazione.

crossover_points: N/2 punti di taglio, ciascuno tra 1 e L - 1.

mutations: Coppie [child, position] (può essere vuoto).

Output

Restituisci gli N figli in ordine.

Vincoli

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

0 ≤ numero di mutazioni ≤ 1.000

Esempi

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

Output atteso:
expected = ["0100", "1111", "1011", "0111"]

Input:
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};

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

Input:
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};

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

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

Output atteso:
expected = ["11", "00"]

Input:
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};

Output atteso:
std::vector<std::string> expected = {"11", "00"};

Input:
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};

Output atteso:
string[] expected = new string[] {"11", "00"};

Riferimenti

Questa sfida è adattata per CodeUtility. Segui la traccia e i vincoli sopra.

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