आनुवंशिक कलनविधियाँ

आनुवंशिक कलनविधियाँ जैविक विकास से प्रेरित एक खोज/अनुकूलन तकनीक हैं, इकाई 10 में अपने ही उप-प्रकरण के रूप में नामित, GATE CS में कोई समतुल्य नहीं। यह अध्याय संकारकों व समग्र चक्र को सही ढंग से आधारित करता है — अनुकृत चयन, संकरण व उत्परिवर्तन से 'योग्यतर की उत्तरजीविता' — सतही जीवविज्ञान-रूपक के बजाय।

एन्कोडिंग रणनीतियाँ व फ़िटनेस फलन

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

आनुवंशिक संकारक: चयन, संकरण व उत्परिवर्तन

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

GA चक्र

  1. क्रोमोसोमों की समष्टि आरंभीकृत करें, सामान्यतः यादृच्छिक रूप से।
  2. समस्या-विशिष्ट फ़िटनेस फलन से हर क्रोमोसोम की फ़िटनेस मूल्यांकित करें।
  3. उच्चतर फ़िटनेस की ओर पक्षपाती जनक चुनें।
  4. संतति उत्पन्न करने हेतु चुने जनक-युग्मों पर संकरण लागू करें।
  5. निम्न प्रायिकता पर संतति पर उत्परिवर्तन लागू करें।
  6. पुरानी समष्टि को (पूर्णतः या आंशिक रूप से) नई संतति से बदलें, अगली पीढ़ी बनाते हुए, व चरण 2 से दोहराएँ जब तक कोई रोकने की कसौटी (फ़िटनेस-सीमा, या पीढ़ियों की स्थिर संख्या) न पहुँचे।
⚠️ GA अच्छा हल खोजता है; यह **सर्वश्रेष्ठ** हल की गारंटी नहीं देता
आनुवंशिक कलनविधि एक अनुमानी/मेटा-अनुमानी खोज है, ठीक कलनविधि नहीं — यह वैश्विक इष्टतम खोजने की गारंटी नहीं देती, व (किसी भी स्थानीय-सुधार-आधारित खोज की भाँति) केवल स्थानीय रूप से-अच्छे हल की ओर प्रगति करते अटक सकती है, यद्यपि उत्परिवर्तन व विविध समष्टि भोले पहाड़ी-आरोहण की तुलना में यह जोखिम घटाते हैं। यह ठीक वही 'सन्निकटन, सटीकता नहीं' चरित्र है जो इस पाठ्यक्रम की अपनी सन्निकटन कलनविधि व यादृच्छिकीकृत कलनविधि सामग्री में देखा गया — GA को कठिन खोज/अनुकूलन समस्याओं हेतु सामान्य-प्रयोजन अनुमानी के रूप में सर्वोत्तम समझा जाता है जहाँ ठीक कलनविधि अव्यावहारिक हो, उस विधि के रूप में नहीं जो शाखा-व-परिबंध की भाँति इष्टतमता सिद्ध करती है।

GA का प्रयोग कर समस्या-समाधान

GA उन समस्याओं हेतु उपयुक्त हैं जिनकी खोज-समष्टि विशाल, अव्यवस्थित हो व कोई दक्ष ठीक कलनविधि ज्ञात न हो — अनेक स्थानीय इष्टतमों सहित फलन-अनुकूलन, अनेक परस्पर-क्रिया करते प्रतिबंधों सहित अनुसूचन व समय-सारणीकरण, तथा हल की (केवल उसके प्राचल-मानों की नहीं) संरचना को विकसित करना मानक अनुप्रयोग-कुल हैं। एक हल किया रेखाचित्र: [0, 31] में पूर्णांक x पर f(x) = x² अधिकतम करने हेतु, x को 5-बिट द्विआधारी क्रोमोसोम में एन्कोड करें (32 संभव मान ठीक 5 बिट भरते हैं), फ़िटनेस को स्वयं f(x) होने दें (कोई रूपांतरण आवश्यक नहीं, क्योंकि बड़ा x पहले से बेहतर है), उच्चतर x² की ओर पक्षपाती जनक चुनें, एकल-बिंदु संकरण व निम्न-प्रायिकता बिट-पलट उत्परिवर्तन लागू करें, व पुनरावृत्त करें — 11111 (x = 31, वास्तविक इष्टतम) रखती समष्टि एक बार खोजे जाने पर शीघ्र चयन पर हावी हो जाएगी, क्योंकि इसकी फ़िटनेस (961) शेष से कहीं ऊपर है, जो ठीक वही चयन-दबाव है जो इष्टतम की ओर अभिसरण चलाता है।

