A gravity search algorithm with a distance-fitness evaluation strategy for path planning

कंप्यूटर विज्ञान की दुनिया में, उन समस्याओं के लिए सबसे अच्छा संभव समाधान खोजने का एक निरंतर संघर्ष रहता है जिनमें एक-एक करके जांचने के लिए बहुत अधिक चर (variables) होते हैं। कल्पना कीजिए कि आप पहाड़ियों और घाटियों से भरे एक विशाल, धुंधले परिदृश्य में सबसे निचले बिंदु को खोजने की कोशिश कर रहे हैं। आप पूरे मानचित्र को नहीं देख सकते, और आप हर एक रास्ते पर चल भी नहीं सकते। इसे हल करने के लिए, वैज्ञानिकों ने "स्वार्म इंटेलिजेंस" (झुंड बुद्धि) एल्गोरिदम विकसित किए हैं, जो इस बात की नकल करते हैं कि कैसे जानवरों के समूह, जैसे पक्षी या चींटियाँ, भोजन खोजने या घोंसले बनाने के लिए मिलकर काम करते हैं। ऐसा ही एक तरीका "ग्रेविटी सर्च एल्गोरिदम" (गुरुत्वाकर्षण खोज एल्गोरिदम) है। यह प्रत्येक संभावित समाधान को द्रव्यमान वाले एक कण के रूप में मानता है। जिस तरह ग्रह गुरुत्वाकर्षण के माध्यम से एक-दूसरे को खींचते हैं, ये कण भी एक-दूसरे को खींचते हैं। एक कण जितना भारी होगा—अर्थात उसका समाधान जितना बेहतर होगा—उसका खिंचाव उतना ही मजबूत होगा। समय के साथ, कणों का पूरा समूह सबसे भारी, सबसे आशाजनक समाधान की ओर बढ़ता है, इस उम्मीद में कि वे धुंध में छिपे पूर्णतः सर्वोत्तम उत्तर को खोज लेंगे।

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

टीम ने, जिसका नेतृत्व झिचाओ फेंग, जियान सुई और झेनझेन लुओ ने किया, एक नया संस्करण विकसित किया जिसे वे SDGSA कहते हैं। उनके सुधार का मूल आधार कणों के व्यवहार के दो विशिष्ट परिवर्तनों में निहित है। सबसे पहले, उन्होंने "गुरुत्वाकर्षण" को ही समायोजित किया। मूल पद्धति में, कणों के बीच खिंचाव की शक्ति एक निश्चित, अनुमानित दर पर कम होती है। नई टीम ने इस क्षय दर को लचीला बनाया। खोज के शुरुआती चरणों में, जब कण अभी अज्ञात का पता लगा रहे होते हैं, तो खिंचाव धीरे-धीरे कम होता है, जिससे उन्हें दूर-दूर तक घूमने की अनुमति मिलती है। जैसे-जैसे खोज आगे बढ़ती है और कण समाधान के करीब पहुँचते हैं, खिंचाव तेजी से कम होता है, जो उन्हें सबसे आशाजनक क्षेत्रों पर तीव्रता से ध्यान केंद्रित करने के लिए प्रोत्साहित करता है। यह गतिशील समायोजन समूह को बहुत जल्दी निष्कर्ष पर पहुँचने या उत्तर के करीब होने पर बिना किसी उद्देश्य के भटकने में समय बर्बाद करने से रोकता है।

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

यह परीक्षण करने के लिए कि क्या ये परिवर्तन वास्तव में काम करते हैं, शोधकर्ताओं ने अपने नए एल्गोरिदम को कठोर परीक्षणों की एक श्रृंखला से गुजारा। उन्होंने सरल वक्रों से लेकर अत्यधिक उलझे हुए, बहु-आयामी पहेलियों तक, अट्ठावन अलग-अलग जटिल गणितीय समस्याओं का उपयोग किया। उन्होंने अपने नए SDGSA की तुलना मूल ग्रेविटी सर्च पद्धति और वैज्ञानिकों और इंजीनियरों द्वारा आज उपयोग किए जाने वाले ग्यारह अन्य लोकप्रिय अनुकूलन एल्गोरिदम से की। परिणाम स्पष्ट थे। इन परीक्षणों के विशाल बहुमत में, नए एल्गोरिदम ने अपने प्रतिस्पर्धियों की तुलना में बेहतर समाधान खोजे। यह उन स्थानीय जालों से बचने में विशेष रूप से प्रभावी था जिन्होंने पुराने तरीकों को परेशान किया था। कई मामलों में, इसने वास्तविक सर्वोत्तम उत्तर को खोज निकाला जहाँ अन्य एल्गोरिदम केवल एक 'अच्छे' उत्तर पर ही रुक गए थे। डेटा ने दिखाया कि नया तरीका न केवल अधिक सटीक था बल्कि अधिक कुशल भी था, जो कम कम्प्यूटेशनल चरणों के साथ इन उच्च-गुणवत्ता वाले समाधानों तक पहुँच गया।

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

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

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