دانلود, پاورپوینت, در مورد, هوش مصنوعی, ( فراتر, از جست و جوی کلاسیک,)

مشخصات فایل

عنوان :هوش مصنوعی

قالب بندی : پاورپوینت

تعداد اسلاید: ۳۴اسلاید

فهرست مطالب

هوش مصنوعی

عنوان های پاور پوینت  : 

 فصل چهارم فراتر از جست و جوی کلاسیک

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

دماغه

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

جست و جوی سخت سازی شبیه سازی شده

جستجوی پرتویی محلی

الگوریتم ژنتیک

مراحل الگوریتم ژنتیک

مثال الگوریتم ژنتیک روی ۸ وزیر

تکه های از این پروژه :

تا به حال همه الگوریتمها برون خطی بودند

برون خطی(Offline):راه حل قبل از اجرا مشخص است

درون خطی(Online):با یک در میان کردن محاسبات و فعالیت عمل میکند

جستجوی درون خطی در محیطهای پویا و نیمه پویا مفید است

آنچه را که باید واقعا اتفاق بیفتد، در نظر گرفته نمیشود

جست و جوی درون خطی ایده ضروری برای مسئله اکتشاف است

فعالیتها و حالتها برای عامل مشخص نیستند

مثال:قرار گرفتن روبات در محیطی جدید, نوزاد تازه بدنیا آمده

مقداردهی اولیه جمعیت

انتخاب یکسری از موجودات  جمعیت به منظور تولید جمعیت جدید

اعمال آمیزش و جهش روی موجودات انتخاب شده

ارزیابی جمعیت جدید

جایگزینی جمعیت قدیمی با جمعیت جدید

یک حالت بعدی با ترکیب دو حالت پدر ایجاد می شود.

شروع با k حالت تصادفی (جمعیت اولیه)

نمایش یک عضو جمعیت: کروموزوم

تابع ارزیابی: fitness function)) : هر حالت از جمعیت فعلی را ارزیابی  می کند و عددی تولید می کند.

نسل بعدی جمعیت با انجام اعمال زیر روی جمعیت فعلی تولید می شود:

انتخاب (selection)

آمیزش (crossover)

جهش (mutation)

به جای یک حالت، k حالت را نگهداری میکند

۱- حالت اولیه:شروع جستجو با k حالت تصادفی

۲- گام بعد: پسین همه k حالت تولید میشود

۳- اگر یکی از پسین ها هدف بود، تمام میشود

۴- وگر نه از بین k حالت اولیه و k حالت تولید شده، k حالت بهتر را انتخاب می کند و به مرحله ۲ برمی گردد

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

در جست و جوی شروع مجدد تصادفی، هر فرایند مستقل از بقیه اجرا میشود

در جست و جوی پرتو محلی، اطلاعات مفیدی بین k فرایند موازی مبادله میشود

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

ترکیبی از تپه نوردی با حرکت تصادفی

پیشروی مانند تپه نوردی می باشد، اما در هر مرحله حالت بعدی به طور  تصادفی انتخاب می شود.

اگر حالت بعدی انتخاب شده بهتر باشد، همواره به آن حالت بعدی خواهیم رفت.

در غیر این صورت، تنها با یک احتمال به آن حالت خواهیم رفت و این احتمال به صورت نمایی کاهش می یابد.

شبیه سازی حرارت:

در متالوژی، سخت سازی فرایندی است که برای آب دادن فلزات و شیشه ها به کار می رود. ابتدا آنها را با درجه بالا حرارت می دهند و سپس به تدریج آنها را سرد می کنند که به ماده اجازه می دهد به شکل مورد نظر دربیاید.

مقایسه با حرکت توپ

اگر توپ را رها کنیم تا قل بخورد، در یک کمینه محلی گیر می کند. اگر سطح را تکان دهیم می توانیم توپ را از کمینه محلی در بیاوریم. تکان مجدد باید به حدی باشد که توپ را از کمینه محلی در بیاورد ولی نتواند توپ را از کمینه اصلی (سراسری) خارج کند.

بنابراین

ابتدا تکان شدید به توپ می دهیم (دمای زیاد)

بتدریج تکان های کمتر (به دمای پایین تر)

مشکل اصلی تپه نوردی: بسته به حالت اولیه مسأله ممکن است در ماکزیمم محلی گیر کند.

تپه نوردی به دلایل زیر میتواند متوقف شود:

بیشینه محلی: قله ای است که از تمام همسایه ها بلندتر است اما از قله اصلی، کوتاهتر است.

دماغه ها (مانند شکل بعد): دنباله ای از بیشینه های محلی که عبور از آنها مشکل است.

فلات: ناحیه ای است که در آن، تابع ارزیاب، ثابت است. یعنی همسایه بهتر وجود ندارد. ممکن است نتواند راه عبور از فلات را بیابد.

انواع تپه نوردی:

تپه نوردی غیرقطعی،  تپه نوردی اولین انتخاب،  تپه نوردی شروع مجدد تصادفی

مثال: مسئله ۸ وزیر

مسئله ۸ وزیر با استفاده از فرمولبندی حالت کامل

در هر حالت ۸ وزیر در صفحه قرار دارند

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

تابع اکتشاف: جفت وزیرهایی که نسبت به هم گارد دارند

مستقیم یا غیر مستقیم

حلقه ای که در جهت افزایش مقدار حرکت میکند(بطرف بالای تپه)

رسیدن به بلندترین قله در همسایگی حالت فعلی، شرط خاتمه است.

ساختمان داده گره فعلی، فقط حالت و مقدار تابع هدف را نگه میدارد

جست و جوی محلی حریصانه نیز نام دارد

بدون فکر قبلی حالت همسایه خوبی را انتخاب میکند

تپه نوردی به دلایل زیر میتواند متوقف شود:

بیشینه محلی

برآمدگی ها

فلات

الگوریتم های قبلی، فضای جست و جو را به طور سیستماتیک بررسی میکنند

تا رسیدن به هدف یک یا چند مسیر نگهداری میشوند

مسیر رسیدن به هدف، راه حل مسئله را تشکیل میدهد

در بسیاری از مسائل بهینه سازی، مسیر راه حل اهمیت ندارد؛ خود حالت هدف پاسخ مسأله می باشد.

مانند ۸ وزیر

در چنین مواردی می توان از الگوریتم های جستجوی محلی بهره گرفت.

ایده جستجوی محلی: یک حالت (حالت فعلی) را در نظر بگیر، سعی کن آن را بهبود بخشی.

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

• مزایا:

– استفاده از حافظه بسیار کم

– یافتن راه حل های معقول در اغلب موارد در فضاهای حالت بزرگ و یا نامحدود

• مفید برای مسائل بهینه سازی محض

یافتن بهترین حالت بر طبق تابع هدف: (objective function)