कण झुंड एल्गोरिथम

परिचय

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







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



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



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

Boids

बर्ड ने 1986 में एक कंप्यूटर मॉडल बनाने के लिए क्रेग रेनॉल्ड्स को प्रेरित किया, जिसे उन्होंने Boids कहा। पक्षियों के झुंड के व्यवहार का अनुकरण करने के लिए, रेनॉल्ड्स ने उनमें से प्रत्येक के व्यवहार को व्यक्तिगत रूप से, साथ ही साथ उनकी बातचीत को भी प्रोग्राम किया। उन्होंने तीन सरल सिद्धांतों का इस्तेमाल किया। सबसे पहले, प्रत्येक मॉडल ने अपने मॉडल में अन्य पक्षियों के साथ टकराव से बचने की मांग की। दूसरे, प्रत्येक पक्षी उसी दिशा में चला गया जैसे पास के पक्षी। तीसरे, पक्षियों ने एक दूसरे से समान दूरी पर जाने की मांग की।



पहले सिमुलेशन के परिणामों ने रचनाकार को खुद को आश्चर्यचकित किया: कार्यक्रम में अंतर्निहित एल्गोरिदम की सादगी के बावजूद, स्क्रीन पर झुंड बेहद विश्वसनीय लग रहा था। पक्षी समूहों में घूमते थे, टकराव से बचते थे, और यहां तक ​​कि बेतरतीब ढंग से असली लोगों की तरह दौड़ते थे।

कंप्यूटर ग्राफिक्स के विशेषज्ञ के रूप में, क्रेग रेनॉल्ड्स मुख्य रूप से उनके द्वारा बनाए गए सिमुलेशन के परिणामों के दृश्य पक्ष में रुचि रखते थे। हालाँकि, Boids पर एक लेख में, उन्होंने यह भी कहा कि उनके द्वारा विकसित व्यवहार मॉडल को अतिरिक्त कारकों की शुरूआत से विस्तारित किया जा सकता है, जैसे कि भोजन की खोज या शिकारियों का डर [1]।

क्लासिक कण झुंड एल्गोरिथ्म

1995 में, जेम्स कैनेडी और रसेल एबरहार्ट ने निरंतर गैर-रेखीय कार्यों को अनुकूलित करने के लिए एक विधि प्रस्तावित की, जिसे उन्होंने कण झुंड एल्गोरिथ्म [2] कहा। वे रेनॉल्ड्स के सिमुलेशन मॉडल से प्रेरित थे, साथ ही एक समान विषय [4] पर हेपनर (हेपनर) और ग्रेनेडियर (ग्रेनेडियर) के काम से भी जुड़े थे। कैनेडी और एबरहार्ट ने उल्लेख किया कि दोनों मॉडल पक्षियों के बीच की दूरी को नियंत्रित करने पर आधारित हैं - और, इसलिए, झुंड का सिंक्रनाइज़ेशन उन प्रयासों का एक फ़ंक्शन है जो पक्षी इष्टतम दूरी बनाए रखने के लिए करते हैं।



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



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



एल्गोरिथ्म के प्रत्येक पुनरावृत्ति पर, प्रत्येक कण के वेग वेक्टर की दिशा और लंबाई में पाए गए अनुकूलन के बारे में जानकारी के अनुसार बदलते हैं:



।



जहाँ कण वेग वेक्टर है ( - इसका i-th घटक), । - निरंतर त्वरण, कण द्वारा पाया जाने वाला सबसे अच्छा बिंदु है, - सिस्टम के सभी कणों द्वारा ट्रेस किए गए सबसे अच्छे बिंदु, कण और फ़ंक्शन की वर्तमान स्थिति है 0 से 1 समावेशी से एक यादृच्छिक संख्या देता है।



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

क्लासिक एल्गोरिथ्म के लिए संशोधन

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

LBEST

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



।



जहाँ - कण और उसके पड़ोसियों के बीच सबसे अच्छा परिणाम। पड़ोसी कण या तो ऐसे कण होते हैं जो दिए गए सूचकांक से अलग होते हैं जो किसी निश्चित मूल्य से अधिक नहीं होते हैं, या ऐसे कण जिनकी दूरी किसी दिए गए सीमा से अधिक नहीं होती है।



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

जड़ता भारित PSO

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

इसे ध्यान में रखते हुए, शीया और एबरहार्ट ने कण वेग वैक्टर को अद्यतन करने के लिए नियम बदलने का प्रस्ताव दिया:



।



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

टाइम-वैरिंग जड़ता भारित PSO

अपने 1998 के काम में, शीया और एबरहार्ट ने उल्लेख किया कि जड़ता का एक सकारात्मक निरंतर होना जरूरी नहीं है: यह एक रैखिक और गैर-रैखिक कानून [5] के अनुसार एल्गोरिथ्म के संचालन के दौरान बदल सकता है। 1999 के एक लेख में और बाद में काम करता है, वे अक्सर कमी के रैखिक कानून का उपयोग करते थे, काफी प्रभावी और एक ही समय में सरल [6]। फिर भी, जड़ता परिवर्तन के अन्य कानूनों को विकसित और सफलतापूर्वक लागू किया गया था।



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

