एकाधिक विशिष्ट लागतों के साथ अनुरूपित एनीलिंग के लिए स्वीकृति संभावना फ़ंक्शन कैसे डिज़ाइन करें?

Question

मैं एनपी-पूर्ण संसाधन शेड्यूलिंग समस्या को हल करने के लिए simulated annealing का उपयोग कर रहा हूं। प्रत्येक उम्मीदवार के कार्यों के आदेश के लिए मैं कई अलग-अलग लागत (या ऊर्जा मूल्य) की गणना करता हूं। कुछ उदाहरण हैं (हालांकि बारीकियों शायद सवाल के लिए अप्रासंगिक हैं):

• global_finish_time: दिन है कि अनुसूची स्पैन की कुल संख्या।
• split_cost: अन्य कार्यों द्वारा बाधाओं के कारण प्रत्येक कार्य में देरी होने की संख्या (यह एक बार शुरू होने के बाद किसी कार्य के बाधा को हतोत्साहित करने के लिए है)।
• deadline_cost: दिनों की स्क्वायर संख्या की राशि जिसके द्वारा प्रत्येक चूक की समयसीमा अतिदेय है।

पारंपरिक स्वीकृति संभावना समारोह इस (अजगर में) की तरह दिखता है:

def acceptance_probability(old_cost, new_cost, temperature): 
    if new_cost < old_cost: 
     return 1.0 
    else: 
     return math.exp((old_cost - new_cost)/temperature) 

अब तक मैं बस, उन्हें जोड़ने इतना है कि मैं में परिणाम फ़ीड कर सकते हैं द्वारा एक में मेरी पहली दो लागत संयुक्त है acceptance_probability। लेकिन मैं वास्तव में deadline_cost के लिए global_finish_time से अधिक प्राथमिकता लेने के लिए पर split_cost पर प्राथमिकता लेने के लिए वास्तव में चाहता हूं।

तो स्टैक ओवरफ़्लो पर मेरा प्रश्न यह है कि: मैं एक स्वीकृति संभावना फ़ंक्शन कैसे डिज़ाइन कर सकता हूं जो एकाधिक ऊर्जा को ध्यान में रखता है लेकिन हमेशा दूसरी ऊर्जा की तुलना में पहली ऊर्जा को अधिक महत्वपूर्ण मानता है, और इसी तरह? दूसरे शब्दों में, मैं old_cost और new_cost में कई लागतों के tuples के रूप में पास करना और एक समझदार मूल्य वापस करना चाहते हैं।

संपादित करें:, प्रस्तावित समाधान मैं यह निष्कर्ष निकाला है कि एक ही रास्ता है कि मेरे लिए काफी अच्छी तरह से काम करता है माइक Dunlavey के सुझाव है के साथ प्रयोग भले ही यह विभिन्न इकाइयों है कि लागत घटकों के साथ कई अन्य कठिनाइयों बनाता है के कुछ दिनों के बाद । मैं संतरे सेब से तुलना करने के लिए व्यावहारिक रूप से मजबूर हूँ।

तो, मैंने मानों को "सामान्यीकृत" करने में कुछ प्रयास किया। सबसे पहले, deadline_cost वर्गों का योग है, इसलिए यह अन्य घटकों को रैखिक रूप से बढ़ते समय तेजी से बढ़ता है। इसे संबोधित करने के लिए मैं समान विकास दर प्राप्त करने के लिए वर्ग रूट का उपयोग करता हूं। दूसरा, मैंने एक ऐसा फ़ंक्शन विकसित किया जो लागत के रैखिक संयोजन की गणना करता है, लेकिन अब तक देखे गए उच्चतम लागत वाले घटक के अनुसार गुणांक को स्वत: समायोजित करता है।

उदाहरण के लिए, यदि उच्चतम लागत का ट्यूपल (ए, बी, सी) है और इनपुट लागत वेक्टर (x, y, z) है, तो रैखिक संयोजन बीसीएक्स + सी + जेड है। इस तरह, इससे कोई फर्क नहीं पड़ता कि यह कितना उच्च जेड प्राप्त करता है, यह 1 मान के x मान से अधिक महत्वपूर्ण नहीं होगा।

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

एक चीज जो अभी भी मुझे कुछ उलझन में रखती है वह तब होता है जब अधिकतम लागत 1.0 और उससे कम होती है, 0.5 कहें। अधिकतम वेक्टर (0.5, 0.5, 0.5) के साथ यह रैखिक संयोजन 0.5 * 0.5 * x + 0.5 * y + z, i.e.प्राथमिकता का क्रम अचानक उलट दिया गया है। मुझे लगता है कि इससे निपटने का सबसे अच्छा तरीका अधिकतम वेक्टर का उपयोग सभी मानों को दिए गए श्रेणियों को स्केल करने के लिए करना है, ताकि गुणांक हमेशा एक जैसा हो (कहें, 100x + 10y + z)। लेकिन मैंने अभी तक कोशिश नहीं की है।

Answer 1

mbeckish सही है।

क्या आप विभिन्न ऊर्जा का रैखिक संयोजन बना सकते हैं, और गुणांक समायोजित कर सकते हैं?

संभावित रूप से उन्हें अंदर और बाहर लॉग-इन कर रहा है?

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

Answer 2

यह "प्राथमिकता लेता है" से आपका क्या मतलब है इस पर निर्भर करता है। उदाहरण के लिए, यदि deadline_cost 0.001 से नीचे चला जाता है, लेकिन global_finish_time लागत 10000 तक बढ़ जाती है? क्या आप 1.0 लौटते हैं, क्योंकि deadline_cost कम हो गया है, और यह किसी और चीज पर प्राथमिकता लेता है? ऐसा लगता है कि यह एक निर्णय कॉल है जो केवल आप कर सकते हैं, जब तक कि आप इस परियोजना पर पर्याप्त पृष्ठभूमि जानकारी प्रदान न कर सकें ताकि अन्य लोग अपने स्वयं के सूचित निर्णय कॉल का सुझाव दे सकें।

If (new deadline_cost > old deadline_cost) 
    return (calculate probability) 

else if (new global finish time > old global finish time) 
    return (calculate probability) 

else if (new split cost > old split cost) 
    return (calculate probability) 

else 
    return (1.0) 

पाठ्यक्रम तीन स्थानों पर आप की गणना संभावना एक अलग समारोह इस्तेमाल कर सकते हैं में से प्रत्येक के

:

Answer 3

मैं की तर्ज पर कुछ पर विचार करेंगे।

Answer 4

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

हालांकि, यह पहली बार प्राथमिकता लेने के विचार को छोड़ देता है।

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