محاكاة التلدين
محاكاة التلدينالخوارزمية هي خوارزمية احتمالية عامة تستخدم لإيجاد الحل الأمثل لقضية في مساحة بحث كبيرة.
مبدأ
بتطبيق نظرية الديناميكا الحرارية على الإحصاء، تخيل كل نقطة في مساحة البحث كجزيء في الهواء؛ طاقة الجزيء هي طاقته الحركية الخاصة به؛ وكل نقطة في فضاء البحث، مثل جزيء الهواء، تحمل "طاقة" تشير إلى درجة ملاءمة النقطة للاقتراح.
تبدأ الخوارزمية بنقطة عشوائية في مساحة البحث: في كل خطوة، يتم تحديد "جار" ثم يتم حساب احتمال الوصول إلى "الجار" من الموضع الحالي.
العناصر الأساسية
مساحة الحالة ووظيفة توليد الحالة
1) تسمى مساحة البحث أيضًا بمساحة الحالة، والتي تتكون من مجموعة الحلول الممكنة المشفرة.
2) يجب أن تضمن وظيفة توليد الحالة (وظيفة الجوار) أن الحلول المرشحة المولدة موزعة على مساحة الحل بأكملها قدر الإمكان. يتكون عادةً من جزأين، وهما طريقة توليد الحلول المرشحة وتوزيع احتمالات الحلول المرشحة.
3) يتم الحصول على الحلول المرشحة عمومًا عن طريق أخذ عينات عشوائية من مساحة الحل وفقًا لدالة كثافة احتمالية معينة.
4) يمكن أن يكون توزيع الاحتمالات توزيعًا موحدًا، أو توزيعًا طبيعيًا، أو توزيعًا أسيًا، وما إلى ذلك.
احتمالية انتقال الحالة
1) احتمالية انتقال الحالة تشير إلى احتمالية الانتقال من حالة إلى أخرى.
2) الفهم المشترك هو احتمال قبول الحل الجديد باعتباره الحل الحالي.
3) ترتبط بمعامل درجة الحرارة الحالية T وتنخفض مع انخفاض درجة الحرارة.
4) يتم اعتماد معيار المدينة بشكل عام.
معايير إنهاء الحلقة الداخلية
1) التحقق من استقرار متوسط دالة الهدف.
2) تتغير قيمة الهدف قليلاً على مدى عدة خطوات متتالية.
3) أخذ العينات وفقا لعدد معين من الخطوات.
معايير إنهاء الحلقة الخارجية
1) ضبط عتبة درجة الحرارة النهائية.
2) قم بتعيين عدد تكرارات الحلقة الخارجية.
3) القيمة المثلى التي تم البحث عنها بواسطة الخوارزمية تظل دون تغيير لعدة خطوات متتالية.
4) التحقق من استقرار إنتروبيا النظام.
الخطوات الرئيسية
دالة توليد الحالة الجديدة ← دالة قبول الحالة الجديدة ← معيار استقرار أخذ العينات ← دالة التبريد ← معيار نهاية التلدين
مزايا محاكاة التلدين
يمكن لخوارزمية محاكاة التلدين العثور على الحل الأمثل التقريبي للمشكلة بسرعة. في ظل فرضية إعداد المعلمات المناسبة، تتمتع خوارزمية محاكاة التلدين بكفاءة بحث عالية.