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

यदि आपको अनुकूलन समस्याओं और खोज अनुमानों से परिचय की आवश्यकता है, तो आप नीचे दी गई पोस्ट पढ़ सकते हैं।

ग्राफ़ रंग

आइए ग्राफ़ रंग की समस्या से शुरुआत करें। बाधा प्रोग्रामिंग की अवधारणाओं को स्पष्ट करने के लिए इस समस्या का उपयोग पूरे पोस्ट में किया गया है।

किसी दिए गए मानचित्र के लिए, आप प्रत्येक देश को रंगना चाहते हैं। आपके पास असीमित मात्रा में रंग हैं. निकटवर्ती देशों को एक जैसा रंग देने की अनुमति नहीं है। मानचित्र को भरने के लिए आपको न्यूनतम कितने रंगों की आवश्यकता होगी?

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

आसान लगता है? व्यवहार में यह कठिन हो सकता है! यहाँ अफ़्रीका के लिए समाधान का एक भाग है:

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

बाधा प्रोग्रामिंग क्या है?

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

मूल बातें

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

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

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

खोज

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

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

आप विभिन्न प्रकार की खोज लागू कर सकते हैं। समस्या के आधार पर, आप सर्वश्रेष्ठ चुन सकते हैं (या उन सभी को आज़मा सकते हैं):

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

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

• यादृच्छिकीकरण और पुनः आरंभ
  यादृच्छिक क्रम में विभिन्न समाधानों को आज़माना भी संभव है। आप बस बेतरतीब ढंग से चर के लिए मान चुनते हैं और जांचते हैं कि समाधान संभव है या नहीं। यदि कुछ समय या कई प्रयासों के बाद भी कोई समाधान नहीं मिलता है, तो आप खोज फिर से शुरू करते हैं।

बाधा भंडार

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

यहां विभिन्न प्रकार की बाधाएं हैं जिन्हें आप बाधा भंडार में जोड़ सकते हैं:

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

• निरर्थक बाधाएँ
  निरर्थक बाधा एक ऐसी बाधा है जो किसी समाधान को बाहर करने में कोई मूल्य नहीं जोड़ती है। लेकिन अनावश्यक बाधाएं कम्प्यूटेशनल रूप से महत्वपूर्ण हैं, क्योंकि वे खोज स्थान को कम करते हैं। एक निरर्थक बाधा किसी ऐसी चीज़ को पकड़ लेती है जो संभव नहीं है लेकिन बाधा में कैद नहीं होती है। ग्राफ़ रंग में एक उदाहरण: रंगों की संख्या देशों की संख्या से अधिक नहीं हो सकती।
• सरोगेट बाधाएं
  मौजूदा बाधाओं को मिलाकर, आपको सरोगेट बाधाएं मिलती हैं। सरोगेट बाधाएँ सहायक होती हैं क्योंकि वे अधिक वैश्विक दृष्टिकोण प्रदान करती हैं। एक उदाहरण मौजूदा बाधाओं का विलय करना या उनका एक रैखिक संयोजन लेना है।
• निहित बाधाएं
  एक अन्य प्रकार की बाधाएं जिन्हें आप जोड़ सकते हैं वे अंतर्निहित बाधाएं हैं। कई मौजूदा बाधाओं से एक संपत्ति प्राप्त करना निहित बाधाएं देता है।

सीपी और एमआईपी के बीच क्या संबंध है?

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

मिश्रित पूर्णांक प्रोग्रामिंग क्या है?

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

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

सीपी और एमआईपी कैसे संबंधित हैं?

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

निष्कर्ष

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

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

नीचे आप गणितीय अनुकूलन के बारे में अधिक पोस्ट पा सकते हैं।

संबंधित