Archive for category خوارزميات الذكاء الصناعي AI Algorithms

خوارزمية تسلق التل Hill-Climbing Algorithm

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

 خوارزمية تسلق التل Hill-Climbing Algorithm

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

سنشرح ضمن هذه الحلقة خوارزمية تسلق التل Hill-Climbing Algorithm
وهي خوارزمية, سهلة الشرح, بسيطة المبدأ.

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

سوف نتطرق اثناء شرحنا لهذه الخورازمية لخوارزمية اخرى, الا وهي خوارزمية “توليد حل واختباره” Generate-And-Test Algorithm, وذلك لاننا سنشير اليها فيها بعد اثناء الحديث عن خوارزمية تسلق التل.

مقدمة

خورازمية تسلق التل Hill-Climbing Algorithm

في التحليل العددي Numerical Analysis تعتبر خوارزمية تسلق التل hill climbing على انها احد التقنيات الرياضية التي تهدف الى الوصول الى الحل  الامثل mathematical optimization technique. وتنتمي هذه التقنية الى عائلة تقينات البحث المحلي  Family of local search.
وهي عبارة عن خوارزمية تكرارية iterative algorithm, التي تبدأ من حل عشوائي للمسألة قيد الحل, ومن ثم تحاول الوصول الى حل افضل تدريجيا عن طريق تغيير عنصر واحد من عناصر الحل الحالي في كل مرة.

خوارزمية “توليد حل واختباره”Generate-And-Test Algorithm

عبارة عن تكنيك بسيط جدا, يهدف لايجاد حل افضل.

خطوات الخوارزمية هي التالية:Generate-and-test1.jpg

  • تحديد الحالة الراهنة current state كحالة اولية
  • تطبيق كل العمليات الممكنة على الحالة الحالية بهدف الحصول على حل محتمل.
  • مقارنة الحل الذي تم توليده حديثا مع الحالة الهدف goal state .
  • في حال تم الوصول الى الحالة الهدف, او لم يعد بالامكان توليد اي حالات جديدة, عندها يتم الخروج, والا تتم العودة للخطوة الثانية من الحلقة.

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

خوارزمية تسلق التل Hill-Climbing Algorithm

في التكنيك المستخدم ضمن خوارزمية تسلق التل. يتم البدء من قاعدة التل, يتابع السير صعودا حتى الوصول الى قمة التل. بعبارة اخرى, نبدأ من الحالة الاولية, ونحافظ على تحسين الحل, الى حين الوصول الى افضل شكل ممكن للحل.init_goal

تختلف خوارزمية تسلق التل عن خوارزمية “توليد حل واختباره” Generate-and-test بأنها تتجاهل كل الحالات التي لا تبدوا واعدة, او تبدو من غير المرجح ان تؤدي الى الحالة الهدف. ومن اجل اتخاذ مثل هذا القرار, فإن خوارزمية تسلق التل تستخدم تابع لتقييم الحل  evaluation function الذي يشير الى مدى قرب الحالة الحالية من الحالة المنشودة.

بإمكاننا ان نلخص الكلام السابق بالقول بإن:

خوارزمية تسلق التل = خوارزمية توليد حل واختباره + تجريبيات

Hill-Climbing = generate-and-test + heuristics

 

دعونا الآن ننظر الى شكل مبسط لخوارزمية تسلق التل Hill-Climbing Algorithm

  • تحديد الحالة الراهنة كحالة اولية
  • ندخل في حلقة loop الى حين الوصول الى الحالة الهدفgoal state , او نصل الى مرحلة لا يعود بالامكان عندها تطبيق المزيد من العمليات operators على الحالة الحالية:
    1. تطبيق احد العمليات operators على الحالة الحالية بهدف الحصول على حالة جديدة
    2. مقارنة الحالة الجديدة new state بالحالة المنشودة goal state
    3. الخروج في حال لم يتم تحقيق الحالة الهدفgoal state .
    4. تقييم الحالة الجديدة new state باستخدام تابع تجريبي heuristic function ومقارنتها بالحالة الحالية. في حال كانت الحالة الجديدة new state اقرب للحالة الهدف من الحال الحاليةcurrent state , عندها يتم تحديث الحالة الحالية بالحالة الجديدة.

