Linear Proposal Operators and Stochastic Search Geometry in SOMA and Differential Evolution

कल्पना कीजिए कि आप पहाड़ियों, उभारों और छिपे हुए गड्ढों से भरी एक विशाल, धुंधली घाटी में सबसे निचले बिंदु को खोजने की कोशिश कर रहे हैं। आप पूरे मानचित्र को नहीं देख सकते, और आपके पास ऐसा कोई कंपास भी नहीं है जो "नीचे" की ओर इशारा करे। यह एक कंप्यूटर के लिए एक "ब्लैक-बॉक्स" अनुकूलन (optimization) समस्या को हल करने की दैनिक जीवन की स्थिति है। इसे करने के लिए, वैज्ञानिक विशेष प्रोग्रामों का उपयोग करते हैं जिन्हें इवोल्यूशनरी एल्गोरिदम (evolutionary algorithms) कहा जाता है। इन्हें डिजिटल पारिस्थितिक तंत्र (ecosystems) के रूप में सोचें जहाँ आभासी खोजकर्ताओं (explorers) की एक टीम (एक "जनसंख्या") घूमती है। वे केवल बेतरतीब ढंग से नहीं चलते; वे एक-दूसरे से सीखते हैं। कुछ खोजकर्ता "नेता" (वे जिन्होंने अब तक सबसे अच्छे स्थान खोजे हैं) होते हैं, और अन्य या तो उनकी ओर बढ़ने की कोशिश करते हैं, या कुछ भी बेहतर खोजने के लिए अन्य खोजकर्ताओं के रास्तों के साथ अपने रास्तों को मिलाते हैं। खोजकर्ताओं की दो प्रसिद्ध टीमें SOMA (सेल्फ-ऑर्गनाइजिंग माइग्रेटिंग एल्गोरिदम) और डिफरेंशियल इवोल्यूशन (DE) कहलाती हैं। वे काफी समय से मौजूद हैं, लेकिन उन्हें अक्सर स्वयं "ब्लैक बॉक्स" की तरह माना जाता है: हम जानते हैं कि वे काम करते हैं, लेकिन हम हमेशा यह पूरी तरह से नहीं समझ पाते कि वे अपने खोजकर्ताओं को चरण-दर-चरण कैसे घुमाते हैं।

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

"प्रपोजल" बनाम "जज" का जादू

कल्पना कीजिए कि आप एक खेल खेल रहे हैं जहाँ आपको 0 और 100 के बीच एक गुप्त संख्या का अनुमान लगाना है। आपके पास आपकी मदद के लिए दोस्तों की एक टीम है। पुराने तरीके में, पूरी प्रक्रिया एक धुंधली सी चीज़ है: एक दोस्त एक संख्या का सुझाव देता है, आप जाँचते हैं कि क्या वह सही है, शायद आप उसे बदलते हैं यदि वह बहुत अधिक है, और फिर आप तय करते हैं कि कौन खेल में बना रहेगा। यह बताना कठिन है कि एक दोस्त ने एक विशिष्ट संख्या का सुझाव क्यों दिया।

इस शोध पत्र के लेखकों ने महसूस किया कि यहाँ वास्तव में दो अलग-अलग चरण हो रहे हैं, और उन्हें अलग-अलग माना जाना चाहिए:

1. द प्रपोजल (The "What If"): एक मित्र अपनी स्थिति और सबसे अच्छे मित्र के स्थान के आधार पर एक नई संख्या का सुझाव देता है। यह चरण पूरी तरह से ज्यामितीय (geometric) है। यह एक मानचित्र पर रेखा खींचने जैसा है।
2. द सिलेक्शन (The "Judge"): आप सुझाव को देखते हैं और निर्णय लेते हैं, "क्या यह हमारे पास जो है उससे बेहतर है?" यह चरण विशिष्ट समस्या (फिटनेस) पर निर्भर करता है, और यह अव्यवस्थित और नॉन-लीनियर है।

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

कूद की ज्यामिति (The Geometry of the Jump)

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

इसे इस प्रकार सोचें: यदि आप बिंदु A पर खड़े हैं और आपका नेता बिंदु B पर है, तो एल्गोरिदम केवल यह अनुमान नहीं लगाता कि कहाँ जाना है। यह आपके और नेता के बीच एक सीधी रेखा खींचता है। फिर, यह उस रेखा पर एक स्थान चुनता है।

