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

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

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

اگرچه این روش های جستجو سیستمانیک نیستند، با این این الگوریتم ها دو خاصیت ویژه را دارا میباشند.

  • این روش ها حافظه بسیار کمی مصرف میکنند که معمولا مقداری ثابت است.
  •  میتوانند راه حل های قابل قبولی در فضای وضعیت های بزرگ و یا نامتناهی را بیابند.

بررسی نمودار زیر میتواند به درک ما از الگوریتم های جستجوی محلی کمک کند.

نمودار کارکرد الگوریتم جستجوی محلی

به نمودار فوق نموردا state-space landscape  میگویند. همانطور که مشاهده میکنید در حالی که محور X ها روند پیشرفت وضعیت ها را نمایش میدهد، محور Y ها نمایشگر هزینه وضعیتها میباشد. حال با قبول این فرض خواهیم گفت که هدف در این روش های جستجو یافتن پایین ترین درّه و یا همان Global Minimum میباشد. الگوریتم های جستجوی محلی با بررسی ساختار داده ای مشابه به نمودار فوق اقدام به یافتن وضعیت هدف مینمایند. اگر الگوریتم جستجوی محلی ما کامل باشد، طبیعتا در صورت وجود پاسخ در نمودار فوق قطعا آن را خواهد یافت. از طرفی الگوریتم های جستجوی محلی بهینه قادر به یافتن Global Minimum میباشند. (دوستان دقت بفرمایید که در صورتی که مقدار تابع هزینه را منفی در نظر بگیریم باید به سمت Global Maximumحرکت نماییم.)

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

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

One Comment

Add a Comment

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

Copy Protected by Chetan's WP-Copyprotect.