• شماره مطلب : 23
• دسته بندی : هوش مصنوعی
• عنوان : الگوریتم جستجوی تپه نورد
• نویسنده : NetBoss
• پیش نیاز : الگوریتم جستجوی محلی
• پروژه عملی : پروژه 8 وزیر – تپه نورد

الگوریتم جستجوی تپه نوردی چگونه کار میکند؟

شرح الگوریتم جستجوی تپه نوردی با مثال 8 وزیر

مشکلات الگوریتم جستجوی تپه نوردی

در کتاب راسل سه مشکل اساسی برای این الگوریتم جستجو عنوان شده است که ما نیز به شرح و بررسی آنها خواهیم پرداخت.

• • • • Local Maxima / مشکل قله و یا دره محلی
      • Ridges / مشکل سلسله قله ها
      • plateau / مشکل فلات

مشکل قله و یا دره محلی

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

تصویر زیر را با دقت بررسی بفرمایید. الگوریتم جستجوی تپه نوردی عملا به یک Local Maxima رسیده است که هر حرکت وزیر در آن هیوریستیک وضعیت فعلی را افزایش میدهد!

مشکل سلسله قله ها

در کتاب راسل ذکر شده که سلسله قله های (پشت سر هم ) محلی باعث خواهند شد تا الگوریتم جسجتوی حریصانه با مشکل مواجه شوند. تا اینجای کار در کتاب به همین توضیح مختصر بسنده شده و بیش از این در این مورد توضیحی داده نشده است.

  مشکل فلات یا کوه پایه

فلات یا کوه پایه به ناحیه های صاف از نمودار وضعیت-هزینه میگویند. شما میتوانید در تصویر نمودار بالا نمونه های از فلات را مشاهده نمایید. معنی وجود فلات در طول روند کار الگوریتم جستجوی تپه نوردی کاملا واضح و روشن است. تفسیر چنین رخدادی این است که به وضعیتی رسیده ایم که هیوریستیک آن با هیوریستیک وضعیت های مجاور آن کاملا برابر میباشد. یک فلات میتواند یک فلات ِ Local Maximum باشد. (اگر اهل کو هنوردی هستید، مثل قله ای هست که امتداد آن یک دشت صاف است!) همچنین یک فلات میتواند شانه shoulder باشد که ادامه روند جستجو از آنجا امکان پذیر است. نکته مهم در مورد فلات ها این است که احتمال شکست خوردن جستجو در صورت مواجه شدن با آنها امکان پذیر است!

بررسی دقیق مواجهه با مشکلات فوق

در تمامی سه مشکل شرح داده شده فوق الگوریتم جستجوی تپه نوردی قادر به ادامه روال یافتن پاسخ نخواهد بود. در کتاب راسل ذکر شده که در 86% موارد حل مسئله 8 وزیر (با وضعیت اولیه رندم)، الگوریتم با شکست مواجه شده و تنها در 14% موارد الگوریتم موفق به یافتن پاسخ نهایی شده است! با این وجود در کتاب ادعا شده است که الگوریتم بسیار سریع عمل میکند و بطور میانگین برای حالت های موفق (همان 14%) با چهار حرکت پاسخ را میابد. همچنین گفته شده که در حالت هایی که به دلایل فوق الگوریتم با مشکل مواجه میشود بطور میانگین تنها با گذشت سه مرحله از اجرای آن الگوریتم اعلام شکست مینماید. این آمار برای مجموعه فضای حالت 17 ملیونی (8^8) مسئله 8 وزیر قابل قبول است.

رفع مشکل فلات های شانه

