الأمثَلة بالتلدين المحاكى

كثير من مسائل الأمثَلة تشبه محاولة التنقل في تضاريس وعرة وأنت في ظلام تام. دالة الكُلفة تحدّد «الارتفاع» عند كل نقطة، والهدف هو الوصول إلى أخفض وادٍ — أي النهاية الصغرى الشاملة. أبسط طريقة هي التحسين التكراري: في كل خطوة انتقل إلى حلّ مجاور كُلفته أقل. هذا الأسلوب يتقارب دائماً، لكنّ المشكلة أنه يتقارب نحو أقرب نهاية صغرى محلية، وقد تكون بعيدة تماماً عن الحل الأفضل.

في المسائل الصغيرة أو الملساء لا ضير في ذلك. لكن حين ننتقل إلى المسائل التوافقية الحقيقية — توزيع ملايين الترانزستورات على شريحة، توجيه شاحنة توصيل عبر مئات المدن، جدولة آلاف المهام — نجد أنّ سطح الكُلفة مليء بالنهايات الصغرى المحلية. المُحسِّن الجشع الذي ينطلق من نقطة عشوائية لن يصل تقريباً أبداً إلى النهاية الصغرى الشاملة.

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

الملاحظة الذكية التي قدّمها كيركباترك وجيلات وفيكّي هي أنّ هناك تناظراً عميقاً بين الحالتين: دالة الكُلفة في مسألة الأمثَلة تقابل طاقة المنظومة الفيزيائية، والحل المرشّح يقابل ترتيب الذرات. وكانت خوارزمية متروبولس — التي ظهرت عام 1953 لمحاكاة الاتزان الحراري — تقدّم بالفعل آلية لأخذ عيّنات من الترتيبات عند درجة حرارة معيّنة. الفكرة الجوهرية كانت: خفض الحرارة تدريجياً مع الوقت — أي نقل جدول التلدين من ورشة الحدّاد إلى عالم الأمثَلة.

خوارزمية متروبولس هي المحرّك الداخلي للتلدين المحاكى. في كل خطوة تقترح تعديلاً عشوائياً صغيراً على الحل الحالي، ثم تحسب مقدار التغيّر في الكُلفة $\Delta E$، وتقرّر: هل نقبل هذا التعديل أم نرفضه؟ قاعدة القرار بسيطة وأنيقة:

• إذا كان الحل الجديد أفضل ($\Delta E \leq 0$): اقبله دائماً.
• إذا كان الحل الجديد أسوأ ($\Delta E > 0$): اقبله بـاحتمال $\exp(-\Delta E / T)$.

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

تصوّر الأمر وكأنك ترمي عملة معدنية غير متوازنة. انحياز العملة يتحدّد بشيئين: كم هي سيئة الخطوة المقترحة ($\Delta E$)، وكم المنظومة ساخنة ($T$). خطوة أسوأ بفارق بسيط عند حرارة مرتفعة تُقبل شبه حتماً. خطوة أسوأ بكثير عند حرارة منخفضة تُرفض شبه حتماً. الجميل أنّ هذه الآلية البسيطة وحدها تكفي لضمان التقارب نحو النهاية الصغرى الشاملة — بشرط واحد: أن يكون جدول التبريد بطيئاً بما يكفي.

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

الورقة الأصلية استخدمت جدولاً هندسياً: $T_{k+1} = \alpha \cdot T_k$ حيث تتراوح $\alpha$ عادةً بين 0.9 و0.99. عند كل مستوى حرارة تُنفَّذ تكرارات كافية حتى تصل المنظومة إلى شبه اتزان قبل خفض الحرارة مجدداً. هناك أيضاً جداول أخرى كالتناقص الخطي والتناقص اللوغاريتمي ($T_k = C / \ln(1+k)$) الذي يملك ضماناً نظرياً بـالتقارب، لكنّه بطيء بدرجة لا تُحتمل عملياً.

في الممارسة، ضبط الجدول مزيج من الحدس والتجريب: ابدأ بحرارة عالية تكفي لقبول نحو 95% من الخطوات، ثم أبطئ التبريد في النطاق الذي تنخفض فيه نسبة القبول من 90% إلى 10% — هذا هو النطاق الحرج الذي يتشكّل فيه هيكل الحل — ثم برّد بسرعة في النهاية.

