الانتقال إلى المحتوى
العودة إلى نتائج البحث

التلدين المحاكى - التحسين الاحتمالي

السنة
1983
النوع
Probabilistic metaheuristic / local search

هذا النص ترجمة آلية ولم تتم مراجعته بعد. اقرأ النص الأصلي بالإنجليزية

حجم الخط

ماذا تفعل؟

التلدين المحاكى هو استراتيجية بحث محلية احتمالية قدمها كيركباتريك وجيلات وفيتشي في عام 1983. وهي تحاكي عملية التلدين الفيزيائي في علم المعادن - حيث يتم تسخين المادة ثم تبريدها ببطء للوصول إلى حالة بلورية ذات طاقة منخفضة - وتستخدم هذا القياس لتجنب القيم المثلى المحلية في مشاكل التحسين التوافقية والمستمرة.

الفكرة الحدسية وراء الطريقة

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

التاريخ

تم تقديم التلدين المحاكى بواسطة كيركباتريك وجيلات وفيتشي في ورقتهم الرائدة عام 1983 في مجلة Science، والتي رسمت قياسًا صريحًا بين التلدين الديناميكي الحراري للمواد الصلبة والتحسين التوافقي. تم اقتراح نفس الفكرة بشكل مستقل من قبل سيرني (1985) في سياق مشكلة البائع المتجول. قدم فان لار هوفن وآرتس (1987) أول معالجة نظرية صارمة، وأثبتوا خصائص التقارب في ظل جداول تبريد مختلفة. منذ ذلك الحين، أصبحت هذه الطريقة واحدة من أكثر الاستراتيجيات الفوقية دراسة وتطبيقًا على نطاق واسع، وتستخدم في تصميم الهندسة، وبحوث العمليات، وتخطيط تخطيط الدوائر المتكاملة، وضبط المعلمات الفائقة للتعلم الآلي.

متى تُستخدم

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

الحدود والاعتبارات

  • جودة الحل حساسة لجدول التبريد؛ قد ينتج جدول سيء نتائج لا تختلف عن البحث العشوائي.
  • يجب تصميم بنية الجوار لكل فئة من فئات المشاكل، وهذا يتطلب خبرة في المجال.
  • التقارب إلى القيمة المثلى العالمية يتطلب تبريدًا بطيئًا للغاية في الممارسة العملية، مما يجعل وقت التشغيل طويلاً لضمانات الجودة العالية.
  • لا يستفيد من معلومات التدرج أو البنية، لذلك تتفوق عليه الطرق المعتمدة على التدرج في المشاكل السلسة والقابلة للتفاضل.

لا تغني شروط المصدر عن المراجعة العلمية المستقلة أو التحقق بواسطة محرك تحليل.

نقاط القوة

  • يمكن الهروب من القيم المثلى المحلية من خلال القبول الاحتمالي للحلول الأسوأ، على عكس التسلق الحاد البحت.
  • ينطبق على أي نوع من المشاكل تقريبًا - التوافقية، المستمرة، المختلطة - طالما تم تعريف بنية جوار.
  • لا يتطلب معلومات التدرج وهو غير مبالٍ بالبنية الرياضية لدالة الهدف.
  • لديه ضمان نظري للتقارب إلى القيمة المثلى العالمية في ظل تبريد بطيء بما فيه الكفاية (هاجيك 1988).
  • عدد قليل من المعلمات الفائقة: درجة الحرارة الأولية، معدل التبريد، وبنية الجوار.

التطبيقات

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

كيف يعمل

كيف يعمل

1

تبدأ الخوارزمية بحل مبدئي - أي نقطة ممكنة في مساحة البحث - ودرجة حرارة أولية عالية. يمكن أن يكون الحل المبدئي عشوائيًا أو خاصًا بالمشكلة؛ عادةً ما يتم تعيين درجة الحرارة الأولية لتكون عالية بما يكفي لقبول أي حل مجاور تقريبًا في البداية.

2

