💻 computer science

MO-ELA: Rigorously Expanding Exploratory Landscape Features for Automated Algorithm Selection in Continuous Multi-Objective Optimisation

यह शोध पत्र MO-ELA को प्रस्तुत करता है, जो पांच विशिष्ट श्रेणियों में निर्णय और उद्देश्य दोनों स्थानों से प्राप्त खोजपूर्ण परिदृश्य विशेषताओं (exploratory landscape features) का एक नया समूह है, जो समस्या की जटिलता को प्रभावी ढंग से पकड़कर और एल्गोरिदम के प्रदर्शन के बीच अंतर करके निरंतर बहु-उद्देश्यीय अनुकूलन (continuous multi-objective optimization) के लिए स्वचालित एल्गोरिदम चयन को महत्वपूर्ण रूप से बढ़ाता है।

मूल लेखक: Oliver Preuß, Jeroen Rook, Jakob Bossek, Heike Trautmann

प्रकाशित 2026-02-03

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

CC BY 4.0

मूल लेखक: Oliver Preuß, Jeroen Rook, Jakob Bossek, Heike Trautmann

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

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

यह ऑटोमेटेड एल्गोरिदम सिलेक्शन (AAS) की समस्या है। यह एक स्मार्ट 'सू-शेफ' (सहायक रसोइया) की तरह है जो आपकी सामग्रियों को देखता है और तुरंत बताता है, "इस विशिष्ट सामग्री के सेट के लिए, रेसिपी A का उपयोग करें, न कि रेसिपी B का।"

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

यह पेपर MO-ELA (मल्टी-ऑब्जेक्टिव एक्सप्लोरेटरी लैंडस्केप एनालिसिस) नामक उपकरणों का एक नया, सुपर-पावर्ड सेट पेश करता है, जो सू-शेफ को इन जटिल समस्याओं के परिदृश्य (लैंडस्केप) को स्पष्ट रूप से देखने में मदद करता है।

समस्या: एक धुंधली पर्वत श्रृंखला में रास्ता खोजना

एक मल्टी-ऑब्जेक्टिव समस्या को एक धुंधली पर्वत श्रृंखला के रूप में सोचें जहाँ आप उच्चतम शिखर (सर्वश्रेष्ठ समाधान) खोजने की कोशिश कर रहे हैं। हालाँकि, आपके पास दो परस्पर विरोधी लक्ष्य हैं: आप जितना संभव हो सके उतना ऊँचा होना चाहते हैं (एक ऑब्जेक्टिव को मैक्सिमाइज करना) और साथ ही एक विशिष्ट घाटी के जितना संभव हो सके उतना करीब रहना चाहते हैं (दूसरे को मिनिमाइज करना)।

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

समाधान: दूरबीन का एक नया सेट

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

डिसिजन स्पेस (Decision Space): जहाँ हाइकर खड़े हैं (इनपुट)।
ऑब्जेक्टिव स्पेस (Objective Space): हाइकर कितने ऊँचे हैं और घाटी के कितने करीब हैं (परिणाम)।

उन्होंने इस स्नैपशॉट का विश्लेषण करने के लिए पाँच अलग-अलग प्रकार के लेंस बनाए हैं:

"लेयर केक" लेंस (नॉन-डोमिनेटेड सॉर्टिंग): कल्पना कीजिए कि हाइकरों को परतों में छाँटना। सबसे ऊपरी परत में "सुपर-हाइकर्स" होते हैं जो कम से कम एक तरीके से बाकी सभी से बेहतर होते हैं। यह लेंस गिनता है कि कितनी परतें हैं और "सुपर-हाइकर्स" का वितरण कैसा है। यदि परतें सपाट और समान हैं, तो पहाड़ आसान है। यदि वे ऊबड़-खाबड़ और असमान हैं, तो पहाड़ कठिन है।
"स्टैटिस्टिकल स्नैपशॉट" लेंस: यह बस हाइकरों की सबसे ऊपरी परत का एक त्वरित गणितीय चेक लेता है। वे कितने फैले हुए हैं? क्या वे तालमेल में चलते हैं? यह देखने जैसा है कि समूह एक एकजुट टीम है या एक बिखरी हुई भीड़।
"शेप शिफ्टर" लेंस (PCA): यह लेंस 3D पहाड़ को 2D मानचित्र में सिकोड़ देता है ताकि मुख्य आकार देखा जा सके। यह पूछता है: "क्या पहाड़ एक लंबी कतार (रिज) है, एक गोल गुंबद है, या एक सपाट मैदान है?"
"स्ट्रिंग आर्ट" लेंस (ग्राफ स्ट्रक्चर): यह सबसे रचनात्मक हिस्सा है। कल्पना कीजिए कि हाइकरों को धागों से जोड़कर एक जाल बनाया गया है।
- वे धागे इस आधार पर खींचते हैं कि हाइकर डिसिजन स्पेस (जहाँ वे खड़े हैं) में कितने करीब हैं।
- फिर, वे उन्हीं धागों को ऑब्जेक्टिव स्पेस (जहाँ वे पहुँचते हैं) तक फैलाते हैं।
- जादू: यदि धागे तने हुए और सीधे रहते हैं, तो पहाड़ चिकना है। यदि धागे मुड़ जाते हैं, उलझ जाते हैं या आकार से बिगड़ जाते हैं, तो इसका मतलब है कि परिदृश्य भ्रामक और कठिन है। यह देखने जैसा है कि क्या एक नक्शा वास्तविक इलाके से मेल खाता है या नहीं।
"स्लोप" (ढलान) लेंस (ग्रेडिएंट): यह पहाड़ियों की ढलान को मापता है। क्या ढलान हल्की है, या अचानक खड़ी चट्टानें हैं?

प्रयोग: द ग्रेट टेस्ट ऑफ टेस्ट

इन नई दूरबीनों का परीक्षण करने के लिए, लेखकों ने एक बड़ा प्रयोग चलाया। उन्होंने 1,165 अलग-अलग "पर्वत श्रृंखलाएं" (बेंचमार्क समस्याएं) लीं और तीन अलग-अलग पर्वतारोही टीमों (एल्गोरिदम: NSGA-II, SMS-EMOA, और MOEA/D) को उन्हें जीतने की कोशिश करने दी।

उन्होंने पूछा: "क्या हमारी नई दूरबीनें भविष्यवाणी कर सकती हैं कि कौन सी टीम किस पहाड़ पर जीतेगी?"

परिणाम:

पुराना तरीका: नए उपकरणों के बिना, भविष्यवाणी ठीक थी, लेकिन अक्सर गलत भी थी।
नया तरीका: MO-ELA फीचर्स के साथ, "सू-शेफ" अविश्वसनीय रूप से सटीक हो गया। दो-लक्ष्य वाली समस्याओं के लिए, सिस्टम लगभग सटीक था, जो लगभग हर बार जीतने वाली टीम को चुन रहा था। तीन-लक्ष्य वाली समस्याओं के लिए भी, इसमें बहुत सुधार हुआ।
सबसे अच्छी बात: सिस्टम को सभी दूरबीनों की आवश्यकता नहीं थी। इसे पूरी तरह से काम करने के लिए केवल एक छोटा, विशिष्ट उपसमुच्चय (200+ फीचर्स में से लगभग 32) चाहिए था। यह साबित करता है कि नए उपकरण कुशल हैं और केवल "शोर" (नॉइज़) नहीं हैं।

यह क्यों महत्वपूर्ण है

यह पेपर दिखाता है कि जहाँ से आप शुरू करते हैं और जहाँ आप पहुँचते हैं—इन चतुर "स्ट्रिंग आर्ट" और "लेयर केक" तकनीकों का उपयोग करके—के बीच के संबंध को देखकर, आप बहुत जल्दी किसी समस्या की कठिनाई को समझ सकते हैं।

लेखकों ने पाया कि ये उपकरण स्थिर (stable) हैं (वे एक ही उत्तर देते हैं भले ही आप पहाड़ का थोड़ा अलग स्नैपशॉट लें) और अभिव्यंजक (expressive) हैं (वे बताते हैं कि वास्तव में क्या चीज़ किसी समस्या को कठिन बनाती है)।

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

तकनीकी सारांश: MO-ELA

समस्या विवरण

