الحلقة 3 : خوارزمية محاكاة التلدين – مثال Simulated Annealing Algorithm Example
السلام عليكم ورحمة الله وبركاته
نتابع ضمن هذه الحلقة الحديث عن خوارزمية محاكاة التلدين SA Algorithm
وكما ذكرنا في الحلقة السابقة, سندرج في هذه الحلقة مثال من كود بايثون يوضح لنا بشكل عملي وبسيط الخوارزمية
فيما يلي ادناه المخطط التالي عبارة عن تذكرة لخطوات الخوارزمية
مثال كود باثيون Python
يمثل الكود ادناه نسخة بسيطة جدا عن خوارزمية محاكاة التلدين SA.
حيث تعمد الخوارزمية على الحفاظ على افضل حل تصل اليه.
يمثل المثال السابق الهيكل الاساسي للخوارزمية, حيث يترك لك ملأ النقاط الهامة التي تم تمثيلها بشكل مجرد مثل:
تابع : Neighbor()
والذي يتم عبره توليد حل عشوائي مجاور random neighboring solution
التابع: cost()
يمثل تابع حساب الكلفة
تابع acceptance_probability()
وسنتحدث عنه بعد قليل.
تابع احتمال القبول acceptance probability function
يأخد هذا التابع كلفة الحل القديم old cost , كلفة الحل الجديد new cost, بالاضافة ا لى درجة الحرارة الحالية current temperature, ويكون خرج هذا التابع عبارة عن رقم يقع في المجال [0..1].
ويعتبر هذا الرقم بمثابة توصية توضح فيما اذا كان يتوجب الانتقال الى الحل الجديد ام لا.
على سبيل المثال:
- القيمة 1: حتما يتوجب الانتقال للحل الجديد ( الحل الجديد افضل من الحل السابق)
- القيمة 0: حتما يتوجب البقاء على الحل القديم ( الحل الجديد اسوء من الحل السابق)
- القيمة 0.5: النسب هي 50-50.
ما إن يتم حساب احتمال القبول acceptance probability, تتم مقارنة قيمتها مع رقم يتم توليده بشكل عشوائي وقيمته تقع في المجال بين الواحد والصفر.
في حال كانت قيمة احتمال القبول اكبر من الرقم العشوائي, عندها يتم الانتقال الى الحل الجديد!
حساب احتمال القبول Calculating the acceptance probability
تستخدم المعادلة التالية عادة من اجل حساب احتمال القبول:
حيث ان “الرمز الفا” يمثل احتمال القبول acceptance probability
تمثل الفرق بين كلفة الحل القديم وكلفة الحل الجديد
T عبارة عن درجة الحرارة temperature
E = 2.71828
عبارة عن ثابت رياضي.
تعتبر هذه المعادلة جزء من محاكاة التلدين Simulated annealing, وهي تمثل طاقة الجسيمات المعدنية عندما يتم تبريدها بشكل بطيء بعد تعرضها لدرجات حرارة عالية.
هذه العملية تسمح للجسيمات particles بالانتقال من تكوين عشوائي الى تكوين اخر اكثر انتظاما وبطاقة منخفضة.
يقترض علماء الحاسوب معادلة التلدين من اجل مساعدتهم في حل المسائل وذلك بالانتقال من حل عشوائي الى حل اخر اكتر انتظاما وبكلفة منخفضة.
تعني المعادلة السابقة بأن احتمال القبول acceptance probability:
- يكون دوما اكبر من “واحد” عندما يكون الحل الجديد افضل من الحل السابق ( كلفته اخفض)
- يصبح اصغر عندما يكون الحل الجديد new solution اسوء من الحل السابق.
- يصبح اصغر من تناقض درجة الحرارة ( اذا كان الحل الجديد اسوء من الحل القديم).
الخلاصة:
اذا كان لديك مسألة امثلة بحاجة لحل, يجب ان تختطر خوارزمية محاكاة التلدين الى بالك.
هنالك طبعا الكثير من الاستراتيجيات والخوارزميات غيرها
طبعا بالنهاية لسنا هنا لتزكية خوارزمية دون اخرى بشكل عام, حيث ان هنالك عدة طرق وخوارزميات وبعضها افضل من بعضها الاخر في حل نوع محدد من المسائل.
——————–
نكتفي بهذا القدر عند هذه الحلقة, والى اللقاء في حلقة قادمة من خوارزمية محاكاة التلدين
والى ذلك الحين نستودعكم الله والسلام عليكم ورحمة الله وبركاته
مع تحيات
م. نور الصباحي
سلسلة الحلقات
- خوارزمية محاكاة التلدين – الحلقة الاولى
- خوارزمية محاكاة التلدين – الحلقة الثانية
- خوارزمية محاكاة التلدين – مثال – الحلقة الثالثة
- خوارزمية محاكاة التلدين – برنامج التبريد – الحلقة الرابعة
- خوارزمية محاكاة التدلين – التطبيقات – الحلقة الخامسة والاخيرة
| المصطلح | الترجمة |
| temperature | الحرارة |
| parameter | معامل |
| internal thermal energy | الطاقة الداخلية الحرارية |
| stochastically | بشكل عشوائي |
| algorithm | خوارزمية |
| Crystal | بلوري |
| amorphous | غير متبلور |
| thermodynamics | الديناميك الحراري |
| annealing | التلدين |
| Optimization problems | مسائل الأمثلة |
| solid state | الحالة الصلبة |
| Liquid state | الحالة السائلة |
| stochastic computational method | طريقة عشوائية حسابية |
| المراجع |
|
Simulated Annealing Algorithms |
|
The Simulated Annealing Algorithm |
|
SIMULATED ANNEALING APPLICATIONS K. Nara Ibaraki University /2-1 Nakanarusawa 4 Chome Hitachi 316-8511 JAPAN |
|
An Introduction to Simulated Annealing https://www.aero.iitb.ac.in/~rkpant/webpages/DefaultWebApp/salect.pdf |
|
Simulated Annealing Link to download pdf document |
|
Simulated Annealing Link to download word document |