كما هو واضح من الخوارزمية, فإنه يتم الوصول الى الحالة الهدف عبرة عدة تحسينات متكررة.في خوارزمية تسلق التل Hill-Climbing Algorithm , عملية ايجاد الحل الافضل, تكافئ الوصول الى قمة التل.

state_iterations

خوارزمية Steepest-Ascent Hill Climbing Algorithm

وتعرف ايضا باسم البحث المتدرج Gradient Search, وهي عبارة عن نسخة معدلة ومختلفة عن خوارزمية تسلق التل Hill-Climbing Algorithm.

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

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

بعبارة اخرى, في حالة تسلق التل يتم اختيار اي حالة – اقرب حالة – لتكون بمثابة الحالة الاحقة, والتي تكون اقرب للحالة الهدف من الحالة الحالية, بينما في خوارزمية Steepest-Ascent Hill Climbing algorithm, فإن الحالة الاحقة successor state يتم اختيارها من بين كل الحالات الممكنة – ليس فقط اقرب حالة – بحيث تكون اقرب حالة الى الحالة الهدف, ومن ثم يتم تعديل الحالة الحالية current state بها.

 

المساوئ Disadvantages :

تعتبر خوارزمية تسلق التل Hill-Climbing بمثابة خوارزمية قصيرة النظر, لانها تقوم بتقييم فقط الحالات الفورية. وبالتالي قد ينتهي بها الامر في بعض الحالات التي لا يمكن عندها اختيار اي حالات اخرى.
دعونا ننظر الى مثل هذه الحالات وبعض الحلول الممكنة لها:maxresdefault

  • نهاية محلية عظمى Local maximum: وهي عبارة عن حالة, تكون بمثابة افضل حالة ضمن الجوار, ولكن هنالك حالة افضل منها, ولكنها بعيدة عنها.
    في حال وقعت النهاية المحلية العظمى local maximum بالقرب من الحل, عندها تعرف هذه الحالة باسم “foothills”.
  • الهضبة Plateau: في هذه الحالة تملك كل الحلول – الحالات- المجاورة نفس قيم تابع التجريب evaluation function, لذلك يصبح من غير الواضح اختيار الحالة التالية عبر القيام بالمقارنات المحلية.
  • القمة Ridge: عبارة عن منطقة اعلى من مناطق الحالات المجاورة, ولكن لا يمكن الوصول اليهم عبر حركة واحدة. على سبيل المثال: عندما يكون لدينا 4 اتجاهات ممكنة للتحرك (شرقE , غرب W, شمال N, جنوب S) والمنطقة متواجدة ضمن الشمال الشرقي NE.drawbackt

هنالك عدة حلول للتغلب على هذه الحالات.

  • بامكاننا التراجع والعودة للخلف backtrack الى احد الحالات السابقة, والعودة للاستكشاف بقية الاتجاهات من تلك الحالة.
  • بإمكاننا تجاوز عدة حالات states من اجل القيام بقفزة الى اتجاهات جديدة.
  • بإمكاننا استكشاف عدة اتجاهات بهدف معرفة الطريق الافضل.

 

الخلاصة:

بالرغم من ان تقنية خوارزمية تسلق التل hill climbing  technique افضل بكثير من خوارزمية البحث الشامل  exhaustive search , لكنها لا تزال غير عملية وغير ملائمة للمسائل ذات فضاء البحث الخضم large problem spaces

قد يخطر ببال البعض بأنه بإمكاننا دوما ترميز المعلومات العامة عبر توابع استدلال تجريبية heuristic functions من اجل جعل عملية اتخاذ القرار افضل, ولكن التعقيد الحسابي computational complexity لمثل هذه العمليات سيكون عاليا.

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

—————-

نرجو ان نكون قد قدمنا لمحة وشرح كافي عن هذه الخورازمية

والى لقاء قريب ان شاء الله مع خوارزمية جديدة ومنهج من مناهج الذكاء الصناعي

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

مع تحيات:

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

