모든 챌린지
보통 1명 해결 정답률 100.0%

One Generation of a Genetic Algorithm

Breed the next generation of bit strings with tournament selection, single-point crossover and mutation.

배우게 될 내용

  • Select parents with tournaments
  • Combine solutions with crossover
  • Add variation with mutation

문제

번역본 보기

A genetic algorithm improves a population of candidate solutions the way evolution does: select fit parents, combine them, and add random mutations. Here the candidates are bit strings and fitness is the number of 1s (the OneMax problem).

To make it testable, every random choice is given. With N strings (N is even), build N children in pairs. For pair k = 0, 1, …, N/2 - 1:

  1. Selection: parent1 wins tournament tournaments[2k] and parent2 wins tournaments[2k + 1]. A tournament [i, j] is won by whichever of population[i] and population[j] has more 1s; on a tie, population[i] wins.
  2. Crossover at c = crossover_points[k]: child 2k = parent1[0:c] + parent2[c:] and child 2k + 1 = parent2[0:c] + parent1[c:].

Then apply each mutation [child, position] in order by flipping that bit of that child.

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

Input

population: N bit strings of equal length L.

tournaments: N pairs of population indices.

crossover_points: N/2 cut points, each between 1 and L - 1.

mutations: [child, position] pairs (may be empty).

Output

Return the N children in order.

제약 조건

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

0 ≤ number of mutations ≤ 1,000

예시

예시 1
입력:
population = ["0000", "1111", "1100", "0011"]
tournaments = [
    [0, 1],
    [2, 3],
    [1, 2],
    [0, 3]
]
crossover_points = [2, 1]
mutations = [
    [0, 0]
]

예상 출력:
expected = ["0100", "1111", "1011", "0111"]
입력:
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::vector<long long>> mutations = {
    {0, 0}
};

예상 출력:
std::vector<std::string> expected = {"0100", "1111", "1011", "0111"};
입력:
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};
long[][] mutations = new long[][] {
    new long[] {0, 0}
};

예상 출력:
string[] expected = new string[] {"0100", "1111", "1011", "0111"};

설명

Pair 0: "1111" beats "0000", and "1100" ties "0011" so the first one wins. Cutting after 2 bits gives "1100" and "1111". Pair 1: parents "1111" and "0011", cut after 1 bit: "1011" and "0111". Finally child 0 has bit 0 flipped: "0100".

예시 2
입력:
population = ["10", "01"]
tournaments = [
    [0, 1],
    [1, 0]
]
crossover_points = [1]
mutations = []

예상 출력:
expected = ["11", "00"]
입력:
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::vector<long long>> mutations = {};

예상 출력:
std::vector<std::string> expected = {"11", "00"};
입력:
string[] population = new string[] {"10", "01"};
long[][] tournaments = new long[][] {
    new long[] {0, 1},
    new long[] {1, 0}
};
long[] crossover_points = new long[] {1};
long[][] mutations = new long[][] {};

예상 출력:
string[] expected = new string[] {"11", "00"};

설명

Both strings have one 1, so each tournament is won by its first index: parent1 = "10" and parent2 = "01". Cutting after 1 bit gives "11" and "00".

접근 방법

먼저 스스로 풀어 본 뒤 힌트를 하나씩 열어 보세요.

힌트 1

Build children in pairs by first choosing two parents from each tournament, then combining their bit strings at one cut point.

힌트 2

Selection depends on fitness only, with ties always favoring the first contestant in the tournament pair.

힌트 3

Apply mutations after all children are created, and make sure each flip targets the current child string.

예상 복잡도

O(N * L + M) time, O(N * L) extra space

참고 자료

이 문제는 CodeUtility에 맞게 수정되었습니다. 위의 설명과 제한 조건을 따르세요.

코더마다 가장 좋은 통과 풀이입니다. 더 빠르고, 메모리를 덜 쓰고, 평가가 좋은 풀이가 위에 옵니다.

# 코더 언어 시간 메모리 AI 평가 풀이
1 ННикита Python 769 ms - 4/5 코드 보기

다른 사람의 풀이 보기

커뮤니티 솔루션

스포일러: 아래에 1개 전체 솔루션 있음 먼저 직접 풀어보세요. 다른 개발자의 코드와 AI 리뷰도 참고할 수 있습니다. 로그인하고 문제를 풀면 토론에 참여할 수 있습니다.