البحث الجدولي المعتمد على الوكلاء — تحسين استدلالي متعدد الوكلاء موزع
- قدّمه
- Glover, F. (tabu search); multi-agent extension by various researchers in the 1990s–2000s
- السنة
- 1989–1995
- النوع
- Hybrid metaheuristic — agent-based distributed tabu search
- العائلة
- Simulation / optimization
هذا النص ترجمة آلية ولم تتم مراجعته بعد. اقرأ النص الأصلي بالإنجليزية
ماذا تفعل؟
يُدمج البحث الجدولي المعتمد على الوكلاء (ABTS) استدلال البحث الجدولي في إطار عمل متعدد الوكلاء حيث يقوم كل وكيل مستقل بتشغيل خيوط بحث جدولي مستقلة أو متعاونة، ويشارك الحلول الواعدة للهروب من النقاط المثلى المحلية واستكشاف مساحات البحث التوافقية أو المستمرة الكبيرة بشكل جماعي أكثر فعالية من تطبيق أحادي الخيط.
الفكرة الحدسية وراء الطريقة
يمكن للبحث الجدولي الكلاسيكي أن يعلق في استكشاف منطقة ضيقة حتى مع آلية الذاكرة قصيرة المدى. من خلال نشر وكلاء مستقلين متعددين، يحتفظ كل منهم بقائمة جدولة خاصة به وجواره، ينتشر البحث عبر نقاط بداية متنوعة. يتبادل الوكلاء بشكل دوري الحلول النخبوية (التكثيف) ويتفرقون عمدًا إلى مناطق غير مستكشفة (التنويع). يعكس هذا الهيكل التعاوني والمستقل في نفس الوقت سلوك أسراب الكائنات الحية — لا يمتلك وكيل واحد الصورة الكاملة، ومع ذلك يجد الجماعي حلولًا عالية الجودة بشكل أسرع بكثير من أي باحث فردي.
التاريخ
تمت صياغة البحث الجدولي بواسطة فريد جلوفر في 1986-1989. ظهرت المتغيرات الموزعة والمتوازية في أوائل التسعينيات حيث سعى الباحثون إلى استغلال معماريات المعالجات المتعددة. قدم Verhoeven و Aarts (1995) دراسة منهجية للبحث المحلي المتوازي بما في ذلك استراتيجيات الجدولة التعاونية. أصبح التأطير المعتمد على الوكلاء بارزًا في العقد الأول من القرن الحادي والعشرين مع دخول مفردات النمذجة المعتمدة على الوكلاء إلى بحوث العمليات.
متى تُستخدم
استخدم البحث الجدولي المعتمد على الوكلاء عند حل مشاكل التحسين التوافقية الصعبة أو المختلطة الأعداد الصحيحة (الجدولة، المسارات، تصميم الشبكات، تخصيص الموارد) حيث يتعثر البحث الجدولي أحادي الخيط وتتوفر موارد الحوسبة المتوازية. إنه فعال بشكل خاص عندما تحتوي مساحة البحث على العديد من النقاط المثلى المحلية ذات الجودة المتشابهة. تجنبه عندما تكون المشكلة صغيرة بما يكفي للمحللات الدقيقة (MILP، الفرع والحد)، عندما يكون التقييم الفردي مكلفًا للغاية حسابيًا (مما يجعل العديد من التقييمات المتوازية غير ممكنة)، أو عندما تتعارض متطلبات قابلية التكرار مع ديناميكيات التفاعل بين الوكلاء غير الحتمية.
الحدود والاعتبارات
- يمكن أن تلغي نفقات المزامنة وتكلفة الاتصال بين الوكلاء مكاسب التوازي على الأنظمة المرتبطة بإحكام أو الشبكات البطيئة.
- معلمات فائقة أكثر من البحث الجدولي أحادي الخيط: عدد الوكلاء، طوبولوجيا الاتصال، تردد المزامنة، ومشغلات التنويع كلها تتطلب ضبطًا.
- ضمانات التقارب النظرية أضعف من الطرق الدقيقة؛ تعتمد جودة الحل بشكل كبير على الضبط وهيكل المشكلة.
- صعوبة تحقيق قابلية التكرار لأن تفاعلات الوكلاء تقدم عشوائية إضافية تتجاوز التهيئة العشوائية.
لا تغني شروط المصدر عن المراجعة العلمية المستقلة أو التحقق بواسطة محرك تحليل.
نقاط القوة
- يقلل الاستكشاف المتوازي بشكل كبير من وقت الحل للمشاكل التوافقية الكبيرة مقارنة بالبحث الجدولي أحادي الخيط.
- يدعم إطار العمل متعدد الوكلاء التنويع بشكل طبيعي، مما يقلل من خطر التقارب المبكر إلى نقاط مثلى محلية سيئة.
- يسمح الهيكل المرن بوكلاء غير متجانسين بهياكل جوار مختلفة، أو استراتيجيات فترة جدولة مختلفة، أو حتى استدلالات مختلطة.
- ينقل مشاركة الحلول التعاونية الاكتشافات عبر الوكلاء، مما يسرع التكثيف حول المناطق عالية الجودة.
- يتوسع بشكل جيد مع نوى الحوسبة المتاحة، مما يجعله مناسبًا لبيئات الحوسبة الحديثة متعددة النوى والموزعة.
التطبيقات
- مسارات المركبات والخدمات اللوجستية: تنسيق وكلاء متعددين يقوم كل منهم بتحسين مشاكل فرعية للمسار.
- جدولة خطوط الإنتاج المرنة وجدولة الوظائف: يتعامل الوكلاء مع مجموعات فرعية من الآلات بشكل تعاوني.
- تصميم شبكات الاتصالات: تخصيص قنوات موزع وتحسين الطوبولوجيا.
- تخطيط سلسلة التوريد: تحسين المخزون والتوزيع متعدد المستويات.
- التنبؤ ببنية البروتين: بحث جوار متوازي عبر مساحات التكوين.
- جدولة أكاديمية وجدولة دورات دراسية بوكلاء على مستوى القسم الموزع.
كيف يعمل
كيف يعمل
تعريف مجموعة من الوكلاء المستقلين. يُعيّن لكل وكيل دور: يركز البعض على التكثيف (بحث محلي عميق حول المناطق الواعدة)، والبعض الآخر على التنويع (الهروب إلى مناطق غير مستكشفة). يحتفظ كل وكيل بقائمة جدولة خاصة به للحركات المحظورة، وحل حالي، وهيكل جوار مصمم خصيصًا لنوع المشكلة (مثل، تبديل، إدراج، أو حركات 2-opt للمشاكل التوافقية).
تهيئة الوكلاء بحلول بداية مميزة، إما تم إنشاؤها عشوائيًا أو تم بذرتها عبر استدلال بناء (مثل، أقرب جار للمسارات). التنوع بين حلول البداية أمر بالغ الأهمية — البدايات المتطابقة تؤدي إلى عمليات بحث متوازية متكررة. تقييم دالة الهدف لكل حل مبدئي وتسجيل أفضل حل عالمي عبر جميع الوكلاء.
ينفذ كل وكيل حلقة البحث الجدولي الخاصة به: إنشاء جوار الحل الحالي، تقييم جميع (أو مجموعة فرعية من) الحلول المجاورة، اختيار أفضل جار غير جدولي كخطوة تالية (معيار الطموح يسمح بتجاوز قائمة الجدولة إذا تجاوز المرشح أفضل حل عالمي)، وتحديث قائمة الجدولة بإضافة الحركة العكسية مع فترة بقاء مستمدة من نطاق ثابت أو قابل للتكيف.
يتواصل الوكلاء في فترات مزامنة محددة أو مشغلات أحداث. تشمل الاستراتيجيات الشائعة بث أفضل حل عالمي حالي لجميع الوكلاء (الذين قد يبدأون من جديد منه)، أو حقن الحل النخبوي في مجمع مشترك يستشيره الوكلاء بشكل دوري، أو تبادل الحلول من نظير إلى نظير بين الوكلاء المتجاورين في طوبولوجيا (حلقة، متصل بالكامل، أو عشوائي). تمنع ضوابط التنوع التقارب المبكر عن طريق معاقبة الوكلاء الذين لديهم حلول متطابقة.
إنهاء عند الوصول إلى ميزانية تكرار قصوى، أو حد زمني بالساعة، أو معيار ركود (مثل، عدم تحسن أفضل حل عالمي لعدد معين من التكرارات). اختيار أفضل حل عالمي تم العثور عليه عبر جميع الوكلاء عبر جميع التكرارات كناتج نهائي. اختياريًا، قم بالإبلاغ عن واجهة باريتو إذا تم تتبع أهداف متعددة.
الأخطاء الشائعة
- تعيين جميع الوكلاء لحلول بداية متطابقة يهدر القدرة المتوازية — تأكد من التهيئة المتنوعة.
- الاتصال المتكرر جدًا يجبر الوكلاء على الدخول في نفس حوض الحل، مما يلغي فوائد التنويع ويقلل البحث بشكل فعال إلى خيط واحد.
- تجاهل معيار الطموح في تصميم قائمة الجدولة يمكن أن يتسبب في تفويت الوكلاء لحلول أفضل بشكل واضح، خاصة في مرحلة البحث المبكرة.
- تطبيق ABTS على مشاكل يكون فيها تقييم الجوار مكلفًا للغاية بدون نموذج بديل سيؤدي إلى أوقات تشغيل باهظة.
الأسئلة الشائعة
كيف يختلف البحث الجدولي المعتمد على الوكلاء عن مجرد تشغيل خيوط بحث جدولي متعددة؟
الاختلاف الرئيسي هو التعاون. في عمليات التشغيل المتوازية المستقلة، لا تتبادل الخيوط المعلومات أبدًا. في ABTS، يتبادل الوكلاء بنشاط الحلول، أو يحدثون مجمع نخبة مشترك، أو يتبنون مشغلات تنويع بناءً على الحالة الجماعية — مما ينتج سلوك بحث ناشئ غائب عن العمليات المستقلة.
كم عدد الوكلاء الذين يجب أن أستخدمهم؟
نقطة انطلاق شائعة هي وكيل واحد لكل نواة معالج متاحة. تشير الأبحاث إلى تناقص العوائد بعد 8-16 وكيلًا لمعظم المشاكل التوافقية، مع زيادة نفقات الاتصال. تساعد التجارب التجريبية مع 4 و 8 و 16 وكيلًا في تحديد النقطة المثلى لمشكلة معينة.
هل يمكن لـ ABTS التعامل مع مشاكل متعددة الأهداف؟
نعم. يمكن للوكلاء الاحتفاظ بتقريبات محلية لواجهة باريتو ومشاركة الحلول غير المهيمنة عبر أرشيف مشترك. يُطلق على هذا أحيانًا اسم البحث الجدولي متعدد الأهداف المعتمد على الوكلاء وهو يختلف عن ABTS القياسي أحادي الهدف.
ما هي طوبولوجيا الاتصال الأفضل؟
توزع الطوبولوجيات المتصلة بالكامل الحلول الجيدة بأسرع ما يمكن ولكنها تخلق تكلفة اتصال عالية. توازن طوبولوجيات الحلقة أو العالم الصغير بين انتشار المعلومات والاستقلالية. بالنسبة لمعظم المشاكل العملية، تعمل طوبولوجيا الحلقة أو الطوبولوجيا العشوائية المتفرقة بشكل جيد كإعداد افتراضي.
متى يجب أن أفضل خوارزمية جينية أو سرب جسيمات على ABTS؟
فضل الطرق القائمة على المجموعات (GA، PSO) عندما تكون للمشكلة مساحة مستمرة وسلسة أو عندما تكون عوامل التقاطع/إعادة التركيب محددة جيدًا. يتفوق ABTS في المشاكل المنفصلة والتوافقية ذات عوامل الجوار المحددة جيدًا حيث توفر ذاكرة الجدولة ميزة بحث قوية.
طرق ذات صلة
المصادر
Glover, F. (1989). Tabu search — Part I. ORSA Journal on Computing, 1(3), 190–206.
افتح مرجع DOIتم النسخ.Verhoeven, M. G. A., Aarts, E. H. L. (1995). Parallel local search. Journal of Heuristics, 1(1), 43–65.
افتح مرجع DOIتم النسخ.