يتم إنشاء حل مجاور عن طريق تطبيق تغيير عشوائي صغير ("حركة") على الحل الحالي. يجب تخصيص بنية الجوار للمشكلة: بالنسبة لمشكلة جدولة قد تكون الحركة عبارة عن تبديل مهمتين؛ بالنسبة لدالة مستمرة قد تكون إضافة اضطراب عشوائي صغير إلى متجه المعلمات الحالي.

3

يتم حساب الفرق في قيمة الهدف بين الحل الجديد والحل الحالي. إذا كان الحل الجديد أفضل، يتم قبوله دائمًا. إذا كان أسوأ، يتم قبوله باحتمالية تتناقص مع حجم التدهور ودرجة الحرارة الحالية - عادةً exp(−ΔE / T). هذا القبول الاحتمالي هو الآلية الأساسية التي تمنع التقارب المبكر.

4

بعد كل تكرار (أو بعد عدد ثابت من التحركات عند نفس درجة الحرارة)، يتم تقليل درجة الحرارة وفقًا لجدول تبريد - عادةً جدول هندسي T ← α·T حيث α أقل بقليل من 1. يؤثر اختيار جدول التبريد بشكل كبير على جودة الحل: التبريد السريع جدًا يحبس البحث في قيمة مثلى محلية؛ التبريد البطيء جدًا يهدر وقت الحساب.

5

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

الأخطاء الشائعة

  • تشغيل عدد قليل جدًا من التكرارات (أقل من حوالي 1000) يمنع جدول التبريد من العمل بشكل صحيح ويترك البحث محصورًا في قيمة مثلى محلية - فضل البحث المحظور أو البحث المحلي الحتمي إذا كان وقت التشغيل محدودًا بشدة.
  • تعيين درجة الحرارة الأولية منخفضة جدًا يعني أن الخوارزمية تتصرف فورًا مثل التسلق الحاد الجشع وتفقد قدرتها على الهروب من القيم المثلى المحلية.
  • تعيين معدل التبريد بشكل عدواني جدًا (على سبيل المثال، α أقل من 0.9) يسبب تقاربًا مبكرًا؛ تحقق من جودة الحل النهائي عن طريق إعادة التشغيل من حلول أولية متعددة.
  • تطبيق حركة جوار مصممة لنوع مشكلة واحد على مشكلة مختلفة يمكن أن يجعل التحركات غير ممكنة أو غير ذات معنى - تحقق دائمًا من أن كل جار تم إنشاؤه هو حل صالح.
  • الإبلاغ عن الحالة النهائية فقط بدلاً من أفضل حل تم رؤيته على الإطلاق أثناء التشغيل يمكن أن يفوت القيمة المثلى الحقيقية التي تم العثور عليها في خطوة وسيطة.

الأسئلة الشائعة

كيف أختار جدول التبريد؟

الجدول الهندسي T ← α·T مع α بين 0.90 و 0.99 هو نقطة البداية الأكثر شيوعًا. نهج عملي هو تعيين درجة الحرارة الأولية عالية بما يكفي لقبول حوالي 80٪ من التحركات في البداية، ثم تقليلها حتى يتم قبول أقل من 1٪ من التحركات الصاعدة. إذا كانت جودة الحل النهائي ضعيفة، قم بإبطاء معدل التبريد (زيادة α)؛ إذا كان وقت التشغيل طويلاً جدًا، قم بتسريعه. قم دائمًا بتشغيل الخوارزمية عدة مرات من حلول أولية مختلفة لتقييم المتانة.

كيف يختلف التلدين المحاكى عن الخوارزميات الجينية أو تحسين سرب الجسيمات؟

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

هل القيمة المثلى العالمية مضمونة؟

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

متى يجب أن أفضل البحث المحظور أو الخوارزمية الجينية بدلاً من ذلك؟

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

طرق ذات صلة

المصادر

  1. Kirkpatrick, S., Gelatt, C.D. & Vecchi, M.P. (1983). Optimization by Simulated Annealing. Science, 220(4598), 671-680.

    افتح مرجع DOI
    تم النسخ.
  2. van Laarhoven, P.J.M. & Aarts, E.H.L. (1987). Simulated Annealing: Theory and Applications. Springer.

    ردمك: 9789027725431
    تم النسخ.