سلام

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

منبع مورد بررسی در این بخش هوش مصنوعی نوشته ی راسل -پیترنوروینگ

ویراست سوم-۲۰۱۰ چاپ سوم، به ترجمه ی جعفر نژاد.
فیلم های دانشگاه صنعتی شریف
=========

پیشنهاد شما برای منابع بهتر و کمک با توجه به سایر منابع باعث می شود تردید ها کاسته شود و پاسخ گویی به تست های این بخش با تردید کمتری باشد.(پس اگر منبع بهتری سراغ دارید اطلاع دهید)

---

شرح کلیت و هدف جستجوی محلی :

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

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


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

۱-۱- الگوریتم های جستجوی محلی و مساله های بهینه سازی
شرح کلیت :
در این الگوریتم ها مانند مساله ی ۸ وزیر مسیر رسیدن به هدف مهم نیست و تنها پیکربندی نهایی مهم است.

نکته : وقتی مسیر رسیدن به هدف مهم نباشد یعنی گره ای در حافظه ذخیره نمی شود.
الگوریتم های جستجوی محلی با استفاده از گره ی فعلی عمل می کنند و فقط به همسایه های ان گره منتقل میشوند و مسیر هایی که در جستجو رد یابی می شوند نگهداری نخواهند شد.
دو امتیاز عمده الگوریتم های جستجوی محلی :
۱)از حافظه اندکی استفاده میکنند(معمولا مقدار ثابت)
۲)در فضاهای حالت بزرگ و نامتناهی جواب های منطقی را پیدا میکنند.
====
نکته ها :
۱)الگوریتم های جستجوی محلی علاوه بر یافتن هدف برای حل مسائل بهینه سازی نیز مفید هستند
۲)در این مساله ها هدف یافتن بهترین حالت بر اساس تابع هدف است

سوال : منظور از مورد بالا چیست ؟
به عنوان مثال در طبیعت یک تابع هدف وجود دارد که تکامل داروینی را میتوان تلاش برای بهینه سازی آن دانست و نمیتوان این روش ها را قائل به یک وضعیت سیستماتیک دانست.
پ ن :(در کتاب فرگشت و ژنتیک هم با اجازه تون من خوندم قبلا که نقش تکامل داروین این هستش که بر اساس یک سری خصوصیات چطور میتوانیم نسل بعدی را برتر کنیم و این حالت کلی نیست بلکه بر اساس انتخاب بهترین ویژگی ها از هر دو نفر برای تولید نسل بعدی هستش که موضوع قسمت ژنتیک می باشد)
پس وقتی هدف تنها بهینه سازی هست آزمون هدف و هزینه ی مسیر برای این مسائل وجود ندارد.
====
۱-۱-۱ ) جستجوی تپه نوردی
۱-۱-۲) simulated annealing
۱-۱-۳) جستجوی پرتو محلی
۱-۱-۴)الگوریتم های ژنتیک

در ادامه به توضیح هر بخش خواهیم پرداخت :

۱-۱-۱ ) جستجوی تپه نوردی ااا (hill-climbing)
الگوریتم جستجوی تپه نوردی(نسخه ی تیز ترین صعود(یا شیب)) حلقه ای است که در جهت افزایش مقدار حرکت می کند(به طرف بالای تپه)-وقتی به قله ای رسید که هیچ همسایه ای از آن بلندتر نیست خاتمه می یابد. این الگوریتم درخت جستجو را نگهداری نمیکند لذا ساختمان داده ی گره ی فعلی فقط باید حالت و مقدار تابع هدف را نگهداری کند.تپه نوردی به همسایه های حالت فعلی نگاه میکند.مثل تلاش برای یافتن قله ی کوه اورست در مه گرفتگی غلیظ در حالی که دچار فراموشی هستید.
نکته :
۱) مه گرفتگی غلیظ منظور ناتوانی در یافتن ماکزیمم سراسری به صورت قطعی است.(بعد خواهید دید که یکی از دلایل توقف این الگوریتم ماکزیمم محلی است)
۲)دچار فراموشی بودن منظور عدم استفاده از حافظه یا همان استفاده ی اندک است(فلسفه ی جستجوی محلی نیز همین است)

نکته: الگوریتم های جستجوی محلی معمولا از فرموله کردن حالت کامل استفاده میکنند(۸ وزیر)
نکته : تپه نوردی گاهی جستجوی محلی حریصانه نام دارد زیرا بدون این که قبلا فکر کند به کجا برود حالت های همسایه ی خوبی را انتخاب می کند
سوال : دلایل توقف الگوریتم تپه نوردی؟ سه مورد دارد :

