🎛️ تحسين دالة ذات فخاخ (وديان محلية)
دالة f(x) المراد تصغيرها. النزول الساذج يقع في أول دنوية محلية. أما التلدين المحاكى فيقبل أحيانًا الصعود — خاصة في البداية عندما تكون T مرتفعة — فيجد الدنوية الشاملة الحقيقية.
الحرارة
5.000
f(x) الحالية
—
أفضل قيمة موجودة
—
الكرة تتبع المنحنى. عند ارتفاع T، تقفز فوق الحواجز. وعندما تنخفض T، تستقر في أعمق وادٍ.
⚒️ الاستعارة الميتالورجية
منذ آلاف السنين، يعرف الحدادون والميتالورجيون تقنية التلدين: تسخين المعدن إلى درجة حرارة عالية جدًا، ثم تبريده ببطء شديد. النتيجة: تجد الذرات الوقت الكافي لإعادة تنظيم نفسها في بلورة مثالية بلا عيوب. يصبح المعدن أكثر صلابة وأقل هشاشة.
إذا برّدناه بسرعة كبيرة (السقي/الإخماد)، تبقى الذرات مجمدة في مواضع دون مثالية: فتظهر عيوب وإجهادات داخلية. يصبح المعدن صلبًا لكنه هش.
🎯 1983: كيركباتريك يترجم الفكرة إلى خوارزمية
سكوت كيركباتريك، سي. دانيال جيلات وماريو فيكي، باحثون في IBM، كانوا يعملون على تصميم VLSI (التكامل فائق الحجم للدارات): وضع ملايين الترانزستورات على رقاقة من أجل تصغير الطول الكلي للوصلات. مسألة صعبة من صنف NP.
كان لديهم الحدس التالي: أي نظام فيزيائي يبرد ببطء يجد حالة طاقته الدنيا (الحالة الأساسية). فلماذا لا نحاكي هذه الفيزياء لحل مسائل التحسين؟
في عام 1983، نشروا مقال « Optimization by Simulated Annealing » في مجلة Science. أصبح المقال من بين الأكثر استشهادًا في كل علوم الحاسوب النظرية.
🔥 الخوارزمية في 5 أسطر
- الانطلاق من حل ابتدائي x. تقييم كلفته E(x).
- في كل خطوة، نقترح اضطرابًا x' (جار عشوائي). ΔE = E(x') − E(x).
- إذا كانت ΔE < 0 (تحسّن): نقبل x → x'.
- إذا كانت ΔE > 0 (تدهور): نقبل باحتمال exp(−ΔE/T).
- نخفض الحرارة T (مخطط التبريد). نعيد من جديد.
معيار ميتروبوليس (1953)
P(القبول) = exp(−ΔE / T)
T كبيرة → نقبل كل شيء تقريبًا (استكشاف)
T صغيرة → لا نقبل سوى التحسينات (استغلال)
🌡️ مخططات التبريد
- هندسي: T_{n+1} = α · T_n مع α ∈ [0.8, 0.999]. الأكثر استخدامًا.
- لوغاريتمي: T_n = T₀ / log(n + 2). تقارب مضمون نظريًا (جيمان-جيمان 1984)، لكنه بطيء جدًا في الممارسة.
- خطي: T_n = T₀ · (1 − n/N).
- تكيفي: ضبط T حسب معدل القبول. أكثر تطورًا، ويُستخدم في الممارسة.
⚖️ الضمان النظري (جيمان-جيمان 1984)
إذا تناقصت الحرارة ببطء كافٍ (T_n ≥ C / log(n))، فإن التلدين المحاكى يتقارب نحو الأمثل الشامل باحتمال 1. وهذا ضمان فريد بين الخوارزميات الاستدلالية.
في الممارسة، نغش: نستعمل تبريدًا هندسيًا أسرع بكثير. فنفقد الضمان، لكننا نحصل على حلول ممتازة في وقت معقول.
🚀 تطبيقات ملموسة
- تصميم VLSI: وضع الترانزستورات على رقائق إنتل، AMD، آبل سيليكون. لا يزال مستخدمًا اليوم بالموازاة مع التلدين الكمومي (D-Wave).
- البائع المتجول (TSP): التلدين المحاكى أحد الخوارزميات المعيارية. يحل حالات من 10 000 مدينة في حدود 5 % من الأمثل.
- جدولة المواعيد: SNCF، إير فرانس، الجامعات. توزيع الدروس/الأساتذة/القاعات تحت قيود.
- معالجة الصور: ترميم الصور، التجزئة، إزالة الضجيج. حقل ماركوف.
- طي البروتينات: إيجاد التشكل ثلاثي الأبعاد ذي الطاقة الدنيا. قبل AlphaFold، كانت الطريقة المهيمنة.
- تحسين المحفظة المالية: ماركويتز مع قيود معقدة (أعداد صحيحة، معاملات، ضرائب).
- تخصيص الترددات: إسناد القنوات لهوائيات الهاتف المحمول (4G/5G) مع تجنب التشويش.
- تصميم الجزيئات: اكتشاف الأدوية، تحسين ارتباط الليغند بالبروتين.
- تحسين الشفرات: المترجمات، جدولة تعليمات المعالج CPU.
- تحليل الشفرات: كسر بعض أنظمة التشفير البسيطة (الإبدال، التبديل).
- الرياضة: تحسين رزنامة NBA، NFL، كأس العالم.
🌌 عائلة الخوارزميات الاستدلالية الفوقية المستوحاة من الأحياء
ينتمي التلدين المحاكى إلى عائلة كبيرة من الخوارزميات المستوحاة من الطبيعة:
- الخوارزميات الجينية (هولاند 1975): مجموعة سكانية، انتقاء، طفرة، تقاطع. تحاكي التطور الدارويني.
- تحسين سرب الجسيمات (Particle Swarm Optimization) (كينيدي-إبرهارت 1995): سرب الطيور.
- مستعمرات النمل (دوريغو 1992): الفيرومونات. ممتازة لمسألة TSP.
- الخوارزميات المناعية: تحاكي الجهاز المناعي.
- التلدين الكمومي (كادواكي-نيشيموري 1998): نسخة كمومية تستغل النفق الكمومي. قلب حواسيب D-Wave (أكثر من 5000 كيوبت في 2024).
🔍 مقارنة مع نزول التدرج
| الجانب | نزول التدرج | التلدين المحاكى |
|---|---|---|
| السرعة | سريع جدًا | بطيء |
| الدنوية الشاملة | لا (محاصر محليًا) | نعم (مقاربيًا) |
| الاتصال المطلوب | نعم (التدرج) | لا (التوافقي ممكن) |
| حالة الاستعمال | التعلم العميق، المحدب | صعب من صنف NP، متقطع |
📐 الرابط مع برنامجك الدراسي
- الدالة الأسية: exp(−ΔE/T) هي أساس معيار القبول. برنامج الثانية بكالوريا علوم رياضية.
- الاحتمالات: نقبل باحتمال معين. القانون المنتظم، المحاكاة. برنامج الثانية بكالوريا علوم رياضية.
- المتتاليات: الحرارة T_n متتالية (هندسية في الغالب). برنامج الأولى والثانية بكالوريا علوم رياضية.
- التقارب: دراسة التقارب نحو الأمثل. برنامج المتتاليات الثانية بكالوريا علوم رياضية.
- الترموديناميك / بولتزمان: التوزيع exp(−E/T) هو توزيع بولتزمان. الفيزياء الثانية بكالوريا.
- الطرق العددية: خوارزميات تكرارية. برنامج خيار المعلوميات.