الگوریتم تپه‌نوردی: تفاوت میان نسخه‌ها

'''الگوریتم تپه نوردی''' (Hill climbing) الگوریتمی است که برای یافتن بهترین پاسخ یک مسئله یا برای پیدا کردن پاسخی از مسئله که به اندازهٔ کافی مناسب و بهینه باشد، استفاده می شودمی‌شود.

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

- تابع f به هر یک از اعضای [[مجموعهٔ متناهی]] S یک [[عدد حقیقی]] نسبت می دهدمی‌دهد. هدف ما یافتن عضوی از S است که بیش‌ترین (یا کم ترین) مقدار به آن نسبت داده شده استشده‌است.

ابتدا یکی از اعضای مجموعهٔ S را (به صورت تصادفی) انتخاب می کنیم و آن را A می نامیم. سپس در میان اعضایی از S که به A نزدیکند به دنبال پاسخ مناسب تری برای مسئله می گردیم. به بیانی دیگر نلاش می کنیم در میان اعضایی که به A نزدیکند عضوی بیابیم که مقدار تابع f برای آن بیش تربیشتر از <math>f ( A )</math> باشد. سپس این روند را ادامه می دهیم تا به یک بیشینهٔ نسبی برای f دست یابیم.

بدیهی است که بیشینهٔ نسبی به دست آمده لزوماً پاسخ خواسته شده نیست. ولی اگر الگوریتم گفته شده چندین بار تکرار شود می توانمی‌توان به یافتن پاسخی مطلوب امیدوار بود. (در هر بار اجرای الگوریتم نخستین عضو به صورت تصادفی انتخاب می شودمی‌شود.)

بدی این الگوریتم این است که در یک تابع که مینیمم ویا ماکزیمم محلی زیادی دارد(مانند تابع Ackley)به راحتی در ان گیر می‌افتد و قدرت خروج از انجا را ندارد چون این الگوریتم فقط نقاط اطراف خود را میبیند که در لحظه حضور در یک ماکزیمم محلی این احساس را دارد که از همه نقاط بالاتر است در حالی که چنین نیست و ان در یک ماکزیمم محلی اسیر شده استشده‌است.

سورس برنامه تپه نوردی در محیط دو بعدی (که با f سه بعدی می شودمی‌شود)

یک گراف ساده همبند را که یال‌های آن وزن دار است، در نظر بگیرید. هدف یافتن مسیری همیلتونی است که در آن مجموع وزن یال‌ها کمینه (یا به اندازهٔ کافی کم) باشد. (مسیر هامیلتونی مسیری است که شامل همهٔ راس‌هایرأس‌های گراف باشد.)

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

می خواهیم در یک صفحهٔ n * n شطرنج، n وزیر شطرنج را به گونه ایگونه‌ای قرار دهیم که هیچ دو وزیری یکدیگر را تهدید نکنند. (دو وزیر شطرنج در صورتی یکدیگر را تهدید می کنندمی‌کنند که در یک سطر یا یک ستون یا یک قطر باشند.)

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

روش عقبگرد تمامی جواب‌های مسئله را تولید کرده، و با صرف نظر کردن از گره‌های نا امید کنندهٔامیدکنندهٔ بهینگی قابل توجهی در [[زمان اجرای الگوریتم]] ایجاد می‌کند. اما با افزایش مقدار n و افزایش عمق درخت و تعداد فرزندان هر گره، سرعت اجرا نیز به صورت شبه نمایی افزایش یافته، و کارایی روش پایین می‌آید.

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

با این حال می توانمی‌توان تغییر کوچکی در این الگوریتم داد و تا حدودی میزان موقعیت الگوریتم تپه نوردی را در حل مسائله [[بهینه سازی]] بالا برد. مشکل الگوریتم تپه نوردی این بود که هنگام قادر به تغییر

حالت از یک محل بهینگی به محل بهینگی دیگر نبود. اما برای گریز از بهینگی هایبهینگی‌های محلی می توانیممی‌توانیم ترتیبی اتخاذ کنیم که هنگام قرار گرفتن در بهینگی هایبهینگی‌های محلی به بخش دیگری از فضای حالت جهش کنیم و سپس در آنجا به جستجوی جواب با روش تپه نوردی بپردازیم و این عمل را تا رسیدن به یک ماکزیمم سراسری تکرار کنیم. [[شبه کد]] زیر نحوه اجرای این الگوریتم را نشان می دهد :

در این روش علاوه بر دو تابع Objective و Neighbor ، تابعی با نام Mutate نیز خواهیم داشت که وظیفه این تابع جهش در فضای حالت مسئله خواهد بود. همچنین باید بتوان نقطه بهینگی سراسری را تشخیص داد. به عنوان مثال بهینه ترینبهینه‌ترین جواب برای مسئله 8 وزیر ، نقطه اینقطه‌ای است که در آن تعداد گاردهای جفت وزیرها صفر عدد باشد. اما مسائلی نیز وجود دارند که از ابتدا نمی توان مقدار بهینگی سراسری مسئله را در آن هاآن‌ها تشخیص داد. لازم به ذکر است که برای مسائل مختلف می توانیممی‌توانیم شرط پایان حلقه و نحوه اجرای الگوریتم را تغییر دهیم. لازم به ذکر است که تابع Mutate را به طوربه‌طور کلی می توانمی‌توان با دو استراتژی مختلف پیاده سازیپیاده‌سازی کرد :

2. جهش هایجهش‌های بزرگ در فضای حالت انجام دهد

جهش کوتاه جهشی است که تعداد حالت هایحالت‌های میان حالت فعلی و حالت [[جهش یافته]] کم باشد. نقطه مقابل جهش کوتاه نیز جهش بلند می باشدمی‌باشد. استفاده از هرکدام از این روش‌ها بستگی به مسئله دارد و نمی توان در مورد ارجحیت یکی به دیگری اظهار نظر کرد. ما در این برنامه از جهش هایجهش‌های کوتاه برای گریز از بهینگی هایبهینگی‌های محلی استفاده کرده ایم.

در بسیاری از موارد یافت بیشینهٔ نسبی یا کمینهٔ نسبی با استفاده از الگوریتم تپه نوردی کارساز نیست. در این گونه موارد از الگوریتم‌های کارآمد تری چون simulated annealing استفاده می شودمی‌شود. در این الگوریتم ها، پیمایش روی اعضای S همواره در جهت افزایش مقدار تابع f نیست.

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