โจทย์
อัลกอริทึมเชิงพันธุกรรม ปรับปรุงประชากรของคำตอบที่เป็นไปได้แบบเดียวกับวิวัฒนาการ: เลือกพ่อแม่ที่แข็งแรง รวมเข้าด้วยกัน และเพิ่มการกลายพันธุ์แบบสุ่ม ในที่นี้คำตอบคือสตริงบิต และความเหมาะสมคือจำนวนเลข 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] แต่ละรายการตามลำดับ โดยกลับบิตนั้นของลูกตัวนั้น
จง implement ga_generation(population, tournaments, crossover_points, mutations)
อินพุต
population: สตริงบิต N ตัวที่ยาว L เท่ากัน
tournaments: คู่ index ของประชากร 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 ตัวเดียว แต่ละทัวร์นาเมนต์จึงชนะโดย index แรก: parent1 = "10" และ parent2 = "01" ตัดหลัง 1 บิตได้ "11" และ "00"
แหล่งอ้างอิง
โจทย์นี้ปรับให้เหมาะกับ CodeUtility กรุณาทำตามคำชี้แจงและข้อจำกัดด้านบน