Une génération d'algorithme génétique

Un algorithme génétique améliore une population de solutions candidates comme le fait l'évolution : sélectionner des parents performants, les combiner et ajouter des mutations aléatoires. Ici, les candidats sont des chaînes de bits et la fitness est le nombre de 1 (le problème OneMax).

Pour rendre le tout testable, chaque choix aléatoire est fourni. Avec N chaînes (N pair), construisez N enfants par paires. Pour la paire k = 0, 1, …, N/2 - 1 :

1. Sélection : parent1 remporte le tournoi tournaments[2k] et parent2 remporte tournaments[2k + 1]. Un tournoi [i, j] est remporté par celle de population[i] et population[j] qui a le plus de 1 ; en cas d'égalité, population[i] gagne.
2. Croisement en c = crossover_points[k] : enfant 2k = parent1[0:c] + parent2[c:] et enfant 2k + 1 = parent2[0:c] + parent1[c:].

Appliquez ensuite chaque mutation [child, position] dans l'ordre en inversant ce bit de cet enfant.

Implémentez ga_generation(population, tournaments, crossover_points, mutations).

Entrée

population : N chaînes de bits de même longueur L.

tournaments : N paires d'indices de la population.

crossover_points : N/2 points de coupe, chacun entre 1 et L - 1.

mutations : Des paires [child, position] (peut être vide).

Sortie

Renvoyez les N enfants dans l'ordre.

Contraintes

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

0 ≤ nombre de mutations ≤ 1 000

Exemples

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

Sortie attendue :
expected = ["0100", "1111", "1011", "0111"]

Entrée :
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};

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

Entrée :
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};

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

Entrée :
mutations = []
population = ["10", "01"]
tournaments = [
    [0, 1],
    [1, 0]
]
crossover_points = [1]

Sortie attendue :
expected = ["11", "00"]

Entrée :
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};

Sortie attendue :
std::vector<std::string> expected = {"11", "00"};

Entrée :
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};

Sortie attendue :
string[] expected = new string[] {"11", "00"};

Références

Ce défi a été adapté pour CodeUtility. Suivez l'énoncé et les contraintes ci-dessus.

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