मेरे अनुवांशिक एल्गोरिदम के लिए क्रॉसओवर जोड़ने से मुझे और नतीजे मिलते हैं?

Question

मैंने ट्रैवलिंग सेल्समैन समस्या (टीएसपी) को हल करने के लिए एक जेनेटिक एल्गोरिदम लागू किया है। जब मैं केवल उत्परिवर्तन का उपयोग करता हूं, तो जब मैं क्रॉसओवर में जोड़ता हूं तो मुझे बेहतर समाधान मिलते हैं। मुझे पता है कि सामान्य क्रॉसओवर विधियां टीएसपी के लिए काम नहीं करती हैं, इसलिए मैंने Ordered Crossover और PMX Crossover विधियों दोनों को लागू किया, और दोनों खराब परिणामों से पीड़ित हैं। 1% और 25% के बीच का परीक्षण किया उत्परिवर्तन दर के साथ एकल स्वैप उत्परिवर्तन या उल्टे Subsequence उत्परिवर्तन (as described by Tiendil here):

उत्परिवर्तन:

यहाँ अन्य पैरामीटर मैं उपयोग कर रहा हूँ कर रहे हैं।

चयन: रूलेट व्हील चयन

स्वास्थ्य समारोह: दौरे के 1/दूरी

जनसंख्या आकार: GA 5 बार 100 परीक्षण किया गया, 200, 500, मैं भी चलाने के लिए इतना है कि मेरे पास विभिन्न प्रकार की आबादी है।

बंद करो स्थिति: 2500 पीढ़ियों

26 अंक का एक ही डाटासेट के साथ

, मैं आमतौर पर उच्च उत्परिवर्तन दर के साथ विशुद्ध रूप से उत्परिवर्तन का उपयोग कर 500-600 के बारे में दूरी के परिणाम मिलता है। क्रॉसओवर जोड़ते समय मेरे परिणाम आमतौर पर 800 दूरी सीमा में होते हैं। दूसरी भ्रमित बात यह है कि मैंने समस्या को हल करने के लिए एक बहुत ही सरल हिल-क्लाइंबिंग एल्गोरिदम लागू किया है और जब मैं उस 1000 गुना (GA 5 बार चलाने से तेज़) चलाता हूं तो मुझे परिणाम 410-450 दूरी मिलते हैं, और मैं उम्मीद करता हूं जीए का उपयोग करके बेहतर परिणाम प्राप्त करने के लिए।

कोई विचार यह है कि जब मैं क्रॉसओवर जोड़ता हूं तो मेरा जीए खराब क्यों होता है? और यह एक साधारण हिल-क्लाइंब एल्गोरिदम की तुलना में बहुत खराब क्यों कर रहा है जो स्थानीय मैक्सिमा पर फंस जाना चाहिए क्योंकि स्थानीय मैक्स मिलने के बाद इसका अन्वेषण करने का कोई तरीका नहीं है?

Answer 1

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

यह भी कहना उचित है कि जीएसपी को हल करने के लिए जीए सबसे अच्छा उपकरण नहीं है। वैसे भी, आपको इसे लागू करने के कुछ उदाहरणों की तरह दिखना चाहिए। जैसे http://www.lalena.com/AI/Tsp/

Answer 2

क्रॉसओवर जोड़ा जाने पर आपके परिणामों के बदतर होने का एक कारण यह हो सकता है क्योंकि यह ऐसा नहीं कर रहा है जो इसे करना चाहिए- दो व्यक्तियों की सर्वोत्तम सुविधाओं को गठबंधन करें। कम क्रॉसओवर संभावना के साथ प्रयास करें? जनसंख्या विविधता यहां एक मुद्दा हो सकता है। मॉरिसन और डी जोंग उनके काम में जनसंख्या विविधता का मापन विविधता का एक उपन्यास उपाय प्रस्तावित करता है। उस उपाय का उपयोग करके आप देख सकते हैं कि पीढ़ियों में आपकी जनसंख्या विविधता कैसे बदल रही है। देखें कि जब आप क्रॉसओवर का उपयोग करते हैं या क्रॉसओवर का उपयोग नहीं करते हैं तो इससे क्या फर्क पड़ता है।

इसके अलावा, आपके ओएक्स या पीएमएक्स कार्यान्वयन में कुछ मामूली गलती/मिस्ड विस्तार हो सकता है। शायद आपने कुछ अनदेखा किया है? बीटीडब्लू, क्या आप एज रीकॉम्बिनेशन क्रॉसओवर ऑपरेटर को आजमा सकते हैं? (Pyevolve में एक कार्यान्वयन है)।

Answer 3

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

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

यह रेखांकित है कि क्रॉसओवर आनुवांशिक एल्गोरिदम की इस समरूपता को तोड़ने के बिना विकासवादी 'निकस' (जहां समरूपता की कमी अक्सर आवश्यक होती है) भरने में सक्षम नहीं होगी - और यही कारण है कि क्रॉसओवर (इसके सभी रूपों में) अनिवार्य रूप से महत्वपूर्ण है मामलों के विशाल बहुमत में।

Answer 4

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

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

Answer 5

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