🔢 mathematics

Benchmarking Optimization Algorithms with Quality Profiles and Test Set Profiles

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

मूल लेखक: G. Fasano, C. Piermarini, M. Roma

प्रकाशित 2026-07-21✓ Author reviewed ⓘ

📖 5 मिनट में पढ़ें🧠 गहराई से पढ़ें

CC BY 4.0

मूल लेखक: G. Fasano, C. Piermarini, M. Roma

मूल पेपर CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) के तहत लाइसेंस किया गया है। ✨ नीचे दिए गए पेपर की यह व्याख्या AI से तैयार की गई है। इसे लेखकों ने नहीं लिखा है। तकनीकी सटीकता के लिए मूल पेपर देखें। पूरा डिस्क्लेमर पढ़ें

कल्पना कीजिए कि आप एक कोच हैं जो यह पता लगाने की कोशिश कर रहे हैं कि आपका कौन सा एथलीट सबसे अच्छा धावक है। आप केवल इस बात की परवाह नहीं करते कि कौन दौड़ सबसे पहले पूरी करता है; आप इस बात की भी परवाह करते हैं कि उन्होंने दौड़ कैसे पूरी की। क्या वे सटीक फॉर्म के साथ फिनिश लाइन की ओर स्प्रिंट करते हुए आए, या वे लड़खड़ाते हुए और मुश्किल से खड़े रहने की स्थिति में फिनिश लाइन पार कर गए? कंप्यूटर विज्ञान की दुनिया में, विशेष रूप से ऑप्टिमाइज़ेशन (optimization) नामक एक क्षेत्र में, एल्गोरिदम ही एथलीट होते हैं। उनका काम एक जटिल गणितीय समस्या का "सर्वश्रेष्ठ" उत्तर खोजना है, जैसे कि एक पहाड़ी परिदृश्य में सबसे निचले बिंदु को खोजना। पारंपरिक रूप से, कोच (शोधकर्ता) मुख्य रूप से यह देखने के लिए धावकों का समय देखते हैं कि वे कितने तेज़ हैं (दक्षता/efficiency) या उन्होंने कितनी बार सफलतापूर्वक दौड़ पूरी की (विश्वसनीयता/reliability)। लेकिन क्या होगा यदि दो धावक अलग-अलग स्थानों पर समाप्त करते हैं? एक बिल्कुल नीचे (पूर्ण उत्तर) पर हो सकता है, जबकि दूसरा ढलान पर थोड़ा ऊपर हो सकता है। यदि आप केवल समय देखते हैं, तो आप इस तथ्य को अनदेखा कर सकते हैं कि एक धावक ने वास्तव में बहुत बेहतर स्थान खोज लिया था। यह वह पहेली है जिसे यह शोध पत्र हल करता है: हम उन धावकों की निष्पक्ष तुलना कैसे करें जो अंततः अलग-अलग स्थानों पर पहुँचते हैं, और हम यह कैसे जान सकते हैं कि हमारा रेस ट्रैक (समस्याओं का सेट जो हम उन्हें देते हैं) वास्तव में एक अच्छा परीक्षण है?

लेखक, जियोवानी फासानो, क्रिश्चियन पियरमारिनी और मैसिमो रोमा, इसे हल करने के लिए दो नए उपकरण पेश करते हैं: क्वालिटी प्रोफाइल्स (Quality Profiles) और टेस्ट सेट प्रोफाइल्स (Test Set Profiles)। सोचिए कि क्वालिटी प्रोफाइल्स एक विशेष स्कोरबोर्ड की तरह है जो केवल गति को नहीं मापता, बल्कि यह भी मापता है कि प्रत्येक एल्गोरिदम "पूर्ण उत्तर के कितने करीब" पहुँचा। यह यह नहीं पूछता कि, "इसमें कितना समय लगा?", बल्कि यह पूछता है, "यह समाधान शुरुआती बिंदु से कितना बेहतर है?" यह शोधकर्ताओं को विवरणों पर ज़ूम करने की अनुमति देता है, यह देखने के लिए कि कौन सा एल्गोरिदम लगातार गणितीय परिदृश्य में सबसे गहरी घाटियाँ खोजता है, भले ही वे वहां तक पहुँचने के लिए अलग-अलग रास्ते अपनाते हों। यह महत्वपूर्ण है क्योंकि कभी-कभी सबसे तेज़ एल्गोरिदम वह नहीं होता है जो सबसे अच्छा उत्तर खोजता है।

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

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

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

तकनीकी सारांश: क्वालिटी प्रोफाइल्स और टेस्ट सेट प्रोफाइल्स के साथ अनुकूलन एल्गोरिदम का बेंचमार्किंग

