문제
유전 알고리즘은 진화와 같은 방식으로 후보 해 집단을 개선합니다. 적합한 부모를 고르고, 결합하고, 무작위 돌연변이를 더합니다. 여기서 후보는 비트 문자열이고 적합도는 1의 개수입니다 (OneMax 문제).
테스트할 수 있도록 모든 무작위 선택이 주어집니다. N개의 문자열 (N은 짝수)로 N개의 자식을 쌍으로 만듭니다. 쌍 k = 0, 1, …, N/2 - 1에 대해:
- 선택: parent1은 토너먼트
tournaments[2k]의 승자이고 parent2는tournaments[2k + 1]의 승자입니다. 토너먼트[i, j]는population[i]와population[j]중 1이 더 많은 쪽이 이기며, 같으면population[i]가 이깁니다. - 교차 (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: 길이가 L로 같은 N개의 비트 문자열.
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"};설명
쌍 0: "1111"이 "0000"을 이기고, "1100"과 "0011"은 동점이므로 앞의 것이 이깁니다. 2비트 뒤에서 자르면 "1100"과 "1111". 쌍 1: 부모는 "1111"과 "0011", 1비트 뒤에서 자르면 "1011"과 "0111". 마지막으로 자식 0의 비트 0을 뒤집어 "0100".
입력:
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"};설명
두 문자열 모두 1이 하나이므로 각 토너먼트는 첫 번째 인덱스가 이깁니다: parent1 = "10", parent2 = "01". 1비트 뒤에서 자르면 "11"과 "00".
접근 방법
먼저 스스로 풀어 본 뒤 힌트를 하나씩 열어 보세요.
힌트 1
각 tournament에서 부모 2명을 고른 뒤, 비트 문자열을 한 절단점에서 합쳐 자식을 쌍으로 만드세요.
힌트 2
선택은 fitness만으로 결정되고, 동률이면 tournament 쌍에서 항상 첫 번째 참가자를 우선합니다.
힌트 3
변이는 모든 자식을 만든 뒤 적용하고, 각 flip이 현재 자식 문자열을 대상으로 하도록 하세요.
예상 복잡도
시간 O(N * L + M), 추가 공간 O(N * L)
참고 자료
이 문제는 CodeUtility에 맞게 수정되었습니다. 위의 설명과 제한 조건을 따르세요.