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

بخشی از پاورپوینت

اسلاید 1 :

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

اسلاید 3 :

جستجو تپه نوردی

اسلاید 5 :

جستجو تپه نوردی

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

اسلاید 6 :

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

Function HILL-CLIMBING (problem)returns a solution
Input: problem; problem
Local variable: current, next;node
Current MAKE-NODE (INITIAL- STATE [problem])
Loop do
next  a highest valued successor of current
If value [next] Current  next
end
تپه نوردی با تندترین شیب

اسلاید 7 :

۸ وزیر در ۸۶%  حالات در ماکزیمم محلی گیر میکند
Search space = 88
اگر زمانی که به فلات رسیدیم الگوریتم را متوقف نکنیم و تا یک زمانی ادامه دهیم که در لوپ هم نیفتیم. آنگاه ۱۴% موفقیت در رسیدن به جواب (۸ وزیر ) تبدیل به ۹۴% میشود. این نشان میدهد که مساله ۸ وزیر زیاد در فلات گیر میوافتد
زمانی هم که به جواب میرسیم بطور متوسط ۲۱ حرکت میکنیم

اسلاید 8 :

تپه نوردی تصادفی

اسلاید 10 :

تپه نوردی اولین انتخاب

این راهبرد زمانی مناسب است که یک حالت دارای تعداد زیادی پسین باشد، مثلا ۱۰۰۰ تا

اسلاید 11 :

تپه نوردی اولین انتخاب

اسلاید 12 :

تپه  نوردی با شروع مجدد تصادفی

اسلاید 13 :

تپه  نوردی با شروع مجدد تصادفی

ایده این است که اگر بگوییم احتمال یک کاری1/p است. چند بار باید به طور متوسط تکرارش کنیم تا به جواب برسیم؟ حتما P بار.
در مساله تپه نوردی با تندترین شیب گفتیم که ۱۴% احتمال موفقیت داریم. پس اگر به طور متوسط ۷ بار (۱۰۰/۱۴) از اول با شروعِ تصادفی مساله رو با تپه نوردی تندترین شیب حل کنم به جواب خواهم رسید

اسلاید 15 :

نتیجه گیری

الگوریتمهای جستجو محلی به حفظ کمی نیاز دارند. چرا؟
اصولاً سعی میکنند مساله را از حالت عادی بهینه تر کنند. آیا ممکن است به هدف نرسیم؟
با این حال برای مسائل بهینه سازی بسیار کاربرد دارد، زمانی که هدف را نمیدانیم و دنبال یافتن آن هستیم. مثلا رئیسِ یک شرکت به دنبال راه کاری برای افزایش سود شرکت هست. بهترین سود چه عددی است؟ نمیدانیم.
اصولاً در الگوریتمهای جستجوی محلی یک تابع هدف داریم که بهتر بودن وضعیت را به ما میگوید. (مقدار خوب بودن گره)

اسلاید 16 :

Simulated Annealing

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

اسلاید 17 :

شبه  کد شبیه سازی ذوب فلزات

تابع نزولی
اگر شیب کم شدن زمان کم باشد میتوان ثابت کرد که با احتمال بسیار زیاد به ماکزیمم مطلق میرسیم

اسلاید 18 :

Local beam search

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

ممکن است بگویید چه فرقی کرد؟ ما اگر الگوریتم تپه نوردی را بارk تکرار کنیم تبدیل به پرتو محلی میشود. در حالی که اینطور نیست

اسلاید 19 :

Local beam search

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

اسلاید 20 :

Stochastic beam search

ایده عین تپه نوردی تصادفی است. kحالت جدید بر اساس احتمال انتخاب میشوند یعنی از بینk.y   تا حالت بهترینها(k) بر اساس احتمال خوبیتشان انتخاب میشوند

اصولاً روشهای تصادفی احتمال همگرا شدن به جواب بهینه را بیشتر تضمین میکنند اگرچه ممکن است در سرعت همگرا شدن کند تر باشند