समस्या विवरण
अनुकूलन एल्गोरिदम (optimization algorithms) का बेंचमार्किंग एक महत्वपूर्ण चुनौती प्रस्तुत करता है, विशेष रूप से उन सॉल्वर की तुलना करने में जो एक परीक्षण सेट (test set) पर अलग-अलग समाधान बिंदुओं पर अभिसरित (converge) हो सकते हैं। मौजूदा बेंचमार्किंग उपकरण, जैसे कि परफॉरमेंस प्रोफाइल्स (डोलन और मोरे) और डेटा प्रोफाइल्स (मोरे और वाइल्ड), मुख्य रूप से दक्षता (कंप्यूटेशनल प्रयास) और विश्वसनीयता (सफलता दर) पर ध्यान केंद्रित करते हैं। जबकि परफॉरमेंस प्रोफाइल्स अभिसरण प्रयास (जैसे, CPU समय, इटरेशन) को मापने के लिए मानक हैं, वे अक्सर उन समस्याओं को बाहर कर देते हैं जहाँ सॉल्वर अलग-अलग समाधानों पर अभिसरित होते हैं ताकि कम्प्यूटेशनल बोझ की निष्पक्ष तुलना सुनिश्चित की जा सके। फलस्वरूप, उन उपकरणों की कमी है जो विशेष रूप से विभिन्न सॉल्वरों द्वारा प्राप्त अंतिम ऑब्जेक्टिव फंक्शन मानों की गुणवत्ता (सटीकता) का आकलन करने और तुलना करने के लिए डिज़ाइन किए गए हैं, विशेष रूप से उन परिदृश्यों में जहाँ सटीक विधियों (exact methods) और ह्यूरिस्टिक्स (heuristics) की तुलना की जाती है, या जहाँ सॉल्वर अलग-अलग स्थानीय मिनिमा (local minima) पर अभिसरित होते हैं। इसके अलावा, साहित्य ने बेंचमार्क किए जा रहे सॉल्वरों के संबंध में टेस्ट सेट की उपयुक्तता और निरंतरता का मात्रात्मक रूप से आकलन करने पर सीमित ध्यान दिया है।

कार्यप्रणाली
लेखक दो नवीन ग्राफिकल उपकरण प्रस्तावित करते हैं: क्वालिटी प्रोफाइल्स (Quality Profiles) और टेस्ट सेट प्रोफाइल्स (Test Set Profiles)।

क्वालिटी प्रोफाइल्स:
- परिभाषा: सॉल्वरों के एक सेट $S$ और परीक्षण समस्याओं $P$ के लिए, एक क्वालिटी प्रोफाइल $Q_s(\tau)$ उन समस्याओं के अनुपात को दर्शाता है जहाँ एक सॉल्वर $s$ एक विशिष्ट सटीकता सीमा $\tau$ के भीतर समाधान प्राप्त करता है। सटीकता को एक संदर्भ मान $f_L^{(p)}$ (आमतौर पर सेट में किसी भी सॉल्वर द्वारा पाया गया सर्वश्रेष्ठ समाधान) और एक प्रारंभिक बिंदु $x_0^{(p)}$ के सापेक्ष मापा जाता है।
- मुख्य असमानता: प्रोफाइल का निर्माण इस असमानता के आधार पर किया जाता है:
  $f_s^{(p)}(x^*) - f_L^{(p)} \leq \tau [f^{(p)}(x_0^{(p)}) - f_L^{(p)}]$
  जहाँ $\tau \in [0, 1]$ है।
