تحديد الوظيفة

Question

لدي وظيفة،

P (X0، X1، ...، XN)

يستغرق ذلك 100 أعداد صحيحة كمدخلات ويعطي كإخراج عدد صحيح. P هو وظيفة بطيئة لتقييم (يمكن أن تتراوح بين 30 ثانية إلى بضع دقائق).

أحتاج إلى معرفة قيم النقاط التي ستزيد من القيمة المفرطة من P.

ما هي التقنيات التي يمكنني استخدامها لإنجاز هذا؟ وأنا أعلم عموما أن الناس يستخدمون الخوارزميات الوراثية لهذا، لكنني أخشى أن تأخذ الأعمار لحسابها معهم، حتى مع عدد قليل من الأجيال والأجيال القليلة (دعنا نقول، السكان = 50، أجيال = 50)، ص كذلك بطيئة سوف يستغرق أكثر من 40 ساعة لحسابها.

هل هناك طريقة أرخص للقيام بذلك؟ ربما عملية تكرارية؟ لا أحتاج إلى أن أكون مثاليا للغاية، لكن ليس لدي أي أيديولوجية لكيفية تتصرف (لقد جربت خطية / تربيعية / أسية، لكن لا يبدو أنها تسفر عن أي قيم جيدة. أعرف P يمكن العودة القيم على الأقل 5-10 مرات أفضل مما أحصل عليه).

يجب أن يكون هناك شيء أسهل في التنفيذ (أي يجب أن أقوم بتطبيقه بنفسي).

شكرًا

تحرير: ص هي عملية عشوائية.

Answer 1

كخوارزميات من الخط الأول لهذا النوع من المشكلة، أود أن أوصي بصيل محاكاة. SA هو الخيار الأول كبير لأنه يمكنك التحكم بوضوح نقطة البداية ووقت التشغيل.

إذا كنت تعرف شيئا عن بنية مساحة 100 الأبعاد الخاصة بك، حيث يمكنك اختيار نقطة انطلاق جيدة ويمكن أن يكون لها تأثير كبير على جودة النتيجة. أيضا مع SA يمكنك التحكم في "معدل التبريد" الذي يؤثر على كل من وقت التشغيل وجودة نتائجك - بشكل طبيعي في اتجاهين متعاكسين. عادة ما يتم تشغيل معدل تبريد سريع نسبيا أولا للبحث عن ناقلات البدء الجيدة، ثم تباطأ معدل التبريد في عمليات التشغيل اللاحقة لتحسين النتائج. نوع من تقنية Meta-SA التي يمكن أن تكون آلية.

لقد استخدمت SA بنجاح لتعظيم الوظيفة العالية للغاية المستخدمة في تفاعلات النمذجة بروتون النمذجة في الماضي.

أيضا، أود أن أنظر إلى الأبعاد تقليل P () إذا كان ذلك ممكنا. لمشكلتك الخاصة، هناك حاجة كل 100 متغيرات؟ إذا كنت تستطيع إصلاح 1/2 من أولئك الذين ستعملون تسريع أي محسن وينتهي بهم الأمر بنتائج أفضل.

(و SA يسهل التنفيذ.)

Answer 2

محاكاة الصلب, ، ترتبط ارتباطا وثيقا ماركوف سلسلة مونت كارلو (MCMC). وبعد البديل ربما تريد هو metropolis-hastings.. وبعد عندما تحصل على تعليق منه، إنه لطيف تماما. ربما توجد بعض الطرق لتحسينها لأن المدخلات والنتيجة هي جميع الأعداد الصحيحة. إنه مناسب مكثف وقد يتطلب بعض الضبط، لكنه قوي للغاية، وأنا لست متأكدا من الطرق الأخرى التي يمكن أن تفعل أي أفضل.

إليك بعض الرمز الميت في الدماغ للقيام بذلك:

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

طرق TWEET هي توسيع أو تضييق توزيع الاقتراح، لذلك يتطلب الأمر خطوات أكبر أو أصغر، أو يمكنك الحصول عليها في البداية خطوات أكبر ثم خطوات أصغر. ما تبحث عنه هو نسبة مئوية من الخطوات التي يتم الاحتفاظ بها ليست عالية جدا ولا منخفضة للغاية. ربما ترغب في أن يكون لديك مرحلة "حرق" من العينات الأولية الأولى أو نحو ذلك التي تتخلص منها، بينما تطارد مساحة الوضع.

