💻 computer science

Speeding Up the NSGA-II via Dynamic Population Sizes

यह शोध पत्र एक गतिशील NSGA-II संस्करण प्रस्तुत करता है जो अपने जनसंख्या आकार को अनुकूल रूप से बढ़ाता है, जिससे बेंचमार्क समस्याओं पर स्थिर संस्करण की तुलना में काफी तेज़ सैद्धांतिक रनटाइम प्राप्त होता है और यह प्रदर्शित करता है कि एक समवर्ती-रन (concurrent-run) रणनीति आगे चलकर एक पैरामीटर-रहित एल्गोरिदम बना सकती है जो स्थिर NSGA-II की तुलना में $\tilde\Omega(n)$ के कारक से बेहतर प्रदर्शन करती है।

मूल लेखक: Benjamin Doerr, Martin S. Krejca, Simon Wietheger

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

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

CC BY 4.0

मूल लेखक: Benjamin Doerr, Martin S. Krejca, Simon Wietheger

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

कल्पना कीजिए कि आप दो परस्पर विरोधी लक्ष्यों के बीच एक आदर्श संतुलन खोजने की कोशिश कर रहे हैं, जैसे कि एक ऐसी कार बनाने की कोशिश करना जो सबसे तेज़ भी हो और सबसे अधिक ईंधन-कुशल (fuel-efficient) भी। वास्तविक दुनिया में, आप आमतौर पर दोनों को पूर्ण रूप से प्राप्त नहीं कर सकते; एक को सुधारने से अक्सर दूसरे को नुकसान पहुँचता है। एक "सर्वश्रेष्ठ" कार खोजने के बजाय, आप व्यापार-संतुलन (trade-offs) का एक पूरा मेन्यू चाहते हैं (जैसे, "सुपर फास्ट लेकिन बहुत तेल पीने वाली," "संतुलित," "धीमी लेकिन बेहद कुशल")। इस मेन्यू को पारेटो फ्रंट (Pareto Front) कहा जाता है।

इस मेन्यू को खोजने के लिए, कंप्यूटर वैज्ञानिक एक उपकरण का उपयोग करते हैं जिसे इवोल्यूशनरी एल्गोरिदम (Evolutionary Algorithm) कहते हैं। इस एल्गोरिदम को एक डिजिटल प्रजनन कार्यक्रम (breeding program) के रूप में समझें। यह यादृच्छिक कार डिजाइनों की एक आबादी से शुरू होता है, उन्हें विकसित करता है, उनमें उत्परिवर्तन (mutation) लाता है, और अगली पीढ़ी बनाने के लिए सबसे अच्छे डिजाइनों को रखता है।

समस्या: "बहुत अधिक, बहुत जल्दी" की दुविधा

इस टूल का क्लासिक संस्करण, जिसे NSGA-II कहा जाता है, एक पेचीदा समस्या का सामना करता है:

जनसंख्या का आकार (The Population Size): मेन्यू के सभी अलग-अलग विकल्पों को खोजने के लिए, आपको उम्मीदवारों के एक बड़े समूह (जनसंख्या) की आवश्यकता होती है। यदि आपका समूह बहुत छोटा है, तो आप कुछ विकल्पों को छोड़ सकते हैं।
गति (The Speed): हालाँकि, एक विशाल समूह में हर एक कार की जाँच करने में बहुत समय लगता है। यदि आप एक बहुत बड़े समूह के साथ शुरुआत करते हैं, तो एल्गोरिदम शुरुआत से ही धीमा हो जाता है।

यह एक साथ 100 बेहतरीन व्यंजनों (recipes) को खोजने जैसा है। यदि आप एक साथ 10,000 व्यंजन पकाने की कोशिश करते हैं, तो आप पहला कोर्स खत्म करने से पहले ही थककर हार जाएंगे। लेकिन यदि आप केवल 5 व्यंजन पकाते हैं, तो आप शायद बेहतरीन मिठाई को भी मिस कर देंगे।

समाधान: "डायनामिक" दृष्टिकोण

इस शोध पत्र के लेखक इस एल्गोरिदम को चलाने का एक स्मार्ट तरीका प्रस्तावित करते हैं, जिसे वे Dynamic NSGA-II कहते हैं।

