समारोह सन्निकटन

Question

मैं एक समारोह है,

पी (x0, x 1, ..., xn)

कि इनपुट के रूप में 100 पूर्णांक लेता है और आउटपुट के रूप में एक पूर्णांक देता है। पी मूल्यांकन करने के लिए एक धीमी गति है (यह 30 सेकंड से कुछ मिनट तक हो सकती है)।

मुझे पता है कि अंकों की जो मान पी

क्या तकनीक मैं यह पूरा करने के लिए उपयोग कर सकते से झुकेंगे मूल्य को अधिकतम जाएगा की जरूरत है? मुझे पता है कि आम तौर पर लोग इसके लिए अनुवांशिक एल्गोरिदम का उपयोग करते हैं, लेकिन मुझे डर है कि इसमें उनकी गणना करने के लिए उम्र लगेगी, यहां तक ​​कि एक छोटी आबादी और कुछ पीढ़ियों के साथ (मान लीजिए, आबादी = 50, पीढ़ियों = 50), पी ऐसा है इसे धीमा करने में 40 घंटे से अधिक समय लगेगा।

क्या ऐसा करने का कोई सस्ता तरीका है? शायद एक पुनरावृत्ति प्रक्रिया? मुझे इसे वास्तव में इष्टतम होने की आवश्यकता नहीं है, लेकिन मेरे पास यह व्यवहार करने की कोई विचार नहीं है कि यह कैसे व्यवहार करता है (मैंने रैखिक/वर्गिक/घातीय की कोशिश की है लेकिन यह किसी भी अच्छे मूल्य उत्पन्न नहीं कर रहा है। मुझे पता है पी वापस लौटा सकता है मुझे जो कुछ मिल रहा है उससे कम से कम 5-10 गुना बेहतर मूल्य)।

यह ऐसा कुछ होना चाहिए जो कार्यान्वित करना आसान हो (यानी, मुझे इसे स्वयं लागू करना होगा)।

धन्यवाद

संपादित करें: पी एक स्टोकास्टिक प्रक्रिया है।

Answer 1

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

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

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

इसके अलावा, यदि संभव हो तो मैं आयामी पी() को कम करने के लिए देखता हूं। आपकी विशेष समस्या के लिए, क्या सभी 100 चर आवश्यक हैं? यदि आप उनमें से 1/2 को ठीक कर सकते हैं तो आप किसी भी अनुकूलक को तेज करेंगे और बेहतर परिणामों के साथ समाप्त होंगे।

(और एसए को लागू करने के लिए आसान है।)

Answer 2

Neural networks: डी या Taylor series?

Answer 3

शायद आपके एल्गोरिदम का एक महत्वपूर्ण हिस्सा समांतर है? यदि हां, तो क्या आपने अपना कोड समानांतर माना है?

Answer 4

here सूचीबद्ध विभिन्न स्टोकास्टिक ऑप्टिमाइज़ेशन तकनीकों को देखें। मैं simulated annealing की अनुशंसा करता हूं।

Answer 5

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

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

Answer 6

एक और पूरी तरह से गंभीर जवाब है, लेकिन सोचा के लिए भोजन:

यह समस्या इतनी बड़ी है कि अधिकारों के द्वारा आप इसे हल करने के लिए एक SETI @ होम प्रयास की तरह कुछ की आवश्यकता चाहिए लग रहा है। हजारों कंप्यूटर इस तरह की चीज का उचित प्रकाश काम करते हैं। लेकिन मुझे यकीन नहीं है कि आप अपने कंप्यूटर का उपयोग प्राप्त करने के लिए हजारों कंप्यूटर उपयोगकर्ताओं तक कैसे पहुंचेंगे।

वास्तव में, मैं करता हूं। सभी की वैधता को अनदेखा करने में कृपया एक पल के लिए मेरे साथ भालू।

