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

في كل خطوة، تأخذ خوارزمية التلدين المحاكي بعين الاعتبار حالة مجاورة s* للحالة الحالية s ، وتقرر احتماليًا بين نقل النظام إلى الحالة s* أو البقاء في الحالة s . تؤدي هذه الاحتمالات في النهاية إلى انتقال النظام إلى حالات طاقة أقل. عادةً، تُكرر هذه الخطوة حتى يصل النظام إلى حالة مناسبة للتطبيق، أو حتى استنفاد ميزانية الحوسبة المحددة.

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

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

احتمالية الانتقال من الحالة الحالية${\displaystyle s}$إلى ولاية جديدة مرشحة${\displaystyle s_{\mathrm {new} }}$يتم تحديدها بواسطة دالة احتمالية القبول${\displaystyle P(e,e_{\mathrm {new} },T)}$وهذا يعتمد على الطاقات${\displaystyle e=E(s)}$و${\displaystyle e_{\mathrm {new} }=E(s_{\mathrm {new} })}$من بين الحالتين، وعلى معلمة عالمية متغيرة مع الزمن${\displaystyle T}$تُسمى درجة الحرارة . الحالات ذات الطاقة الأقل أفضل من تلك ذات الطاقة الأعلى. دالة الاحتمال${\displaystyle P}$يجب أن يكون إيجابياً حتى عندما${\displaystyle e_{\mathrm {new} }}$أكبر من${\displaystyle e}$تمنع هذه الميزة الطريقة من أن تتعثر عند الحد الأدنى المحلي الذي يكون أسوأ من الحد الأدنى العالمي.

متى${\displaystyle T}$عندما يقترب الاحتمال من الصفر،${\displaystyle P(e,e_{\mathrm {new} },T)}$يجب أن يؤول إلى الصفر إذا${\displaystyle e_{\mathrm {new} }>e}$وتكون قيمتها موجبة في غير ذلك. بالنسبة للقيم الصغيرة بما فيه الكفاية لـ${\displaystyle T}$وبالتالي، سيفضل النظام بشكل متزايد التحركات التي تؤدي إلى انخفاض الطاقة (أي إلى قيم طاقة أقل)، ويتجنب تلك التي تؤدي إلى ارتفاعها .${\displaystyle T=0}$يختزل الإجراء إلى الخوارزمية الجشعة ، التي تقوم فقط بالانتقالات الهابطة.