शुरुआत में एक निश्चित समूह आकार चुनने और उसी पर टिके रहने के बजाय, वे छोटी शुरुआत करने और फिर बढ़ने का सुझाव देते हैं।

उपमा (The Analogy): कल्पना कीजिए कि आप एक रहस्य सुलझाने की कोशिश कर रहे हैं एक जासूस हैं।
- पुराना तरीका (Static NSGA-II): आप तुरंत 1,000 जासूसों की एक विशाल टीम काम पर रखते हैं। आप पहले दिन से ही उन सभी को भुगतान करते हैं। यह महंगा और धीमा है क्योंकि आपको उन सभी को प्रबंधित करना पड़ता है, भले ही शुरुआत में सुराग सरल हों।
- नया तरीका (Dynamic NSGA-II): आप केवल 4 जासूसों के साथ शुरुआत करते हैं। वे कुछ समय तक काम करते हैं। यदि उन्होंने अभी तक रहस्य नहीं सुलझाया है, तो आप अपनी टीम को दुगना कर देते हैं (8 कर देते हैं)। वे कुछ समय तक काम करते हैं। यदि फिर भी हल नहीं हुआ, तो आप इसे फिर से दुगना करते हैं (16 कर देते हैं)। आप तब तक टीम का आकार बढ़ाते रहते हैं जब तक कि आपके पास सभी सुरागों को कवर करने के लिए पर्याप्त लोग न हों, लेकिन आप तब तक एक विशाल टीम के लिए भुगतान नहीं करते जब तक कि आपको इसकी वास्तव में आवश्यकता न हो।

उन्होंने इसका परीक्षण कैसे किया

शोधकर्ताओं ने इस "बढ़ती हुई टीम" की रणनीति का परीक्षण दो विशिष्ट पहेली प्रकारों (benchmarks) पर किया:

"OneMinOneMax" पहेली: यह लाल और नीले मार्बल्स (कंचों) के हर संभव संयोजन को खोजने जैसा है।
- परिणाम: डायनामिक संस्करण पारंपरिक स्टैटिक संस्करण ( $O(n^2 \log n)$ ) की तुलना में बहुत तेज़ था (गणितीय रूप से, यह $O(n \log^2 n)$ था)। इसने व्यापार-संतुलन के पूरे मेन्यू को काफी तेज़ी से खोजा।
"Jump" पहेली: यह एक कठिन पहेली है जहाँ समाधान खराब विकल्पों की एक "घाटी" के पीछे छिपा होता है। आपको अच्छे समाधानों तक पहुँचने के लिए एक बड़ी छलांग लगानी पड़ती है।
- परिणाम: फिर से, डायनामिक संस्करण स्टैटिक संस्करण ($O(nk+1) $) की तुलना में तेज़ ($ O(nk \log^2 n)$) था।

"लॉन्गर स्टार्ट" अपग्रेड

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

उपमा: जासूसों की टीम को हर घंटे दोगुना करने के बजाय, वे छोटी टीम को बुनियादी बातें सही करने के लिए लंबे समय तक काम करने देते हैं, फिर दोगुना करना शुरू करते हैं। यह और भी तेज़ साबित हुआ, जो लगभग इस प्रकार की समस्या के लिए सैद्धांतिक गति सीमा के करीब पहुँच गया।

"नो-सेटिंग्स" संस्करण

इस नए तरीके का एक नुकसान यह है कि आपको कंप्यूटर को यह बताना होगा कि टीम को कब दोगुना करना है (जैसे, "100 घंटों के काम के बाद टीम को दोगुना करें")। यदि आप गलत समय चुनते हैं, तो यह उतना अच्छा काम नहीं कर सकता है।

इसे ठीक करने के लिए, उन्होंने एक "कन्करेंट रन" (Concurrent Run) रणनीति बनाई:

उपमा: एक जासूस टीम को काम पर रखने और उसके बढ़ने का अनुमान लगाने के बजाय, आप एक साथ कई टीमें काम पर रखते हैं।
- टीम A, हर 10 मिनट में दोगुनी होती है।
- टीम B, हर 20 मिनट में दोगुनी होती है।
- टीम C, हर 40 मिनट में दोगुनी होती है।
- आप उन सभी को एक साथ चलाते हैं लेकिन काम साझा करते हैं। जो टीम पहले काम पूरा करती है, वही जीतती है।
परिणाम: यह उपयोगकर्ता को समय का अनुमान लगाने की आवश्यकता को समाप्त कर देता है। एल्गोरिदम "पैरामीटर-लेस" (आपको सेटिंग्स को ट्यून करने की आवश्यकता नहीं है) बन जाता है, और यह अभी भी अविश्वसनीय रूप से तेज़ है—परफेक्टली ट्यून किए गए संस्करण से थोड़ा ही धीमा है, लेकिन पुराने स्टैटिक मेथड की तुलना में बहुत तेज़ है।

