एल्गोरिदम की तुलना करने के लिए एक पद्धति और इसके अलावा क्या काम आ सकता है

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



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

मूल्यांकन मानदंड

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

एक छोटा विषयांतर: यहां वर्णित सब कुछ का परीक्षण माटलैब में नहीं किया गया था, जैसा कि मूल लेख में, लेकिन ओक्टेव में [http://www.gnu.org/software/octave/]। इसके कई कारण हैं - पहला, मेरे पास, और दूसरा, इसकी प्रोग्रामिंग भाषा लगभग पूरी तरह से मैटलैब के अनुकूल है, और अंत में, हर कोई इसे कर सकता है क्योंकि यह स्वतंत्र और सार्वजनिक है।

विश्लेषण कर रहा है ...

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

तो विश्लेषण समारोह:

function [timeUsed, distTotal] = Analyze( ) %         load points_data.dat cities %    timeStart = cputime(); %    result = SimulatedAnnealing(cities, 10, 0.00001); %     timeUsed = cputime - timeStart; %     distTotal = PathLengthMat(result); %    plot(result(:,1), result(:,2), '-*'); drawnow (); end 

मैंने शहर के निर्देशांक की एक सरणी के साथ एक फ़ाइल बनाने के लिए एक फ़ंक्शन नहीं लिखा था। आप इसे सीधे कमांड लाइन से कर सकते हैं:

  cities = rand(100, 2)*10; save points_data.dat cities; 

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

 function [dist] = distEuclid(A, B) dist = (A - B).^2; dist = sum(dist); dist = sqrt(dist); end 

खैर, यह निर्धारित करने के लिए कि परिणाम समय-समय पर कितना स्थिर है, हम यह सब कई बार एक चक्र में चलाएंगे, परिणाम एकत्र करेंगे और उनके औसत और परिणामों के प्रसार की डिग्री का मूल्यांकन करेंगे:

 function [] = Statistics testNum = 1000; %      timeUsed = zeros(testNum,1); distTotal = zeros(testNum,1); for n=1:testNum [timeUsed(n), distTotal(n)] = Analyze; end %      time = [mean(timeUsed), std(timeUsed)] dist = [mean(distTotal), std(distTotal)] end 

पहली निराशा कितनी देर लगती है! कंप्यूटर कोर i5-3450 3.1GHz 8Gb रैम पर, एक पास औसतन 578 सेकंड में किया जाता है। इसलिए मैं अधिक विश्वसनीयता के लिए 1000 चक्रों को शुरू करना और औसत करना चाहता था, लेकिन यह ... 6.69 दिन। मुझे 100 चक्रों के लिए दौड़ना पड़ा और लगभग 16 घंटे 4 मिनट (यानी सुबह के समय) के बाद हमारे पास परिणाम आया:
औसत गणना समय 578.1926 (नमूना 3.056 में मानक विचलन), परिणामस्वरूप पथ की औसत लंबाई 91.0844 (मानक विचलन 2.49)। यही है, सब कुछ स्थिर से अधिक है, और, इसलिए, उपयोग के लिए उपयुक्त है। लेकिन कब तक। मैं विरोध नहीं कर सका और अनुकूलन करने के लिए ललचा गया।

अनुकूलन

त्वरण के लिए पहला उम्मीदवार दूरी का अनुमान है। मैट्रिक्सलेब की तरह ऑक्टेव मैट्रिक्स कंप्यूटिंग के लिए अनुकूलित है - हम इसे भी फिर से लिखेंगे। समारोह में दो सरणियाँ होंगी: ए - खंडों की शुरुआत, बी - क्रमशः, उनके छोर:

 function [dist] = distEuclid(A, B) dist = (A - B).^2; dist = sum(dist, 2); dist = sqrt(dist); dist = sum(dist); end 

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

 function [length] = PathLengthMat(cities) citiesShifted = circshift(cities, 1); length = distEuclid(cities, citiesShifted); end 

ठीक है, निश्चित रूप से, आपको सीधे फ़ंक्शन सरणियों के साथ काम करने के लिए फ़ंक्शन SimulatedAnnealing और GenerateStateCandidate को फिर से लिखना होगा। मैं पूर्ण कोड नहीं दूंगा, अंत में संग्रह के लिए सभी स्रोत कोड के साथ एक लिंक होगा जो रुचि रखते हैं।
हम शुरू करते हैं, देखो ... औसत गणना का समय 70.554 है (नमूने में मानक विचलन 0.096 है), जिसके परिणामस्वरूप पथ की औसत लंबाई 90.403 (मानक विचलन 2.204) है।
गति में वृद्धि आठ गुना से अधिक है! आगे कोशिश करना दिलचस्प नहीं है - आपको ऐसी वृद्धि नहीं मिली है। सच है, मेमोरी की खपत (प्रस्तावित पद्धति के अनुसार) में अब दो निर्देशांक (वर्तमान समाधान और नए उम्मीदवार) में अंक के दो सरणियां हैं, वह है ... एन * 4। कुछ भी नहीं बदला है।
लेकिन, चूंकि हम एल्गोरिदम का मूल्यांकन कर रहे हैं, हम तापमान डेटा की जांच करेंगे। उत्पन्न बिंदु सरणियों की प्रारंभिक "ऊर्जा" 500 से 700 तक होती है, और अंतिम आउटपुट मार्गों में लगभग 90 प्लस / माइनस 5. उतार चढ़ाव होता है। इसलिए, लेखक द्वारा चुना गया तापमान व्यावहारिक रूप से केवल 100,000 पुनरावृत्तियों की एक सीमा प्रदान करता है (वैसे, यह कोड में हार्ड-कोडित है। लूपिंग को रोकने के लिए। मैंने इसे दस मिलियन तक बढ़ा दिया है, एल्गोरिथ्म की जांच करते समय मुझे खुद को क्यों रोकना चाहिए?)। वास्तव में, थोड़ा प्रयोग करने पर, हमें Tmax = 300 और Tmin = 0.001 के लगभग समान परिणाम मिलते हैं। इसी समय, निष्पादन का समय 21 सेकंड तक कम हो गया था।

खोज के विकल्प

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


संभवतः फ़ंक्शन के हर के रैखिकता का मतलब था, क्योंकि विज्ञान में उपयोग किए जाने वाले अन्य सभी विकल्पों के भाजक वास्तव में बदतर दिखते हैं।
तुलना के लिए, हम तापमान फ़ंक्शन T = Tmax * (A ^ k) भी प्रयास करेंगे, जहां A को चुना जाता है, आमतौर पर 0.7 - 0.999 के भीतर। (लागू होने पर, यह बिल्कुल लालची नहीं है - तिवारी = ए * टीआई -1)। इसके उपयोग के साथ "एनीलिंग" के विकल्प को "शमन" कहा जाता है। यह न्यूनतम तापमान तक बहुत तेज़ी से गिरता है, लेकिन प्रारंभिक अवस्था में अधिक कोमल होता है। यही है, एल्गोरिथ्म शुरुआत में इसके साथ अधिक प्रयोग करता है, लेकिन काम तेजी से पूरा करता है। तो - परिणामों का सारांश तालिका:

एल्गोरिथ्म	लंबाई (फैला हुआ)	समय (बिखराव)	स्मृति
लेख से	91.0844 (2.4900)	578.1926 (3.0560)	एन * ४
डॉट मैट्रिक्स (10-0.00001)	90.4037 (2.2038)	70.554593 (0.096166)	एन * ४
डॉट मैट्रिक्स (300-0.001)	90.7956 (2.1967)	20.94024 (0.16235)	एन * ४
मैट्रिक्स मैनहट्टन (10-0.00001)	90.0506 (3.2397)	70.96909 (0.7807)	एन * ४
मैट्रिक्स "शमन" (300-0.001)	92.0963 (2.3129)	22.59591 (0.39581)	एन * ४

निष्कर्ष।

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

वादा किए गए स्रोत यहां मिल सकते हैं
ठीक है, अगर आपको यह पसंद आया - आप कुछ समय बाद किसी और चीज़ से इसकी तुलना कर सकते हैं।