समस्या
जेनेटिक एल्गोरिदम उम्मीदवार समाधानों की आबादी को विकास की तरह सुधारता है: योग्य माता-पिता चुनें, उन्हें मिलाएँ, और यादृच्छिक म्यूटेशन जोड़ें। यहाँ उम्मीदवार बिट स्ट्रिंग हैं और फ़िटनेस 1 की संख्या है (OneMax समस्या)।
इसे टेस्ट करने लायक बनाने के लिए हर यादृच्छिक चुनाव दिया जाता है। N स्ट्रिंग (N सम) से जोड़ों में N बच्चे बनाएँ। जोड़ी k = 0, 1, …, N/2 - 1 के लिए:
- चयन: parent1 टूर्नामेंट
tournaments[2k]का विजेता है और parent2tournaments[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
Children को pairs में बनाओ: पहले हर tournament से दो parents चुनो, फिर उनके bit strings को एक cut point पर combine करो.
संकेत 2
Selection सिर्फ fitness पर depend करती है, और tournament pair में tie होने पर हमेशा पहला contestant favor होता है.
संकेत 3
सारे children बन जाने के बाद mutations apply करो, और हर flip current child string पर ही target हो.
अपेक्षित जटिलता
समय O(N * L + M), अतिरिक्त स्थान O(N * L)
संदर्भ
यह चुनौती CodeUtility के लिए अनुकूलित की गई है। ऊपर दिए गए स्टेटमेंट और सीमाओं का पालन करें।