दावों का सारांश

तेज़ (Faster): डायनामिक विधि पारंपरिक विधि की तुलना में परीक्षण किए गए कार्यों के लिए सर्वोत्तम ट्रेड-ऑफ बहुत तेज़ी से खोजती है।
मजबूत (Robust): यह तब भी अच्छा काम करता है जब आप सही "डबलिंग टाइम" नहीं चुनते हैं।
स्वचालित (Automatic): आप बिना किसी सेटिंग को ट्यून किए इसे चलाने के लिए एक साथ कई संस्करण चला सकते हैं।
दायरा (Scope): ये परिणाम विशिष्ट कंप्यूटर विज्ञान पहेलियों (OneMinOneMax और OneJumpZeroJump) के लिए गणितीय प्रमाण हैं। यह शोध पत्र यह दावा नहीं करता है कि ये परिणाम वास्तविक दुनिया के चिकित्सा निदान, वित्तीय व्यापार या अन्य विशिष्ट उद्योगों पर लागू होते हैं; यह पूरी तरह से एल्गोरिदम की सैद्धांतिक गति पर केंद्रित है।

तकनीकी सारांश: डायनेमिक पॉपुलेशन साइज के माध्यम से NSGA-II की गति बढ़ाना

समस्या विवरण
मल्टी-ऑब्जेक्टिव इवोल्यूशनरी एल्गोरिदम (MOEAs), विशेष रूप से नॉन-डोमिनेटेड सॉर्टिंग जेनेटिक एल्गोरिदम II (NSGA-II), मल्टी-ऑब्जेक्टिव ऑप्टिमाइजेशन समस्याओं को हल करने के लिए व्यापक रूप से उपयोग किए जाते हैं। उनके अनुप्रयोग में एक केंद्रीय चुनौती जनसंख्या आकार ( $N$ ) का प्रबंधन करना है। पारेटो फ्रंट (इष्टतम ट्रेड-ऑफ का सेट) को प्रभावी ढंग से प्रदर्शित करने के लिए, जनसंख्या पर्याप्त रूप से बड़ी होनी चाहिए। हालांकि, एक बड़ी जनसंख्या एल्गोरिदम को धीमा कर देती है क्योंकि NSGA-II प्रत्येक इटरेशन में $N$ समाधानों का मूल्यांकन करता है। यह एक डिज़ाइन दुविधा पैदा करता है: एक जनसंख्या जो बहुत छोटी है, पारेटो फ्रंट को कुशलतापूर्वक कवर करने में विफल रहती है, जबकि एक जनसंख्या जो बहुत बड़ी है, अनावश्यक कम्प्यूटेशनल लागत का कारण बनती है। हालिया गणितीय विश्लेषणों ने दिखाया है कि एक इष्टतम निश्चित जनसंख्या आकार के साथ स्टेटिक NSGA-II का रनटाइम वनमिनमैक्स (OneMinMax - OMM) बेंचमार्क पर $\Theta(n^2 \log n)$ है, जिसे कुछ श्रेणियों के एल्गोरिदम के लिए सैद्धांतिक निचली सीमाओं की तुलना में उप-इष्टतम माना जाता है।

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

