Одно поколение генетического алгоритма

Генетический алгоритм улучшает популяцию решений-кандидатов так же, как эволюция: отбирает приспособленных родителей, скрещивает их и добавляет случайные мутации. Здесь кандидаты — битовые строки, а приспособленность — число единиц (задача OneMax).

Чтобы алгоритм можно было проверить, все случайные выборы передаются на вход. Из N строк (N чётно) постройте N потомков парами. Для пары k = 0, 1, …, N/2 - 1:

1. Отбор: parent1 — победитель турнира tournaments[2k], а parent2 — победитель tournaments[2k + 1]. Турнир [i, j] выигрывает та из строк population[i] и population[j], в которой больше единиц; при равенстве выигрывает population[i].
2. Скрещивание в точке c = crossover_points[k]: потомок 2k = parent1[0:c] + parent2[c:] и потомок 2k + 1 = parent2[0:c] + parent1[c:].

Затем примените каждую мутацию [child, position] по порядку, инвертируя этот бит этого потомка.

Реализуйте ga_generation(population, tournaments, crossover_points, mutations).

Входные данные

population: N битовых строк одинаковой длины L.

tournaments: N пар индексов популяции.

crossover_points: N/2 точек разреза, каждая от 1 до L - 1.

mutations: Пары [child, position] (могут отсутствовать).

Выходные данные

Верните N потомков по порядку.

Ограничения

2 ≤ N ≤ 200 (N чётно), 2 ≤ L ≤ 64

0 ≤ число мутаций ≤ 1 000

Примеры

Ввод:
mutations = [
    [0, 0]
]
population = ["0000", "1111", "1100", "0011"]
tournaments = [
    [0, 1],
    [2, 3],
    [1, 2],
    [0, 3]
]
crossover_points = [2, 1]

Ожидаемый вывод:
expected = ["0100", "1111", "1011", "0111"]

Ввод:
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};

Ожидаемый вывод:
std::vector<std::string> expected = {"0100", "1111", "1011", "0111"};

Ввод:
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};

Ожидаемый вывод:
string[] expected = new string[] {"0100", "1111", "1011", "0111"};

Ввод:
mutations = []
population = ["10", "01"]
tournaments = [
    [0, 1],
    [1, 0]
]
crossover_points = [1]

Ожидаемый вывод:
expected = ["11", "00"]

Ввод:
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};

Ожидаемый вывод:
std::vector<std::string> expected = {"11", "00"};

Ввод:
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};

Ожидаемый вывод:
string[] expected = new string[] {"11", "00"};

Ссылки

Это задание адаптировано для CodeUtility. Следуйте условию и ограничениям выше.

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