في الوصف الأصلي لعملية التلدين المحاكي، الاحتمالية${\displaystyle P(e,e_{\mathrm {new} },T)}$كانت تساوي 1 عندما${\displaystyle e_{\mathrm {جديد} <e}$أي أن العملية كانت تتجه دائمًا نحو الأسفل عندما تجد سبيلًا لذلك، بغض النظر عن درجة الحرارة. ولا تزال العديد من أوصاف وتطبيقات التلدين المحاكي تعتبر هذا الشرط جزءًا من تعريف الطريقة. ومع ذلك، فإن هذا الشرط ليس ضروريًا لعمل الطريقة.

ال${\displaystyle P}$عادةً ما يتم اختيار الدالة بحيث يقل احتمال قبول النقلة عندما يكون الفرق${\displaystyle e_{\mathrm {جديد} }-e}$تزداد احتمالية حدوث تحركات صعودية صغيرة أكثر من التحركات الكبيرة. ومع ذلك، فإن هذا الشرط ليس ضروريًا تمامًا، شريطة استيفاء الشروط المذكورة أعلاه.

بالنظر إلى هذه الخصائص، فإن درجة الحرارة${\displaystyle T}$يلعب دورًا حاسمًا في التحكم في تطور الدولة${\displaystyle s}$من حيث حساسية النظام لتغيرات طاقات النظام. وبشكل أدق، بالنسبة لـ${\displaystyle T}$تطور${\displaystyle s}$يكون حساسًا لتغيرات الطاقة الأكبر حجمًا، بينما يكون حساسًا لتغيرات الطاقة الأصغر حجمًا عندما${\displaystyle T}$صغير.

سريع

بطيء

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

يتطلب اسم الخوارزمية ومصدر إلهامها التحكم في تغير درجة الحرارة. وهذا يستلزم خفض درجة الحرارة تدريجيًا مع تقدم المحاكاة. تبدأ الخوارزمية مبدئيًا بـ${\displaystyle T}$يتم ضبطها على قيمة عالية، ثم يتم تقليلها في كل خطوة وفقًا لجدول تلدين معين - والذي يمكن للمستخدم تحديده ولكن يجب أن ينتهي بـ${\displaystyle T=0}$مع اقتراب نهاية الوقت المخصص. وبهذه الطريقة، من المتوقع أن يتجول النظام في البداية نحو منطقة واسعة من فضاء البحث تحتوي على حلول جيدة، متجاهلاً السمات الصغيرة لدالة الطاقة؛ ثم ينجرف نحو مناطق الطاقة المنخفضة التي تصبح أضيق، وأخيراً يتحرك نزولاً وفقاً لخوارزمية الانحدار الأسرع .

بالنسبة لأي مسألة محدودة معينة، فإن احتمال انتهاء خوارزمية التلدين المحاكي بحل أمثل شامل يقترب من 1 مع تمديد جدول التلدين. ^{[ 12 ]} ومع ذلك، فإن هذه النتيجة النظرية ليست مفيدة بشكل خاص، لأن الوقت اللازم لضمان احتمال نجاح كبير سيتجاوز عادةً الوقت اللازم لإجراء بحث كامل في فضاء الحلول . ^{[ 13 ]}

يمكن نمذجة التلدين المحاكي كمسار عشوائي على رسم بياني للبحث، حيث تمثل رؤوسه جميع الحالات الممكنة، والحواف التي تربط هذه الرؤوس تمثل التحركات المرشحة. من المتطلبات الأساسية لدالة neighbor() أن توفر مسارًا قصيرًا بما فيه الكفاية على هذا الرسم البياني من الحالة الابتدائية إلى أي حالة قد تكون الأمثل عالميًا - أي يجب أن يكون قطر الرسم البياني للبحث صغيرًا. في مثال البائع المتجول أعلاه، على سبيل المثال، تحتوي مساحة البحث لـ n = 20 مدينة على n! = 2,432,902,008,176,640,000 (2.4 كوينتيليون) حالة؛ ومع ذلك، فإن عدد جيران كل رأس هو   ${\displaystyle \sum _{k=1}^{n-1}k={\frac {n(n-1)}{2}}=190}$الحواف (القادمة من${\displaystyle n \choose 2}$، وقطر الرسم البياني هو${\displaystyle n-1}$.

لتحليل سلوك خوارزمية التلدين المحاكي على مسألة معينة، قد يكون من المفيد النظر في احتمالات الانتقال الناتجة عن خيارات التصميم المختلفة التي تم اتخاذها في تنفيذ الخوارزمية. لكل حافة${\displaystyle (s,s')}$في مخطط البحث، يُعرَّف احتمال الانتقال بأنه احتمال انتقال خوارزمية التلدين المحاكي إلى الحالة ${\displaystyle s'}$عندما تكون حالتها الحالية${\displaystyle s}$يعتمد هذا الاحتمال على درجة الحرارة الحالية كما هو محدد بواسطة الدالة temperature() ، وعلى ترتيب توليد الحركات المرشحة بواسطة الدالة neighbor() ، وعلى دالة احتمال القبول P() . لاحظ أن احتمال الانتقال ليس ببساطة${\displaystyle P(e,e',T)}$لأن المرشحين يخضعون للاختبار بشكل متسلسل.

يُعدّ تحديد الدوال neighbor() و P() و temperature() زائداً جزئياً. عملياً، من الشائع استخدام دالة القبول P() نفسها للعديد من المسائل، وتعديل الدالتين الأخريين وفقاً لطبيعة المسألة.

في صياغة كيركباتريك وآخرون للطريقة، عُرِّفت دالة احتمال القبول P(e, e', T) بأنها تساوي 1 إذا كان e' < e ، و exp(-(e'-e)/T) فيما عدا ذلك. وقد بُرِّرَت هذه الصيغة ظاهريًا بالقياس على انتقالات نظام فيزيائي؛ فهي تُطابق خوارزمية متروبوليس-هاستينغز ، في حالة T=1 وتوزيع الاقتراح في متروبوليس-هاستينغز متناظر. مع ذلك، يُستخدم احتمال القبول هذا غالبًا في التلدين المحاكي حتى عندما لا تكون دالة neighbor() ، المُماثلة لتوزيع الاقتراح في متروبوليس-هاستينغز، متناظرة، أو غير احتمالية على الإطلاق. ونتيجةً لذلك، لا تُطابق احتمالات الانتقال في خوارزمية التلدين المحاكي انتقالات النظام الفيزيائي المُماثل، ولا يُشترط أن يُشابه التوزيع طويل الأمد للحالات عند درجة حرارة ثابتة T توزيع التوازن الديناميكي الحراري لحالات ذلك النظام الفيزيائي، عند أي درجة حرارة. ومع ذلك، فإن معظم أوصاف التلدين المحاكي تفترض دالة القبول الأصلية، والتي من المحتمل أن تكون مضمنة بشكل ثابت في العديد من التطبيقات.

في عام 1990، اقترح موسكاتو وفونتاناري ^{[ 14 ]} ، وبشكل مستقل ديوك وشوير ^{[ 15 ]،} أن التحديث الحتمي (أي الذي لا يعتمد على قاعدة القبول الاحتمالية) يمكن أن يُسرّع عملية التحسين دون التأثير على الجودة النهائية. وخلص موسكاتو وفونتاناري، من خلال ملاحظة تشابه منحنى "الحرارة النوعية" لعملية التلدين "التحديث العتبي" في دراستهما، إلى أن "عشوائية تحديث متروبوليس في خوارزمية التلدين المحاكي لا تلعب دورًا رئيسيًا في البحث عن القيم الدنيا شبه المثلى". وبدلاً من ذلك، اقترحا أن "تنعيم سطح دالة التكلفة عند درجات الحرارة العالية والتحديد التدريجي للقيم الدنيا أثناء عملية التبريد هما العنصران الأساسيان لنجاح التلدين المحاكي". وقد شاع استخدام هذه الطريقة لاحقًا تحت مسمى "القبول العتبي" نسبةً إلى تسمية ديوك وشوير. في عام 2001، أظهر فرانز وهوفمان وسالامون أن استراتيجية التحديث الحتمية هي بالفعل الاستراتيجية المثلى ضمن فئة كبيرة من الخوارزميات التي تحاكي المشي العشوائي على سطح التكلفة/الطاقة. ^{[ 16 ]}

عند اختيار مولد المرشح neighbour()، يجب مراعاة أنه بعد بضع دورات من خوارزمية التلدين المحاكي، من المتوقع أن تكون طاقة الحالة الحالية أقل بكثير من طاقة الحالة العشوائية. لذلك، وكقاعدة عامة، ينبغي توجيه المولد نحو التحركات المرشحة التي تكون فيها طاقة حالة الوجهة أقل.${\displaystyle s'}$من المرجح أن يكون الوضع مشابهًا للوضع الحالي. تميل هذه الطريقة الاستدلالية (وهي المبدأ الأساسي لخوارزمية متروبوليس-هاستينغز ) إلى استبعاد التحركات المرشحة الجيدة جدًا وكذلك السيئة جدًا ؛ ومع ذلك، فإن الأولى عادةً ما تكون أقل شيوعًا بكثير من الثانية، لذا فإن هذه الطريقة الاستدلالية فعالة بشكل عام.

في مسألة البائع المتجول المذكورة أعلاه، على سبيل المثال، من المتوقع أن يكون لتبديل مدينتين متتاليتين في جولة منخفضة الطاقة تأثير طفيف على طاقتها (طولها)؛ بينما من المرجح أن يؤدي تبديل مدينتين عشوائيتين إلى زيادة طولها أكثر من تقليله. وبالتالي، من المتوقع أن يكون أداء مولد الجوار بالتبديل المتتالي أفضل من أداء مولد التبديل العشوائي، على الرغم من أن الأخير قد يوفر مسارًا أقصر نوعًا ما إلى الحل الأمثل (مع${\displaystyle n-1}$عمليات الاستبدال، بدلاً من${\displaystyle n(n-1)/2}$).

ويمكن صياغة القاعدة الاستدلالية بشكل أدق على أنه ينبغي تجربة الحالات المرشحة الأولى${\displaystyle s'}$والتي${\displaystyle P(E(s),E(s'),T)}$كبير. بالنسبة لدالة القبول "القياسية"${\displaystyle P}$أعلاه، هذا يعني أن${\displaystyle E(s')-E(s)}$وهو في حدود${\displaystyle T}$أو أقل. وبالتالي، في مثال البائع المتجول أعلاه، يمكن استخدام neighbour()دالة تبدل بين مدينتين عشوائيتين، حيث يتلاشى احتمال اختيار زوج من المدن كلما زادت المسافة بينهما عن${\displaystyle T}$.

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

كقاعدة عامة، يستحيل تصميم مولد مرشحين يحقق هذا الهدف ويُعطي الأولوية للمرشحين ذوي الطاقة المتقاربة. من ناحية أخرى، يمكن في كثير من الأحيان تحسين كفاءة التلدين المحاكي بشكل كبير من خلال تغييرات بسيطة نسبيًا في المولد. في مسألة البائع المتجول، على سبيل المثال، ليس من الصعب عرض مسارين.${\displaystyle A}$،${\displaystyle B}$، بأطوال متساوية تقريبًا، بحيث (1)${\displaystyle A}$(2) هو الأمثل، كل تسلسل من عمليات تبديل أزواج المدن التي تحول${\displaystyle A}$ل${\displaystyle B}$يخوض جولات أطول بكثير من كليهما، و(3)${\displaystyle A}$يمكن تحويلها إلى${\displaystyle B}$عن طريق قلب (عكس ترتيب) مجموعة من المدن المتتالية. في هذا المثال،${\displaystyle A}$و${\displaystyle B}$تقع في "أحواض عميقة" مختلفة إذا كان المولد يقوم فقط بتبديل الأزواج العشوائي؛ لكنها ستكون في نفس الحوض إذا كان المولد يقوم بقلب القطاعات العشوائي.

يفترض التشبيه الفيزيائي المستخدم لتبرير عملية التلدين المحاكي أن معدل التبريد منخفض بما يكفي لضمان اقتراب التوزيع الاحتمالي للحالة الراهنة من حالة التوازن الديناميكي الحراري في جميع الأوقات. مع ذلك، يعتمد زمن الاسترخاء - أي الوقت اللازم لاستعادة التوازن بعد تغير درجة الحرارة - اعتمادًا كبيرًا على "تضاريس" دالة الطاقة ودرجة الحرارة الراهنة. في خوارزمية التلدين المحاكي، يعتمد زمن الاسترخاء أيضًا على المولد المرشح، بطريقة معقدة للغاية. تجدر الإشارة إلى أن جميع هذه المعلمات تُقدم عادةً كدوال صندوق أسود لخوارزمية التلدين المحاكي. لذلك، لا يمكن تحديد معدل التبريد الأمثل مسبقًا، بل يجب تعديله تجريبيًا لكل مسألة. تعالج خوارزميات التلدين المحاكي التكيفية هذه المشكلة بربط جدول التبريد بتقدم البحث. أما الأساليب التكيفية الأخرى، مثل التلدين المحاكي الديناميكي الحراري ^{[ 17 ]} ، فتُعدّل درجة الحرارة تلقائيًا في كل خطوة بناءً على فرق الطاقة بين الحالتين، وفقًا لقوانين الديناميكا الحرارية.