स्वचालित एल्गोरिदम चयन (Automated Algorithm Selection - AAS) एकल-उद्देश्य (single-objective - SO) अनुकूलन के लिए एक परिपक्व क्षेत्र है, जहाँ मशीन लर्निंग मॉडल "एक्सप्लोरेटरी लैंडस्केप एनालिसिस" (exploratory landscape analysis - ELA) विशेषताओं के आधार पर किसी विशिष्ट समस्या इंस्टेंस के लिए सबसे अच्छा प्रदर्शन करने वाले एल्गोरिदम की भविष्यवाणी करते हैं। हालाँकि, निरंतर बहु-उद्देश्य (multi-objective - MO) अनुकूलन के डोमेन में, उपलब्ध विशेषताओं का परिदृश्य विरल (sparse) है। मौजूदा दृष्टिकोण अक्सर प्रत्येक उद्देश्य के लिए व्यक्तिगत रूप से SO विशेषताओं की गणना करने पर निर्भर करते हैं, जो उद्देश्यों के बीच जटिल अंतःक्रियाओं (interactions) को पकड़ने में विफल रहते हैं, या बाधित (constrained) MO विशेषताओं पर निर्भर करते हैं जो सीधे तौर पर अनबाधित (box-constrained) निरंतर बहु-उद्देश्य समस्याओं पर लागू नहीं होते हैं। बॉक्स-कन्स्ट्रेंड निरंतर बहु-उद्देश्य अनुकूलन समस्याओं (MOPs) के परिदृश्य को चित्रित करने के लिए विशेष रूप से डिज़ाइन किए गए एक कठोर, पूरक विशेषताओं के सेट की आवश्यकता है ताकि AAS प्रदर्शन में सुधार किया जा सके।

कार्यप्रणाली (Methodology)

लेखक MO-ELA का प्रस्ताव करते हैं, जो द्वि-उद्देश्य (bi-objective) के लिए 226 और त्रि-उद्देश्य (tri-objective) समस्याओं के लिए 233 विशेषताओं का एक नया सेट है। ये विशेषताएँ निर्णय (decision) और उद्देश्य (objective) दोनों स्थानों में बिंदुओं के यादृच्छिक नमूने (random sample) से प्राप्त की जाती हैं, जिसमें प्रभुत्व संबंधों (dominance relationships) और विभिन्न संरचनात्मक विश्लेषणों का उपयोग किया जाता है। इन विशेषताओं को पांच अलग-अलग समूहों में वर्गीकृत किया गया है:

