विकासवादी एल्गोरिदम: इष्टतम Repopulation टूटने

Question

यह सब शीर्षक में वास्तव में है, लेकिन यहां किसी के लिए भी एक टूटने जो विकासवादी एल्गोरिथम में रुचि रखता है है:

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

तब आप बचे हुए लोगों के क्रॉसब्रीड्स, बचे हुए लोगों के उत्परिवर्तन, और कुछ यादृच्छिक जीवों की एक निश्चित संख्या के संयोजन के साथ दोहराते हैं।

क्या यह कई हज़ार बार और कुशल जीव उत्पन्न होता है।

कुछ लोग जीवों के कई "द्वीप" पेश करने जैसी चीजें भी करते हैं, जो अलग-अलग आबादी हैं जिन्हें थोड़ी देर में पार करने की अनुमति दी जाती है।

तो, मेरा सवाल है: इष्टतम रिपोप्यूलेशन प्रतिशत क्या हैं?

मैं शीर्ष 10% कलाकारों को रख रहा हूं, और 30% क्रॉसब्रीड्स और 30% उत्परिवर्तनों के साथ दोबारा तैयार कर रहा हूं। शेष 30% नए जीवों के लिए है।

मैंने कई द्वीप सिद्धांतों को भी आजमाया है, और मुझे इसके परिणामों में भी रूचि है।

यह मुझ पर खोया नहीं गया है कि यह वास्तव में समस्या का एक प्रकार है जिसे ईए हल कर सकता है। क्या आप किसी को भी कोशिश कर रहे हैं?

अग्रिम धन्यवाद!

Answer 1

मैंने शुरुआत में मॉडल को मॉडल करने की कोशिश की जो मैंने सोचा था कि कार्बनिक सिस्टम कैसा था। आखिरकार फैसला किया कि कोई अच्छा नहीं था, और 10% रखा गया, 20% उत्परिवर्तित, 60% क्रॉसब्रेड, और 10% यादृच्छिक, और अधिक आक्रामक चला गया।

तब मैंने देखा कि मेरे शीर्ष 10% लगभग समान थे। इसलिए मैंने यादृच्छिक रूप से 30% तक बढ़ा दिया। इससे कुछ मदद मिली, लेकिन ज्यादा नहीं।

मैं किसी भी परिणाम प्राप्त करने के शीर्ष 10%, पागल लंबी पीढ़ियों की संख्या में कई द्वीप, और पीढ़ी लंघन, और reseeding है, जो बेहतर परिणाम दे दी है, लेकिन अभी भी अत्यधिक असंतोषजनक, बहुत कम बदलाव की कोशिश की थी। अधिकतर कोड ने सीखा कि मेरे फिटनेस मूल्यांकन को कैसे हैक करना है।

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

मुझे अभी भी विश्वास है कि आपके प्रश्न का इष्टतम उत्तर प्राकृतिक घटनाओं को देखकर पाया जा सकता है, जैसे फलों-फ्लाई उड़ान पथों की यादृच्छिकता के संबंध में हाल के लेख में, ताकि बाहर निकल सके।

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

Answer 2

आप जानते हैं कि आप क्या कर सकते हैं ... आप इष्टतम वितरण को निर्धारित करने के लिए आनुवांशिक एल्गोरिदम लिख सकते हैं।

लेकिन, आमतौर पर मैं शीर्ष 12% और 28% क्रॉसब्रिड रखता हूं; दूसरों के लिए 30% प्रत्येक के साथ।

Answer 3

जीए और ईए के लिए मैंने जो सर्वोत्तम संसाधन पूरे किए हैं, वे जॉन कोज़ा की किताबें Genetic Programming पर थीं। वह इस विषय को गहराई से कवर करता है - जीनोम एन्कोडिंग के लिए तकनीक, यादृच्छिक उत्परिवर्तन, प्रजनन, फिटनेस फ़ंक्शन को ट्यून करना।

