🌊 🔻 💇🏻 आनुवंशिक एल्गोरिथ्म। बस जटिल के बारे में 🗞️ 👩🏻‍🤝‍👨🏼 👨‍🔬

हाल ही में, अधिक-से-अधिक "बात" नए-कल्पित एल्गोरिदम के बारे में, जैसे कि तंत्रिका नेटवर्क और आनुवंशिक एल्गोरिथ्म। आज मैं आनुवंशिक एल्गोरिदम के बारे में बात करूंगा, लेकिन इस बार चलो गर्भपात परिभाषाओं और जटिल शब्दों के बिना करने की कोशिश करते हैं।
जैसा कि महान वैज्ञानिकों में से एक ने कहा: "यदि आप अपनी पत्नी को अपने सिद्धांत नहीं समझा सकते हैं, तो आपका सिद्धांत कुछ भी नहीं है!" तो चलिए चीजों को क्रमबद्ध करने की कोशिश करते हैं।

इतिहास की एक चुटकी

जैसा कि विकिपीडिया कहता है: "आनुवंशिक एल्गोरिदम के संस्थापक पिता जॉन हॉलैंड हैं, जो 1975 में अपने स्वयं के प्रयोजनों के लिए आनुवंशिकी का उपयोग करने के विचार के साथ आए थे।" संदर्भ के लिए, Altair 8800 एक ही वर्ष में दिखाई दिया, और नहीं, यह एक आतंकवादी नहीं है, लेकिन पहला व्यक्तिगत कंप्यूटर है। तब तक, जॉन पहले से ही 46 साल का था।

इसका उपयोग कहां किया जाता है

चूंकि एल्गोरिथ्म स्व-शिक्षा है, इसलिए अनुप्रयोगों की सीमा अत्यंत विस्तृत है:

ग्राफ कार्य
लेआउट कार्य
शेड्यूलिंग
"आर्टिफिशियल इंटेलिजेंस" का निर्माण

संचालन का सिद्धांत

आनुवंशिक एल्गोरिथम मुख्य रूप से एक विकासवादी एल्गोरिथ्म है, दूसरे शब्दों में, एल्गोरिथ्म की मुख्य विशेषता क्रॉसिंग (संयोजन) है। जैसा कि आप आसानी से अनुमान लगा सकते हैं, एल्गोरिथ्म का विचार स्वाभाविक रूप से प्रकृति से लिया गया है, क्योंकि इसने इस पर मुकदमा नहीं किया। इसलिए, सबसे महत्वपूर्ण बात यह है कि सही "संयोजन" का चयन करके, प्राप्त किया जाता है।
एल्गोरिथ्म को तीन चरणों में विभाजित किया गया है:

चौराहा
चयन (चयन)
नई पीढ़ी का गठन

यदि परिणाम हमें सूट नहीं करता है, तो ये चरण तब तक दोहराए जाते हैं जब तक कि परिणाम हमें संतुष्ट करना शुरू न कर दे या निम्न में से कोई एक स्थिति उत्पन्न न हो:

पीढ़ियों की संख्या (चक्र) पूर्व-चयनित अधिकतम तक पहुंचती है
उत्परिवर्तन समय है

चरणों पर अधिक जानकारी।