एल्गोरिदम संरचना: एल्गोरिदम $N=4$ की जनसंख्या आकार के साथ शुरू होता है। यह एक उपयोगकर्ता-निर्दिष्ट पैरामीटर $\tau$ द्वारा दर्शाए गए निश्चित संख्या में फंक्शन इवैल्यूएशन (function evaluations) करता है, जिसके बाद जनसंख्या आकार को दोगुना करने का प्रयास किया जाता है। यह दोहरीकरण तब तक जारी रहता है जब तक कि एक उपयोगकर्ता-निर्धारित अधिकतम जनसंख्या आकार, $N_{max}$ , तक नहीं पहुँच जाता। महत्वपूर्ण रूप से, दोहरीकरण वर्तमान जनसंख्या आकार के बजाय फंक्शन इवैल्यूएशन की संख्या द्वारा ट्रिगर किया जाता है, जिससे यह सुनिश्चित होता है कि एल्गोरिदम के प्रत्येक "फेज" को वर्तमान जनसंख्या आकार की परवाह किए बिना लगभग समान कम्प्यूटेशनल बजट प्राप्त हो।
चयन तंत्र (Selection Mechanism): लेखक एक विशिष्ट NSGA-II संस्करण का उपयोग करते हैं जो टाई-ब्रेकिंग के लिए करंट क्राउडिंग डिस्टेंस (current crowding distance) का उपयोग करता है। यह तंत्र, जिसे पहले समाधान वितरण में सुधार के लिए दिखाया गया है, न्यूनतम क्राउडिंग डिस्टेंस वाले व्यक्तियों को पुनरावर्ती रूप से हटाता है और दूरियों की पुनर्गणना करता है, जिससे समाधानों का अधिक समदूरस्थ प्रसार (equidistant spread) होता है।
संस्करण:
1. स्टैंडर्ड डायनेमिक NSGA-II: प्रत्येक $\tau$ इवैल्यूएशन के बाद जनसंख्या को दोगुना करता है।
2. लॉन्गर इनिशियल फेज के साथ डायनेमिक NSGA-II: प्रारंभिक चरण (जहाँ $N=4$ है) की अवधि को सभी आगामी चरणों के कुल कम्प्यूटेशनल बजट से मेल खाने के लिए बढ़ा देता है। यह एल्गोरिदम को बिना एसिम्प्टोटिक रनटाइम ऑर्डर बढ़ाए अत्यधिक कुशल प्रारंभिक चरण में अधिक समय बिताने की अनुमति देता है।
3. पैरामीटर-लेस रणनीति (एल्गोरिदम 3): $\tau$ के लिए मैनुअल ट्यूनिंग की आवश्यकता को हटाने के लिए, लेखक एक कंकरेंट-रन (concurrent-run) रणनीति का प्रस्ताव करते हैं। यह फ्रेमवर्क अलग-अलग $\tau$ मानों (दो की घातों) के साथ डायनेमिक NSGA-II के कई इंस्टेंस लॉन्च करता है और गतिशील रूप से उस इंस्टेंस को संसाधन आवंटित करता है जिसने अब तक सबसे कम कुल कम्प्यूटेशनल प्रयास खर्च किया है।

प्रमुख योगदान और परिणाम
पेपर दो मानक बेंचमार्क: वनमिनमैक्स (OMM) और वनजम्पजीरोजम्प (OJZJ $_k$ ) पर प्रस्तावित एल्गोरिदम के लिए कठोर गणितीय रनटाइम विश्लेषण प्रदान करता है।