व्यक्तिगत रूप से मैंने केवल शैक्षिक उद्देश्यों के लिए सिमुलेटर के एक छोटे से मुट्ठी भर लिखे हैं। मुझे जो मिला वह यह था कि मैंने उन प्रतिशतों को कैसे ट्यून किया था, जो फिटनेस फ़ंक्शन का उपयोग कर रहा था, मैं कितना यादृच्छिक उत्परिवर्तन पेश किया था और उत्परिवर्तन और प्रजनन करने के लिए मैंने कितना 'स्मार्ट' प्रयास किया था - मैंने पाया कि कम 'स्मार्ट' मैंने म्यूटेटर और क्रॉस-ओवर लॉजिक बनाने की कोशिश की, तेजी से जनसंख्या ने अपने फिटनेस स्कोर में सुधार किया - मैंने यह भी पाया कि मैं उत्परिवर्तन की संभावना में रूढ़िवादी रहा हूं - मेरे प्रारंभिक रनों ने स्थानीय अधिकतमता को मारा और एक उनमें से बाहर निकलने में मुश्किल हो रही है।

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

इस बात पर निर्भर करता है कि आप कैसे 'मेटा' प्राप्त करना चाहते हैं।

Answer 4

यह एक गर्म बहस (साहित्य और Melanie, et al books) विषय है जो बहुत डोमेन-विशिष्ट प्रतीत होता है। एन पैरामीटर के साथ एक प्रकार की एक समस्या के लिए क्या काम करता है लगभग किसी अन्य समस्या, किसी अन्य डोमेन या किसी अन्य पैरामीट्रिक सेट के लिए काम नहीं करेगा।

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

@ केली बर्टन: जीओएस और जीपी को सौंपी गई समस्याओं के प्रत्येक वर्ग में क्रॉसओवर बनाम उत्परिवर्तन दर constantly debated भी हैं।

Answer 5

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

Answer 6

दूसरे GA के लिए इष्टतम पैरामीटर निर्धारित करने के बारे में कोई उल्लेख नहीं होने के साथ, पहले GA के लिए इष्टतम पैरामीटर निर्धारित करने के लिए दूसरे GA का उपयोग करने का सुझाव देने वाले कुछ उत्तर दिखाई देंगे। मैं इस दृष्टिकोण का सुझाव देने वालों की धार्मिक मान्यताओं के बारे में सोचने में मदद नहीं कर सकता ...

Answer 7

मुझे माता-पिता गुणसूत्रों से कुछ जीनों से उत्परिवर्तन और क्रॉसओवर स्थापित करके जनसंख्या की विविधता में वृद्धि हुई है।

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

प्रैक्टिस में, मैंने बहु-गुणसूत्र जीनोटाइप का चयन किया। एक गुणसूत्र दूसरे के प्रजनन समारोह के लिए कोडित।छोटे 'प्रजनन गुणसूत्र' उत्परिवर्तन और क्रॉसओवर के लिए एक समझदार निश्चित दर थी।

मैंने पाया कि इस क्लासिक पठार और जनसंख्या के अभिसरण बंद कर देंगे।

एक तरफ, मैं प्रत्येक बच्चे के लिए क्रॉसओवर और उत्परिवर्तन दोनों करता हूं।

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

Answer 8

दूसरों के रूप में उल्लेख किया है, इष्टतम मिश्रण इस तरह के समाधान अंतरिक्ष के आकार के रूप में अपने विशिष्ट समस्या और अन्य समस्या को विशिष्ट कारकों पर निर्भर करेगा।

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

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

जब आप एक ब्रेक प्राप्त नीचे कोई है, तो दोहराव (ऊपर आंतरिक प्रजनन पर एक जैसे या नव समान व्यक्तियों का एक बहुत) के लिए कुछ बातों पर विचार करने के लिए ... कर रहे हैं। इसे कम करने के लिए आप पीढ़ियों के बीच अपनी आबादी को पार करना और नए यादृच्छिक व्यक्तियों या क्रॉसब्रेड वाले डुप्लिकेशंस को प्रतिस्थापित करना चाहते हैं।

यह कहा गया है कि मेरा वर्तमान दृष्टिकोण शीर्ष 1% को शीर्ष 20% में दोबारा पार करना है, अगले 20% में शीर्ष 40% को पार कर गया है, अगले 20% उत्पन्न करने के लिए शीर्ष 90% को पार किया है %, और यादृच्छिक रूप से बाकी उत्पन्न (3 9%)। यदि डुप्लिकेट हैं, तो मैं उन्हें हटा देता हूं और उन्हें नए यादृच्छिक व्यक्तियों के साथ बदल देता हूं।

मैं म्यूटेशन का उपयोग नहीं क्योंकि यादृच्छिक व्यक्तियों की संख्या अधिक निम्नलिखित crossbreeding के दौरान "उत्परिवर्तन" में जोड़ने का ध्यान रखना चाहिए है।