आनुवंशिक एल्गोरिथ्म के लिए जनसंख्या आकार का चयन

आत्मा के लिए आनुवंशिक एल्गोरिदम के साथ प्रयोग करना।

मैं निबंध की एक छोटी श्रृंखला में अपने अनुभव, टिप्पणियों और विचारों को थोड़ा साझा करना चाहता था।

इसलिए, पहला सवाल जिसके बारे में मैंने सोचा था: किस आकार की आबादी का चयन करना है।
यदि हम इस प्रश्न को व्यवस्थित रूप से तैयार करते हैं, तो यह इस तरह से ध्वनि करेगा:

किस सिद्धांत के आधार पर, जनसंख्या के आकार की गणना करने के लिए कौन से मापदंड पर आधारित है?


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

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

सादगी के लिए, हम एक उदाहरण के रूप में एल जीन से एक गुणसूत्र लेते हैं, जिसमें प्रत्येक जीन के युग्मक मान {0, 1} हैं।

सैद्धांतिक रूप से, गुणसूत्रों की जनसंख्या का आकार सीमा [1, 2 ^ L] हो सकता है।
जहां जनसंख्या का आकार 2 ^ L सीमित मामला है जिसमें आनुवंशिक एल्गोरिथ्म एक संपूर्ण खोज एल्गोरिथ्म में पतित हो जाता है (वह स्थिति जब आनुवंशिक ऑपरेटरों के उपयोग के बिना समाधान पाया जाता है क्योंकि फिटनेस फ़ंक्शन सभी संभावित मूल्यों के लिए गणना की जाती है);
और जनसंख्या का आकार 1 एक पतित मामला है (किसी भी मूल्य का एक यादृच्छिक विकल्प और स्वैच्छिक तरीके से अपने इष्टतम की घोषणा)।
यह पतित मामला अच्छी तरह से लागू हो सकता है जब किसी भी उत्तर (यहां तक ​​कि इष्टतम नहीं) एक उत्तर की पूर्ण अनुपस्थिति की तुलना में बहुत बेहतर है।
वैसे, इस दृष्टिकोण की प्रयोज्यता का क्षेत्र अच्छी तरह से एक मजाक द्वारा विशेषता है:
Chapaev Petke: उपकरणों?
पेटका: बीस
चापाव: बीस क्या है?
पेटका: उपकरणों के बारे में क्या?

हमारी गुणसूत्र आबादी का आकार N है
चूंकि हम एक उपसमुच्चय पर पुनर्संयोजन करते हैं, लेकिन साथ ही साथ हमारा लक्ष्य पूरे सेट के लिए इष्टतम मूल्य का पता लगाना है, गुणसूत्रों के सेट में सभी मूल्य आवश्यक होने चाहिए ताकि उन्हें पुन: संयोजन करके पूरे सेट के तत्वों में से कोई भी तत्व प्राप्त हो सके।
यानी जनसंख्या का आकार ऐसा होना चाहिए कि प्रत्येक जीन (हमारे मामले में, नियंत्रण रेखा) के लिए एलील के सभी संभावित मान पूरी आबादी में प्रस्तुत किए जाएं।
मुझे एक उदाहरण के साथ समझाता हूं: L = 5, N = 4 और कुछ बिंदु पर जनसंख्या इस तरह दिखती है:
10110
10011
11100
10001
तो:
- सभी चार गुणसूत्रों में पहला स्थान केवल एलील 1 द्वारा दर्शाया गया है;
- दूसरे स्थान को तीन मानों 0 और एक मान 1 द्वारा दर्शाया गया है;
- तीसरे स्थान को दो मानों 0 और दो मान 1 द्वारा दर्शाया गया है;
- चौथे स्थान को 0 के दो मूल्यों और 1 के दो मूल्यों द्वारा दर्शाया गया है;
- पाँचवें लोको को 0 के दो मान और 1 के दो मान द्वारा दर्शाया जाता है।

तदनुसार, यदि गुणसूत्र 01010 के लिए इष्टतम मूल्य प्राप्त किया जाता है, तो कोई भी बात नहीं है कि आनुवंशिक एल्गोरिथ्म कितना काम करता है (म्यूटेशन ऑपरेटर का उपयोग किए बिना), यह मान कभी नहीं मिलेगा।