पूर्व लौह पर्दे के पीछे छिपे कुछ लोगों द्वारा संचालित बॉटनेट हैं। मैंने हाल ही में 24 घंटे के लिए $ 70 के लिए एक बॉटनेट किराए पर देने का प्रस्ताव देखा। बस सोचो, हजारों 0wned पीसी आपकी बोली लगाने के लिए तैयार हैं! उन्हें डीडीओएस इंटरनेट साइटों के बजाय, आप उन्हें अपनी समस्या पर मंथन कर सकते हैं।:)

दो इस के बारे में सलाह के अंतिम बिट, हालांकि:

• उन्हें अपने खुद के क्रेडिट कार्ड :) के साथ भुगतान न करें
• इतने पर अजनबियों से कानूनी सलाह न लें :)

शुभकामनाएं!

Answer 7

Simulated annealing, Markov Chain Monte Carlo (MCMC) से निकटता से संबंधित है। वे संस्करण जो आप शायद चाहते हैं Metropolis-Hastings है। जब आप इसे लटकाते हैं, तो यह काफी अच्छा है। संभवतः इसे अनुकूलित करने के कुछ तरीके हैं क्योंकि आपके इनपुट और परिणाम सभी पूर्णांक हैं। यह गणना-गहन है और कुछ ट्यूनिंग की आवश्यकता हो सकती है, लेकिन यह काफी मजबूत है, और मुझे यकीन नहीं है कि अन्य विधियां बेहतर हो सकती हैं। tweak करने के लिए इसे बढ़ाना या प्रस्ताव वितरण संकीर्ण करने के लिए कर रहे हैं

const int n = 100; // length of vector to optimize 
int a[n]; // the vector to optimize 
double P(a){..} // Get the probability of vector a. 
       // This is the function to optimize. 
// for a large number of a samples 
for (i = 0; i < large_number; i++){ 
    // get P(a) 
    double p = P(a); 
    // for each element of vector a 
    for (j = 0; j < n; j++){ 
    // get an amount by which to change it. This choice has to be symmetric. 
    // this is called the Proposal Distribution 
    int step = uniform_random_choice_from(-2, -1, 1, 2); 
    // make the change to a[j], and get p1, the new value of p 
    a[j] += step; 
    double p1 = P(a); 
    bool bKeepTheStep = true; 
    // if p1 is better than p, keep the step 
    // if p1 is worse than p, then keep the step p1/p of the time 
    if (p1 < p){ 
     bKeepTheStep = (unif(0,1) < p1/p); 
    } 
    if (bKeepTheStep) p = p1; 
    else a[j] -= step; 
    } 
    // now a is a sample, and p is its value 
    // record a and p 
} 
// what you have now is a large random sampling of vectors from distribution P 
// now you can choose the best one, the average, the variance, 
// any statistic you like 

तरीके, तो यह बड़ा या छोटा कदम उठा लेता है, या आप कर सकते हैं इसे शुरू में बड़ा ले:

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

और हर तरह से, प्रोफ़ाइल पी। इसे यथासंभव तेज़ी से होने की आवश्यकता है। Here's my favorite way to do that.

Answer 8

यदि आपके पास matlab तक पहुंच है, तो आप अपने कोड को बहुत तेज़ और आसानी से समानांतर कर सकते हैं। यहां तक ​​कि इसके लूप लूप

Answer 9

यदि कोई माइक्रोसॉफ्ट समाधान एक विकल्प है, तो Solver Foundation देखें। मैंने स्कॉट हंसेलमैन के पॉडकास्ट (#191) पर सुना।

Answer 10

अनुमान:

पहले - चर पूर्णांक होना चाहिए।
दूसरा - उद्देश्य कार्य पी() गैर-रैखिक है।

अवलोकन:

सामान्य, गैर रेखीय पूर्णांक प्रोग्रामिंग में हल करने के लिए बहुत मुश्किल है। हकीकत में, जैसा कि ऊपर अनुशंसित किया गया है, पूर्णांक प्रतिबंध को आराम से समाधान को गोल करने से मदद मिल सकती है।

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