OMM बेंचमार्क:
- इष्टतम $\tau$ के साथ स्टैंडर्ड डायनेमिक NSGA-II उच्च संभावना के साथ $O(n \log^2 n)$ फंक्शन इवैल्यूएशन का रनटाइम प्राप्त करता है। यह स्टेटिक NSGA-II के $\Theta(n^2 \log n)$ रनटाइम की तुलना में एक महत्वपूर्ण सुधार है।
- लॉन्गर इनिशियल फेज वाला वेरिएंट $O(n \log n)$ का रनटाइम प्राप्त करता है। यह अनबायस्ड ब्लैक-बॉक्स एल्गोरिदम के एक बड़े वर्ग के लिए एसिम्प्टोटिक रूप से इष्टतम है, जो ऑल-ओन्स स्ट्रिंग खोजने के लिए सैद्धांतिक निचली सीमा से मेल खाता है।
- पैरामीटर-लेस कंकरेंट रणनीति $O(n \log^3 n)$ (स्टैंडर्ड) और $O(n \log(N_{max}) \log(n \log N_{max}))$ (लॉन्गर इनिशियल फेज) के रनटाइम प्राप्त करती है, जो इष्टतम रूप से ट्यून किए गए संस्करणों की तुलना में केवल एक लॉगरिदमिक फैक्टर का दंड (penalty) लेती है।
OJZJ $_k$ बेंचमार्क (गैप साइज $k$ के साथ):
- स्टैंडर्ड डायनेमिक NSGA-II $O(nk \log^2 n)$ का रनटाइम प्राप्त करता है, जो स्टेटिक NSGA-II के ज्ञात $\Theta(nk+1)$ रनटाइम में सुधार करता है।
- लॉन्गर इनिशियल फेज वाला वेरिएंट $O(nk \log n)$ प्राप्त करता है।
- पैरामीटर-लेस रणनीति क्रमशः $O(kn^k \log^3 n)$ और $O(kn^k \log(N_{max}) \log(nk \log N_{max}))$ के रनटाइम प्रदान करती है।
मजबूती और पैरामीटर स्वतंत्रता:
- डायनेमिक वेरिएंट्स के लिए रनटाइम गारंटी अधिकतम जनसंख्या आकार $N_{max}$ से काफी हद तक स्वतंत्र है, बशर्ते कि $N_{max}$ , पारेटो फ्रंट के आकार से थोड़ा बड़ा हो (जैसे, $N_{max} \ge n+4$ )।
- यदि $\tau$ को उप-इष्टतम (बहुत छोटा) चुना जाता है, तो एल्गोरिदम $N_{max}$ जनसंख्या आकार वाले स्टेटिक NSGA-II के प्रदर्शन पर वापस आ जाता है, जिससे यह सुनिश्चित होता है कि एक खराब पैरामीटर चयन विनाशकारी नहीं होगा।
- कंकरेंट-रन रणनीति प्रभावी रूप से उपयोगकर्ता को $\tau$ चुनने की आवश्यकता को समाप्त करती है, जिससे एक "पैरामीटर-लेस" एल्गोरिदम बनता है।

महत्व और दावे
लेखकों का दावा है कि यह कार्य डायनेमिक पैरामीटर्स वाले MOEA का गणितीय विश्लेषण करने वाला पहला कार्य है, जो यह प्रदर्शित करता है कि समस्याओं की मल्टी-ऑब्जेक्टिव प्रकृति जनसंख्या वृद्धि रणनीतियों के माध्यम से महत्वपूर्ण गति-वृद्धि (speed-ups) की अनुमति देती है।

सैद्धांतिक प्रगति: पेपर स्थापित करता है कि डायनेमिक जनसंख्या साइजिंग NSGA-II के लिए $\Theta(n^2 \log n)$ बाधा को तोड़ सकता है, जिससे OMM पर $O(n \log^2 n)$ रनटाइम प्राप्त होता है। लॉन्गर इनिशियल फेज को विस्तारित करने पर यह लगभग इष्टतम ( $O(n \log n)$ ) रनटाइम प्राप्त करता है।
व्यावहारिक निहितार्थ: यह दिखाकर कि एक सरल कंकरेंट-रन रणनीति मैनुअल पैरामीटर ट्यूनिंग के बिना निकट-इष्टतम प्रदर्शन प्राप्त कर सकती है, लेखक एक अधिक मजबूत, "पैरामीटर-लेस" MOEAs की ओर एक मार्ग का सुझाव देते हैं।
आर्काइव्स के साथ तुलना: लेखक उल्लेख करते हैं कि जबकि अन्य कार्यों ने समाधानों को संग्रहीत करने और छोटी आबादी की अनुमति देने के लिए आर्काइव्स का उपयोग करने का प्रस्ताव दिया है, उनका डायनेमिक दृष्टिकोण कुछ संदर्भों में (विशेष रूप से क्रॉसओवर के बिना बिट-वाइज म्यूटेशन के संबंध में) सैद्धांतिक रूप से बेहतर है क्योंकि यह इस जोखिम से बचता है कि जनसंख्या पारेटो फ्रंट पर नए समाधान उत्पन्न करने के लिए अपर्याप्त हो जाएगी।

पेपर निष्कर्ष निकालता है कि डायनेमिक NSGA-II स्टेटिक NSGA-II की तुलना में $\tilde{\Omega}(n)$ का प्रमाणित स्पीड-अप प्रदान करता है और प्रारंभिक चरण को और अधिक विस्तारित करने से प्रदर्शन सैद्धांतिक सीमाओं तक सुधर जाता है। भविष्य के कार्य के लिए यह जांचना सुझाया गया है कि क्या ये लाभ अन्य लोकप्रिय परिदृश्यों, जैसे कि LOTZ बेंचमार्क के लिए भी लागू होते हैं।