الگوریتم تپه نوردی – مبانی و مفاهیم + فیلم آموزشی رایگان

۳۳۱۵ بازدید
آخرین به‌روزرسانی: ۰۴ اسفند ۱۴۰۰
زمان مطالعه: ۲۰ دقیقه
الگوریتم تپه نوردی – مبانی و مفاهیم + فیلم آموزشی رایگان

تپه‌نوردی یک تکنیک بهینه‌سازی متعلق به خانواده الگوریتم‌های جستجوی محلی است؛ یک تکنیک تکرارشونده که با یک راه‌حل دلخواه شروع به کار کرده و سپس تلاش می‌کند تا با تغییر بر روی یک عنصر از راه حل، به پاسخ بهتری دست پیدا کند. اگر این تغییر منجر به ایجاد یک راه حل بهتر شود، تغییر دیگری بر روی این راه حل جدید انجام خواهد گرفت. این روال تا زمانی که بهبود بیشتری در راه حل میسر نباشد ادامه می‌یابد.

997696

فیلم آموزشی الگوریتم تپه نوردی

دانلود ویدیو

برای مثال، تپه‌نوردی می‌تواند در حل مسئله فروشنده دوره‌گرد مورد استفاده قرار گیرد. یافتن راه حل اولیه‌ای که تمام شهرها را ملاقات کرده اما در مقابل راه حل بهینه مسئله بسیار ضعیف باشد کار آسانی‌ست. الگوریتم با راه حلی مشابه، شروع به کار کرده و بر روی آن بهبودهای کوچکی همچون تعویض ترتیب ملاقات دو شهر ایجاد می‌کند. سرانجام، یک مسیر بسیار کوتاه‌تر از راه حل اولیه به دست خواهد آمد.

تپه‌نوردی برای یافتن بهینه محلی مناسب است اما تضمین نمی‌کند که بهترین راه حل ممکن (بهینه سراسری) از بین تمام راه‌حل‌های ممکن (فضای جستجو) پیدا شود. در مسائل محدب، تپه‌نوردی بهترین انتخاب است. مثال‌های از الگوریتم‌هایی که مسائل محدب را با تپه‌نوردی حل می‌کنند شامل الگوریتم سیمپلکس برای برنامه‌ریزی خطی، و جستجوی باینری است. اگر محیط جستجو محدب نباشد، این الگوریتم اغلب در یافتن ماکزیموم سراسری شکست خواهد خورد.

یک محیط جستجوی محدب.

یک محیط جستجوی محدب. الگوریتم تپه‌نوردی در جستجوی این گونه محیط‌ها موفق بوده و می‌تواند به ماکزیموم سراسری همگرا شود.

سادگی این تکنیک آن را در دسته الگوریتم‌های بهینه‌سازی بسیار محبوب کرده است. از تپه‌نوردی به شکل گسترده‌ای در هوش مصنوعی برای یافتن هدف از یک نود آغازگر استفاده می‌شود. تپه‌نوردی اغلب در شرایطی که زمان اجرای جستجو محدود است (همچون سیستم‌های بلادرنگ)، نتیجه بهتری از سایر الگوریتم‌های هم‌نوعش تولید می‌کند. تپه‌نوردی یک الگوریتم "همه زمانی" است: حتی اگر پیش از رسیدن به پایان نیز قطع شود یک جواب قابل قبول تحویل می‌دهد.

تعریف ریاضی الگوریتم تپه‌نوردی

تپه‌نوردی تلاش می‌کند تا تابع هدف (f(x را بیشینه (یا کمینه) کند، که x برداری از مقادیر پیوسته و/یا گسسته است. در هر تکرار، تپه‌نوردی یک عنصر از x را تنظیم کرده و بررسی می‌کند که آیا این تغییر باعث بهبود مقدار (f(x شده است یا خیر. (توجه کنید که این با متدهای گرادیان نزولی متفاوت است. در گرادیان نزولی تمام مقادیر x در هر تکرار بر حسب گرادیان تپه با هم تنظیم می‌شوند.) در تپه‌نوردی هر تغییری که باعث بهبود (f(x شود قابل قبول است و این پروسه تا زمانی که هیچ تغییری منجر به بهبود مقدار (f(x نگردد، ادامه می‌یابد. در این مرحله، x به عنوان "بهینه محلی" و خروجی الگوریتم خواهد بود.

تا کنون نسخه‌های بهبود یافته مختلفی از این تکنیک ارائه شده‌اند که می‌توان در آن بین به steepest ascent hill climbing، Stochastic hill climbing، و Shotgun hill climbing اشاره کرد.

حال که مفهوم الگوریتم تپه نوردی را دیدید، ممکن است که مطالب آموزشهای زیر از فرادرس برای شما مفید باشد:

بر اساس رای ۲۴ نفر
آیا این مطلب برای شما مفید بود؟
اگر بازخوردی درباره این مطلب دارید یا پرسشی دارید که بدون پاسخ مانده است، آن را از طریق بخش نظرات مطرح کنید.
۳ دیدگاه برای «الگوریتم تپه نوردی – مبانی و مفاهیم + فیلم آموزشی رایگان»

با سلام لطفا الگوریتم hill climbing و valley tracing رو بطور کامل آموزشش رو در سایت قرار دهید یا یک مرجع خوب معرفی بفرمایید

سلام.متن بسیار محدود و ضعیف بود!!!!نه شکل داشت نه الگوریتمش بود!!

سلام. ضمن تشکر و قدردانی از زحماتی که میکشید و مطالب بسیار مفیدی در سایتتون قرار میدید. ممنونم

نظر شما چیست؟

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *