البحث الشجري المونت كارلو بالميزانية المتساوية مقابل جدولة القائمة بإعادة التشغيل العشوائي لسير عمل الرسوم البيانية الموجهة غير الدورية: دراسة حسابية مضبوطة بالميزانية المتساوية

غالبًا ما يُقترح البحث الشجري المونت كارلو (MCTS) لجدولة سير عمل الرسوم البيانية الموجهة غير الدورية (DAG). ومع ذلك، لا تجري العديد من الدراسات المقارنات الضرورية التي قد تتحدى هذا النهج من خلال تطبيق نفس الجهد البحثي على طريقة أبسط. تعالج هذه الدراسة هذه الفجوة من خلال بروتوكول مضبوط. تلقت جميع الطرق المُقيَّمة نفس الميزانية، والتي تتكون من عدد متساوٍ من الجداول المرشحة التي تم بناؤها وتقييمها. كان الذراع الرئيسي طريقة جدولة MCTS، بينما كانت جدولة القائمة بإعادة التشغيل العشوائي بدون شجرة بحث بمثابة الضابط. بالإضافة إلى ذلك، تم تضمين ذراع MCTS من نوع UCT الكتابي كمتتبع مسجل في نفس المجال. تم وضع خطة التحليل قبل جمع البيانات، وأكد مدقق مستقل أن جميع الجداول الـ 768 في مرحلة التأكيد كانت صالحة ولها أوقات إنجاز دقيقة. مع ميزانية أولية قدرها 2048 جدولًا مُقيَّمًا، كان أداء MCTS أسوأ بنسبة 2.88% من إعادات التشغيل العشوائية، مع فاصل ثقة 95% من [-3.62%، -2.15%]، وأظهرت 72 من 96 حالة محتفظ بها هامشًا إيجابيًا نسبيًا للأساس. لم يكن هذا العجز في الأداء بسبب نقص الميزانية؛ في مجموعة استكشاف منفصلة، تحسنت إعادات التشغيل بنسبة 1.85%، بينما اكتسب MCTS فقط 0.24%. والجدير بالذكر أن 700 من أصل 720 نتيجة أولية من MCTS كانت ببساطة هي البداية الدافئة التي تلقاها. ركزت قاعدة الاختيار المستخدمة بشكل حتمي على الطفل الأول الموسع، مما حافظ على الارتباط بين التجارب، بينما استفادت إعادات التشغيل من المكاسب في الذيول. تظل العلاقة السببية بزمن الإنجاز استنتاجًا. تشير خريطة هيكلية إلى حيث تتوقف الشجرة عن أن تكون فعالة: تتفوق إعادات التشغيل في سير العمل غير المنتظم المتناثر، ولا يُلاحظ فرق كبير في سير العمل الطبقي المنتظم، ولا توفر سير العمل الكثيف أي فرصة للتحسين. يؤدي تغيير قاعدة الاختيار إلى UCT الكتابي إلى تخفيف معظم العجز، مما يؤدي إلى تغيير بنسبة -0.26% مع فاصل ثقة 95% من [-0.71%، +0.23%]، على الرغم من أنه لا يعكس النتيجة. تقتصر النتائج على مجال اصطناعي مضبوط بأعداد مهام N في {8، 16، 32}، و2-8 معالجات، وميزانيات تصل إلى 2048، ولا يتم تقديم أي ادعاءات بشأن ميزانيات أكبر.

المصدر: arxiv.org