मैंने एक नकली एनालिंग विधि का आविष्कार कैसे किया

अच्छा समय, हेब्र!

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

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

कार्य विश्लेषण

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



इस तरह के ग्राफ को मुख्य विकर्ण पर शून्य के साथ एक सममित मैट्रिक्स के रूप में दर्शाया जा सकता है (शहर से इसके लिए पथ की लंबाई शून्य के बराबर है)।

निर्णय एल्गोरिथ्म

इस भाग में, मैं एल्गोरिथ्म (सीरियल और समानांतर) को लागू करने के दोनों तरीकों का वर्णन करूंगा, और मैं सीरियल संस्करण के लिए प्रोग्राम कोड दूंगा।

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

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

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

सी # सॉफ्टवेयर कार्यान्वयन

class CCities { //   public Point[] Coordinate; public CCities(int N, int maxValue) //maxValue -   pictureBox   { Random random = new Random(); Coordinate = new Point[N]; //   ,   pictureBox,        //     int minBorder = (int)(maxValue * 0.05); int maxBorder = (int)(maxValue * 0.95); for (int i = 0; i < N; i++) { Coordinate[i] = new Point(random.Next(minBorder, maxBorder), random.Next(minBorder, maxBorder)); } } } 

  class CPath { //   double[,] distance; //     public int[] Path; public CPath(CCities map) { //      distance = new double[map.Coordinate.Length, map.Coordinate.Length]; //  ,        for (int j = 0; j < map.Coordinate.Length; j++) { distance[j, j] = 0; for (int i = 0; i < map.Coordinate.Length; i++) { double value = Math.Sqrt(Math.Pow(map.Coordinate[i].X - map.Coordinate[j].X, 2) + Math.Pow(map.Coordinate[i].Y - map.Coordinate[j].Y, 2)); distance[i, j] = distance[j, i] = value; } } //   //  1  - ,       0 -      ""  Path = new int[map.Coordinate.Length + 1]; for (int i = 0; i < map.Coordinate.Length; i++) { Path[i] = i; } Path[map.Coordinate.Length] = 0; } //,      public void FindBestPath() { Random random = new Random(); for (int fails = 0, F = Path.Length * Path.Length; fails < F; ) { //    //      int p1 = 0, p2 = 0; while (p1 == p2) { p1 = random.Next(1, Path.Length - 1); p2 = random.Next(1, Path.Length - 1); } //  double sum1 = distance[Path[p1 - 1], Path[p1]] + distance[Path[p1], Path[p1 + 1]] + distance[Path[p2 - 1], Path[p2]] + distance[Path[p2], Path[p2 + 1]]; double sum2 = distance[Path[p1 - 1], Path[p2]] + distance[Path[p2], Path[p1 + 1]] + distance[Path[p2 - 1], Path[p1]] + distance[Path[p1], Path[p2 + 1]]; if (sum2 < sum1) { int temp = Path[p1]; Path[p1] = Path[p2]; Path[p2] = temp; } else { fails++; } } } //   public double PathLength() { double pathSum = 0; for (int i = 0; i < Path.Length - 1; i++) { pathSum += distance[Path[i], Path[i + 1]]; } return pathSum; } } 

एल्गोरिथ्म के उदाहरण

एल्गोरिथम प्रदर्शन विश्लेषण

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


जहां K समानांतर में चलने वाली प्रक्रियाओं की संख्या है। इस तरह की निर्भरता बहुत जल्दी छोटे पी पर 1 तक जाती है। चित्र p = 0.1 के लिए निर्भरता P (K) का एक ग्राफ दिखाता है ("de jure" ग्राफ असतत होना चाहिए, लेकिन मुझे आशा है कि आप मुझे इस तरह की स्वतंत्रता को माफ कर देंगे):



यह देखा जा सकता है कि पहले से ही K = 6..7 पर, संभावना P 0.5 के बराबर हो जाती है। यही है, कई प्रक्रियाओं का उपयोग करने के लाभ स्पष्ट हैं - संभावना में बहुत तेजी से वृद्धि।
अब हम एक प्रक्रिया के लिए प्रायिकता p ज्ञात करते हैं। जाहिर है, यह मैट्रिक्स के आकार एन के विपरीत आनुपातिक है और सीधे एफ के मूल्य के आनुपातिक है, जो काउंटर तब पहुंचता है जब एल्गोरिथ्म अपना काम करना बंद कर देता है। दुर्भाग्य से, अधिक सटीक मूल्यांकन देना लगभग असंभव है। ग्राफ के बारे में लगभग हम केवल इतना ही कह सकते हैं कि विभिन्न रास्तों की संख्या (N-1) के बराबर है ! Ract2 (हम एक को घटाते हैं क्योंकि एक शहर शुरू करने वाला होता है और जाहिर तौर पर गणना में भाग नहीं लेता है, लेकिन हम दो के कारण विभाजित होते हैं उसी मार्ग को दोनों दिशाओं में घेरा जा सकता है)।
इस प्रकार, वांछित संभावना का केवल प्रयोगात्मक रूप से अनुमान लगाया जा सकता है। विभिन्न मापदंडों एन के लिए प्रयोगों की एक श्रृंखला की गई थी । काउंटर के लिए प्रतिबंध के रूप में, मूल्य F = N ^ 2 को स्वीकार किया जाता है। प्रत्येक N के लिए , 10,000 रन किए गए थे और प्राप्त किए गए परिणाम तालिका में सूचीबद्ध हैं:



मैं प्रस्तुत संकेतन की व्याख्या करूँगा:
पी (न्यूनतम) इष्टतम समाधान खोजने की संभावना है। पी (एक्स%) - एक समाधान खोजने की संभावना जो एक्स% से अधिक नहीं द्वारा इष्टतम से भिन्न होती है। यह है, उदाहरण के लिए, पी (10%) के लिए, ऐसे समाधान वे होंगे जो अंतराल में आते हैं [न्यूनतम, न्यूनतम + (अधिकतम-न्यूनतम) * 0.1] , जहां न्यूनतम और अधिकतम पथ क्रमशः पाए जाते हैं।
यहाँ एक विषयांतर करना और यह कहना आवश्यक है। बेशक, इस तरह का विश्लेषण किसी भी वास्तविक सटीकता का ढोंग नहीं करता है, क्योंकि वांछित पैटर्न प्राप्त करने के लिए भी 10,000 प्रयोग बहुत कम होते हैं (जब आप परिणाम को पुनः आरंभ करते हैं, तो यह पूरी तरह से अलग हो सकता है), और, सबसे महत्वपूर्ण बात, कोई गारंटी नहीं है कि एल्गोरिथ्म ने सत्य पाया। संभव तरीकों का इष्टतम। मूल्यांकन के लिए, वह सबसे अच्छा पाया के ज्ञान पर काम करता है, लेकिन यह इस तथ्य से बहुत दूर है कि वह सभी का सबसे अच्छा भी है। फिर भी, मेरा मानना ​​है कि परिणामों का उपयोग करना संभव है, यदि मात्रात्मक के लिए नहीं, लेकिन कम से कम एल्गोरिथम की गुणात्मक समझ के लिए।
हम उन्हीं परिणामों का वर्णन करते हैं:



विधि के लाभ

• एल्गोरिथ्म की "वैचारिक" सादगी;
• धारावाहिक और समानांतर संस्करणों दोनों में कार्यान्वयन में आसानी;
• इसके समानांतर कार्यान्वयन के साथ एल्गोरिथ्म की तेजी से बढ़ती दक्षता;
• इष्टतम के करीब एक समाधान खोजने की उच्च संभावना।

विधि का नुकसान

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

एल्गोरिथ्म अनुकूलन
विधि पर काम करने और शोध करने की प्रक्रिया में, मैंने एल्गोरिथ्म को बेहतर बनाने के लिए निम्नलिखित संभव तरीके सुझाए:

• सिद्ध पथों का "इतिहास" जोड़ना। फिलहाल, एल्गोरिथ्म परीक्षण किए गए रास्तों को याद नहीं करता है और प्रत्येक पुनरावृत्ति पर प्राप्त नए विकल्पों को नियंत्रित नहीं करता है। ऐसे रास्तों की जाँच करने और बाहर भेजने के कार्य को जोड़ना परिणाम की सटीकता को बहुत प्रभावित करना चाहिए;
• शायद काउंटर रेफरेंस वैल्यू को और अधिक बारीक करने का एक तरीका है। जैसा कि परीक्षण सेटिंग्स से देखा जा सकता है, वर्तमान सेटिंग्स ( एफ = एन ^ 2 ) पर, आकार " एन = 20" के मेट्रिसेस के क्षेत्र में एक "छेद" दिखाई देता है। मुझे इस ग्राफ व्यवहार के कारणों की सटीक समझ नहीं है, लेकिन संभवतः इस मूल्य को अधिक सफल तरीके से चुनने का एक तरीका है। ।

निष्कर्ष

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

उन लोगों के लिए जो कोड में खुदाई करना चाहते हैं, मैंने प्रोजेक्ट को अपने मेल क्लाउड पर लिखा है (VS2012 में लिखा है, परियोजना वीएस के पुराने संस्करणों के साथ संगत नहीं होगी। कार्यक्रम को चलाने के लिए, आपको एक .net फ्रेमवर्क 4.5 की आवश्यकता होगी, .exe फ़ाइल \ Salesman \ Salesman \ bin \ फ़ोल्डर में स्थित है। डीबग करें)