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

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

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

اگر مسیر رسیدن به هدف مهم نباشد، میتوانیم دسته دیگری از الگوریتم ها را در نظر بگیریم. الگوریتم های جست وجوی محلی، با استفاده از گره ی فعلی(به جای چند مسیر) عمل میکنند و فقط به همسایه های آن گره منتقل میشوند. مسیرهایی که در جست وجو ردیابی میشوند، نگهداری نخواهند شد. گرچه الگوریتم های جست وجوی محلی سیستماتیک نیستند، دو امتیاز عمده دارند: 1- از حافظه ی اندکی استفاده میکنند و 2- در فضاهای حالت بزرگ و نامتناهی که الگوریتم های سیستماتیک مفید نیستند، جوابهای منطقی را پیدا میکنند.

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

الگوریتم های جست وجوی محلی به جای اینکه مسیرهایی از "حالت شروع" را بطور سیستماتیک و منظم بررسی کنند، یک یا چند "حالت فعلی" را ارزیابی و اصلاح میکنند.

خانواده الگوریتم های جست وجوی محلی شامل روشهایی است که از فیزیک آماری (simulated annealing) و زیست شناسی تکاملی (الگوریتم های ژنتیک) سرچشمه میگیرند.

این الگوریتمها (الگوریتم های جست وجوی محلی) علاوه بر یافتن هدف، برای حل مسئله های بهینه سازی نیز مفید هستند. در این مسئله ها، هدف یافتن بهترین حالت براساس تابع هدف است. بسیاری از مسئله ها از مدل جست وجوی استاندارد پیروی نمیکنند.

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

الگوریتم های جست وجوی محلی این دورنما را بررسی میکنند. الگوریتم های جست وجوی محلی کامل، در صورت وجود هدف آنرا می یابد. الگوریتم های جست وجوی محلی بهینه، همواره یک مینیمم/ماکزیمم سراسری را پیدا میکند.