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

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

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

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

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

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

همانطور که میدانید مسئله معروف هشت وزیر از این قرار است که میبایست  8 مهره وزیر را در یک صفحه شطرنج بنحوی قرار داد که هیچ یک دیگری را مورد اثابت قرار ندهد. حال فرض کنید برای حل این مسئله با روش الگوریتم جستجوی تپه نوردی مراحل زیر را ادامه دهیم.
ابتدا وضعیت اولیه را ایجاد مینماییم. فرض میکنیم وضعیت اولیه وضعیتی باشد که در آن هر 8 مهره در ستون های سطر اول صفحه قرار دارند.  وقتی این وضعیت را در اختیار الگوریتم قرار دهیم، الگوریتم با جابجایی تک مهره وزیرها در ستون ها تمامی وضعیت های مجاور وضعیت ابتدایی را ایجاد مینماید. بدین ترتیب پر واضح است که برای وضعیت اولیه 8*7 یا 56 وضعیت مجاور وجود خواهد داشت. حال الگوریتیم هیوریستیک این 56 وضعیت را با وضعیت فعلی مقایسه مینماید. اگر در میان این 56 وضعیت، وضعیتی بود که هیوریستیک با مقدار کمتری نسبت به وضعیت فعلی داشت (کمترین در میان کمترها)، عملیات فوق برای آن تکرار میشود. این روال آنقدر ادامه پیدا خواهد نمود تا به وضعیتی برسیم که وضعیت های مجاور آن هیوریستیکی کمتر از آن نداشته باشند! یعنی در این حالت عملا به یک قله/دره (Local یا Global) رسیده ایم. با رسیدن به چنین شرایطی کار الگوریتم به پایان خواهد رسید و وضعیت نهایی را Return  خواهد نمود.
تصویر زیر نشان میدهد که در صورت جابجایی هر کدام از مهره ها به خانه های دیگر وضعیت ایجاد شده جدید دارای چه هیوریستیکی خواهد بود.  (هیوریستیک وضعیت فعلی برابر با 17 میباشد)

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

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

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

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

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

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

الگوریتم جستجوی تپه نورد و مسئله معروف 8 وزیر

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

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

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

فلات یا کوه پایه به ناحیه های صاف از نمودار وضعیت-هزینه میگویند. شما میتوانید در تصویر نمودار بالا نمونه های از فلات را مشاهده نمایید. معنی وجود فلات در طول روند کار الگوریتم جستجوی تپه نوردی کاملا واضح و روشن است. تفسیر چنین رخدادی این است که به وضعیتی رسیده ایم که هیوریستیک آن با هیوریستیک وضعیت های مجاور آن کاملا برابر میباشد. یک فلات میتواند یک فلات ِ 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  خیلی سریع پاسخ مسئله را خواهد یافت. از طرفی در مسائل واقعی نمودار مذکور بیشتر شبیه سطحی مملو از ناهمواری هاست.

الگوریتم جستجوی محلی

Add a Comment

Your email address will not be published. Required fields are marked *

Copy Protected by Chetan's WP-Copyprotect.