नॉन-डोमिनेटेड सॉर्टिंग (NDS) आधारित विशेषताएँ:
- नमूने को परतों ( $L_1, L_2, \dots$ ) में विभाजित करने के लिए नॉन-डोमिनेटेड सॉर्टिंग प्रक्रिया (NSGA-II से प्रेरित) का उपयोग करता है।
- परतों की संख्या, परतों की संख्या और प्रति परत औसत बिंदुओं जैसे मेट्रिक्स की गणना करता है।
- प्रथम पाँच परतों के लिए हाइपरवॉल्यूम (HV) और सोलो-पोलास्की (SP) मापों की गणना करता है।
- परतों के माध्यम से HV मानों पर गैर-रैखिकता (non-linearity) को पकड़ने के लिए बहुपद प्रतिगमन (polynomial regressions - डिग्री 1–4) को फिट करता है, जिसमें $R^2$ का उपयोग एक विशेषता के रूप में किया जाता है।
नॉन-डोमिनेटेड बिंदुओं के वर्णनात्मक सांख्यिकी (Descriptive Statistics):
- प्रथम नॉन-डोमिनेटेड परत ( $L_1$ ) के उद्देश्य वेक्टर्स पर सांख्यिकीय मापों (min, max, avg, std) को लागू करता है।
- इसमें उद्देश्यों के बीच युग्मवार स्पियरमैन सहसंबंध (pairwise Spearman correlations) और द्वि-उद्देश्य मामलों के लिए मानक विचलन (standard deviations) के पूर्ण अंतर को शामिल किया गया है।
PCA-आधारित विशेषताएँ:
- तीन सेटों पर प्रिंसिपल कंपोनेंट एनालिसिस (PCA) करता है: निर्णय स्थान के बिंदु ( $X$ ), उद्देश्य स्थान के बिंदु ( $Y$ ), और नॉन-डोमिनेटेड परत का संयोजित सेट ($XY$)।
- इन सेटों के प्रिंसिपल कंपोनेंट्स से न्यूनतम, अधिकतम और औसत समझाया गया विचरण (explained variance) निकालता है।
ग्राफ-आधारित विशेषताएँ:
- निर्णय और उद्देश्य स्थानों में नॉन-डोमिनेटेड परत $L_1$ के आधार पर ग्राफ बनाता है।
- MST और kNN ग्राफ: निर्णय स्थान ( $G_D$ ) और उद्देश्य स्थान ( $G_O$ ) में मिनिमम स्पैनिंग ट्री (MST) और k-निकटतम पड़ोसी (kNN) ग्राफ ( $k=1$ ) बनाता है।
- एज ट्रांसफर (Edge Transfer): एक ग्राफ की एज संरचना को दूसरे पर स्थानांतरित करता है (जैसे, निर्णय स्थान से MST एडजेस को उद्देश्य बिंदुओं पर लागू करना, जिसे $G_{D \to O}$ कहा जाता है)।
- मेट्रिक्स: एज वेट्स (दूरी), नोड क्लोजनेस सेंट्रलिटी, जुड़े हुए नोड्स के बीच कोण, और कनेक्टेड कंपोनेंट्स के गुणों (कंपोनेंट्स की संख्या, प्रति कंपोनेंट नोड्स, सबसे लंबा पथ) की गणना करता है।
- स्थानों के बीच विरूपण (distortion) को पकड़ने के लिए निर्णय और उद्देश्य स्थान के ग्राफ के बीच विशेषताओं के अनुपात को शामिल करता है।
ग्रेडिएंट-आधारित विशेषताएँ:
- ऑब्जेक्टिव स्पेस के MST ( $G^O_{ST}$ ) में जुड़े हुए नोड्स के बीच पूर्ण प्रति-चर ढलान (per-variable slopes) की गणना करता है।
- इन ढलानों को सभी उद्देश्यों और एडजेस में एकत्रित करके एक मल्टी-ऑब्जेक्टिव ग्रेडिएंट वेक्टर बनाता है, जिससे min, max, std और औसत मान निकाले जाते हैं।

प्रायोगिक सेटअप (Experimental Setup):

बेंचमार्क्स: BiObjBBOB, ZDT, DTLZ, और MPM2 से प्राप्त 1,165 समस्या इंस्टेंस का एक व्यापक सेट, जो 2 और 3 उद्देश्यों और आयाम $d \in \{2, 5, 10, 20\}$ को कवर करता है।
एल्गोरिदम: तीन सॉल्वर (NSGA-II, SMS-EMOA, MOEA/D) को प्रति इंस्टेंस 20 बार चलाया गया।
AAS फ्रेमवर्क: मशीन लर्निंग मॉडल (SVM, XGBoost, Random Forest) को सर्वश्रेष्ठ सॉल्वर की भविष्यवाणी करने के लिए प्रशिक्षित किया गया। सबसे प्रभावशाली उपसमूह (subset) की पहचान करने के लिए फीचर चयन 'फॉरवर्ड-बैकवर्ड एग्जॉस्टिव सर्च' का उपयोग करके किया गया।
मेट्रिक्स: प्रदर्शन का मूल्यांकन नॉर्मलाइज्ड हाइपरवॉल्यूम (HVN) और सिंगल बेस्ट सॉल्वर (SBS) तथा वर्चुअल बेस्ट सॉल्वर (VBS) के बीच के अंतर को कम करने में रिलेटिव इम्प्रूवमेंट (RI) का उपयोग करके किया गया।

मुख्य परिणाम