References
http://www.baeldung.com/java-hill-climbing-algorithm
https://en.wikipedia.org/wiki/Hill_climbing
https://en.wikipedia.org/wiki/Hill_climbing

 

 

 

Advertisements

, , , , , , , , , , ,

أضف تعليق

شرح خوارزمية Tabu Search Algorithm

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

نعود اليكم مع خوارزمية جديدة تتحدث عن احد طرائق البحث الذكية, وتدعى
Tabu Search Algorithm

في البداية سنشرح مصدر اسم الخوارزمية ومعناه

Tabu: تأتي بمعنى محظور, ممنوع او محرم, وسنلاحظ اثناء شرح الخوارزمية بأن هنالك قائمة توضع فيها مجموعة الحلول التي لا يتوجب العودة واستخدمها مرة ثانية, تدعى هذه القائمة باسم “Tabu List”  اي القائمة المحظورة. ومن هنا جاء اسم الخوارزمية Tabu Search Alorithm.

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

في البداية سنبدأ بتعريف هذه الخوارزمية:

خوارزمية البحث تابو  Tabu Search Algorithm

تندرج خوارزمية البحث تابوTabu Search algorithm  تحت تصنيف الخوارزميات العشوائية Stochastic Algorithms.

عبارة عن احد طرائق البحث التجريبية, والتي تستخدم طرائق البحث المحلي local search methods من اجل ايجاد حلول لمسائل الامثلة الرياضية mathematical optimization.

في البداية دعونا نعرف ب طرائق البحث المحلي local search methods لنستطيع بعدها ان نفهم ماذا اضافت خوارزمية البحث تابو لها.

طرائق البحث المحلي – في الجوار local (neighborhood) search:

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

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

هنا يأتي دور خوارزمية البحث تابوTabu search algorithm  , حيث انها تقوم على تحسين اداء طرائق البحث المحلي local search methods عبر تخفيف الشروط الاساسية لطرائق البحث المحلية.
في البداية, تقبل الخوارزمية التحرك والانتقال الى حل اسوء في حال لم يتواجد اي حل افضل ضمن الجوار الحالي ( وهي تمثل الحالة عندما يعلق البحث عند نهاية محلية صغرى local minimum ).
بالاضافة الى ذلك, يتم اضافة هذه الخطوة والحركة الى قائمة الحظر- ومن هنا جاء اسم الخوارزمية Tabu اي محظور وممنوع – بحيث تمنع عملية البحث من العودة الى نفس الحلول التي تمت زيارتها سابقا.

عملية تنفيذ خوارزمية البحث تابو يتطلب استخدام بنى للذاكرة memory structures التي تخزن توصيف للحلول التي تمت زيارتها سابقا, او مجموع من القواعد المزودة من قبل المستخدمين.
إذا كان هنالك حل محتمل قد تمت زيارته سابقا خلال فترة زمنية قصيرة, او في حال انتهك هذا الحل احد القواعد, عندها يتم وضع علامة على هذا الحل على انه “محضور” “Tabu-Forbidden”, وبالتالي فإن الخوارزمية لن تعود الى هذا الحل مجددا.

تطبيقات خوارزمية البحث تابوا Tabu search algorithm

في السنوات الأخيرة، نشرت عدة مجلات علمية مجموعة واسعة من المقالات التعليمية والدراسات الحسابية توثق النجاحات التي حصدتها خوارزمية البحث تابو TS من حيث:

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

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

  • مجال تخطيط الموارد resource planning
  • مجال الاتصالات telecommunications
  • التحليل المالي financial analysis
  • مسائل الجدولة scheduling
  • Space planning
  • توزيع الطاقة energy distribution
  • الهندسة الجزيئية molecular engineering
  • الخدمات اللوجستية مخلهسفهؤس
  • تصنيف النماذج pattern classification
  • الحفاظ على البيئة environmental conservation

التوصيف الاساسي للخوارزمية Basic Description

كما وضحنا سابقا, فإن خوارزمية البحث تابو TS تستخدم اجرائيات بحث محلية ضمن الجوار Local or neighborhood search, حتى تقوم بشكل متكرر بالانتقال من حل محتمل x الى حل محسن اخر x’  ضمن جوار الحل x.