• इंटरपोलेशन (Interpolation): यह शायद आपके और नेता के बीच का आधा स्थान चुन सकता है।
• प्रोजेक्शन (Projection): यह ठीक उसी स्थान को चुन सकता है जहाँ नेता है।
• ओवरशूटिंग (Overshooting): यह नेता के पार एक स्थान चुन सकता है, जैसे कि वह बहुत तेज़ दौड़ रहा हो और उसे यह देखना हो कि नेता के पीछे क्या है।

शोध पत्र दिखाता है कि यह गति कुछ सरल बटनों (knobs) द्वारा नियंत्रित होती है:

• पाथ पैरामीटर ($t$): हम रेखा पर कितनी दूर तक जाते हैं?
• द मास्क (PRT या CR): यह धूप के चश्मे की तरह है जो कुछ दिशाओं में आपकी दृष्टि को रोकता है। यदि मास्क कहता है "उत्तर दिशा में आगे मत बढ़ो," तो खोजकर्ता केवल पूर्व, दक्षिण या पश्चिम में चलता है। यह एक "स्पार्स" (sparse) मूवमेंट बनाता है जहाँ एक समय में केवल कुछ ही निर्देशांक (coordinates) बदलते हैं।

मास्क को एक रैंडम कॉइन फ्लिप (बर्नौली डिस्ट्रीब्यूशन) मानकर, लेखक खोजकर्ता के औसत व्यवहार की गणना कर सके। उन्होंने इन चीजों के लिए सूत्र खोजे:

• औसतन, खोजकर्ता कितनी दूर कूदेगा?
• कूद में कितनी "फैलाव" (spread) या अनिश्चितता है?
• खोजकर्ता वास्तव में कितने दिशाओं (dimensions) में चलेगा?

उन्होंने यह भी खोजा कि "मास्क" (चश्मा) केवल दिशाओं को बेतरतीब ढंग से नहीं रोकता; यह अनिश्चितता का एक विशिष्ट आकार बनाता है। यदि मास्क की संभावना कम है, तो खोजकर्ता बहुत कम दिशाओं में चलता है। यदि संभावना अधिक है, तो वह कई दिशाओं में चलता है। सबसे अधिक "अराजक" (उच्चतम वेरिएंस) मूवमेंट तब होता है जब मास्क 50% पर सेट होता है, न कि जब यह पूरी तरह से खुला या पूरी तरह से बंद होता है।

बेहतर खोजकर्ता बनाना: नए वेरिएंट्स

एक बार जब लेखकों ने गति के पीछे के गणित को समझ लिया, तो वे केवल सिद्धांत तक ही सीमित नहीं रहे। उन्होंने इन सूत्रों का उपयोग SOMA एल्गोरिदम के तीन नए, बेहतर संस्करण बनाने के लिए किया।

1. जियोमेट्री-कंट्रोल्ड SOMA (GC-SOMA):
   कितनी दिशाओं में घूमना है इसका अनुमान लगाने के बजाय, यह संस्करण उपयोगकर्ता को यह कहने की अनुमति देता है, "मैं चाहता हूँ कि खोजकर्ता ठीक 5 दिशाओं में घूमे" या "मैं चाहता हूँ कि खोजकर्ता नेता के 90% तक पहुँचे।" एल्गोरिदम फिर उन विशिष्ट ज्यामितीय लक्ष्यों को प्राप्त करने के लिए आवश्यक सेटिंग्स (मास्क प्रोबेबिलिटी और पाथ लेंथ) का पता लगाने के लिए गणितीय सूत्रों का उपयोग करता है। यह एक कार को बताने जैसा है, "ठीक 50 मील चलो," और कार का कंप्यूटर यह पता लगाता है कि गैस पेडल को कितनी देर तक दबाना है।

2. रोटेशन-अवेयर SOMA (RA-SOMA):
   मानक एल्गोरिदम ग्रिड लाइनों (उत्तर, दक्षिण, पूर्व, पश्चिम) के साथ चलता है। लेकिन क्या होगा यदि घाटी झुकी हुई है? क्या होगा यदि सबसे अच्छा रास्ता तिरछा (diagonal) है? मानक एल्गोरिदम संघर्ष करता है क्योंकि वह सीधी ग्रिड लाइनों में चलने के लिए मजबूर है। RA-SOMA खोजकर्ताओं के पूरे समूह को देखता है, उस "आकार" को समझता है जिसमें वे घाटी में हैं, और उस आकार से मेल खाने के लिए अपनी गति को घुमाता (rotate) है। यह एक हाइकर (पर्वतारोही) की तरह है जो ग्रिड में चलना बंद कर देता है और इसके बजाय ढलान पर तिरछा चलता है क्योंकि उसे एहसास हुआ कि पहाड़ झुका हुआ है। यह एल्गोरिदम को जटिल, मुड़े हुए समस्याओं को हल करने में बहुत बेहतर बनाता है।