नई आबादी का निर्माण । इस कदम पर, एक प्रारंभिक जनसंख्या बनाई जाती है, जो संभवतः, कोषेर नहीं होगी, लेकिन यह संभावना है कि एल्गोरिथ्म इस समस्या को ठीक करेगा। मुख्य बात यह है कि वे "प्रारूप" के अनुरूप हैं और "प्रजनन के लिए अनुकूलित" हैं।
प्रजनन । खैर, सब कुछ मनुष्यों की तरह है, एक वंशज को पाने के लिए दो माता-पिता लगते हैं। मुख्य बात यह है कि वंशज (बच्चा) माता-पिता से अपनी विशेषताओं को प्राप्त कर सकता है। इस मामले में, सभी, न केवल बचे, गुणा (यह वाक्यांश विशेष रूप से बेतुका है, लेकिन चूंकि हमारे पास एक गोलाकार वैक्यूम में सब कुछ है, सब कुछ किया जा सकता है), अन्यथा एक अल्फा पुरुष बाहर खड़ा होगा, जिसके जीन अन्य सभी को ओवरलैप करेंगे, लेकिन यह हमारे लिए मौलिक रूप से अस्वीकार्य है। ।
म्यूटेशन । उत्परिवर्तन प्रजनन के समान हैं, एक निश्चित संख्या में व्यक्तियों को म्यूटेंट से चुना जाता है और पूर्वनिर्धारित संचालन के अनुसार संशोधित किया जाता है।
चयन । यहां सबसे प्यारी शुरुआत होती है, हम उन लोगों के अनुपात से चुनना शुरू करते हैं जो "आगे बढ़ते हैं।" उसी समय, हम एक पैरामीटर के रूप में इंगित करते हुए, हाथ से हमारे चयन के बाद "बचे" के अनुपात का निर्धारण करते हैं। दुख की बात है कि बाकी व्यक्तियों को मरना चाहिए।

अभ्यास

आपने चमत्कारिक एल्गोरिथम के बारे में "परी कथा" को सफलतापूर्वक सुना है, और यह बहुत संभव है कि आप इसका इंतजार कर रहे हैं जब हम इसे अंत में संचालित करना शुरू करते हैं, तो मैं आपको खुश करना चाहता हूं, समय आ गया है।
आइए मेरे पसंदीदा Diophantine समीकरणों (पूर्णांक जड़ों वाले समीकरण) का एक उदाहरण देखें।
हमारा समीकरण: a + 2b + 3c + 4d = 30
आपको शायद पहले से ही संदेह है कि इस समीकरण की जड़ें अंतराल पर हैं [1; 30], इसलिए हम 5 लेते हैं
यादृच्छिक मान a, b, c, d (30 की सीमा विशेष रूप से कार्य को आसान बनाने के लिए ली गई है)
और इसलिए, हमारे पास पहली पीढ़ी है:

(1,28,15,3)
(14,9,2,4)
(13,5,7,3)
(23,8,16,19)
(9,13,5,2)

उत्तरजीविता दरों की गणना करने के लिए, हम प्रत्येक समाधान को अभिव्यक्ति में प्रतिस्थापित करते हैं। प्राप्त मूल्य से 30 तक की दूरी वांछित मूल्य होगी।

| 114-30 | = 84 |
| 54-30 | = 24 |
| 56-30 | = 26 |
| 163-30 | = 133 |
| 58-30 | = 28 |

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

(1/84) /0.135266 = 8.80%
(1/24) /0.135266 = 30.8%
(1/26) / 0.135266 = 28.4%
(1/133) / 0.135266 = 5.56%
(१/२0) / ०.१.३५२६६ = २६.४%

इसके बाद, हम उन पाँच जोड़ियों को चुनेंगे जिनके पास एक बच्चा होगा। मौका देने के लिए स्वतंत्र लगाम देने के लिए हम हर बार ठीक पाँच बार देंगे, हर बार माता-पिता बनने का मौका एक ही होगा और जीवित रहने की संभावना के बराबर होगा।
3-1, 5-2, 3-5, 2-5, 5-3
जैसा कि पहले उल्लेख किया गया है, वंशज में पिता और मां के जीन के बारे में जानकारी होती है। यह विभिन्न तरीकों से प्राप्त किया जा सकता है, लेकिन इस मामले में "क्रॉसओवर" का उपयोग किया जाएगा। (- = विभाजन रेखा)

एच। पिता: a1 | b1, c1, d1 H. माँ: a2 | बी 2, सी 2, डी 2 एक्स। वंशज: ए 1, बी 2, सी 2, डी 2 या ए 2, बी 1, सी 1, डी 1
एच। पिता: ए 1, बी 1 | c1, d1 H. माँ: a2, b2 | सी 2, डी 2 एक्स। वंशज: ए 1, बी 1, सी 2, डी 2 या ए 2, बी 2, सी 1, डी 1
एच। पिता: ए 1, बी 1, सी 1 | डी 1 एच। माँ: ए 2, बी 2, सी 2 | डी 2 एक्स। वंशज: ए 1, बी 1, सी 1, डी 2 या ए 2, बी 2, सी 2, डी 1

