एक बड़े ग्राफ़ (यात्रा विक्रेता समस्या) में हैमिल्टनियन चक्र की खोज करें। भाग 2

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

मेरा सुझाव है कि जिन्होंने पहला लेख नहीं पढ़ा है वे इसे पढ़ें, क्योंकि यह एक निरंतरता है, और किसी भी मामले में एक स्वतंत्र लेख नहीं है।

1.Ant एल्गोरिथ्म, उर्फ ​​चींटी कॉलोनी अनुकूलन (ACO)

इस एल्गोरिथ्म का विचार सबसे पहले मार्को डोरिगो को हुआ, जिन्होंने 1992 में इस एल्गोरिथम का प्रस्ताव रखा था।
एल्गोरिथ्म को मेटाएरिस्टिक ऑप्टिमाइज़ेशन के रूप में जाना जाता है।

एल्गोरिदम का आइडिया

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

इस तथ्य का एक उदाहरण कि अधिक चींटियाँ प्रति यूनिट कम से कम पथ के साथ चलेंगी, और अंत में, अन्य सभी फेरोमोन वाष्पित हो जाएंगे, लेकिन इस एक पर, यह पूरी कॉलोनी के लिए पथ बन जाएगा।
यात्रा विक्रेता समस्या के लिए इसे कैसे लागू करें?
हम शाखा और बाध्य विधि लेते हैं, जिसे मैंने पहले लेख में वर्णित किया है, और निम्नलिखित परिवर्तन करें:
1) अगर एक चयन करने के लिए पेड़ में / एक बढ़त लेने के लिए नहीं, तो हम रास्ते में से एक के साथ चले गए, रूट से इस वर्टेक्स के लिए निश्चित संख्या में फेरोमोन्स पर "डाल"।
2) प्रत्येक किनारे पर, इस किनारे के माध्यम से सभी रास्तों के फेरोमोन जोड़ते हैं।
3) एल्गोरिथ्म के प्रत्येक पुनरावृत्ति पर, प्रत्येक पथ पर फेरोमोन की संख्या एक निश्चित प्रतिशत से घट जाती है।
4) अगली चोटी चुनते समय, हम न केवल इसके लागत अनुमान से, बल्कि इसके रास्ते में फेरोमोन की संख्या से भी निर्देशित होते हैं।

एल्गोरिदम को बड़े ग्राफ़ पर हैमिल्टनियन चक्र के पॉज़िक के लिए सबसे प्रभावी बहुपद एल्गोरिदम में से एक माना जाता है।
शाखाओं और सीमाओं की लिखित विधि होने से, चींटी कॉलोनी के सरलतम संस्करण को तेज करने के लिए यह काफी सरल है, कठिनाई केवल वाष्पीकरण दर के लिए स्थिरांक के सही चयन में है, पास होने पर कितने फेरोमोन डालते हैं, आदि।
लालची से लाभ ~ 17% है, काम करने का समय लगभग एक घंटे है।

आनुवंशिक एल्गोरिथ्म

एल्गोरिदम का आइडिया

इस एल्गोरिथ्म के लिए विचारों का मुख्य स्रोत जैविक विकास है।
इस एल्गोरिथ्म में मुख्य जोर तथाकथित क्रॉसओवर ऑपरेटर पर रखा गया है, जो उम्मीदवार समाधानों के पुनर्संयोजन का उत्पादन करता है।
1) मुख्य आवश्यकता यह है कि हम समाधान को किसी चीज़ (बिट्स, संख्याओं, प्रतीकों) के वेक्टर के रूप में संग्रहित करें
हमारी समस्या में, हम i-th सेल में स्टोर करेंगे उस वर्टेक्स की संख्या जिस पर हम इस i-th सेल से जा रहे हैं।
2) नए समाधान, जिसमें से हम क्रॉसिंग के लिए समाधानों में से चुनेंगे, हम पुराने समाधानों और क्रॉस के म्यूटेशन के परिणामस्वरूप प्राप्त करेंगे।
3) एक उत्परिवर्तन को एक फ़ंक्शन के रूप में परिभाषित किया गया है जो कुछ जीनों (हमारे मामले में सरणी कोशिकाओं) को बेतरतीब ढंग से बदलता है, और परिणाम कई समाधानों में एम्बेडेड है।
4) क्रॉसब्रीडिंग को पिछले पुनरावृत्ति से कई सर्वश्रेष्ठ समाधानों के जीनों के संयोजन (यादृच्छिक) के रूप में परिभाषित किया गया है।
5) प्रत्येक चरण में, हमें अनुपयुक्त समाधानों को बाहर फेंकना चाहिए - वे जो तुच्छ हैमिल्टनियन चक्र नहीं हैं। (उदाहरण के लिए, उनके आकार के दो चक्र 250 होते हैं)
6) म्यूटेशन के समाधान को कुछ संभावना के साथ यादृच्छिक रूप से चुना जाता है।
7) क्रॉस-ब्रीडिंग समाधान को फिर से यादृच्छिक रूप से चुना जाता है, लेकिन इस पुनरावृत्ति (जिसके लिए चक्र का वजन कम है) के लिए प्राप्त किए जाने वाले सर्वोत्तम समाधान अधिक होने की संभावना है।
यदि आप प्रत्येक चरण में मेमोरी के लिए खेद महसूस करते हैं, तो आप अनुकूलित समाधानों में से सबसे खराब फेंक सकते हैं।
इस तरह के एल्गोरिथ्म को चलाने का सबसे आसान तरीका यह है कि पहले इसे कुछ सही समाधानों के साथ प्रदान किया जाए, उदाहरण के लिए, अलग-अलग कोने से चलने वाली एक लालची महिला द्वारा हमें दिया गया।
बंद करो राज्य - एल्गोरिथ्म के कुछ पैरामीटर, जो कहते हैं कि गिनती खत्म करने का समय है और आपको उत्तर (पल में सबसे अच्छा समाधान) प्रदर्शित करने की आवश्यकता है
मेरे मामले में, स्टॉप पैरामीटर समय सीमा थी।
सबसे सरल कार्यान्वयन ने 2 घंटे में काम किया और लालची से केवल 4% जीत लिया
यह ध्यान देने योग्य है कि यह काफी हद तक सरलतम कार्यान्वयन के कारण है, कई स्रोतों का दावा है कि आनुवंशिक एल्गोरिथम सबसे अच्छा है, यदि सर्वोत्तम नहीं है।
इसके साथ बहुत सारी समस्याएं हैं, जैसे आधे सूत्रों का कहना है कि इस समय रिकॉर्ड धारक एसीओ है, जो कि आधा आनुवांशिकी है।

पी एस निरंतरता मोटे तौर पर पहले लेख पर टिप्पणियों के लिए धन्यवाद लिखा गया था, जिसने मुझे इन एल्गोरिदम के कम से कम सरल कार्यान्वयन को लिखने की कोशिश करने के लिए प्रोत्साहित किया, जिसके लिए धन्यवाद mephistopheies और Diversus