وتستمر هذه التكرارات الى حين الوصول الى احد شروط التوقف ( عادة ما تتمثل بالوصول الى عدد تكرارات محدد, او تحقيق عتبة محددة).

غالبا ما تعلق اجرائيات البحث المحلي ضمن مناطق محلية.
من اجل تجنب مثل هذه المطبات, واستكشاف فضاء البحث بشكل افضل, مع عدم ترك العديد من المناطق غير المستكشفة, جاءت خوارزمية البحث تابو TS لتستكشف بعناية جوار كل حل من الحلول مع تقدم البحث.
حيث يتم تحديد الحلول المقبولة ضمن كل جوار جديد N^*(x), باستخدام هياكل وبنى للذاكرة memory structures.
وبالاستفادة من هياكل الذاكرة هذه, يتم الانتقال من الحل الحالي x الى الحل المحسن x’ ضمن الجوار الحالي N^*(x)

تشكل هياكل الذاكرة هذه ما يعرف باسم قوائم تابو – اي القوائم المحضورة – tabu list, وهي عبارة عن مجموعة من القواعد والحلول المحضورة التي تستخدم لتصفية الحلول التي يتم قبولها من كل جوار N^*(x) يتم البحث فيه.

بشكل مبسط, إن قائمة تابو tabu list  عبارة عن مجموعة قصيرة الامد short-term set من الحلول التي تمت زيارتها ضمن الماضي القريب ( اقل من n تكرار, حيث ان n يمثل عدد الحلول السابقة التي تم تخزينها – ويدعى ايضا باسم tabu tenure – فترة الحظر).

وكما ذكرنا فإن خوارزمية البحث تابو TS تعتمد على بنى وهياكل للذاكرة لتخزين الحلول السابقة خلال فترة محددة بالاضافة الى تخزين القواعد ضمن هذه الذواكر.

إذن فقد حان الوقت الآن لنتحدث بشيء من التفصيل عن انماط وانواع هذه الذواكر

انواع الذواكر Types of memory

يمكن تصنيف انواع هياكل وبنى الذاكرة المستخدمة في خوارزمية البحث تابو TS الى ثلاث فئات:

  • ذاكرة قصيرة الامد Short-term memory: وتحوي على قائمة بالحلول التي تم اخذها مؤخرا بعيد الاعتبار. في حال تواجد احد الحلول المحتملة ضمن القائمة المحضورة tabu list , عندها لن يتم اعادة زيارة واستخدام هذا الحل حتى يصل الحل الى مرحلة انتهاء صلاحية تواجده ضمن قائمة تابو tabu list.
  • ذاكرة متوسطة الامد intermediate-term memory: وتحوي على قواعد تسمى بقواعد التكثيف intensification rules , وتهدف الى توجيه البحث نحو المناطق الواعدة من فضاء البحث.
  • ذاكرة طويلة الامد long-term memory: وتحوي على قواعد تسمى بقواعد التنويع diversification rules, ومهمتها قيادة البحث نحو مناطق جديدة ضمن فضاء البحث بحيث تضمن تنوع الحلول.
    مع هذا النوع من الذواكر طويلة الامد تستخدم عدة استراتيجيات منها : توليد حلول من مركبات ناردة الاستخدام, وبالتالي تحييد الاجيال المتولدة الجديدة من اعادة استخدام نفس المركبات المستخدمة عادة لتوليد الحلول. وبالتالي تضمن تنوع الحلول ضمن فضاء البحث.

بشكل عملي من الممكن ان تتداخل كل من الذاكرة قصيرة الامد short-term memory مع الذاكرة متوسطة الامد intermediate-term memory.

سنطرح مثال على الذواكر متوسطة الامد: المثال: الذاكرة التي تحتفظ بمعلومات فيما يخص الحلول الممنوعة أو المرغوبة التي تحتوي مثلا على صفات محددة ( على سبيل المثال الحلول التي تحوي  قيم غير مرغوبة او مرغوبة بالنسبة لمتحولات محددة certain variables).
او قد تحوي بنية الذاكرة على معلومات بحيث تمنع او تشجع تحركات محددة.

