Una generación de un algoritmo genético

Un algoritmo genético mejora una población de soluciones candidatas como lo hace la evolución: selecciona padres aptos, los combina y añade mutaciones aleatorias. Aquí los candidatos son cadenas de bits y la aptitud es el número de 1 (el problema OneMax).

Para que se pueda probar, cada elección aleatoria se proporciona. Con N cadenas (N par), construye N hijos por parejas. Para la pareja k = 0, 1, …, N/2 - 1:

1. Selección: parent1 gana el torneo tournaments[2k] y parent2 gana tournaments[2k + 1]. Un torneo [i, j] lo gana la de population[i] y population[j] que tenga más 1; en caso de empate, gana population[i].
2. Cruce en c = crossover_points[k]: hijo 2k = parent1[0:c] + parent2[c:] e hijo 2k + 1 = parent2[0:c] + parent1[c:].

Después aplica cada mutación [child, position] en orden invirtiendo ese bit de ese hijo.

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

Entrada

population: N cadenas de bits de la misma longitud L.

tournaments: N parejas de índices de la población.

crossover_points: N/2 puntos de corte, cada uno entre 1 y L - 1.

mutations: Parejas [child, position] (puede estar vacío).

Salida

Devuelve los N hijos en orden.

Restricciones

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

0 ≤ número de mutaciones ≤ 1.000

Ejemplos

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

Salida esperada:
expected = ["0100", "1111", "1011", "0111"]

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

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

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

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

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

Salida esperada:
expected = ["11", "00"]

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

Salida esperada:
std::vector<std::string> expected = {"11", "00"};

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

Salida esperada:
string[] expected = new string[] {"11", "00"};

Referencias

Este reto está adaptado para CodeUtility. Sigue el enunciado y las restricciones indicadas arriba.

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