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

الگوریتم تپه نوردی ( 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 )