موضوع مقاله: الگوریتم تپه‌نوردی | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # الگوریتم تپه‌نوردی | مقدمه: الگوریتم تپه‌نوردی (به انگلیسی: Hill climbing) الگوریتمی است که برای یافتن بهترین پاسخ یک مسئله یا برای پیدا کردن پاسخی از مسئله که به اندازهٔ کافی مناسب و بهینه باشد، استفاده می‌شود. | ## بخش 1: الگوریتم تپه‌نوردی | بررسی الگوریتم تپه‌نوردی تپه‌نوردی یک تکنیک بهینه‌سازی متعلق به خانواده الگوریتم‌های جستجوی محلی است؛ یک تکنیک تکرارشونده که با یک راه‌حل دلخواه شروع به کار کرده و سپس تلاش می‌کند تا با تغییر بر روی یک عنصر از راه حل، به پاسخ بهتری دست پیدا کند. اگر این تغییر منجر به ایجاد یک راه حل بهتر شود، تغییر دیگری بر روی این راه حل جدید انجام خواهد گرفت. برای مثال، تپه‌نوردی می‌تواند در حل مسئله فروشنده دوره‌گرد مورد استفاده قرار گیرد. یافتن راه حل اولیه‌ای که تمام شهرها را ملاقات کرده اما در مقابل راه حل بهینه مسئله بسیار ضعیف باشد کار آسانی‌ست. الگوریتم با راه حلی مشابه، شروع به کار کرده و بر روی آن بهبودهای کوچکی همچون تعویض ترتیب ملاقات دو شهر ایجاد می‌کند. تپه‌نوردی برای یافتن بهینه محلی مناسب است اما تضمین نمی‌کند که بهترین راه حل ممکن (بهینه سراسری) از بین تمام راه‌حل‌های ممکن (فضای جستجو) پیدا شود. مثال‌های از الگوریتم‌هایی که مسائل محدب را با تپه‌نوردی حل می‌کنند شامل الگوریتم سیمپلکس برای برنامه‌ریزی خطی، و جستجوی باینری است. اگر محیط جستجو محدب نباشد، این الگوریتم اغلب در یافتن ماکزیموم سراسری شکست خواهد خورد. الگوریتم تپه‌نوردی در جستجوی این گونه محیط‌ها موفق بوده و می‌تواند به ماکزیموم سراسری همگرا شود. از تپه‌نوردی به شکل گسترده‌ای در هوش مصنوعی برای یافتن هدف از یک نود آغازگر استفاده می‌شود. تپه‌نوردی اغلب در شرایطی که زمان اجرای جستجو محدود است (همچون سیستم‌های بلادرنگ)، نتیجه بهتری از سایر الگوریتم‌های هم‌نوعش تولید می‌کند. تپه‌نوردی یک الگوریتم "همه زمانی" است: حتی اگر پیش از رسیدن به پایان نیز قطع شود یک جواب قابل قبول تحویل می‌دهد. تپه‌نوردی تلاش می‌کند تا تابع هدف (f(x را بیشینه (یا کمینه) کند، که x برداری از مقادیر پیوسته و/یا گسسته است. در هر تکرار، تپه‌نوردی یک عنصر از x را تنظیم کرده و بررسی می‌کند که آیا این تغییر باعث بهبود مقدار (f(x شده است یا خیر. در گرادیان نزولی تمام مقادیر x در هر تکرار بر حسب گرادیان تپه با هم تنظیم می‌شوند.) در تپه‌نوردی هر تغییری که باعث بهبود (f(x شود قابل قبول است و این پروسه تا زمانی که هیچ تغییری منجر به بهبود مقدار (f(x نگردد، ادامه می‌یابد. در این‌جا بیشتر مسئله‌هایی مورد بحث قرار می‌گیرند که چندین پاسخ با ارزش برابر دارند و هدف ما یافتن یکی از آن هاست. | ## بخش 2: الگوریتم تپه‌نوردی | برای بررسی الگوریتم تپه‌نوردی مسئلهٔ زیر را بررسی می‌کنیم: - تابع f به هر یک از اعضای مجموعهٔ متناهی S یک عدد حقیقی نسبت می‌دهد. هدف ما یافتن عضوی از S است که بیش‌ترین (یا کم‌ترین) مقدار به آن نسبت داده شده‌است. همان گونه که گفته شد در این‌جا فرض بر این است که مقدار تابع f برای چندین عضو مختلف S بیشینه است و هدف ما یافتن تنها یکی از آن هاست. (در غیر این صورت معمولاً الگوریتم تپه‌نوردی، الگوریتم کار آمدی نیست) الگوریتم: ابتدا یکی از اعضای مجموعهٔ S را (به صورت تصادفی) انتخاب می‌کنیم و آن را A می‌نامیم. سپس در میان اعضایی از S که به A نزدیکند به دنبال پاسخ مناسب تری برای مسئله می‌گردیم. به بیانی دیگر نلاش می‌کنیم در میان اعضایی که به A نزدیکند عضوی بیابیم که مقدار تابع f برای آن بیشتر از باشد. بدیهی است که بیشینهٔ نسبی به دست آمده لزوماً پاسخ خواسته شده نیست؛ ولی اگر الگوریتم گفته شده چندین بار تکرار شود می‌توان به یافتن پاسخی مطلوب امیدوار بود. (در هر بار اجرای الگوریتم نخستین عضو به صورت تصادفی انتخاب می‌شود) بدی این الگوریتم این است که در یک تابع که مینیمم ویا ماکزیمم محلی زیادی دارد (مانند تابع Ackley)به راحتی در ان گیر می‌افتد و قدرت خروج از آنجا را ندارد چون این الگوریتم فقط نقاط اطراف خود را می‌بیند که در لحظه حضور در یک ماکزیمم محلی این احساس را دارد که از همه نقاط بالاتر است در حالی که چنین نیست و ان در یک ماکزیمم محلی اسیر شده‌است. هدف یافتن مسیری همیلتونی است که در آن مجموع وزن یال‌ها کمینه (یا به اندازهٔ کافی کم) باشد. (مسیر هامیلتونی مسیری است که شامل همهٔ رأس‌های گراف باشد) برای یافتن چنین مسیری می‌توان ابتدا یک مسیر هامیلتونی تصادفی انتخاب نمود و سپس در هر گام با ایجاد تغییری اندک در مسیر، مجموع وزن یال‌های آن مسیر را بهینه نمود. مسئلهٔ n وزیر می‌خواهیم در یک صفحهٔ n * n شطرنج، n وزیر شطرنج را به گونه‌ای قرار دهیم که هیچ دو وزیری یکدیگر را تهدید نکنند. (دو وزیر شطرنج در صورتی یکدیگر را تهدید می‌کنند که در یک سطر یا یک ستون یا یک قطر باشند) برای یافتن چیدمانی از n وزیر که در آن هیچ دو وزیری یکدیگر را تهدید نمی‌کنند ابتدا n وزیر را به صورتی تصادفی روی یک صفحهٔ شطرنج n * n قرار می‌دهیم. (بهتر است این چیدمان به گونه‌ای باشد که هیچ دو مهره‌ای هم سطر یا هم ستون نباشند) سپس در هر گام با ایجاد تغییراتی اندک در چیدمان مهره‌ها نلاش می‌کنیم تعداد زوج مهره‌هایی که یکدیگر را تهدید می‌کنند کاهش دهیم. روش عقبگرد تمامی جواب‌های مسئله را تولید کرده، و با صرف نظر کردن از گره‌های ناامیدکنندهٔ بهینگی قابل توجهی در زمان اجرای الگوریتم ایجاد می‌کند. اما با افزایش مقدار n و افزایش عمق درخت و تعداد فرزندان هر گره، سرعت اجرا نیز به صورت شبه نمایی افزایش یافته، و کارایی روش پایین می‌آید. اگر هدف از حل مسئله تنها رسیدن به یک جواب باشد، روش‌های دیگری وجود دارد که کارایی بهتری دارند. | ## بخش 3: الگوریتم تپه‌نوردی | این روش‌ها عموماً از چیدمان تصادفی یا شبه‌تصادفی (تصادفی هوشمند) برای رسیدن به یک جواب استفاده می‌کنند. اکثر الگوریتم‌های تکاملی و مکاشفه‌ای - مانند الگوریتم ژنتیک - در این حالت جوابگوی نیازها هستند. الگوریتم تپه‌نوردی تعمیم یافته همان‌طور که در الگوریتم تپه‌نوردی بررسی کردیم، این روش جستجوی محلی دارای مشکل قرار گرفتن در بهینگی محلی است. این مشکل تا حدی است که حتی در مورد مسائل ساده‌ای همچون مسئله ۸ وزیر نیز این روش جستجو از درصد موفقیت بسیار پایینی برخوردار بود. با این حال می‌توان تغییر کوچکی در این الگوریتم داد و تا حدودی میزان موقعیت الگوریتم تپه‌نوردی را در حل مسائله بهینه‌سازی بالا برد. مشکل الگوریتم تپه‌نوردی این بود که هنگام قادر به تغییر حالت از یک محل بهینگی به محل بهینگی دیگر نبود. اما برای گریز از بهینگی‌های محلی می‌توانیم ترتیبی اتخاذ کنیم که هنگام قرار گرفتن در بهینگی‌های محلی به بخش دیگری از فضای حالت جهش کنیم و سپس در آنجا به جستجوی جواب با روش تپه‌نوردی بپردازیم و این عمل را تا رسیدن به یک ماکزیمم سراسری تکرار کنیم. به عنوان مثال بهینه‌ترین جواب برای مسئله ۸ وزیر، نقطه‌ای است که در آن تعداد گاردهای جفت وزیرها صفر عدد باشد. اما مسائلی نیز وجود دارند که از ابتدا نمی‌توان مقدار بهینگی سراسری مسئله را در آن‌ها تشخیص داد. لازم است ذکر شود که برای مسائل مختلف می‌توانیم شرط پایان حلقه و نحوه اجرای الگوریتم را تغییر دهیم. لازم است ذکر شود که تابع Mutate را به‌طور کلی می‌توان با دو استراتژی مختلف پیاده‌سازی کرد : ۱. جهش‌های بزرگ در فضای حالت انجام دهد جهش کوتاه جهشی است که تعداد حالت‌های میان حالت فعلی و حالت جهش یافته کم باشد. استفاده از هرکدام از این روش‌ها بستگی به مسئله دارد و نمی‌توان در مورد ارجحیت یکی به دیگری اظهار نظر کرد. ما در این برنامه از جهش‌های کوتاه برای گریز از بهینگی‌های محلی استفاده کرده‌ایم. الگوریتم‌های مشابه در بسیاری از موارد یافت بیشینهٔ نسبی یا کمینهٔ نسبی با استفاده از الگوریتم تپه‌نوردی کارساز نیست. | ## جمع‌بندی | اما برای گریز از بهینگی‌های محلی می‌توانیم ترتیبی اتخاذ کنیم که هنگام قرار گرفتن در بهینگی‌های محلی به بخش دیگری از فضای حالت جهش کنیم و سپس در آنجا به جستجوی جواب با روش تپه‌نوردی بپردازیم و این عمل را تا رسیدن به یک ماکزیمم سراسری تکرار کنیم.