السلام عليكم ورحمة الله وبركاته

ضمن هذه الحلقة من خوارزمية التلدين simulated annealing algorithm SA سنتحدث بشكل مفصل عن عنصر مهم من عناصر الخوارزمية, الا وهو مخطط وبرنامج التبريدThe cooling schedule .

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

التلدين الفيزيائي physical annealing  وخوارزمية محاكاة التدلين simulated annealing

في البداية دعونا نوضح العلاقة بين التلدين الفيزيائي physical annealing  وخوارزمية محاكاة التدلين simulated annealing

وذلك اهمية خاصة, حيث انه سوف يساعدنا على تمثيل اي مسألة باستخدام خوارزمية محاكاة التلدين SA

الجدول ادناه يوضح مقاربة التلدين الفيزيائي مع محاكاة التلدين برمجيا

Thermodynamic Simulation	Combinatorial Optimization
System States	Feasible Solutions
Energy	Cost
Change of State	Neighboring Solutions
Temperature	Control Parameter
Frozen State	Heuristic Solution

بالاعتماد على هذه المقاربات الموضحة بالجدول, بالامكان الآن تمثيل اي مسألة امثلة   combinatorial optimization problem بواسطة خوارزمية محاكاة التلدين SA .

اما الآن فسننتقل للحديث عن نقطة اساسية ومهمة في الخوارزمية, الا وهي عملية التبريد Cooling process, حيث تعتمد الخوارزمية بشكل اساسي في ادائها على طريقة التبريد المستخدمة.

برنامج التبريد The Cooling Schedule

يتألف برنامج التبريد cooling schedule في خوارزمية محاكاة التلدين من المكونات التالية:

1. درجة الحرارة البدائية Starting Temperature
2. درجة الحرارة النهائية Final Temperature
3. تخفيض درجة الحرارة Temperature Decrement
4. عدد التكرارات عند كل درجة حرارة Iterations at each temperature

سنتحدث فيما يلي عن كل مكون من هذه المكونات بالتفصيل.

 درجة الحرارة البدائية Starting Temperature

يجب أن تكون درجة حرارة الابتدائية Starting temperature ساخنة بما فيه الكفاية للسماح للخوارزمية بالانتقال الى اي حل من الحلول القريبة. إذا لم يتم ذلك  – اي البدء بدرجات حرارة عالية – فإن الحل النهائي ending solution سيكون هو نفسه (أو قريب جدا) إلى الحل البدائي Starting solution. وعندها سنكون اقرب ببساطة من تنفيذ خوارزمية تسلق التلHill climbing , بدلا خوارزمية محاكاة التلدين!

ومع ذلك يجب الانتباه الى نقطة اخرى، ففي حال كانت درجات الحرارة في البداية عالية جدا, عندها يصبح من الممكن الانتقال الى اي حل مجاور, وبالتالي تتحول عملية البحث – على الاقل في المراحل البدائية من الخوارزمية – الى عملية بحث عشوائي random search.
فعليا, سوف تتحول عملية البحث في هذه الحالة الى عملية بحث عشوائي الى ان يتم تخفيض درجات الحرارة عن طريق التبريد cooling , وتصل الى درجة مناسبة لكي تعود الخوارزمية وتتصرف بسلوك خوارزمية محاكاة التلدين simulated annealing algorithm.

كما هو واضح, فإن المشكلة الاساسية تكمن في ايجاد درجة الحرارة الابتدائية starting temperature.

حاليا لا توجد طريقة معروفة لايجاد درجة حرارة ابتدائية مناسبة لكل المسائل بشكل عام. لذلك نحن بحاجة للجوء الى طرق اخرى, ووضع عدد من النقاط بعين الاعتبار من اجل حساب درجة الحرارة الابتدائية.

إذا كنا نعرف المسافة القصوى (فرق تابع الكلفة الموضح بالمعادلات بالحلقة السابقةcost function difference ) بين جار وآخر, عندها يمكننا استخدام هذه المعلومات لحساب درجة الحرارة الابتدائية.

هنالك طريقة أخرى، تم اقتراحها من قبل (Rayward-Smith، 1996)، وتتمثل بأن تبدأ مع درجة حرارة عالية جدا ومن ثم يتم تبريدها بسرعة حتى يتم قبول حوالي 60٪ من أسوأ الحلول. لتعتبر عندها هذه الدرجة بمثابة درجة الحرارة الابتدائية, وعند هذه النقطة نبدأ بتخفيض سرعة التبريد.

وهناك فكرة مماثلة، تم اقتراحها من قبل (Dowsland، 1995)، وتتمثل بتسخين النظام بسرعة حتى يتم قبول نسبة معينة من الحلول الأسوأ , ومن ثم يمكن أن تبدأ بعدها عملية التبريد البطيء.

يمكن النظر الى الاقتراحات السابقة على انها مماثلة لعملية التلدين الفيزيائيphysical annealing . حيث يتم تسخين المواد في البداية لدرجات حرارة عالية حتى تصل الى المرحلة السائلةliquate status , ومن ثم يبدأ التبريد (حيث انه لا جدوى من تسخين المادة اكثر بعد وصولها للمرحلة السائلة في عملية التدلين الفيزيائي).

درجة الحرارة النهائية Final Temperature

عادة ما يتم ترك درجة الحرارة تتناقص حتى تصل الصفر.

على كل حال, هذا قد يجعل الخوارزمية تعمل لفترة اطول وخصوصا عندما يتم استخدام طريقة جدول التبريد الهندسي geometric cooling schedule – سيتم شرحه بعد قليل.

عمليا, ليس من الضرورة ترك درجة الحرارة تصل للصفر, لانه عندما تقترب درجة الحرارة من الصفر, ستكون عندها فرصة قبول الانتقال الى حل اسوء تقريبا مساوية للحالة التي تكون فيها درجة الحرارة مساوية للصفر.

لذلك، يجب وضع معايير للتوقف, والتي من الممكن ان تكون:

• إما درجة حرارة منخفضة بشكل مناسب
• أو عندما يكون النظام “مجمداfrozen ” عند درجة الحرارة الحالية (أي أنه لا يتم قبول أي تحركات أفضل أو أسوأ).

 

تخفيض درجة الحرارة Temperature Decrement

بعد ان تحدثنا عن كل من درجتي الحرارة البدائية والنهائية, الان يلزمنا معرفة كيفية الانتقال من درجة حرارة الى اخرى.

اي نحن بحاجة الى تخفيض درجة الحرارة حتى نصل بالنهاية الى شرط التوقف.

تعتبر طريقة تخفيض درجة الحرارة مهمة جدا في نجاح الخوارمية.

تنص النظرية على انه يجب أن نسمح بعدد كافي من التكرارات عند كل درجة الحرارة بحيث النظام يستقر عند تلك الدرجة.

ولكن لسوء الحظ، فإن النظرية أيضا تشير إلى أن عدد التكرارات اللازم لتحقيق ذلك عند كل درجة حرارة قد يكون كبيرا بالنسبة لحجم المسألة, ويزيد من كلفة الحل بشكل اسي exponential . ولكون ذلك غير عملي, فإننا بحاجة الى تسوية.

يتم ذلك اما عبر اجراء عدد كبير من التكرارات عند بضعة درجات حرارة, وعدد قليل من التكرارات عند بقية درجات الحرارة, او اجراء موازنة فيما بينهم.

لتخفيض درجة الحرارة, يمكن استخدام طريقة خطية بسيطة simple linear method.

او

هنالك طريقة اخرى باستخدام طريقة التخفيض الهندسي geometric decrement

حيث ان

t = tα

where α < 1.

اظهرت التجارب بأن قيم الف α يجب ان تتراوح بين 0.8 و 0.99 , حيث لوحظ بأنه يتم الحصول على نتائج افضل عند القيم الاعلى من المجال المذكور سابقا.

طبعا كلما كانت قيمة α اعلى, كلما تطلب الامر وقتا اطول لتخفيض درجة الحرارة وصولا الى شرط التوقف stopping criterion.

طبعا هنالك طرق عديدة وتجريبات بخصوص تخفيض درجة الحرارة, وما ذكر سابقا كان بهدف الذكر لا الحصر.

بعض الطرق الاخرى هي التالية:

اذا اعتبرنا ان درجة الحرارة الابتدائية T₀

ودرجة الحرارة النهائية T_N

حيث ان T_i عبارة عن درجة الحرارة عن المرحلة i اثناء الانتقال ضمن المجال من 0  الى N

عدد التكرارات عند كل درجة حرارة Iterations at each temperature

يبقى هنالك القرار النهائي الذي لانزال بحاجة الى اتخاذه:

تحديد عدد التكرارات عند كل درجة حرارة.

هنالك طريقة بسيطة جدا وواضحة, الا وهي بتحديد عدد ثابت من التكرارات عند كل درجة حرارة.

هنالك طريقة اخرى, تم اقتراحها من قبل (Lundy,1986) وتتمثل باجراء تكرار وحيد عند كل درجة حرارة, ولكن عندها يجب ان تتم عملية التبريد بشكل بطيء جدا.

الصيغة التي تم استخدامها:

t = t/(1 + βt)

حيث ان β  عبارة عن قيمة صغيرة بشكل مناسب.

يوجد حل بديل عن الحلول السابقة, ويتمثل بتغير عدد التكرارات بشكل ديناميكي مع تقدم الخوارزمية.  حيث يكون من المهم اجراء عدد كبير من التكرارت عند درجات الحرارة المنخفضة, وبذلك يتم استكشاف الحلول المحلية الامثلية بشكل كامل. ويمكن تقليل عدد التكرارات عند درجات الحرارة المرتفعة.

تبدو طريقة مناسبة وعملية اكتر من غيرها.

————-

ارجو ان تكون مخطط واجرائية التبريد قد توضحت عبر الشرح السابق

حيث تعتبر عنصرا هاما جدا في الخوارزمية, وتلعب دور اساسي في نجاح الخوارزمية او فشلها.

طبعا هنالك عدة عوامل اخرى يجب التمهل ودراستها بشكل مفصل ضمن هذه الخوارزمية

ولكن سنكتفي بهذا القدر ضمن هذه الحلقة, والى اللقاء ضمن حلقة اخرى من سلسلة خوارزمية محاكاة التلدين SA.

والى ذلك الحين استودعكم الله والسلام عليكم ورحمة الله وبركاته

مع تحيات

م. نور الصباحي

سلسلة الحلقات

1. خوارزمية محاكاة التلدين – الحلقة الاولى
2. خوارزمية محاكاة التلدين – الحلقة الثانية
3. خوارزمية محاكاة التلدين – مثال – الحلقة الثالثة
4. خوارزمية محاكاة التلدين – برنامج التبريد – الحلقة الرابعة
5. خوارزمية محاكاة التدلين – التطبيقات – الحلقة الخامسة والاخيرة

المصطلح	الترجمة
temperature	الحرارة
parameter	معامل
internal thermal energy	الطاقة الداخلية  الحرارية
stochastically	بشكل عشوائي
algorithm	خوارزمية
Crystal	بلوري
amorphous	غير متبلور
thermodynamics	الديناميك الحراري
annealing	التلدين
Optimization problems	مسائل الأمثلة
solid state	الحالة الصلبة
Liquid state	الحالة السائلة
stochastic computational method	طريقة عشوائية حسابية
the cooling schedule	جدول التبريد

 

المراجع

Simulated Annealing Algorithms http://www.iue.tuwien.ac.at/phd/binder/node87.html

The Simulated Annealing Algorithm http://katrinaeg.com/simulated-annealing.html

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 https://www.google.com.tr/url?sa=t&rct=j&q=&esrc=s&source=web&cd=8&cad=rja&uact=8&ved=0ahUKEwiawauM0c3VAhUDaVAKHc1nCp4QFghZMAc&url=http%3A%2F%2Fwww.springer.com%2Fcda%2Fcontent%2Fdocument%2Fcda_downloaddocument%2F9783319411910-c2.pdf%3FSGWID%3D0-0-45-1579890-p180080441&usg=AFQjCNE6X9vSDzVMyd4JATIbyOIsuWH1DA

Simulated Annealing Link to download word document https://www.google.com.tr/url?sa=t&rct=j&q=&esrc=s&source=web&cd=10&cad=rja&uact=8&ved=0ahUKEwiawauM0c3VAhUDaVAKHc1nCp4QFghkMAk&url=http%3A%2F%2Fwww.cs.nott.ac.uk%2F~pszgxk%2Faim%2Fnotes%2Fsimulatedannealing.doc&usg=AFQjCNFlbfpKGnne-ZnM137yivTkepFZfA

Simulated Annealing Cooling Schedules http://www.btluke.com/simanf1.html