MATLAB में आनुवंशिक एल्गोरिथ्म

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

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



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



(कटौती के तहत, मुख्य भाग + कुछ स्क्रीनशॉट)।





MATLAB में आनुवंशिक एल्गोरिदम के साथ काम करने का तंत्र दो तरीकों से लागू किया गया है:



1. आनुवंशिक एल्गोरिदम के कार्य को कॉल करना

2. जेनेटिक एल्गोरिथम टूल का उपयोग करना



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

जेनेटिक अलॉजिटम टूल के साथ काम करें

जेनेटिक एल्गोरिथम टूल को चलाने के लिए, MATLAB कमांड लाइन पर गैटूल कमांड चलाएं। उसके बाद, आनुवंशिक एल्गोरिदम का पैकेज लॉन्च किया जाएगा और मुख्य उपयोगिता विंडो स्क्रीन पर दिखाई देगी।







फिटनेस फ़ंक्शन फ़ील्ड में, अनुकूलित फ़ंक्शन को @fitnessfun के रूप में इंगित किया जाता है, जहां fitnessfun.m M-फ़ाइल का नाम है जिसमें अनुकूलित फ़ंक्शन को पहले वर्णित किया जाना चाहिए। बस के मामले में, मैं ध्यान दें कि मेनू फ़ाइल के माध्यम से MATLAB वातावरण में बनाई गई है फ़ाइल-> नई-> M- फ़ाइल। एम-फाइल में कुछ फ़ंक्शन my_fun के विवरण का एक उदाहरण:



समारोह z = my_fun (x)

z = x (1) ^ 2 - 2 * x (1) * x (2) + 6 * x (1) + x (2) ^ 2 - 6 * x (2);



गैटूल उपयोगिता की मुख्य खिड़की पर वापस। चर फ़ील्ड की संख्या फ़ंक्शन के इनपुट वेक्टर की लंबाई को अनुकूलित करने का संकेत देती है। उपरोक्त उदाहरण में, फ़ंक्शन my_fun में लंबाई 2 का इनपुट वेक्टर है।

बाधा पैनल में, आप बाधाओं या एक गैर-रेखीय फ़ंक्शन को निर्दिष्ट कर सकते हैं। रैखिक असमानताओं के क्षेत्र में, एक रेखीय प्रतिबंध फार्म की असमानता से निर्धारित होता है:



ए * एक्स * बी।



इस पैनल के रैखिक समानता क्षेत्र में, समानता द्वारा रैखिक बाधाएं निर्धारित की जाती हैं:



ए * एक्स = बी।



दोनों मामलों में, ए कुछ मैट्रिक्स है, बी एक वेक्टर है।



वेक्टर रूप में सीमा क्षेत्र में, चर की निचली और ऊपरी बाधाएं निर्धारित की जाती हैं, और नॉनलाइनियर बाधा समारोह क्षेत्र में, आप एक मनमाने ढंग से गैर-बाधा अवरोधक कार्य निर्दिष्ट कर सकते हैं।



यदि किसी विशिष्ट कार्य के लिए बाधाओं की स्थापना की आवश्यकता नहीं है, तो बाधा पैनल के सभी फ़ील्ड खाली छोड़ दिए जाने चाहिए।



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



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



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







गैटूल में मुख्य विन्यास विकल्प हैं:

- जनसंख्या (जनसंख्या टैब);

- स्केलिंग (फिटनेस स्केलिंग टैब);

- चयन ऑपरेटर (चयन टैब);

- प्रजनन ऑपरेटर (प्रजनन टैब);

- म्यूटेशन ऑपरेटर (म्यूटेशन टैब);

- ऑपरेटर क्रॉसिंग (क्रॉसओवर टैब);

- आबादी के बीच व्यक्तियों का स्थानांतरण (प्रवासन टैब);

- विशेष एल्गोरिथ्म पैरामीटर (एल्गोरिथम सेटिंग्स टैब);

- कार्य हाइब्रिड फ़ंक्शन (हाइब्रिड फ़ंक्शन टैब);

- एल्गोरिथ्म (टैब स्टॉपिंग मानदंड) को रोकने के लिए मानदंड स्थापित करना;

