जेनेटिक एल्गोरिदम (या ग्राहक हमेशा राजा होता है - और अक्सर मूर्ख होता है)

(संस्करण 2, सही टाइपो के साथ - मुझे उम्मीद है कि हर कोई ...)

नमस्कार, हेब्र!

अब वह बैठा था, एक मित्र के लिए आनुवंशिक एल्गोरिथम का एक प्रोटोटाइप बना रहा था। उससे साझा करने के लिए प्रेरित किया गया है, और कुछ अन्य विचार ...

दिया (ग्राहक ने आदेश दिया): एक निश्चित राज्य में, गोदाम में 100 सेल हैं। माल उसमें है। मात्रा एक्स को कैसे लें ताकि सभी शामिल कोशिकाओं को अंत तक खाली कर सकें? ठीक है, अर्थात्, आपके पास एक सेल प्रकार है [34, 10, 32, 32, 33, 41, 44, 4, 28, 23, 22, 28, 29, 14, 28, 15, 38, 49, 30, 24, 24] 18, 9, 15, 8, 17, 9, 2, 7, 30, 29, 29, 2, 28, 23, 19, 4, 15, 30, 38, 3, 14, 21, 43, 50, 29, 29 14, 17, 12, 25, 15, 23, 28, 47, 38, 29, 7, 36, 45, 25, 6, 25, 11, 10, 1, 19, 37, 24, 27, 50, 12, 1, 1, 44, 22, 48, 13, 46, 49, 11, 33, 29, 4, 19, 33, 12, 3, 47, 27, 26, 45, 40, 37, 21, 2, 8, 8 ४१, ५, १, ९, ५] - कैसे डायल करें, ४०

ठीक है, आप बस्ट कर सकते हैं, यकीन है कि कुछ स्मार्ट है, लेकिन आप इसे एक जेनेटिक एल्गोरिदम के साथ हल कर सकते हैं ...


पहला सवाल: अपने दिमाग को क्यों सुखाएं, क्योंकि अगर आप सिर्फ सूची से गुजरते हैं, तो आपको इसके लिए पहली दो कोशिकाओं से लेने की जरूरत है - दूसरा, हालांकि, शेष रहेगा। और आपको बहुत दूर नहीं जाना पड़ेगा। लेकिन देखने के लिए, ग्राहक एक पूर्णतावादी है, वह चाहता है कि यह एक फार्मेसी में हो। संभवतः सोने के वजन में एक सेल गोदाम में। ऐसा होता है।

दूसरा सवाल: यदि आप इसे बढ़ते क्रम में क्रमबद्ध करते हैं, तो आप निश्चित रूप से बहुत अधिक कोशिकाओं को स्वाइप कर सकते हैं ... हमारे उदाहरण में, दस से कम कोशिकाओं वाले बहुत सारे सेल हैं। शायद, ग्राहक भी नहीं चाहता;) मुझे भी ऐसे लोग मिले: मैं यहां का मालिक हूं। उन्होंने तुमसे कहा - यह करो, सवाल मत पूछो।

(खैर, मेरे मुवक्किल नहीं, अन्यथा मैं एक बार फिर से मानव मन में विश्वास खो देता ...)

खैर, भगवान उसके साथ रहें, सभी की अपनी प्राथमिकताएं हैं ... फिर हम आनुवंशिक एल्गोरिदम के बारे में बात करेंगे - हमें किसी तरह इसे हल करना होगा ... हम जावा में लिखेंगे।

उन लोगों के लिए जिन्होंने वास्तव में उनके बारे में पहले नहीं सुना है: मातृ प्रकृति की नकल करें।

1. व्यवहार को सांकेतिक शब्दों में बदलना
2. हम यह जाँचते हैं कि उपयुक्त बेंचमार्क की मदद से प्रत्येक विकल्प कितनी अच्छी तरह काम करता है
3. अगली पीढ़ी के लिए उनके गुणों पर सबसे अच्छा पास

प्रकृति में अंतिम चरण में, दो घटक होते हैं: क्रॉसिंग ओवर (गुणसूत्र के समान भागों के बीच वर्णों का आदान-प्रदान) और उत्परिवर्तन (आनुवंशिक कोड में सहज परिवर्तन)। हाय, हाई स्कूल;)

शायद यही सब है। हम कोड लेंगे कि कौन से सेल लेने हैं, और किस से नहीं। हमारे पास 100 कोशिकाएं हैं, जिसका अर्थ है कि हमारा गुणसूत्र 100 सच्चे / झूठे तत्वों का होगा, इसके लिए मैंने स्ट्रिंग लिया, जिसमें शून्य और लिखे जाएंगे। वे, निश्चित रूप से, 100 होंगे।

इस प्रक्रिया में बेंचमार्क सबसे महत्वपूर्ण है। प्रकृति एक आला की तलाश में है, और कंप्यूटर प्रकृति इसे बेवकूफ बनाने और जीवित रहने के लिए आपके बेंचमार्क में एक छेद की तलाश करेगी। अद्भुत, ईमानदारी से ...

