Đề bài
Thuật toán di truyền cải thiện một quần thể lời giải ứng viên theo cách tiến hóa: chọn cha mẹ khỏe, kết hợp chúng, và thêm đột biến ngẫu nhiên. Ở đây các ứng viên là chuỗi bit và độ thích nghi là số bit 1 (bài toán OneMax).
Để có thể kiểm thử, mọi lựa chọn ngẫu nhiên đều được cho sẵn. Với N chuỗi (N chẵn), tạo N con theo từng cặp. Với cặp k = 0, 1, …, N/2 - 1:
- Chọn lọc: parent1 là người thắng giải đấu
tournaments[2k]và parent2 là người thắngtournaments[2k + 1]. Giải đấu[i, j]thuộc về chuỗi nào trongpopulation[i]vàpopulation[j]có nhiều bit 1 hơn; nếu bằng nhau,population[i]thắng. - Lai ghép tại c =
crossover_points[k]: con 2k = parent1[0:c] + parent2[c:] và con 2k + 1 = parent2[0:c] + parent1[c:].
Sau đó áp dụng từng đột biến [child, position] theo thứ tự bằng cách đảo bit đó của con đó.
Hãy viết ga_generation(population, tournaments, crossover_points, mutations).
Đầu vào
population: N chuỗi bit cùng độ dài L.
tournaments: N cặp chỉ số trong quần thể.
crossover_points: N/2 điểm cắt, mỗi điểm từ 1 đến L - 1.
mutations: Các cặp [child, position] (có thể rỗng).
Đầu ra
Trả về N con theo thứ tự.
Ràng buộc
2 ≤ N ≤ 200 (N chẵn), 2 ≤ L ≤ 64
0 ≤ số đột biến ≤ 1.000
Ví dụ
Đầu vào:
mutations = [
[0, 0]
]
population = ["0000", "1111", "1100", "0011"]
tournaments = [
[0, 1],
[2, 3],
[1, 2],
[0, 3]
]
crossover_points = [2, 1]
Kết quả mong đợi:
expected = ["0100", "1111", "1011", "0111"]Đầu vào:
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};
Kết quả mong đợi:
std::vector<std::string> expected = {"0100", "1111", "1011", "0111"};Đầu vào:
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};
Kết quả mong đợi:
string[] expected = new string[] {"0100", "1111", "1011", "0111"};Giải thích
Cặp 0: "1111" thắng "0000", còn "1100" hòa "0011" nên chuỗi đầu thắng. Cắt sau 2 bit được "1100" và "1111". Cặp 1: cha mẹ là "1111" và "0011", cắt sau 1 bit: "1011" và "0111". Cuối cùng con 0 bị đảo bit 0: "0100".
Đầu vào:
mutations = []
population = ["10", "01"]
tournaments = [
[0, 1],
[1, 0]
]
crossover_points = [1]
Kết quả mong đợi:
expected = ["11", "00"]Đầu vào:
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};
Kết quả mong đợi:
std::vector<std::string> expected = {"11", "00"};Đầu vào:
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};
Kết quả mong đợi:
string[] expected = new string[] {"11", "00"};Giải thích
Cả hai chuỗi đều có một bit 1, nên mỗi giải đấu thuộc về chỉ số đầu tiên: parent1 = "10" và parent2 = "01". Cắt sau 1 bit được "11" và "00".
Hướng tiếp cận
Hãy tự thử trước, sau đó mở từng gợi ý một.
Gợi ý 1
Tạo con theo cặp bằng cách chọn hai cha mẹ từ mỗi vòng đấu, rồi ghép chuỗi bit tại một điểm cắt.
Gợi ý 2
Việc chọn chỉ dựa trên fitness, với trường hợp hòa luôn ưu tiên thí sinh đầu tiên trong cặp đấu.
Gợi ý 3
Áp dụng đột biến sau khi tạo xong tất cả con, và đảm bảo mỗi lần lật bit tác động lên chuỗi con hiện tại.
Độ phức tạp mong đợi
thời gian O(N * L + M), bộ nhớ phụ O(N * L)
Tham khảo
Thử thách này đã được điều chỉnh cho CodeUtility. Hãy làm theo đề bài và các ràng buộc ở trên.