आनुवंशिक एल्गोरिदम का उपयोग करके अमूर्त चित्र उत्पन्न करें

हाय, हेब्र!

इस गर्मियों में मैंने मॉस्को स्टेट यूनिवर्सिटी के साइंटिफिक एंड एजुकेशनल स्कूल में भाग लिया, जो मॉस्को स्टेट यूनिवर्सिटी और मॉस्को स्टेट यूनिवर्सिटी के एसएससी की वैज्ञानिक रचनात्मकता की प्रयोगशाला है । इस लेख में, मैं आपको एक ऐसे प्रोजेक्ट के बारे में बताना चाहूंगा जिसे मैंने स्कूल के दौरान MAD_GooZe के नेतृत्व में एक विशेष प्रोग्रामिंग कोर्स में विकसित किया था।

अधीर के लिए

परियोजना का विचार

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

कार्य सिद्धांत

इसलिए, जैसा कि आप शायद जानते हैं, आनुवंशिक एल्गोरिदम विकासवाद के सिद्धांतों पर आधारित हैं। वे आपको उन समस्याओं को हल करने की अनुमति देते हैं जिनके "आदर्श" समाधान परिभाषित नहीं है, या इसकी प्रत्यक्ष प्राप्ति की विधि ज्ञात नहीं है। आमतौर पर, ऐसे एल्गोरिदम के कार्यान्वयन में निम्नलिखित चरण शामिल होते हैं:

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

हम अपनी परियोजना में इन चरणों के कार्यान्वयन के बारे में बताएंगे।

छवि प्रस्तुत करने के बारे में

हम आरजीबी रंग अंतरिक्ष में चित्रों का प्रतिनिधित्व करेंगे, जिसमें प्रत्येक पिक्सेल के रंग को 3 घटकों का उपयोग करके दर्शाया गया है - लाल, हरा और नीला, जिनमें से प्रत्येक अंतराल से संबंधित है [0; 255]। हम छवि को तीन फ़ंक्शन आर (एक्स, वाई), जी (एक्स, वाई), बी (एक्स, वाई) के एक समूह के रूप में परिभाषित करेंगे - प्रत्येक रंग घटक के लिए एक फ़ंक्शन। इन कार्यों की एक तस्वीर कैसे खींचें?

1. हम छवि के सभी पिक्सेल के चारों ओर जाएंगे और उनके लिए इन कार्यों के मूल्यों का पता लगाएंगे, x और y अक्षों के साथ पिक्सेल के निर्देशांक को तर्क के रूप में पारित करेंगे;
2. अलग-अलग, प्रत्येक फ़ंक्शन के लिए हम प्राप्त मानों को सामान्य करते हैं, अर्थात, हम उन्हें सूत्र के अनुसार 0 से 255 तक अंतराल पर लाते हैं, और गोल।

हम पेड़ों के रूप में सूत्र प्रस्तुत करेंगे। उदाहरण के लिए, इस तरह:

रैंडम इमेज जेनरेशन

चूंकि हम पेड़ों के रूप में कार्यों का प्रतिनिधित्व करते हैं, इसलिए हम आसानी से प्रारंभिक पीढ़ी उत्पन्न कर सकते हैं। हम प्रत्येक फ़ंक्शन को उसके घटक भागों (अन्य कार्यों, स्थिरांक और तर्क) से इकट्ठा करते हैं। निम्नलिखित आदिम कार्यों का उपयोग किया जाता है:

एकल	बाइनरी
| ए |	ए + बी
cos (a)	ए - बी
पाप (क)	ए * बी
ln (a)	ए / बी
arccos (a)	एक मॉड बी
आर्क्सिन (ए)

इसी समय, कुछ विशेषताएं हैं:

• हम बहुत अधिक जटिल कार्य उत्पन्न नहीं कर सकते हैं, क्योंकि इससे प्रदर्शन समस्या उत्पन्न होगी। इसलिए, फ़ंक्शन ट्री की अधिकतम गहराई जैसे एक पैरामीटर पेश किया जाता है। इस पैरामीटर का प्रायोगिक रूप से चयनित इष्टतम मान संख्या 6 है, क्योंकि फ़ंक्शंस जो बहुत गहरी हैं (और इसलिए जटिल हैं), उल्लेखित समस्या के अलावा, छवियों को बनाते समय भी तरंग उत्पन्न करते हैं, जिससे उनकी गुणवत्ता कम हो जाती है, और ऐसे कार्य जो बहुत ही सरल आदिम छवियां उत्पन्न करते हैं।
• दूसरे, पहली पीढ़ी की विविधता को प्राप्त करने के लिए, उत्पन्न कार्यों को उनकी संरचना में एक दूसरे के समान नहीं होना चाहिए, अर्थात्, कांटे की संख्या और स्थान, साथ ही साथ शाखाओं की लंबाई भी। इसलिए, चित्र बनाने की निम्न विधि का आविष्कार किया गया था। संभावना के साथ , जहां n वर्तमान नोड की गहराई है और N पेड़ की अधिकतम गहराई है, एक बच्चे के बिना एक तत्व इस नोड में रखा गया है (यानी, एक निरंतर या समन्वय, उन कार्यों के विपरीत जो वंशजों के पास होना चाहिए, क्योंकि वे उनके तर्क हैं)। इस सूत्र को निम्नलिखित आवश्यकताओं के आधार पर प्रयोगात्मक रूप से चुना गया था:
  
  1. फ़ंक्शन बढ़ते एन के साथ इसके मूल्य को बढ़ाता है;
  2. एन = एन के लिए , अर्थात्, फ़ंक्शन की गहराई अधिकतम से अधिक नहीं हो सकती;
  3. व्यक्तिपरक मानदंड यह है कि उत्पन्न छवियां बहुत सरल नहीं हैं और बहुत जटिल नहीं हैं
  
  
  
