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

(مهدی قنبری از اراک ) تپه‌نوردی یک تکنیک بهینه‌سازی متعلق به خانواده الگوریتم‌های جستجوی محلی است؛ یک تکنیک تکرارشونده که با یک راه‌حل دلخواه شروع به کار کرده و سپس تلاش می‌کند تا با تغییر بر روی یک عنصر از راه حل، به پاسخ بهتری دست پیدا کند. اگر این تغییر منجر به ایجاد یک راه حل بهتر شود، تغییر دیگری بر روی این راه حل جدید انجام خواهد گرفت. این روال تا زمانی که بهبود بیشتری در راه حل میسر نباشد ادامه می‌یابد.
برای مثال، تپه‌نوردی می‌تواند در حل مسئله فروشنده دوره‌گرد مورد استفاده قرار گیرد. یافتن راه حل اولیه‌ای که تمام شهرها را ملاقات کرده اما در مقابل راه حل بهینه مسئله بسیار ضعیف باشد کار آسانی‌ست. الگوریتم با راه حلی مشابه، شروع به کار کرده و بر روی آن بهبودهای کوچکی همچون تعویض ترتیب ملاقات دو شهر ایجاد می‌کند. سرانجام، یک مسیر بسیار کوتاه‌تر از راه حل اولیه به دست خواهد آمد.
تپه‌نوردی برای یافتن بهینه محلی مناسب است اما تضمین نمی‌کند که بهترین راه حل ممکن (بهینه سراسری) از بین تمام راه‌حل‌های ممکن (فضای جستجو) پیدا شود. در مسائل محدب، تپه‌نوردی بهترین انتخاب است. مثال‌های از الگوریتم‌هایی که مسائل محدب را با تپه‌نوردی حل می‌کنند شامل الگوریتم سیمپلکس برای برنامه‌ریزی خطی، و جستجوی باینری است. اگر محیط جستجو محدب نباشد، این الگوریتم اغلب در یافتن ماکزیموم سراسری شکست خواهد خورد.
یک محیط جستجوی محدب. الگوریتم تپه‌نوردی در جستجوی این گونه محیط‌ها موفق بوده و می‌تواند به ماکزیموم سراسری همگرا شود.
سادگی این تکنیک آن را در دسته الگوریتم‌های بهینه‌سازی بسیار محبوب کرده است. از تپه‌نوردی به شکل گسترده‌ای در هوش مصنوعی برای یافتن هدف از یک نود آغازگر استفاده می‌شود. تپه‌نوردی اغلب در شرایطی که زمان اجرای جستجو محدود است (همچون سیستم‌های بلادرنگ)، نتیجه بهتری از سایر الگوریتم‌های هم‌نوعش تولید می‌کند. تپه‌نوردی یک الگوریتم "همه زمانی" است: حتی اگر پیش از رسیدن به پایان نیز قطع شود یک جواب قابل قبول تحویل می‌دهد.
تپه‌نوردی تلاش می‌کند تا تابع هدف (f(x را بیشینه (یا کمینه) کند، که x برداری از مقادیر پیوسته و/یا گسسته است. در هر تکرار، تپه‌نوردی یک عنصر از x را تنظیم کرده و بررسی می‌کند که آیا این تغییر باعث بهبود مقدار (f(x شده است یا خیر. (توجه کنید که این با متدهای گرادیان نزولی متفاوت است. در گرادیان نزولی تمام مقادیر x در هر تکرار بر حسب گرادیان تپه با هم تنظیم می‌شوند.) در تپه‌نوردی هر تغییری که باعث بهبود (f(x شود قابل قبول است و این پروسه تا زمانی که هیچ تغییری منجر به بهبود مقدار (f(x نگردد، ادامه می‌یابد. در این مرحله، x به عنوان "بهینه محلی" و خروجی الگوریتم خواهد بود.
تا کنون نسخه‌های بهبود یافته مختلفی از این تکنیک ارائه شده‌اند که می‌توان در آن بین به steepest ascent hill climbing، Stochastic hill climbing، و Shotgun 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