Đề 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".
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.