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

🎛️ تحسين دالة ذات فخاخ (وديان محلية)

دالة f(x) المراد تصغيرها. النزول الساذج يقع في أول دنوية محلية. أما التلدين المحاكى فيقبل أحيانًا الصعود — خاصة في البداية عندما تكون T مرتفعة — فيجد الدنوية الشاملة الحقيقية.

الحرارة الابتدائية

T_{0}

: 5.0

معامل التبريد α : 0.995

الحرارة

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 (- Δ \frac{E}{T})$

T كبيرة → نقبل كل شيء تقريبًا (استكشاف)
T صغيرة → لا نقبل سوى التحسينات (استغلال)

🌡️ مخططات التبريد

هندسي: T_{n+1} = α · T_n مع α ∈ [0.8, 0.999]. الأكثر استخدامًا.
لوغاريتمي: T_n = $T_{0}$ / log(n + 2). تقارب مضمون نظريًا (جيمان-جيمان 1984)، لكنه بطيء جدًا في الممارسة.
خطي: T_n = $T_{0}$ · (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) هو توزيع بولتزمان. الفيزياء الثانية بكالوريا.
الطرق العددية: خوارزميات تكرارية. برنامج خيار المعلوميات.

التلدين المحاكى نموذج مدرسي عن التقاطع العميق بين الفيزياء والمعلوميات. مهارة حرفية عمرها آلاف السنين (الحدادة)، صاغتها الفيزياء الإحصائية لبولتزمان (1872)، ثم نقلتها IBM إلى خوارزمية تحسين عام 1983، وهي اليوم تساعد على تصميم الرقائق التي تشغّل هذا المقال الذي تقرؤه. حلقة جميلة تربط بين الإنسان والمادة والخوارزمية.

🎯

تحقّق من فهمك

٣ أسئلة قصيرة للتأكد من مكتسباتك. يمكنك إعادة المحاولة.

)؟","options":["لتجنب الوقوع في فخ الأدنى المحلي واستكشاف مناطق أخرى","لتسريع التقارب نحو الأدنى الشامل","لأن الخوارزمية ترتكب أخطاء حسابية عند درجة حرارة عالية","لضمان انخفاض درجة الحرارة بشكل أسرع"],"correct":0,"explanation":"يقبل التلدين المحاكى أحيانًا التدهورات باحتمال \\exp\\left(-\\dfrac{\\Delta E}{T}\\right)

لكي يتمكن من تجاوز الحواجز والإفلات من الأدنيات المحلية. هذا هو المبدأ الأساسي الذي يميزه عن الانحدار الساذج. القبولات ليست أخطاء بل استراتيجية متعمدة للاستكشاف.&#34;},{&#34;q&#34;:&#34;في مخطط التبريد الهندسي

T_{n+1} = \\alpha \\cdot T_n

،ماهيقيمة

\\alpha

المستخدمة عادة في الممارسة العملية؟&#34;,&#34;options&#34;:[&#34;

\\alpha = 0.95

&#34;,&#34;

\\alpha = 0.5

&#34;,&#34;

\\alpha = 1.1

&#34;,&#34;

\\alpha = 2.0

&#34;],&#34;correct&#34;:0,&#34;explanation&#34;:&#34;يشير النص إلى أن

\\alpha \\in [0.8, 0.999]

بالنسبةللتبريدالهندسي،لذافإن

\\alpha = 0.95

قيمةنموذجية.قيمةمثل

0.5

ستبردبسرعةكبيرة،بينما

\\alpha > 1

سترفع درجة الحرارة بدلاً من خفضها.&#34;},{&#34;q&#34;:&#34;ما هو الفرق الرئيسي بين الضمان النظري لـ Geman-Geman (1984) والاستخدام العملي للتلدين المحاكى؟&#34;,&#34;options&#34;:[&#34;تتطلب النظرية تبريدًا لوغاريتميًا بطيئًا جدًا، لكن في الممارسة نستخدم تبريدًا هندسيًا سريعًا دون ضمان&#34;,&#34;تضمن النظرية حلًا دقيقًا فوريًا، لكن في الممارسة تكون الخوارزمية بطيئة دائمًا&#34;,&#34;تنطبق النظرية فقط على المسائل المتصلة، لكن في الممارسة نستخدمها على المسائل المتقطعة&#34;,&#34;تفرض النظرية

T_0 = 5

،لكنفيالممارسةنختاردائمًا

T_0 > 100

&#34;],&#34;correct&#34;:0,&#34;explanation&#34;:&#34;يوضح النص بشكل جلي: يضمن Geman-Geman التقارب نحو الأمثل الشامل إذا كان

T_n \\geq \\dfrac{C}{\\log(n)}$ (تبريد لوغاريتمي)، لكن هذا بطيء جدًا. في الممارسة، نستخدم «حيلة» بتبريد هندسي أسرع بكثير، فنفقد الضمان النظري لكن نحصل على حلول ممتازة في وقت معقول."}]">

← أطلس المفاهيم يُثرى الأطلس كل أسبوع

Disponible dans 0 jour

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

🎛️ تحسين دالة ذات فخاخ (وديان محلية)

⚒️ الاستعارة الميتالورجية

🎯 1983: كيركباتريك يترجم الفكرة إلى خوارزمية

🔥 الخوارزمية في 5 أسطر

🌡️ مخططات التبريد

⚖️ الضمان النظري (جيمان-جيمان 1984)

🚀 تطبيقات ملموسة

🌌 عائلة الخوارزميات الاستدلالية الفوقية المستوحاة من الأحياء

🔍 مقارنة مع نزول التدرج

📐 الرابط مع برنامجك الدراسي

تحقّق من فهمك