لو جمعنا كل ما سبق، يعمل التلدين المحاكى في أربع مراحل:

• التهيئة. اختر حلاً ابتدائياً عشوائياً $s$ واضبط درجة حرارة أوّلية مرتفعة $T_0$.
• الاقتراح. ولّد حلاً مجاوراً عشوائياً $s'$ للحل الحالي.
• القرار. احسب $\Delta E = \text{cost}(s') - \text{cost}(s)$. إن كان $\Delta E \leq 0$ اقبل $s'$. وإلا اقبله بـاحتمال $\exp(-\Delta E / T)$.
• التبريد. بعد عدد كافٍ من التكرارات عند الحرارة الحالية، خفّض $T$ وفق جدول التبريد. كرّر العملية حتى تقترب $T$ من الصفر أو يستقرّ الحل.

القرارات التصميمية المحورية ثلاثة: كيف تُعرِّف الجوار (أي ما الذي يُعدّ «تغييراً صغيراً»)، وكيف تضبط الحرارة الأوّلية، وأيّ جدول تبريد تختار. هذه القرارات تعتمد كلياً على طبيعة المسألة — لا يوجد إعداد سحري يصلح لكل شيء، وهذا في الوقت نفسه مصدر مرونة الأسلوب وتحدّيه.

الأساس النظري الذي يقف خلف التلدين المحاكى هو توزيع بولتزمان من الميكانيكا الإحصائية. الفكرة أنه عند الاتزان الحراري، منظومة فيزيائية عند حرارة $T$ تشغل الحالة $s$ بـاحتمال يتناسب مع $\exp(-E(s) / T)$. معنى ذلك أنّ الحالات منخفضة الطاقة مُرجَّحة أكثر بشكل أُسِّي، لكنّ الحالات مرتفعة الطاقة ليست مستحيلة — تظهر بتواتر يعتمد على الحرارة.

خوارزمية متروبولس تولّد سلسلة ماركوف توزيعها المستقر هو بالضبط توزيع بولتزمان عند الحرارة الحالية. حين تكون $T$ عالية يصير التوزيع شبه منتظم — كل الحالات مُستكشَفة. وحين تكون $T$ منخفضة تتركّز كتلة الاحتمال على الحالات ذات الطاقة (أو الكُلفة) الأدنى. ومع اقتراب $T$ من الصفر يتقارب التوزيع نحو كتلة نقطية عند النهاية الصغرى الشاملة.

مبرهنة التقارب تقول: إذا انخفضت الحرارة ببطء كافٍ ($T_k \geq C / \ln(1+k)$ حيث $C$ ثابت مرتبط بطبيعة سطح الطاقة)، فإن الخوارزمية تتقارب نحو النهاية الصغرى الشاملة باحتمال 1. ضمان قوي بلا شك — لكنّ معدّل التبريد المطلوب بطيء جداً للاستخدام العملي، ولذلك تلجأ التطبيقات الحقيقية إلى جداول أسرع وتقبل حلولاً قريبة من المثالية.

اختبرت الورقة الأصلية التلدين المحاكى على مسألتين من فئة NP-صعبة:

مسألة البائع المتجول (TSP) — المطلوب إيجاد أقصر مسار يزور كل مدينة مرة واحدة بالضبط. التعديل المحلي هنا هو ما يُعرف بتبديل 2-opt: تأخذ جزءاً من المسار وتعكس ترتيبه. جرّب كيركباترك وزملاؤه ذلك على حالات تتراوح بين مئات وآلاف المدن، فحصلوا على نتائج تنافس أفضل الخوارزميات المعروفة وقتها.

تقسيم البيانات البيانية لتصميم الدوائر (VLSI) — الهدف توزيع مكوّنات الدائرة على مجموعتين بحيث يقلّ عدد الأسلاك العابرة بينهما (ما يُسمّى «القطع»)، لأنّ ذلك يؤثّر مباشرةً في تكلفة التصنيع. التعديل المحلي هو نقل مكوّن من مجموعة إلى أخرى. النتيجة: التلدين المحاكى وجد تقسيمات أفضل بوضوح من التبريد المفاجئ (أي الأمثَلة الجشعة من نقطة عشوائية)، وهذا أثبت أنّ القبول المنضبط للخطوات الصاعدة ليس ترفاً بل ضرورة.

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