मेमेटिक कलनविधि

कंप्यूटर विज्ञान और संचालन अनुसंधान में जेनेटिक एल्गोरिद्म (एमए) पारंपरिक आनुवंशिक कलनविधि (जीए) या अधिक सामान्य विकासवादी कलनविधि (ईए) का विस्तार है। यह अनुकूलन समस्या के लिए पर्याप्त रूप से अच्छा समाधान प्रदान कर सकता है। यह ईए द्वारा उत्पन्न समाधानों की गुणवत्ता में संशोधन करने और समयपूर्व अभिसरण की संभावना को कम करने के लिए उपयुक्त अनुमानी या स्थानीय खोज (अनुकूलन) विधि का उपयोग करता है।

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

परिचय

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

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

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

सैद्धांतिक पृष्ठभूमि

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

एमए का विकास

पहली पीढ़ी

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

छद्म कोड:

   Procedure Memetic Algorithm

   Initialize: Generate an initial population, evaluate the individuals and assign a quality value to them;
   while Stopping conditions are not satisfied do
       Evolve a new population using stochastic search operators.
       Evaluate all individuals in the population and assign a quality value to them.
       Select the subset of individuals, $\Omega _{il}$, that should undergo the individual improvement procedure.
       for each individual in $\Omega _{il}$ do
           Perform individual learning using meme(s) with frequency or probability of $f_{il}$, with an intensity of $t_{il}$.
           Proceed with Lamarckian or Baldwinian learning.
       end for

   end while        

इस संदर्भ में लैमार्कवाद का अर्थ है व्यक्तिगत सीखने के चरण द्वारा प्राप्त उत्तम समाधान के अनुसार क्रोमोसोम को अपडेट करना, जबकि बाल्डविनियन प्रभाव क्रोमोसोम को अपरिवर्तित छोड़ देता है और केवल उत्तम फिटनेस का उपयोग करता है। यह छद्म कोड खुला छोड़ देता है कि कौन से कदम व्यक्तियों की फिटनेस पर आधारित हैं और कौन से नहीं हैं। प्रश्न में नई जनसंख्या का विकास और $\Omega _{il}$ चयन है।

चूंकि अधिकांश एमए कार्यान्वयन ईएएस पर आधारित होते हैं, पहली पीढ़ी के संबंधित प्रतिनिधि का छद्म कोड भी यहां दिया गया है, क्रास्नोगोर के बाद:

छद्म कोड

   Procedure Memetic Algorithm Based on an EA

   Initialization: ;
                   randomly generate an initial populationn;
   while Stopping conditions are not satisfied do
       Evaluation: Compute the fitness ;
       Selection: Accordingly to $f(p)$ choose a subset of $P(t)$ and store it in $M(t)$;
       Offspring: Recombine and mutate individuals $p\in M(t)$ and store them in $M'(t)$;
       Learning: Improve $p'$ by loacal search or heuristic $\forall p'\in M'(t)$;
       Evaluation: Compute the fitness $f(p')\ \ \forall p'\in M'(t)$;
       if Lamarckian learning then
          Update chromosome of $p'$ according to improvement $\forall p'\in M'(t)$;
       fi
       New generation: Generate $P(t+1)$ by selecting some individuals from $P(t)$ and $M'(t)$;
      $t=t+1$;
   end while
   Return best individual $p\in P(t-1)$ as result;

इस एमए योजना के लिए कुछ विकल्प हैं। उदाहरण के लिए:

• सभी या कुछ प्रारंभिक व्यक्तियों को मीम द्वारा संशोधन किया जा सकता है।
• संतान के स्थान पर माता-पिता का स्थानीय संशोधन हो सकता है।
• सभी संतानों के अतिरिक्त , केवल अनियमित ढंग से चयनित या फिटनेस पर निर्भर अंश में स्थानीय संशोधन हो सकता है।

दूसरी पीढ़ी

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

तीसरी पीढ़ी

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

कुछ डिज़ाइन टिप्पणियाँ

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

किसी विशेष समस्या या व्यक्ति के लिए उपयोग की जाने वाली व्यक्तिगत सीखने की विधि या मेम का चयन

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

संयोजी अनुकूलन में, दूसरी ओर, अलग-अलग सीखने की विधियां सामान्यतः ह्यूरिस्टिक्स (जो नियतात्मक या स्टोचैस्टिक हो सकते हैं) के रूप में उपस्थित होते हैं जो कि ब्याज की विशिष्ट समस्या के अनुरूप होते हैं। विशिष्ट अनुमानी प्रक्रियाओं और योजनाओं में के-जीन एक्सचेंज, एज एक्सचेंज, प्रथम-संशोधन, और कई अन्य सम्मिलित हैं।

व्यक्तिगत सीखने की आवृत्ति का निर्धारण

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

व्यक्तियों का चयन जिस पर व्यक्तिगत शिक्षा प्रयुक्त होती है

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

व्यक्तिगत सीखने की तीव्रता की विशिष्टता

व्यक्तिगत सीखने की तीव्रता, $t_{il}$, व्यक्तिगत सीखने की पुनरावृत्ति के लिए आवंटित कम्प्यूटेशनल बजट की राशि है; अर्थात, एकल समाधान में संशोधन पर खर्च करने के लिए व्यक्तिगत सीखने के लिए स्वीकार्य अधिकतम कम्प्यूटेशनल बजट।

लैमार्कियन या बाल्डविनियन सीखने का विकल्प

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

अनुप्रयोग

मेमेटिक कलनविधि को वास्तविक दुनिया की कई समस्याओं पर सफलतापूर्वक प्रयुक्त किया गया है। चूंकि बहुत से लोग मेमेटिक कलनविधि से संबंधित विधियों को नियोजित करते हैं, वैकल्पिक नाम जैसे हाइब्रिड जेनेटिक कलनविधि भी कार्यरत हैं।

शोधकर्ताओं ने कई शास्त्रीय एनपी (जटिलता) समस्याओं से निपटने के लिए मेमेटिक कलनविधि का उपयोग किया है। उनमें से कुछ को उद्धृत करने के लिए: ग्राफ़ विभाजन, नैपसैक समस्या, ट्रैवलिंग सेल्समैन की समस्या, द्विघात असाइनमेंट समस्या, सेट कवर समस्या, ग्राफ़ रंग # कलनविधि, स्वतंत्र सेट समस्या, बिन पैकिंग समस्या और सामान्यीकृत असाइनमेंट समस्या।

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

मेमेटिक कलनविधि में हाल की गतिविधियाँ

• मेमेटिक कलनविधि पर आईईईई वर्कशॉप (डब्ल्यूओएमए 2009)। कार्यक्रम के अध्यक्ष: जिम स्मिथ, इंग्लैंड के पश्चिम विश्वविद्यालय, यू.के.; यू-सून ओंग, नानयांग टेक्नोलॉजिकल यूनिवर्सिटी, सिंगापुर; गुस्ताफसन स्टीवन, नॉटिंघम विश्वविद्यालय; यू.के.; मेंग हियोट लिम, नानयांग टेक्नोलॉजिकल यूनिवर्सिटी, सिंगापुर; नतालियो क्रास्नोगोर, नॉटिंघम विश्वविद्यालय, यू.के.
• मेमेटिक कंप्यूटिंग जर्नल, पहला अंक जनवरी 2009 में प्रकाशित हुआ।
• 2008 IEEE वर्ल्ड कांग्रेस ऑन कम्प्यूटेशनल इंटेलिजेंस (WCCI 2008), हांगकांग, पर विशेष सत्र मेमेटिक कलनविधि।
• 'सॉफ्ट कंप्यूटिंग में उभरते रुझान - मेमेटिक कलनविधि' पर विशेष अंक, सॉफ्ट कंप्यूटिंग जर्नल, पूर्ण और प्रेस में , 2008.
• Memetic कंप्यूटिंग पर IEEE कम्प्यूटेशनल इंटेलिजेंस सोसाइटी इमर्जेंट टेक्नोलॉजीज टास्क फोर्स
• IEEE Congress on Evolutionary Computation (CEC 2007), सिंगापुर, org/web/20080216234225/http://ntu-cg.ntu.edu.sg/ysong/MA-SS/MA.htm मेमेटिक कलनविधि पर विशेष सत्र।
• 'Memetic Computing' थॉमसन साइंटिफिक के एसेंशियल साइंस इंडिकेटर्स एज एन इमर्जिंग फ्रंट रिसर्च एरिया द्वारा।
• मेमेटिक कलनविधि पर विशेष अंक, सिस्टम, मैन और साइबरनेटिक्स पर आईईईई लेनदेन - भाग बी: साइबरनेटिक्स, वॉल्यूम। 37, नंबर 1, फरवरी 2007।
• Memetic Algorithms में हालिया प्रगति, सीरीज: अस्पष्टता और सॉफ्ट कंप्यूटिंग में अध्ययन , वॉल्यूम। 166, ISBN 978-3-540-22904-9, 2005.
• Memetic कलनविधि पर विशेष अंक, विकासवादी संगणना पतन 2004, Vol. 12, संख्या 3: वी-वि।