सभी ने कहा, कुछ इस तरह से:

private static int benchmark(String chromosome, boolean verbose) { int sum = 0; char[] cArr = chromosome.toCharArray(); for (int i = 0; i < cnt_bins; i++) { if (cArr[i] == '1') { sum += stock[i]; if (verbose) System.out.println("storage bin " + i + ":\t+" + stock[i] + "\t= " + sum); } if (sum == target_qty) { return 0; } } return Math.abs(target_qty - sum); } 

विचार यह है कि हम वांछित संख्या 40 से दूर हैं, इससे भी बदतर। यदि हमने 40 का स्कोर किया है, तो हम गुणसूत्र पर आगे नहीं बढ़ेंगे, हम जीत गए। हम निश्चित रूप से बढ़ते क्रम में - कम पेनल्टी अंक, बेहतर होंगे।

पहली पीढ़ी बेतरतीब ढंग से बनाई गई है:

 // create 1st generation for (int i = 0; i < generation_size; i++) { StringWriter sw = new StringWriter(); for (int j = 0; j < cnt_bins; j++) { // take stock from this bin? sw.append(rnd.nextBoolean() ? "1" : "0"); } chromosomes.add(sw.toString()); sw.close(); } 

चूंकि आनुवंशिक एल्गोरिथम, वास्तव में, लक्ष्य तक पहुंचता है, लेकिन हमेशा इसे हासिल नहीं करता है, इसलिए पीढ़ियों की संख्या को सीमित करना महत्वपूर्ण है।

 for (int generationNo = 0; generationNo < maxGenerationCnt; generationNo++) { // evaluate List<SimpleEntry<String, Integer>> evaluated = new ArrayList<>(); for (int i = 0; i < chromosomes.size(); i++) { evaluated.add( new SimpleEntry<String, Integer>(chromosomes.get(i), benchmark(chromosomes.get(i), false))); } // ...    , .  ... } System.out.println("No solution found after " + maxGenerationCnt + " iterations"); 

क्रमबद्ध करें, सर्वोत्तम छोड़ें:

 ... // sort evaluated = evaluated.stream().sorted((e1, e2) -> Integer.compare(e1.getValue(), e2.getValue())) .collect(Collectors.toList()); System.out.println("Generation " + generationNo + "; Best / last parent / worst: " + evaluated.get(0).getValue() + " / " + evaluated.get(best_size).getValue() + " / " + evaluated.get(evaluated.size() - 1).getValue()); if (evaluated.get(0).getValue() == 0) { System.out.println("Solution found"); benchmark(evaluated.get(0).getKey(), true); System.exit(0); } // leave only the best evaluated = evaluated.subList(0, best_size); ... 

हम नस्ल और गुणा करते हैं, आबादी के आकार को पुनर्स्थापित करते हैं। यही है, हम बेतरतीब ढंग से माता-पिता का चयन करते हैं, समान संकेतों को जोड़ते हैं (यदि आप भाग्यशाली हैं - एक्सचेंज फ्लैग देखें), म्यूट करें (म्यूटेशन फ्लैग), एक चमत्कार की प्रतीक्षा करें ...

 // replication List<String> parents = evaluated.stream().map(e -> e.getKey()).collect(Collectors.toList()); chromosomes.clear(); while (chromosomes.size() < generation_size) { int parent1 = rnd.nextInt(evaluated.size()); int parent2 = rnd.nextInt(evaluated.size()); char[] cArr1 = parents.get(parent1).toCharArray(); char[] cArr2 = parents.get(parent2).toCharArray(); for (int i = 0; i < cnt_bins; i++) { boolean exchange = rnd.nextDouble() < exchange_rate; if (exchange) { char c1 = cArr1[i]; char c2 = cArr2[i]; // exchange both values cArr1[i] = c2; cArr2[i] = c1; } // mutation boolean mutation = rnd.nextDouble() < mutation_rate; if (mutation) { cArr1[i] = rnd.nextBoolean() ? '1' : '0'; } mutation = rnd.nextDouble() < mutation_rate; if (mutation) { cArr2[i] = rnd.nextBoolean() ? '1' : '0'; } } chromosomes.add(new String(cArr1)); chromosomes.add(new String(cArr2)); } 

और अंत में: यदि आप मापदंडों से छेड़छाड़ करते हैं - बहुत अधिक उत्परिवर्तन, बहुत कम जनसंख्या का आकार, आदि। - सभी खराब परिणामों को स्थिर या यहां तक ​​कि दे देंगे।

यह समस्या, वैसे, अक्सर पहले से ही यादृच्छिक रूप से हल हो जाती है और अगली पीढ़ियों की आवश्यकता नहीं होती है :) यदि आप कंप्यूटर के जीवन को जटिल बनाना चाहते हैं, तो बेंचमार्क से इस वापसी को हटा दें:

 if (sum == target_qty) { return 0; } 

यह कार्य को जटिल करेगा और कंप्यूटर को थोड़ा नुकसान पहुंचाएगा ...

सौभाग्य है

m_OO_m