एक वंशज को जानकारी पारित करने के लिए बहुत सारे तरीके हैं, और क्रॉस-ओवर कई में से एक है। विभाजक का स्थान पूरी तरह से मनमाना हो सकता है, साथ ही पिता या माता रेखा के बाईं ओर होंगे।
अब हम वंशजों के साथ भी ऐसा ही करते हैं:

एच। पिता: (13 | 5,7,3) एच। माँ: (1 | 28,15,3) एच। वंशज: (13,28,15,3)
एच। पिता: (9.13 | 5.2) एच। माँ: (14.9 | 2.4) एच। वंशज: (9.13.2.4)
एच। -पिता: (13,5,7 | 3) एच। -माँ: (9,13,5 | 2) एच। -वंशज: (13,5,7,2)
एच। पिता: (14 | 9.2.4) एच। माँ: (9 | 13.5.2) एक्स। वंशज: (14.13.5.2.2)
एच।-पिता: (१३.५ |,, ३) एच। -माँ: (९ .३३ | ५, २) एच। -वंशज: (१३,५,५,२)

अब हम वंशजों की उत्तरजीविता दर की गणना करते हैं।

(13,28,15,3) - | 126-30 | = 96 (9,13,2,4) - | 57-30 = = 27 |
(13,5,7,2) - | 57-30 | = 22
(14,13,5,2) - | 63-30 | = 33 |
(13,5,5,2) - | 46-30 | = 16