- कमजोर बनाम मजबूत (Weak vs. Strong): "कमजोर" (Weak) प्रोफाइल सामान्यीकरण (normalization) में प्रारंभिक बिंदु $x_0^{(p)}$ का उपयोग करते हैं, जबकि "मजबूत" (Strong) प्रोफाइल सबसे खराब समाधान का उपयोग करते हैं जो सॉल्वरों द्वारा पाया गया हो।
- विज़ुअलाइज़ेशन संवर्द्धन: घनीभूत ट्रैक्स (closely packed tracks) के बीच अंतर करने की कठिनाई को दूर करने के लिए, लेखक स्केलिंग पैरामीटर $r_1$ और $r_2$ पेश करते हैं। ये एब्सीसा (शुद्धता/precision) और ऑर्डिनेट (समस्याओं का प्रतिशत) अक्षों के गैर-रैखिक संपीड़न (compression) या विस्तार (expansion) की अनुमति देते हैं। यह डेटा को हटाए बिना विशिष्ट सटीकता श्रेणियों (जैसे, $\tau=0$ के पास उच्च परिशुद्धता) में ज़ूम करने की सुविधा देता है।
- गुणधर्म: प्रोफाइल्स को ऑब्जेक्टिव फंक्शन के सुसंगत एफाइन ट्रांसफॉर्मेशन (affine transformations) के तहत अपरिवर्तनीय (invariant) सिद्ध किया गया है और वे गैर-घटते (non-decreasing) हैं। परफॉरमेंस प्रोफाइल्स के विपरीत, इनके लिए पूर्व-निर्धारित पैरामीटर पहचान की आवश्यकता नहीं है जो पूर्वाग्रह (bias) उत्पन्न कर सकती है, हालांकि वे प्रति सॉल्वर एक निश्चित कम्प्यूटेशनल बजट (स्टॉपिंग क्राइटेरियन) पर निर्भर करते हैं।
टेस्ट सेट प्रोफाइल्स:
- उद्देश्य: बेंचमार्किंग निष्कर्षों की मजबूती और टेस्ट सेट $P$ की निरंतरता का आकलन करना।
- कार्यप्रणाली: यह उपकरण एक बूटस्ट्रैपिंग तकनीक लागू करता है। यह कई उपसमुच्चयों $\hat{P}$ को उत्पन्न करने के लिए टेस्ट सेट $P$ से बार-बार रिसैंपलिंग (प्रतिस्थापन के साथ) करता है। प्रत्येक उपसमुच्चय के लिए क्वालिटी प्रोफाइल्स की गणना की जाती है।
- आउटपुट: बूटस्ट्रैप चक्रों में क्वालिटी प्रोफाइल मानों का विचरण (variance) $\sigma_s^2(\tau)$ को $\tau$ के विरुद्ध प्लॉट किया जाता है। कम विचरण यह दर्शाता है कि सॉल्वर की रैंकिंग और प्रदर्शन टेस्ट सेट की संरचना में परिवर्तनों के प्रति मजबूत है, जबकि उच्च विचरण यह सुझाव देता है कि बेंचमार्किंग निष्कर्ष चुने गए विशिष्ट समस्याओं के प्रति संवेदनशील हैं।

प्रमुख योगदान

नवीन बेंचमार्किंग टूल: क्वालिटी प्रोफाइल्स की शुरूआत सॉल्वरों की तुलना करने के लिए एक नियतात्मक (deterministic) प्रक्रिया प्रदान करती है जो कम्प्यूटेशनल प्रयास के बजाय समाधान की सटीकता पर आधारित है। यह उन समस्याओं को शामिल करने की अनुमति देता है जहाँ सॉल्वर अलग-अलग समाधानों पर अभिसरित होते हैं, जिन्हें आमतौर पर परफॉरमेंस प्रोफाइल तुलनाओं से बाहर रखा जाता है।
पूरक प्रकृति: लेखक क्वालिटी प्रोफाइल्स को परफॉरमेंस या डेटा प्रोफाइल्स के विकल्प के रूप में नहीं, बल्कि एक पूरक उपकरण के रूप में देखते हैं। वे समाधान की गुणवत्ता का एक संक्षिप्त ग्राफिकल प्रतिनिधित्व प्रदान करके साहित्य के अंतराल को भरते हैं, जो सटीक विधियों के साथ ह्यूरिस्टिक्स की तुलना करने के लिए विशेष रूप से उपयोगी है।
टेस्ट सेट डायग्नोस्टिक्स: टेस्ट सेट प्रोफाइल्स का परिचय एक मात्रात्मक, पोस्ट-हॉक विधि प्रदान करता है जिसका उपयोग टेस्ट सेट की विश्वसनीयता और विभेदक शक्ति (discriminative power) का मूल्यांकन करने के लिए किया जाता है, जो बेंचमार्किंग के एक ऐसे आयाम को संबोधित करता है जिसे अक्सर अनदेखा किया जाता है।
विज़ुअलाइज़ेशन में लचीलापन: स्केलिंग पैरामीटर्स ( $r_1, r_2$ ) और सेमिलॉगैरिद्मिक स्केल का उपयोग सटीकता के विभिन्न क्रमों (orders of magnitude) में सॉल्वर के प्रदर्शन के विस्तृत विश्लेषण की अनुमति देता है, जो एक ऐसी विशेषता है जिसे मानक परफॉरमेंस या डेटा प्रोफाइल्स में आसानी से विस्तारित नहीं किया जा सकता है।

परिणाम
पेपर टूल्स को मान्य करने के लिए व्यापक संख्यात्मक प्रयोग प्रस्तुत करता है:

स्मूथ ऑप्टिमाइज़ेशन (Smooth Optimization):
- 166 CUTEst समस्याओं पर चार बड़े पैमाने के अनकन्स्ट्रेंड सॉल्वर्स (L-BFGS, CG+, TRON, CG DESCENT) की तुलना में, क्वालिटी प्रोफाइल्स ने खुलासा किया कि TRON ने निम्न-से-मध्यम सटीकता अंतराल में अन्य की तुलना में बेहतर प्रदर्शन किया, जबकि CG+ ने थोड़ी बेहतर मजबूती (कम विफलताओं) दिखाई। स्केलिंग पैरामीटर्स ( $r_1 > 1$ ) को उच्च-सटीकता वाले क्षेत्रों में सॉल्वर के बीच अंतर करने के लिए आवश्यक दिखाया गया था जहाँ ट्रैक अन्यथा अविभेदित थे।
- दूसरा प्रयोग विभिन्न नेगेटिव कर्वेचर डायरेक्शन रणनीतियों के साथ ट्रंकेटेड न्यूटन (Truncated Newton) विधियों की तुलना करता है। क्वालिटी प्रोफाइल्स ने प्रभावी ढंग से हाइलाइट किया कि TN-NC3 रणनीति (पहला नेगेटिव आइगेनवैल्यू चुनना) सबसे प्रभावी थी, जो सैद्धांतिक अपेक्षाओं की पुष्टि करती है और एल्गोरिथम की विशिष्ट विशेषताओं को मापने की टूल की क्षमता को प्रदर्शित करती है।
डेरिवेटिव-फ्री ऑप्टिमाइज़ेशन (Derivative-Free Optimization):
- लेखकों ने 145 समस्याओं पर सात डेरिवेटिव-फ्री सॉल्वर्स (NEWUOA, Nelder-Mead और पैटर्न सर्च विधियों सहित) पर क्वालिटी प्रोफाइल्स लागू किए।
- प्रयोगों ने डेटा प्रोफाइल्स के साथ पूरकता की पुष्टि की: जहाँ डेटा प्रोफाइल्स निश्चित सटीकता के लिए कम्प्यूटेशनल बजट बनाम प्रदर्शन दिखाते हैं, वहीं क्वालिटी प्रोफाइल्स निश्चित कम्प्यूटेशनल बजट के लिए प्रदर्शन बनाम सटीकता दिखाते हैं।
- प्रयोगों ने पुष्टि की कि मॉडल-आधारित विधियाँ (NEWUOA) पैटर्न-सर्च विधियों की तुलना में सामान्यतः उच्च सटीकता प्रदान करती हैं, भले ही बजट मध्यम हो, और स्केलिंग पैरामीटर्स इन अंतरों को विज़ुअलाइज़ करने के लिए महत्वपूर्ण हैं।
टेस्ट सेट विश्लेषण:
- सिंथेटिक डेटा और टेस्ट सेट की कार्डिनैलिटी ( $|P|$ ) को बदलकर, टेस्ट सेट प्रोफाइल्स ने दिखाया कि छोटे टेस्ट सेट सॉल्वर की रैंकिंग में उच्च विचरण की ओर ले जाते हैं, जो टेस्ट सेट की संरचना के प्रति बेंचमार्किंग की संवेदनशीलता की पुष्टि करता है।

महत्व और दावे
लेखक दावा करते हैं कि क्वालिटी प्रोफाइल्स और टेस्ट सेट प्रोफाइल्स सॉल्वर के व्यवहार की अधिक पूर्ण तस्वीर प्रदान करके बेंचमार्किंग प्रक्रिया को बेहतर बनाते हैं। विशेष रूप से:

वे उन एल्गोरिदम की तुलना करने की अनुमति देते हैं जो अलग-अलग समाधानों पर अभिसरित होते हैं, एक ऐसा परिदृश्य जहाँ पारंपरिक परफॉरमेंस प्रोफाइल्स अक्सर अपर्याप्त होते हैं या जिनमें डेटा को बाहर करने की आवश्यकता होती है।
वे सॉल्वर की मजबूती के "दूसरे पक्ष" का आकलन करने का एक तरीका प्रदान करते हैं: टेस्ट सेट की स्वयं की उपयुक्तता।
दृष्टिकोण रचनात्मक (constructive) है न कि एक्सिओमैटिक (axiomatic); यह रैंकिंग में विरोधाभासों (जैसे Liu et al. द्वारा चर्चा किए गए) को हल करने का दावा नहीं करता है, बल्कि प्रदर्शन के एक विशिष्ट आयाम (समाधान की गुणवत्ता) को मापने के लिए एक व्यावहारिक, डेटा-संचालित उपकरण प्रदान करता है।
ये उपकरण डेरिवेटिव-फ्री और ब्लैक-बॉक्स ऑप्टिमाइज़ेशन में विशेष रूप से मूल्यवान हैं, जहाँ फंक्शन इवैल्यूएशन के निश्चित बजट आम हैं, और समाधान की गुणवत्ता प्राथमिक मेट्रिक है।

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

इसी तरह के और पेपर