यूनिट परीक्षण अनुमान एल्गोरिदम

Question

मैं आधार के रूप में कुछ लोकप्रिय पायथन पैकेजों का उपयोग करके ग्राफ और नेटवर्क के लिए ओपन-सोर्स सन्निकेशन एल्गोरिदम लाइब्रेरी पर काम कर रहा हूं। मुख्य लक्ष्य ग्राफ और नेटवर्क पर एनपी-पूर्ण समस्याओं के लिए अप-टू-डेट सन्निकटन एल्गोरिदम शामिल करना है। इसका कारण 1 है) मैंने एक अच्छा (आधुनिक) समेकित पैकेज नहीं देखा है जो इसे कवर करता है और 2) यह एनपी-हार्ड अनुकूलन समस्याओं पर सन्निकटन एल्गोरिदम के बारे में सीखने के लिए एक अच्छा शैक्षिक उपकरण होगा।

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

इकाई परीक्षण अनुमान एल्गोरिदम का सबसे अच्छा तरीका क्या होगा? यादृच्छिक उदाहरण उत्पन्न करें और सुनिश्चित करें कि लौटाए गए परिणाम एल्गोरिदम द्वारा गारंटीकृत सीमा से कम हैं? ऐसा लगता है कि झूठी सकारात्मकताएं होती हैं (परीक्षण उस समय भाग्यशाली हो गया है, सभी मामलों के लिए बाध्य होने की गारंटी नहीं है)।

Answer 1

आपको यहां दो चिंताओं को अलग करने की आवश्यकता है। आपके सन्निकटन एल्गोरिदम की गुणवत्ता और उन एल्गोरिदम के कार्यान्वयन की शुद्धता।

अनुमानित एल्गोरिदम की गुणवत्ता का परीक्षण आमतौर पर सॉफ्टवेयर विकास में उपयोग की जाने वाली यूनिट परीक्षण विधियों को उधार नहीं देगा। उदाहरण के लिए आपको यादृच्छिक समस्याएं उत्पन्न करने की आवश्यकता होगी जो वास्तविक समस्याओं के प्रतिनिधि हैं। असुरक्षित बड़े उदाहरणों के लिए आपके एल्गोरिदम की गुणवत्ता का न्याय करने के लिए आपको कुछ ऊपरी/निचले बाउंड प्राप्त करने के लिए गणितीय कार्य करने की आवश्यकता हो सकती है। या समस्या परीक्षण सेट का उपयोग करें जो ज्ञात या सर्वोत्तम ज्ञात समाधान हैं और अपने परिणामों की तुलना करें। लेकिन किसी भी मामले में यूनिट परीक्षण आपको सन्निकटन एल्गोरिदम की गुणवत्ता में सुधार करने में बहुत मदद नहीं करेगा। यह वह जगह है जहां अनुकूलन और गणित में आपका डोमेन ज्ञान मदद करेगा।

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

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

Answer 2

उत्पादित समाधान की वैधता की जांच करना पहला पहला कदम है।

इसके अतिरिक्त, हमले का एक कोण regression testing उदाहरणों का उपयोग करके अनुमानित अनुमानित समाधान ज्ञात हो सकता है (उदाहरण के लिए हाथ से एल्गोरिदम निष्पादित करके या किसी अन्य एल्गोरिदम के किसी अन्य कार्यान्वयन का उपयोग करके प्राप्त किया जाता है)।

टीएसपी जैसी समस्याओं के लिए TSPLIB जैसे ज्ञात (इष्टतम) समाधानों के साथ समस्या उदाहरणों के भंडार भी मौजूद हैं। शायद इन्हें कुछ उपयोग में लाया जा सकता है।

यदि प्रश्न में एल्गोरिदम के लिए ऊपरी सीमाएं ज्ञात हैं, तो कई यादृच्छिक उदाहरण उत्पन्न करना और ऊपरी सीमाओं के खिलाफ हेरिस्टिक समाधानों को सत्यापित करना उपयोगी साबित हो सकता है। यदि आप ऐसा करते हैं, तो मैं आपको आग को पुन: उत्पन्न करने के लिए आग्रह करता हूं (उदाहरण के लिए हमेशा एक ही यादृच्छिक संख्या जनरेटर और बीज का उपयोग करके)।

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

Answer 3

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

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