क्या जेनेटिक एल्गोरिदम नथ की समस्या जैसी समस्याओं के लिए उपयुक्त हैं?
हम सभी जानते हैं कि जेनेटिक एल्गोरिदम एक इष्टतम या निकट-इष्टतम समाधान दे सकते हैं। तो, एनपी-हार्ड जैसी कुछ समस्याओं में, समय और इष्टतम समाधान के बीच व्यापार-बंद होने के साथ निकट-इष्टतम समाधान काफी अच्छा है।
चूंकि इष्टतम समाधान खोजने की कोई गारंटी नहीं है, क्या जीए नथ की समस्या को हल करने के लिए एक अच्छा विकल्प माना जाता है?
आर्टिफिशियल इंटेलिजेंस के अनुसार: एक आधुनिक दृष्टिकोण (तीसरा संस्करण), खंड 3.2 (पृष्ठ 73):
नुथ ने अनुमान लगाया कि संख्या 4 से शुरू होकर, फैक्टरियल, स्क्वायर रूट और फ्लोर ऑपरेशंस का एक क्रम किसी भी वांछित सकारात्मक पूर्णांक तक पहुंच जाएगा।
उदाहरण के लिए, 4 से 5 तक पहुंचा जा सकता है:
मंजिल (sqrt (sqrt (sqrt) (sqrt (4!!)!)))))
इसलिए, यदि हमारे पास एक संख्या (5) है और हम दिए गए नंबर तक पहुंचने के लिए 3 उल्लिखित कार्यों के अनुक्रम को जानना चाहते हैं, तो गुणसूत्र के प्रत्येक जीन एक संख्या होगी जो एक अतिरिक्त संख्या के साथ एक निश्चित ऑपरेशन का प्रतिनिधित्व करता है। (कोई ऑपरेशन नहीं) और फिटनेस फ़ंक्शन दिए गए नंबर और प्रत्येक क्रोमोसोम (मिनट से) के लिए एक निश्चित क्रम में संचालन को लागू करने से प्राप्त संख्या के बीच पूर्ण अंतर होगा। आइए विचार करें कि पुनरावृत्तियों की संख्या (पीढ़ियों) कोई इष्टतम समाधान नहीं है और हमारे पास निकटतम संख्या 4 है (फिटनेस 1 के साथ), समस्या यह है कि हम 4 पर कोई ऑपरेशन लागू करने से 4 प्राप्त कर सकते हैं जबकि 5 के लिए हमें ज़रूरत है कई ऑपरेशन, तो निकट-इष्टतम समाधान समाधान के पास भी नहीं है।
तो, जीए इस तरह की समस्याओं के लिए उपयुक्त नहीं है? या सुझाया गया गुणसूत्र प्रतिनिधित्व और फिटनेस फ़ंक्शन पर्याप्त अच्छा नहीं है?
जवाब
अपने प्रश्न का अधिक सीधे उत्तर देने का प्रयास करने से पहले, मुझे कुछ स्पष्ट करने दें।
लोग अक्सर आनुवंशिक एल्गोरिदम (GAs) शब्द का उपयोग करते हैं , लेकिन, कई मामलों में, उनका वास्तव में क्या मतलब है विकासवादी एल्गोरिदम (ईएएस), जो जनसंख्या-आधारित का एक संग्रह है (अर्थात एक ही समय में कई समाधान बनाए जाते हैं) अनुकूलन एल्गोरिदम और दृष्टिकोण जो डार्विनवाद और योग्यतम के अस्तित्व से प्रेरित हैं । GA इन तरीकों में से एक है, जहां गुणसूत्र द्विआधारी हैं और आपके पास उत्परिवर्तन और क्रॉस-ओवर ऑपरेशन दोनों हैं। अन्य दृष्टिकोण हैं, जैसे कि विकास रणनीतियों या आनुवंशिक प्रोग्रामिंग ।
जैसा कि आपने भी देखा, ईएएस मेटा-सांख्यिकी हैं, और, हालांकि उनके अभिसरण गुणों [ 1 ] पर कुछ शोध हैं , व्यवहार में, वे अभिसरण नहीं कर सकते हैं। हालांकि, जब कोई अन्य संभावित दृष्टिकोण विफल हो गया है, तो ईएएस निश्चित रूप से उपयोगी हो सकता है।
आपके मामले में, समस्या वास्तव में एक फ़ंक्शन के बंद-प्रपत्र (या विश्लेषणात्मक ) अभिव्यक्ति को खोजने के लिए है, जो अन्य छोटे कार्यों से बना है। यह वास्तव में आनुवंशिक प्रोग्रामिंग (विशेष रूप से, पेड़-आधारित जीपी) के लिए बनाया गया था। वास्तव में, नुथ समस्या प्रतीकात्मक प्रतिगमन समस्या का एक विशेष उदाहरण है , जो कि जीपी पर लागू होने वाली एक विशिष्ट समस्या है। तो, जीपी संभवतः पहला दृष्टिकोण है जिसे आपको प्रयास करना चाहिए।
इस बीच, मैंने डीईएपी में एक सरल कार्यक्रम लागू किया है जो नूथ समस्या को हल करने की कोशिश करता है। इसे यहां देखें । सर्वोत्तम समाधान की फिटनेस जो इसे अब तक मिली है (कुछ बीज के साथ) 4 है और समाधान है floor(sqrt(float(sqrt(4))))(यहां floatबस एक फ्लोटिंग-पॉइंट संख्या में इनपुट को परिवर्तित करता है, प्रकार की सुरक्षा सुनिश्चित करने के लिए)। मैंने फिटनेस फ़ंक्शन के रूप में अंतर का उपयोग किया और प्रत्येक पीढ़ी के लिए 100 व्यक्तियों के साथ जीपी एल्गोरिथ्म चलाया (जो बहुत अधिक नहीं है!)। मैंने हाइपर-पैरामीटर्स को ज्यादा ट्विस्ट नहीं किया, इसलिए हो सकता है कि सही बीज और हाइपर-पैरामीटर्स के साथ, आप सही समाधान पा सकें।
अपनी चिंताओं को दूर करने के लिए, सिद्धांत रूप में, आप उस एन्कोडिंग का उपयोग कर सकते हैं, लेकिन, जैसा कि आप ध्यान दें, जीए वास्तव में वापस आ सकता है $4$ सबसे अच्छा समाधान के रूप में (जो वास्तव में उस से दूर नहीं है $5$), जो आप मेरी हत्या से बच सकते हैं, हर पीढ़ी में, किसी भी व्यक्ति के पास जो केवल मूल्य है।
मैंने अपने कार्यान्वयन और इस समस्या के बारे में सोचने में बहुत अधिक समय नहीं बिताया , लेकिन, जैसा कि मैंने ऊपर कहा, यहां तक कि आनुवंशिक प्रोग्रामिंग के साथ और केवल नूथ के संचालन का उपयोग करके, यह स्थानीय ऑप्टिमा में फंस सकता है। आप अन्य कार्यों, जैसे गुणा और जोड़, के साथ मेरे (या अपने) कार्यान्वयन को बढ़ाने की कोशिश कर सकते हैं और देखें कि क्या कुछ सुधार होता है।