🖕🏼 ✌️ 🦉 चींटी एल्गोरिदम 👨🏿‍🤝‍👨🏽 👩🏼‍💻 💮

प्रस्तावना

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

परिचय

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

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

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

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

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

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

यात्रा विक्रेता समस्या को हल करने के लिए क्लासिक चींटी एल्गोरिदम

जैसा कि ऊपर उल्लेख किया गया है, चींटी एल्गोरिदम एक मल्टी-एजेंट सिस्टम को मॉडल करता है। उसके एजेंटों को भविष्य में चींटियों कहा जाएगा। वास्तविक चींटियों की तरह, वे काफी सरल हैं: उन्हें अपने कर्तव्यों को निभाने के लिए थोड़ी मात्रा में स्मृति की आवश्यकता होती है, और काम के प्रत्येक चरण में वे सरल गणना करते हैं।

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

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

चींटी एक गाँठ में हो

, और नोड

- यह संक्रमण के लिए उपलब्ध नोड्स में से एक है:

। नोड्स को जोड़ने वाले किनारे के वजन को नकारें

और

कैसे

और उस पर फेरोमोन की तीव्रता जैसी है

। फिर चींटी के संक्रमण की संभावना

में

के बराबर होगा:

$p_ {ij} = \ frac {t_ {ij} ^ \ alpha + \ frac {1} {w_ {ij} ^ \ Beta}} {\ _ sum_ {l \ _ s_i} \ बाएँ (t_ / il) ^ \ अल्फा + \ _ frac {1} {w_ {il} ^ \ beta} \ right)}$

जहाँ

और

- ये समायोज्य पैरामीटर हैं जो पथ का चयन करते समय घटकों (रिब वजन और फेरोमोन स्तर) के महत्व को निर्धारित करते हैं। जाहिर है, के लिए

एल्गोरिथ्म एक क्लासिक लालची एल्गोरिथ्म में बदल जाता है, और जब

वह जल्दी से कुछ उप-अपनाने के समाधान में जुट जाता है। मापदंडों के सही अनुपात का विकल्प अनुसंधान का विषय है, और सामान्य मामले में अनुभव पर आधारित है।

चींटी सफलतापूर्वक मार्ग से गुजरने के बाद, यह पारित सभी किनारों पर एक निशान छोड़ देती है, पथ की लंबाई के विपरीत आनुपातिक होता है:

$\ Delta _ {ij} = \ left \ {\ {start \ array} {c} {\ frac {k} {L}, (ij) \ _ in P} \\ {0, (ij) \ notin P} \ end {सरणी} \ सही।$ ।

जहाँ

पथ की लंबाई है, और

- समायोज्य पैरामीटर। इसके अलावा, फेरोमोन निशान का वाष्पीकरण होता है, अर्थात, एल्गोरिथ्म के प्रत्येक पुनरावृत्ति पर सभी किनारों पर फेरोमोन की तीव्रता घट जाती है। इस प्रकार, प्रत्येक पुनरावृत्ति के अंत में, तीव्रता को अद्यतन करना आवश्यक है:

$t_ {ij} = \ left (1-e \ right) \ cdot t_ {ij} + \ Delta t_ {jj}$

शास्त्रीय एल्गोरिदम के संशोधनों की समीक्षा

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

Elitist चींटी प्रणाली

इन सुधारों में से एक एल्गोरिथ्म में तथाकथित "कुलीन चींटियों" की शुरूआत है। अनुभव से पता चला है कि जब छोटे रास्तों से प्रवेश करने वाली पसलियों को पास किया जाता है, तो चींटियों को और भी छोटे रास्ते मिलने की संभावना होती है। इस प्रकार, सबसे प्रभावी मार्गों पर फेरोमोन के स्तर को कृत्रिम रूप से बढ़ाने के लिए एक प्रभावी रणनीति है। ऐसा करने के लिए, एल्गोरिथ्म के प्रत्येक पुनरावृत्ति पर, कुलीन चींटियों में से प्रत्येक रास्ता जाता है, जो इस समय पाए जाने वाले लोगों में सबसे छोटा है।

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

चींटी-क्यू

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

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

चींटी कॉलोनी प्रणाली

1997 में, उन्हीं शोधकर्ताओं ने एक पेपर प्रकाशित किया, जो उनके द्वारा विकसित एक और चींटी एल्गोरिथम था [5]। शास्त्रीय एल्गोरिथ्म की तुलना में दक्षता बढ़ाने के लिए, उन्होंने तीन मुख्य बदलाव पेश किए।

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

मैक्स-मिन एंट सिस्टम

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

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

ASrank

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

निष्कर्ष

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

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

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

साहित्य

[१] एम। डोरिगो, "ओटिमिज़ाज़िऑन, एप्रेंडिमेंटो ऑटोमो, एड अल्गोरिटिमी बासमती सु मेटाफोरा न्यूट्रेल (ऑप्टिमाइज़ेशन, लर्निंग, एंड नेचुरल अल्गोरिद्म)", सिस्टम और सूचना इलेक्ट्रॉनिक इंजीनियरिंग में डॉक्टरेट, पोलिटेकनिको डी मिलानो, १ ९९ २ शहर

[२] ए। कोलोर्नी, एम। डोरिगो, वी। मनिएज़ो, "चींटी ऑप्टिमाइजेशन बाई एंट कालोनीज" // कृत्रिम यूरोपीय, पेरिस, फ्रांस, एल्सेवियर प्रकाशन पर प्रथम यूरोपीय सम्मेलन की कार्यवाही, पीपी। १३४-१४२, १ ९९ १।

[३] एम। डोरिगो, वी। मनिज़ो, ए। कोलॉर्नी, "द एंट सिस्टम: कोऑपरेटिंग एजेंट्स की एक कॉलोनी द्वारा अनुकूलन" // IEEE ट्रांज़ैक्शंस ऑन सिस्टम्स, मैन एंड साइबरनेटिक्स-पार्ट बी, २६, १, १, पृष्ठ २ ९। -41, 1996

[४] एलएम गम्बार्डेला, एम। डोरिगो, "एंट-क्यू: ए रीइनफोर्समेंट लर्निंग एप्रोच टू द ट्रैवलिंग सेल्समैन प्रॉब्लम" // बारहवीं इंटरनेशनल कांफ्रेंस ऑन मशीन लर्निंग, मॉर्गन कॉफमैन, पीपी। २५२-२६०, १ ९९ ५।

[५] एम। डोरिगो, एलएम गम्बार्डेला, एंट कालोनी सिस्टम: ट्रैवलिंग सेल्समैन समस्या के लिए एक सहकारी शिक्षण दृष्टिकोण // इवोल्यूशनरी कम्प्यूटेशन वॉल्यूम पर IEEE लेनदेन। 1, 1, पीपी। 53-66, 1997।

[६] टी। स्टुट्ज़ल, एच। होस, "मैक्स-मिन चींटी सिस्टम एंड द ट्रैवल सेल्समैन प्रॉब्लम की स्थानीय खोज" // IEEE इंटरनेशनल कॉन्फ्रेंस ऑन इवोल्यूशनरी कंपीटेशन, पीपी। 309-314, 1997।

[[] बर्न बुलडाइमर, रिचर्ड एफ। हार्टल, क्रिस्टीन स्ट्रू “," चींटी सिस्टम का एक नया रैंक आधारित संस्करण। एक कम्प्यूटेशनल अध्ययन "// अर्थशास्त्र और प्रबंधन विज्ञान में अनुकूली सूचना प्रणाली और मॉडलिंग, 1, 1997।

[[] टी। स्टुट्ज़ल, एम। लोपेज़-इबनेज़, पी। पेलेग्रीनी, एम। मौर, एम। डे। ओका, एम। बिराटारी, माइकल मॉर, एम। डोरिगो, "एंटोन कॉलोनी ऑप्टिमाइज़ेशन में पैरामीट एडाप्टेशन" // टेक्निकल रिपोर्ट, इरोडिया, यूनिवर्सिटे लिबरे डी ब्रुक्सले, 2010

चींटी एल्गोरिदम