كيفية تصميم وظيفة احتمالية القبول من أجل صلب محاكاة مع تكاليف متعددة مميزة؟

Question

انا استخدم محاكاة الصلب لحل مشكلة جدولة الموارد NP-Complete. لكل طلب مرشح للمهام أحسب العديد من التكاليف المختلفة (أو قيم الطاقة). بعض الأمثلة (على الرغم من أن التفاصيل ربما تكون غير ذات صلة بالسؤال):

• 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, ، ولل global_finish_time لأخذ الأسبقية split_cost.

لذا فإن سؤالي لتفكيك المكدس هو: كيف يمكنني تصميم وظيفة احتمالية القبول التي تأخذ طاقات متعددة في الاعتبار ولكنها تعتبر دائما الطاقة الأولى أكثر أهمية من الطاقة الثانية، وما إلى ذلك؟ وبعبارة أخرى، أود أن تمر old_cost و new_cost كما tuples من العديد من التكاليف وإرجاع قيمة معقولة.

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

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

على سبيل المثال، إذا كان Tuple من أعلى التكاليف (A، B، C) ومتاجر تكلفة الإدخال هو (x، y، z)، المزيج الخطي هو bcx + cy + z. بهذه الطريقة، بغض النظر عن مدى ارتفاع Z، لن يكون أكثر أهمية من قيمة X من 1.

يؤدي هذا إلى إنشاء "Jaggies" في وظيفة التكلفة، حيث يتم اكتشاف أقصى تكاليف جديدة. على سبيل المثال، إذا ارتفعت C ثم BCX وسيكون CEVEN كلاهما أعلى للحصول على إدخال معين (x و y و z) وهكذا سوف الاختلافات بين التكاليف. يعني اختلاف أعلى تكلفة أن احتمال القبول سينخفض، كما لو أن درجة الحرارة قد خفضت فجأة خطوة إضافية. في الممارسة العملية رغم أن هذه ليست مشكلة لأن الحد الأقصى للتكاليف يتم تحديثها عدة مرات فقط في البداية ولا تتغير لاحقا. أعتقد أن هذا قد ثبت أنه من الناحية النظرية أن تتقارب نتيجة صحيحة لأننا نعلم أن التكلفة ستقارب نحو قيمة أقل.

الشيء الوحيد الذي لا يزال هناك مشوش إلى حد ما هو ما يحدث عندما يكون الحد الأقصى للتكاليف 1.0 وأسفل، يقول 0.5. مع أقصى ناقلات (0.5، 0.5، 0.5) من شأنه أن يمنح هذا المزيج الخطي 0.5 * 0.5 * x + 0.5 * y + z، أي أن ترتيب الأسبقية عكس فجأة. أفترض أن أفضل طريقة للتعامل معها هي استخدام الحد الأقصى للمتجه لتوسيع نطاق جميع القيم إلى النطاقات المعطاة، بحيث يمكن أن تكون المعاملات هي نفسها دائما (قل، 100x + 10y + z). لكنني لم أحاول ذلك بعد.

Answer 1

mbeckish هو الصحيح.

هل يمكن أن تجعل مزيج خطي من الطاقات المختلفة، وضبط المعاملات؟

ربما سجل تحويلها داخل وخارج؟

لقد فعلت بعض MCMC باستخدام Metropolis-Hastings. في هذه الحالة، سأحدد احتمال السجل (غير الطبيعي) لحالة معينة (بالنظر إلى بظرتها)، وأجد أن طريقة لتوضيح تفكيري حول ما أريد.

Answer 2

وأود أن تلمح من خوارزمية تطورية متعددة الموضوعية (MOEA) ولديها انتقال إذا الكل من الأهداف تمر في وقت واحد مع acceptance_probability وظيفة أعطيتها. سيكون لهذا تأثير استكشاف جبهة باريتو كثيرا مثل المسامنة القياسية المحاكاة المستكشفات هضاب حلول الطاقة نفسها.

ومع ذلك، فإن هذا يتخلى عن فكرة وجود الأولوية الأولى.

من المحتمل أن تضطر إلى تعديل المعلمات الخاصة بك، مثل منحها درجة حرارة أولية أعلى.

Answer 3

سأعتبر شيئا على غرار:

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 4

ذلك يعتمد على ما تقصد به "الأسبقية". على سبيل المثال، ماذا لو deadline_cost انخفض بنسبة 0.001، ولكن global_finish_time تكلفة ترتفع بنسبة 10000؟ هل تعود 1.0، لأن deadline_cost انخفض، وهذا له الأسبقية على أي شيء آخر؟ يبدو أن هذا هو نداء الحكم الذي يمكنك فقط إجراءه، إلا إذا كان بإمكانك تقديم معلومات أساسية كافية حول المشروع حتى يتمكن الآخرون من اقتراح مكالمة حكمهم المستنيرة الخاصة بهم.