• कोई भी निरंतर कार्य करने के लिए परेशान नहीं करता है (जो उनके तर्कों पर निर्भर नहीं करता है)। इस स्थिति में, सभी पिक्सेल के लिए घटक मान 0 पर सेट है।

एक बेतरतीब ढंग से उत्पन्न पीढ़ी का एक उदाहरण:


यह उम्मीद है कि लगभग सभी यादृच्छिक छवियां उबाऊ लगती हैं। इस दुखद तथ्य को ठीक करने के लिए, हमें, वास्तव में, आनुवंशिक एल्गोरिदम की आवश्यकता है।
वैसे, प्रत्येक चैनल की एक अलग छवि भी दिलचस्प नहीं दिखती है, लेकिन उनमें से तीन सुंदर रंग प्रभाव बनाते हैं।

पीढ़ी की छवि रेटिंग

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

चौराहा

स्कोर करने के बाद, नई पीढ़ी पाने के लिए व्यक्तियों को पार करना आवश्यक है। एक बच्चे की छवि प्राप्त करने के लिए, 2 माता-पिता की आवश्यकता होती है। प्रत्येक व्यक्ति के माता-पिता बनने की संभावना उसके मूल्यांकन के सीधे आनुपातिक है।
यहाँ उपयोग की जाने वाली क्रॉस-ब्रीडिंग एल्गोरिथ्म एक दिए गए कार्य के लिए अनुकूलित मल्टीपॉइंट क्रॉस-ब्रीडिंग का एक प्रकार है, अर्थात, संतान जीन एक विशिष्ट क्रम में लिए गए पैतृक जीन के कुछ हिस्सों का एक सेट है, इसके अलावा।

• क्रॉसिंग के परिणामस्वरूप, एक गलत फ़ंक्शन प्राप्त नहीं किया जा सकता है
• उच्च श्रेणीबद्ध छवि वंश में अधिक योगदान देती है

क्रॉस्ब्रेडिंग उदाहरण:

परिवर्तन

एक वंश प्राप्त करने के बाद, इसे म्यूट करना आवश्यक है ताकि पीढ़ियों की विविधता खो न जाए। उत्परिवर्तन सभी वंशों पर लागू होता है और निम्नलिखित में शामिल होता है - सभी 3 छवि कार्यों को बाईपास किया जाता है और उनमें से प्रत्येक में स्थिरांक / निर्देशांक के साथ एक निश्चित संभावना परिवर्तन के साथ निर्देशांक / निर्देशांक होते हैं।
उत्परिवर्तन उदाहरण:

नई पीढ़ी का गठन

30% सर्वश्रेष्ठ छवियां पुरानी से नई पीढ़ी को स्थानांतरित की जाती हैं, ताकि गलती से उनके जीन न खोएं। और पीढ़ी में शेष छवियां क्रॉसब्रीडिंग का परिणाम हैं। यह आपको व्यक्तियों की विविधता और "गुणवत्ता" जीन की निरंतरता के बीच संतुलन बनाए रखने की अनुमति देता है।

तकनीकी कार्यान्वयन

इस परियोजना का कार्यान्वयन जावास्क्रिप्ट में लिखा गया है। छवियां कैनवास पर खींची जाती हैं, उनकी गणना वेब श्रमिकों में होती है, जिससे काम में तेजी आती है।

• डेमो
• GitHub

परिणाम

इस परियोजना के साथ, मैंने स्कूली बच्चों, भविष्य के वैज्ञानिकों के वैज्ञानिक कार्यों के एक सम्मेलन में भाग लिया और वहां 4 वां स्थान हासिल किया, जो कि 8 वीं कक्षा के छात्र के लिए बुरा नहीं है :)।

संबंधित लिंक

• ग्रेडर्स का उपयोग करके चित्र बनाना
• दृश्य इंटरफ़ेस जनरेटर
• चित्रों का सृजन दूर से लोगों के चेहरे के समान है

यह लेख मॉस्को स्टेट यूनिवर्सिटी के वैज्ञानिक और शैक्षिक स्कूल के हिस्से के रूप में मेरे पर्यवेक्षक MAD_GooZe के साथ मिलकर तैयार किया गया था।