अब आइए इस संभावना की गणना करें कि गुणसूत्रों के एक यादृच्छिक सेट में सभी आवश्यक तत्व शामिल होंगे:
सभी गुणसूत्रों में किसी भी लोकी की संभावना केवल 1 (1/2) ^ N के बराबर होती है
सभी गुणसूत्रों में किसी भी लोकी की संभावना केवल 0 (1/2) ^ N के बराबर होती है
जाहिर है, अन्य सभी मामलों में, पूरा सेट {0,1} मौजूद होगा
इस प्रकार, एक स्थान की संभावना है: 1 - (1/2) ^ एन - (1/2) ^ एन = 1 - (1/2) ^ (एन -1)
तदनुसार, संभावना है कि सभी एल लोकी में एलील्स का एक पूरा सेट होगा:
पी 1 = (1 - (1/2) ^ (एन -1)) ^ एल
अब हम P के संदर्भ में N (जनसंख्या में गुणसूत्रों की संख्या) को व्यक्त करते हैं (संभावना है कि जनसंख्या में पुनर्संयोजन के लिए आवश्यक सभी तत्व शामिल होंगे) और L (गुणसूत्र में लोकी की संख्या)
N = 1 + LOG2 (1 / (1-P1 ^ (1 / L)))

उदाहरण के लिए, एल = 100 और पी 1 = 0.999 (यानी 99.9%) के लिए, हम आवश्यक जनसंख्या आकार N = 18 प्राप्त करते हैं (संभावित विभिन्न गुणसूत्रों की कुल संख्या के साथ ~ 10 ^ 30)

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

संभावना यह है कि किसी भी लोकी में सभी गुणसूत्रों के लिए केवल 1 या केवल 0 होगा (1/2) ^ (N-1)
हम कुछ हद तक P2 उत्परिवर्तन की संभावना (खोई विविधता को बहाल करने के लिए) को व्यक्त करने का प्रयास करेंगे
तो, पी 2 एक गुणसूत्र के उत्परिवर्तन की संभावना है।
फिर गुणसूत्र के एक विशिष्ट स्थान के उत्परिवर्तन की संभावना P2 / L के बराबर होती है।
संभावना है कि किसी दिए गए गुणसूत्र स्थान को उत्परिवर्तित नहीं करता है 1 - P2 / L
संभावना है कि यह लोकोस किसी भी गुणसूत्र में उत्परिवर्तित नहीं होता है (1 - P2 / L) ^ N
तदनुसार, संभावना यह है कि किसी दिए गए लोकोस को कम से कम एक गुणसूत्र में परिवर्तित किया जाता है 1 - (1 - P2 / L) ^ N
विश्वसनीयता के लिए, यह आवश्यक है कि किसी गुणसूत्र के कम से कम एक गुणसूत्र में दिए गए स्थान के उत्परिवर्तन की संभावना सभी गुणसूत्रों में इस स्थान में किसी भी मान (0 या 1) की अनुपस्थिति की संभावना से अधिक परिमाण का एक आदेश है।
इसके अलावा, एक उत्परिवर्तन के तथ्य का मतलब यह नहीं है कि हम उस उत्परिवर्तन से निपट रहे हैं जिसकी हमें आवश्यकता है।
इस प्रकार, हमारे पास असमानता है:
1 - (1 - पी 2 / एल) ^ एन> 10 * (1/2) ^ (एन -1)
इसे बदलने पर, हमें निम्नलिखित मूल्य मिलते हैं:
P2> L * (1- (1-10 * (1/2) ^ (N-1)) ^ (1 / N)
असमानता की निचली सीमा के आधार पर, हम एक गुणसूत्र के उत्परिवर्तन की संभावना की गणना के लिए निम्नलिखित सूत्र प्राप्त करते हैं:
पी 2 = एल * (1- (1-10 * (1/2) ^ (एन -1)) ^ (1 / एन)
N = 18 के लिए (हमारे द्वारा गणना, L = 100 और P1 = 99.9% के आधार पर), हम P2 ~ 0.05% प्राप्त करते हैं

यानी एक लंबे एल = 100 लोकी के साथ गुणसूत्रों के लिए, हम न्यूनतम आवश्यक जनसंख्या आकार एन = 18 प्राप्त करते हैं और एक गुणसूत्र पी 2 = 0.04% के उत्परिवर्तन की आवश्यक संभावना
L = 1000 के लिए, हमें N = 22 और P2 = 0.03% मिलता है

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

परिस्थितियों की पर्याप्तता का आकलन करने के लिए, स्थानीय / वैश्विक आशाओं के अभिसरण / अभिसरण की दर को ध्यान में रखना आवश्यक है (यह अगले निबंध का विषय है - मुझे लगता है कि एक या दो सप्ताह में)।