اما بالنسبة للذاكرة قصيرة الامد short-term memory فإنه يتم تصنيف بعض الصفات المختارة من الحلول التي تمت زيارتها مؤخرا على انها “tabu-active”. وبالتالي فإن الحلول التي تحوي على عناصر من “Tabu-active”  تعد حلولاً محظورة.
هنالك ما يعرف باسم Aspiration criteria وهي عبارة عن طريقة تستخدم بهدف تجاوز القيود الموجودة ضمن القائمة المحظورة tabu list, يعني ذلك في حال تواجد احد الحلول ضمن قائمة الحظر tabu list, فإنه هنالك احتمالية بأن يتم اعادة زيارة هذا الحل في حال كان يحوي على خواص وصفات موجودة ضمن قائمة السماح allowed set والتي تحوي على الصفات التي اذا وجدت بالحل يعتبر الحل جيد بما فيه الكفاية من حيث الجودة او التنوع.
اي باختصار فإن Aspiration ceiterion  تستخدم لكي تسمح باستخدام واعادة زيارة الحلول التي تعتبر افضل من الحل الحالي.

المخطط  ادناه يوضح خوارزمية بحث تابو TS ويوضح مهام كل من:

  • قائمة الحظر Tablu list
  • وقائمة السماح allow list using aspiration criterion

 

choosing best admissible candidate

ان استخدام ذاكرة قصيرة الامد short-term memory لوحدها ممكن ان يكون كافي من اجل ايجاد حل جيد متفوق على الحلول التي يمكن ايجادها باساليب البحث المحلية التقليديةconventional local search methods, ولكن بنى وهياكل الذاكرة متوسطة وطويلة الامد غالبا ما تكون ضرورية من اجل حل المسائل الاصعب.

في بعض الاحيان قد يتم دمج خوارزمية البحث تابو TS مع بعض الخوارزميات والتجريبيات الاخرى بهدف انتاج طرائق هجينة hybrid methods. واشهر مثال على ذلك يتمثل بدمج خوارزمية البحث تابو TS مع خوارزمية Scatter Search والتي هي عبارة عن اجرائية بحث تعتمد على التجمع population-based procedure, وتشترك بمجموعة من النقاط مع خوارزمية البحث تابو, وغالبا ما يتم استخدامها من اجل حل مسائل الامثلة  الكبيرة الغير خطيةالغير خطية non-linear optimization problems.

الاجرائية Procedure

الكود الترميزي ادناه يمثل نسخة مبسطة من خوارزمية البحث تابو Tabu search algorithm, حيث يتم استخدام الذاكرة قصيرة الامد فقط ضمن هذه الخوارزمية

العبارة “fitness” عبارة عن تابع يقوم بحساب وتقيييم الحل المرشح, لحساب مدى جودته.

algorithm.JPG

اضغط على الصورة لتكبيرها

توضح الخوارزمية السابقة الشرح المذكور سابقا.

بالنهاية نلخص بمايلي:

تتميز خوارزمية البحث تابو TS بمرونتها التي تعود الى استخدامها للذاكرة, حيث تسمح لها هذه البنية باستغلال معلومات البحث بشكل شمولي اكثر من الانظمة التي تعتمد على بنية ثابتة للذاكرة rigid memory systems, او الانظمة عديمة الذاكرة memoryless systems.

وتتميز هذه الخوارزمية Tabu Search Algorithm بأنها سهلة التطبيق: اي انه يمكن استخدامها وتطبيقها بالبداية بشكل مبسط جدا, لتقوم بوظيفتها الاساسية, ومن ثم يمكن تطويرها والتعديل عليها فيما بعد.
تعتبر خوارزمية Tabu Search بمثابة الاب الكبير لعائلة كبيرة من الطرائق المشتقة منها, والتي تستخدم بنى خاصة للذاكرة من اجل اتمام عملية البحث, مثل:

  • Reactive Tabu Search
  • Parallel Tabu Search

———————

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

