अमीबा के साथ तंत्रिका नेटवर्क ने 8 शहरों के लिए यात्रा सेल्समैन समस्या को हल किया

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

टोक्यो में कीओ विश्वविद्यालय के जापानी शोधकर्ताओं के एक समूह ने दिखाया कि अमीबा यात्रा विक्रेता समस्या के रूप में ज्ञात एक आश्चर्यजनक रूप से जटिल गणितीय समस्या के लगभग समाधान उत्पन्न करने में सक्षम है ।

सेल्समैन का कार्य सबसे प्रसिद्ध दहनशील अनुकूलन कार्यों में से एक है, जिसमें सबसे अधिक लाभदायक मार्ग ढूंढना शामिल है जो इन शहरों से कम से कम एक बार गुजरता है और फिर मूल शहर में लौटता है।

समस्या का अनुकूलन कथन एनपी-कठिन समस्याओं के वर्ग से संबंधित है, हालांकि, इसके अधिकांश विशेष मामलों की तरह। "निर्णय समस्या" का संस्करण (अर्थात, वह प्रश्न जिसमें यह सवाल उठाया गया है कि क्या मार्ग k के दिए गए मान से अधिक समय तक मौजूद नहीं है) NP- पूर्ण समस्याओं के वर्ग से संबंधित है।

सही समाधान की गणना करने की कठिनाई तेजी से बढ़ जाती है क्योंकि कार्य में अधिक शहरों को जोड़ा जाता है। उदाहरण के लिए, चार शहरों के लिए तीन समाधान हैं, और छह शहरों के लिए - 360. भविष्य में, घातीय वृद्धि जारी है।

महान कम्प्यूटेशनल जटिलता के बावजूद, बड़ी संख्या में हेयूरिस्टिक और सटीक एल्गोरिदम हैं जो कुछ मामलों को पूरी तरह से हजारों शहरों के साथ हल कर सकते हैं, और यहां तक ​​कि लाखों शहरों की समस्याओं को 0.05% के भीतर अनुमानित किया जा सकता है । संकेतित लिंक में नेशनल जियोग्राफिकल सोसाइटी के आधार से पृथ्वी के 1,904,711 शहरों को हल करने के प्रयास शामिल हैं।


1,904,711 शहरों की नेशनल जियोग्राफिकल सोसाइटी का आधार

फिलहाल, पृथ्वी के शहरों के लिए न्यूनतम दूरी का रिकॉर्ड 7 515 772 107 किमी है, इसे 13 मार्च, 2018 को हेरीस्टिक एलकेएच एल्गोरिथ्म का उपयोग करके सेट किया गया था।

कंप्यूटर विज्ञान में क्लासिक विक्रेता समस्या का उपयोग अनुकूलन एल्गोरिदम के लिए एक बेंचमार्क के रूप में किया जाता है।

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


एक वैज्ञानिक लेख के अनुसार, Physarum polycephalum नामक एक अमीबा, जो पहले कई अन्य प्रयोगों में जैविक कंप्यूटर के रूप में इस्तेमाल किया गया था, प्रयोगों में भाग लिया। यह जीव जैविक कंप्यूटिंग में विशेष रूप से उपयोगी माना जाता है क्योंकि यह भोजन प्राप्त करने के लिए अधिक कुशल तरीके की तलाश में अपने शरीर के विभिन्न क्षेत्रों का विस्तार कर सकता है, और यह प्रकाश से नफरत करता है।

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

यात्रा सेल्समैन की समस्या का अनुकरण करने के लिए, प्लेट पर 64 चैनलों में से प्रत्येक को 1 से 8 की संख्या के अलावा ए और एच के बीच एक शहर कोड सौंपा गया था, जो शहरों के आदेश को इंगित करता है (शहरों का क्रम उस क्रम से मेल खाता है जिसमें वे विक्रेता द्वारा गए थे)।

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

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

वैज्ञानिक लेख 19 दिसंबर, 2018 को रॉयल सोसाइटी ओपन साइंस (doi: 10.1098 / rsos.180396) पत्रिका में प्रकाशित हुआ था।