بخشی از پاورپوینت
اسلاید 1 :
فصل 4: فراتر از جستجوی کلاسیک
اسلاید 2 :
مقدمه
در فصل قبل محیط های قابل مشاهده، قطعی و شناخته شده را بررسی کردیم که در آنها جواب دنباله ای از فعالیتها است
در این فصل بعضی از این فرضها را کنار میگذاریم.
الگوریتمهای جستجوی محلی:
وقتی فقط جواب مهم است و هزینه اهمیتی ندارد: 8 وزیر
جستجو در محیطهای غیرقطعی و به طور جزیی قابل مشاهده
جستجوی آنلاین: جستجو در محیطی که در ابتدا ناشناخته است.
اسلاید 3 :
الگوریتمهای جستجوی محلی
صرفاً جواب مهم است و راه رسیدن به آن مهم نیست.
صرفاً بر اساس حالت فعلی (به جای تکیه بر چند مسیر) عمل میکنند.
از حافظه کمی استفاده میکنند.
در فضاهای حالت بزرگ و نامتناهی جوابهای منطقی پیدا میکنند.
مسایل بهینه سازی: به جای یافتن هدف، تلاش در بهینه کردن تابع هدف است.
دورنمای فضای حالت:
فضای حالت +
تابع هدف
اسلاید 4 :
جست و جوی تپه نوردی
حلقه اي که در جهت افزايش مقدار حرکت ميکند(بطرف بالای تپه)
رسيدن به بلندترين قله در همسايگی حالت فعلی، شرط خاتمه است.
ساختمان داده گره فعلی، فقط حالت و مقدار تابع هدف را نگه ميدارد.
مثال: مسئله 8 وزير با استفاده از فرمولبندی حالت کامل
در هر حالت 8 وزير در صفحه قرار دارند
تابع جانشين: انتقال يک وزير به مربع ديگر در همان ستون
تابع اکتشافی: جفت وزيرهايي که نسبت به هم گارد دارند
اسلاید 5 :
جست و جوی تپه نوردی
حالت با هزينه h=17 که مقدار h را برای هر جانشين نشان ميدهد
کمينه محلی در فضای حالت 8 وزير؛ h=1
اسلاید 6 :
جست و جوی تپه نوردی
جست و جوی محلی حريصانه نيز نام دارد
بدون فکر قبلي حالت همسايه خوبي را انتخاب ميکند
تپه نوردی به دلايل زير ميتواند متوقف شود:
بيشينه محلي
برآمدگي ها
فلات
انواع دیگر تپه نوردی:
غيرقطعی: احتمالی
اولين انتخاب: اولین حالت پسین بهتر
شروع مجدد تصادفی: کامل است.
اسلاید 7 :
جست و جوی شبيه سازی حرارت
شبيه سازی حرارت: حرارت با درجه بالا و به تدريج سرد کردن
مقايسه با حرکت توپ
توپ در فرود از تپه به عميق ترين شکاف ميرود
با تکان دادن سطح توپ از بيشينه محلي خارج ميشود
در شروع با تکانهای شديد (دمای زياد)، بتدريج تکانهای کمتر (به دمای پايين تر)
این الگوریتم ترکیب حرکت تپه نوردی با حرکت تصادفی است.
تابع زمانبندی میزان تکانهای تصادفی را کنترل میکند.
اگر تابع زمانبندی T را به تدريج کاهش دهند، الگوريتم يک بهينه سراسری را با احتمال نزدیک به یک مي يابد.
اسلاید 8 :
جست و جوی پرتو محلي
به جای يک حالت، k حالت را نگهداری ميکند
حالت اوليه: k حالت تصادفی
گام بعد: جانشينهای همه k حالت توليد ميشود
اگر يکي از جانشين ها هدف بود، تمام ميشود
وگرنه بهترين جانشين را انتخاب کرده، تکرار ميکند
تفاوت عمده با k جستجوی شروع مجدد تصادفی
در جست و جوی شروع مجدد تصادفی، هر فرايند مستقل از بقيه اجرا ميشود
در جست و جوی پرتو محلی، اطلاعات مفيدی بين k فرايند موازی مبادله ميشود
جست و جوی پرتو غيرقطعی
مشکل پرتو محلی این است که سریع به سمت حالتهای بهتر متمرکز میشود.
به جای انتخاب بهترين k از جانشينها، k جانشين تصادفی را بطوريکه احتمال انتخاب يکي تابعی صعودی از مقدارش باشد، انتخاب ميکند.
اسلاید 9 :
الگوريتم های ژنتيک
شکلی از جست و جوی پرتو غير قطعی که حالتهای جانشين از طريق ترکيب دو حالت والد توليد ميشود
اسلاید 10 :
الگوريتم های ژنتيک
جمعیت
فرد
تابع برازش
پیوند
جهش
اسلاید 11 :
جست و جوی محلی در فضاهای پيوسته
گسسته در مقابل محيط های پيوسته
در فضاهای پيوسته، تابع جانشين در اغلب موارد، حالتهای نامتناهی را بر ميگرداند.
مثلاً میخواهیم در بین شش شهر سه فرودگاه ایجاد کنیم به طوریکه مجموع فاصله شهرها تا فرودگاهها حداقل باشد.
حل مسئله:
گسسته کردن همسايه هر حالت
استفاده از شيب (گرادیان)
اسلاید 12 :
شیب
با بهنگام سازی حالت فعلی با استفاده از فرمول زیر میتوان یک الگوریتم تپه نوردی حریصانه را اجرا کرد:
α: اندازه مرحله، در هر مرحله چقدر جلو برویم؟
اندازه مرحله کوچک: الگوریتم کند جلو میرود
اندازه مرحله بزرگ: از جواب رد میشویم.
اسلاید 13 :
جستجو با اقدامات غیرقطعی (جستجوی برخط)
تا کنون در همه الگوريتمها محیط قطعی و قابل مشاهده فرض میشد. در این حالت ادراک فقط برای درک حالت اولیه مفید است و پس از آن به درد نمیخورد.
در محیط غیرقطعی یا قابل مشاهده جزیی عامل در مجموعه ای از حالتهاست و ادراک عامل میتواند به کاهش این حالتها کمک کند.
اینجا دیگر جواب یک دنباله از اقدامات نیست بلکه یک طرح احتمالی است (استراتژی)
مثال: دنیای نامنظم جاروبرقی
عمل مکش به صورت زیر عمل میکند:
وقتی روی مربع کثیف اجرا میشود این مربع را تمیز میکند و گاهی مربع همجوار
را نیز تمیز میکند.
وقتی روی مربع تمیز اجرا میشود گاهی گرد و خاک را روی فرش جا میگذارد.
اینجا دیگر جواب دنبالۀ اقدام «مکش، راست، مکش» نیست
بلکه میتواند به شکل if های تودر تو باشد. (یک درخت)
اسلاید 14 :
درختهای AND-OR
در درختهای جستجو در محیط قطعی تنها انشعاب ممکن، انتخابهای عامل است (گره های OR)
اما در محیط غیرقطعی بر اثر انتخابهای محیط هم انشعاب ایجاد میشود. (گره AND)
یک جواب برای جستجوی AND-OR یک زیر درخت است که:
در هر گره برگ آن یک گره هدف وجود دارد.
در هر گره OR خود یک فعالیت را مشخص کرده باشد.
هر انشعاب ممکن را در گره AND خود قرار دهد.
اسلاید 15 :
الگوریتم جستجوی عمقی برای جستجوی گراف AND-OR
از سایر روشهای جستجو هم میتوان برای جستجوی درخت AND-OR استفاده کرد.
کاری که عامل میتواند انجام دهد
کاری که محیط ممکن است انجام دهد (یا بر اثر عدم قطعیت یا مشاهده جزیی.)
اسلاید 16 :
تلاش و تلاش دوباره
جواب عاری از چرخه ای از حالت 1 وجود ندارد.
اما جواب چرخه ای وجود دارد:
یا تا وقتی به حالت 5 برسی به راست برو
طرح چرخه ای جوابی (زیردرختی) است که هر گره برگ آن هدف باشد و از هر گره آن طرح مسیری به یک گره برگ وجود داشته باشد.
عاملی که یک طرح چرخه ای را اجرا کند بالاخره به جواب میرسد
به شرطی که هر خروجی ممکن از یک اقدام غیرقطعی بالاخره رخ دهد. (آیا همیشه اینطور است؟)
اسلاید 17 :
جستجو بدون مشاهده
عامل بدون حسگر است.
حالت باور: اعتقاد عامل با توجه به دنباله عملها و ادراکاتش درباره حالات فیزیکی (N)که میتواند در آنها باشد.
مثال: دنیای جاروبرقی بدون سنسور
در جستجوهای بدون مشاهده، جستجو به جای فضای حالت در فضای باور صورت میپذیرد.
اسلاید 18 :
تعریف مساله
اسلاید 19 :
پیشگویی باور
اسلاید 20 :
فضای حالت باور دنیای جاروبرقی-حالت قطعی
