आनुवंशिक एल्गोरिथ्म का उपयोग करके कंटेनरों में पैकेजिंग (बिन पैकिंग)

अच्छे दिन, सहकर्मियों।
इस लेख के साथ , मैं आनुवंशिक एल्गोरिथम द्वारा समस्याओं को हल करने के लिए EvoJ - Java फ्रेमवर्क को समर्पित श्रृंखला जारी रखता हूं।
अपने पिछले लेख में, मैंने EvoJ के साथ काम करने के बुनियादी सिद्धांतों के लिए Habr पाठकों को पेश किया।

आज हम इस बात पर ध्यान देंगे कि कंटेनर में पैकेजिंग की समस्या को ईवो कैसे हल कर सकता है।

समस्या का बयान

संक्षेप में, कंटेनरों में पैकिंग का कार्य निम्नानुसार किया गया है: एक निश्चित मात्रा के कंटेनरों का एक सेट है, और उन वस्तुओं का एक सेट जिसे इन कंटेनरों में पैक करने की आवश्यकता है (सरलतम मामले में, स्थानिक अभिविन्यास उपेक्षित है)। लक्ष्य संभव के रूप में कुछ कंटेनरों का उपयोग करते हुए, सभी वस्तुओं को ढेर करना है।

समाधान विवरण विधि चुनना

EvoJ का उपयोग करने के लिए, हमें किसी तरह से उन चरों का वर्णन करना चाहिए जो जावा इंटरफेस के रूप में समस्या का समाधान करते हैं।

पहला विकल्प प्रत्येक कंटेनर को उसमें गिरने वाली वस्तुओं की सूची के रूप में वर्णित करना है:

public interface Solution { List<List<Integer>> getContainers(); } 

वास्तव में, यह कंटेनरों की एक सूची है, जिनमें से प्रत्येक को भागों की एक सूची द्वारा वर्णित किया गया है जो इसमें गिर गए।

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

एक सरल दृष्टिकोण वर्णन करेगा कि किस कंटेनर में प्रत्येक विशिष्ट वस्तु गिर गई:

 public interface Solution { @ListParams(length = "itemsCount", elementRange = @Range(strict = "true", min = "0", max = "lastBinIndex"), elementMutationRange = @MutationRange(value = "100%")) List<Integer> getBinIndices(); } 

यहां समाधान को एक सूची के रूप में प्रस्तुत किया गया है, जिनमें से प्रत्येक तत्व इंगित करता है कि किस कंटेनर में संबंधित आइटम गिर गया।

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

स्वास्थ्य सुविधा चयन

प्राकृतिक फिटनेस फ़ंक्शन कब्जे वाले कंटेनरों की संख्या होगी, लेकिन यह दृष्टिकोण बहुत प्रभावी नहीं है। हम इसका कारण बताते हैं।

समाधान 1


निर्णय २


दोनों समाधान तीन कंटेनरों का उपयोग करते हैं। लेकिन, जाहिर है, दूसरा समाधान बेहतर है, क्योंकि दो कंटेनरों के कब्जे से पहले उसे केवल एक म्यूटेशन की जरूरत होती है। बेशक, पहले समाधान से, उत्परिवर्तन के परिणामस्वरूप, एक समाधान प्राप्त किया जा सकता है जहां केवल दो कंटेनरों का कब्जा है, लेकिन इसकी संभावना बहुत कम है।

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

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

हम समाधान का मूल्यांकन करने के लिए तीसरे संकेतक का परिचय देते हैं - वर्ग के अधिभार का योग।

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

 public class PackRating implements Comparable { private int binsUsed; private int score; private int overflow; public PackRating(int binsUsed, int score, int overflow) { this.binsUsed = binsUsed; this.score = score; this.overflow = overflow; } public int compareTo(Object o) { PackRating other = (PackRating) o; if (this.overflow != other.overflow) { return other.overflow - this.overflow; } if (this.binsUsed != other.binsUsed) { return other.binsUsed - this.binsUsed; } return this.score - other.score; } public int getBinsUsed() { return binsUsed; } public int getOverflow() { return overflow; } public int getScore() { return score; } } 

यहाँ binsUsed क्षेत्र में उपयोग किए जाने वाले कंटेनरों की संख्या है। score फ़ील्ड कंटेनरों में रिक्त स्थान के वर्गों का योग है। और अंत में, अतिप्रवाह क्षेत्र कंटेनर अधिभार के वर्गों का योग है।

तुलना प्रक्रिया किसी भी समाधान को भीड़ के बिना किसी भी समाधान से बेहतर मानती है, जब भीड़ बराबर होती है, व्यस्त कंटेनरों को ध्यान में रखा जाना शुरू होता है (कम बेहतर होता है), और अंत में, यदि समान संख्या में कंटेनरों पर कब्जा कर लिया जाता है, तो score फ़ील्ड (अधिक बेहतर) को ध्यान में रखा जाता है। ।

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

 public class BinPackRatingCalculator extends AbstractSimpleRating<Solution> { private int[] items; private int[] bins; public BinPackRatingCalculator(int[] items, int[] bins) { this.items = items; this.bins = bins; } @Override protected Comparable doCalcRating(Solution solution) { int[] tmpBins = new int[bins.length]; int score = 0; int overflow = 0; int binsUsed = 0; final List<Integer> indicex = solution.getBinIndices(); for (int item = 0; item < indicex.size(); item++) { Integer binIndex = indicex.get(item); tmpBins[binIndex] += items[item]; } for (int bin = 0; bin < tmpBins.length; bin++) { int dl = bins[bin] - tmpBins[bin]; final int dl2 = dl * dl; if (dl < 0) { overflow += dl2; } else { score += dl2; } if (tmpBins[bin] > 0) { binsUsed++; } } return new PackRating(binsUsed, score, overflow); } } 

हम इस कोड का विस्तार से विश्लेषण नहीं करेंगे, यह बस हमारे फिटनेस संकेतकों की गणना करता है और उन्हें PackRating वर्ग की एक आवृत्ति के रूप में वापस करता है।

सबकुछ बनाने का काम

main विधि के साथ एक नया वर्ग बनाएँ:

  public static void main(String[] args) { int[] items = {3, 2, 4, 4, 5, 3, 4, 5, 6}; int[] bins = {8, 8, 8, 8, 8, 4, 12, 12, 8, 6}; Map<String, String> context = new HashMap<String, String>(); context.put("itemsCount", Integer.toString(items.length)); context.put("lastBinIndex", Integer.toString(bins.length - 1)); DefaultPoolFactory factory = new DefaultPoolFactory(); GenePool<Solution> pool = factory.createPool(200, Solution.class, context); DefaultHandler handler = new DefaultHandler(new BinPackRatingCalculator(items, bins), null, null, null); handler.iterate(pool, 40); Solution bestSolution = pool.getBestSolution(); showSolution(bestSolution, bins, items); } 

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

जनसंख्या के आकार और पुनरावृत्तियों की संख्या को प्रयोगात्मक रूप से चुना जाता है।

उपरोक्त कोड बहुत तेज है, और मेरे चार साल पुराने लैपटॉप पर 200 समाधानों की आबादी पर 1000 पुनरावृत्तियों में लगभग दो सेकंड लगते हैं।

अंतभाषण

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

रुचि रखने वालों के लिए , माना गया उदाहरण का स्रोत कोड मावेन परियोजना के रूप में रखा गया है।

आपका ध्यान देने के लिए धन्यवाद।