Matlab में आनुवंशिक एल्गोरिदम चंचलता से

प्रस्तावना

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

आनुवंशिक एल्गोरिदम का सार

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

समस्या का बयान

वीके सोशल नेटवर्क में एक दिलचस्प खेल है जिसे "लाइट ऑन करें" कहा जाता है, यह वह था जिसने एक लेख लिखने की इच्छा जताई, क्योंकि उपयोगकर्ता जो भी काम करता है, वह आनुवंशिक एल्गोरिदम के लिए एकदम सही है। तीन शब्दों में, खेल का सार इस प्रकार है: पावर स्टेशन और घरों को केबलों से जोड़ना आवश्यक है। खेल मैदान की प्रत्येक कोशिका पर चार प्रकार के केबलों में से एक होता है: घर को जोड़ने के लिए एल-आकार, टी-आकार, आई-आकार, आई-आकार का आधा (एच द्वारा चिह्नित)। खिलाड़ी उन्हें 90 डिग्री की वृद्धि में घुमाने के लिए स्वतंत्र है। सामान्य तौर पर, पहली बार में समझने की कोशिश करना बेहतर होता है।
क्या आपने इसे आजमाया है? चलिए आगे बढ़ते हैं। खेल मैदान की स्थिति के उद्देश्य समारोह का निर्माण करना आवश्यक है। इनपुट डेटा केबल के प्रत्येक टुकड़े का रोटेशन कोण है। यह समझना आसान है कि इसे 2 बिट्स में एन्कोड किया जा सकता है। खेल की शुरुआत में कुल क्षेत्र 5x5 वर्ग है। इसलिए, बाइनरी कोड में जीन की लंबाई 5x5x2 = 50 बिट्स है। वस्तुनिष्ठ फ़ंक्शन इनपुट के रूप में शून्य और लोगों की एक सरणी लेगा (मैटलैब में ऐसी संभावना है)।
खेल के मैदान की स्थिति की गुणवत्ता का आकलन कैसे करें? मैं पड़ोसी कोशिकाओं के बीच कनेक्शन की संख्या का उपयोग करने का सुझाव देता हूं। खेल के मैदान का स्कोर कोशिकाओं की रेटिंग का योग है। पड़ोसी के साथ प्रत्येक सेल कनेक्शन एक स्कोर है। 4 कोशिकाओं में पड़ोसी: ऊपरी, निचले, बाएं, दाएं।

कार्यान्वयन सुविधाएँ

मैं स्रोतों को चिपकाना और उन्हें लाइन से अलग करना नहीं चाहूंगा, जैसा कि कुछ लोग हैंबे पर करना पसंद करते हैं। गिट रिपॉजिटरी सिर्फ इतना ही करेगी: github.com/player999/turnonthelight । README में टिप्पणियाँ मदद करनी चाहिए। अब मैं आपको सलाह देता हूं कि स्रोत को खोलें और उन्हें लेख के साथ कॉपी करें। मैंने जानबूझकर उन्हें काफी सरल बना दिया। बस कार्यान्वयन के महत्वपूर्ण बिंदुओं पर स्पर्श करें। कार्यक्रम के इनपुट पर, पाठ फ़ाइल में खेल के क्षेत्र की प्रारंभिक स्थिति लगभग इस प्रकार है:

 H1 H0 I1 I1 I3
 I1 H2 T1 T1 I3
 L3 L2 H1 L0 H1
 एच ० एल १ टी ३ आई ० टी ३
 L0 I0 L0 L0 L0

यहाँ पत्र सेल का प्रकार है, और संख्या 90 डिग्री दक्षिणावर्त के वेतन वृद्धि में 0 से 270 डिग्री तक का अभिविन्यास है। यह फ़ील्ड स्कीम_कॉन्फ़िगर फ़ंक्शन का उपयोग करके पढ़ी जाती है, जिसे मुख्य रन स्क्रिप्ट से कहा जाता है। इसके अलावा, एक आनुवंशिक एल्गोरिथ्म इसे solve_scheme फ़ंक्शन पर कॉल करके लागू किया जा सकता है। रन स्क्रिप्ट में, लक्ष्य फ़ंक्शन को मजेदार के रूप में नामित किया गया है, जो कि eval_bits फ़ंक्शन के लिए एक आवरण है। eval_bits खेल क्षेत्र का वर्णन करने वाले दो बाइनरी स्ट्रिंग्स को स्वीकार करता है। पहला सेल प्रकार है, दूसरा उनका अभिविन्यास है। स्वाभाविक रूप से, आनुवंशिक एल्गोरिथ्म के संचालन के दौरान, पहला पैरामीटर स्थिर होना चाहिए। खिलाड़ी सेल प्रकार नहीं बदल सकता है। इन पंक्तियों का निर्माण प्ले 2 क्षेत्र की कोशिकाओं के अरेंजमेंट के साथ किया जाता है। eval_bits eval_scheme के लिए एक आवरण है। यह उद्देश्य फ़ंक्शन का मूल है, और eval_bits बस तर्कों को एक मैट्रिक्स में परिवर्तित करता है जो खेल के मैदान का वर्णन करता है।
मुझे उम्मीद है कि मैं समझता हूं कि उद्देश्य फ़ंक्शन कैसे काम करता है। अब बहुत कम करने के लिए। पहले आपको आनुवंशिक एल्गोरिथ्म के विकल्पों के साथ एक संरचना प्राप्त करने की आवश्यकता है। हर स्वाद के लिए कई हैं। लेकिन केवल सबसे महत्वपूर्ण संकेत दिया।
options = gaoptimset('PopulationType','bitstring','PopulationSize',1000,'Generations',100);

जनसंख्याप्रकार - तर्कों की प्रस्तुति। हमारे मामले में, थोड़ा स्ट्रिंग। और यद्यपि "स्ट्रिंग" शब्द यहां दिखाई देता है, वास्तव में यह शून्य और लोगों का एक दोहरा सरणी है।
पॉपुलेशनाइज़ - प्रत्येक पुनरावृत्ति में कितने जीन होंगे। अधिक जीन, बेहतर एल्गोरिथ्म काम करेगा, लेकिन एक ही समय में यह धीमा होगा। प्रत्येक हिरन जीन के लिए, आपको उद्देश्य फ़ंक्शन की गणना करने की आवश्यकता है।
पीढ़ी - आनुवंशिक एल्गोरिथ्म के पुनरावृत्तियों की संख्या। यह संभावित निकास स्थितियों में से एक है। एक और, उदाहरण के लिए, उद्देश्य समारोह में परिवर्तन बंद हो जाता है।
निम्नलिखित अनुकूलन कार्य के लिए एक कॉल है:
opt = ga(fun,length(pos),[],[],[],[],[],[],[],options);

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

निष्कर्ष

यद्यपि एल्गोरिथ्म को भी अनुकूलन की आवश्यकता होती है, यह आत्मविश्वास से साबित हुआ कि यह पहेली के समाधान की खोज कर सकता है। मुझे उम्मीद है कि लेख ने आपको थोड़ी मदद की, या कम से कम आपका मनोरंजन किया। उदाहरण के लिए, यहां काम का परिणाम है।