3. iL-SHOMA-RA:
   यह एक "सुपर-चार्ज्ड" संस्करण है जो रोटेशन ट्रिक को अन्य स्मार्ट फीचर्स के साथ जोड़ता है। यह याद रखता है कि अतीत में कौन से मूव्स ने अच्छा काम किया (सक्सेस-हिस्ट्री) और जैसे-जैसे यह समाधान के करीब पहुँचता है, यह खोजकर्ताओं की संख्या को धीरे-धीरे कम करता जाता है (पॉपुलेशन रिडक्शन)। यह एक खोज दल की तरह है जो 100 लोगों के साथ शुरू होता है, लेकिन जैसे-जैसे वे खजाने के करीब पहुँचते हैं, वे अधिकांश लोगों को घर भेज देते हैं और केवल सर्वश्रेष्ठ स्काउट्स को रखते हैं, जो अब सही दिशा में चल रहे हैं।

परिणाम: क्या वे वास्तव में काम करते हैं?

लेखकों ने इन नए खोजकर्ताओं का परीक्षण 24 अलग-अलग "घाटियों" (जिसे BBOB बेंचमार्क कहा जाता है) पर किया, जिनके अलग-अलग आकार और कठिनाइयाँ थीं। उन्होंने इनकी तुलना मूल SOMA और कुछ बेहतरीन डिफरेंशियल इवोल्यूशन एल्गोरिदम (जैसे iL-SHADE) के साथ की।

परिणाम स्पष्ट थे:

• मूल संस्करण पीछे है: मानक, बिना संशोधित SOMA आमतौर पर सबसे खराब प्रदर्शन करने वाला था। यह धीमा था और अक्सर फंस जाता था।
• नए संस्करण मजबूत हैं: तीनों नए संस्करण (GC-SOMA, RA-SOMA, और iL-SHOMA-RA) मूल से बहुत बेहतर थे।
• रोटेशन महत्वपूर्ण है: रोटेशन-अवेयर संस्करण कम-आयामी (low-dimensional) समस्याओं (जैसे 5 या 10 वेरिएबल्स) में स्टार था। इसने कुछ मामलों में सर्वश्रेष्ठ डिफरेंशियल इवोल्यूशन एल्गोरिदम को भी पछाड़ दिया। यह साबित करता है कि समस्या के आकार के अनुसार अपनी गति को "टिल्ट" करना एक बड़ा लाभ है।
• बजट मायने रखता है: "सुपर-चार्ज्ड" संस्करण (iL-SHOMA-RA) विशेष रूप से तब अच्छा था जब कंप्यूटर के पास बहुत कम समय (कम "बजट") था। इसने तेजी से अच्छे समाधान खोजे।
• यह कोई जादुई छड़ी नहीं है: हालाँकि, शोध पत्र सावधानी बरतते हुए कहता है कि इन नए तरीकों ने सब कुछ नहीं जीता। बहुत उच्च आयामों (20 वेरिएबल्स) में या कुछ प्रकार की समस्याओं पर, स्थापित डिफरेंशियल इवोल्यूशन एल्गोरिदम अभी भी बेहतर थे। नए तरीके सभी अनुकूलन (optimization) के लिए "हल किया गया" (solved) मामला नहीं हैं, लेकिन वे पुराने SOMA की तुलना में एक बड़ा सुधार हैं।

यह क्यों मायने रखता है

यह शोध पत्र महत्वपूर्ण है क्योंकि यह इन एल्गोरिदम के बारे में हमारी सोच को बदल देता है। लंबे समय तक, हमने उन्हें रहस्यमय ब्लैक बॉक्स के रूप में माना। यह पत्र उस बॉक्स को खोलता है और हमें इसके गियर दिखाता है। यह सिद्ध करता है कि इन एल्गोरिदम का "मूवमेंट" हिस्सा वास्तव में एक सरल, लीनियर मैथ ऑपरेशन है।

ज्यामिति को समझकर, हम अनुमान लगाना बंद कर सकते हैं और डिजाइन करना शुरू कर सकते हैं। हम एल्गोरिदम को ठीक बता सकते हैं कि उसे कैसे घूमना चाहिए, बजाय इसके कि केवल इस उम्मीद में रहें कि रैंडम सेटिंग्स काम कर जाएँगी। लेखकों ने दिखाया कि कूद के "आकार" (ज्यामिति) को नियंत्रित करके, हम इन एल्गोरिदम को बहुत अधिक कुशल बना सकते हैं।

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