जेनेटिक एलगोरिदम: फाइटिंग प्रीमेच्योर कन्वर्जेंस

पिछले निबंध में ( आनुवंशिक एल्गोरिथ्म के लिए जनसंख्या का आकार चुनना ), आनुवंशिक एल्गोरिथ्म के प्रदर्शन के लिए आवश्यक न्यूनतम जनसंख्या आकार निर्धारित किया गया था:
एन = 1 + लॉग 2 (1 / (1-पी 1 ^ (1 / एल))), जहां
पी 1 आवश्यक संभावना है कि गुणसूत्रों के एक यादृच्छिक सेट में प्रत्येक स्थान के लिए सभी आवश्यक तत्व शामिल होंगे;
एल गुणसूत्र की लंबाई है।

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

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

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


यह तुरंत ध्यान देने योग्य है कि एक स्थानीय या वैश्विक अधिकतम फिटनेस फ़ंक्शन की संभावना क्या है, इसके प्रकार पर बहुत निर्भर करता है।
नीचे दी गई समस्या के फिटनेस फ़ंक्शन के स्थानीय मैक्सिमा के क्षेत्रों का एक उदाहरण है:

एक उदाहरण के रूप में, एक ट्रैवलिंग सेल्समैन जैसी समस्या हल हो गई है, गुणसूत्रों की लंबाई L = 25 है
- क्षैतिज अक्ष पर, सभी संभव गुणसूत्र मान दिखाए गए हैं, जो दशमलव समन्वय प्रणाली में दिए गए हैं (उदाहरण के लिए, गुणसूत्र 101001010111111111110101010 x = 21692298 से मेल खाती है);
- ऊर्ध्वाधर अक्ष फिटनेस फ़ंक्शन के मूल्यों का प्रतिनिधित्व करता है।
(जैसा कि आप देख सकते हैं, स्थानीय मैक्सीमा एक दूसरे से काफी दृढ़ता से अलग हैं - इस समस्या में, समय से पहले अभिसरण के लिए सभी आवश्यक शर्तें देखी जाती हैं)।

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

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

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

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

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

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

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

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

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

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

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

- जनसंख्या के आकार के मूल्यों को क्षैतिज अक्ष के साथ प्लॉट किया जाता है, जहां 1 जनसंख्या का आकार N के बराबर है (न्यूनतम आवश्यक जनसंख्या आकार);
- आनुवंशिक एल्गोरिथ्म के परिणामस्वरूप प्राप्त गुणसूत्रों के फिटनेस फ़ंक्शन के औसत मूल्य, जहां 1 वैश्विक अधिकतम के बराबर फिटनेस फ़ंक्शन का मूल्य है, ऊर्ध्वाधर अक्ष के साथ प्लॉट किए जाते हैं।

यह स्पष्ट रूप से देखा जाता है कि माइटोसिस ऑपरेटर के उपयोग से आनुवंशिक एल्गोरिथ्म की प्रभावशीलता में काफी वृद्धि हो सकती है।
तो, आकार में 2N की आबादी के लिए माइटोसिस के साथ एक एल्गोरिथ्म (परिकलित उदाहरण एन = 20 के लिए) अधिकतम संभव का 0.9694 का औसत परिणाम देता है। मानक आनुवंशिक एल्गोरिथ्म का उपयोग करके समान मूल्यों को प्राप्त करने के लिए, 7N की आबादी की आवश्यकता होती है।
अधिकतम मिटोसिस एल्गोरिथ्म से 0.98 का ​​परिणाम प्राप्त करने के लिए, 3N की आबादी की आवश्यकता होती है, और मानक एल्गोरिथ्म में 11N की आबादी की आवश्यकता होगी

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

अपडेट: सवालों और दिलचस्प टिप्पणियों के लिए धन्यवाद - मैं केवल शाम को जवाब दे सकता हूं (दुर्भाग्य से दिन के दौरान कोई अवसर नहीं होगा); धारणा को सुगम बनाने के लिए मैं प्रूफरीडिंग भी करूंगा।