Artificial Intelligence
هوش مصنوعی
Chapter 4
استوارت راسل-پیتر نورویگ
فصل چهارم فراتر از جست و جوی کلاسیک
الگوریتم های جستجوی محلی
الگوریتم های قبلی، فضای جست و جو را به طور سیستماتیک بررسی میکنند
تا رسیدن به هدف یک یا چند مسیر نگهداری میشوند
مسیر رسیدن به هدف، راه حل مسئله را تشکیل میدهد
در بسیاری از مسائل بهینه سازی، مسیر راه حل اهمیت ندارد؛ خود حالت هدف پاسخ مساله می باشد.
مانند 8 وزیر
در چنین مواردی می توان از الگوریتم های جستجوی محلی بهره گرفت.
ایده جستجوی محلی: یک حالت (حالت فعلی) را در نظر بگیر، سعی کن آن را بهبود بخشی.
جستجوی محلی = استفاده از یک حالت فعلی و حرکت به حالت های همسایه
• مزایا:
– استفاده از حافظه بسیار کم
– یافتن راه حل های معقول در اغلب موارد در فضاهای حالت بزرگ و یا نامحدود
• مفید برای مسائل بهینه سازی محض
یافتن بهترین حالت بر طبق تابع هدف: (objective function)
الگوریتم های جست و جوی محلی و بهینه سازی
الگوریتم های جستجوی محلی
5
جست و جوی تپه نوردی
حلقه ای که در جهت افزایش مقدار حرکت میکند(بطرف بالای تپه)
رسیدن به بلندترین قله در همسایگی حالت فعلی، شرط خاتمه است.
ساختمان داده گره فعلی، فقط حالت و مقدار تابع هدف را نگه میدارد
جست و جوی محلی حریصانه نیز نام دارد
بدون فکر قبلی حالت همسایه خوبی را انتخاب میکند
تپه نوردی به دلایل زیر میتواند متوقف شود:
بیشینه محلی
برآمدگی ها
فلات
6
انواع تپه نوردی:
تپه نوردی غیرقطعی، تپه نوردی اولین انتخاب، تپه نوردی شروع مجدد تصادفی
مثال: مسئله 8 وزیر
مسئله 8 وزیر با استفاده از فرمولبندی حالت کامل
در هر حالت 8 وزیر در صفحه قرار دارند
تابع جانشین: انتقال یک وزیر به مربع دیگر در همان ستون
تابع اکتشاف: جفت وزیرهایی که نسبت به هم گارد دارند
مستقیم یا غیر مستقیم
جست و جوی تپه نوردی
8
جست و جوی آگاهانه و اکتشاف
مثال جست و جوی تپه نوردی
الف- حالت با هزینه h=17 که مقدار h را برای هر جانشین نشان میدهد
ب- کمینه محلی در فضای حالت 8 وزیر؛ h=1
الف
ب
جست و جوی تپه نوردی
مشکل اصلی تپه نوردی: بسته به حالت اولیه مساله ممکن است در ماکزیمم محلی گیر کند.
تپه نوردی به دلایل زیر میتواند متوقف شود:
بیشینه محلی: قله ای است که از تمام همسایه ها بلندتر است اما از قله اصلی، کوتاهتر است.
دماغه ها (مانند شکل بعد): دنباله ای از بیشینه های محلی که عبور از آنها مشکل است.
فلات: ناحیه ای است که در آن، تابع ارزیاب، ثابت است. یعنی همسایه بهتر وجود ندارد. ممکن است نتواند راه عبور از فلات را بیابد.
دماغه
حالت فعلی، هر کدام از دایره های مشکی می باشند
جست و جوی تپه نوردی
انواع تپه نوردی
تپه نوردی اتفاقی
به طور تصادفی از میان حرکت های رو به بالا یکی را انتخاب می کند. احتمال این انتخاب می تواند بر اساس شیب حرکت های رو به بالا تغییر کند.
تپه نوردی اولین گزینه
اگر یک همسایه بهتر از حالت فعلی باشد به سمت آن حرکت می کند و به بررسی دیگر همسایه ها نمی پردازد (پس بهترین همسایه را انتخاب نمی کند)
تپه نوردی با شروع مجدد تصادفی
چند حالت شروع تصادفی در نظر می گیرد و جستجو را در اطراف تک تک آنها انجام می دهد. هنگامی که یک هدف پیدا شد متوقف می شود.
موفقیت تپه نوردی بستگی به دورنمای فضای حالت دارد
اگر تعداد کمی بیشینه محلی و فلات وجود داشته باشد، تپه نوردی با شروع مجدد تصادفی خیلی سریع یک راه حل خوب پیدا می کند.
جست و جوی سخت سازی شبیه سازی شده
ایده: از بهینه های محلی، با انجام حرکت های بد، فرار کن. اما به تدریج اندازه و تعداد حرکات بد را کم کن.
ترکیبی از تپه نوردی با حرکت تصادفی
پیشروی مانند تپه نوردی می باشد، اما در هر مرحله حالت بعدی به طور تصادفی انتخاب می شود.
اگر حالت بعدی انتخاب شده بهتر باشد، همواره به آن حالت بعدی خواهیم رفت.
در غیر این صورت، تنها با یک احتمال به آن حالت خواهیم رفت و این احتمال به صورت نمایی کاهش می یابد.
شبیه سازی حرارت:
در متالوژی، سخت سازی فرایندی است که برای آب دادن فلزات و شیشه ها به کار می رود. ابتدا آنها را با درجه بالا حرارت می دهند و سپس به تدریج آنها را سرد می کنند که به ماده اجازه می دهد به شکل مورد نظر دربیاید.
مقایسه با حرکت توپ
اگر توپ را رها کنیم تا قل بخورد، در یک کمینه محلی گیر می کند. اگر سطح را تکان دهیم می توانیم توپ را از کمینه محلی در بیاوریم. تکان مجدد باید به حدی باشد که توپ را از کمینه محلی در بیاورد ولی نتواند توپ را از کمینه اصلی (سراسری) خارج کند.
بنابراین
ابتدا تکان شدید به توپ می دهیم (دمای زیاد)
بتدریج تکان های کمتر (به دمای پایین تر)
جستجوی پرتویی محلی
به جای یک حالت، k حالت را نگهداری میکند
1- حالت اولیه:شروع جستجو با k حالت تصادفی
2- گام بعد: پسین همه k حالت تولید میشود
3- اگر یکی از پسین ها هدف بود، تمام میشود
4- وگر نه از بین k حالت اولیه و k حالت تولید شده، k حالت بهتر را انتخاب می کند و به مرحله 2 برمی گردد
تفاوت عمده با جستجوی شروع مجدد تصادفی
در جست و جوی شروع مجدد تصادفی، هر فرایند مستقل از بقیه اجرا میشود
در جست و جوی پرتو محلی، اطلاعات مفیدی بین k فرایند موازی مبادله میشود
الگوریتم های ژنتیک
شکلی از جست و جوی پرتویی که حالتهای جانشین از طریق ترکیب دو حالت والد تولید میشود
الگوریتم ژنتیک
یک حالت بعدی با ترکیب دو حالت پدر ایجاد می شود.
شروع با k حالت تصادفی (جمعیت اولیه)
نمایش یک عضو جمعیت: کروموزوم
تابع ارزیابی: fitness function)) : هر حالت از جمعیت فعلی را ارزیابی می کند و عددی تولید می کند.
نسل بعدی جمعیت با انجام اعمال زیر روی جمعیت فعلی تولید می شود:
انتخاب (selection)
آمیزش (crossover)
جهش (mutation)
مراحل الگوریتم ژنتیک
مقداردهی اولیه جمعیت
انتخاب یکسری از موجودات جمعیت به منظور تولید جمعیت جدید
اعمال آمیزش و جهش روی موجودات انتخاب شده
ارزیابی جمعیت جدید
جایگزینی جمعیت قدیمی با جمعیت جدید
مثال الگوریتم ژنتیک روی 8 وزیر
مثال الگوریتم ژنتیک روی 8 وزیر
29
جست و جوی آگاهانه و اکتشاف
جست و جوی محلی در فضاهای پیوسته
گسسته در مقابل محیط های پیوسته
در فضاهای پیوسته، تابع جانشین در اغلب موارد، حالتهای نامتناهی را بر میگرداند
حل مسئله:
گسسته کردن همسایه هر حالت
استفاده از شیب منظره
روش نیوتن رافسون
30
جست و جوی آگاهانه و اکتشاف
عاملهای جست و جوی Online و محیطهای ناشناخته
تا به حال همه الگوریتمها برون خطی بودند
برون خطی(Offline):راه حل قبل از اجرا مشخص است
درون خطی(Online):با یک در میان کردن محاسبات و فعالیت عمل میکند
جستجوی درون خطی در محیطهای پویا و نیمه پویا مفید است
آنچه را که باید واقعا اتفاق بیفتد، در نظر گرفته نمیشود
جست و جوی درون خطی ایده ضروری برای مسئله اکتشاف است
فعالیتها و حالتها برای عامل مشخص نیستند
مثال:قرار گرفتن روبات در محیطی جدید, نوزاد تازه بدنیا آمده
31
جست و جوی آگاهانه و اکتشاف
مسئله های جست و جوی Online
اطلاعات عامل
Actions(s): لیستی از فعالیتهای مجاز در حالت s
تابع هزینه مرحله ای c(s,a,s’): استفاده وقتی که بداند s’ نتیجه است
Goal-Test(s): آزمون هدف
عامل حالت ملاقات شده قبلی را تشخیص میدهد
فعالیتها قطعی اند
دسترسی به تابع اکتشافی قابل قبول h(s)
32
جست و جوی آگاهانه و اکتشاف
مسئله های جست و جوی Online
هدف: رسیدن به G با کمترین هزینه
هزینه: مجموع هزینه های مراحل مسیری است که عامل طی میکند
نسبت رقابتی: مقایسه هزینه با هزینه مسیری که اگر عامل فضای حالت را از قبل میشناخت، طی میکرد
در بعض موارد، بهترین نسبت رقابتی
نامتناهی است
ممکن است جستجو به یک حالت
بن بست برسد که نتوان از طریق آن به هدف رسید
33
جست و جوی آگاهانه و اکتشاف
مسئله های جست و جوی Online
دو فضای حالت که عامل جست و جوی Online را به بن بست میرسانند. هر عاملی حداقل در یکی از این دو فضا شکست می خورد
34
جست و جوی آگاهانه و اکتشاف
مسئله های جست و جوی Online
یک محیط دو بعدی که موجب میشود عامل جست و جویOnline مسیر دلخواه ناکارآمدی را برای رسیدن به هدف حل کند