आनुवंशिक एल्गोरिथम: इष्टतम जनसंख्या का आकार

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

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

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

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


तो जनसंख्या के आकार पर परिणाम की निर्भरता इस प्रकार है:

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

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

यदि संसाधन सीमित हैं (अंत में, यह समय की कमी के कारण आता है), तो उनके उपयोग की प्रभावशीलता का मुद्दा महत्वपूर्ण हो जाता है।

इस सवाल पर विचार करें कि गणना पर प्राप्त परिणाम / संसाधनों के अनुपात के संदर्भ में जनसंख्या का आकार सबसे अधिक लाभदायक क्या है।

हम निम्नानुसार समस्या का सुधार करते हैं: 2N की जनसंख्या आकार के साथ एक बार GA चलाने या एन के जनसंख्या आकार के साथ एल्गोरिथ्म को दो बार चलाने में अधिक लाभदायक क्या है और प्राप्त 2 में से सबसे अच्छा परिणाम चुनें?
तुलनात्मक परिणाम निम्नलिखित ग्राफ में देखे जा सकते हैं:


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

एक्स 1 द्वारा इंगित किए गए अंक जनसंख्या आकार एन।
इस मामले में, पहला बिंदु GA के एकल लॉन्च से मेल खाता है;
दूसरा बिंदु 2 जीए लॉन्च के अनुरूप है और प्राप्त परिणामों से अधिकतम मूल्य का विकल्प, आदि।

X2 द्वारा इंगित किए गए अंक 2N की जनसंख्या के आकार के अनुरूप हैं
आदि

यह स्पष्ट रूप से देखा जाता है कि दक्षता एन में एक उल्लेखनीय वृद्धि केवल तभी प्राप्त की जाती है जब आकार N की जनसंख्या से आकार 2N की जनसंख्या में स्थानांतरित किया जाता है।
जनसंख्या के आकार में और वृद्धि से दक्षता में कोई उल्लेखनीय वृद्धि नहीं होती है।

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