أرشيف لـ23 يناير, 2018

خوارزمية تسلق التل 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

, , , , , , , , , , ,

أضف تعليق