विहित पीएसओ

2002 में, मौरिस क्लार्क और जेम्स कैनेडी ने कण झुंड एल्गोरिथ्म के अपने संशोधन का प्रस्ताव दिया, जो इतना लोकप्रिय हो गया है कि अब इसे कैनोनिकल कण झुंड एल्गोरिथ्म [7] कहा जाता है। यह कणों के अभिसरण को नियंत्रित करते हुए एल्गोरिथ्म के समायोज्य मापदंडों के उचित मूल्यों को "अनुमान" करने की आवश्यकता को समाप्त करता है।



क्लेयर और कैनेडी ने अतिरिक्त कारक को पेश करके कण वेग वैक्टर की गणना करने के तरीके को बदल दिया:



।



जहाँ , और संपीड़न अनुपात के बराबर है:



।



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

पूरी तरह से सूचित कण झुंड

अपने 2004 के काम में, रुई मेंडेस, जेम्स कैनेडी, और जोस नेवेस ने नोट किया कि यह धारणा कि केवल सबसे सफल कण कैनोनिकल कण झुंड एल्गोरिथ्म में प्रत्येक कण को ​​प्रभावित करता है, इसके अंतर्निहित के अनुरूप नहीं है प्राकृतिक तंत्र और, संभवतः, एल्गोरिथ्म [8] की दक्षता में कमी की ओर जाता है। उन्होंने सुझाव दिया कि एकल समाधान के लिए एल्गोरिथ्म के अत्यधिक ध्यान के कारण, खोज स्थान की संरचना के बारे में महत्वपूर्ण जानकारी खो सकती है।



इसके आधार पर, उन्होंने सभी कणों को "पूरी तरह से सूचित" करने का निर्णय लिया, अर्थात सभी पड़ोसी कणों से जानकारी प्राप्त की। ऐसा करने के लिए, उन्होंने विहित एल्गोरिथ्म में गति के परिवर्तन का नियम बदल दिया:



।



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

निष्कर्ष

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



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



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

साहित्य

[१] क्रेग रेनॉल्ड्स, "झुंड, झुंड, और स्कूल: एक वितरित व्यवहार मॉडल" // कंप्यूटर ग्राफिक्स, 21 (4), पीपी। 25-34, 1987।

[२] जे। कैनेडी, आरसी एबरहार्ट, "पार्टिकल स्वॉर्म ऑप्टिमाइज़ेशन" // तंत्रिका नेटवर्क पर IEEE अंतर्राष्ट्रीय सम्मेलन की कार्यवाही में, पीपी। १ ९४२-१९ ४,, १ ९९ ५।

[३] आरसी एबरहर्ट, जे। कैनेडी, "कण स्वार्म सिद्धांत का उपयोग कर एक नया आशावादी" // माइक्रो मशीन और मानव विज्ञान पर छठे अंतर्राष्ट्रीय संगोष्ठी की कार्यवाही MHS'95, पीपी। 39-43, 1995।

[४] एफ। हेप्पनर, यू। ग्रेनेडर, "समन्वित पक्षी झुंडों के लिए एक स्टोकेस्टिक नॉनलाइन मॉडल" // अराजकता की विशिष्टता, पीपी। २३३-२३,, १ ९९ ०।

[५] वाई। शि।, आर। एबरहार्ट, "ए मॉडिफ़ाइड पार्टिकल स्वॉर्म ऑप्टिमाइज़र" // १ ९९ ut आईवीईई इंटरनेशनल कॉन्फ्रेंस ऑन इवोल्यूशनरी कम्प्यूटेशन प्रोसीडिंग्स, पीपी ६ ९ -73३, १ ९९ Shi।

[६] वाई। शि।, आर। एबरहार्ट, "कण स्वाम अनुकूलन का अनुभवजन्य अध्ययन" // विकासवादी संगणना पर १ ९९९ आईईईई कांग्रेस की कार्यवाही, पीपी। १ ९४५-१ ९ ५०, १ ९९९।

[[] एम। क्लार्क, जे। कैनेडी, "कण स्वारम - विस्फोट, स्थिरता, और एक बहुआयामी जटिल स्थान में अभिसरण" // IEEE लेन-देन विकासवादी संगणना, संख्या ६ (१), पीपी ५ 58-73३, २००२। ।

[[] आर। मेंडेस, जे। केनेडी, जे। नेव्स, "पूरी तरह से सूचित कण दलदल: सरल, शायद बेहतर" // IEEE लेन-देन विकासवादी संगणना, संख्या ation (३), पीपी। २०४-२१२, २००४