ومن المرجح ان تكون خوارزميتنا القادمة هي خوارزمية Bacterial Foraging Optimization Algorithm بناء على طلب الباحثين عن العلم

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

مع تحيات:

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

الترجمة المصطلح
خوارزمية البحث تابو Tabu Search Algorithm
بنية او هيكلية الذاكرة memory structure
مسائل الامثلة Optimization problems
اجرائية تجريبية heuristic procedure
خوارزميات الامثلة العامة Global Optimization algorithm
فضاء البحث Search space
مسائل الامثلة Optimization problems
هيكلية , بنية Structure
طرائق هجينة hybrid methods
طرائق البحث المحلية التقليدية conventional local search methods
References
Tabu Search Tutorial

http://www.ida.liu.se/~zebpe83/teaching/rtes/papers/tabu_search.pdf

 

Clever Algorithms: Nature-Inspired Programming Recipes – Tabu Search

http://www.cleveralgorithms.com/nature-inspired/stochastic/tabu_search.html

 

Tabu Search Algorithm

https://en.wikipedia.org/wiki/Tabu_search

 

 

, , , , ,

أضف تعليق

الحلقة 5 : خوارزمية محاكاة التلدين – التطبيقات Simulated Annealing Algorithm – Applications

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

ضمن هذه الحلقة من خوارزمية التلدين simulated annealing algorithm SA سنذكر باختصار بعض تطبيقات خوارزمية محاكاة التلدين.

التطبيقات Applications

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

فيما يلي سوف نذكر باختصار بعض تطبيقات خوارزمية محاكاة التلدين:

  • مسائل الجدولة Scheduling problems
    1. جدولة – برامج – الانتاج production scheduling
    2. جدولة – برامج – النقل transport scheduling
      1. مثل مسألة البائع المتجول travelling salesman problem
  • توليد البرامج Time-tablingscheduling problems
    1. كالبرنامج الاسبوعي للمدارس او غيرها
  • مسائل معالجة الصور Image processing
  • DNA Mapping
  • التصميم الهندسي Engineering Design
    1. في مرحلة التصميم النظري للطائرات Aircraft Conceptual Design
  • في مجال الرياضيات في التوابع الاحصائية Statistical Functions
    1. وتفيد هذه في مجال التحليل المالي Financial analysis
    2. وفي مجال القطاع المصرفي Banking Industry

بالاضافة الى العديد من التطبيقات الاخرى.

——————

وبهذه الحلقة نكون قد انهينا شرح خوارزمية محاكاة التلدين Simulated Annealing Algorithm 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

 

 

, , , , , , , , , ,

أضف تعليق

الحلقة 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

 

 

, , , , , , ,

أضف تعليق

الحلقة 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

 

 

, , , , ,

أضف تعليق

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

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

 

 

, , , , ,

أضف تعليق

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

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

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

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

لقد عرضنا فيما سبق عدة خوارزميات, منها:

الخوارزميات الجينية Genetic algorithmgen

من الخوارزميات التطورية Evolutionary algorithms EA وهي مستوحاة من الاختيار الطبيعي وبيولوجيا الجينات – ذات اساس بيولوجي

خوارزميات Memetic algorithmdual-evolution-system - memetic algorithm ma

تبني ثنائية للتطور الجيني والثقافي مع بعضهم البعض

ذات اساس بيولوجي وثقافي اجتماعي

خوارزمية امثلة اسراب الطيور PSOswarm

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

 

اما خوارزمية اليوم

محاكاة عملية التلدين Simulated Annealing SA

erlenmeyer-full-of-liquid-with-bubbles-md.png

في مستوحاة من الفيزياء والقوانين الفيزيائية

وتُستخدم خوارزمية محاكاة عملية التلدين في حل العديد من مسائل الأمثلة Optimization problems

حيث تعتمد الخوارزمية على طريقة عشوائية حسابية بهدف ايجاد الحلول القصوى extremum – العليا والدنيا – للعديد من مسائل الأمثلة.

 

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

 

عملية التلدين باختصار  Annealing

