• Home
  • Courses
  • Portfolio
  • Contact
    Tiger 4 CodeTiger 4 Code
    • Home
    • Courses
    • Portfolio
    • Contact

      خوارزمية محاكاة التلدين Simulated Annealing Algorithm

      • Home
      • Blog
      • خوارزمية محاكاة التلدين Simulated Annealing Algorithm
      • الحلقة 2 : خوارزمية محاكاة التلدين Simulated Annealing Algorithm

      الحلقة 2 : خوارزمية محاكاة التلدين Simulated Annealing Algorithm

      • Posted by Schwarztiger
      • Categories خوارزمية محاكاة التلدين Simulated Annealing Algorithm
      • Date August 26, 2017
      • Comments 0 comment

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

      نتابع ضمن هذه الحلقة الحديث عن خوارزمية محاكاة التلدين SA Algorithm

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

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

      لماذا خوارزمية محاكاة التلدين Why Simulated Annealing Algorithm

      كما نعلم, هنالك العديد من خوارزميات الامثلة optimization algorithms مثل:

      • خوارزمية تسلق الهضبة Hill climbing algorithm – سنقدم سلسلة عنها ايضا ان شاء الله في المستقبل
      • الخوارزميات الجينية Genetic Algorithms
      • Gradient descent
      • ….

      في الواقع, تكمن قوة خوارزمية محاكاة التلدينSA  في قدرتها على تجنب السقوط بالنهايات العظمى المحلية local maxima.

      وتكاد تكون الحلول solutions  التي تقدمها الخوارزمية افضل من غيرها من الخوارزميات, ولكنها ليست الأفضل على الاطلاق.

      يمكن تصور ذلك عن طريق تخيل رسم ثنائي البعد 2D – كما هو موضح بالشكل ادناه, حيث تمثل كل نقطة من الاحداثيات الواقعة على محور x حلا من الحلول ( على سبيل المثال خط سير معين بالنسبة لمسألة البائع المتجول salesman problem ).

      وتمثل كل نقطة احداثيات على محور y مدى جودة هذا الحل ( على سبيل المثال, عكس قيمة المسافة المقطوعة بالنسبة لمسار من مسارات البائع المتجول – المقصود بعكس القيمة اي انه كل ما قصر المسار, كل ما كان الحل افضل, وبالتالي عكس القيمة تمثل الجودة في هذه الحالة)

      SA Solutions

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

      هذا يبدوا منطقيا جدا, ولكنه قد يؤدي حالات, حيث تعلق الخوارزمية في اماكن مثلى محلية sub-optimal places.

      في المخطط ادناه, تم تحديد الحل الافضل بنجمة صفراء.

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

      تمثل النجمة الخضراء حل امثلي محلي sub-optimal local solution.

      ملاحظة:

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

      SA Solutions with stars.jpg

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

      SA Solutions with stars and line.jpg

      بالاضافة الى ذلك, فإن خوارزمية محاكاة التلدين ليست صعبة التنفيذ, على الرغم من اسمها المرعب 🙂

      الخوارزمية

      سنطرح ونقدم الخوارزمية عبر شرح عام وبسيط, قد نلجأ ضمن حلقات قادمة الى شرح تقني ومدعم بالرياضيات

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

      1. في البداية, توليد حل عشوائي random solution
      2. حساب الكلفة باستخدام احد التوابع التي قمت بتعريفها.
      3. توليد حل عشوائي مجاور random neighboring solution
      4. حساب كلفة الحل الجديد solution cost
      5. اجراء المقارنات التالية:
        • اذا كانت (كلفة الحل الجديد “اصغر” من كلفة الحل القديم) =< عندها يتم الانتقال الى الحل الجديد
        • اذا كانت (كلفة الحل الجديد “أكبر” من كلفة الحل القديم) =< “ربما” يتم الانتقال الى الحل الجديد.
      6. اعادة الخطوات من الثالثة حتى الخامسة حتى الوصول الى حل مقبول, او تصل الخوارزمية الى الحد الاعلى المسموح من التكرارات.

       

      لنحلل الآن الخوارزمية الى قطع صغيرة:

      الخطوة الأولى: توليد حل عشوائي.

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

      الخطوة الثانية: حساب كلفة الحل باستخدام تابع حساب الكلفة function تقوم بتعريفه.

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

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

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

      الخطوة الثالثة: توليد حل عشوائي مجاور

      “مجاور neighboring” تعني بأن هنالك اختلاف وحيد بين الحل القديم والحل الجديد. بشكل فعال, يتم الحصول على الحل الجيد عبر تبديل عنصرين من الحل الحالي ومن ثم تتم اعادة حساب الكلفة. المتطلب الاساسي ضمن هذه الخطوة, هي ان تتم بشكل عشوائي.

      الخطوة الرابعة: حساب كلفة الحل الجديد

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

      اذا كانت (كلفة الحل الجديد “اصغر” من كلفة الحل القديم) =< عندها يتم الانتقال الى الحل الجديد

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

      اذا كانت (كلفة الحل الجديد “أكبر” من كلفة الحل القديم) =< “ربما” يتم الانتقال الى الحل الجديد.

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

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

      من اجل اتخاذ القرار في هذه المسالة – الاحتفاظ بالحل  الحالي او الانتقال الى حل اسوء – تقوم الخوارزمية بحساب شيء يدعبى باسم “احتمال القبول acceptance probability” ومن ثم تقوم بمقارنته برقم عشوائي.

      التفاصيل المهمة ضمن الخوارزمية

      الشرح اعلاه, لم يتطرق الى احد اهم المعاملات parameter ضمن الخوارزمية, الا هو درجة الحرارة temperature.

      “درجة الحرارةTemperature ” عبارة عن تابع يستخدم ضمن التكرار في الخوارزمية.

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

      عادة تبدأ قيمة معامل الحرارة temperature  بالقيمة 1.0, وتتناقص قيمتها في نهاية كل تكرار عبر ضربها – رياضيا – بثابت يدعى α

      بالامكان التحكم بقيمة α.

      بشكل عام, الخيارات تتراوح بين 0.8  الى 0.99.

      فعليا, الخوارزمية اعقد بقليل من التوصيف والتبسيط اعلاه.

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

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

      مع تحيات: م. نور الصباحي

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

      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

       

       

      Tag:AI algorithm, SA, Simulated Annealing Algorithm, Simulated Annealing Algorithm شرح, Simulated Annealing شرح خوارزمية, خوارزمية محاكاة التلدين

      • Share:
      author avatar
      Schwarztiger

      Previous post

      12 : Angular2 - Forms النماذج
      August 26, 2017

      Next post

      الحلقة 3 : خوارزمية محاكاة التلدين - مثال Simulated Annealing Algorithm Example
      September 4, 2017

      You may also like

      cooling-simulated-annealing
      الحلقة 5 : خوارزمية محاكاة التلدين – التطبيقات Simulated Annealing Algorithm – Applications
      5 October, 2017
      The-path-of-the-hill-climbing-and-the-simulated-annealing-algorithm-is-represented-with
      الحلقة 4 : خوارزمية محاكاة التلدين – برنامج التبريد Simulated Annealing Algorithm – Cooling Schedule
      14 September, 2017
      The-path-of-the-hill-climbing-and-the-simulated-annealing-algorithm-is-represented-with
      الحلقة 3 : خوارزمية محاكاة التلدين – مثال Simulated Annealing Algorithm Example
      4 September, 2017

      Leave A Reply Cancel reply

      Your email address will not be published. Required fields are marked *

      Search

      Latest Courses

      Android Development

      Android Development

      $950.00
      HTML Tutorial: HTML & CSS for Beginners

      HTML Tutorial: HTML & CSS for Beginners

      $800.00
      Learn WordPress Content Management System

      Learn WordPress Content Management System

      Coming soon
      logo-eduma-the-best-lms-wordpress-theme

      info@tiger4code.com

      Links

      • Courses
      • Portfolio

      Copyright 2019 | Educational, Web & Mobile Development Platform By Tiger 4 Code