أرشيف لـ14 سبتمبر, 2017

الحلقة 4 : خوارزمية محاكاة التلدين – برنامج التبريد Simulated Annealing Algorithm – Cooling Schedule

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

ضمن هذه الحلقة من خوارزمية التلدين 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

heating-and-cooling-maury-county-tennesseeيتألف برنامج التبريد cooling schedule في خوارزمية محاكاة التلدين من المكونات التالية:

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

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

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

يجب أن تكون درجة حرارة الابتدائية Starting temperature ساخنة بما فيه الكفاية للسماح للخوارزمية بالانتقال الى اي حل من heating-naples-fl-2-300x300.pngالحلول القريبة. إذا لم يتم ذلك  – اي البدء بدرجات حرارة عالية – فإن الحل النهائي 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

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

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

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

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

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

 

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

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

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

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

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

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

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

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

او

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

حيث ان

t = tα

where α < 1.

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

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

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

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

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

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

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

Cooling Schedule 1

Cooling Schedule 1

Cooling Schedule

Cooling Schedule 2

Cooling Schedule 3

Cooling Schedule 3

Cooling Schedule 4(sigmoid)

Cooling Schedule 4(sigmoid)

Cooling Schedule 6

Cooling Schedule 6

Cooling Schedule 7

Cooling Schedule 7

Cooling Schedule 8

Cooling Schedule 8

Cooling Schedule 9

Cooling Schedule 9

عدد التكرارات عند كل درجة حرارة 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

 

 

Advertisements

, , , , , , ,

أضف تعليق

الحلقة 3 : خوارزمية محاكاة التلدين – مثال Simulated Annealing Algorithm Example

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

نتابع ضمن هذه الحلقة الحديث عن خوارزمية محاكاة التلدين 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 function

حيث ان “الرمز الفا” يمثل احتمال القبول acceptance probability

old cost minue new cost

تمثل الفرق بين كلفة الحل القديم وكلفة الحل الجديد

T عبارة عن درجة الحرارة temperature

E = 2.71828

عبارة عن ثابت رياضي.

 

­تعتبر هذه المعادلة جزء من محاكاة التلدين Simulated annealing, وهي تمثل طاقة الجسيمات المعدنية عندما يتم تبريدها بشكل بطيء بعد تعرضها لدرجات حرارة عالية.

هذه العملية تسمح للجسيمات particles بالانتقال من تكوين عشوائي الى تكوين اخر اكثر انتظاما وبطاقة منخفضة.

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

تعني المعادلة السابقة بأن احتمال القبول acceptance probability:

  • يكون دوما اكبر من “واحد” عندما يكون الحل الجديد افضل من الحل السابق ( كلفته اخفض)
  • يصبح اصغر عندما يكون الحل الجديد new solution اسوء من الحل السابق.
  • يصبح اصغر من تناقض درجة الحرارة ( اذا كان الحل الجديد اسوء من الحل القديم).

 

الخلاصة:

اذا كان لديك مسألة امثلة بحاجة لحل, يجب ان تختطر خوارزمية محاكاة التلدين الى بالك.

هنالك طبعا الكثير من الاستراتيجيات والخوارزميات غيرها

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

——————–

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

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

مع تحيات

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

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

  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 طريقة عشوائية حسابية

 

المراجع

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

 

 

, , , , ,

أضف تعليق