संतानों की औसत फिटनेस 38.8 होने के बाद से यह दुखी है, जबकि माता-पिता के लिए यह गुणांक 59.4 था। यह इस समय है कि एक उत्परिवर्तन का उपयोग करना अधिक समीचीन है, इसके लिए, हम एक या अधिक मानों को यादृच्छिक संख्या से 1 से 30 तक बदलते हैं।
एल्गोरिथ्म तब तक काम करेगा जब तक जीवित रहने की दर शून्य के बराबर न हो। यानी समीकरण का हल है।
बड़ी आबादी वाले सिस्टम (उदाहरण के लिए, 5 के बजाय 50 वांछित स्तर (0) में अधिक तेज़ी और दृढ़ता से परिवर्तित होते हैं।

कोड

यह वह जगह है जहाँ सादगी समाप्त होती है और अद्भुत सी ++ शुरू होता है ...
C ++ वर्ग को आरंभीकरण के दौरान 5 मानों की आवश्यकता होती है: 4 गुणांक और एक परिणाम। उपरोक्त उदाहरण के लिए, यह इस तरह दिखेगा: सीडीओओफेंटाइन डीपी (1,2,3,4,30);

फिर, समीकरण को हल करने के लिए, हल () फ़ंक्शन को कॉल करें, जो समाधान वाले एलील को वापस कर देगा। GetGene () को सही मानों के साथ जीन प्राप्त करने के लिए कॉल करें a, b, c, d। इस वर्ग का उपयोग करने वाली मानक main.cpp प्रक्रिया हो सकती है:

#include "<iostream.h>" #include "diophantine.h" void main() { CDiophantine dp(1,2,3,4,30); int ans; ans = dp.Solve(); if (ans == -1) { cout << "No solution found." << endl; } else { gene gn = dp.GetGene(ans); cout << "The solution set to a+2b+3c+4d=30 is:\n"; cout << "a = " << gn.alleles[0] << "." << endl; cout << "b = " << gn.alleles[1] << "." << endl; cout << "c = " << gn.alleles[2] << "." << endl; cout << "d = " << gn.alleles[3] << "." << endl; } }

CDiophantine वर्ग ही:

 #include <stdlib.h> #include <time.h> #define MAXPOP 25 struct gene { int alleles[4]; int fitness; float likelihood; // Test for equality. operator==(gene gn) { for (int i=0;i<4;i++) { if (gn.alleles[i] != alleles[i]) return false; } return true; } }; class CDiophantine { public: CDiophantine(int, int, int, int, int);// Constructor with coefficients for a,b,c,d. int Solve();// Solve the equation. // Returns a given gene. gene GetGene(int i) { return population[i];} protected: int ca,cb,cc,cd;// The coefficients. int result; gene population[MAXPOP];// Population. int Fitness(gene &);// Fitness function. void GenerateLikelihoods(); // Generate likelihoods. float MultInv();// Creates the multiplicative inverse. int CreateFitnesses(); void CreateNewPopulation(); int GetIndex(float val); gene Breed(int p1, int p2); }; CDiophantine::CDiophantine(int a, int b, int c, int d, int res) : ca(a), cb(b), cc(c), cd(d), result(res) {} int CDiophantine::Solve() { int fitness = -1; // Generate initial population. srand((unsigned)time(NULL)); for(int i=0;i<MAXPOP;i++) {// Fill the population with numbers between for (int j=0;j<4;j++) {// 0 and the result. population[i].alleles[j] = rand() % (result + 1); } } if (fitness = CreateFitnesses()) { return fitness; } int iterations = 0;// Keep record of the iterations. while (fitness != 0 || iterations < 50) {// Repeat until solution found, or over 50 iterations. GenerateLikelihoods();// Create the likelihoods. CreateNewPopulation(); if (fitness = CreateFitnesses()) { return fitness; } iterations++; } return -1; } int CDiophantine::Fitness(gene &gn) { int total = ca * gn.alleles[0] + cb * gn.alleles[1] + cc * gn.alleles[2] + cd * gn.alleles[3]; return gn.fitness = abs(total - result); } int CDiophantine::CreateFitnesses() { float avgfit = 0; int fitness = 0; for(int i=0;i<MAXPOP;i++) { fitness = Fitness(population[i]); avgfit += fitness; if (fitness == 0) { return i; } } return 0; } float CDiophantine::MultInv() { float sum = 0; for(int i=0;i<MAXPOP;i++) { sum += 1/((float)population[i].fitness); } return sum; } void CDiophantine::GenerateLikelihoods() { float multinv = MultInv(); float last = 0; for(int i=0;i<MAXPOP;i++) { population[i].likelihood = last = last + ((1/((float)population[i].fitness) / multinv) * 100); } } int CDiophantine::GetIndex(float val) { float last = 0; for(int i=0;i<MAXPOP;i++) { if (last <= val && val <= population[i].likelihood) return i; else last = population[i].likelihood; } return 4; } gene CDiophantine::Breed(int p1, int p2) { int crossover = rand() % 3+1;// Create the crossover point (not first). int first = rand() % 100;// Which parent comes first? gene child = population[p1];// Child is all first parent initially. int initial = 0, final = 3;// The crossover boundaries. if (first < 50) initial = crossover; // If first parent first. start from crossover. else final = crossover+1;// Else end at crossover. for(int i=initial;i<final;i++) {// Crossover! child.alleles[i] = population[p2].alleles[i]; if (rand() % 101 < 5) child.alleles[i] = rand() % (result + 1); } return child;// Return the kid... } void CDiophantine::CreateNewPopulation() { gene temppop[MAXPOP]; for(int i=0;i<MAXPOP;i++) { int parent1 = 0, parent2 = 0, iterations = 0; while(parent1 == parent2 || population[parent1] == population[parent2]) { parent1 = GetIndex((float)(rand() % 101)); parent2 = GetIndex((float)(rand() % 101)); if (++iterations > 25) break; } temppop[i] = Breed(parent1, parent2);// Create a child. } for(i=0;i<MAXPOP;i++) population[i] = temppop[i]; }

लेख विकिपीडिया और साइट algolist.manual.ru पर आधारित है।

आनुवंशिक एल्गोरिथ्म। बस जटिल के बारे में

इतिहास की एक चुटकी

इसका उपयोग कहां किया जाता है

संचालन का सिद्धांत

चरणों पर अधिक जानकारी।

अभ्यास

कोड

More articles: