जेनेटिक एल्गोरिदम समझाया गया

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

मैदान के निचले हिस्से से एक दीवार के चारों ओर होकर हरे लक्ष्य की ओर उड़ते रॉकेट, जिनमें सबसे अच्छी उड़ान टूटी रेखा से दिखाई गई है
मैदान के निचले हिस्से से एक दीवार के चारों ओर होकर हरे लक्ष्य की ओर उड़ते रॉकेट, जिनमें सबसे अच्छी उड़ान टूटी रेखा से दिखाई गई है

विचार

1960 और 1970 के दशकों में मिशिगन विश्वविद्यालय के जॉन हॉलैंड ने डार्विन के सिद्धांत को एक एल्गोरिदम में बदला, जिसका वर्णन उन्होंने 1975 की अपनी पुस्तक Adaptation in Natural and Artificial Systems में किया। लगभग उसी समय जर्मनी में इंगो रेचेनबर्ग और हांस-पॉल श्वेफ़ेल ने इंजीनियरिंग डिज़ाइन के लिए विकास रणनीतियाँ (evolution strategies) विकसित कीं। साझा नुस्ख़ा यह है: संभावित हलों की एक जनसंख्या रखें, उन्हें स्कोर दें, बेहतर हलों को बदलाव के साथ प्रजनन करने दें, और यह कई पीढ़ियों तक दोहराएँ।

जॉन हॉलैंड, जिन्होंने 1975 की अपनी पुस्तक Adaptation in Natural and Artificial Systems में जेनेटिक एल्गोरिदम का वर्णन किया।
जॉन हॉलैंड, जिन्होंने 1975 की अपनी पुस्तक Adaptation in Natural and Artificial Systems में जेनेटिक एल्गोरिदम का वर्णन किया।

जीन और जनसंख्या

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

फ़िटनेस फ़ंक्शन

फ़िटनेस वह एक संख्या है जो बताती है कि कोई उम्मीदवार कितना अच्छा है, और एल्गोरिदम समस्या के बारे में केवल यही जानता है। रॉकेटों के लिए यह सबसे अधिक जल्दी पहुँचने को, फिर लक्ष्य के पास रुकने को पुरस्कृत करती है, और टकराने पर दंड देती है। अच्छी तरह चुना गया फ़िटनेस फ़ंक्शन खोज को सहजता से अच्छे उत्तरों की ओर ले जाता है; लापरवाही से बनाया गया फ़ंक्शन ग़लत चीज़ को पुरस्कृत करता है, और एल्गोरिदम उसकी छोड़ी हर खामी का फ़ायदा उठाएगा।

चयन

माता-पिता इस तरह चुने जाते हैं कि अधिक फ़िट उम्मीदवारों की अधिक संतानें हों, लेकिन कमज़ोर उम्मीदवारों को भी मौक़ा मिले, क्योंकि उनके जीनों में उपयोगी टुकड़े हो सकते हैं। रूलेट व्हील चयन हर उम्मीदवार को उसकी फ़िटनेस के अनुपात में पहिये का एक हिस्सा देता है; टूर्नामेंट चयन कुछ उम्मीदवारों को यादृच्छिक रूप से चुनकर उनमें से सबसे अच्छे को लेता है। अधिक कड़ा चयन प्रगति को तेज़ करता है, लेकिन जनसंख्या को अधिक एक-जैसा भी बना देता है, जिससे खोज बहुत जल्दी समाप्त हो सकती है।

क्रॉसओवर और उत्परिवर्तन

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

एलीटिज़्म, अन्वेषण और दोहन

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

स्थानीय इष्टतम

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

ख़ुद आज़माएँ

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

अक्सर पूछे जाने वाले प्रश्न

क्या जेनेटिक एल्गोरिदम एक तरह की कृत्रिम बुद्धिमत्ता है?

खोज और ऑप्टिमाइज़ेशन की एक विधि के रूप में यह AI और मशीन लर्निंग के व्यापक क्षेत्र से संबंधित है। यह न्यूरल नेटवर्क की तरह उदाहरणों से नहीं सीखता; यह आज़माइश और चयन के ज़रिए संभावित हलों को बेहतर बनाता है। दोनों को अक्सर मिलाया जाता है, उदाहरण के लिए न्यूरल नेटवर्क की संरचना या वेट को विकसित करके, जिस तरीक़े को न्यूरोइवोल्यूशन कहते हैं।

क्या जेनेटिक एल्गोरिदम हमेशा सबसे अच्छा उत्तर ढूँढता है?

नहीं। यह एक ह्यूरिस्टिक है: यह आमतौर पर कठिन समस्याओं के अच्छे उत्तर ढूँढ लेता है, लेकिन सबसे अच्छे उत्तर की कोई गारंटी नहीं देता और न ही यह प्रमाण देता है कि उसका उत्तर सबसे अच्छे के कितना क़रीब है। जिन समस्याओं के लिए कोई सटीक विधि पर्याप्त तेज़ हो, उनके लिए वह विधि बेहतर है।

जेनेटिक एल्गोरिदम और विकास रणनीतियों में क्या अंतर है?

दोनों विकासवादी एल्गोरिदम हैं। क्लासिक जेनेटिक एल्गोरिदम स्ट्रिंग जैसे गुणसूत्रों पर क्रॉसओवर पर ज़ोर देते हैं; विकास रणनीतियाँ मुख्य रूप से वास्तविक संख्याओं पर उत्परिवर्तन के साथ काम करती हैं और अक्सर चलते-चलते अपने उत्परिवर्तन के आकार को ख़ुद ढालती हैं। आधुनिक विधियाँ दोनों के विचारों को मिलाती हैं।

शुरुआत में रॉकेट इतने अनाड़ी क्यों होते हैं?

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

आज़माने के लिए तैयार?

अपने ब्राउज़र में PictorX खोलें — शुरू करने के लिए इंस्टॉल या क्रेडिट कार्ड की ज़रूरत नहीं।

जेनेटिक एल्गोरिदम प्लेग्राउंड खोलें