- आनुवंशिक एल्गोरिथ्म (प्लॉट फ़ंक्शंस टैब) के संचालन के दौरान विभिन्न अतिरिक्त जानकारी का उत्पादन;

- नए फ़ंक्शन (टैब आउटपुट फ़ंक्शन) के रूप में एल्गोरिदम के परिणामों का आउटपुट;

- कमांड विंडो पर आउटपुट के लिए जानकारी का एक सेट निर्दिष्ट करना (विंडो टैब को कमांड करने के लिए प्रदर्शन);

- अनुकूलित और सीमित कार्यों (उपयोगकर्ता फ़ंक्शन मूल्यांकन टैब) के मूल्यों की गणना करने की एक विधि।



आइए हम उपरोक्त सभी टैब विकल्प पैनल और उन तत्वों पर अधिक विस्तार से विचार करें, जिनमें वे शामिल हैं।



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

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



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



चयन टैब आपको ज़ूम फ़ंक्शन से डेटा के आधार पर एक मूल चयन ऑपरेटर का चयन करने की अनुमति देता है। निम्नलिखित विकल्प चयनकर्ता विकल्प के रूप में उपलब्ध हैं:



- टूर्नामेंट - व्यक्तियों की निर्दिष्ट संख्या को यादृच्छिक रूप से चुना जाता है, उनमें से सबसे अच्छा प्रतिस्पर्धी आधार पर चुना जाता है;

- रूले - रूलेट नकली है जिसमें प्रत्येक खंड का आकार इसकी संभावना के अनुसार सेट किया गया है;

- वर्दी - माता-पिता को किसी दिए गए वितरण के अनुसार यादृच्छिक रूप से चुना जाता है और माता-पिता की संख्या और उनकी संभावनाओं को ध्यान में रखते हुए;

- स्टोचैस्टिक यूनिफॉर्म - एक लाइन बनाई जाती है, जिसमें प्रत्येक माता-पिता को एक निश्चित आकार (माता-पिता की संभावना के आधार पर) का एक हिस्सा सौंपा जाता है, फिर एल्गोरिथ्म उसी लंबाई के चरणों में लाइन के पसीने को चलाता है और माता-पिता का चयन करता है, जिसके आधार पर लाइन के किस हिस्से पर कदम टकराया है।



प्रजनन टैब निर्दिष्ट करता है कि नए व्यक्ति कैसे बनाए जाते हैं। अभिजात वर्ग गणना आइटम आपको उन व्यक्तियों की संख्या निर्दिष्ट करने की अनुमति देता है जो अगली पीढ़ी को पास करने की गारंटी देते हैं। क्रॉसओवर अंश उन व्यक्तियों के अनुपात को इंगित करता है जो क्रॉसिंग द्वारा बनाए जाते हैं। शेष उत्परिवर्तन द्वारा निर्मित है।



म्यूटेशन ऑपरेटर टैब में, म्यूटेशन ऑपरेटर का प्रकार चुना जाता है। निम्नलिखित विकल्प उपलब्ध हैं:



- गॉसियन - प्रत्येक व्यक्तिगत वेक्टर के सभी घटकों के लिए एक छोटे यादृच्छिक संख्या (गॉसियन वितरण के अनुसार) को जोड़ता है;

- वर्दी - वैक्टर के घटकों को यादृच्छिक रूप से चुना जाता है और स्वीकार्य सीमा से यादृच्छिक संख्या उनके स्थान पर लिखी जाती है;

अनुकूली व्यवहार्य - नवीनतम सबसे सफल और असफल पीढ़ियों के आधार पर दिशाओं का एक सेट उत्पन्न करता है और, लगाए गए प्रतिबंधों के अधीन, सभी दिशाओं को एक अलग लंबाई में ले जाता है;

- कस्टम - आप अपने खुद के समारोह सेट करने के लिए अनुमति देता है।



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



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



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



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

- कोई नहीं (हाइब्रिड फ़ंक्शन का उपयोग न करें);

- fminsearch (मूल्यों की न्यूनतम के लिए खोज);

- पैटर्न खोज (पैटर्न द्वारा खोज);

