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

پیمایش گراف و پیمایش درخت
هرس آلفا بتا A* B* Beam الگوریتم بلمن–فورد Best-first Bidirectional الگوریتم جستجوی اول سطح D* الگوریتم جستجوی عمق اول Depth-limited الگوریتم دیکسترا الگوریتم فلوید-وارشال الگوریتم تپه‌نوردی جستجوی عمق اول عمیق‌کننده تکراری الگوریتم جانسون Lexicographic breadth-first Uniform-cost رده:الگوریتم‌های جستجو
جستار وابسته
برنامه‌ریزی پویا Search games

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

بررسی الگوریتم تپه نوردی

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

برای بررسی الگوریتم تپه نوردی مسئلهٔ زیر را بررسی می کنیم:

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

همان گونه که گفته شد در این جا فرض بر این است که مقدار تابع f برای چندین عضو مختلف S بیشینه است و هدف ما یافتن تنها یکی از آن هاست. (در غیر این صورت معمولاً الگوریتم تپه نوردی، الگوریتم کار آمدی نیست.)

الگوریتم :

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

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

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

Hill Climbing Algorithm

bestEval = -INF;

currentNode = startNode;

bestNode = NULL;

for MAX times

if (EVAL(currentNode) > bestEval)

bestEval = EVAL(currentNode);

bestNode = currentNode;

L = NEIGHBORS(currentNode);

nextEval = -INF;

for all x in L

if (EVAL(x) > nextEval)

currentNode = x;

nextEval = EVAL(x);

return currentNode

چند مثال

فروشندهٔ دوره گرد :

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

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

مسئلهٔ n وزیر :

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

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

اگر هدف از حل مساله تنها رسیدن به یک جواب باشد، روش‌های دیگری وجود دارد که کارایی بهتری دارند. این روش‌ها عموما از چیدمان تصادفی یا شبه‌تصادفی (تصادفی هوشمند) برای رسیدن به یک جواب استفاده می‌کنند. اکثر الگوریتم‌های تکاملی و مکاشفه‌ای - مانند الگوریتم ژنتیک - در این حالت جوابگوی نیازها هستند.

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

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

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

Procedure HillClimbing

 Generate a solution ( s' )
 Best = S'
 Loop
   S = Best
   S' = Neighbors (S)
   Best = SelectBest (S')
   IF there is no changes in Best solution THEN
        Jump to new state in state space
 Until stop criterion satisfied

End

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

   1. جهش در فضای حالت کوتاه باشد

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

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

الگوریتم‌های مشابه

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

منابع

http://en.wikipedia.org/wiki/Hill_climbing

http://www.talkorigins.org/faqs/genalg/genalg.html

http://ai.amini.eu/tutorial/ai/aiMetaExtendedHillclimbing.aspx