پیشتر ذکر کردیم که مواجهه با شانه که یک نوع خاص از فلات میباشد میتواند به شکست الگوریتم تپه نوردی ختم شود. همچنین یادآوری میکنم که مواجهه با یک فلات Local Maximum قطعا به شکست الگوریتم ختم خواهد. حال شما ممکن است با خود بیاندیشید که در صورت مواجهه با یک شانه شانس فرار از آن و اوج گیری مجدد الگوریتم برای رسیدن به قله امکان پذیر باشد! چطور؟! اینگونه که در صورت تشخیصِ رسیدن به یک فلات کماکان به الگوریتم اجازه دهیم تا به کار خود ادامه دهد، به این امید که الگوریتم از فلات شانه عبور کرده و دوباره اوج بگیرد. اما از آنجا که الگوریتم معیاری برای تشخیص فلات های شانه از فلات های Local Maximum  ندارد با این کار احتمال گیر افتادن در لوپ نامتناهی وجود خواهد داشت. راسل برای رفع مشکل مذکور پیشنهاد داده تا تعداد این تلاش ها از تعداد خاصی (مثلا x بار ) تجاوز نکند. مثلا فرض کنید الگوریتم در طول حل مسئله با یک فلات مواجه شود. به الگوریتم تا 100 بار اجازه داده میشود تا بروری خط مستقیم فلات حرکت نماید. اگر موفق به اوج گیری شد که روال ادامه پیدا خواهد کرد در این صورت برای جلوگیری از تکرار نامتناهی الگوریتم اعلام شکست مینماید. به تکنیکی که برای عبور از فلات های شانه عنوان شد تکنیک Sideways moves میگویند.  نکته بسیار شگفت انگیز که در کتاب عنوان شده این است که با بکار گیری این تکنیک تعداد دفعات موفقیت از 14% به 94% افزایش پیدا خواهد کرد! با این وجود یادمان باشد که هیچ موفقیتی بی هزینه نیست! این بدان معناست که با تکنیک جدید بطور تقریبی هر پیروزی الگوریتم به 21 و برای اعلام شکست به 64 حرکت نیازمند است!!!

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

از الگوریتم جستجوی تپه نوردی ورژن های مختلفی وجود دارد. ورژنی که در بالا به شرح آن پرداختیم معروف به steepest-ascent میباشد. در ادامه به ورژن های دیگر الگوریتم جستجوی تپه نورد خواهیم پرداخت.

ورژن جستجوی تپه نورد شانسی

یکی دیگر از ورژن های معروف الگوریتم اصلی الگوریتم Stochastic hill climbing یا الگوریتم جستجوی تپه نوردی شانسی میباشد. تفاوت اصلی این الگوریتم با الگوریتم اصلی این است که در الگوریتم اصلی همیشه ازمیان وضعیت های مجاور آن وضعیتی را انتخاب میکنیم که هیوریستیک آن از هیوریستیک وضعیت جاری کمتر و همچنین دارای کمترین هیوریستیک در میان دیگر وضعیت های مجاور است. در حالی که در روش شانسی از میان تمام وضعیت های مجاوری که دارای هیوریستیکی کمتری میباشند یکی را بصورت رندم انتخاب مینماییم. طبق نظر راسل این روش نسبت به روش اصلی از سرعت پایین تری برخوردار است با این حال در بعضی مسائل روش های بهتری را جهت حل مسئله ارائه میدهد.

ورژن جستجوی تپه نوردی انتخاب اول

ورژن سوم این الگوریتم، ورژن First-choice hill climbing یا تپه نورد انتخاب اول میباشد. این ورژن از نظر پیاده سازی شبیه به ورژن تپه نورد شانسی میباشد با این تفاوت که الگوریتم وضعیت های مجاور وضعیت جاری را تولید میکند و به محض رسیدن به اولین وضعیتی که هیوریستیک آن کمتر از هیوریستیک وضعیت جاری باشد کار را با آن وضعیت جاری ادامه میدهد. باید دقت کرد در صورتی که در مسئله برای وضعیت جاری تعداد بسیار زیادی از وضعیت های مجاور وجود داشت که دارای هیوریستیک های قابل قبول باشند (مثلا هزار عدد) این ورژن بازدهی بالایی خواهد داشت. 

ورژن جستجوی تپه نوردی با شروع مجدد رندم

 Random-restart hill climbing یکی دیگر از ورژن های الگوریتم جستجوی تپه نوردی میباشد. این الگوریتم بر یک ضرب المثل معروف انگلیسی که میگوید “!If at first you don’t succeed, try, try again” استوار است. در واقع این ورژن تا زمانی که به پاسخ نهایی نرسد با مجموعه ای از وضعیت های اولیه رندوم مراحل جستجو را مجددا انجام خواهد داد. یعنی به زبان ساده آنقدر تلاش میکند تا به پاسخ مناسب برسد! بر خلاف الگوریتم اصلی که غیر کامل است این روش کامل میباشد(در کتاب راسل از صفت trivially برای کامل بودن آن استفاده شده!) . زیرا از نظر علم احتمالات خود وضعیت هدف میتواند در روند ایجاد وضعیت های اولیه رندم ایجاد شود!!!

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

موفقیت الگوریتم جستجوی تپه نوردی بسیار وابسته به نمودار فضای فضای حالت آن میباشد. اگر فضای حالت دارای Local Maxiama ها و فلات های کمی باشد ورژه Random Restart Search  خیلی سریع پاسخ مسئله را خواهد یافت. از طرفی در مسائل واقعی نمودار مذکور بیشتر شبیه سطحی مملو از ناهمواری هاست.