وبجميع الوسائل، يجب أن يكون الملف الشخصي P. في أسرع وقت ممكن. ها هي طريقتي المفضلة للقيام بذلك.

Answer 3

ربما جزء كبير من خوارزمية الخاص بك هو متوازي؟ إذا كان الأمر كذلك، فهل اعتبرك موازيا الكود الخاص بك؟

Answer 4

انظر إلى تقنيات تحسين الاستوكاستك المختلفة المدرجة هنا. وبعد أوصي محاكاة الصلب.

Answer 5

هناك الكثير من خوارزميات التحسين العالمية المعروفة (محاكاة الصلب، نفق الأسوشيكاستيك، إلخ ...) التي يمكن أن تجد الحد الأقصى العالمي، ولكن لا شيء مضمون للعثور عليه في غضون فترة زمنية معقولة دون تحقيق افتراضات حول شكل وظيفة.

لن تجد طريقة سريعة / سهلة لتحسين وظيفة 100 أبعاد وغير تافهة. ستحتاج إلى الكثير من قوة المعالجة والوقت. على افتراض أنك لا ترغب في كتابة رمز التحسين بنفسك (بناء على سؤالك)، ستحتاج أيضا إلى بعض برامج الرياضيات الجيدة (على سبيل المثال، Mathematica).

Answer 6

آخر ليس إجابة خطيرة تماما، ولكن الغذاء للفكر:

تتطلع هذه المشكلة إلى أن تكون كبيرة جدا بالحقوق التي يجب أن تحتاج إلى شيء مثل جهد Seti @ Home لحلها. تجعل الآلاف من أجهزة الكمبيوتر عمل خفيف معقول من هذا النوع من الأشياء. لكنني لست متأكدا من كيفية الوصول إلى الآلاف من مستخدمي الكمبيوتر للحصول على استخدام أجهزة الكمبيوتر الخاصة بهم.

في الواقع، أفعل. يرجى تحمل معي للحظة في تجاهل مشروعية كل شيء.

هناك botnets تديرها بعض الناس يختبئون وراء الستار الحديدي السابق. لقد رأيت مؤخرا عرضا لاستئجار الروبوتات 70 دولارا لمدة 24 ساعة. مجرد التفكير، الآلاف من أجهزة الكمبيوتر 0wned جاهزة للقيام العطاءات الخاصة بك! بدلا من امتلاك مواقع الإنترنت DDOS، يمكنك الحصول عليها في مشكلتك. :)

قطعتان نهائيين من المشورة بشأن هذا، على الرغم من:

• لا تدفع لهم ببطاقة الائتمان الخاصة بك :)
• لا تأخذ المشورة القانونية من الغرباء على ذلك :)

حظا طيبا وفقك الله!

Answer 7

الافتراضات:

أولا - يجب أن تكون المتغيرات عددا صحيحا.
ثانيا - الوظيفة الموضوعية P () غير خطية.

ملاحظة:

بشكل عام، من الصعب حل البرمجة الصحيحة غير الخطية. في الواقع، على النحو الموصى به أعلاه، قد تساعد تقريب حل عن طريق استرخاء القيود الصحيحة.

هناك تقنيات التحسين العامة غير المقيدة المتاحة. نهج واحد يأتي من التصميم التجريبي هو الاتصال "منهجية السطح الاستجابة". مفيدة للغاية عندما تكون تكلفة التجربة مهمة. يتمثل النهج في تشغيل مجموعة من التجارب من خلال البدء بنقطة واحدة وانحراف كل من مدخلاتك من خلال زيادة مجموعة. ثم قمت بحساب التدرج لكل إدخال وخذ خطوة في هذا الاتجاه لكل منهما، ثم كرر. فليتشر - الأساليب العملية للتحسين والصندوق إحصائيات الصندوق والإحصاءات للمجربين هي المكان المناسب للنظر.

Answer 8

الشبكات العصبية : د أو سلسلة تايلور ?

Answer 9

إذا كان لديك إمكانية الوصول إلى MATLAB، فيمكنك موازاة التعليمات البرمجية الخاصة بك بسرعة كبيرة وسهولة جدا. حتى أنه يمكن أن يجعل خطي بسيط لحلقات موازية مع parfor حلقة

Answer 10

إذا كان حل Microsoft هو خيار، تحقق من SOLVER FESTATION.. وبعد سمعت عن بودكاست سكوت هانزيلمان (#191).