۱)ماکزیمم محلی(local maxima)
قله ای که از هر یک از همسایه هایش بلند تر است اما از ماکزیمم سراسری کوتاه تر است.الگوریتم های تپه نوردی که به مجاورت ماکزیمم محلی می رسند به طرف بالا و به سمت قله حرکت میکنند ولی از آن پس متوقف می شوند و جایی نمی روند.

۲)برآمدگی ها(ridges) : موجب "دنباله ای از ماکزیمم های محلی" می شوند که عبور از آن ها برای الگوریتم های حریصانه دشوار است

۳)فلات(plateaux) ناحیه ی همواری از دور نمای فضای حالت است فلات میتواند یک ماکزیمم محلی هموار باشد که هیچ خروجی به سمت بالا وجود نداردیا یک شانه باشد که از طریق آن می توان پیشروی کرد"جستجوی تپه نوردی ممکن است نتواند راه خروج را در فلات پیدا کند و مفقود شود
نکته : شانه معمولا همان فلات است که در نهایت به حالتی می رسد که می تواند در آن صعود داشته باشیم
شکل ۱-۴ صفحه ی ۱۴۸ از منبع مورد بررسی


نتیجه این که : در هر یک از موارد بالا الگوریتم به نقطه ای میرسد که پیشروی از ان ممکن نیست

نکته : اگر در الگوریتم تپه نوردی مقدار بعدی گره ها(مابعد ها ، پسین ها) با مقدار فعلی برابر باشد متوقف میشود.(یعنی حتی اگر ماکزیمم سراسری بعد از ان قرار داشته باشد توان پیدا کردنش را ندارد) سوال؟ آیا ادامه ی حرکت ایده ی خوبی نیست؟
بله هست، و ما در مسیر های فرعی اجازه ی حرکت میدهیم، دقت کنید که مسیر های فرعی را خود ما انتخاب میکنیم به این امید که فلات ها یک شانه باشند.(مسیر های فرعی را خود ما انتخاب میکنیم) ایده ی اجازه ی حرکت در صورت یافتن نقاط مساوی موجب میشود در ۹۴% موارد به موفقیت برسیم.
{فلسفه ی توسعه و اختراع شکل های مختلف الگوریتم تپه نوردی همین موضوع است} شامل :

۱)تپه نوردی اتفاقی(تصادفی) : به طور تصادفی حرکت هایی را به سمت بالای تپه انتخاب میکند(به انتخاب مسیر های فرعی فکر کنید) احتمال انتخاب می تواند بر اساس شیب دار بودن حرکت به سمت بالای تپه تغییر کند. (**) این روش نسبت به روش تیز ترین صعود(یا شیب){که نسخه ای از همان تپه نوردی عادی است} کندتر همگرا میشود ولی در بعضی از دور نماهای حالت جواب های بهتری را میابد.
نکته : کندتر همگرا :منظور سرعت کمتر در نزدیک شدن به هدف است

۲)روش تپه نوردی اولین انتخاب این روش نوعی از پیاده سازی تپه نوردی اتفاقی(تصادفی) است که پسین ها(مابعد ها) را به طور تصادفی تولید میکند تا اینکه یکی از آن ها بهتر از حالت فعلی باشد.اگر یک حالت دارای پسین های زیادی باشد این راهبرد مناسب است
نکته : دقت کنید اگر گراف فضای حالتی را داشته باشیم که پس از انتخاب نقطه ی فعلی ۱۰ همسایه باز شود(پسین ها) این ده همسایه به صورت تصادفی تولید میشوند و نه بر اساس احتمال های بهتر.

نکته ی مهم(**): الگوریتم های تپه نوردی که تا کنون شرح داده شدند"کامل" نیستند چون در ماکزیمم های محلی متوقف می شوند و با وجود هدف موفق به یافتن آن نمی شوند

۳)تپه نوردی با شروع مجدد تصادفی : دنباله ای از جستجو های تپه نوردی را از حالت های شروعی که به طور تصادفی تولید شده اند اجرا میکند تا هدفی را پیدا کند.به عبارت دیگر کار این الگوریتم اداره ی مجموعه ای از جستجو های تپه نوردی است که از حالت های شروع آغاز می کنند.
نکته مهم(**) : این الگوریتم با احتمال نزدیک به یک "کامل" است،زیرا سر انجام حالت هدف را به عنوان حالت شروع تولید میکند
نکته :این روش برای مساله ی ۸ وزیر کارامد تر از سایر روش ها است
=====
نکاتی که باید بدانید : (**)

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

۲) در مسائل NP که تعدا ماکزیمم های محلی "توانی" است پس از چند شروع مجدد تصادفی میتوان "ماکزیمم محلی" خوبی را پیدا کرد.

پایان بخش اول