आनुवंशिक एल्गोरिथ्म SOA के भाग के रूप में एक परिवहन समस्या का समाधान

आनुवंशिक एल्गोरिथ्म SOA के भाग के रूप में एक परिवहन समस्या का समाधान

प्रतिष्ठित हब्रसोसिटीटी को बधाई!

इस अनुच्छेद में, मैं इस बारे में बात करना चाहूंगा कि मैंने आनुवंशिक एल्गोरिथ्म का उपयोग करके परिवहन समस्या को कैसे हल किया।

कार्य विवरण

विकिपीडिया समस्या को निम्न प्रकार से प्रस्तुत करता है - समरूप डेटा और एक रैखिक दृष्टिकोण के साथ सजातीय वाहनों (एक पूर्व निर्धारित मात्रा) पर खपत के सजातीय बिंदुओं के लिए सजातीय बिंदुओं से एक सजातीय उत्पाद के लिए इष्टतम परिवहन योजना की समस्या।

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


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

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

विवरण

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

एक समानांतर एल्गोरिदम कहा जाता है क्योंकि कई अलग-अलग गुणसूत्र आबादी एक साथ विकसित होते हैं। समय में कुछ बिंदुओं पर, बेतरतीब ढंग से चयनित गुणसूत्र आबादी के बीच चलते हैं।

गुणसूत्र निरूपण

प्रत्येक गुणसूत्र समस्या का एक हल है और इसे सरणियों के एक सरणी के रूप में प्रस्तुत किया जाता है, जहां प्रत्येक नेस्टेड सरणी एक मार्ग (1 कार) का प्रतिनिधित्व करता है। सरणी का प्रत्येक तत्व एक ग्राहक है जिसे सामान वितरित करने की आवश्यकता है:


सभी मार्ग स्पष्ट रूप से एक गोदाम से शुरू होते हैं और उनका अंत होता है।

चौराहा

हमारे पास 2 प्रकार के क्रॉस हैं - रैंडम (रैंडम क्रॉसओवर) और सजातीय (यूनिफॉर्म क्रॉसओवर)
रैंडम क्रॉसिंग - पैरेंट 1 से एक मनमाना मार्ग का एक मनमाना हिस्सा माता-पिता के लिए सबसे अच्छा सम्मिलन स्थान में रखा गया है। सबसे अच्छा सम्मिलन स्थान वह है जो सबसे कम लंबाई देता है।


यूनिफ़ॉर्म क्रॉस माता-पिता के सभी मार्गों के लिए घनत्व सूचकांकों की गणना करते हैं और वैकल्पिक रूप से माता-पिता 1 और 2 से सबसे कम सूचकांक वाले मार्गों को जोड़ते हैं। शेष बिंदुओं को सर्वश्रेष्ठ प्रविष्टि के स्थानों पर वितरित किया जाता है।

म्यूटेशन

एल्गोरिथ्म 2 प्रकार के म्यूटेशनों का उपयोग करता है - यादृच्छिक और मार्ग उत्परिवर्तन के सबसे दूर के हिस्सों के उद्देश्य से।
रैंडम म्यूटेशन रूट के रैंडम पार्ट का हिस्सा काट देते हैं और इसे ऐसी जगह पर डालते हैं जो न्यूनतम कुल दूरी देता है। दूसरे प्रकार का उत्परिवर्तन यादृच्छिक मार्गों में सबसे दूर के ग्राहकों को ढूंढता है और इसे सर्वश्रेष्ठ सम्मिलन के स्थान पर स्थानांतरित करता है।

स्थानीय अनुकूलन

क्रॉसिंग और म्यूटेशन ऑपरेशन के बाद, एल्गोरिथ्म प्रत्येक मार्ग के बिंदुओं को स्थानांतरित करने की कोशिश करता है ताकि मार्ग की लंबाई कम से कम हो।

स्वास्थ्य समारोह

सूत्र द्वारा प्रत्येक गुणसूत्र की फिटनेस (गुणवत्ता) पर विचार किया जाता है:
फिटनेस = ओवरलोड के लिए कुल दूरी + जुर्माना * अधिभार + अंडरलोड के लिए जुर्माना * अंडरलोड

रूट यूनीकनेस बनाए रखना

तेज़ रिज़ॉल्यूशन के लिए, प्रत्येक समूह में केवल अनन्य गुणसूत्र समाहित होते हैं।

गणना का अंत

एल्गोरिथ्म एक निश्चित% युग के लिए युगों की अधिकतम संख्या या सुधारों की अनुपस्थिति को प्राप्त करने के लिए गणना पूरी करता है

एल्गोरिथम परिणाम

नीचे कार्यों के मानक सेट के सबसेट पर एल्गोरिथ्म के परिणाम हैं। समस्या के नाम पर पहला अंक अंकों की संख्या है, दूसरा कारों की संख्या है। 5 कारों के साथ बी-एन 31-के 5 - 31 अंक।
8 परमाणु एएमडी (8350) पर काम के परिणाम:


सभी परीक्षण डेटा पर काम के परिणाम परियोजना पृष्ठ पर हैं।

समाधान वास्तुकला

समाधान C # में लिखा गया है और इसमें कई सेवाएँ, डेटाबेस और कतारें शामिल हैं:


प्रौद्योगिकी ढेर:
1. .NET 4.5 / C # / WCF / WinService
2. कतार: RabbitMQ
3. DB: MongoDB
4. डि कंटेनर: ऑटोफेक
5. यूनिट परीक्षण: एमएस टेस्ट / राइनो मोक्स / धाराप्रवाह अभिकथन

.NET विशिष्ट अनुभव जिसे मैं साझा करना आवश्यक समझता हूं:
1. कोड के अक्सर एक्सेस किए गए वर्गों में, गुणों का उपयोग न करें, लेकिन बस सार्वजनिक चर
2. Arrays अक्सर सूचियों और शब्दकोशों (Dictionary) की तुलना में तेज़ होते हैं, जब वे प्रविष्टि और विलोपन कार्यों को लागू करते हैं।

अगले चरण

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

संदर्भ

Google में आनुवंशिक (और न केवल) एल्गोरिदम का उपयोग करके समस्या को हल करने के बारे में बहुत सारे प्रकाशन हैं। उनमें से कुछ के नाम इस प्रकार हैं:
1. जेनेटिक एल्गोरिदम के साथ वाहन रूटिंग समस्या का समाधान
2. टाइम विंडोज के साथ वाहन रूटिंग समस्या के लिए एक हाइब्रिड एल्गोरिथ्म
3. टाइम-विंडोज के साथ वाहन रूटिंग समस्या के लिए रूट-निर्देशित हाइब्रिड जेनेटिक दृष्टिकोण