मुख्य बिंदु

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

अभ्यास प्रश्न (8)

उत्तर खोलने से पहले प्रत्येक प्रश्न हल करें। हर व्याख्या सही विकल्प के साथ लुभावना गलत विकल्प भी बताती है, क्योंकि अंक वहीं जाते हैं।

  1. आनुवंशिक कलनविधि में, फ़िटनेस फलन है:

    1. एकमात्र समस्या-विशिष्ट भाग, वही सामान्य GA यंत्रावली भिन्न समस्याओं में पुनर्प्रयुक्त होने देते हुए
    2. हर समस्या में सदा समान
    3. क्रोमोसोम का हल कितना अच्छा है इससे असंबद्ध
    4. केवल एक बार, बिल्कुल आरंभ में प्रयुक्त
    उत्तर देखें

    उत्तर: A — एकमात्र समस्या-विशिष्ट भाग, वही सामान्य GA यंत्रावली भिन्न समस्याओं में पुनर्प्रयुक्त होने देते हुए

    फ़िटनेस फलन हर पीढ़ी मूल्यांकित होता है व वही एकमात्र घटक है जो विशिष्ट हल की जा रही समस्या हेतु अनुकूलित है; GA का शेष (चयन, संकरण, उत्परिवर्तन यंत्रावली) सामान्य रहता है।

  2. उत्परिवर्तन की तुलना में, संकरण को मुख्यतः इस संकारक के रूप में सर्वोत्तम वर्णित किया जाता है जो देता है:

    1. शोषण — समष्टि में पहले से विद्यमान आनुवंशिक सामग्री का पुनर्संयोजन
    2. अन्वेषण — कहीं भी विद्यमान न सामग्री बिल्कुल नई आनुवंशिक सामग्री लाना
    3. बिल्कुल कुछ नहीं
    4. केवल क्रोमोसोमों को हटाना, कभी संयोजन नहीं
    उत्तर देखें

    उत्तर: A — शोषण — समष्टि में पहले से विद्यमान आनुवंशिक सामग्री का पुनर्संयोजन

    संकरण दो विद्यमान जनकों की सामग्री पुनर्संयोजित करता है, पहले से आशाजनक आंशिक हलों को परिष्कृत करते हुए; उत्परिवर्तन ही वह है जो समष्टि में सर्वत्र अनुपस्थित वास्तव में नई सामग्री लाता है।

  3. यदि समष्टि में कहीं भी किसी क्रोमोसोम में विशेष उपयोगी बिट-प्रतिरूप न हो, तो वह प्रतिरूप इससे लाया जा सकता है:

    1. उत्परिवर्तन से, अकेले संकरण से नहीं
    2. अकेले संकरण से, चाहे कितनी भी पीढ़ियाँ चलें
    3. अकेले चयन से
    4. इसे किसी भी साधन से कभी नहीं लाया जा सकता
    उत्तर देखें

    उत्तर: A — उत्परिवर्तन से, अकेले संकरण से नहीं

    संकरण केवल वही सामग्री पुनर्संयोजित करता है जो समष्टि में कहीं पहले से विद्यमान हो; उत्परिवर्तन ही वह संकारक है जो सर्वत्र अनुपस्थित वास्तव में नई सामग्री ला सकता है।

  4. मानक GA चक्र में, एक पीढ़ी में चरणों का सही क्रम है:

    1. फ़िटनेस मूल्यांकित करें, जनक चुनें, संकरण करें, उत्परिवर्तित करें, समष्टि बदलें
    2. समष्टि बदलें, फिर उसे पहली बार आरंभीकृत करें
    3. फ़िटनेस बिल्कुल मूल्यांकित करने से पहले उत्परिवर्तित करें
    4. समष्टि बनने से पहले भी संकरण करें
    उत्तर देखें

    उत्तर: A — फ़िटनेस मूल्यांकित करें, जनक चुनें, संकरण करें, उत्परिवर्तित करें, समष्टि बदलें

    चयन को इसकी ओर पक्षपाती होने से पहले फ़िटनेस ज्ञात होनी ही चाहिए, व संकरण/उत्परिवर्तन प्रतिस्थापन से पहले चुने जनकों पर कार्य कर अगली पीढ़ी की संतति उत्पन्न करते हैं।

  5. आनुवंशिक कलनविधि का सर्वोत्तम वर्णन है:

    1. अनुमानी खोज, वैश्विक इष्टतम खोजने की गारंटी के बिना
    2. ठीक कलनविधि, वैश्विक इष्टतम खोजने की गारंटीशुदा
    3. वर्गीकरण कलनविधि
    4. केवल पहले से क्रमित आँकड़े पर प्रयोग करने योग्य
    उत्तर देखें

    उत्तर: A — अनुमानी खोज, वैश्विक इष्टतम खोजने की गारंटी के बिना

    किसी भी स्थानीय-सुधार-आधारित मेटा-अनुमानी की भाँति, GA केवल स्थानीय रूप से-अच्छे हल की ओर प्रगति करते अटक सकता है — यह कठिन खोज-समस्याओं हेतु व्यावहारिक अनुमानी है, वह विधि नहीं जो इष्टतमता सिद्ध करे।

  6. आनुवंशिक कलनविधियों में प्रयुक्त निम्नलिखित में कौन मानक क्रोमोसोम-एन्कोडिंग हैं? (एक से अधिक विकल्प सही हो सकते हैं।)

    1. स्थिर-लंबाई द्विआधारी स्ट्रिंग
    2. वास्तविक-मान एन्कोडिंग
    3. क्रमचय एन्कोडिंग (वस्तुओं का क्रम)
    4. बिल्कुल कोई एन्कोडिंग कभी प्रयुक्त नहीं होती
    उत्तर देखें

    उत्तर: A — स्थिर-लंबाई द्विआधारी स्ट्रिंग; B — वास्तविक-मान एन्कोडिंग; C — क्रमचय एन्कोडिंग (वस्तुओं का क्रम)

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

  7. उस चयन-क्रियाविधि का नाम बताइए जिसमें क्रोमोसोम के चुने जाने की प्रायिकता उसकी फ़िटनेस के अनुपात में हो, सामान्यतः फ़िटनेस से आकारित खंडों में बँटे चक्र को घुमाने के रूप में कल्पित।

    संख्यात्मक उत्तर — मान टाइप करें।

    उत्तर देखें

    उत्तर: roulette wheel selection

    रूलेट-व्हील चयन कमज़ोर क्रोमोसोमों को पूर्णतः बाहर किए बिना चुनाव को योग्यतर क्रोमोसोमों की ओर पक्षपाती करता है, टूर्नामेंट चयन के साथ दो मानक चयन-क्रियाविधियों में से एक।

  8. दो जनक क्रोमोसोमों पर एकल-बिंदु संकरण इस प्रकार काम करता है:

    1. दोनों जनकों को उसी यादृच्छिक स्थिति पर काटकर व पूँछें बदलकर संतति बनाना
    2. बिना कोई संतति उत्पन्न किए दोनों जनकों को पूर्णतः मिटाना
    3. कभी दो नहीं, सदा केवल एक जनक पर काम करना
    4. किसी भी जनक की परवाह किए बिना व्यक्तिगत बिट यादृच्छिक रूप से बदलना
    उत्तर देखें

    उत्तर: A — दोनों जनकों को उसी यादृच्छिक स्थिति पर काटकर व पूँछें बदलकर संतति बनाना

    एकल-बिंदु संकरण एक कट-स्थिति चुनता है व दोनों जनकों के बीच उसके आगे की पूँछें बदलता है, अतः हर संतति को एक जनक से उपसर्ग व दूसरे से प्रत्यय मिलता है — उत्परिवर्तन के एकल-क्रोमोसोम संचालन के विपरीत, दो-जनक संकारक।