تسلق التلال

في التحليل العددي ، يعتبر تسلق التلال أسلوبًا رياضيًا للتحسين ينتمي إلى عائلة البحث المحلي .

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

على سبيل المثال، يمكن تطبيق خوارزمية تسلق التلال على مسألة البائع المتجول . من السهل إيجاد حل أولي يمر بجميع المدن، ولكنه غالبًا ما يكون ضعيفًا جدًا مقارنةً بالحل الأمثل. تبدأ الخوارزمية بهذا الحل وتُجري عليه تحسينات طفيفة، مثل تغيير ترتيب زيارة مدينتين. في النهاية، يُرجح الحصول على مسار أقصر بكثير.

يجد تسلق التل حلولاً مثالية للمسائل المحدبة - أما بالنسبة للمسائل الأخرى، فإنه سيجد فقط الحلول المثلى المحلية (الحلول التي لا يمكن تحسينها بواسطة أي تكوينات مجاورة)، والتي ليست بالضرورة أفضل حل ممكن ( الحل الأمثل العالمي ) من بين جميع الحلول الممكنة ( مساحة البحث ).

من أمثلة الخوارزميات التي تحل المسائل المحدبة باستخدام خوارزمية تسلق التلال، خوارزمية سيمبلكس للبرمجة الخطية والبحث الثنائي . ^{[ 1 ]}^{: 253}

لمحاولة تجنب الوقوع في الحلول المثلى المحلية، يمكن للمرء استخدام عمليات إعادة التشغيل (أي البحث المحلي المتكرر)، أو مخططات أكثر تعقيدًا تعتمد على التكرارات (مثل البحث المحلي المتكرر )، أو على الذاكرة (مثل تحسين البحث التفاعلي والبحث المحظور )، أو على التعديلات العشوائية بدون ذاكرة (مثل التلدين المحاكي ).

تُعدّ بساطة الخوارزمية النسبية سببًا في شيوع استخدامها كخيار أول بين خوارزميات التحسين. وهي تُستخدم على نطاق واسع في الذكاء الاصطناعي للوصول إلى حالة الهدف انطلاقًا من عقدة البداية. وتُستخدم خيارات مختلفة للعقد التالية وعقد البداية في الخوارزميات ذات الصلة. على الرغم من أن الخوارزميات الأكثر تطورًا، مثل التلدين المحاكي أو البحث المحظور، قد تُعطي نتائج أفضل، إلا أن خوارزمية تسلق التل تُؤدي الغرض نفسه في بعض الحالات. غالبًا ما تُحقق خوارزمية تسلق التل نتائج أفضل من الخوارزميات الأخرى عندما يكون الوقت المتاح لإجراء البحث محدودًا، كما هو الحال في الأنظمة الآنية، طالما أن عددًا قليلًا من الزيادات يتقارب عادةً نحو حل جيد (الحل الأمثل أو تقريب دقيق له). في المقابل، يُمكن اعتبار فرز الفقاعات خوارزمية تسلق تل (حيث يُقلل كل تبادل للعناصر المتجاورة من عدد أزواج العناصر غير المرتبة)، إلا أن هذا النهج بعيد كل البعد عن الكفاءة حتى مع قيم N المتواضعة، إذ يزداد عدد عمليات التبادل المطلوبة بشكل تربيعي.

خوارزمية تسلق التلال هي خوارزمية تعمل في أي وقت : يمكنها إرجاع حل صالح حتى لو تم مقاطعتها في أي وقت قبل انتهائها.

الوصف الرياضي

