البحث العشوائي المحظور — استدلالي عشوائي مع ذاكرة
- قدّمه
- Glover, F. (base TS); stochastic extensions by various authors (1990s–2000s)
- السنة
- 1990s
- النوع
- Stochastic metaheuristic optimizer
- العائلة
- Simulation / optimization
هذا النص ترجمة آلية ولم تتم مراجعته بعد. اقرأ النص الأصلي بالإنجليزية
ماذا تفعل؟
البحث العشوائي المحظور (STS) هو امتداد للبحث المحظور الكلاسيكي الذي يُدخل العشوائية في مراحل استكشاف الجوار واختيار الحركة. من خلال الجمع بين ذاكرة الحظر — التي تمنع الحلول التي تمت زيارتها مؤخرًا — والقبول الاحتمالي أو أخذ عينات عشوائية للمرشحين، يتجنب STS التحسينات المحلية بشكل أكثر فعالية ويستكشف مناظر الحلول الوعرة التي قد يفشل البحث المحظور الحتمي في عبورها.
الفكرة الحدسية وراء الطريقة
يتنقل البحث المحظور الكلاسيكي في مساحة الحلول عن طريق الانتقال دائمًا إلى أفضل جار مسموح به، باستخدام ذاكرة قصيرة المدى (قائمة المحظورات) لمنع التكرار. عمليًا، ومع ذلك، فإن أفضل حركة مسموح بها لا تزال قادرة على حبس الخوارزمية في منطقة من المشهد. يُدخل البحث العشوائي المحظور عشوائية مُتحكم بها: يتم اختيار الحركة التالية بشكل احتمالي من مجموعة من الجيران المرشحين بدلاً من الاختيار الجشع، ويتم إدخال اضطرابات عشوائية بشكل دوري لتنويع البحث. هذا يحافظ على انضباط البحث المحظور الموجه بالذاكرة مع إضافة قوة الاستكشاف التي يفتقر إليها الانحدار الحتمي البحت.
التاريخ
تم تقديم البحث المحظور رسميًا بواسطة Fred Glover في عام 1986 وتم تفصيله في أوراق بارزة خلال 1989-1990. ظهرت الامتدادات العشوائية في التسعينيات عندما أدرك الباحثون أن تقييم الجوار الحتمي كان عنق زجاجة في المشاكل واسعة النطاق. تم دمج أخذ عينات المرشحين العشوائية، والقبول الاحتمالي للحركات، وحقن الضوضاء لتحسين التنويع، مما أدى إلى ما يسمى بشكل عام بالبحث العشوائي المحظور. تُطبق هذه التقنية على نطاق واسع في بحوث العمليات، وتصميم الهندسة، وتحسين المعلمات الفائقة للتعلم الآلي.
متى تُستخدم
استخدم البحث العشوائي المحظور عند حل مشاكل التحسين التوافقي أو المستمر ذات الصندوق الأسود مع مناظر وعرة ومتعددة الأنماط حيث تعلق خوارزميات البحث المحلي الحتمية باستمرار (مثل الجدولة، التوجيه، اختيار الميزات). إنه قيّم بشكل خاص عندما يكون تقييم الجوار الكامل مكلفًا حسابيًا، مما يجعل أخذ العينات العشوائية ضروريًا. لا تستخدم STS عندما تكون المشكلة محدبة أو أحادية النمط — فالطرق المعتمدة على التدرج أو الطرق الدقيقة أسرع وأمثل. تجنبها عندما تحتاج إلى تحسين عالمي مضمون، حيث لا يقدم STS ضمانًا للتقارب يتجاوز أفضل الحلول الموجودة استدلاليًا. تجنبها أيضًا عندما تكون دالة الهدف رخيصة التقييم بالكامل ويكون البحث المحظور الحتمي مع بحث شامل للجوار ممكنًا.
الحدود والاعتبارات
- لا يوجد ضمان نظري لإيجاد التحسين العالمي؛ تعتمد جودة الحل بشكل كبير على إعدادات المعلمات.
- تتطلب مدة الحظر وحجم قائمة المرشحين ضبطًا خاصًا بالمشكلة؛ تؤدي الخيارات السيئة إلى تقارب مبكر أو تقدم بطيء.
- التشغيلات العشوائية غير قابلة للتكرار بدون بذرة عشوائية ثابتة، مما يعقد المقارنة المعيارية والتدقيق.
- تنمو متطلبات الذاكرة مع حجم قائمة المحظورات؛ هناك حاجة لتمثيلات سمات الحظر للتعامل مع مساحات الحلول الكبيرة.
لا تغني شروط المصدر عن المراجعة العلمية المستقلة أو التحقق بواسطة محرك تحليل.
نقاط القوة
- يتجنب التحسينات المحلية بشكل أكثر فعالية من البحث المحظور الحتمي من خلال الجمع بين الذاكرة والاستكشاف الاحتمالي.
- يتكيف مع هياكل الجوار الكبيرة عن طريق أخذ عينات جزئية للمرشحين، مما يقلل من تكلفة الحساب لكل تكرار.
- تمنع ذاكرة الحظر التكرار، وهو وضع فشل شائع للطرق العشوائية البحتة مثل تسلق التل بإعادة التشغيل العشوائي.
- إطار عمل مرن: يمكن ضبط احتمال الاضطراب ومدة الحظر لتحقيق التوازن بين التكثيف والتنويع.
- قابل للتطبيق على كل من المشاكل التوافقية (TSP، الجدولة) والتحسين المستمر مع تعديل طفيف.
التطبيقات
- تحسين توجيه المركبات واللوجستيات في ظل الطلب غير المؤكد
- جدولة ورش العمل والمصانع ذات أوقات المعالجة العشوائية
- اختيار الميزات في مجموعات بيانات التعلم الآلي عالية الأبعاد
- تصميم الشبكات وتحسين الطوبولوجيا
- تحسين المحفظة مع قيود اختيار الأصول التوافقية
- ضبط المعلمات الفائقة لنماذج المحاكاة المعقدة
كيف يعمل
كيف يعمل
إنشاء حل أولي x0 (عشوائيًا أو استدلاليًا). تعيين قائمة المحظورات T إلى فارغة، وتحديد مدة الحظر tau، وحد التكرار I_max، والمعلمات العشوائية (مثل حجم قائمة المرشحين k، احتمال الاضطراب p_perturb).
في كل تكرار، قم بأخذ عينة عشوائية لمجموعة فرعية N_s من الجوار الكامل N(x_current) بدلاً من تقييم جميع الجيران. هذا يقلل من تكلفة كل تكرار ويُدخل العشوائية في المناطق التي يتم استكشافها من الفضاء.
اختر الحل التالي x_next من N_s: إما (أ) اختر أفضل مرشح غير محظور باحتمال 1-p_perturb، أو (ب) باحتمال p_perturb اختر مرشحًا عشوائيًا غير محظور للتنويع. قد تتجاوز معايير الطموح حالة الحظر إذا كان x_next يحسن أفضل حل معروف.
أضف x_current (أو سمة الحركة) إلى قائمة المحظورات T. قم بإزالة أقدم إدخال إذا كان |T| > tau. قم بتحديث أفضل حل قائم x_best إذا كان f(x_next) < f(x_best).
كرر أخذ عينات الجوار عبر تحديث الحظر حتى يتم الوصول إلى I_max تكرار، أو يتم تحقيق قيمة هدف مستهدفة، أو لم يحدث تحسن خلال فترة صبر. أعد x_best كحل نهائي.
الأخطاء الشائعة
- ضبط مدة الحظر قصيرة جدًا يسمح بالتكرار على الرغم من قائمة المحظورات؛ طويلة جدًا تمنع المناطق الواعدة دون داع.
- استخدام قائمة مرشحين صغيرة جدًا (أخذ عينات جزئية مكثفة) يمكن أن يجعل البحث يفقد الجيران الجيدين باستمرار.
- إهمال معايير الطموح يتسبب في رفض الخوارزمية للحركات التي تحسن الحل العالمي والتي تكون محظورة عن طريق الخطأ.
- الإبلاغ عن تشغيل واحد فقط بدون عمليات إعادة تشغيل متعددة أو بذور يعطي صورة مضللة لجودة الحل النموذجية.
- الخلط بين البحث العشوائي المحظور والتلدين المحاكى: كلاهما عشوائي ولكنهما يختلفان اختلافًا جوهريًا — يستخدم STS ذاكرة صريحة بينما يستخدم SA القبول الاحتمالي المستند إلى درجة الحرارة بدون ذاكرة.
الأسئلة الشائعة
كيف يختلف البحث العشوائي المحظور عن التلدين المحاكى؟
كلاهما من الاستدلاليات العشوائية، لكن STS يستخدم ذاكرة حظر صريحة لمنع الحركات التي تمت زيارتها مؤخرًا، مما يمنع التكرار. SA ليس لديه ذاكرة — فهو يقبل الحلول الأسوأ باحتمال يتناقص بمرور الوقت (جدول درجة الحرارة). يعتبر STS بشكل عام أقوى في المشاكل التوافقية حيث يكون إعادة زيارة الحركات خطرًا واضحًا.
كم عدد التكرارات (I_max) التي يجب أن أعمل بها؟
لا توجد قاعدة عالمية. الممارسة الشائعة هي إجراء تجارب مستقلة متعددة (مثل 30-10 إعادة تشغيل) بميزانية تتناسب مع حجم المشكلة، ثم الإبلاغ عن أفضل النتائج ومتوسطها. للمقارنة المعيارية، قم بمطابقة ميزانية تقييم الوظائف الإجمالية التي تستخدمها الطرق المنافسة.
هل يمكن للبحث العشوائي المحظور التعامل مع المتغيرات المستمرة؟
نعم، ولكنه يتطلب تعريف جوار مستمر (مثل اضطراب غاوسي حول الحل الحالي) وسمة مناسبة لقائمة المحظورات (مثل منطقة أو اتجاه). تستهدف معظم أدبيات STS المشاكل التوافقية؛ بالنسبة للمساحات المستمرة، غالبًا ما تكون خوارزميات التطور التفاضلي أو CMA-ES بدائل أكثر طبيعية.
ما هو دور معايير الطموح؟
تتجاوز معايير الطموح حالة الحظر للحركة إذا كان قبولها ينتج عنه حل أفضل من أفضل حل تم العثور عليه حتى الآن. بدون الطموح، قد ترفض الخوارزمية بشكل دائم الحركات التي تحسن الحل العالمي والتي تكون محظورة، مما يحد بشدة من جودة الحل.
هل يجب عليّ تثبيت البذرة العشوائية لضمان قابلية التكرار؟
نعم، قم بتثبيت البذرة عند الإبلاغ عن النتائج في البحث لضمان قابلية التكرار. في الممارسة العملية، قم بالتشغيل باستخدام بذور متعددة والإبلاغ عن الإحصائيات (المتوسط، الأفضل، الانحراف المعياري) لإعطاء صورة موثوقة لأداء الخوارزمية عبر المشهد العشوائي.
طرق ذات صلة
المصادر
Glover, F. (1990). Tabu search: A tutorial. Interfaces, 20(4), 74-94.
افتح مرجع DOIتم النسخ.Hu, J., Fu, M. C., & Marcus, S. I. (2007). A model reference adaptive search method for global optimization. Operations Research, 55(3), 549-568.
افتح مرجع DOIتم النسخ.