عندما نقوم بتسخين مادة صلبة الى درجة حرارة مرتفعة, ومن ثم نقوم بتبريدها, عندها فإن الخواص البنيوية structural properties لهذه المادة الصلبة سوف تتغير اعتمادا على معدل التبريد وسرعته.

فإذا بردنا الشكل السائل للمادة – بعد تسخينها – بشكل بطيء كفاية, عندها سنحصل على بنية كرستالية بلورية.

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

glass

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

وكما هو واضح فإن عملية التبريد البطيء تعطينا بنية أفضل للمادة, وهو المطلوب محاكاته في خوارزميتنا هذه

كان هذا شرح مبسط جدا لعملية التلدين, اما الآن فسنقدم شرح اكتر دقة وتفصيلا لعملية التلدين  الفيزيائية

كيف تتم عملية التلدين Annealing Process

عندما يتم تسخين معدن في وعاء للانصهار, فإن طاقة المعدن الداخلية الحراريةinternal thermal energy تزداد مع التسخين, وتتحول حالة المعدن من الحالة الصلبة للحالة السائلة. عند هذه الحالة, تكون جزئيات molecules المعدن في اوضاع عشوائية وتتحرك بحرية وبسرعة عالية ضمن وعاء التسخين – كما هو موضح بالجزء a من الشكل رقم 1  ادناه.

1 introduction sa

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

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

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

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

Boltzmann Propability.JPG

 حيث ان

boltzmann delta.JPG : يمثل فرق الطاقة الحرارية بين الحالتين

T : درجة الحرارة المطلقة

KB : ثابت بولتزمان

————–

نتابع

عندما يتم تبريد المعدن, فإن سرعة حركة الجزئيات تنقص مع تناقص طاقتها الداخلية internal energy, كما هو موضح بالشكل 1-b.

وما تلبث ان تتحول حالةالمعدن الى الحالة الصلبة solid state مجددا, وتقل سرعة حركة الجزئيات اكثر فأكثر.

وبما ان عملية تبريد المعدن هي عملية محكومة بقوانين الديناميكا الحرارية العشوائية stochastic thermodynamics, فإن الحالة النهائية للجزئيات – المواضع – يتم تحديدها بشكل عشوائي وفقا لسلوك الجزئيات او سرعة برودتها.

في حال تم تبريد المعدن بشكل سريع, عندها تكون الحالة النهائية للمعدن غير متبلورة وغير منتظمة amorphous – مثل الزجاج

c5fd9d0c-9082-4c43-b017-7598b800cbea

في الحالة الصلبة المتبلورة – إلى اليمين – تنتظم جزيئات المادة بشكل متجانس يتخذ نمط متكرر، إنه ذلك الجزيء سداسي الشكل هو ما يتكرر في كل مكان بالبلورة، على عكس الحالة الصلبة اللابلورية -إلى اليسار- التي تتوزع بشكل عشوائي بحيث لا يمكن أن نلاحظ أي نمط متكرر ومنتظم

 

اما في حال تم تبريد المعدن بشكل بطيء جدا, عندها نحصل على حالة ارضية ground state, وتكون متبلورة Crystal, حيث تكون كل الجزئيات مصفوفة بشكل منتظم كما هو موضح بالجزء رقم 1-c  من الرسم.

 تدعى عملية تسخين المعدن, ومن ثم تبريده بهذه الطريقة باسم التلدين annealing.

———————-

ارجو ان تكون القوانين الفيزيائية – التي تم استيحاء الخوارزمية منها – قد توضحت.

والى لقاء في الحلقة القادمة التي سنشرح خلالها هذه الخوارزمية.

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

مع تحيات

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

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

  1. خوارزمية محاكاة التلدين – الحلقة الاولى
  2. خوارزمية محاكاة التلدين – الحلقة الثانية
  3. خوارزمية محاكاة التلدين – مثال – الحلقة الثالثة
  4. خوارزمية محاكاة التلدين – برنامج التبريد – الحلقة الرابعة
  5. خوارزمية محاكاة التدلين – التطبيقات – الحلقة الخامسة والاخيرة
المصطلح الترجمة
Simulated Annealing محاكاة التلدين
molecules الجزيئات
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

 

 

, , , , ,

أضف تعليق