يسعى تسلق التلال إلى تعظيم (أو تقليل) دالة الهدف $f(\mathbf {x} )$ ، أين $\mathbf {x}$ هو متجه من القيم المتصلة و/أو المنفصلة. في كل تكرار، يقوم خوارزمية البحث عن التلال بتعديل عنصر واحد في $\mathbf {x}$ وتحديد ما إذا كان التغيير يحسن قيمة $f(\mathbf {x} )$ (لاحظ أن هذا يختلف عن طرق التدرج الهبوطي ، التي تُعدّل جميع القيم في $\mathbf {x}$ في كل تكرار وفقًا لانحدار التل.) مع تسلق التل، أي تغيير يحسن $f(\mathbf {x} )$ يتم قبول ذلك، وتستمر العملية حتى يتعذر إيجاد أي تغيير لتحسين قيمة $f(\mathbf {x} )$ . ثم $\mathbf {x}$ يقال إنها "مثالية محلياً".

في فضاءات المتجهات المنفصلة، كل قيمة ممكنة لـ $\mathbf {x}$ يمكن تصورها كرأس في رسم بياني . سيتبع تسلق التلال الرسم البياني من رأس إلى رأس، مع زيادة (أو تقليل) قيمة محليًا دائمًا. $f(\mathbf {x} )$ ، حتى الوصول إلى قيمة عظمى محلية (أو قيمة صغرى محلية ) $x_{m}$ يتم الوصول إليه.

المتغيرات

في خوارزمية تسلق التلال البسيطة ، يتم اختيار أقرب عقدة، بينما في خوارزمية تسلق التلال ذات الانحدار الأسرع، تتم مقارنة جميع العقد اللاحقة واختيار الأقرب إلى الحل. تفشل كلتا الخوارزميتين إذا لم تكن هناك عقدة أقرب، وهو ما قد يحدث في حال وجود قيم عظمى محلية في فضاء البحث لا تمثل حلولًا. تشبه خوارزمية تسلق التلال ذات الانحدار الأسرع خوارزمية البحث الأفضل أولًا ، التي تجرب جميع الامتدادات الممكنة للمسار الحالي بدلًا من امتداد واحد فقط. ^{[ 2 ]}

لا تفحص خوارزمية تسلق التلال العشوائية جميع الجيران قبل اتخاذ قرار الانتقال. بل تختار جارًا عشوائيًا، وتقرر (بناءً على مقدار التحسن في حالة هذا الجار) ما إذا كانت ستنتقل إليه أم ستفحص جارًا آخر. أما خوارزمية تسلق التلال بالاختيار الأول، فتُطبّق خوارزمية تسلق التلال العشوائية عن طريق توليد جيران عشوائيًا حتى يتم توليد جار أفضل، ثم يُختار هذا الجار. تُحقق هذه الطريقة أداءً جيدًا عندما يكون للحالات العديد من الخلفاء المحتملين (مثل الآلاف).^{[ 3 ]}

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

خوارزمية تسلق التلال ذات إعادة التشغيل العشوائي هي خوارزمية فوقية مبنية على خوارزمية تسلق التلال. تُعرف أيضًا باسم خوارزمية تسلق التلال العشوائية . تقوم هذه الخوارزمية بتسلق التلال بشكل تكراري، مع استخدام حالة ابتدائية عشوائية في كل مرة. $x_{0}$ . الأفضل $x_{m}$ يتم الاحتفاظ به: إذا أنتجت جولة جديدة من تسلق التلال نتيجة أفضل $x_{m}$ بدلاً من الحالة المخزنة، فإنه يحل محل الحالة المخزنة.

مشاكل

الحد الأقصى المحلي

لن يؤدي تسلق التلال بالضرورة إلى إيجاد القيمة العظمى المطلقة، بل قد يتقارب بدلاً من ذلك إلى قيمة عظمى محلية . لا تحدث هذه المشكلة إذا كانت الدالة الاستدلالية محدبة. ومع ذلك، نظرًا لأن العديد من الدوال ليست محدبة، فقد يفشل تسلق التلال في كثير من الأحيان في الوصول إلى القيمة العظمى المطلقة. تحاول خوارزميات البحث المحلي الأخرى التغلب على هذه المشكلة، مثل تسلق التلال العشوائي ، والمسارات العشوائية ، والتقسية المحاكاة .

