الحلقة 2 : خوارزمية محاكاة التلدين Simulated Annealing Algorithm
السلام عليكم ورحمة الله وبركاته
نتابع ضمن هذه الحلقة الحديث عن خوارزمية محاكاة التلدين SA Algorithm
حيث تحدثنا في الحلقة السابقة عن منشأ الخوارزمية, والقوانين الفيزيائية التي تعمل الخوارزمية على محاكاتها.
اما في هذه الحلقة فسوف نتحدث عن سبب استخدام هذه الخوارزمية, بالاضافة الى شرح مبسط عن الخوارزمية
لماذا خوارزمية محاكاة التلدين Why Simulated Annealing Algorithm
كما نعلم, هنالك العديد من خوارزميات الامثلة optimization algorithms مثل:
- خوارزمية تسلق الهضبة Hill climbing algorithm – سنقدم سلسلة عنها ايضا ان شاء الله في المستقبل
- الخوارزميات الجينية Genetic Algorithms
- Gradient descent
- ….
في الواقع, تكمن قوة خوارزمية محاكاة التلدينSA في قدرتها على تجنب السقوط بالنهايات العظمى المحلية local maxima.
وتكاد تكون الحلول solutions التي تقدمها الخوارزمية افضل من غيرها من الخوارزميات, ولكنها ليست الأفضل على الاطلاق.
يمكن تصور ذلك عن طريق تخيل رسم ثنائي البعد 2D – كما هو موضح بالشكل ادناه, حيث تمثل كل نقطة من الاحداثيات الواقعة على محور x حلا من الحلول ( على سبيل المثال خط سير معين بالنسبة لمسألة البائع المتجول salesman problem ).
وتمثل كل نقطة احداثيات على محور y مدى جودة هذا الحل ( على سبيل المثال, عكس قيمة المسافة المقطوعة بالنسبة لمسار من مسارات البائع المتجول – المقصود بعكس القيمة اي انه كل ما قصر المسار, كل ما كان الحل افضل, وبالتالي عكس القيمة تمثل الجودة في هذه الحالة)
بشكل عام, تبحث خوارزميات الامثلة عن أفضل حل, وذلك عبر توليد عدد من الحلول العشوائية البدائية, ومن ثم تقوم الخوارزمية باستكشاف المنطقة المجاورة ضمن فضاء الحل. في حال كان الحل المجاور افضل من الحل الحالي, عندها فإنه يتم الانتقال الى الحل الجديد. وإلا, فإن الخوارزمية تبقى على الحل الحالي
هذا يبدوا منطقيا جدا, ولكنه قد يؤدي حالات, حيث تعلق الخوارزمية في اماكن مثلى محلية sub-optimal places.
في المخطط ادناه, تم تحديد الحل الافضل بنجمة صفراء.
ولكن في حال وجدت خوارزمية بسيطة طريقها الى النجمة الخضراء – احد الحلول في الرسم – عندها لن تتحرك من عنده, حيث ان كل الحلول المجاورة اسوء منه.
تمثل النجمة الخضراء حل امثلي محلي sub-optimal local solution.
ملاحظة:
المقصود بحل امثلي محلي, اي انه افضل حل ضمن منطقة الجوار المعرفة له, ولكنه ليس الافضل على الاطلاق ضمن فضاء الحل.
تضيف محاكاة الصلب الكمية الصحيحة من العشوائية الى الاشياء بهدف الهروب من النهايات المحلية العظمى في بداية اجرائية العمل.
بالاضافة الى ذلك, فإن خوارزمية محاكاة التلدين ليست صعبة التنفيذ, على الرغم من اسمها المرعب 🙂
الخوارزمية
سنطرح ونقدم الخوارزمية عبر شرح عام وبسيط, قد نلجأ ضمن حلقات قادمة الى شرح تقني ومدعم بالرياضيات
فيما يلي سنقدم مخطط عام عن الخوارزمية, متجاوزين بذلك عدد من الخطوات المهمة, التي سنعود لذكرها بعد قليل.
- في البداية, توليد حل عشوائي random solution
- حساب الكلفة باستخدام احد التوابع التي قمت بتعريفها.
- توليد حل عشوائي مجاور random neighboring solution
- حساب كلفة الحل الجديد solution cost
- اجراء المقارنات التالية:
- اذا كانت (كلفة الحل الجديد “اصغر” من كلفة الحل القديم) =< عندها يتم الانتقال الى الحل الجديد
- اذا كانت (كلفة الحل الجديد “أكبر” من كلفة الحل القديم) =< “ربما” يتم الانتقال الى الحل الجديد.
- اعادة الخطوات من الثالثة حتى الخامسة حتى الوصول الى حل مقبول, او تصل الخوارزمية الى الحد الاعلى المسموح من التكرارات.
لنحلل الآن الخوارزمية الى قطع صغيرة:
الخطوة الأولى: توليد حل عشوائي.
بإمكانك تنفيذ هذه الطريقة بالشكل الذي تريد. النقطة الاساسية المهمة هي العشوائية – لا يتوجب ان تكون افضل تمثيل يخطر ببالك للحل المثالي.
الخطوة الثانية: حساب كلفة الحل باستخدام تابع حساب الكلفة function تقوم بتعريفه.
تنفيذ وتطبيق هذه الخطوة ايضا عائد لك. بالاعتماد على نوع المسألة التي تسعى الى حلها, قد يكون التابع جدا بسيط مثلا اجمالي مجموع الاميال التي يقطعها البائع المتجول ضمن رحلته.
او من الممكن ان يكون التابع معقدا اكثر, بحيث يكون عبارة عن مجموعة من العوامل التي تشكل بمجموعها تابع حساب الكلفة.
تعتبر عملية حساب الكلفة لكل حل بمثالة الجزء الاكثر كلفة ضمن الخوارزمية, لذلك يفضل ان يكون بسيطا قدر الامكان.
الخطوة الثالثة: توليد حل عشوائي مجاور
“مجاور neighboring” تعني بأن هنالك اختلاف وحيد بين الحل القديم والحل الجديد. بشكل فعال, يتم الحصول على الحل الجيد عبر تبديل عنصرين من الحل الحالي ومن ثم تتم اعادة حساب الكلفة. المتطلب الاساسي ضمن هذه الخطوة, هي ان تتم بشكل عشوائي.
الخطوة الرابعة: حساب كلفة الحل الجديد
يتم استخدام نفس تابع الملائمة السابق – الذي تم استخدامه في الخطوة السابقة. ومن هنا يتوضح لماذا يتوجب علينا ان ننفذ وننجز تابع الملائمة بأفضل شكل يعطيه امكانية انجاز ممتازة, لانه يتم استدعائه ضمن كل تكرار في الخوارزمية.
اذا كانت (كلفة الحل الجديد “اصغر” من كلفة الحل القديم) =< عندها يتم الانتقال الى الحل الجديد
في حال كانت كلفة الحل الجديد اصغر من كلفة الحل القديم, عندها يكون الحل الجديد افضل من الحل القديم. وهذه الحالة تسعد الخوارزمية 🙂 لانها تقترب من الحل الافضل. ويتم في هذه الحالة التحرك الى الحل الجديد, ويتم الاعتماد عليه للمقارنة معه في الخطوات السابقة على انه افضل حل لحد الان.
اذا كانت (كلفة الحل الجديد “أكبر” من كلفة الحل القديم) =< “ربما” يتم الانتقال الى الحل الجديد.
هذه نقطة مثيرة للاهتمام ضمن الخوارزمية. حيث ان الخوارزمية معظم الوقت تسعى الى تجنب الانتقال الى حل اسوء. لانها اذا قامت بذلك اغلب الوقت, عندها سيكون هنالك احتمال كبير للوقوع ضمن نهاية محلية عظمى.
لتجنب هذه المشكلة, تلجأ الخوارزمية في بعض الاحيان للاحتفاظ بالحل الاسوء.
من اجل اتخاذ القرار في هذه المسالة – الاحتفاظ بالحل الحالي او الانتقال الى حل اسوء – تقوم الخوارزمية بحساب شيء يدعبى باسم “احتمال القبول acceptance probability” ومن ثم تقوم بمقارنته برقم عشوائي.
التفاصيل المهمة ضمن الخوارزمية
الشرح اعلاه, لم يتطرق الى احد اهم المعاملات parameter ضمن الخوارزمية, الا هو درجة الحرارة temperature.
“درجة الحرارةTemperature ” عبارة عن تابع يستخدم ضمن التكرار في الخوارزمية.
وكما هو واضح من الاسم, فهو مستوحى من المبدأ الفيزيائي الذي اشتقت منه الخوارزمية – محاكاة التلدين عن طريق تسخين وتبريد المعادن.
عادة تبدأ قيمة معامل الحرارة temperature بالقيمة 1.0, وتتناقص قيمتها في نهاية كل تكرار عبر ضربها – رياضيا – بثابت يدعى α
بالامكان التحكم بقيمة α.
بشكل عام, الخيارات تتراوح بين 0.8 الى 0.99.
فعليا, الخوارزمية اعقد بقليل من التوصيف والتبسيط اعلاه.
نكتفي بهذا القدر ضمن هذه الحلقة, لنتابع بمزيد من الشرح التقني للخوارزمية و بمثال عملي لتطبيق الخوارزمية باستخدام كود من لغة بايثون Python.
والى ذلك الحين نستودعكم الله والسلام عليكم ورحمة الله وبركاته
مع تحيات: م. نور الصباحي
سلسلة الحلقات
- خوارزمية محاكاة التلدين – الحلقة الاولى
- خوارزمية محاكاة التلدين – الحلقة الثانية
- خوارزمية محاكاة التلدين – مثال – الحلقة الثالثة
- خوارزمية محاكاة التلدين – برنامج التبريد – الحلقة الرابعة
- خوارزمية محاكاة التدلين – التطبيقات – الحلقة الخامسة والاخيرة
| المصطلح | الترجمة |
| 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 |