- fminunc (असीमित एल्गोरिथ्म के लिए);

- fmincon (दिए गए प्रतिबंधों के साथ एक एल्गोरिथ्म के लिए)।



स्टॉपिंग मानदंड टैब उन स्थितियों को इंगित करता है जिसमें एल्गोरिथ्म बंद हो जाता है। एक ही समय में, निम्नलिखित पैरामीटर विन्यास योग्य हैं:



- पीढ़ियां - पीढ़ियों की अधिकतम संख्या जिसके बाद एक पड़ाव होता है;

- समय सीमा - एल्गोरिथ्म के लिए समय सीमा;

- फिटनेस सीमा - यदि इस सीमा से अधिक या इसके बराबर अनुकूलित मूल्य कम है, तो एल्गोरिथ्म बंद हो जाएगा;

- स्टाल पीढ़ी - थोड़ी अलग पीढ़ियों की संख्या जिसके बाद एल्गोरिथ्म बंद हो जाता है;

- स्टाल समय सीमा - पिछले पैरामीटर के समान, लेकिन एल्गोरिथ्म के चलने के समय के लिए लागू;

- समारोह सहिष्णुता और Nonlinear बाधा सहिष्णुता - क्रमशः और सीमित कार्यों के परिवर्तनों के न्यूनतम मूल्य, जिस पर एल्गोरिदम काम करना जारी रखेगा।



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



- प्लॉट अंतराल - पीढ़ियों की संख्या जिसके बाद शेड्यूल का अगला अपडेट होता है;

- सर्वश्रेष्ठ फिटनेस - प्रत्येक पीढ़ी के लिए अनुकूलित फ़ंक्शन के सर्वोत्तम मूल्य का आउटपुट;

- सर्वश्रेष्ठ व्यक्ति - प्रत्येक पीढ़ी में सबसे अच्छा अनुकूलन परिणाम के साथ पीढ़ी के सर्वश्रेष्ठ प्रतिनिधि का निष्कर्ष;

- दूरी - पीढ़ी में व्यक्तियों के मूल्यों के बीच के अंतराल को प्रदर्शित करता है;

- अपेक्षा - संभावनाओं की एक श्रृंखला और पीढ़ियों के संबंधित व्यक्तियों को प्राप्त करता है;

- वंशावली - व्यक्तियों के परिवार के पेड़ का निष्कर्ष;

- रेंज - प्रत्येक पीढ़ी के लिए अनुकूलित फ़ंक्शन के सबसे छोटे, सबसे बड़े और औसत मूल्यों का उत्पादन;

- स्कोर विविधता - प्रत्येक पीढ़ी में रेटिंग का हिस्टोग्राम प्रदर्शित करें;

- स्कोर - एक पीढ़ी में प्रत्येक व्यक्ति की आउटपुट रेटिंग;

- चयन - माता-पिता का एक हिस्टोग्राम प्रदर्शित करें;

- रोकना - उन सभी मापदंडों की स्थिति के बारे में जानकारी प्रदर्शित करना जो रोक के मानदंडों को प्रभावित करते हैं;

- कस्टम - कुछ उपयोगकर्ता-निर्दिष्ट फ़ंक्शन के चार्ट पर प्रदर्शित करें।



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



उपयोगकर्ता फ़ंक्शन मूल्यांकन टैब बताता है कि किस क्रम में अनुकूलित और सीमित कार्यों के मूल्यों की गणना की जाती है (अलग से, एक कॉल में समानांतर में, या एक साथ)।



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



पुनश्च। इस विषय को लिखते समय, लेखक ने अपने व्यक्तिगत अनुभव और हेल्प'म परिवेश MATLAB का उपयोग किया। आगे के लेखों में मैं विशिष्ट उदाहरणों, दोनों शास्त्रीय (एक रैखिक समारोह का अनुकूलन, शूटिंग और यात्रा सेल्समैन कार्यों का अनुकूलन), और कुछ विशिष्ट लोगों के साथ ऊपर वर्णित तंत्र को प्रकट करने का प्रयास करूंगा।



PPS उन लोगों के लिए आपका ध्यान देने के लिए धन्यवाद जो अंत तक पढ़ते हैं।