على الرغم من وجود العديد من القيم العظمى المحلية في هذا الرسم البياني، إلا أنه لا يزال بالإمكان إيجاد القيمة العظمى العالمية باستخدام خوارزمية التلدين المحاكي. مع ذلك، فإن تطبيق هذه الخوارزمية يعتمد على طبيعة المشكلة، إذ يتطلب إيجاد *قفزات موفقة* تُحسّن الوضع. في مثل هذه الحالات المتطرفة، من المرجح أن تُنتج خوارزمية تسلق التلال قيمة عظمى محلية.

التلال والأزقة

تُشكّل التلال تحديًا كبيرًا لخوارزميات تسلق التلال التي تُحسّن الحلول في الفضاءات المتصلة. ولأن هذه الخوارزميات تُعدّل عنصرًا واحدًا فقط في المتجه في كل مرة، فإن كل خطوة ستتحرك في اتجاه محاذٍ للمحور. إذا كانت دالة الهدف تُنشئ تلة ضيقة تصعد في اتجاه غير محاذٍ للمحور (أو إذا كان الهدف هو التصغير، ممرًا ضيقًا ينزل في اتجاه غير محاذٍ للمحور)، فلن تتمكن خوارزمية تسلق التلال من صعود التلة (أو النزول في الممر) إلا بالتحرك بشكل متعرج. وإذا كانت جوانب التلة (أو الممر) شديدة الانحدار، فقد تُضطر الخوارزمية إلى اتخاذ خطوات صغيرة جدًا أثناء تحركها المتعرج نحو موقع أفضل. وبالتالي، قد يستغرق صعود التلة (أو النزول في الممر) وقتًا طويلًا جدًا.

على النقيض من ذلك، يمكن لطرق الانحدار التدرجي أن تتحرك في أي اتجاه قد يصعد أو ينزل فيه التل أو الممر. لذا، يُفضل عمومًا استخدام الانحدار التدرجي أو طريقة التدرج المترافق على تسلق التلال عندما تكون الدالة المستهدفة قابلة للتفاضل. مع ذلك، تتميز طرق تسلق التلال بأنها لا تتطلب أن تكون الدالة المستهدفة قابلة للتفاضل، لذا قد يُفضل استخدامها عندما تكون الدالة المستهدفة مركبة.

هضبة

من المشاكل الأخرى التي قد تظهر أحيانًا في خوارزمية البحث عن التلال مشكلة الهضبة. تحدث الهضبة عندما تكون مساحة البحث مسطحة، أو مسطحة لدرجة يصعب معها تمييز القيمة التي تُرجعها الدالة المستهدفة عن القيم المُرجعة للمناطق المجاورة، وذلك بسبب دقة الآلة في تمثيل القيمة. في مثل هذه الحالات، قد لا يتمكن الباحث من تحديد الاتجاه الصحيح للتقدم، وقد يتجول في اتجاه لا يُحقق أي تقدم.

خوارزمية تسلق التلال في الفضاء المنفصل هي خوارزمية شبه رمزية  العقدة الحالية := عقدة البداية حلقة تكرارية L := NEIGHBORS(currentNode) nextEval := −INF nextNode := NULL لكل x في L، إذا كان EVAL(x) > nextEval، فقم بما يلي: nextNode := x nextEval := EVAL(x) إذا كان nextEval ≤ EVAL(currentNode) // إرجاع العقدة الحالية لعدم وجود جيران أفضل إرجاع العقدة الحالية العقدة الحالية := العقدة التالية