एल्गोरिदम चयन प्रदर्शन: प्रस्तावित विशेषताओं ने AAS प्रदर्शन में महत्वपूर्ण सुधार किया। द्वि-उद्देश्य समस्याओं के लिए, सर्वश्रेष्ठ सेलेक्टर (फीचर चयन के साथ XGBoost) ने एक RI 0.963 प्राप्त किया, जो प्रभावी रूप से VBS के अंतर को पाट देता है। त्रि-उद्देश्य समस्याओं के लिए, एक RI 0.272 प्राप्त किया गया।
विशेषता योगदान (Feature Contribution): फीचर चयन के बाद, नए प्रस्तावित MO-ELA फीचर्स अक्सर शीर्ष योगदानकर्ताओं में शामिल थे।
- द्वि-उद्देश्य समस्याओं के लिए, 32 चयनित विशेषताओं में से 14 नई थीं (NDS विशेषताओं का वर्चस्व था)।
- त्रि-उद्देश्य समस्याओं के लिए, 36 चयनित विशेषताओं में से 17 नई थीं (kNN ग्राफ विशेषताओं का वर्चस्व था)।
विशेषता स्थिरता (Feature Stability): विशेषताओं ने विभिन्न यादृच्छिक नमूनों और नमूना आकारों के बीच उच्च स्थिरता प्रदर्शित की, सभी विशेषताओं के लिए औसत युग्मवार सहसंबंध (pairwise correlations) ~0.8 और चयनित उपसमूह के लिए लगभग 1.0 रहा।
विशेषता अभिव्यक्ति (Feature Expressiveness): चयनित विशेषताओं ने निम्न आपसी सहसंबंध (द्वि-उद्देश्य के लिए औसत ~0.30, त्रि-उद्देश्य के लिए ~0.23) दिखाया, जो इंगित करता है कि वे समस्या के परिदृश्य के विभिन्न पहलुओं को पकड़ते हैं।
नमूना आकार संवेदनशीलता (Sample Size Sensitivity): आयाम 5, 10, और 20 के लिए 500 का नमूना आकार सर्वोत्तम परिणाम देता है। आयाम 2 के लिए, 200 का नमूना आकार इष्टतम था। उल्लेखनीय रूप से, बड़े नमूना आकार ने सॉल्वर रन के शेष बजट में कमी होने के बावजूद प्रदर्शन में सुधार किया, जिससे पता चलता है कि फीचर अभिव्यक्ति (feature expressiveness) महत्वपूर्ण है।

महत्व और दावे

यह पेपर दावा करता है कि MO-EDA निरंतर बहु-उद्देश्य अनुकूलन के लिए एक्सप्लोरेटरी लैंडस्केप फीचर्स का एक कठोर विस्तार प्रदान करता है। इसका प्राथमिक महत्व निम्नलिखित है:

अंतराल को भरना: यह विशेषताओं की कमी को दूर करता है और उद्देश्यों के बीच की अंतःक्रियाओं और निर्णय एवं उद्देश्य दोनों स्थानों की ज्यामिति को कैप्चर करने वाले एक व्यापक सेट को पेश करता है।
प्रमाणित उपयोगिता: ये विशेषताएँ केवल सैद्धांतिक नहीं हैं; वे अनुभवजन्य रूप से मशीन लर्निंग मॉडल को समस्या इंस्टेंस के बीच अंतर करने और लगभग इष्टतम सटीकता (द्वि-उद्देश्य मामलों के लिए VBS के करीब) के साथ एल्गोरिदम चुनने में सक्षम बनाती हैं।
पूरकता (Complementarity): नए फीचर्स मौजूदा MO-ELA फीचर्स (Liefooghe et al., 2021 से) के पूरक हैं, क्योंकि फीचर चयन लगातार दोनों के मिश्रण को बनाए रखता है, जो बताता है कि विभिन्न फीचर समूह परिदृश्य के विभिन्न आवश्यक गुणों को कैप्चर करते हैं।
व्यावहारिकता: ये विशेषताएँ अपेक्षाकृत छोटे नमूना आकारों (जैसे, 200–500 बिंदु) के साथ भी स्थिर और प्रभावी हैं, जिससे वे व्यावहारिक अनुप्रयोग के लिए व्यवहार्य हो जाती हैं जहाँ कंप्यूटेशनल बजट सीमित होता है।

लेखक निष्कर्ष निकालते हैं कि हालांकि यह शोध प्रारंभिक चरण में है, ये विशेषताएँ समस्या की संरचना के बारे में सार्थक अंतर्दृष्टि प्रदान करती हैं और निरंतर बहु-उद्देश्य अनुकूलन के लिए स्वचालित एल्गोरिदम चयन के अत्याधुनिक स्तर (state-of-the-art) को महत्वपूर्ण रूप से बढ़ाती हैं।