Problema
Um algoritmo genético melhora uma população de soluções candidatas como a evolução faz: seleciona pais aptos, combina-os e adiciona mutações aleatórias. Aqui os candidatos são strings de bits e a aptidão é o número de 1s (o problema OneMax).
Para que possa ser testado, cada escolha aleatória é fornecida. Com N strings (N par), construa N filhos em pares. Para o par k = 0, 1, …, N/2 - 1:
- Seleção: parent1 vence o torneio
tournaments[2k]e parent2 vencetournaments[2k + 1]. Um torneio[i, j]é vencido por aquela entrepopulation[i]epopulation[j]que tiver mais 1s; em caso de empate,population[i]vence. - Cruzamento em c =
crossover_points[k]: filho 2k = parent1[0:c] + parent2[c:] e filho 2k + 1 = parent2[0:c] + parent1[c:].
Depois aplique cada mutação [child, position] em ordem, invertendo aquele bit daquele filho.
Implemente ga_generation(population, tournaments, crossover_points, mutations).
Entrada
population: N strings de bits com o mesmo comprimento L.
tournaments: N pares de índices da população.
crossover_points: N/2 pontos de corte, cada um entre 1 e L - 1.
mutations: Pares [child, position] (pode ser vazio).
Saída
Retorne os N filhos em ordem.
Restrições
2 ≤ N ≤ 200 (N par), 2 ≤ L ≤ 64
0 ≤ número de mutações ≤ 1.000
Exemplos
Entrada:
mutations = [
[0, 0]
]
population = ["0000", "1111", "1100", "0011"]
tournaments = [
[0, 1],
[2, 3],
[1, 2],
[0, 3]
]
crossover_points = [2, 1]
Saída 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};
Saída 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};
Saída esperada:
string[] expected = new string[] {"0100", "1111", "1011", "0111"};Explicação
Par 0: "1111" vence "0000", e "1100" empata com "0011", então a primeira vence. Cortar após 2 bits dá "1100" e "1111". Par 1: pais "1111" e "0011", corte após 1 bit: "1011" e "0111". Por fim, o filho 0 tem o bit 0 invertido: "0100".
Entrada:
mutations = []
population = ["10", "01"]
tournaments = [
[0, 1],
[1, 0]
]
crossover_points = [1]
Saída 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};
Saída 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};
Saída esperada:
string[] expected = new string[] {"11", "00"};Explicação
As duas strings têm um único 1, então cada torneio é vencido pelo primeiro índice: parent1 = "10" e parent2 = "01". Cortar após 1 bit dá "11" e "00".
Como abordar
Tente sozinho primeiro e depois abra uma dica de cada vez.
Dica 1
Construa os filhos em pares, primeiro escolhendo dois pais de cada torneio e depois combinando suas strings binárias em um ponto de corte.
Dica 2
A seleção depende só do fitness, com empates sempre favorecendo o primeiro competidor no par do torneio.
Dica 3
Aplique as mutações depois que todos os filhos forem criados, e garanta que cada flip atinja a string do filho atual.
Complexidade esperada
tempo O(N * L + M), espaço extra O(N * L)
Referências
Este desafio foi adaptado para o CodeUtility. Siga o enunciado e as restrições acima.