خوارزمية تسلق التلال في الفضاء المستمر هي currentPoint := initialPoint // متجه ذو مقدار صفري مشترك stepSize := initialStepSizes // متجه من جميع القيم 1 هو العنصر المشترك التسارع := بعض التسارع // قيمة مثل 1.2 شائعة candidate[0] := −acceleration candidate[1] := −1 / acceleration candidate[2] := 1 / acceleration candidate[3] := acceleration أفضل نتيجة := EVAL(النقطة الحالية) حلقة تكرارية قبل النتيجة := أفضل نتيجة لكل عنصر i في النقطة الحالية، قم بما يلي: beforePoint := currentPoint[i] bestStep := 0 for j from 0 to 3 do // جرّب كل موقع من المواقع الأربعة المرشحة الخطوة := حجم الخطوة[i] × المرشح[j] currentPoint[i] := beforePoint + step النتيجة := EVAL(النقطة الحالية) إذا كانت النتيجة > أفضل نتيجة ، أفضل نتيجة := النتيجة أفضل خطوة := خطوة إذا كانت قيمة bestStep تساوي 0، currentPoint[i] := beforePoint stepSize[i] := stepSize[i] / acceleration آخر currentPoint[i] := beforePoint + bestStep stepSize[i] := bestStep // التسارع إذا كان (أفضل نتيجة - النتيجة السابقة) < إبسيلون، فأرجع النقطة الحالية

مقارنة بين الخوارزمية الجينية والتحسين العشوائي .

انظر أيضاً

مراجع

راسل، ستيوارت جيه ؛ نورفيج، بيتر (2003)، الذكاء الاصطناعي: منهج حديث ( الطبعة الثانية)، أبر سادل ريفر، نيو جيرسي: برنتيس هول، الصفحات 111-114 ، رقم ISBN 0-13-790395-2

↑ سكينا، ستيفن (2010). دليل تصميم الخوارزميات ( الطبعة الثانية). سبرينغر ساينس + بيزنس ميديا . ISBN 978-1-849-96720-4.
↑ تستند هذه المقالة إلى مواد مأخوذة من Hill+climbing في قاموس الحوسبة المجاني على الإنترنت قبل 1 نوفمبر 2008 وتم دمجها بموجب شروط "إعادة الترخيص" الخاصة بـ GFDL ، الإصدار 1.3 أو أحدث.
↑ راسل، ستيوارت جيه؛ نورفيج، بيتر (2022). الذكاء الاصطناعي: منهج حديث . سلسلة برنتيس هول في الذكاء الاصطناعي. مينغ-وي تشانغ، جاكوب ديفلين، أنكا دراغان، ديفيد فورسيث، إيان غودفيلو، جيتندرا مالك، فيكاش مانسينغكا، جوديا بيرل، مايكل جيه. وولدريدج (الطبعة الرابعة، العالمية ). بوسطن: بيرسون. ص 131. ISBN 978-1-292-40117-1.

للمزيد من القراءة

لاسري، جورج (2018). منهجية لتحليل الشفرات الكلاسيكية باستخدام خوارزميات البحث الفوقية (ملف PDF) . مطبعة جامعة كاسل . رقم ISBN 978-3-7376-0459-8.

روابط خارجية

تسلق التلال في ويكي بوكس

[1] سكينا، ستيفن (2010). دليل تصميم الخوارزميات ( الطبعة الثانية). سبرينغر ساينس + بيزنس ميديا . ISBN 978-1-849-96720-4.

[2] تستند هذه المقالة إلى مواد مأخوذة من Hill+climbing في قاموس الحوسبة المجاني على الإنترنت قبل 1 نوفمبر 2008 وتم دمجها بموجب شروط "إعادة الترخيص" الخاصة بـ GFDL ، الإصدار 1.3 أو أحدث.

[3] راسل، ستيوارت جيه؛ نورفيج، بيتر (2022). الذكاء الاصطناعي: منهج حديث . سلسلة برنتيس هول في الذكاء الاصطناعي. مينغ-وي تشانغ، جاكوب ديفلين، أنكا دراغان، ديفيد فورسيث، إيان غودفيلو، جيتندرا مالك، فيكاش مانسينغكا، جوديا بيرل، مايكل جيه. وولدريدج (الطبعة الرابعة، العالمية ). بوسطن: بيرسون. ص 131. ISBN 978-1-292-40117-1.

[ 1 ]

[ 2 ]

[ 3 ]

اللغة	العربية (RTL)
روابط موسوعية	30 رابطاً
المصدر الأصلي	ويكيبيديا ↗