بخشی از پاورپوینت
اسلاید 5 :
جست و جوی محلی (Local Search )
در این الگوریتم ها به جای اینکه مسیرهایی از حالت شروع را به طور سیستماتیک و منظم بررسی کنند. یک یا چند حالت فعلی را ارزیابی و اصلاح می کنند .
این الگوریتم ها برای مسئله هایی مفید هستند که در آن ها حالت جواب مهم است و هزینه مسیر دستیابی به حالت جواب ، اهمیتی ندارد
خانواده الگوریتم های جستجوی محلی ، شامل روش هایی است که از فیزیک آماری ( Simulated Annealing ) و زیست شناسی تکاملی ( الگوریتم های ژنتیک ) سرچشمه می گیرد .
الگوریتم های جستجوی محلی ، با استفاده از گره فعلی ( به جای چند مسیر ) عمل می کنند و فقط به همسایه آن گره منتقل می شوند .مسیر هایی که در جستجو ردیابی می شوند نگهداری نخواهند شد .
اسلاید 6 :
امتیاز الگوریتم های جستجوی محلی
1 ) از حافظه اندکی استفاده می کنند .
2 ) در فضاهای حالت بزرگ و نامتناهی که الگوریتم های سیستماتیک مفید نیستند ، جواب های منطقی را پیدا می کند .
الگوریتم های جست و جو محلی علاوه بر یافتن هدف ، برای حل مسئله بهینه سازی نیز مفید هستند . در این مسئله ها ، هدف یافتن بهترین حالت بر اساس تابع هدف است .
برای درک جست و جوی محلی ، دور نمای فضای حالت را در نظر می گیریم . دور نما هم داری مکان و هم دارای ارتفاع است . مکان با حالت تعریف می شود و ارتفاع توسط تابع هزینه ابتکاری یا تابع هدف تعریف می شود . اگر ارتفاع متناظر با هزینه باشد . هدف رسیدن به پایین ترین دره ، یا مینیمم سراسری است . اگر ارتفاع متناظر با تابع هدف باشد . آنگاه هدف یافتن بلندترین قله یا ماکزیمم سراسری است .
اسلاید 8 :
جستجوی تپه نوردی ( Hill- Climbing Search )
این الگوریتم ، حلقه ای است که در جهت افزایش مقدار حرکت می کند ( به طرف بالای تپه ) وقتی به قله ای رسید که هیچ همسایه ای از آن بلندتر نیست ، خاتمه می یابد .
الگوریتم جست و جوی تپه نوردی از ابتدایی ترین تکنیک جست و جوی محلی است . در هر مرحله ، گره فعلی با بهترین همسایه جایگزین می شود .
در این الگوریتم ، درخت جستجو را نگهداری نمی کند . لذا ساختمان داده گره فعلی فقط باید حالت و مقدار تابع هدف را نگهداری کند .
جست و جوی محلی حریصانه نام دارد . زیرا بدون اینکه قبلا فکر کند به کجا برود ، حالت همسایه خوبی را انتخاب می کند .
اسلاید 9 :
الگوریتم جست و جوی تپه نوردی
اسلاید 10 :
تپه نوردی به دلایل زیر متوقف می شود :
ماکزیمم محلی (Local Maxima )
قله ای که بلندتر از هر یک از همسایه هایش می باشد ، اما از ماکزیمم سراسری کوتاهتر است . الگوریتم تپه نورد که به مجاورت ماکزیمم محلی می رسد .به طرف بالا و به سمت قله حرکت می کند ، ولی متوقف می شود .
برآمدگی ها ( Ridges )
برآمدگی ها منجر به دنباله ای از ماکزیمم محلی می شود که عبور از آن برای الگوریتم حریصانه دشوار است .
اسلاید 11 :
تپه نوردی به دلایل زیر متوقف می شود :
فلات ( Plateaux )
فلات می تواند یک ماکزیمم محلی هموار باشد که هیچ خروجی به سمت بالا وجود ندارد . یا یک شانه باشد که از طریق آن می توان پیشروی کرد .
جستجوی تپه نورد ی ممکن است نتواند را خروج را در فلات پیدا کند و مفقود شود .
هر وقت که الگوریتم به یک ماکزیمم محلی هموار می رسد که شانه نیست ، یک حلقه تکرار بی نهایت به وجود خواهد آمد .
اسلاید 12 :
شکل های گوناگون تپه نوردی
تپه نوردی اتفاقی ( Stochastic hill climbing )
به طور تصادفی حرکت هایی را به سمت بالای تپه انتخاب می کند .
تپه نوردی اولین انتخاب ( First-Choice hill climbing )
تپه نوردی اتفاقی را به این صورت پیاده سازی می کند که پسین ها را به طور تصادفی تولید می کند تا اینکه از آنها بهتر از حالت فعلی باشد .
تپه نوردی با شروع مجدد تصادفی ( Random-Restart hill climbing )
این الگوریتم ، دنباله ای از جست و جوهای تپه نوردی را از حالت شروع تصادفی آغاز می کند و با رسیدن به هدف متوقف می شوند .
اسلاید 13 :
با احتمال نزدیک به 1، این الگوریتم کامل است .
برای مسئله 8 وزیر ، تپه نوردی با شروع مجدد تصادفی کارآمدتر است
موفقیت تپه نوردی به شکل دورنمای فضای حالت بستگی دارد . اگر تعداد ماکزیمم های محلی و فلات کم باشد ، تپه نوردی با شروع مجدد تصادفی ، سریعا راه حل خوبی را می یابد .
الگوریتم تپه نوردی و مساله 8 وزیر
الگوریتم های جست و جوی محلی معمولا از فرموله کردن حالت کامل استفاده می کنند .که در هر حالت 8 وزیر در صفحه قرار دارند. به طوری که در هر ستون یک وزیر است .
اسلاید 14 :
الگوریتم تپه نوردی و مساله 8 وزیر
پسین های یک حالت ، تمام حالت های ممکنی هستند که با انتقال یک وزیر به مربع دیگری در همان ستون تولید می شود.
هر حالت 7 * 8 = 56 اعداد پسین دارد .
تابع هزینه ابتکاری h : تعداد جفت هایی از وزیران است که به طور مستقیم یا غیر مستقیم به یکدیگر گارد می دهند .
اسلاید 15 :
h=17 h=1
اسلاید 16 :
Simulated Annealing
الگوریتم متشکل است از تپه نوردی با حرکت تصادفی ،که کارآمد و کامل باشد .
درمتالوژی annealing فرآیندی است که فلز های سخت و شیشه را با درجه بالایی حرارت می دهند و سپس آن ها را به تدریج سرد می کنند به این ترتیب مواد به حالت کریستالی با انرژی پایین در می آیند .
مقایسه با حرکت توپ
در فرود توپ از تپه به عمیق ترین شکاف می رود .
با تکان دادن سطح ف توپ از ماکزیمم محلی خارج میشود .
با تکان شدید شروع می کند ( دمای زیاد )
به تدریج تکان کاهش ( به دمای پایین تر )
اسلاید 17 :
Simulated Annealing
اسلاید 18 :
Simulated Annealing
داخلی ترین حلقه الگوریتم Simulated Annealing شبیه تپه نوردی است .
به جای انتخاب بهترین حرکت ، یک حرکت تصادفی را انتخاب می کند اگر این حرکت ، وضعیت را بهبود بخشید همواره قابل قبول است .و گرنه الگوریتم حرکت را با احتمال کمتر از 1 می پذیرد . ( بر خلاف تپه نوردی )
در اين گروه از الگوريتمها به جاي شروع دوباره به طور تصادفي، زماني که در يک ماکزيمم محلي گير افتاديم، ميتوانيم اجازه دهيم که جستجو چند قدم به طرف پائين بردارد تا از ماکزيمم محلي فرار کند.
اسلاید 19 :
جست و جوی پرتومحلی ( Local Beam Search )
الگوریتم جست و جوی پرتو محلی به جای یک حالت ، K حالت را نگهداری می کند .
مرحله 1) این الگوریتم با K حالت که به طور تصادفی تولید شده اند ،شروع می کند .
مرحله 2 ( در هر مرحله ، تمام پسین های همه ی حالت ها تولید می شوند .
اگر یکی از آنها هدف بود ، الگوریتم متوقف می شود.
در غیر این صورت ، بهترین پسین انتخاب و عمل تکرار می شود .
اسلاید 20 :
تفاوت جست و جوی پرتو محلی با شروع مجدد تصادفی
در جست و جوی شروع مجدد تصادفی هر فرآیند جست و جو مستقل از بقیه اجرا می شود .
در جست و جوی پرتو محلی ، اطلاعات مفیدی بین K فرآیند جست و جوی موازی مبادله می شود .
معایب جست و جوی پرتو محلی
مشکل جست و جوی پرتو محلی این است که K حالت تنوع زیادی ندارد. ممکن است سریعا در یک منطقه کوچک از فضای حالت متمرکز شوند .
جست و جوی پرتو اتفاقی
به جای انتخاب بهترین K ، K پسین را به طور تصادفی نتخاب می کند .به طوری که احتمال انتخاب یک پسین ، یک تابع صعودی از مقادیرش است .
